Diversity Control and Multi-Parent Recombination for Evolutionary Graph Coloring Algorithms

We present a hybrid evolutionary algorithm for the graph coloring problem (Evocol). Evocol is based on two simple-but-effective ideas. First, we use an enhanced crossover that collects the best color classes out of more than two parents; the best color classes are selected using a ranking based on both class fitness and class size. We also introduce a simple method of using distances to assure the population diversity: at each operation that inserts an individual into the population or that eliminates an individual from the population, Evocol tries to maintain the distances between the remaining individuals as large as possible. The results of Evocol match the best-known results from the literature on almost all difficult DIMACS instances (a new solution is also reported for a very large graph). Evocol obtains these performances with a success rate of at least 50%