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

• 三木, 彰馬

• 榎原, 博之

書誌事項

タイトル別名

• Solving Combinatorial Optimization Problems Using Deep Learning

抄録

本論文では代表的な組合せ最適化問題の1つである巡回セールスマン問題（TSP）に注目し，深層学習を適用した解法を提案する．本手法では，畳み込みニューラルネットワークを用いて最適経路を画像として学習することで，最適経路に含まれうる辺の分布である優良エッジ分布を求め，これにより計算される辺の評価値である優良エッジ値を利用して近傍探索を行う．この提案手法の性能を調べるために実験を行い，解の精度向上において有効であることを示す．

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.

収録刊行物

• 情報処理学会論文誌

  情報処理学会論文誌 60 (2), 651-659, 2019-02-15

  情報処理学会

キーワード

• [一般論文] 組合せ最適化問題，巡回セールスマン問題，深層学習，畳み込みニューラルネットワーク，近傍探索法

詳細情報

• CRID: 1050564288245524480
• NII論文ID: 120006811815
• NII書誌ID: AN00116647
• ISSN: 18827764
• HANDLE: 10112/00019610
• Web Site: http://id.nii.ac.jp/1001/00194303/
• Web Site: https://kansai-u.repo.nii.ac.jp/records/15553
• 本文言語コード: ja
• 資料種別: journal article
• データソース種別:
  • IRDB
  • CiNii Articles
  • KAKEN