- 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, tree fitness landscapes, nand gates, Monte Carlo sampling, symbolic regression, Santa Fe trail, artificial ant",
- ISSN = "1063-6560",
-
URL = "
http://www.mitpressjournals.org/doi/pdf/10.1162/evco.1999.7.4.399",
-
URL = "
http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/WBL.fitnessspaces.pdf",
-
URL = "
http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/WBL.fitnessspaces.ps.gz",
-
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 http://www.cs.ucl.ac.uk/staff/W.Langdon/fitnessspaces
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 http://www.dagstuhl.de/files/Reports/00/00071.ps.gz (page 12), and also presented at GECCO'2000.
PMID: 10578029",
