加速度粒子群算法在多旅行商问题中的应用

Application of a new acceleration particle swarm optimization for solving multiple traveling salesman problems

标准粒子群算法(PSO)在求解多旅行商问题(MTSP)时易发生早熟收敛,为此提出一种新的加速度粒子群算法。借鉴力学思想将粒子的运动描述为受力以后在解空间中的搜索运动,粒子受个体最优、全局最优的牵引力,并受局部最优的排斥力,加速度由粒子所受的合力决定。通过审敛操作判断早熟收敛,当发生早熟时局部最优对所有粒子产生的排斥力使种群跳出局部最优继续搜索。为进一步提高算法效率,针对MTSP问题的特点设计了基于维度的粒子学习策略和编解码方法。仿真结果表明,该算法能够有效克服早熟收敛,从而提高解的收敛性和稳定性,为MTSP问题提供了一种可行的方法。

To overcome the premature convergence of the standard particle swarm optimization（PSO）in solving multiple travelling salesman problems（MTSP）,a new acceleration particle swarm optimization is constructed.Rely on the idea of mechanics,the movement of particle is described as search motion driving by force in solution space.The particle is attracted by personal best force,global best force and repelled by local best force.Thus the acceleration of particle depends on the resultant of forces.Using convergence criterions to estimate premature convergence,the local best will repel all the particles when premature convergence occurs,so the particle swarm can jump out the local best and continue to search.In order to improve the efficiency of the algorithm,a dimensional learning strategy of particle and a new coding method are designed for MTSP.The simulation results show that the proposed algorithm can effectively overcome the premature convergence,and improve the quality and stability of solutions.Thus it provides a feasible method for MTSP.