改进粒子群优化算法求解TSP问题

Improved particle swarm optimization for traveling salesman problem

针对粒子群优化算法易陷入局部极值的缺点,提出一种改进粒子群算法,该算法借鉴贪婪算法的思想初始化种群,利用两个种群同时寻优,并将遗传算法中交叉和变异操作引入其中,实现种群间的信息共享。用14点TSP标准数据对算法性能进行了测试,结果表明该算法能够较早跳出局部最优,具有较高的收敛速度和收敛率。

In allusion to particle swarm optimization being prone to get into local minimum,an improved particle swarm optimization algorithm is proposed.The algorithm draws on the thinking of the greedy algorithm to initialize the particle swarm. Two swarms are used to optimize synchronously,and crossover and mutation operators in genetic algorithm are introduced into the new algorithm to realize the sharing of information among swarms.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.