求解TSP问题的动态邻域粒子群优化算法

Dynamic Neighborhood Particle Swarm Optimization for TSP

旅行商(TSP)问题是一个典型的NP问题.为了克服基本粒子群优化(PSO)算法在求解离散问题所具有的计算时间长和容易陷入停滞状态等问题,本文基于“簇”思想,对粒子间距离进行重新定义并给出了相应的动态邻域PSO算法.实验结果表明了新型算法在求解TSP问题中的有效性,同时提高了算法的性能,并具有更快的收敛速度.

Traveling salesman problems （TSP） is well known as a NP-hard problem. Particle swarm optimization （PSO） has some shortcomings such as needing much time and easier occurring of stagnation behavior when used in discrete problems. This paper gives a dynamic neighborhood PSO algorithm, which based on ＂cluster＂ and redefines the concept of neighborhoods. The experimental result indicates that the new method speeds up the velocity of the PSO convergence and it has better performance than the original algorithm to escape from local minimum.