Combining Monte Carlo Tree Search and Heuristic Search for Weighted Vertex Coloring
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912257247543296 |
|---|---|
| author | Grelier, Cyril Goudet, Olivier Hao, Jin-Kao |
| author_facet | Grelier, Cyril Goudet, Olivier Hao, Jin-Kao |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_12146 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Combining Monte Carlo Tree Search and Heuristic Search for Weighted Vertex Coloring Grelier, Cyril Goudet, Olivier Hao, Jin-Kao Artificial Intelligence 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. |
| title | Combining Monte Carlo Tree Search and Heuristic Search for Weighted Vertex Coloring |
| topic | Artificial Intelligence |
| url | https://arxiv.org/abs/2304.12146 |