language: en

How good are genetic algorithms at finding large cliques: an experimental study

Bob Carter
carter@cs.bu.edu
Kihong Park
park@cs.bu.edu BU-CS-93-015 October 10, 1993
Boston University Computer Science Department
Boston, MA 02215

[Phone: 617 353-8919 Fax: 617 353-6457]

Abstract This paper investigates the power of genetic algorithms at solving the MAX-CLIQUE problem. We measure the performance of a standard genetic algorithm on an elementary set of problem instances consisting of embedded cliques in random graphs. We indicate the need for improvement, and introduce a new genetic algorithm, the multi-phase annealed GA, which exhibits superior performance on the same problem set. As we scale up the problem size and test on "hard" benchmark instances, we notice a degraded performance in the algorithm caused by premature convergence to local minima. To alleviate this problem, a sequence of modifications are implemented ranging from changes in input representation to systematic local search. The most recent version, called union GA, incorporates the features of union cross-over, greedy replacement, and diversity enhancement. It shows a marked speed-up in the number of iterations required to find a given solution, as well as some improvement in the clique size found. We discuss issues related to the SIMD implementation of the genetic algorithms on a Thinking Machines CM-5, which was necessitated by the intrinsically high time complexity (O(n 3 )) of the serial algorithm for computing one iteration. Our preliminary conclusions are: (1) a genetic algorithm needs to be heavily customized to work "well" for the clique problem; (2) a GA is computationally very expensive, and its use is only recommended if it is known to find larger cliques than other algorithms; (3) although our customization effort is bringing forth continued improvements, there is no clear evidence, at this time, that a GA will have better success in circumventing local minima.

[Part of this research was presented at the]

[2nd DIMACS Implementation Challenge on Combinatorial Optimiza tion, DIMACS, October, 1993.]

[Supported in part by NSF grant CCR-9204284]

1 Introduction