Abstract:
In this paper, we investigate the capabilities of Ant Colony
Optimization (ACO) for solving the maximum clique
problem. We describe Ant-Clique, an algorithm that
successively generates maximal cliques through the repeated addition
of vertices into partial cliques. ACO is used
to choose, at each step, the vertex to add. We illustrate the behaviour of this
algorithm on two representative benchmark instances and we study the impact of pheromone on the solution process. We also experimentally compare
Ant-Clique with GLS, a Genetic Local Search approach, and we show that
Ant-Clique finds larger cliques, on average, on a majority of
DIMACS benchmark instances, even though it does not
reach the best known results on some instances.
Full paper (postscript)