Research On The Ant Colony Optimization Algorithm And Its Applications

Ant colony optimization algorithm is a novel evolutionary algorithm.It provides a new way to solve complicated combinatorial optimization problems as genetic algorithms,simulated annealing,tabu search,and so on.The primary study shows ant colony optimization algorithm is a better robust algorithm based on population , having been enlightened by the behavior of ant colony's searching for food,positive feedback construction and distributed computing combined with certain heuristics are adopted in the algorithm,which makes it easier to find better solution.However,there still exist some shortcomings such as shortage of pheromone during early phase,long running time and early convergence, which affect the algorithm's quality of solving the practical problems . Meanwhile, more research of its applications in fields beyond optimization problems solving is still needed.This dissertation is used study representative NP problem-traveling salesman problem starting,the background,content,realization method,algorithm self and performance of ant colony optimization are introduced detailedly.And then some improved ant colony optimizations are advanced and simulated.Finally different applications based on ant colony optimization and the improved,such as Berlin52-TSP,Eil51-TSP and quality of service route problem,are discussed.The main content of this dissertation are presented as follows:(1) Because of problematic uncertainty , the ant colony optimization algorithm is greatly influenced by the parameters setting , therefore , the reasonableness of parameters was researched,and three methods of parameters selected were suggested.(2) To overcome the shortcomings of ant colony optimization algorithm such as its slow computing speed,and it is easy to fall in local peak,an improved ant colony optimization algorithm was advanced.The advantages of MAX-MIN ant system algorithm were extracted in this algorithm,and the new parameters such as A,B,C and D was was introduced,the local and global pheromone updating strategy of this algorithm was adjusted comprehensively.(3) The path selecting strategy was improved through add parameters E and F.A state transition rule was used to guide the optimization process of algorithm in this method in order to take full advantage of prior knowledge,the probability of algorithm falling into local optimization result was reduced gradually,so an acceptable result would soon be found.(4) The validity of improved algorithm was verified by applying ant colony optimization algorithm and its improved algorithm to TSP problem.(5) A method of solving QoS multicast route problem based on ant colony optimization algorithm was suggested and analyzed its expansibility in a transient of network.