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.