考虑动态导向与邻域交互的双蚁型算法

摘要：

针对蚁群算法在求解旅行商问题(TSP)时,易出现陷入局部最优和收敛速度较慢的问题,提出了考虑动态导向与邻域交互的双蚁型算法.首先,结合动态导向策略,在迭代前期增加属于最大生成树路径上的动态信息素,从而有效增加种群多样性;在迭代后期增加属于最小生成树路径上的动态信息素,使其加快收敛速度.进一步,将蚂蚁分为两类,融入邻域交互策略,第二类蚂蚁通过吸引因子改进状态转移和局部信息素更新公式,并运用最大-最小蚂蚁系统(MMAS)信息素限制策略,使其不仅提高了收敛性,又能防止算法过早停滞.求解TSP测试集及与其他改进蚁群算法对比的实验结果表明,改进后的算法既能有效加快收敛速度,又能避免陷入局部最优,从而获得更精确的解,尤其在针对大规模TSP问题时效果更为显著.

关键词：蚁群算法、最大生成树、最小生成树、吸引因子、旅行商问题(TSP)

所属期刊栏目：14

分类号：TP18(自动化基础理论)

资助基金：The National Natural Science Foundation of China under Grant Nos. 61673258, 61075115 国家自然科学基金

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

页数：共12页

页码：1005-1016