[1E1] 基礎・理論-制約充足・最適化・定性推論

[1E1-02] 粒子群最適化を用いた巡回セールスマン問題の解法

〇山田 悠希¹、穴田 一¹ (1. 東京都市大学)

キーワード：粒子群最適化、巡回セールスマン問題

経済の問題の多くは，最も効率が良い組み合わせを求める組み合わせ最適化問題に帰着することができる．その中に，与えられた全ての都市を巡る最短経路を求める巡回セールスマン問題(TravelingSalesmanProblem,TSP)という問題がある．このTSPを解くアルゴリズムに挿入操作PSO戦略（Insertion-based PSO strategy,IPSO)がある．IPSOは，解空間上に配置された粒子がそれまでの最良解と，近傍の粒子の最良解の情報を基に解の更新を繰り返すことで解空間の探索を行うアルゴリズムである．しかし，このIPSOには探索が十分に行われないうちに，局所解に陥ってしまうという問題点がある．
本研究では解の更新時に，それまでの最良解と近傍の粒子の最良解の情報に加え，解空間上で最も遠い粒子の情報とランダムに選択した粒子の情報を与えることで，既存手法よりも広範囲の探索を行えるアルゴリズムを構築した．そして，TSPLIBに掲載されているベンチマーク問題を用いて，性能の向上を確認した．