An Improved Ant Colony Optimization and Its Application on TSP Problem

摘要

Ant colony optimization (ACO) is a kind of simulated evolutionary algorithm. It imitates ants' foraging process to find the shortest path, coexists with the characteristics of randomness and heuristic. It is applied successfully to solve combinatorial optimization problems, such as the TSP problem, the job-shop scheduling problem, etc. In practical application, ACO has the limitation of easily being trapped into local optimum and long time to converge. We propose an improved ant colony optimization algorithm, consisting of introducing random factor and introducing elitist ants as well as weakened strategy. Random factor provides a direction to search within the field of the optimal path. Elitist ants and weakened strategy strengthens the pheromone above the shortest path and weakens the pheromone above the suboptimal path to decrease the accumulated impact. Both of them shorten the convergence time. Simulation results show that the improved algorithm has a better performance than the traditional one. It can not only find a shorter path but also cost less convergence time, along with satisfactory time complexity. The best path length of TSPlib pr136 we get is 96910, closed to official record 96772 and relative error is 0:14%.