The Research On Ant Colony Optimization For TSP

Ant colony optimization (ACO) is a bionic intelligence algorithm for optimization,which has the characteristics of positive feedback,distributing computing and heuristic serach. As an important branch of computational intelligence and swarm intelligence,ACO have been successfully applied to solve many combinational optimization problems.This paper makes an exhaustive and systematic study of some typical ACO algorithms,mainly discuss using ACO to solve TSP.Through using TSPLIB as the benchmark,some analyses and remarks are made to compare the performance of some typical ACO algorithms,and the optimum parameter settings are tested and analysed.The results of experiments show that the ACO algorithms have high performance for solving small TSP,can find the optimal solution in short time,but for the large TSP,the current ACO algorithms can't find the global optimal solution in a limited time,it could easily reach the stagnation phase and get the local optimum.So it is necessary to improve the current ACO algorithms,which would have better performance for solving large TSP.In order to correct the shortcoming of the basic ACO easily getting stuck,this paper proposed an improved ACO algorithm,namely MPAS.The basic idea is:dividing the pheromones into local pheromones and global pheromones,and then updating pheromones using different strategics and dynamic path selection probability during searching process,it can efficiently find global optimal solution in the last searching period.Many experiments based on the data of TSPLIB show the improved algorithm has better ability to find global optimal solution in large TSP.This paper proposed the concept of solution performance distribution,giving the performance analysis of MPAS for solving TSP through the running time distributions of MPAS and the solution performance distributions of MPAS, obtains some practical conclusions that may give guidance to solve the TSP:The probability of finding optimal solution is increasing as the running time becomes longer; the speed of improving solution is fast in the earlier phase but becomes slow evidently in the later phase; it can reduce the running time and increase the probability of obtaining optimal solution by way of restarting the algorithm.