Speaker
Description
Monte Carlo tree search (MCTS) has shown significant success in game playing, achieving state-of-the-art results in many complex domains. While there are known applications in optimization, they often don't fully capitalize on the problem-specific knowledge available. This work addresses this gap by proposing adaptations of MCTS tailored for optimization problems. We focus on enhancing the exploitation of problem-specific heuristics, exploring methods to integrate these heuristics directly into the selection and expansion phases of the MCTS algorithm.
We also introduce strategies for a more elaborate exploitation of the incumbent solution. This involves incorporating ideas from local search techniques into the MCTS framework. By strategically exploring the vicinity of promising solutions, we aim to improve the quality of the final result.
Finally, we propose the adoption of non-deterministic selection rules within the MCTS algorithm. These rules are designed to promote a more diversified exploration of the search tree, particularly at the topmost levels. By introducing stochasticity into the selection process, we aim to mitigate stagnation caused by excessive breadth at those levels.
These ideas will be illustrated with the graph coloring problem, and some applications on timetabling will be analyzed.
