Research On ACO For Solving The Maximum Clique Problem

Ant Colony Optimization (ACO) algorithm is a meta-heuristic algorithm, whose idea comes from nature phenomena. After more than ten years development, it has become one of the most effective tools to solve optimization problems.The maximum clique problem (MCP) is a classical NP-hard combinatorial optimization problem. It not only plays an important role in theory studies, but also has practical use. It is a good tool to test the ability of many algorithms. Many practical problems can be transformed to MCP.This paper further studied MCP solving with ACO based on vanguards'research. Limitations and neglects in previous algorithms were pointed out, and a new means to balance the intensification and diversification was introduced.Basic concepts of MCP and meta-heuristic was firstly presented in this paper, and also some vanguards'algorithms, including the Vertex-AC algorithm, Edge-AC algorithm and the Vertex-AC with local pheromone update rule. Analysis on the balance between intensification and diversification of these algorithms was done, and thus their limitations emerged. After that, a tactic to improve local pheromone update rule is introduced. Benchmarks graph test, offered by DIMACS (Discrete for Mathematics and Theoretical Computer Science), shows that the improved algorithm performs better.The performance improvement of ACO is also studied. First, this paper presented the RLS algorithm, which is the most efficient algorithm to solve MCP. And the means that brought in its efficiency was pointed out. In the light of such means, this paper introduced a new algorithm. To suit different problems, the new algorithm adjusts the parameters based on balance estimation. We analyzed algorithm balance estimation and the effects of the parameters to the algorithm balance. Finally, some experiments testified the analysis.