求解旅行商问题的改进局部搜索混沌离散粒子群优化算法

来源：计算机应用杂志2016年第1期北京时间：

作者：程毕芸, 鲁海燕, 徐向平, 沈莞蔷

单位：江南大学 理学院, 江苏 无锡 214122

摘要：针对基本离散粒子群优化(DPSO)算法收敛速度慢、易于陷入局部最优等问题,提出了一种基于优秀系数的局部搜索混沌离散粒子群优化(ILCDPSO)算法并用于求解旅行商问题(TSP)。基于轮盘赌选择原理,给每段路径设定一个合理的优秀系数,以提高短边被选择的概率,从而有利于提高算法的寻优能力和收敛速度;为了进一步提高解的精确性,在算法机制中添加了局部搜索策略,通过调整每个城市在给定邻域内的城市路径,提高算法的局部搜索能力;另外,在算法的迭代公式中加入了混沌序列来提高粒子的随机性和多样性,增强了算法的全局搜索能力。最后用国际通用的TSP数据库(TSPLIB)中的若干经典实例对算法进行了测试,并与粒子群优化(PSO)算法、改进的PSO(IPSO)算法和混沌PSO(CPSO)算法等进行了比较。实验数据显示,在相同的实验条件下,与其他算法相比,ILCDPSO算法获得最优解的平均迭代次数较少且获得最优解的次数比例最高。研究结果表明,加入优秀系数后,ILCDPSO算法在收敛速度、全局寻优能力以及稳定性方面均优于其他算法。

关键词：离散粒子群优化算法,旅行商问题,优秀系数,局部搜索,混沌序列

基金资助：国家自然科学基金资助项目(61402201);中央高校基本科研业务费专项资金资助项目(1142050205135260,JUSRP51317B);江苏省自然科学青年基金资助项目(BK20130117)。