A Novel Parallel Ant Colony Optimization Algorithm with Dynamic Transition Probability

Parallel implementation of ant colony optimization (ACO) can reduce the computational time obviously for the large scale combinatorial optimization problem. A novel parallel ACO algorithm is proposed in this paper, which use dynamic transition probability to enlarge the search space by stimulating more ants choosing new path at early stage of the algorithm; use new parallel strategies to improve the parallel efficiency. We implement the algorithm on the Dawn 400L parallel computer using MPI and C language. The numerical result indicates that: (1) the algorithm proposed in this paper can improve convergence speed effectively with the better solution quality; (2) more computational nodes can reduce the computational time obviously and obtain significant speedup; (3) the algorithm is more efficient for the large scale traveling salesman problem with fine quality of solution.