The Application Of Ant Colony Algorithm In Combinatorial Optimization

Many combinatorial optimization problems, which are fundamental and important in science and engineering calculation, are NP-complete problems. The solution of these problems has been the key problems in the study of algorithm theory. For NP-complete combination optimization problems, there is no efficient algorithm to the solution of the problems. Consequently, heuristic algorithms may be used to solve such type of problems. As a new heuristic algorithm, Ant Colony Optimization (ACO) algorithm whose main characteristics are positive feedback, distributed computation and constructive greedy heuristic can solve many NP-complete combination optimization problems successfully. This thesis introduces the principles of ACO in detail and describes our deep research work in the application of combination optimization problems. We apply ACO to Maximum Clique Problems and MaxCut problems, which are typical NP-complete combination optimization problems. The main contribution of this thesis is as follows:1,Based on the characteristics of maximum clique problems (MCP), a new version of ACO is proposed to solve MCP. The simulation results show that the proposed heuristic ant colony optimization is effective and efficient for MCP.2,Based on the detail discussion of ACO's characteristics, such as parameters setting, time complexity and so on, we design a local dynamic heuristic algorithm to improve the performance of the algorithm. Simulation results demonstrate that the improved algorithm can achieve better performance than before.3,Heuristic Ant colony optimization is extended for solving MaxCut Problems. The effectiveness of the algorithm is demonstrated by simulations.