Computer Engineering and Applications ›› 2021, Vol. 57 ›› Issue (6): 67-73.DOI: 10.3778/j.issn.1002-8331.2003-0296

Previous Articles     Next Articles

Ant Colony Algorithm with Adaptive Grouping

BU Guannan, LIU Jianhua, JIANG Lei, ZHANG Dongyang   

  1. 1.School of Information Science and Engineering, Fujian University of Technology, Fuzhou 350118, China
    2.Fujian Provincial Key Laboratory of Big Data Mining and Applications, Fuzhou 350118, China
  • Online:2021-03-15 Published:2021-03-12

一种自适应分组的蚁群算法

卜冠南,刘建华,姜磊,张冬阳   

  1. 1.福建工程学院 信息科学与工程学院,福州 350118
    2.福建省大数据挖掘与应用技术重点实验室,福州 350118

Abstract:

Ant Colony Optimization(ACO) Algorithm is an intelligent algorithm that can be applied to solve Traveling Salesman Problem(TSP). However, in solving TSP, ACO algorithm has a slow convergence rate and is easy to fall into local optimal solution, so grouping ant colonies can enhance the global search ability and improve the performance of solving path planning. In this paper, the relationship between the size of ant colony and the performance of ant colony algorithm is analyzed, and an ant colony algorithm with adaptive grouping is proposed, which adopts the policy of the group number decreasing over iteration. The new algorithm is applied to solve the TSP. The comparison of experimental results show that the adaptive grouping ant colony algorithm has significantly improved the convergence speed and search quality.

Key words: Traveling Salesman Problem(TSP), ant colony algorithm, grouping, adaptive

摘要:

蚁群优化算法是一种能应用于求解旅行商问题(Traveling Salesman Problem,TSP)的智能算法,但蚁群算法在求解TSP路径规划问题中存在收敛速度慢、易陷入局部最优解问题,而将蚂蚁算法的蚁群分组,能增加全局搜索能力,提高求解路径规划性能。通过分析蚁群分组大小与蚁群算法性能的关系,并提出了一种自适应分组蚁群算法,采用一种随迭代分组数减少策略方法,并将其应用于对TSP路径规划问题求解。通过实验结果对比表明,自适应分组蚁群算法在收敛速度和搜索质量方面都有了明显提高。

关键词: 旅行商问题, 蚁群算法, 分组, 自适应