计算机工程与应用 ›› 2021, Vol. 57 ›› Issue (8): 70-77.DOI: 10.3778/j.issn.1002-8331.2004-0360

• 理论与研发 • 上一篇    下一篇

基于种群相似度的自适应改进蚁群算法及应用

张松灿,普杰信,司彦娜,孙力帆   

  1. 1.河南科技大学 信息工程学院,河南 洛阳 471000
    2.河南科技大学 电气工程学院,河南 洛阳 471000
  • 出版日期:2021-04-15 发布日期:2021-04-23

Adaptive Improved Ant Colony Algorithm Based on Population Similarity and Its Application

ZHANG Songcan, PU Jiexin, SI Yanna, SUN Lifan   

  1. 1.School of Information Engineering, Henan University of Science and Technology, Luoyang, Henan 471000, China
    2.School of Electrical Engineering, Henan University of Science and Technology, Luoyang, Henan 471000, China
  • Online:2021-04-15 Published:2021-04-23

摘要:

针对蚁群算法收敛速度较慢、易陷入局部最优的问题,提出了一种基于种群相似度的自适应改进蚁群算法。利用种群相似度对种群内个体的多样性进行度量并根据优化过程中种群相似度的变化情况自适应地调整蚁群算法的参数和信息素更新策略,提升算法的优化性能。该算法用于求解旅行商问题(Traveling Salesman Problem,TSP)问题,并与经典的蚁群系统(Ant Colony System,ACS)及最大最小蚂蚁系统(MAX-MIN Ant System,MMAS)算法进行比较,实验结果表明改进算法在解的质量与算法稳定性方面得到显著提升,有效地平衡了种群多样性与收敛速度之间的矛盾。

关键词: 蚁群算法, 种群多样性, 种群相似度, 自适应信息素更新, 收敛速度, 旅行商问题

Abstract:

An adaptive improved ant colony algorithm based on population similarity is proposed to solve the problem that ant colony algorithm converges slowly and is prone to local optimality. The population similarity is used to measure the diversity of individuals in the population, and the parameters and pheromone update strategy of the ant colony algorithm are automatically adjusted according to the variation of population similarity in the evolutionary process to improve the optimization performance of the algorithm. The algorithm is used to solve the TSP problem and compared with the classic ACS and MMAS algorithms. The experimental results show that the proposed algorithm has significantly improved the quality of the solution and the stability of the algorithm, and effectively balances the contradiction between population diversity and convergence speed.

Key words: ant colony algorithm, population diversity, population similarity, adaptive pheromone updating, convergence speed, traveling salesman problem