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

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

作　　者：强宁[1] 康凤举[1] 

机构地区：[1]西北工业大学航海学院,陕西西安710072

出　　处：《陕西师范大学学报（自然科学版）》2015年第6期36-42,共7页Journal of Shaanxi Normal University：Natural Science Edition

基　　金：船舶预研支撑技术基金(11J4.1.1);水下信息处理与控制国家重点实验室基金(9140C2305041001)

摘　　要：标准粒子群算法(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.

关 键 词：多旅行商问题 粒子群算法 学习策略 编解码方法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]