An Improved Ant Colony Algorithm And Its Application In Optimal Routing Problem

Traveling Salesman Problem （TSP） is a classical combinatorial optimization question,the research on TSP has great theoretical and practical significance. However, with thedevelopment of science and technology as well as the enlargement of human living space, thescale of question is also gradually expanding, which leads to the result that general methodshave poor efficiency in solving TSP. So people put forward a great many of heuristicintelligent optimization algorithms utilized to get the approximate results of many complexoptimization problems, and ant colony algorithm belongs to them.Ant colony optimization algorithm （ACO） is a newly intelligent bionic evolutionalgorithm proposed by simulating the foraging behavior of ants group in nature. It adopts thedistributed parallel computer system, has stronger robustness, and easily combinates withother algorithms. However, with the defects of spending longer time in searching for optimalsolution of the problem and easily falling into the local best, this thesis presents an improved algorithm and makes further research into its application to TSP. The main contents arecomposed of the following parts:1. The article introduces the research significance, development process and biologicalprinciple of ACO and basic concept of the shortest path problem in detail, and themathematical model and implementation steps of ACO for solving TSP are also presented.2. Taking into account of three important parameters: the pheromone evaporationcoefficient ρ, the pheromone heuristic factorα and the expected heuristic factor β,the articlecarries out a mass of tests for better test results, and makes certain the best combination ofparameters configuration.3. Aiming at the limitation of the basic ant colony algorithm, this paper presents fourimproved algorithms, and for one of whose——ant colony system （ACS）, it proposes anewly improved algorithm:（1） The way of getting the initial pheromone: by calculating thedistances between every two cities and comparing to them, we can get the shortest distance,and let the shortest distance be l_min=min{d_ij}, from which we can get the value of initialpheromone is τ₀=1/n.l_min;（2） The pheromone updating rule: in this paper, in addition to theglobally shortest tour, the pheromone in globally longest tour is also updated;（3） Adopting the MAX-MIN pheromone system: in order to suppress effectively stagnation phenomenoncaused by great difference of pheromone between the shortest and the longest tour, at the endof finishing pheromone update, the amount of pheromone in every edge is limited in a range[τ_min,τ_max].The improved ant colony optimization algorithm is applied to solve TSP problems. WithMATLAB simulation, the dissertation selected10TSP problems from TSPLIB for experimentand first compared with the results of ACS, which proved the effectiveness of the improvedalgorithm, then with the ones of self-organizing neural network algorithm, further provingthat it has better global searching performance. For example, this paper made a comparisonbetween the improved algorithm and three algorithms （F-W, NCSOM, ASOM） introduced inliterature[35], the average relative error of four algorithms are: F-W（10.81464%）,NCSOM（3.2416%）, ASOM （1.74936%） and the improved ant colony algorithm （0.73188%）.Finally, the improved ant colony algorithm was used in solving the practical optimal pathproblems in China, for the chinese100-city-TSP example, the comparison results of fouralgorithms are: F-W （25958km）, NCSOM （25983km）, ASOM （25702km） and theimproved ant colony algorithm （20622.461635km）.Finally, the work of this dissertation is summarized and the prospective of future research is discussed, which points out the direction for future research.