2024-03-28T23:19:29Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001952452023-04-27T10:00:04Z01164:02822:09758:09759
SAベースのイジングマシンにより巡回セールスマン問題を高速解法するための多種軽量係数試行法jpn計算手法http://id.nii.ac.jp/1001/00195156/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=195245&item_no=1&attribute_id=1&file_no=1Copyright (c) 2019 by the Information Processing Society of Japan早稲田大学基幹理工学部情報理工学科早稲田大学大学院基幹理工学研究科情報理工・情報通信専攻株式会社フィックスターズ早稲田大学グリーン・コンピューティング・システム研究機構/科学技術振興機構さきがけ早稲田大学基幹理工学部情報理工学科竹原, 康太於久, 太祐松田, 佳希田中, 宗戸川, 望イジングマシンは組合せ最適化問題を高速に解法し準最適解を得るためのハードウェアとして注目されている.組合せ最適化問題の中でも,多地点を最短経路で巡回する経路を探索する巡回セールスマン問題は NP 困難な問題であり,トラックの配送経路の最適化などに社会的に重要な最適化問題の基礎として知られている.本稿ではシミュレーテッドアニーリング (SA) ベースのイジングマシンにて巡回セールスマン問題を高速に解法する手法を提案する.SA ベースのイジングマシンで巡回セールスマン問題を解法するには,ハミルトニアンに現れる制約重みをいかに設定するかが鍵となる.制約重みが小さいほど解空間がなめらかになり局所解を抜け出しやすくなることが期待される.しかし,制約重みが小さすぎると制約を満たす解を得られなくなる.我々は,巡回セールスマン問題では,多地点を巡回する最短経路を構成する辺について,従来手法は問題中の辺の長さの最大値に制約重みを設定するのに対し,我々は隣り合う辺の和の最大値より少し大きい値に制約重みを設定することで最適解を得る確率の向上を確認した.また制約重みを,最短経路における隣り合う辺の長さの和の最大値よりも小さい場合に設定した場合には,制約を満たす解が得られないことを理論的考察および,実験にて確認した.しかし,どの辺が最短経路に含まれるかを予め知ることは一般に困難である.そこで提案手法はまず,問題中の辺の長さの最大値から最小値の範囲で制約重みを m 種類選び,m 種類の重みでアニーリングして得た m 個の結果のうち最良のものを採用することにする.提案手法により,予めどの辺が最短経路に含まれるかを知ることなく,適当な制約重みでアニーリングした結果を得ることができ,高速に精度の良い解を得ることが期待できる.提案手法を用いた場合と用いない場合を比較した結果,ランダムに生成した 32 地点の巡回セールスマン問題において,提案手法を用いた場合は従来手法と同程度の解を最も高速な場合で,1/1000 程度の総イテレーション数で得ることができた.AA12149313研究報告組込みシステム(EMB)2019-EMB-5053162019-03-102188-868x2019-03-06