meditationatae

Just another WordPress.com site

Update on Parallel Rope Team Coloring

leave a comment »

At the GECCO 2017 conference in Berlin, Moalic and Gondran gave a presentation of a novel algorithm for graph coloring.

The title of their presentation is:

“Heuristic rope team : a parallel algorithm for graph coloring”.

I made a best effort attempt to implement this in the C programming language. I was able to find a 48-coloring for the 500-vertex graph from the DIMACS challenge, “DSJC500.5”.

I haven’t succeeded in finding a proper or valid 47-coloring for this graph. Below, the output refers to DSJC500.5 and 47-colorings, whether valid or not. The variable name “clg” means : conflicts-low, global. The program has various teams of 4 improper colorings evolve in a complex way as described in Moalic and Gondran’s presentation. CLG is the minimum number of conflicted vertices for a team, up to the current time. A conflicted vertex is any vertex for which some edge in the graph connects it to some other vertex which happens to be of the same color. A valid coloring is the same thing as a coloring with zero conflicted vertices.

The output line:

“clg = 2 at 3221 generations for team number 49” indicates

that for the 49th team of four colorings, after 3221 generations (please see Moalic and Gondran paper, the part on evolutionary algorithms and the GPX crossover method), there were two conflicted vertices.

One conflicted vertex by itself is impossible. “clg = 0” would mean a valid 47-coloring. A 47-coloring was discovered around 2012 using another algorithm. The authors report that their implementaion of PrtCol found valid 47-colorings, among other graph colorings. I’m willing to share the program and data needed. PrtCol is a sophisticated algorithm, so there’s 4000 lines of code, with some blocks of code appearing several times with minor differences.

 

clg = 12 at 466 generations for team number 2
clg = 11 at 473 generations for team number 2
clg = 10 at 688 generations for team number 2
clg = 9 at 688 generations for team number 2
clg = 8 at 689 generations for team number 2
clg = 7 at 690 generations for team number 2
clg = 6 at 1701 generations for team number 2
clg = 4 at 3389 generations for team number 2
clg = 12 at 485 generations for team number 3
clg = 11 at 485 generations for team number 3
clg = 12 at 299 generations for team number 4
clg = 11 at 299 generations for team number 4
clg = 10 at 308 generations for team number 4
clg = 8 at 570 generations for team number 4
clg = 7 at 626 generations for team number 4
clg = 6 at 629 generations for team number 4
clg = 12 at 103 generations for team number 5
clg = 11 at 146 generations for team number 5
clg = 10 at 166 generations for team number 5
clg = 9 at 167 generations for team number 5
clg = 8 at 168 generations for team number 5
clg = 7 at 1333 generations for team number 5
clg = 6 at 2049 generations for team number 5
clg = 5 at 2051 generations for team number 5
clg = 12 at 175 generations for team number 6
clg = 11 at 202 generations for team number 6
clg = 10 at 202 generations for team number 6
clg = 9 at 296 generations for team number 6
clg = 8 at 296 generations for team number 6
clg = 7 at 1261 generations for team number 6
clg = 6 at 3052 generations for team number 6
clg = 5 at 4220 generations for team number 6
clg = 4 at 4230 generations for team number 6
clg = 12 at 350 generations for team number 7
clg = 10 at 350 generations for team number 7
clg = 9 at 552 generations for team number 7
clg = 8 at 763 generations for team number 7
clg = 6 at 1147 generations for team number 7
clg = 5 at 1536 generations for team number 7
clg = 11 at 286 generations for team number 8
clg = 10 at 340 generations for team number 8
clg = 9 at 350 generations for team number 8
clg = 8 at 359 generations for team number 8
clg = 7 at 590 generations for team number 8
clg = 6 at 590 generations for team number 8
clg = 5 at 1115 generations for team number 8
clg = 12 at 428 generations for team number 10
clg = 11 at 759 generations for team number 10
clg = 10 at 759 generations for team number 10
clg = 8 at 759 generations for team number 10
clg = 7 at 2287 generations for team number 10
clg = 6 at 2305 generations for team number 10
clg = 5 at 2745 generations for team number 10
clg = 12 at 273 generations for team number 12
clg = 11 at 283 generations for team number 12
clg = 10 at 283 generations for team number 12
clg = 9 at 371 generations for team number 12
clg = 8 at 371 generations for team number 12
clg = 7 at 878 generations for team number 12
clg = 6 at 1149 generations for team number 12
clg = 12 at 208 generations for team number 13
clg = 11 at 208 generations for team number 13
clg = 10 at 232 generations for team number 13
clg = 9 at 412 generations for team number 13
clg = 8 at 476 generations for team number 13
clg = 7 at 588 generations for team number 13
clg = 6 at 590 generations for team number 13
clg = 5 at 757 generations for team number 13
clg = 4 at 4953 generations for team number 13
clg = 3 at 4958 generations for team number 13
clg = 12 at 432 generations for team number 14
clg = 12 at 408 generations for team number 15
clg = 11 at 441 generations for team number 15
clg = 10 at 441 generations for team number 15
clg = 9 at 1029 generations for team number 15
clg = 8 at 1033 generations for team number 15
clg = 7 at 1767 generations for team number 15
clg = 6 at 2154 generations for team number 15
clg = 5 at 2430 generations for team number 15
clg = 12 at 148 generations for team number 16
clg = 11 at 264 generations for team number 16
clg = 10 at 264 generations for team number 16
clg = 9 at 264 generations for team number 16
clg = 8 at 344 generations for team number 16
clg = 7 at 367 generations for team number 16
clg = 12 at 134 generations for team number 17
clg = 11 at 134 generations for team number 17
clg = 10 at 180 generations for team number 17
clg = 8 at 180 generations for team number 17
clg = 7 at 183 generations for team number 17
clg = 6 at 188 generations for team number 17
clg = 5 at 188 generations for team number 17
clg = 4 at 343 generations for team number 17
clg = 12 at 186 generations for team number 18
clg = 11 at 245 generations for team number 18
clg = 10 at 256 generations for team number 18
clg = 9 at 261 generations for team number 18
clg = 8 at 469 generations for team number 18
clg = 12 at 260 generations for team number 19
clg = 11 at 260 generations for team number 19
clg = 10 at 262 generations for team number 19
clg = 9 at 280 generations for team number 19
clg = 8 at 911 generations for team number 19
clg = 7 at 1260 generations for team number 19
clg = 6 at 1301 generations for team number 19
clg = 12 at 402 generations for team number 20
clg = 11 at 403 generations for team number 20
clg = 9 at 465 generations for team number 20
clg = 8 at 473 generations for team number 20
clg = 7 at 473 generations for team number 20
clg = 12 at 89 generations for team number 21
clg = 11 at 96 generations for team number 21
clg = 10 at 542 generations for team number 21
clg = 9 at 1352 generations for team number 21
clg = 8 at 1354 generations for team number 21
clg = 7 at 1359 generations for team number 21
clg = 6 at 1362 generations for team number 21
clg = 5 at 2226 generations for team number 21
clg = 4 at 2758 generations for team number 21
clg = 12 at 169 generations for team number 22
clg = 11 at 201 generations for team number 22
clg = 10 at 530 generations for team number 22
clg = 8 at 1014 generations for team number 22
clg = 7 at 1163 generations for team number 22
clg = 6 at 1529 generations for team number 22
clg = 11 at 64 generations for team number 23
clg = 10 at 64 generations for team number 23
clg = 9 at 67 generations for team number 23
clg = 8 at 1167 generations for team number 23
clg = 7 at 1869 generations for team number 23
clg = 6 at 2552 generations for team number 23
clg = 12 at 426 generations for team number 24
clg = 11 at 427 generations for team number 24
clg = 10 at 427 generations for team number 24
clg = 9 at 431 generations for team number 24
clg = 12 at 496 generations for team number 25
clg = 11 at 501 generations for team number 25
clg = 12 at 149 generations for team number 26
clg = 11 at 472 generations for team number 26
clg = 10 at 472 generations for team number 26
clg = 12 at 381 generations for team number 27
clg = 11 at 383 generations for team number 27
clg = 10 at 384 generations for team number 27
clg = 9 at 387 generations for team number 27
clg = 8 at 390 generations for team number 27
clg = 7 at 538 generations for team number 27
clg = 6 at 538 generations for team number 27
clg = 5 at 2051 generations for team number 27
clg = 12 at 395 generations for team number 28
clg = 11 at 623 generations for team number 28
clg = 10 at 677 generations for team number 28
clg = 9 at 677 generations for team number 28
clg = 8 at 679 generations for team number 28
clg = 7 at 2509 generations for team number 28
clg = 6 at 2518 generations for team number 28
clg = 5 at 2528 generations for team number 28
clg = 12 at 229 generations for team number 29
clg = 11 at 229 generations for team number 29
clg = 10 at 229 generations for team number 29
clg = 9 at 375 generations for team number 29
clg = 8 at 495 generations for team number 29
clg = 7 at 957 generations for team number 29
clg = 6 at 963 generations for team number 29
clg = 12 at 367 generations for team number 30
clg = 10 at 368 generations for team number 30
clg = 9 at 368 generations for team number 30
clg = 8 at 774 generations for team number 30
clg = 6 at 929 generations for team number 30
clg = 12 at 391 generations for team number 31
clg = 11 at 391 generations for team number 31
clg = 10 at 391 generations for team number 31
clg = 9 at 391 generations for team number 31
clg = 8 at 396 generations for team number 31
clg = 7 at 399 generations for team number 31
clg = 6 at 492 generations for team number 31
clg = 5 at 1933 generations for team number 31
clg = 4 at 1956 generations for team number 31
clg = 3 at 2130 generations for team number 31
clg = 12 at 247 generations for team number 32
clg = 11 at 247 generations for team number 32
clg = 10 at 458 generations for team number 32
clg = 8 at 458 generations for team number 32
clg = 7 at 523 generations for team number 32
clg = 6 at 553 generations for team number 32
clg = 5 at 693 generations for team number 32
clg = 4 at 30887 generations for team number 32
clg = 12 at 479 generations for team number 33
clg = 11 at 480 generations for team number 33
clg = 10 at 480 generations for team number 33
clg = 9 at 586 generations for team number 33
clg = 8 at 590 generations for team number 33
clg = 7 at 591 generations for team number 33
clg = 6 at 619 generations for team number 33
clg = 5 at 621 generations for team number 33
clg = 4 at 797 generations for team number 33
clg = 12 at 196 generations for team number 34
clg = 11 at 196 generations for team number 34
clg = 10 at 198 generations for team number 34
clg = 9 at 203 generations for team number 34
clg = 8 at 226 generations for team number 34
clg = 6 at 589 generations for team number 34
clg = 12 at 440 generations for team number 35
clg = 11 at 446 generations for team number 35
clg = 10 at 451 generations for team number 35
clg = 9 at 451 generations for team number 35
clg = 12 at 304 generations for team number 36
clg = 11 at 770 generations for team number 36
clg = 10 at 772 generations for team number 36
clg = 9 at 777 generations for team number 36
clg = 8 at 780 generations for team number 36
clg = 7 at 789 generations for team number 36
clg = 6 at 845 generations for team number 36
clg = 12 at 320 generations for team number 37
clg = 10 at 321 generations for team number 37
clg = 12 at 224 generations for team number 39
clg = 11 at 367 generations for team number 39
clg = 10 at 490 generations for team number 39
clg = 9 at 672 generations for team number 39
clg = 8 at 672 generations for team number 39
clg = 7 at 956 generations for team number 39
clg = 6 at 961 generations for team number 39
clg = 5 at 2167 generations for team number 39
clg = 12 at 157 generations for team number 40
clg = 10 at 157 generations for team number 40
clg = 9 at 473 generations for team number 40
clg = 8 at 502 generations for team number 40
clg = 6 at 1438 generations for team number 40
clg = 5 at 2921 generations for team number 40
clg = 4 at 2924 generations for team number 40
clg = 12 at 325 generations for team number 41
clg = 10 at 325 generations for team number 41
clg = 9 at 325 generations for team number 41
clg = 8 at 535 generations for team number 41
clg = 7 at 600 generations for team number 41
clg = 5 at 600 generations for team number 41
clg = 12 at 172 generations for team number 42
clg = 11 at 202 generations for team number 42
clg = 10 at 202 generations for team number 42
clg = 9 at 659 generations for team number 42
clg = 8 at 735 generations for team number 42
clg = 12 at 456 generations for team number 44
clg = 10 at 499 generations for team number 44
clg = 8 at 561 generations for team number 44
clg = 7 at 679 generations for team number 44
clg = 6 at 695 generations for team number 44
clg = 5 at 908 generations for team number 44
clg = 12 at 175 generations for team number 45
clg = 11 at 175 generations for team number 45
clg = 10 at 192 generations for team number 45
clg = 9 at 362 generations for team number 45
clg = 8 at 362 generations for team number 45
clg = 6 at 397 generations for team number 45
clg = 5 at 510 generations for team number 45
clg = 12 at 225 generations for team number 46
clg = 11 at 330 generations for team number 46
clg = 10 at 341 generations for team number 46
clg = 9 at 343 generations for team number 46
clg = 8 at 344 generations for team number 46
clg = 6 at 465 generations for team number 46
clg = 12 at 424 generations for team number 47
clg = 11 at 426 generations for team number 47
clg = 10 at 731 generations for team number 47
clg = 9 at 740 generations for team number 47
clg = 8 at 788 generations for team number 47
clg = 7 at 801 generations for team number 47
clg = 6 at 801 generations for team number 47
clg = 12 at 178 generations for team number 48
clg = 11 at 180 generations for team number 48
clg = 10 at 224 generations for team number 48
clg = 9 at 225 generations for team number 48
clg = 8 at 268 generations for team number 48
clg = 7 at 456 generations for team number 48
clg = 6 at 507 generations for team number 48
clg = 5 at 766 generations for team number 48
clg = 12 at 235 generations for team number 49
clg = 11 at 246 generations for team number 49
clg = 10 at 747 generations for team number 49
clg = 9 at 752 generations for team number 49
clg = 8 at 946 generations for team number 49
clg = 7 at 1264 generations for team number 49
clg = 6 at 1524 generations for team number 49
clg = 5 at 1526 generations for team number 49
clg = 4 at 1526 generations for team number 49
clg = 2 at 3221 generations for team number 49
clg = 12 at 137 generations for team number 51
clg = 11 at 142 generations for team number 51
clg = 10 at 151 generations for team number 51
clg = 9 at 1277 generations for team number 51
clg = 8 at 1292 generations for team number 51
clg = 7 at 1294 generations for team number 51
clg = 6 at 1294 generations for team number 51
clg = 5 at 4009 generations for team number 51
clg = 4 at 4586 generations for team number 51

Advertisements

Written by meditationatae

August 10, 2017 at 12:23 pm

Posted in History

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: