A New Parallel Ant Colony Optimization Algorithm for Traveling Salesman Problem
As a successful metaheuristic, Ant Colony Optimization (ACO) performs excellently in solving most combinatorial optimization problems. It is difficult to speedup the algorithm when the complexity of the problem increases. Parallel implementing is a good ideal to speedup it. A new parallel ant colony optimization (PACO) algorithm is presented, which has the characteristics of coarse-granularity interacting multi ant colonies, partially asynchronous parallel implementation (PAPI) and a new information exchange strategy. We study the influence of the scale of the problem and the number of computing nodes on the performance of the PACO algorithm proposed in this paper. Numerical results are obtained by using message passing interface (MPI) and C language on the dawn 4000L parallel computer. The numerical results indicate that the PACO algorithm is more efficient for the large scale traveling salesman problem with fine quality of solution; and more computing nodes can reduce the computing time obviously.
Jie Xiong Caiyun Liu Zhong Chen Xueyu Zou
College of Electronics and Information, Yangtze University, Jingzhou, Hubei, 434023, China College of Information and Math, Yangtze University, Jingzhou, Hubei, 434023, China
国际会议
武汉
英文
171-175
2008-12-19（万方平台首次上网日期，不代表论文的发表时间）