The New Memetic Algorithm HEAD for Graph Coloring: An Easy Way for Managing Diversity

This paper presents an effective memetic approach HEAD designed for coloring difficult graphs. In this algorithm a powerful tabu search is used inside a very specific population of individuals. Indeed, the main characteristic of HEAD is to work with a population of only two individuals. This provides a very simple algorithm with neither selection operator nor replacement strategy. Because of its simplicity, HEAD allows an easy way for managing the diversity. We focus this work on the impact of this diversity management on well-studied graphs of the DIMACS challenge benchmarks, known to be very difficult to solve. A detailed analysis is provided for three graphs on which HEAD finds a legal coloring with less colors than reference algorithms: DSJC500.5 with 47 colors, DSJC1000.5 with 82 colors and flat1000_76_0 with 81 colors. The analysis performed in this work will allow to improve HEAD efficiency in terms of computation time and maybe to decrease the number of needed colors for other graphs.