抄録
A-009
粒子群最適化を用いた巡回セールスマン問題の解法
山田悠希・穴田 一(東京都市大)
経済に関する問題には,最も効率が良い組み合わせを求める組み合わせ最適化問題に帰着することができるものが多くある.その中に,与えられた全ての都市を巡る最短経路を求める巡回セールスマン問題(TravelingSalesmanProblem,TSP)という問題がある.本研究では,このTSPを粒子群最適化(PartcleSwarmOptimization,PSO)を適用させて解くことを目的とする.PSOは生物の群れ行動をモデルにしたアルゴリズムであり,素早く問題の解に到達する多点探索であるという特徴がある.しかし,PSOは実数値最適化手法であるため,そのままTSPへ適用させるのは難しい.そこで本研究ではPSOの特徴を維持しつつTSPに適用させるアルゴリズムを構築し,TSPLIBに掲載されているベンチマーク問題を用いて,他の手法との性能を比較した.