关键词: 关旅行商问题, 粒子群优化算法, 聚类分析, k-中心点法

Abstract: To apply Particle Swarm Optimization (PSO) algorithm oriented to continuous optimization problems in solving Traveling Salesman Problem (TSP), a new coding method based on the priority was put forward to transform the TSP from combinatorial optimization to continuous optimization. And the easy operation and high efficiency of the PSO were reserved. Then an innovative approach based on k-center algorithm was proposed with purpose of preventing PSO algorithm from local optimum. In this approach, the dissimilarity matrix was constructed by simple matching coefficient. Based on this, the k-center algorithm was used to execute cluster analysis on the particle swarm, which made particles exchange information with each other and search the best solution in a larger solution space than ever, so as to prevent the algorithm from local optimum. Finally, some TSPLIB examples were used to verify the effectiveness of the improved PSO in the TSP.

Key words: traveling salesman problem, particle swarm optimization algorithm, cluster analysis, k-center