A-005
粒子群最適化を用いた巡回セールスマン問題の解法

◎山田悠希・穴田　一（東京都市大）

経済に関する問題には，最も効率が良い組み合わせを求める組み合わせ最適化問題に帰着することができるものが多くある．その組み合わせ最適化問題の中に，与えられた全ての都市を巡る最短経路を求める巡回セールスマン問題(Traveling Salesman Problem,TSP)という問題がある．本研究では，このTSPに粒子群最適化(Partcle Swarm Optimization, PSO)を適用させて解くことを目的とする．PSOは素早く問題の解に到達する多点探索であるという特徴を保持している．しかし，PSOは実数値最適化手法であるため，そのままTSPへ適用させるのは難しい．そこで本研究ではPSOの特徴を維持しつつTSPに適用させるアルゴリズムを構築し，TSPLIBに掲載されているベンチマーク問題を用いて，他の手法との性能を比較した．