改进混合粒子群算法求解旅行商问题

摘要：

针对混合粒子群算法在求解旅行商问题(TSP)时容易陷入局部最优导致解的质量下降的情况,提出一种改进的混合粒子群算法.通过基于贪心策略的粒子初始化操作,使得初始搜索空间质量提高;加入动态学习概率来平衡粒子群算法中的个体学习和群体学习;在个体学习和群体学习中加入Metropolis准则,依一定概率来接受劣解,能够有效地增加种群多样性和提高跳出局部最优的能力;变异操作采用2-opt局部优化的策略,能够有效地解决路径交叉问题,增强算法局部寻优能力,求得更高质量的解.利用Matlab对改进混合粒子群算法和其他4种算法在TSPLIP实例上进行试验,结果显示改进混合粒子群算法在求解精度、稳定性以及解决较大规模TSP上都具有优势.

关键词：粒子群算法、遗传算法、贪心策略、Metropolis准则、2-opt局部优化、旅行商问题

所属期刊栏目：12

分类号：TP301.6(计算技术、计算机技术)

资助基金：江苏师范大学研究生科研实践创新计划资助项目2021XKT0157

在线出版日期：2022-12-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：229-235