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

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

@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