An Improved Ant Colony Optimization for the Maximum Clique Problem

The maximum clique problem is a classical combinatorial optimization problem which is one of the first problems shown to be NP-complete. Moreover, it does not admit a polynomial-time approximation algorithm unless P=NP. So many heuristic algorithms have been proposed for this problem. In this paper, we introduce an improved ant colony optimization (ACO) for the maximum clique problem. In the proposed algorithm, both a new pheromone updating method and a parameter tuning method are introduced. Simulations are performed on some graphs of the DIMACS clique instances in the second DIMACS challenge. The results show that the improved ant colony optimization can yield satisfactory results.