计算机科学与探索 ›› 2021, Vol. 15 ›› Issue (8): 1511-1525.DOI: 10.3778/j.issn.1673-9418.2006038

• 人工智能 • 上一篇    下一篇

基于动态重组和协同交流策略的蚁群优化算法

刘一凡,游晓明,刘升   

  1. 1. 上海工程技术大学 电子电气工程学院,上海 201620
    2. 上海工程技术大学 管理学院,上海 201620
  • 出版日期:2021-08-01 发布日期:2021-08-02

Ant Colony Optimization Algorithm Based on Dynamic Recombination and Co-  operative Communication Strategy

LIU Yifan, YOU Xiaoming, LIU Sheng   

  1. 1. School of Electronic and Electrical Engineering, Shanghai University of Engineering Science, Shanghai 201620, China
    2. School of Management, Shanghai University of Engineering Science, Shanghai 201620, China
  • Online:2021-08-01 Published:2021-08-02

摘要:

针对传统蚁群算法在解决旅行商问题(TSP)时所存在的收敛速度慢、易陷入局部最优等问题,提出了基于动态重组和协同交流策略的蚁群优化算法(RCACO)。首先,将蚁群划分为贪婪蚁群和探索蚁群,两类蚁群执行不同的路径构建规则和信息素更新策略,以平衡算法的收敛速度和多样性。其次,采用一种基于线索二叉树的新型动态重组算子,并根据不同的重组策略对解集进行有导向性的动态重组,以提升算法的多样性。进一步,提出一种基于相似度和潜力值的协同交流策略,从全局的角度出发,找到最有潜力成为最优解的路径,并对这些路径给予信息素奖励,以提升算法的收敛速度。最后,算法还加入了停滞规避策略,以帮助蚁群跳出局部最优,提升算法的求解精度。通过Matlab对TSPLIB中的多组案例进行仿真实验,与传统蚁群算法和其他优化算法进行对比分析,仿真结果表明,改进的蚁群算法显著提高了收敛速度和求解精度。

关键词: 旅行商问题(TSP), 蚁群优化算法(ACO), 动态重组, 协同交流, 停滞规避

Abstract:

Aiming at the problems of traditional ant colony algorithm in solving traveling salesman problem (TSP), such as slow convergence speed and easy to fall into local optimum, an ant colony optimization algorithm (RCACO) based on dynamic recombination and cooperative communication strategy is proposed. Firstly, the ant colony is divided into greedy ant colony and exploratory ant colony. The two ant colonies implement different path construction rules and pheromone update strategies to balance the convergence speed and diversity of the algorithm. Secondly, a new dynamic recombination operator based on the clew binary tree is adopted, and the solution set is dynamically recombined according to different strategies to improve the diversity of the algorithm. Furthermore, a collaborative communication strategy based on similarity and potential value is proposed. From a global perspective, the path with the most potential to become the optimal solution is found, and pheromone rewards are given to these paths to improve the convergence speed of the algorithm. Finally, the algorithm also adds a stagnation avoidance strategy to help the ant colony jump out of the local optimum and improve the accuracy of the algorithm. Through the Matlab simulation experiment of multiple groups of cases in TSPLIB, compared with the traditional ant colony algorithm and other optimization algorithms, the simulation results show that the improved ant colony algorithm significantly improves the convergence speed and solution accuracy.

Key words: traveling salesman problem (TSP), ant colony optimization (ACO), dynamic recombination, collaborative communication, stagnation avoidance