TSP和GTSP的基本微粒群算法 Particle swarm optimization-based algorithms for TSP and generalized TSP

a College of Computer Science and Technology, Jilin University, Key Laboratory of Symbol Computation and Knowledge Engineering of the Ministry of Education, Changchun 130012, China b Institute of High Performance Computing, Singapore 117528, Singapore c Department of Mechanical Engineering, National University of Singapore, 9 Engineering Drive 1, Singapore 119260, Singapore Received 31 July 2005; received in revised form 10 February 2007 Available online 31 March 2007 Communicated by Wen-Lian Hsu Abstract A novel particle swarm optimization (PSO)-based algorithm for the traveling salesman problem (TSP) is presented. An uncertainsearching strategy and a crossover eliminated technique are used to accelerate the convergence speed. Compared with the existingalgorithms for solving TSP using swarm intelligence, it has been shown that the size of the solved problems could be increased by using the proposed algorithm.Another PSO-based algorithm is proposed and applied to solve the generalized traveling salesman problem by employing thegeneralized chromosome. Two local search techniques are used to speed up the convergence. Numerical results show the effective-ness of the proposed algorithms. © 2007 Elsevier B.V. All rights reserved. 1. Introduction 2. Particle swarm optimization (PSO) algorithm 3. Discrete PSO algorithm for TSP 4. Discrete PSO method for GTSP 摘要:一个新的的关于旅行商问题（TSP）的基本微粒群算法已经提出。一项不定的搜索策略和消除交叉的技术用于加速收敛速度。和现有使用群智能解决TSP算法相比较，它显示解决的问题的规模可能比使用提出的算法增加。提议并且使用广义染色体运用另一种基本PSO的算法解决广义旅游推销商问题。两种局部方法常用来加速收敛速度。数字结果显示已提出的算法的有效性。 2007 Elsevier B.V.获得专利。 1.引言 2.微粒群算法（PSO） 3.TSP的离散变量的微粒群算法 4.GTSP的离散PSO算法 5.结论