文献

J-GLOBAL ID：201902277492205808   整理番号：19A0897779

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

Solving Combinatorial Optimization Problems Using Deep Learning

著者 (2件)： 三木彰馬 (関西大 大学院) ,  榎原博之 (関西大)
資料名： 情報処理学会論文誌ジャーナル(Web)
巻： 60  号： 2  ページ： 651-659 (WEB ONLY)  発行年： 2019年02月15日 
JST資料番号： U0452A  ISSN： 1882-7764  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

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

シソーラス用語： *巡回セールスマン問題 ,  *組合せ最適化問題 ,  機械学習 ,  ニューラルネットワーク ,  最適航路 ,  近傍探索法
準シソーラス用語： 深層学習 ,  畳込みニューラルネットワーク ,  最適経路

分類 (3件)： ネットワーク法  (KA03040X) ,  その他のオペレーションズリサーチの手法  (KA03070E) ,  人工知能  (JE08000Z)

引用文献 (15件)：

• Helsgaun, K.: General k-opt submoves for the Lin-Kernighan TSP heuristic, Mathematical Programming Computation, Vol.1, No.2, pp.119-163 (online), DOI: 10.1007/s12532-009-0004-6 (2009).
• Nagata, Y. and Kobayashi, S.: A Powerful Genetic Algorithm Using Edge Assembly Crossover for the Traveling Salesman Problem, INFORMS Journal on Computing, Vol.25, No.2, pp.346-363 (online), DOI: 10.1287/ijoc.1120.0506 (2013).
• Isola, P., Zhu, J.-Y., Zhou, T. and Efros, A.A.: Image-to-Image Translation with Conditional Adversarial Networks, CVPR 2017, arXiv:1611.07004 (2016).
• Radford, A., Metz, L. and Chintala, S.: Unsupervised Representation Learning with Deep Convolutional Generative Adversarial Networks, arXiv preprint arXiv:1511.06434 (2015).
• Silver, D., Huang, A., Maddison, C.J., et al.: Mastering the game of Go with deep neural networks and tree search, Nature, Vol.529, pp.484-489 (2016) (online), available from http://dx.doi.org/10.1038/nature16961.

タイトルに関連する用語 (3件)： 深層学習 ,  巡回セールスマン問題 ,  解法