计算机工程与应用 ›› 2019, Vol. 55 ›› Issue (3): 15-22.DOI: 10.3778/j.issn.1002-8331.1809-0316

• 热点与综述 • 上一篇    下一篇

基于聚度的自适应动态混沌蚁群算法

刘明霞1,游晓明1,刘  升2   

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

Adaptive Dynamic Chaotic Ant Colony Algorithm Based on Degree of Aggregation

LIU Mingxia1, YOU Xiaoming1, LIU Sheng2   

  1. 1.College of Electronic and Electrical Engineering, Shanghai University of Engineering Science, Shanghai 201620, China
    2.College of Management, Shanghai University of Engineering Science, Shanghai 201620, China
  • Online:2019-02-01 Published:2019-01-24

摘要: 针对蚁群算法收敛速度慢,容易陷入局部最优的问题,提出了一种基于聚度的自适应动态混沌蚁群算法(A_ACS)。在迭代前期利用聚度来衡量解的多样性,自适应调节局部信息素分布,同时引入混沌算子来增加种群多样性,避免算法陷入局部最优,从而提高解的精度;在迭代后期去掉混沌算子,减少混沌扰动性,来提高算法的收敛速度。将A_ACS用于TSP问题,仿真结果表明,该算法较ACS和MMAS算法减少了搜索时间,并且提高了解的质量,其平衡了多样性与收敛性之间的矛盾,整体性能优于其他两种算法。

关键词: 蚁群算法, 聚度, 混沌优化, 自适应信息素更新, 旅行商问题

Abstract: Aiming at the problem that the ant colony algorithm is slow in convergence and easily falls into a local optimum, an adaptive dynamic chaotic ant colony algorithm(A_ACS) based on the degree of aggregation is proposed. In the early iterations, the degree of aggregation is used to measure the diversity of solutions and self-adaptively adjust the local pheromone distribution, and chaos operators are introduced to increase the diversity of the population to avoid the algorithm falling into a local optimum, thereby improving the accuracy of the solution. In the later iterations, the chaotic operator is removed to reduce the chaotic disturbance and increase the convergence speed of the algorithm. The A_ACS is used for the TSP problem. The simulation results show that the proposed algorithm reduces the search time and improves the quality of solution compared with the ACS and MMAS algorithm. It balances the contradiction between diversity and convergence, and the overall performance is better than the other two algorithms.

Key words: ant colony algorithm, degree of aggregation, chaotic optimization method, adaptive method of updating pheromone, traveling salesman problem