Abstract:

This paper researches a hybrid Particle Swarm Optimization(PSO) algorithm for solving travel salesman problem. In order to improve the capability of local searching, some local searching algorithms such as inversion and swapping are added. It takes advantage of strong global searching capability of Genetic Algorithm(GA) to further optimize the results got from PSO algorithm, which can further improve the performance of the hybrid algorithm. Besides, it adds an optimization to eliminate cross path of global optimum solution. Simulation result shows this hybrid algorithm can converge to a satisfactory result within a few generations for middle and small scale travel salesman problem.

Key words: travel salesman problem, Particle Swarm Optimization(PSO) algorithm, Genetic Algorithm(GA), local searching

摘要：

针对旅行商问题提出一种混合粒子群优化算法。为了增强算法的局部搜索能力，在粒子群优化算法中加入倒置、对换等局部搜索算法。利用遗传算法全局搜索能力强的特点对用粒子群优化算法求到的解进行优化，对全局最优路径通过消除交叉路径进行优化，以进一步提高混合算法的性能。仿真结果表明，中小规模旅行商问题能够在较少的代数内收敛到较满意解。

关键词: 旅行商问题, 粒子群优化算法, 遗传算法, 局部搜索

CLC Number: 

• TP312