A study of ACO capabilities for solving the maximum clique problem |
| |
Authors: | Christine Solnon Serge Fenet |
| |
Institution: | (1) LIRIS CNRS UMR 5205, University Lyon I, Nautibus, 43 Bd du 11 novembre, 69622 Villeurbanne cedex, France |
| |
Abstract: | This paper investigates the capabilities of the Ant Colony Optimization (ACO) meta-heuristic for solving the maximum clique
problem, the goal of which is to find a largest set of pairwise adjacent vertices in a graph. We propose and compare two different
instantiations of a generic ACO algorithm for this problem. Basically, the generic ACO algorithm successively generates maximal
cliques through the repeated addition of vertices into partial cliques, and uses “pheromone trails” as a greedy heuristic
to choose, at each step, the next vertex to enter the clique. The two instantiations differ in the way pheromone trails are
laid and exploited, i.e., on edges or on vertices of the graph.
We illustrate the behavior of the two ACO instantiations on a representative benchmark instance and we study the impact of
pheromone on the solution process. We consider two measures—the re-sampling and the dispersion ratio—for providing an insight
into the performance at run time. We also study the benefit of integrating a local search procedure within the proposed ACO
algorithm, and we show that this improves the solution process. Finally, we compare ACO performance with that of three other
representative heuristic approaches, showing that the former obtains competitive results. |
| |
Keywords: | Ant colony optimization Maximum clique problem Metaheuristic |
本文献已被 SpringerLink 等数据库收录! |
|