A novel approach to speed up ant colony algorithm via applying vertex coloring

Abstract

Ant Colony Optimization (ACO) is a popular optimal algorithm, whose typical application is to solve Travel Salesman Problem (TSP). The time complexity of ACO is O(mNt), where the parameters m, N and t denote the number of ants, cities and iteration steps, respectively. Improving running speed is an important research focus, and reducing the parameter N and t is an effective way. Especially, reducing the parameter N is an efficient method. In this paper, we present a new clustering algorithm named Vertex Coloring Clustering (VCC), which uses the thought of vertex coloring to classify all cities into some classes and lets ACO act on each class to get local TSP routes, and joins these local routes as a whole route. Owing to Vertex Coloring has property that the number of color is the minimum, the minimum number of classes is obtained in this paper. Each class can be considered as a smaller TSP. So, when ACO algorithm calculate the local route on each class obtained by VCC algorithm, the parameter N and the iteration number t are reduced. The simulation shows that the improved ACO by VCC is faster than the ACO algorithm which uses algorithm Ant-Cycle by factors of 15-750.

Keywords:

• Ant colony optimization (ACO)
• clustering
• vertex coloring

Acknowledgements

The authors would like to express their sincere gratitude to the two anonymous referees and the editors for many friendly and helpful suggestions, which led to great deal of improvement of the original manuscript.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was partly supported by the Anhui Provincial Natural Science Foundation [grant number 1708085QA12] and the Natural Science Foundations for Colleges and Universities in Anhui Province [grant number KJ2016A602] and the general project of Hefei University [13KY04ZR], and partly supported by the Natural Science Foundation of Anhui Province of China [grant number KJ2013B105], the Natural Science Foundation for the Higher Education Institutions of Anhui Province of China [grant number KJ2015A331], The Project of Anhui Jianzhu University under [Grant number 2016QD116].