Ant Colony Algorithm with Adaptive Grouping

doi:10.3778/j.issn.1002-8331.2003-0296

Abstract

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路径规划问题求解。通过实验结果对比表明，自适应分组蚁群算法在收敛速度和搜索质量方面都有了明显提高。

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

BU Guannan, LIU Jianhua, JIANG Lei, ZHANG Dongyang. Ant Colony Algorithm with Adaptive Grouping[J]. Computer Engineering and Applications, 2021, 57(6): 67-73.

卜冠南，刘建华，姜磊，张冬阳. 一种自适应分组的蚁群算法[J]. 计算机工程与应用, 2021, 57(6): 67-73.

[1]	MA Jun，WANG Yuhao. Object Tracking Algorithm Based on Adaptive Update Strategy and Re-detection Technology [J]. Computer Engineering and Applications, 2021, 57(9): 217-224.
[2]	SHI Chuntian, ZENG Yanyang, HOU Shouming. Summary of Application of Swarm Intelligence Algorithms in Image Segmentation [J]. Computer Engineering and Applications, 2021, 57(8): 36-47.
[3]	ZHANG Songcan, PU Jiexin, SI Yanna, SUN Lifan. Adaptive Improved Ant Colony Algorithm Based on Population Similarity and Its Application [J]. Computer Engineering and Applications, 2021, 57(8): 70-77.
[4]	ZHAO Linsuo, MA Ruiqiang, JIANG Tian, SONG Baoyan,PAN Yishan. Adaptive Early Warning Method for Streaming Big Data Events Based on Two-Stage Regression [J]. Computer Engineering and Applications, 2021, 57(7): 88-94.
[5]	NI Zongjun, CHEN Hui, ZHANG Yun, SU Min, ZHENG Xiujuan. Non-contact Physiological Parameter Estimation Method Based on Adaptive Denoising [J]. Computer Engineering and Applications, 2021, 57(5): 153-160.
[6]	MA Xianghua, ZHANG Qian. Research on Improved Ant Colony Algorithm in Robots Path Planning [J]. Computer Engineering and Applications, 2021, 57(5): 210-215.
[7]	CHEN Shiming, LIN Zipeng, GAO Yanli, PEI Huiqin. Heterogeneous Group Consensus Under Adaptive Coupling Weights [J]. Computer Engineering and Applications, 2021, 57(4): 231-235.
[8]	WANG Fuyin, ZHANG Desheng, ZHANG Xiao. Adaptive Density Peaks Clustering Algorithm Combining with Whale Optimization Algorithm [J]. Computer Engineering and Applications, 2021, 57(3): 94-102.
[9]	CHEN Mingyue, LIU Sanyang. Application of Adaptive Manifold Learning in Fault Diagnosis [J]. Computer Engineering and Applications, 2021, 57(3): 247-252.
[10]	REN Junxiao, CHANG Xin, HOU Ying, CAO Xiaobo. Shared Parking Allocation Model Based on Users’ Preferences and Revenue from Platform [J]. Computer Engineering and Applications, 2021, 57(24): 242-248.
[11]	LI Ya, HOU Yandong, LIU Chang. Adaptive Optimal Fault-Tolerant Control Based on Fault Degree [J]. Computer Engineering and Applications, 2021, 57(23): 295-302.
[12]	XIAO Zhenjiu, KONG Xiangxu, ZONG Jiaxu, YANG Yueying. Image Object Detection Algorithm Based on Adaptive Focal Loss [J]. Computer Engineering and Applications, 2021, 57(23): 185-192.
[13]	ZHANG Zhonglin, ZHAO Yu, YAN Guanghui. Natural Neighbor Density Extremum Clustering Algorithm [J]. Computer Engineering and Applications, 2021, 57(23): 200-210.
[14]	CHANG Yawen, ZHAO Dongqing, SHAN Yanhu. Research on Stereo Matching Algorithm Based on Multi-feature Fusion and Adaptive Aggregation [J]. Computer Engineering and Applications, 2021, 57(23): 219-225.
[15]	CHEN Yao, CHEN Si. Improved Bat Algorithm Based on Self-adaptive Doppler and Dynamic Neighborhood Strategy [J]. Computer Engineering and Applications, 2021, 57(22): 166-176.

Ant Colony Algorithm with Adaptive Grouping

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics