[3J4-J-1] 基礎・理論: 探索問題とその応用

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

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

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

工業や経済の問題の多くは，最も効率が良い組み合わせを求める，組み合わせ最適化問題に帰着することができる．その中に，与えられた全ての都市を巡る最短経路を求める巡回セールスマン問題 (Traveling Salesman Problem,TSP) がある．本庄らは，最適化問題に用いられるアルゴリズムの一つである粒子群最適化(Particle Swarm Optimization, PSO) をTSP向けに改良した挿入操作PSO戦略（Insertion-based PSO strategy, IPSO) を提案した．しかし，このIPSOには探索が十分に行われないうちに，局所解に陥ってしまうという問題点がある．そこで本研究では，既存手法で用いられた各粒子のそれまでの最良解と近傍の粒子の最良解の情報に加え，解空間上で最も遠い粒子の解の情報を現在の解に重ね合わせた解の集合を用いて，解の更新を行うアルゴリズムを構築した．そして，TSPLIBに掲載されているベンチマーク問題を用いて既存手法と提案手法の比較をすることで，その有効性を確認した．