Efficient Graph Coloring with Parallel Genetic Algorithms

keywords: Graph coloring, parallel genetic algorithm, migration model, CEX crossover, SPPX crossover
In this paper a new parallel genetic algorithm for coloring graph vertices is presented. In the algorithm we apply a migration model of parallelism and define two new recombination operators SPPX and CEX. For comparison two problem-oriented crossover operators UISX and GPX are selected. The performance of the algorithm is verified by computer experiments on a set of standard graph coloring instances.
reference: Vol. 24, 2005, No. 2, pp. 123–147