Title :
An Improved Ant Colony Optimization for the Maximum Clique Problem
Author :
Xu, Xinshun ; Ma, Jun ; Lei, JingSheng
Author_Institution :
Shandong Univ., Jinan
Abstract :
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.
Keywords :
graph theory; optimisation; polynomial approximation; NP-complete; ant colony optimization; combinatorial optimization problem; maximum clique problem; parameter tuning method; pheromone updating method; polynomial-time approximation algorithm; Ant colony optimization; Approximation algorithms; Computational modeling; Computer science; Educational institutions; Heuristic algorithms; Information science; Polynomials; Processor scheduling; Very large scale integration;
Conference_Titel :
Natural Computation, 2007. ICNC 2007. Third International Conference on
Conference_Location :
Haikou
Print_ISBN :
978-0-7695-2875-5
DOI :
10.1109/ICNC.2007.205
