4P-08
強化学習を用いた巡回セールスマン問題の解法
○山本大輔,三木彰馬,榎原博之(関西大)
本論文では代表的な組合せ最適化問題の1つである巡回セールスマン問題(TSP)に注目し、強化学習を適用した手法を提案する。本手法では、ε-greedy法によって生成した経路の経路長を過去に生成した経路の平均経路長と比較することで、短い経路を選びやすく、長い経路を選びづらくなるようにActor-Criticを用いて畳み込みニューラルネットワークを学習する。そして、最適経路に含まれうる辺の分布を表した画像である優良エッジ分布を求め、これにより計算される辺の評価値である優良エッジ値を利用して経路を生成する。この提案手法の性質を調べるために実験を行い、解の精度向上において有効であることを示す。

footer 著作権について 倫理綱領 プライバシーポリシー セキュリティ 情報処理学会