Particle Swarm Optimization with Tour Representation for Solving Traveling Salesman Problems

近年注目されている実数値最適化手法の一つに粒子群最適化Particle Swarm Optimization, PSOがあるPSOは群知能の一種であり複数の探索単位粒子が互いに情報共有を行いながら解の探索を行う多点探索を行うメタヒューリスティクスとしては遺伝的アルゴリズムGenetic Algorithm, GAが有名であるが多くの実数値最適化問題においてPSOのほうがGAに比べて高速に良い解を発見できることが知られている本研究では組合せ最適化問題の一種である巡回セールスマン問題Traveling Salesman Problem, TSPに対して短時間で良い解を得ることを目的としてPSOを基にしたアルゴリズムである挿入操作PSO戦略を提案する提案手法では粒子の解候補は実数値ベクトルではなく巡回路として表現され粒子間の相互作用は部分経路挿入によって行われる本論文では挿入操作PSO戦略について説明し数値計算実験からパラメータと得られる解の良さと必要な時間の関係について調査しパラメータ調整の指針を示すまた各ベンチマーク問題に対して提案手法とGAなどの代表的なメタヒューリスティクスを適用し提案手法がこれらの手法より短時間で良い解を求められることを示すIn this paper, we propose a new Traveling Salesman Problem (TSP) solver based on Particle Swarm Optimization (PSO) Algorithm. PSO is one of the optimization methods classified into swarm intelligence, and consists of particles. Particles interact and move through solution space to find a better solution. PSO can find a good solution in a short time compared with Genetic Algorithm (GA) in many real-valued optimization problems. Because TSP is a combinatorial optimization problem, we change two points of the original PSO for solving TSP. The first point is that the position of each particle is represented by a tour instead of a vector. The second is that particles move by using Insertion method. Insertion method is an operation to combine a tour and sub-paths of other two tour. We analyze relation between parameters and length of an obtained tour, and indicate a guide to adjust parameters. The performance comparison result shows that the proposed method can find a better solution than Simulated Annealing (SA) and GA