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.
翻译:在此篇文章中, 我们提出一种超自然算法, 探索与组合优化问题相关的搜索空间树。 该算法以蒙特卡洛树搜索为基础, 这是一种用于探索游戏树的流行游戏算法, 用来探索游戏树, 并代表一些游戏的最先进的算法 。 对蒙特卡洛树搜索提出若干改进, 使该算法更适合组合优化环境 。 这些增强利用了问题的组合结构, 目的是通过剪裁子树来有效探索搜索空间树, 使用超自然模拟政策, 缩小变量的范围, 消除主导值分配, 并使用光宽度。 该算法的组件是专门针对两个组合优化问题的: 非交叉限制的二次重力操作排程问题和 0-1 knappsack 问题 。 对于第一个问题, 我们的算法超越了当前最先进的结果, 并且为一系列基准找到了几个最佳的解决方案 。 对于第二个问题, 我们的算法通常产生近最佳的解决方案, 其范围略为小于状态的值, 并且使用光宽度的宽度。 该算法的组合只需要两个不同的最有竞争力的版本。