Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems
Computers & Operations Research · 2023-02 · 150 · 106070
DOI: 10.1016/j.cor.2022.106070 ↗Kurz gefasst
Fachartikel in der Zeitschrift Computers & Operations Research, 2023-02. Verfasst von Jorik Jooken und 3 weiteren Autor:innen. Die Arbeit wurde bisher 19-mal zitiert (Crossref) und nennt 79 Literaturangaben.
Abstract (Originalsprache)
In this article, a novel approach to solve combinatorial optimization problems is proposed. This approach makes use of a heuristic algorithm to explore the search space tree of a problem instance. The algorithm is based on Monte Carlo tree search, a popular algorithm in game playing that is used to explore game trees. By leveraging the combinatorial structure of a problem, several enhancements to the algorithm are proposed. These enhancements aim to efficiently explore the search space tree by pruning subtrees, using a heuristic simulation policy, reducing the domain of variables by eliminating dominated solutions and using a beam width. They are demonstrated for a specific combinatorial optimization problem: the quay crane scheduling problem with non-crossing constraints. Computational results show that the proposed algorithm is competitive with the state-of-the-art for this problem and eight new best solutions for a benchmark set of instances are found. Apart from this, the results also show evidence that the algorithm is able to learn to correct the incorrect choices of a standard heuristic, yielding an average improvement of 10.0 % with respect to the objective function value of the solution.
Zitieren
APA
Jooken, J., Leyman, P., Wauters, T., & Causmaecker, P. D. (2023). Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems. Computers & Operations Research, 150, 106070. https://doi.org/10.1016/j.cor.2022.106070
Vancouver
Jooken J, Leyman P, Wauters T, Causmaecker PD. Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems. Computers & Operations Research. 2023;150:106070. doi:10.1016/j.cor.2022.106070
BibTeX
@article{Jooken2023,
author = {Jooken, Jorik and Leyman, Pieter and Wauters, Tony and Causmaecker, Patrick De},
title = {Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems},
journal = {Computers & Operations Research},
year = {2023},
volume = {150},
pages = {106070},
doi = {10.1016/j.cor.2022.106070}
}
EUVIMED