深層学習を用いた巡回セールスマン問題の解法

• Item type: Journal(1)
• 公開日: 2019-02-15
• タイトル: 深層学習を用いた巡回セールスマン問題の解法
• タイトル / 言語: en
• タイトル: Solving Combinatorial Optimization Problems Using Deep Learning
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [一般論文] 組合せ最適化問題，巡回セールスマン問題，深層学習，畳み込みニューラルネットワーク，近傍探索法
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 関西大学大学院
• 著者所属: 関西大学
• 著者所属(英): en
• 著者所属(英): Graduate School of Kansai University
• 著者所属(英): en
• 著者所属(英): Kansai University
• 著者名: 三木, 彰馬; 榎原, 博之
• 著者名(英): Shoma, Miki; Hiroyuki, Ebara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では代表的な組合せ最適化問題の1つである巡回セールスマン問題（TSP）に注目し，深層学習を適用した解法を提案する．本手法では，畳み込みニューラルネットワークを用いて最適経路を画像として学習することで，最適経路に含まれうる辺の分布である優良エッジ分布を求め，これにより計算される辺の評価値である優良エッジ値を利用して近傍探索を行う．この提案手法の性能を調べるために実験を行い，解の精度向上において有効であることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we focus on the traveling salesman problem (TSP) that is a typical combinatorial optimization problem, and propose a method for solving it with applying deep learning. This method features learning the image of the optimal tour by a convolutional neural network to acquire the Good-Edge Distribution whose edges could be included in the optimal solution. It also conducts neighborhood search by using Good-Edge Value that is an evaluation of each edge calculated from the distribution. We show experimentally that this method improves the quality of solutions.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 60, 号 2, p. 651-659, 発行日 2019-02-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764