基于平滑归一化信息素熵协调的多策略自适应蚁群优化算法求解对称旅行商问题
《Applied System Innovation》:A Multi-Strategy Adaptive Ant Colony Optimization Algorithm for Solving the Traveling Salesman Problem
【字体:
大
中
小
】
时间:2026年10月02日
来源:Applied System Innovation 3.4
摘要
传统的蚁群优化算法(ACO)在求解旅行商问题(TSP)时,常常面临初始信息素信息不足、过早收敛以及在不同问题规模下适应性有限等挑战。本研究提出了一种多策略自适应蚁群优化算法,称为MSA-ACO。与那些附加策略由独立或预设规则控制的混合ACO方法不同,MSA-ACO采用平滑归一化信息素熵作为共享的内部搜索状态信号。该信号协调搜索阶段的切换、开发偏好、信息素蒸发强度、启发式信息依赖度以及基于尺度相关控制曲线的自适应3-opt预算。此外,还引入了基于排名加权的多元精英初始化方法和候选受限的层次化2-opt/3-opt搜索,以改善早期引导和解决方案细化。在35个TSPLIB实例上的实验表明,MSA-ACO在22个实例上获得了最佳已知解,其最佳解的平均偏差为0.17%,而ACS为3.87%,MMAS为5.27%。其最大偏差为1.22%,且在33个实例上偏差保持在1%以内。非参数检验确认,其整体解质量显著优于ACS和MMAS。在等距离查询预算条件下,MSA-ACO在st70、kroC100和kroA150上获得了最低的均值巡游长度,相较于基于ACS的局部搜索,在kroC100和kroA150上取得了显著改善。逐组分消融和顺序计时结果表明,各组件的效果因实例而异,并识别出3-opt是计算成本的主要来源,也是较大实例上重要的细化机制。此外,与固定1000次迭代的设置相比,按规模分段的迭代预算在四个代表性实例上将平均运行时间减少了28.06%至83.75%,同时在eil76和ts225上仍获得了最佳已知解(BKS),并在ch150和kroA200上分别实现了约0.30%和0.20%的平均偏差。总体而言,MSA-ACO为对称TSP提供了一种有效的尺度感知优化框架,在不同实例规模下兼顾了 consistently 高质量的解与可控的计算代价。
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号