Improved Ant Colony Algorithm To Solve Tsp Problem Research

Ant colony optimization algorithm (ant colony optimization, ACO), which was firstproposed by Italian scholars named Marco Dorigo, V Maniezzo, A. Colorni in 1992, is agroups intelligent optimization methods based on the development of the biological behaviorof marching along the shortest path in the process of ant community grazing. The proposedalgorithm is obtained encouraging effect in the combinatorial optimization with NP-hardcharacteristics problem which is difficult to work in traditional optimization method, and iswidely attended by the academia and industry. At present, the ant colony optimizationalgorithm has become an important branch of the intelligent calculating method, and becomethe prosperous development of the hot research topic nowadays. The study of the theory ofthe ant colony optimization algorithm relatively lags behind, especially for that there still needfurther study for the algorithm parameter selection and the convergence proof. Although, thisresearch method is in its infancy, but some research has shown the superiority of the antcolony system in solving complex optimization problem. At present, the ant colony systemhas been successfully applied to the solving of traveling salesman problem (TSP), quadraticassignment problem (QAP) and job-shop scheduling problem and has got good experimentalresults.TSP (Traveling Salesman Problem) is also known as the HuoLangDan Problem or thetouring Salesman Problem, in operations research, and it has widely range of applications inoperational research, management science and engineering practice. TSP is a famous problemof the combination optimization, and more and more researchers have paid attention to theTSP problem. Due to the nature of the problem of NP, TSP problem have not fully resolved.The main contents are composed of the following parts:1. The dissertation focuses on the basic theory of ant colony algorithm and the application inTSP and especially an in-deep and systemic study. The basic principle, characteristics,structure and the implementation method of the algorithm is introduced. 2. Since basic ant colony algorithm exist some prominent faults such as long search time, easyto fall into local optimal solution and so on, so that it makes the solving effect is not verygood. According to these defects, the dissertation puts forward the improved ant colonyalgorithm for solving TSP problem. The improvement is mainly for three aspects: the initialstate of the main parameters, the selection strategy of the transition probability and theimprovement of the update method of pheromone.①The first considered for an initial TSP is pretreatment. Before using the ant algorithm tosolve problems, firstly using the nearest neighbor method to construct an initial travel, andcalculate the initial value of pheromone.②Using theAnt-Q Systems algorithm which put forward by Dorigo M and using thecombination selection strategy of deterministic and stochastic choice, and do the dynamictransition probability adjustment in the search process.③Pheromone update process using the online single update step combine with the offlinepheromone update step which means the update method of combining the single-steppheromone-line during the process of ant parade and the global pheromone update method atthe end of this iteration .With MATLAB simulation，the dissertation combined the three steps mentioned above,then selected 10 TSP problems in the TSPLIB for experiment and compared the results usingthe improved ant colony algorithm with that using basic ant colony algorithm and geneticalgorithm which is more extensive applicated nowadays. After that, using improved antcolony algorithm, the dissertation made numerical simulation for Chinese TSP withrepresentation of 100 cities and compared the results with that using basic ant colonyalgorithm and neural network algorithm. The results show that although the running time goeslonger, the improved ant colony algorithm is much better than before in the global searchability of the optimum solution and the stability and convergence.Finally, the work of this dissertation is summarized and the prospective of futureresearch is discussed.