A novel approach to speed up ant colony algorithm via applying vertex coloring. Issue 6 (2nd November 2018)

• Record Type: Journal Article
• Authors: Li, Xu; Liu, Jia-Bao
• Is Part Of: International journal of parallel, emergent and distributed systems. Volume 33:Issue 6(2018)
• Page Start: 608
• Page End: 617
• Publication Date: 2018-11-02
• Subjects: Ant colony optimization (ACO) -- clustering -- vertex coloring; Parallel computers -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Computer algorithms -- Periodicals; 004.35
• DOI: 10.1080/17445760.2017.1298758
• Languages: English
• ISSNs: 1744-5760

Abstract

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(mN t), 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.