Combining Monte Carlo Tree Search and Heuristic Search for Weighted Vertex Coloring

Autor:	Grelier, Cyril, Goudet, Olivier, Hao, Jin-Kao
Rok vydání:	2023
Předmět:	Computer Science - Artificial Intelligence
Druh dokumentu:	Working Paper
Popis:	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. Comment: arXiv admin note: substantial text overlap with arXiv:2202.01665
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2304.12146 Zobrazit plný text záznamu View this record from Arxiv