Ant Colony Algorithm In The Application Of TSP

With a rapid development of economy and quantity of vehicle, the increasingly serious traffic problem has become a critical bottleneck to restrict city development. Intelligent Transportation System is one of the most important solutions to deal with the conflict of demand and supply in social traffic. In recent years, with the support of science and technology, ITS has been more and more regarded by people for it applies computer technology, communication technology, database technology and artificial intelligence technology to traffic area to solve traffic jam, ensure traffic safety and improve the efficiency of traffic network. As a hot research point of ITS, the optimum Paths selection, which is a combinatorial optimization problem, can be well solved by ACO.It has been proved by a great deal of research achievements, ACO is good at solving combinatorial optimization problems by its inner searching mechanism and positive feedback trait. However, ACO also has some defects. For example, during the movement of ants, route selection instructed by pheromone and inspiration also has randomicity. Specially, when the scale of problem is larger, route selection usually cost more searching time. In addition, because pheromone may be strengthened in an individual route, the algorithm will easily get into local optimal solution.Firstly, the thesis analyzed the advantages and disadvantages of basic ACO, studied the influence of parameters on algorithm performance, and determined rational value domain of these parameters. Then, the optimization strategy at pheromone was improved, so that it could restrain early stagnation during convergence process effectively. Finally, combining with the practical examples of TSP problem, the effectiveness of the improved algorithm was verified. The results showed that this algorithm has faster convergence and can find globally optimum solutions in a shorter time.