Research On Ant Colony Algorithm For Solving Traveling Salesman Problem

TSP (Traveling Salesman Problem) is a problem of combination optimization with simple definition but difficult to be solved, which attracts many researchers in various fields including mathematics, physics, biology and artificial intelligence (AI). It has become and will continue to become a standard problem to test a new algorithm of combination optimization. Theoretically speaking, the enumeration not only can solve TSP, but also can get the best answer. But to all computers nowadays, it's hardly to obtain its best answer in such huge researching space by using common enumeration. Therefore, all kinds of algorithms to solve TSP emerged because of demand. Among of them, ant colony algorithm (ACA) is one of advanced technologies.Ant colony algorithm is a class of heuristic search algorithms that have been successfully applied to solving NP hard problems. Ant algorithms are biologically inspired from the behavior of colonies of real ants, and in particular how they forage for food. We can find that when ants are looking for food from nest, some chemical trails (we call this trail as pheromone) are laid by all ants, the ants moving around form a network of these trails, and information is laying around, waiting to be used. Good information tends to be reused over and over again, leading to more reinforcement, leading to more use. This is a form of behavior called autocatalytic behavior, and it is the key to the success of the ant colony. ACA has many good features in optimization, but it has the limitations of stagnation and poor convergence, and is easy to fall in local optima, which are the bottlenecks of its wide application. A detailed theoretical research on the global convergence of ACA is performed. A series of improvement schemes are also proposed. Meanwhile, this paper studies and analyses the function and influence of parameter α, β, ρ in the model of ant algorithm theoretically, and then a typical example of TSP Eil51 is calculated.Then, this paper presents a new pheromone updating strategy which is used to optimize ACS (Ant Colony System) in solving the Traveling Salesman Problem. The improved ant colony optimization algorithm is using a new pheromone updating strategy. The pheromone trail of each edge is set with a lower limit at the beginning iterations of thealgorithm, and the worst ant judged by its tour length like the best ant used in ACO is allowed to perform global trail updating. And we demonstrate the efficiency of the algorithm by means of experimental study.Finally, the paper explained the implement of the improved algorithm. and we indicate the future research directions.