Monte Carlo Tree Search with Adaptive Simulation: A Case Study on Weighted Vertex Coloring

This work presents a hyper-heuristic approach to online learning, which combines Monte Carlo Tree Search with multiple local search operators selected on the fly during the search. The impacts of different operator policies, including proportional bias, one-armed bandit, and neural network, are investigated. Experiments on well-known benchmarks of the Weighted Vertex Coloring Problem are conducted to highlight the advantages and limitations of each dynamic selection strategy.

Automated summary

This study proposes a hyper-heuristic approach to online learning that combines Monte Carlo Tree Search with multiple local search operators selected dynamically. Different operator policies, including proportional bias, one-armed bandit, and neural network, are investigated. Experiments on well-known benchmarks of the Weighted Vertex Coloring Problem demonstrate the advantages and limitations of each dynamic selection strategy.