Quadratic Bloat in Genetic Programming

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

  author =       "W. B. Langdon",
  title =        "Quadratic Bloat in Genetic Programming",
  pages =        "451--458",
  year =         "2000",
  publisher =    "Morgan Kaufmann",
  booktitle =    "Proceedings of the Genetic and Evolutionary
                 Computation Conference (GECCO-2000)",
  editor =       "Darrell Whitley and David Goldberg and 
                 Erick Cantu-Paz and Lee Spector and Ian Parmee and Hans-Georg Beyer",
  address =      "Las Vegas, Nevada, USA",
  publisher_address = "San Francisco, CA 94104, USA",
  month =        "10-12 " # jul,
  keywords =     "genetic algorithms, genetic programming, bloat,
                 introns, ineffective code, evolution of shape,
                 subquadratic length growth, linear depth growth, binary
                 tree search spaces",
  ISBN =         "1-55860-708-0",
  URL =          "http://www.cs.bham.ac.uk/~wbl/biblio/gecco2000/GA069.pdf",
  URL =          "http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/WBL.gecco2000.quad.ps.gz",
  URL =          "http://www.cs.bham.ac.uk/~wbl/biblio/gecco2000/GA069.ps",
  URL =          "http://citeseer.ist.psu.edu/316810.html",
  size =         "8 pages",
  abstract =     "In earlier work we predicted program size would grow
                 in the limit at a quadratic rate and up to fifty
                 generations we measured bloat
                 O(generations**(1.2-1.5)). On two simple benchmarks we
                 test the prediction of bloat O(generations**2.0) up to
                 generation 600. In continuous problems the limit of
                 quadratic growth is reached but convergence in the
                 discrete case limits growth in size. Measurements
                 indicate subtree crossover ceases to be disruptive with
                 large programs (1,000,000) and the population
                 effectively converges (even though variety is near
                 unity). Depending upon implementation, we predict run
                 time O(number of generations**(2.0-3.0)) and memory
                 O(number of generations**(1.0-2.0)).",
  notes =        "A joint meeting of the ninth International Conference
                 on Genetic Algorithms (ICGA-2000) and the fifth Annual
                 Genetic Programming Conference (GP-2000) Part of

Genetic Programming entries for William B Langdon