Research On Ant Algorithm To Traveling Salesman Problem

Traveling salesman problem(TSP) is a Combinatorial optimization problem, it has became and will be still became a standard problem to test the new problems of Combinatorial optimization. Theoretically speaking, the enumeration not only can solve TSP problem 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 merged because of demand. Among of them, ant colony algorithm is one of advanced algorithms. Ant colony algorithm(ACA) is a class of heuristic search algorithms that have been successfully applied to solving TSP problem. Ants enhance the pheromones on the better trails and choose the next trail by pheromones intensity. 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 ant colony.In this paper, firstly give the description of TSP and some summarize about TSP. Then clarify the ant algorithm: discuss its mathematic model, important techniques and give the step of its implement.After this, this paper analyzes the effects to the ant algorithm with distinct parameters, then give the experimental parameter values. At the same time, we also analyzed the problems of the ant algorithm, it's manifestation mode is: has the limitation of stagnation and poor convergence, easy to fall in local optima. With further analyzes we get the causes of these problems: a) When pheromone updating, the pheromone is not limited, so some of the route's pheromone is more higher than others, this stop the ability of search. b) Global pheromone updating strategy set to all routes, this cannot make good use of the result of last loop and cannot make the searching around the optima result rapidly. Slowdown the searching efficiency. Aiming at the above problems, this paper propose an improved ant algorithm in solving Traveling Salesman Problem, the improvements are as follows: a) Propose a new pheromone updating strategy, except updating the best and worst route, it also do the partial updating to all routes after every loop, and limit the pheromone to an given range. b) According to the principle of the biologic sensitivity to the environment, give the functions used to adaptα,β. After improvements, the ant algorithm can avoid the dog down of the search, improve the results. Enable the ants can get the more good route with higher probability, upgrade the ability of searching. At the same time, the ants in this model have more similar features as real ants, and proper response to the change of environment.Finally we point out main research work and innovation of the thesis; Analyze the shortcomings of research on TSP and look forward the research orientation in the future.