ナップサック問題に対するモンテカルロ木探索法の適用

カテゴリ: 研究会(論文単位)

論文No: ST20007

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

発行日: 2020/03/08

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

著者名: 飯間 等(京都工芸繊維大学),兵野 拓海(京都工芸繊維大学)

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

キーワード: 最適化|モンテカルロ木探索|ナップサック問題|optimization|Monte Carlo tree search|knapsack problem

要約(日本語): モンテカルロ木探索は囲碁の高性能な人工知能プレイヤーAlpha Go Zeroでも用いられ、注目を集めている探索法である。モンテカルロ木探索は組合せ最適化問題の最適解の探索にも利用できると考えられ、最適解を発見することが期待できる。本論文では、典型的な組合せ最適化問題の１つであるナップサック問題を例題として、この問題に対するモンテカルロ木探索法を提案する。

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

原稿種別: 日本語

PDFファイルサイズ: 496 Kバイト