A hard problem for genetic algorithms: finding cliques in Kellergraphs

摘要

The authors present evidence that finding the maximum clique inKeller graphs is an example of a family of problems which are bothnatural and inherently difficult for genetic algorithms. Specifically,they employ a hybrid genetic algorithm to find the largest clique inKeller graphs. They present theoretical reasons why this problem islikely to be particularly hard for this family of graphs. Their resultsconfirm this suspicion. They then discuss several characteristics ofthis graph family which confound genetic algorithms: its uniformity,edge density and small diameter