论文标题
使用改编版的蒙特卡洛树搜索搜索空间树搜索组合优化问题
Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems
论文作者
论文摘要
在本文中，我们提出了一种启发式算法，以探索与组合优化问题实例相关的搜索空间树。该算法基于蒙特卡洛树搜索，这是一种流行的游戏玩法算法，用于探索游戏树，代表许多游戏的最新算法。提出了对蒙特卡洛树搜索的几种增强功能，使该算法更适合在组合优化环境中。这些增强功能利用了问题的组合结构，并旨在通过使用启发式模拟策略修剪子树来有效地探索搜索空间树，从而通过消除主导的价值分配并使用光束宽度来减少变量的域。该算法是针对两个组合优化问题专门量身定制的：Quay Crane调度问题与非跨限制和0-1 Knapsack问题的专门定制的组件。对于第一个问题，我们的算法超过了最先进的结果，并且在基准一组实例中找到了一些新的最佳解决方案。对于第二个问题，我们的算法通常会产生近乎最佳的解决方案，这些解决方案比最先进的结果稍差，但仅需要一小部分时间才能这样做。这些结果表明，对于两个完全不同的组合优化问题，该算法与最先进的算法具有竞争力。
In this article we propose a heuristic algorithm to explore search space trees associated with instances of combinatorial optimization problems. The algorithm is based on Monte Carlo tree search, a popular algorithm in game playing that is used to explore game trees and represents the state-of-the-art algorithm for a number of games. Several enhancements to Monte Carlo tree search are proposed that make the algorithm more suitable in a combinatorial optimization context. These enhancements exploit the combinatorial structure of the problem and aim to efficiently explore the search space tree by pruning subtrees, using a heuristic simulation policy, reducing the domains of variables by eliminating dominated value assignments and using a beam width. The algorithm was implemented with its components specifically tailored to two combinatorial optimization problems: the quay crane scheduling problem with non-crossing constraints and the 0-1 knapsack problem. For the first problem our algorithm surpasses the state-of-the-art results and several new best solutions are found for a benchmark set of instances. For the second problem our algorithm typically produces near-optimal solutions that are slightly worse than the state-of-the-art results, but it needs only a small fraction of the time to do so. These results indicate that the algorithm is competitive with the state-of-the-art for two entirely different combinatorial optimization problems.
