Reinforcement learning for improved local search : Applied to the graph coloring problem

Abstract: The graph coloring problem (GCP) is an important combinatorial optimization problem (COP) with various applications and a simple formulation: to assign colors to vertices in a graph such that no adjacent vertices share a color. The GCP is NP-hard, and in order to solve it within a reasonable time frame, heuristic local search (LS) based algorithms are commonly used. This study evaluates to what extent a LS algorithm for solving the GCP can be improved by using reinforcement learning (RL). This was achieved by designing and implementing an algorithm, named RLTCol, that combines the popular LS based TabuCol algorithm with RL. Our algorithm was evaluated against several state-of-the-art GCP algorithms as well as a variant of the algorithm that only uses LS. The results show that RL improved the performance of the LS algorithm, and that the RLTCol competed favorably against other LS based methods. Despite the simple RL policy that was used, the RL agent managed to generalize well and was able to solve many simple instances of the GCP on its own. This shows promise in the usefulness and ability of RL in solving complex COPs.