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.

På grund av dess många tillämpningar är graffärgning ett viktigt kombinatoriskt optimeringsproblem. Problemet består i att tilldela färger till noder i en graf så att inga närliggande noder har samma färg. Graffärgning är NP-svårt och därför har olika heuristiska lokalsökningsalgoritmer utvecklats för att kunna lösa problemet inom rimlig tid. I den här studien undersöks i vilken utsträckning en lokalsökningsalgoritm för att lösa graffärgningsproblemet kan förbättras med hjälp av förstärkningsinlärning. I detta syfte designades och implementerades en ny algoritm vid namn RLTCol. Algoritmen kombinerar den populära lokalsökningsalgoritmen TabuCol med förstärkningsinlärning. RLTCol jämfördes med flera av de bästa algoritmerna för att lösa graffärgningsproblemet, samt med en version av algoritmen utan förstärkningsinlärning. Resultatet visade att förstärkningsinlärning förbättrade lokalsökningsalgoritmens prestanda, och höll samma standard som andra lokalsökningsbaserade algoritmer i litteraturen. Trots modellens enkla utformning lyckades förstärkningsinlärningsagenten lösa många enkla probleminstanser på egen hand och generaliserades dessutom bra. Detta visar på potentialen hos förstärkningsinlärning för att lösa komplexa kombinatoriska optimeringsproblem.