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

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

李維平(Wei-Ping Lee) ； 江正文(Cheng-Wen Chiang) ； 賀嘉生(Jia-Sheng Heh) ； 李佩玲(Pei-Ling Lee)

《先進工程學刊》 5卷4期 (2010/10) Pp. 377-383

https://doi.org/10.29948/JAE.201010.0012

摘要

旅行銷售員問題(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 and has been solved in many researches with differential methodology. Genetic Algorithm is very popular to solve the well known TSP because of extensive applications and easily encoding. Particle Swarm Optimization (PSO) is an algorithm with concept of ”group knowledge”, it's useful to solve optimization problems cause of quick convergence but it's difficult to encode for discrete problems, for example TSP. According to the above, we combine the concepts of GA and PSO algorithm to solve Traveling Salesman Problem. The experimental results show the proposal is more stable and the results were better for solving TSP.

並列關鍵字

traveling salesman problem ； particle swarm optimization algorithm ； genetic algorithm