Monte carlo tree search method for solving the knapsack problem

被引：0

作者：

Iima H. ^{[1
]}

Hyono T. ^{[1
]}

机构：

[1] Kyoto Institute of Technology, Matsugasaki, Sakyo-ku, Kyoto

来源：

IEEJ Transactions on Electronics, Information and Systems | 2020年 / 140卷 / 10期

基金：

日本学术振兴会;

关键词：

Knapsack problem; Meta-heuristics; Monte carlo tree search; Optimization;

D O I：

10.1541/ieejeiss.140.1141

中图分类号：

学科分类号：

摘要：

Monte Carlo tree search is used in AlphaGo Zero which is a strong artificial intelligence player for Go, and therefore it has attracted much attention. It can be used for searching for the optimum of combinatorial optimization problems, and it is promising for finding the optimum or a near-optimum. This paper proposes a Monte Carlo tree search method for the knapsack problem which is one of the typical combinatorial optimization problems. In the proposed method, a new candidate solution is generated by using superior ones found so far in the procedure called the simulation. Its performance is evaluated through conducting numerical experiments. © 2020 The Institute of Electrical Engineers of Japan.

引用

页码：1141 / 1146

页数：5

共 8 条

[1]

Ezugwu A. E., Pillay V., Hirasen D., Sivanarain K., Govender M., A Comparative Study of Meta-Heuristic Optimization Algorithms for 0-1 Knapsack Problem: Some Initial Results, IEEE Access, 7, pp. 43979-44001, (2019)

[2]

Browne C. B., Powley E., Et al., A Survey of Monte Carlo Tree Search Methods, IEEE Transactions on Computational Intelligence and AI in Games, 4, 1, pp. 1-43, (2012)

[3]

Silver D., Schrittwieser J., Et al., Mastering the game of Go without human knowledge, Nature, 550, pp. 354-359, (2017)

[4]

Sabar N. R., Kendall G., Population based Monte Carlo tree search hyper-heuristic for combinatorial optimization problems, Information Sciences, 314, pp. 225-239, (2014)

[5]

Neto T., Constantino M., Martins I., Pedroso J. P., A multi-objective Monte Carlo tree search for forest harvest scheduling, European Journal of Operational Research, 282, 3, pp. 1115-1126, (2020)

[6]

Cant R., Remi-Omosowon A., Langensiepen C., Lotfi A., An Entropy-Guided Monte Carlo Tree Search Approach for Generating Optimal Container Loading Layouts, Entropy, 20, 11, (2018)

[7]

Kocsis L., Szepesvari C., Bandit Based Monte-Carlo Planning, Machine Learning: ECML 2006, pp. 282-293, (2006)

[8]

Pisinger D., Where are the hard knapsack problems?, Computers & Operations Research, 32, 9, pp. 2271-2284, (2005)

← 1 →