Improvement Of Ant Colony Optimization And Its Application In TSP

A population-based simulated evolutionary algorithm called ant colony optimization was proposed in 1992 by Italian researchers M.Dorigo, V.Maniezzo and A.Colorni,and it was introduced by means of the application to the TSP. Since then, it has been applied to many optimization problems, from single-objective problems to mufti-objective problems, from discrete problems to continuous problems. Such as system control,artificial intelligence, pattern recognition and so on.The dissertation focuses on the modification and applications of ACO, especially in deep study on how to improve the basic ACO algorithm, inhibiting standstill of the algorithm, and application to TSP. The main contributions of this dissertation are as follows:To overcome some disadvantages of ACO algorithm such as early variety and needing longer computing time, the paper advances two improved ant colony algorithm:1, Rate-paying ant colony algorithm (RACA). First, it uses the moving of pseudorandom proportional, guaranteeing a biggish range of research in early time of search; and guaranteeing convergence property of the algorithm. At the same time, by the way of paying personal income tax, at the time of updating global pheromone, the best tour pays some pheromone tax in addition for every some time. And raised ability of researching a better resolving of the algorithm.2, Evaluateing the route ant colony algorithm (ERACA). When all ants finished the search for one time, recording the route length which every ant found, and evaluating the current search according to an improved formula of Standard deviation, and then deciding to update global pheromone or not. At the same time, to adopt the function of compress interval. If there is no better solution by ants found during some time, compress the pheromone of all routes, to adjust the probability of ants select all cities.Experimental results show that those two improved algorithms have more excellent exhibition in avoiding early variety, searching better solution and stability by simulation experiment and comparing to ant algorithm and ant colony algorithm.Finally, the work of this dissertation is summarized and the prospective of future research is discussed.