基于改进粒子群优化算法的TSP问题研究

Research on Traveling Salesman Problem Based on Improved Particle Swarm Optimization Algorithm

针对标准粒子群优化算法易出现问题,提出一种改进粒子群算法。该算法为不同的粒子分配不同的任务,对性能较好的粒子使用较小的惯性权重,对性能较差的粒子采用较大的惯性权重,惯性权重根据适应度函数自适应调整,更好地平衡算法的全局与局部搜索能力,提高算法的多样性与搜索效率。用14点TSP标准数据对算法性能进行测试,结果表明该算法能够较早跳出局部最优,具有较高的收敛速度和收敛率。

To overcome premature searching by standard Particle Swarm Optimization（PSO） algorithm,an improved particle swarm optimization algorithm is proposed.In the new algorithm,different particles are assigned specific tasks.Better particles are given smaller inertial weights,while worse ones are given larger inertial weights.And the particle＇s inertial weights are adaptively adjusted according to its fitness function.These strategies improve the PSO algorithm at the aspects of diversity and the balance of exploration and exploitation.This paper tests the algorithm with a Traveling Salesman Problem with 14 nodes.The result shows that the algorithm can break away from local minimum earlier and it has high convergence speed and convergence ratio.