结合协同机制与动态调控策略的双蚁群算法

摘要

针对蚁群算法在求解旅行商问题(TSP)时出现的收敛速度慢和多样性较差的问题,提出结合协同机制与动态调控策略的双蚁群算法.首先,将蚁群根据适应度值动态地划分为导向蚁和合作蚁,从而构成异构双蚁群.其次,异构双蚁群采用协同机制平衡算法多样性和收敛速度:导向蚁在路径构建时引入传播因子,增大蚂蚁选择新路径的概率,扩大搜索范围,提高算法多样性;合作蚁受导向蚁中最优路径的引导,当路径相似度达到阈值时,启动合作算子,加快算法收敛速度.最后,引入动态调控策略,在全局信息素更新时引入自适应调控算子,对全局最优路径的信息素进行正向激励或反向惩戒,加快收敛速度的同时避免算法陷入局部最优.求解TSP测试集的实验结果表明,该算法不仅提高了解的质量,保证了算法多样性,而且加快了算法收敛速度,尤其在大规模城市问题中效果更为明显.