An Improved Ant Colony Optimization Algorithm Based on Pheromone Backtracking

Abstract

In this paper, backtracking algorithm is adopted to the pheromone updating rule to resolve the basic Ant Colony Optimization (ACO) algorithm's shortcoming of easily falling into local optima. When the pheromone accumulated to the backtracking point on the tour, pheromone will be backtracked in the improved algorithm. The improved algorithm not only solves the ACO algorithm in excessive accumulation of pheromone problems, but also has better global search ability and convergence speed, which increase the quality of the solution space by using the information of the previous iterations' ants. Finally, the improved algorithm is applied to the Traveling Salesman Problem(TSP), and the simulation results show that it is much better than basic ACO algorithm in many aspects, such as the optimal iterations, the average and the optimal solution etc.