Research On Parallel Ant Colony Algorithm And Application

Ant Colony Optimization Algorithm is a new meta heuristic algorithm. Ant Colony Optimization Algorithm is robust and exhibits great distributing computing mechanism so ACO can be combined with other optimization methods to solve various combination optimization problems such as TSRAnt Colony Optimization Algorithm is naturally with parallelism which is proper to parallel compution. The thesis is focused on Ant Colony Optimization Algorithm and our work including: research on parallelism of Ant Colony Optimization Algorithm; research on applications of parallel Ant Colony Optimization Algorithm; research on optimal parameter combination of Ant Colony Optimization Algorithm. MPICH cluster system is adopted to simulate the proposed algorithms with proper parallel strategy selection according to characteristics of the cluster and Ant Colony Optimization Algorithm.We propose a parallel algorithm to solve massive WTA problem. The simulated experiment demonstrates that the proposed algorithm is order of magnitude better than its counterpart serial algorithm. The speedup factor of our algorithm (speedup factor up to 3.851 with 4 CPUs) and parallel efficiency (up to 0.963) are fairly ideal.In order to determine the optimal parameter optimization of the algorithm, we study the parameter selection of the Ant Colony Optimization Algorithm. There are a series of parameters for the algorithm including number of ants, expected heuristic factor, local Pheromone evaporation factor, global Pheromone evaporation factor,etc.We compare different selections of these parameters using ACS-WTA-MPI algorithm in a series of simulated experiments and attain optimal parameter combination of WTA.Finally, the work of this thesis is summarized and the prospective of future research is discussed.