Searching for maximum cliques with ant colony optimization. (English) Zbl 1033.68623
Cagnoni, Stefano (ed.) et al., Applications of evolutionary computing. EvoWorkshops 2003: EvoBIO, EvoCOP, EvoIASP, EvoMUSART, EvoROB, and EvoSTIM, Essex, UK, April 14–16, 2003. Proceedings. Berlin: Springer (ISBN 3-540-00976-0/pbk). Lect. Notes Comput. Sci. 2611, 236-245 (2003).
Summary: 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.
For the entire collection see [Zbl 1017.68610].
For the entire collection see [Zbl 1017.68610].
MSC:
68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
68R10 | Graph theory (including graph drawing) in computer science |