计算机科学与探索

作者：吴立胜, 游晓明, 刘升

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

关键词：蚁群算法,邻域耦合机制,双边滤波,基尼不纯度,旅行商问题（TSP）

针对蚁群算法在求解旅行商问题（TSP）中收敛速度慢且易陷入局部最优等问题，提出一种结合邻域耦合机制与双边滤波的双蚁群算法（NBACO）。首先，算法通过战斗力指数将蚁群动态分成士兵蚁与指挥蚁，士兵蚁主要负责提高算法的求解精度，指挥蚁主要负责提高算法的收敛速度，两类蚂蚁分工合作从而有效平衡算法的求解精度与收敛速度。其次，采用邻域耦合机制，当指挥蚁经过公共区间时，在公共区间及其邻域动态散布微量的信息素，以增大对蚂蚁的吸引力，增加蚂蚁选择公共区间及其邻域的概率，从而提高算法的收敛速度。进一步，当算法陷入局部最优时，引入基于基尼不纯度的双边滤波策略，动态削弱当前最优路径上的信息素浓度，进而缩小最优路径与其邻域路径的信息素浓度差，在下一次迭代时增大蚂蚁选择其他非最优路径的概率，从而帮助算法摆脱局部最优。最后，对大量TSP实例进行仿真，实验结果表明改进后的蚁群算法有效平衡了算法求解精度和收敛速度。

来源：2023年第9期

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

查看计算机科学与探索杂志2023年第9期