SAベースのイジングマシンにより巡回セールスマン問題を高速解法するための多種軽量係数試行法

• Item type: SIG Technical Reports(1)
• 公開日: 2019-03-10
• タイトル: SAベースのイジングマシンにより巡回セールスマン問題を高速解法するための多種軽量係数試行法
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 計算手法
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 早稲田大学基幹理工学部情報理工学科
• 著者所属: 早稲田大学大学院基幹理工学研究科情報理工・情報通信専攻
• 著者所属: 株式会社フィックスターズ
• 著者所属: 早稲田大学グリーン・コンピューティング・システム研究機構／科学技術振興機構さきがけ
• 著者所属: 早稲田大学基幹理工学部情報理工学科
• 著者名: 竹原, 康太; 於久, 太祐; 松田, 佳希; 田中, 宗; 戸川, 望
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: イジングマシンは組合せ最適化問題を高速に解法し準最適解を得るためのハードウェアとして注目されている．組合せ最適化問題の中でも，多地点を最短経路で巡回する経路を探索する巡回セールスマン問題は NP 困難な問題であり，トラックの配送経路の最適化などに社会的に重要な最適化問題の基礎として知られている．本稿ではシミュレーテッドアニーリング (SA) ベースのイジングマシンにて巡回セールスマン問題を高速に解法する手法を提案する．SA ベースのイジングマシンで巡回セールスマン問題を解法するには，ハミルトニアンに現れる制約重みをいかに設定するかが鍵となる．制約重みが小さいほど解空間がなめらかになり局所解を抜け出しやすくなることが期待される．しかし，制約重みが小さすぎると制約を満たす解を得られなくなる．我々は，巡回セールスマン問題では，多地点を巡回する最短経路を構成する辺について，従来手法は問題中の辺の長さの最大値に制約重みを設定するのに対し，我々は隣り合う辺の和の最大値より少し大きい値に制約重みを設定することで最適解を得る確率の向上を確認した．また制約重みを，最短経路における隣り合う辺の長さの和の最大値よりも小さい場合に設定した場合には，制約を満たす解が得られないことを理論的考察および，実験にて確認した．しかし，どの辺が最短経路に含まれるかを予め知ることは一般に困難である．そこで提案手法はまず，問題中の辺の長さの最大値から最小値の範囲で制約重みを m 種類選び，m 種類の重みでアニーリングして得た m 個の結果のうち最良のものを採用することにする．提案手法により，予めどの辺が最短経路に含まれるかを知ることなく，適当な制約重みでアニーリングした結果を得ることができ，高速に精度の良い解を得ることが期待できる．提案手法を用いた場合と用いない場合を比較した結果，ランダムに生成した 32 地点の巡回セールスマン問題において，提案手法を用いた場合は従来手法と同程度の解を最も高速な場合で，1/1000 程度の総イテレーション数で得ることができた．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10096105
• 書誌情報: 研究報告システム・アーキテクチャ（ARC）; 巻 2019-ARC-235, 号 53, p. 1-6, 発行日 2019-03-10
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8574
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会