MPI-based Parallel Ant Colony Algorithm

Ant Colony Optimization algorithm is a new recta heuristic algorithm. Ant Colony Optimization algorithm is robust and exhibits great distributing computing mechanism. So Ant Colony Optimization can be combined with other optimization methods to solve various combination optimization problems such as TSP.The MPI about design pattern of parallel programming based on high performance computing technology is the standard of message passing used in a parallel environment with famous in resent. MPICH is a fully realized about MPI, is a parallel and distributed environment with extensive application. Set up the connection about existing computer to carry on the high performance calculate is very easy by the MPICH.Due to the ant colony algorithm has natural parallelism, suitable for parallel computing. In this paper, the parallel genetic algorithm based on Message Passing under the environment of pc-cluster has studied, choose a suitable for fleet system and characteristics of ant colony optimization algorithm of parallel strategies, and successfully applied to optimize the TSP.Firstly, the paper discuss the parallel computing, and describes the parallel computer architecture, theory of parallel programming and parallel algorithms. Then, introduced the MPI of message passing standard be used in parallel programming environment with popular and its basic function, build a airplane cluster system based on windows operating using MPICH. And the paper introduces in detail the Ant Colony Optimization algorithm and programming designed of Ant Colony Optimization algorithm based on MPI. The paper analysis and design the problem of TSP using a coarse-grained parallel Ant Colony Optimization algorithm, and make it realized fully by program.Finally, the paper has optimized TSP with 25 customer using the standard Ant Colony Optimization algorithm and parallel Ant Colony Optimization algorithm program, the output of its results were compared and analyzed. Although there is much to be improved about the experiment, the result is satisfactory.