融合奖惩学习策略的动态分级蚁群算法

作者：莫亚东; 游晓明^*; 刘升

来源：计算机科学与探索, 2021, 15(09): 1703-1716.

• 蚁群算法(ACO)
• 学习策略
• 反馈算子
• 动态分级
• 旅行商问题(TSP)

为应对传统蚁群算法在解决旅行商问题(TSP)中求解精度不高、算法易早熟等问题,提出融合奖惩学习策略的动态分级蚁群算法(DHL-ACS)。首先将蚁群动态划分为帝国蚁、殖民蚁及国王蚁,其中帝国蚁与殖民蚁执行局部信息素更新,国王蚁执行全局信息素更新,在局部信息素更新中帝国蚁执行较大权重系数,负责对较优解的开发增强算法导向性,殖民蚁执行较小权重系数,负责对次优解的探索保证算法多样性,并利用帝国蚁与殖民蚁交换优质解的方式提高解的精度。其次提出一种改进的学习策略,通过奖励帝国蚁与殖民蚁的公共路径以实现较优解的同化作用,进而提高算法收敛速度;进一步当算法停滞时,引入反馈算子来减少国王蚁路径上的信息素,以达到对较高信息素路径的惩罚作用,从而提高种群多样性,增强算法跳出局部最优能力。通过对多组TSP数据集实验对比分析,实验结果表明改进后的算法很好地平衡了收敛速度与多样性之间的关系,尤其应对大规模TSP问题,能有效改善解的精度。

• 单位
  电气学院; 上海工程技术大学