计算机科学与探索

作者：潘晗，游晓明，刘升

单位：1. 上海工程技术大学 电子电气工程学院，上海 2016202. 上海工程技术大学 管理学院，上海 201620

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

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

来源：2020年第6期

《计算机科学与探索》期刊编辑部

查看计算机科学与探索杂志2020年第6期