Month: July 2017

Previously, I thought there could be zero conflicts, two or more conflicts, but not exactly one vertex conflict; I’m not sure what’s going on. For 500-vertex graph DSJC500.5.col , program reports 1 vertex conflict (??):   Added July 31: It’s one edge conflict, or two vertices connected by an edge, and who share the same… Continue reading Graph coloring program report 1 vertex conflict

I’ve got C code that seems to work quite well for their new algorithm, comparatively speaking, meaning compared to what I had before. I’m regularly getting improper 47-colorings of DSJC500.5 with just two conflicting vertices, which means precisely one edge with a conflict. It’s as close as it gets without having no conflicts, unless I’m… Continue reading Moalic and Gondran Heuristic rope team : a parallel algorithm for graph coloring (for DSJC500.5 graph)

At the GECCO 2017 Conference in Berlin in July, Moalic and Gondran gave a presentation with a conference paper entitled: “Heuristic rope team : a parallel algorithm for graph coloring”. It can be searched for along with ACM on Google, and it’s in PDF format. It uses Tabu local search, the Greedy Partitioning Crossover operator… Continue reading New evolutionary algorithm, implementation in C

As explained in the previous post, the C language program that implements the HEAD’ graph coloring algorithm of Moalic and Gondran needs as input the graph DSJC500.5.col (DIMACS challenge) in a format detailed previously, as well as a file of 14 “improper 48-colorings” of DSJC500.5, meaning 48-colorings of the 500 vertices of DSJC500.5, where about… Continue reading Data of July 14 to test HEA in Duet, version HEAD’

The source code file, pnewtbuza75a.c , can be compiled using the GCC compiler as follows: gcc -lm -O2 -o pnewtbuza75a.out pnewtbuza75a.c To run the program, at the Unix shell prompt, I type: ./pnewtbuza75a.out DSJC500.5.mt 500 DSJC500.5.mt is a file containing a description of the 500-vertex DSJC500.5 graph created by David Johnson. In substance, it can… Continue reading Source code of July 14 to test HEA in Duet, version HEAD’

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… Continue reading HEA in Duet and graph coloring (continuation)

generation 600 done … 14 conflicts at 18 iterations 13 conflicts at 19 iterations 12 conflicts at 20 iterations 11 conflicts at 22 iterations 10 conflicts at 28 iterations 9 conflicts at 29 iterations 8 conflicts at 33 iterations 7 conflicts at 42 iterations 6 conflicts at 84 iterations 5 conflicts at 248 iterations 4… Continue reading HEA in Duet update (49 colors, DSJC500.5.col )

I intend to write code to implement the HEAD or HEAD’ algorithm for graph coloring of Moalic and Gondran: “Variations on Memetic Algorithms for Graph Coloring Problems”, https://arxiv.org/abs/1401.2184 . There, they use the Greedy Partition Crossover or GPX crossover , and their hybrid Tabu Search + evolutionary method is inspired by Galinier and Hao’s HEA… Continue reading Preparation for writing the evolutionary algorithm code

In the last few posts, I described my attempts at using Tabu Search only to find a 49-coloring for the standard DIMACS challenge graph: DSJC500.5 or DSJC500.5.col with 500 vertices and a density of 0.5 .  For a graph with V vertices, the density is (d^bar)/(V-1) , where d^bar is the average degree of a… Continue reading Plan to implement crossover operator GPX (graph coloring)