Title: How good are genetic algorithms at finding large cliques: an experimental study
Author: Bob Carter and Kihong Park, Boston University
Date: November 1993
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 {\em 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 {\em 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.