Combining Monte Carlo Tree Search and Heuristic Search for Weighted Vertex Coloring
This is an incremental improvement for combinatorial optimization researchers, as it extends prior work on MCTS variants for a specific graph problem.
The paper tackles the Weighted Vertex Coloring Problem by combining Monte Carlo Tree Search (MCTS) with various simulation strategies like greedy and local search heuristics, and it provides empirical evidence on their advantages and limits based on experiments with benchmark instances.
This work investigates the Monte Carlo Tree Search (MCTS) method combined with dedicated heuristics for solving the Weighted Vertex Coloring Problem. In addition to the basic MCTS algorithm, we study several MCTS variants where the conventional random simulation is replaced by other simulation strategies including greedy and local search heuristics. We conduct experiments on well-known benchmark instances to assess these combined MCTS variants. We provide empirical evidence to shed light on the advantages and limits of each simulation strategy. This is an extension of the work of Grelier and al. presented at EvoCOP2022.