以混合基因與粒子群演算法求解旅行銷售員問題

A Hybrid of Genetic Algorithm and Particle Swarm Algorithm to Solve Traveling Salesman Problem

李佩玲(Pei-Line Lee)

指導教授 ： 李維平

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

https://doi.org/10.6840/cycu200600572

摘要

旅行銷售員問題(Traveling Salesman Problem; TSP)是最佳化問題中一個相當經典的例子，已有許多相關研究運用不同的技術來求解TSP問題。粒子群最佳化演算法(Particle Swarm Optimization; PSO)是一種群體智慧演算法，在最佳化的解題上具有收歛快速的表現，但受限於編碼形式不適用於求解離散問題，所以以PSO來求解TSP問題則無法做到靈活運用。而求解TSP最常用的技術為基因演算法(Genetic Algorithm; GA)，雖然編碼靈活、應用廣泛，但它在執行效率上較PSO差，求解TSP問題須花費較多的執行時間。因此研究將基因演算法與粒子群演算法做結合，提出混合基因與粒子群演算法，將基因編碼靈活的優點與PSO收歛快速的優點做結合，能在求解TSP問題上獲得更精確及穩定解答。

關鍵字

旅行銷售員問題 ； 粒子群最佳化演算法 ； 基因演算法

並列摘要

Traveling Salesman Problem(TSP) is a classical problem of optimization, Many research has used different technology to solve TSP. Particle Swarm Optimization (PSO) is an algorithm that use concept of "group knowledge", PSO in solving a problem of optimization has an advantage of quickly convergence but PSO is hard to encode for discrete problem, for this reason, single PSO is not suitable for solving TSP. Genetic Algorithm is most popular to solve the well known TSP because GA is easy to encode and extensive applications but PSO has efficiency of executing more than GA, in other words, GA need more time cost to solve TSP.
According to the above, my study suggests that GA combine with PSO algorithm. That is a hybrid of Genetic Algorithm and Particle Swarm Algorithm to solve Traveling Salesman Problem. This method is combination of GA and PSO advantage. It can catch more exact and stable answer in solving TSP.

並列關鍵字

Particle Swarm Optimization Algorithm ； Genetic Algorithm ； Traveling Salesman Problem

參考文獻

[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.

[3] 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.

[4] Laporte,G.., "The Traveling Salesman Problem: A overview of exact of approximate algorithms," Eupopean Journal of Operational Research, Vol. 59, , 1992, ppt. 231~247.

[5] Mohan,C.K. and Al-kazemi, "Discrete particle swarm optimization," Procedings of the Workshop on Particle Swam Optimizatin 2001,Indianapolis, , , 2001, pp. 622~625.

[7] 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.