Research And Application On Ant Colony Optimization

Ant Colony Optimization (ACO) is a metaheuristic approach for solving hard combinatorial optimization problems. It was first proposed by Dorigo in 1991. From then on, ACO has been successfully used to solve a series of combinatorial problems, such as: Traveling Salesman Problem, Quadratic Assignment Problem, Vehicle Routing Problem, Graph Coloring Problem and so on. For the great performance of ACO, researchers show great interest in the research and applications on ACO nowadays.This thesis firstly introduces the general development of ACO. Then, through using TSPLIB as the benchmark, some analyses and remarks are made to compare the performance of some typical ACO algorithms. Thereof, basic theory supporting ACO and its application are provided. Additionally, Two main disadvantages of ACO are also concluded, that is, stagnation and slow-convergence.In order to reduce the influence of those two disadvantages of ACO, this thesis firstly summarizes the already existed approaches to mitigate stagnation. Then, a multiple-ant-colonies-optimization algorithm based on equilibrium of distribution is proposed. Through dynamically adjusting the interaction among ant colonies, the stagnation of the new algorithm is effectively mitigated. The analysis and the experimental results show that the new algorithm can achieve better performance.Additionally, this thesis provides two applications based on ACO: one is focusing on the effective monitor-nodes selection in net traffic measurement, the other is about the routing and data aggregation problems in wireless sensor network. To the former problem, a weak vertex cover set model is introduced. That is, the nodes selection problem is transformed into the weak vertex cover set problem. Then an algorithm based on ACO for solving weak vertex cover set problem is proposed and the experimental results show that the algorithm can achieve good performance. To solve the latter one, a distributed data-centric routing algorithm based on ant algorithm for wireless sensor networks is presented. The basic idea of the algorithm is as follows: A set of cooperating agents called ants cooperate to find the optimal route to the Sink node, meanwhile data aggregation can be achieved through the positive feedback effect of ACO. The new algorithm is energy efficient and distributed and can reduce the energy consumption through data aggregation. The analysis and the experimental results show that the algorithm is efficient and scalable.