A hard problem for genetic algorithms: finding cliques in Keller graphs
J. Marconi, James A. Foster · 2002
The authors present evidence that finding the maximum clique in Keller graphs is an example of a family of problems which are both natural and inherently difficult for genetic algorithms. Specifically, they employ a hybrid genetic algorithm to find the largest clique in Keller graphs. They present theoretical reasons why this problem is likely to be particularly hard for this family of graphs. Their results confirm this suspicion. They then discuss several characteristics of this graph family which confound genetic algorithms: its uniformity, edge density and small diameter.