Scaling of Program Tree Fitness Spaces

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

  author =       "W. B. Langdon",
  title =        "Scaling of Program Tree Fitness Spaces",
  journal =      "Evolutionary Computation",
  year =         "1999",
  volume =       "7",
  number =       "4",
  pages =        "399--428",
  month =        "Winter",
  keywords =     "genetic algorithms, genetic programming, stochastic
                 search, genetic algorithms, tree fitness landscapes,
                 nand gates, Monte Carlo sampling, symbolic regression,
                 Santa Fe trail, artificial ant",
  ISSN =         "1063-6560",
  URL =          "",
  URL =          "",
  URL =          "",
  DOI =          "doi:10.1162/evco.1999.7.4.399",
  size =         "30 pages",
  abstract =     "We investigate the distribution of fitness of programs
                 concentrating upon those represented as parse trees,
                 particularly how such distributions scale with respect
                 to changes in size of the programs. By using a
                 combination of enumeration and Monte Carlo sampling on
                 a large number of problems from three very different
                 areas we are lead to suggest, in general, once some
                 minimum size threshold has been exceeded, the
                 distribution of performance is approximately
                 independent of program length. We proof this for linear
                 programs and for simple side effect free parse trees.
                 We give the density of solutions to the parity problems
                 in program trees composed of XOR building blocks.

                 We have so far only conducted limited experiments with
                 programs including side effects and iteration. These
                 suggest a similar result may also hold for this wider
                 class of programs.",
  notes =        "Evolutionary Computation (Journal)

                 Special issue on scaling See also
                 \cite{langdon:1999:bool}, \cite{langdon:1998:BBparity}
                 Slides at

                 Parity only with building blocks, ie XOR or EQ, is a
                 needle in a haystack. Hence high order parity is
                 impossible using only XOR.

                 Presented at Schloss Dagstuhl
                 (page 12), and also presented at GECCO'2000.

                 PMID: 10578029",

Genetic Programming entries for William B Langdon