  This paper proposes a hybrid self-adaptive evolutionary algorithm for graph
coloring that is hybridized with the following novel elements: heuristic
genotype-phenotype mapping, a swap local search heuristic, and a neutral
survivor selection operator. This algorithm was compared with the evolutionary
algorithm with the SAW method of Eiben et al., the Tabucol algorithm of Hertz
and de Werra, and the hybrid evolutionary algorithm of Galinier and Hao. The
performance of these algorithms were tested on a test suite consisting of
randomly generated 3-colorable graphs of various structural features, such as
graph size, type, edge density, and variability in sizes of color classes.
Furthermore, the test graphs were generated including the phase transition
where the graphs are hard to color. The purpose of the extensive experimental
work was threefold: to investigate the behavior of the tested algorithms in the
phase transition, to identify what impact hybridization with the DSatur
traditional heuristic has on the evolutionary algorithm, and to show how graph
structural features influence the performance of the graph-coloring algorithms.
The results indicate that the performance of the hybrid self-adaptive
evolutionary algorithm is comparable with, or better than, the performance of
the hybrid evolutionary algorithm which is one of the best graph-coloring
algorithms today. Moreover, the fact that all the considered algorithms
performed poorly on flat graphs confirms that this type of graphs is really the
hardest to color.
