Research On The Improvement Ofant Colonyalgorithm And Itsapplication In TSP

As a kind of bionic optimization algorithm, ant colony algorithm has the advantages of strong robustness, parallel computing, easily combination and so on, it also showed strong competitive advantage in solving complex combinatorial optimization problems. So far, the ant colony algorithm has been widely applied to many fields, the good effect it achieved caught more and more attention and researches of scholars. Although the advantages are significant, ant colony algorithm can't avoid some disadvantages, which limits its further promotion and application.Based on the existing theoretical researches of ant colony algorithm and aiming at the defects of weak convergence speed and precision, this paper has improved and verified ant colony algorithm with living examples. the main work are as follows:(1) This paper has summarized the principles, mathematical models, characteristics and implementations of ant colony algorithm, and also analyzed its parameters, which laid a theoretical foundation for the follow-up study.(2) The introduction of mathematical model, classification and algorithm of TSP has laid a theoretical foundation for the application of ant colony algorithm in TSP.(3) This paper has respectively improved the defects of algorithm from three aspects—routing strategy, pheromone update strategy and algorithm convergence judging. Firstly, this paper has introduced roulette algorithm to improve the global search ability of algorithm and applied 2-opt method into the local search, which further optimized the quality of solutions. Secondly, in order to avoid the falling into local optimum of ant colony algorithm, this paper has used the pheromone update strategy which based on distribution of wolves to speed up the convergence speed of algorithm.Finally, as the traditional ant colony algorithm used repeated iteration to find the optimal solution, the use of information entropy as criterion of convergence of algorithm has reduced the times of iterations and accordingly improved the performance of algorithm.(4) According to the simulation experiments of multi-peak function and TSPinstances, this paper has proved that the improved ant colony algorithm is better than the traditional one in both convergence rate and convergence precision.