A Cartography-Driven Memetic Algorithm with Adaptive Surgical Repair for the Graph Coloring Problem

The graph coloring problem is NP-hard. One promising way to address this challenge is to combine population-based evolutionary algorithms with local search techniques. This paper builds on the NERS HEAD framework, integrating Search Space Cartography and microscopic repair strategies. The algorithm introduces a Guardian module that detects when the search is stuck in a local optimum by keeping track of previously visited regions. For example, if the algorithm revisits a similar solution, the Guardian triggers a mechanism to help escape this state. This mechanism enables the evolutionary process to escape known states using a dynamically calculated explosion. The MIGHT repair operator resolves conflicts between nodes by applying a constructive heuristic called RLFMNC, which systematically selects new colors for conflicting nodes to reduce overall conflicts. These additions enhance the diversity and quality of the evolutionary population, facilitating a more efficient convergence of the search process while preserving essential sub-structures. Experiments on DIMACS benchmark instances show that these methods help the algorithm escape local optima, achieving results close to the best-known solutions, as measured by the number of colors used or the percentage of solved instances