A Hard Problem for Genetic Algorithms: Finding Cliques in Keller Graphs

Created by W.Langdon from gp-bibliography.bib Revision:1.7615

@InProceedings{marconi:1998:hpGAfckg,

• author = "Jamie Marconi and James A. Foster",
• title = "A Hard Problem for Genetic Algorithms: Finding Cliques in Keller Graphs",
• booktitle = "Proceedings of the 1998 IEEE World Congress on Computational Intelligence",
• year = "1998",
• pages = "650--655",
• address = "Anchorage, Alaska, USA",
• month = "5-9 " # may,
• publisher = "IEEE Press",
• keywords = "genetic algorithms, genetic programming, Keller conjecture, Keller graphs, maximum clique, hardness, complexity, edge density, hard problem, hybrid genetic algorithm, maximum clique finding, small diameter, uniformity, computational complexity, graph theory",
• ISBN = "0-7803-4869-9",
• file = "c112.pdf",
• DOI = "doi:10.1109/ICEC.1998.700116",
• size = "6 pages",
• abstract = "We 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, we employ a hybrid genetic algorithm to find the largest clique in Keller graphs. We present theoretical reasons why this problem is likely to be particularly hard for this family of graphs. Our results confirm this suspicion. We then discuss several characteristics of this graph family which confound genetic algorithms: its uniformity, edge density and small diameter.",
• notes = "ICEC-98 Held In Conjunction With WCCI-98 --- 1998 IEEE World Congress on Computational Intelligence",

}

Genetic Programming entries for Jamie Marconi James A Foster

Citations