meditationatae

Just another WordPress.com site

HEA in Duet and graph coloring (continuation)

There were some mistakes and some inefficiencies in my C implementation of the HEAD’ variation of HEA in Duet of Moalic and Gondran (please see previous post). In their arxiv preprint, they propose a hybrid evolutionary algorithm for graph coloring which is really quite sophisticated, and building on earlier work of Galinier and Hao, among others.

HEAD’ uses tabu search and the GPX greedy partitioning crossover introduced by Galinier and Hao in 1999. Moalic and Gondran use a population size of two. HEAD’ is the most straightforward method, while HEAD builds on HEAD’ and adds “elite configurations”; a configuration is a proper or improper coloring of a graph for an instance of graph k-coloring, for instance for the graph DSJC500.5 for k = 47 colors. The “elite colorings” are kept in memory to introduce diversity to the population of two, when needed.

I’ve been working on implementing the simpler evolutionary algorithm HEAD’, the first one discussed.

I had 14 improper 48-colorings, that is colorings with some edges with vertices of the same color for the DIMACS challenge graph from the challenge around 1993-1994 constructed by the theoretical computer scientist David S. Johnson, and known variously as DSJC500.5 and DSJC500.5.col , having 500 vertices and over 62,000 edges.

I paired these 14 improper 48-colorings in 7 pairs of two. Then, following the paper/preprint of Moalic and Gondran, I let each pair run for up to 1000 generations according to the algorithm HEAD’, doing 8000 tabu local search iterations on each configuration in a pair, between “crossovers”, i.e. applying the GPX crossover operator to two “parents” so as to yield two “offspring”, one: GPX( P1, P2) , and the other: GPX(P2, P1) .

The pairs are identified by the numbers 0 to 6.

I find that 3 of the seven pairs evolved to give proper 48-colorings, i.e. 48-colorings of DSJC500.5.col .

The vertices are numbered 1 to 500, and the colors 1 to 48:

num_pair = 0
num_generation = 182
1 28
2 12
3 5
4 41
5 22
6 10
7 2
8 39
9 16
10 41
11 48
12 21
13 13
14 48
15 35
16 45
17 34
18 8
19 47
20 43
21 17
22 1
23 7
24 24
25 6
26 21
27 10
28 45
29 18
30 6
31 7
32 9
33 5
34 46
35 40
36 33
37 39
38 32
39 36
40 44
41 16
42 14
43 42
44 11
45 37
46 30
47 10
48 24
49 37
50 12
51 18
52 23
53 32
54 15
55 3
56 14
57 30
58 8
59 37
60 11
61 43
62 47
63 6
64 33
65 17
66 4
67 32
68 19
69 29
70 12
71 41
72 4
73 36
74 31
75 18
76 22
77 22
78 36
79 25
80 21
81 28
82 24
83 11
84 29
85 29
86 41
87 28
88 26
89 21
90 16
91 11
92 6
93 22
94 23
95 16
96 26
97 37
98 1
99 37
100 13
101 20
102 22
103 30
104 23
105 32
106 30
107 20
108 37
109 46
110 4
111 26
112 19
113 36
114 16
115 28
116 47
117 48
118 19
119 12
120 37
121 1
122 27
123 19
124 46
125 44
126 38
127 11
128 22
129 40
130 3
131 20
132 46
133 6
134 26
135 3
136 41
137 3
138 33
139 48
140 5
141 30
142 7
143 9
144 32
145 11
146 29
147 21
148 24
149 4
150 13
151 42
152 38
153 17
154 1
155 14
156 7
157 15
158 41
159 9
160 20
161 3
162 13
163 24
164 47
165 29
166 34
167 2
168 27
169 44
170 43
171 32
172 12
173 7
174 12
175 2
176 31
177 42
178 27
179 45
180 41
181 20
182 45
183 11
184 17
185 35
186 29
187 42
188 25
189 30
190 3
191 23
192 1
193 29
194 15
195 6
196 4
197 33
198 12
199 15
200 44
201 42
202 27
203 39
204 1
205 6
206 19
207 24
208 26
209 1
210 26
211 18
212 12
213 2
214 27
215 14
216 14
217 22
218 13
219 12
220 2
221 34
222 43
223 25
224 12
225 34
226 45
227 21
228 33
229 10
230 35
231 26
232 34
233 47
234 9
235 27
236 35
237 15
238 23
239 17
240 18
241 18
242 7
243 34
244 3
245 18
246 16
247 15
248 30
249 38
250 9
251 28
252 25
253 47
254 31
255 44
256 21
257 12
258 2
259 31
260 47
261 32
262 13
263 29
264 48
265 8
266 1
267 32
268 14
269 41
270 9
271 18
272 9
273 5
274 34
275 23
276 47
277 14
278 23
279 19
280 41
281 17
282 42
283 33
284 40
285 36
286 15
287 45
288 2
289 8
290 32
291 10
292 1
293 19
294 6
295 36
296 38
297 26
298 25
299 5
300 4
301 10
302 9
303 15
304 4
305 31
306 7
307 2
308 28
309 38
310 29
311 28
312 46
313 22
314 26
315 39
316 19
317 16
318 13
319 31
320 28
321 45
322 10
323 20
324 32
325 5
326 27
327 4
328 4
329 22
330 44
331 27
332 2
333 29
334 22
335 4
336 28
337 44
338 46
339 16
340 10
341 35
342 21
343 38
344 37
345 25
346 27
347 11
348 17
349 30
350 10
351 38
352 30
353 36
354 14
355 23
356 19
357 40
358 20
359 15
360 1
361 3
362 46
363 48
364 9
365 20
366 8
367 38
368 3
369 28
370 43
371 9
372 17
373 24
374 9
375 35
376 30
377 27
378 42
379 18
380 47
381 25
382 8
383 32
384 39
385 32
386 40
387 43
388 20
389 2
390 40
391 21
392 38
393 2
394 4
395 44
396 18
397 11
398 45
399 21
400 24
401 29
402 25
403 18
404 6
405 15
406 31
407 39
408 1
409 25
410 39
411 24
412 24
413 40
414 35
415 28
416 7
417 46
418 39
419 27
420 8
421 6
422 17
423 4
424 8
425 33
426 9
427 8
428 13
429 38
430 23
431 3
432 22
433 31
434 5
435 35
436 24
437 6
438 25
439 44
440 43
441 13
442 48
443 26
444 1
445 39
446 33
447 16
448 14
449 14
450 4
451 35
452 21
453 7
454 45
455 34
456 3
457 1
458 25
459 3
460 31
461 25
462 16
463 19
464 42
465 5
466 5
467 13
468 35
469 17
470 8
471 42
472 3
473 7
474 31
475 26
476 2
477 19
478 43
479 8
480 6
481 44
482 43
483 12
484 23
485 2
486 46
487 5
488 13
489 33
490 48
491 40
492 11
493 7
494 7
495 33
496 8
497 16
498 23
499 14
500 15

num_pair = 2
num_generation = 84
1 4
2 29
3 13
4 27
5 19
6 36
7 1
8 21
9 6
10 13
11 12
12 22
13 19
14 10
15 48
16 27
17 20
18 27
19 29
20 4
21 31
22 5
23 20
24 13
25 20
26 26
27 26
28 20
29 46
30 30
31 16
32 7
33 18
34 46
35 39
36 14
37 10
38 25
39 38
40 32
41 6
42 8
43 16
44 41
45 41
46 40
47 40
48 23
49 8
50 31
51 10
52 10
53 25
54 14
55 3
56 38
57 4
58 32
59 33
60 11
61 9
62 45
63 4
64 12
65 34
66 44
67 40
68 10
69 45
70 40
71 13
72 2
73 15
74 35
75 27
76 10
77 31
78 32
79 4
80 17
81 20
82 12
83 38
84 19
85 45
86 21
87 22
88 43
89 26
90 16
91 31
92 41
93 46
94 30
95 36
96 9
97 2
98 5
99 48
100 42
101 28
102 19
103 39
104 44
105 45
106 42
107 4
108 30
109 47
110 33
111 16
112 16
113 21
114 30
115 18
116 12
117 19
118 28
119 19
120 33
121 5
122 8
123 44
124 41
125 9
126 31
127 24
128 13
129 24
130 3
131 4
132 43
133 37
134 36
135 3
136 37
137 3
138 14
139 46
140 48
141 2
142 17
143 27
144 25
145 36
146 8
147 16
148 9
149 6
150 47
151 10
152 35
153 29
154 5
155 30
156 18
157 29
158 22
159 6
160 40
161 3
162 42
163 29
164 44
165 24
166 12
167 1
168 8
169 25
170 16
171 13
172 6
173 17
174 19
175 1
176 36
177 7
178 8
179 11
180 21
181 4
182 22
183 4
184 45
185 15
186 15
187 29
188 27
189 47
190 3
191 44
192 5
193 6
194 43
195 13
196 42
197 32
198 2
199 7
200 31
201 48
202 7
203 8
204 5
205 41
206 15
207 48
208 29
209 5
210 14
211 43
212 6
213 1
214 31
215 9
216 16
217 4
218 12
219 26
220 1
221 43
222 37
223 33
224 21
225 19
226 25
227 34
228 44
229 28
230 47
231 32
232 40
233 23
234 6
235 30
236 9
237 27
238 45
239 29
240 28
241 41
242 7
243 6
244 3
245 28
246 31
247 34
248 20
249 43
250 39
251 7
252 7
253 38
254 23
255 30
256 46
257 40
258 1
259 36
260 24
261 25
262 8
263 20
264 23
265 11
266 5
267 25
268 30
269 13
270 14
271 28
272 15
273 37
274 24
275 44
276 13
277 14
278 39
279 41
280 11
281 47
282 11
283 26
284 39
285 35
286 17
287 45
288 1
289 34
290 26
291 40
292 5
293 28
294 21
295 15
296 22
297 16
298 33
299 39
300 2
301 28
302 27
303 27
304 2
305 36
306 31
307 1
308 9
309 35
310 37
311 34
312 23
313 10
314 7
315 24
316 7
317 11
318 35
319 47
320 7
321 32
322 34
323 18
324 22
325 12
326 27
327 2
328 2
329 24
330 18
331 11
332 1
333 12
334 28
335 2
336 17
337 19
338 9
339 18
340 35
341 25
342 17
343 22
344 30
345 10
346 19
347 11
348 10
349 25
350 34
351 39
352 15
353 21
354 22
355 2
356 15
357 35
358 16
359 13
360 5
361 3
362 23
363 23
364 14
365 32
366 45
367 46
368 3
369 42
370 42
371 11
372 39
373 18
374 47
375 33
376 33
377 31
378 12
379 36
380 13
381 47
382 41
383 16
384 29
385 15
386 27
387 10
388 21
389 1
390 8
391 33
392 9
393 1
394 40
395 41
396 16
397 13
398 37
399 23
400 33
401 2
402 4
403 19
404 35
405 47
406 25
407 7
408 5
409 23
410 8
411 32
412 9
413 26
414 11
415 30
416 41
417 38
418 48
419 4
420 22
421 29
422 39
423 2
424 42
425 46
426 14
427 32
428 37
429 26
430 44
431 3
432 41
433 48
434 8
435 14
436 24
437 43
438 18
439 9
440 20
441 18
442 23
443 14
444 5
445 18
446 12
447 20
448 33
449 38
450 2
451 11
452 17
453 28
454 15
455 34
456 3
457 5
458 7
459 3
460 4
461 47
462 14
463 23
464 38
465 12
466 37
467 25
468 48
469 42
470 17
471 40
472 3
473 14
474 47
475 11
476 1
477 15
478 32
479 28
480 18
481 26
482 48
483 37
484 22
485 1
486 9
487 15
488 8
489 12
490 42
491 26
492 46
493 34
494 21
495 17
496 35
497 20
498 10
499 22
500 21

num_pair = 4
num_generation = 69
1 43
2 48
3 24
4 44
5 32
6 9
7 2
8 29
9 14
10 17
11 5
12 10
13 28
14 8
15 15
16 5
17 39
18 47
19 6
20 34
21 25
22 27
23 40
24 19
25 26
26 35
27 21
28 35
29 29
30 33
31 31
32 38
33 3
34 33
35 41
36 26
37 8
38 24
39 15
40 18
41 20
42 25
43 48
44 45
45 42
46 15
47 12
48 24
49 47
50 35
51 8
52 8
53 45
54 11
55 13
56 12
57 13
58 33
59 5
60 39
61 20
62 46
63 4
64 5
65 6
66 22
67 12
68 8
69 30
70 29
71 19
72 1
73 28
74 43
75 44
76 8
77 35
78 20
79 4
80 38
81 39
82 36
83 37
84 43
85 26
86 47
87 29
88 28
89 43
90 39
91 3
92 42
93 34
94 11
95 31
96 11
97 1
98 23
99 4
100 7
101 25
102 43
103 21
104 28
105 19
106 22
107 13
108 6
109 16
110 17
111 48
112 45
113 15
114 21
115 42
116 5
117 9
118 20
119 17
120 41
121 27
122 12
123 14
124 14
125 13
126 46
127 42
128 34
129 46
130 25
131 40
132 24
133 40
134 44
135 43
136 17
137 16
138 4
139 30
140 22
141 1
142 36
143 26
144 25
145 3
146 47
147 6
148 9
149 33
150 7
151 8
152 13
153 36
154 27
155 37
156 41
157 21
158 10
159 16
160 46
161 11
162 5
163 31
164 6
165 31
166 9
167 2
168 48
169 16
170 48
171 19
172 14
173 44
174 9
175 2
176 21
177 7
178 38
179 36
180 19
181 46
182 10
183 30
184 23
185 23
186 4
187 14
188 44
189 32
190 12
191 16
192 16
193 12
194 47
195 24
196 6
197 5
198 1
199 44
200 18
201 41
202 16
203 48
204 27
205 37
206 22
207 35
208 31
209 27
210 22
211 11
212 18
213 2
214 32
215 47
216 34
217 28
218 15
219 3
220 2
221 37
222 17
223 15
224 23
225 9
226 46
227 39
228 4
229 3
230 35
231 18
232 37
233 18
234 24
235 32
236 23
237 25
238 37
239 5
240 25
241 14
242 11
243 33
244 11
245 44
246 38
247 24
248 12
249 30
250 20
251 35
252 23
253 45
254 23
255 40
256 22
257 48
258 2
259 7
260 6
261 39
262 28
263 44
264 40
265 15
266 37
267 9
268 21
269 19
270 26
271 25
272 3
273 30
274 22
275 30
276 4
277 11
278 28
279 42
280 13
281 43
282 36
283 48
284 32
285 42
286 36
287 34
288 2
289 6
290 17
291 27
292 27
293 33
294 46
295 3
296 10
297 17
298 4
299 22
300 1
301 25
302 3
303 21
304 1
305 25
306 46
307 2
308 43
309 36
310 26
311 26
312 30
313 8
314 47
315 44
316 9
317 26
318 36
319 29
320 16
321 35
322 39
323 32
324 32
325 10
326 48
327 1
328 1
329 13
330 20
331 12
332 2
333 34
334 42
335 1
336 37
337 29
338 33
339 20
340 38
341 15
342 22
343 10
344 21
345 8
346 42
347 20
348 8
349 16
350 15
351 12
352 28
353 18
354 10
355 1
356 38
357 40
358 16
359 31
360 14
361 4
362 24
363 13
364 11
365 47
366 20
367 32
368 11
369 40
370 19
371 26
372 5
373 31
374 38
375 15
376 22
377 46
378 7
379 45
380 21
381 29
382 14
383 41
384 31
385 10
386 6
387 8
388 32
389 2
390 17
391 33
392 6
393 2
394 37
395 41
396 19
397 19
398 36
399 21
400 7
401 1
402 27
403 25
404 26
405 29
406 39
407 9
408 27
409 24
410 38
411 33
412 28
413 13
414 17
415 7
416 14
417 14
418 9
419 4
420 47
421 24
422 5
423 1
424 33
425 34
426 3
427 15
428 31
429 35
430 13
431 28
432 20
433 26
434 12
435 7
436 31
437 11
438 5
439 41
440 21
441 18
442 38
443 19
444 27
445 34
446 4
447 6
448 23
449 43
450 1
451 23
452 3
453 40
454 4
455 5
456 7
457 14
458 32
459 7
460 35
461 24
462 19
463 18
464 6
465 10
466 22
467 16
468 10
469 38
470 13
471 12
472 11
473 7
474 45
475 18
476 2
477 41
478 18
479 34
480 29
481 20
482 3
483 9
484 28
485 2
486 23
487 37
488 45
489 29
490 3
491 17
492 30
493 7
494 23
495 42
496 17
497 13
498 8
499 10
500 44

Advertisements

Written by meditationatae

July 14, 2017 at 5:38 am

Posted in History

%d bloggers like this: