Hybrid evolutionary algorithms for graph coloring

A recent and very promising approach for combinatorial optimization is to e mbed local search into the framework of evolutionary algorithms. In this pa per, we present such hybrid algorithms for the graph coloring problem. Thes e algorithms combine a new class of highly specialized crossover operators and a well-known tabu search algorithm. Experiments of such a hybrid algori thm are carried out on large DIMACS Challenge benchmark graphs. Results pro ve very competitive with and even better than those of state-of-the-art alg orithms. Analysis of the behavior of the algorithm sheds light on ways to f urther improvement.