改良粒子群演算法求解旅行銷售員問題

Modified Particle Swarm Optimization Algorithms for the Traveling Salesman Problem

李維平(Wei-Ping Lee) ； 張加憲(Jia-Hsien Chang)

《先進工程學刊》 6卷1期 (2011/01) Pp. 21-30

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

摘要

本研究改良粒子群演算法(Particle Swarm Optimization, PSO)應用於旅行銷售員問題(Traveling Salesman Problem, TSP)，與粒子群演算法在旅行銷售員問題的相關文獻比較，獲得更具精確性的解。傳統PSO解TSP問題僅能在少數城市內有較好的成效，而本研究放棄遵循PSO原有的粒子移動公式及應用於TSP的各種轉換方式，改以最近鄰點法(Nearest Neighbor)進行初始化，配合區域搜尋演算法(Local Search, K-Opt)中2-Opt混合Or-Opt取代粒子移動方式。最後融入粒子群體智慧(Swarm Intelligence, SI)概念的精神，提出全體最佳解以及個體最佳解的學習策略。以TSPLIB測試集為例，本演算法在城市數量442個城市以內僅小於1.41%的誤差，然而在100個城市數量內皆達到公佈的最佳值。

關鍵字

旅行銷售員問題 ； 粒子群演算法 ； 群體智慧 ； 區域搜尋演算

並列摘要

This paper presents an implementation of the Modified Particle Swarm Optimization (PSO) for solving the Traveling Salesman Problem (TSP), and comparison with the literature related to the application of using PSO to solve the problem of TSP, this new method can obtain the result more precise. Using traditional PSO to solve TSP problem only works better in a few cities. Therefore, this research abandons keeping the original formula of PSO and any kinds of transformation of TSP. It initializes the Nearest Neighbor, and cooperates the Local Search with 2-Opt combined with Or-Opt to replace the particle moving. At the end, it merges the concept of Swarm Intelligence (SI), and brings the learning strategy of global optimum and individual optimum. Take a case study on TSPLIB for example, the algorithm provides the solution with deviation less than 1.41%, when the sample cities are less than 442; however, it achieves the current best known solution when the sample cities are less than 100.

並列關鍵字

traveling salesman problem ； particle swarm optimization ； swarm intelligence ； K-Opt