Computational Complexity Analysis of Simple Genetic Programming On Two Problems Modeling Isolated Program Semantics

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

@InProceedings{Durrett:2011:foga,
  author =       "Greg Durrett and Frank Neumann and Una-May O'Reilly",
  title =        "Computational Complexity Analysis of Simple Genetic
                 Programming On Two Problems Modeling Isolated Program
                 Semantics",
  booktitle =    "Foundations of Genetic Algorithms",
  year =         "2011",
  editor =       "Hans-Georg Beyer and W. B. Langdon",
  pages =        "69--80",
  address =      "Schwarzenberg, Austria",
  month =        "5-9 " # jan,
  organisation = "SigEvo",
  publisher =    "ACM",
  keywords =     "genetic algorithms, genetic programming, Genetic
                 Programming Theory, Computational Complexity, Hill
                 Climbing",
  isbn13 =       "978-1-4503-0633-1",
  doi =          "doi:10.1145/1967654.1967661",
  size =         "12 pages",
  abstract =     "Analysing the computational complexity of evolutionary
                 algorithms (EAs) for binary search spaces has
                 significantly informed our understanding of EAs in
                 general. With this paper, we start the computational
                 complexity analysis of genetic programming (GP). We set
                 up several simplified GP algorithms and analyse them on
                 two separable model problems, ORDER and MAJORITY, each
                 of which captures a relevant facet of typical GP
                 problems. Both analyses give first rigorous insights
                 into aspects of GP design, highlighting in particular
                 the impact of accepting or rejecting neutral moves and
                 the importance of a local mutation operator.",
  notes =        "See \cite{Durrett:2010:ccaGP2pmips} ACM order number
                 910114",
}

Genetic Programming entries for Greg Durrett Frank Neumann Una-May O'Reilly