Coloring Dynamic Graphs With a Similarity and Pool-Based Evolutionary Algorithm

Abstract

The graph coloring problem is a well-known optimization challenge, particularly relevant in dynamic environments where the graph undergoes continuous changes over time. Evolutionary algorithms, known for their adaptability and effectiveness in handling NP-hard problems, are well-suited for tackling the issues related to coloring dynamic graphs. In this paper, we present a novel Similarity and Pool-Based Evolutionary Algorithm designed to address the graph coloring problem on dynamic graphs. Our approach employs a partition-based representation that adapts to dynamic graph changes while preserving valuable historical information. The algorithm introduces an innovative similarity and conflict-based crossover operator aimed at minimizing the number of colors used, alongside a local search method to enhance solution diversity. We evaluated the performance of the proposed algorithm against a well-known heuristic for the graph coloring problem and a genetic algorithm with a dynamic population across a diverse set of dynamic graphs. Experimental results demonstrate that our algorithm consistently outperforms these alternatives by reducing the number of colors required in the majority of test cases.