Performance Analysis Of Ant Colony Optimization And Its Application

Nature has provided a source of inspiration for us to solve various problems. Researchshows that applying the answer from biological world to practical problem has been proved tobe a successful method, which has formed a special branch of science - bionics. Groupactivities of Social animals often produce amazing self-organizing behavior. For example,while individual behavior seems simple, the blind ant colonies can find the shortest path fromthe nest to a source food. After careful study biologists found that the ant can lay down apheromone material for indirect communication on the path it has traveled. Other ants cansense material which makes them to follow the trail. Through this mutual cooperation the antscan find the shortest path between source food and the nest. Inspired by this phenomenon theItalian scholar M. Dorigo, V. Maniezzo and A. Colorni presented a new algorithm based onsimulation of population evolutionary by simulating the ant colony behavior, called AntColony Algorithm. The appearance of the algorithm aroused great concern from scholars. Inthe past few ten years, the ant colony optimization algorithm as a new class of intelligentbionic evolutionary algorithm has obtained a wide range of applications in many areas, suchas quadratic programming problem, function optimization, network routing, robot pathplanning, data mining, workflow planning, graphics rendering, and achieved good results.This paper focuses on the research of the principle, performance, and applications of antcolony algorithm. Firstly, this paper systematically introduces the ant colony algorithm andgives the description of basic ant system, then discusses several improved ant colonyalgorithms. In Chapter III we compare 1-Ant colony algorithm with 1+1 evolutionaryalgorithm in solving Pseudo-Boolean Optimization problem. With performance analysis ofthe ant colony algorithm, we found the reason why single ant colony algorithm mimics thebehavior of 1+1 evolutionary algorithm and deviated from the optimal solution in solving theBoolean function problem. In the fourth chapter, we propose an improved strategy, memoryarray, to overcome the low convergence of Max-Min Ant Colony System in solving thePseudo-Boolean Optimization problem. Experimental results show the effectiveness of thealgorithm. In the Chapter V, an improved ant colony system is introduced to solve thedynamic traveling salesman problem of urban traffic. Experiments show that the improved algorithm can find a better path in limited iterations when traffic jam appears on the currentpath of the city.