モンテカルロ木探索によるナップサック問題の解法

カテゴリ: 論文誌(論文単位)

グループ名: 【C】電子・情報・システム部門

発行日: 2020/10/01

タイトル(英語): Monte Carlo Tree Search Method for Solving the Knapsack Problem

著者名: 飯間　等（京都工芸繊維大学），兵野　拓海（京都工芸繊維大学）

著者名(英語): Hitoshi Iima (Kyoto Institute of Technology), Takumi Hyono (Kyoto Institute of Technology)

キーワード: モンテカルロ木探索，ナップサック問題，最適化，メタヒューリスティックス　Monte Carlo tree search，knapsack problem，optimization，meta-heuristics

要約(英語): 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.

本誌: 電気学会論文誌C（電子・情報・システム部門誌） Vol.140 No.10 （2020）

本誌掲載ページ: 1141-1146 p

原稿種別: 論文／日本語

電子版へのリンク: https://www.jstage.jst.go.jp/article/ieejeiss/140/10/140_1141/_article/-char/ja/