Research And Application Of Ant Colony Optimization Algorithm To Solve The Shortest Path Problem

The shortest path problem has always been the research focus of the traffic engineering, computer science, and urban planning, Study Of the shortest path problem have great significance and practical value.In solving this problem, the traditional shortest path algorithms are Dijkstra algorithm, dynamic programming algorithm, and the heuristic search algorithms, are simulated annealing algorithm, genetic algorithm, ant colony algorithm.Ant colony algorithm was first proposed by M.Dorigo in1991.As bionic optimization algorithm, the global search, the positive feedback, robustness, and combined with other bionic optimization algorithm easily, distributed computing, reflects the superiority of solving complex optimization problems, promoting more and more study. From the beginning it is used to solve the traveling salesman problem to the graph coloring problem, vehicle scheduling problem, and then later used in dynamic combinatorial optimization problems such as communication network routing problems. Ant colony algorithm has been successively applied to various other areas, many scholars through the study of basic ant colony algorithm for its slow convergence and premature shortcomings, proposed many improved ant colony optimization algorithms, such as Ant Colony System, ant colony algorithm with elitist strategy, polymorphic ant colony algorithm, ant colony algorithm based on immunity, adaptive ant colony algorithm.The article first Discusses a basic ant colony algorithm, introduces several common ant colony optimization algorithms, and deeply analysis ant colony system, then Considering the ant colony algorithm in solving the shortest path between two points of transport network has the shortcomings such as slow convergence and be prone to stagnation phenomenon, the authors provides a improved ant algorithm. The Improvements include:1. it adds the heuristic direction information, reduces the inferior solution, improves the quality of solution;2. Designs a Dynamic factor, to adaptively adjust the renewal of pheromone on the optimal solution, which is more conducive to optimal path, improve the capability of global search, avoid that the algorithm appears premature.The results of experiment show that the improved algorithm enhances the convergence largely and effectively avoids getting into local optimal easily and it prove the validity of the improved algorithm. Finally, an improved ant colony optimization algorithm is applied to the GIS transportation network shortest path problem, to improve the speed of the search to the global optimum solution.