（浙江師范大學電子工程系，金華 321004）

摘要：本文在經典粒子群算法的基礎上，引入了交換子和交換序的概念，構造了一種新的粒子群優化算法，并把此算法應用于求解旅行商問題。為了增強算法的局部搜索能力，在改進的算法中加入倒置，局部搜索等方法，同時利用遺傳算法的全局搜索能力強的特點對求到的解再進行優化，同時，對于搜索全局最優路徑方面，通過應用消除交叉路徑的方法進行了優化。應用此算法，對標準的TSPLIB中的典型問題進行了仿真實驗，并與目前已知的最優結果和其它經典的算法進行了比較分析，結果表明采用了所提出的改進粒子群算法來解決旅行商問題，能夠在較少的迭代次數內就得到較為滿意的解。

關鍵詞：粒子群算法；旅行商問題；交換子和交換序；局部搜索；全局搜索

Solution of Travel Salesman Problem Based on Improved Particle Swarm Optimization Algorithm

JIANG Zheng-jin, DUANMU Chun-jiang

(Department of Electronic Engineering, Zhejiang Normal University, Jinhua 321004, China)

Abstract: This paper proposes an improved particle swarm algorithm by using the concepts of the swap operator and swap sequence. This algorithm is then applied to solve the traveling salesman problems. In order to improve the local searching capability, some local searching algorithms, such as inversion and swapping algorithms, are employed. It takes the advantage of strong global searching capability of the Genetic Algorithm to further optimize the results obtained from the particle swarm optimization algorithm, which can further improve the performance. Then it adds an optimization search strategy to eliminate cross paths for obtaining global optimum solution. Typical problems in the TSPLIB are tested and simulated by using the proposed algorithm. Compared with the current results and other classical algorithms, this algorithm can converge to a satisfactory result in fewer iterative times and can get quite satisfactory solutions for the travel salesman problem.

Key words: particle swarm algorithm; traveling salesman problem; swap operator and swap sequence; local searching; global searching