一种应用于旅行商问题的莱维飞行转移规则蚁群优化算法

来源：计算机应用研究杂志2024年第5期北京时间：

作者：丁增良,陈珏,邱禧荷,

单位：上海工程技术大学电子电气工程学院,上海201620；

摘要：针对旅行商问题（TSP）提出了一种基于莱维飞行转移规则的蚁群优化算法。该算法结合了基于莱维飞行和蚁群系统算法（ant colony system，ACS）的转移规则，形成了一种动态权重的混合转移规则，该策略能够有效地帮助算法跳出局部最优，增强全局搜索能力。此外，随机多路径优化3-opt策略通过随机抽取部分路径与当前最优路径组合，增加算法的多样性。当算法陷入停滞时，采用信息素平均随机重置策略重置路径上的信息素浓度，有助于算法跳出局部最优。实验结果显示，所提算法在处理多个不同规模的TSP实例时，与最优解的误差保持在3%以内，证明了该算法在TSP中具备出色的收敛性和避免陷入局部最优解的能力。

关键词：蚁群算法,旅行商问题,莱维飞行,3-opt,

基金资助：国家自然科学基金青年基金资助项目(62102241)；“科技创新行动计划”自然科学基金面上项目(23ZR1425400)；；