以粒子群演算法求解旅行家問題

Modified Particle Swarm Optimization Algorithms for the Traveling Salesman Problem

吳昌志(Chih-Jyz Wu)

指導教授 ： 李維平

中原大學/商學院/資訊管理學系/碩士(2007年)

https://doi.org/10.6840/cycu200700241

摘要

粒子群演算法（Particle Swarm Optimization, PSO）是一種擁有群體智慧的演算法，以模擬鳥群覓食的行為，讓粒子的每一次移動皆能夠參考其他粒子的移動資訊，以求取全體最佳的解，但由粒子群演算法的編碼方式，並不適用於求解離散型問題。由於傳統的粒子群演算法的維度值是一組連續的實數值，編碼方式不利於求解旅行家問題，故本研究採用權重編碼的方式來代表城市走訪的組合。旅行家問題（Traveling Salesman Problem；TSP）是組合最佳化問題的典型代表，其應用範圍雖廣，解題複雜度卻屬於NP-Complete，因此實務應用上多以啟發式解法(Heuristic)來求得近似解。本研究使用粒子群演算法，搭配權重編碼方式來代表城市走訪的組合，利用粒子群演算法快速收斂的特性，混合貪婪演算法及2-Opt演算法，盼能在求TSP問題的最佳化解答能更精確及穩定。

關鍵字

旅行銷售員問題 ； 粒子群最佳化演算法 ； 2-Opt演算法 ； 貪婪演算法

並列摘要

According Particle Swarm Optimiztion Algorithm, is an swarm intelligence Algorithm. Throught simulate birds behavior,each particle share information each other to reach the best result. But the Particle Swarm Optimiztion Algorithm is good at the continue function,be bad at discrete function. For proofing then Particle Swarm Optimiztion Algorithm can be used at discrete problem, this article combine Particle Swarm Optimiztion Algorithm with 2-Opt algorithm and Greed mtheod to slove Traveling salesman problem. The performance would be superior then the original algorithm.

並列關鍵字

Particle Swarm Optimization ； Traveling salesman Problem ； Greed method ； 2-Opt

參考文獻

[11] Shubhra Sankar Ray,Sanghamitra Bandyopadhyay and Sankar K.Pal, “New Operators of Genetic Algorithms for Traveling Salesman Problem”, Proceedings of the 17th International Conference on Pattern Recognition,Vol. 2,,2004,pp.497~500.

[1] Chia-Feng Juang, “ A Hybrid of Genetic Algorithm and Particle Swarm Optimization for Recurrent Network Design”,IEEE Transactions on Systems,Man, and Cybernetics,Vol. 34,No 2,2004,pp.997~1006

[2] Eberhart R.C. and Kennedy J. , “A new optimizer using particles swarm theory”, Procceedings of the 1995 IEEE Inernational Conference on Neural Networks,1995,vol. 4,,pp. 1942-48

[3] Farzaneh Afshinmanesh, Alireza Marandi, Ashkan Rahimi-Kian, Member, IEEE” A Novel Binary Particle Swarm Optimization Method Using Artificial Immune System. “, Serbia & Montenegro, Belgrade, November 22-24, 2005, pp. 217~220

[4] Kennedy J. and Eberhart R.C. , “A discrete binary version of the particle swarm algorithm”, Proc.1997 Conf. on Systems,Man, and Cybernetics, Piscataway, 1997,pp. 4104~4109.