- author = "Sean Luke",
- title = "Issues in Scaling Genetic Programming: Breeding Strategies, Tree Generation, and Code Bloat",
- year = "2000",
- school = "Department of Computer Science, University of Maryland",
- address = "College Park, MD 20742, USA",
- keywords = "genetic algorithms, genetic programming",
-
URL = "
http://www.cs.gmu.edu/~sean/papers/thesis2p.pdf",
-
URL = "
http://www.cs.gmu.edu/~sean/papers/thesis2p.ps.gz",
-
URL = "
https://www.cs.umd.edu/community/alumnus/sean-luke",
- size = "178 pages",
-
abstract = "Genetic Programming is an evolutionary computation
technique which searches for those computer programs
that best solve a given problem. As genetic programming
is applied to increasingly difficult problems, its
effectiveness is hampered by the tendency of candidate
program solutions to grow in size independent of any
corresponding increases in quality. This bloat in
solutions slows the search process, interferes with
genetic programming's searching, and ultimately
consumes all available memory. The challenge for
scaling up genetic programming is to find the best
solutions possible before bloat puts a stop to
evolution. This can be tackled either by finding better
solutions more rapidly, or by taking measures to delay
bloat as long as possible.
This thesis discusses issues both in speeding the search process and in delaying bloat in order to scale genetic programming to tackle harder problems. It describes evolutionary computation and genetic programming, and details the application of genetic programming to cooperative robot soccer and to language induction. The thesis then compares genetic programming breeding strategies, showing the conditions under which each strategy produces better individuals with less bloating. It then analyzes the tree growth properties of the standard tree generation algorithms used, and proposes new, fast algorithms which give the user better control over tree size. Lastly, it presents evidence which directly contradicts existing bloat theories, and gives a more general theory of code growth, showing that the issue is more complicated than it first appears.",
-
notes = "errata 1. In Algorithm 2 (p. 6), the line P<-P\\[q]
should read P<-P\\[s].
2. Figures 5.2 through 5.5 (p. 38-39) are not in proper evolutionary-time order. The proper order is 5.4, 5.5, 5.2, 5.3.
Supervisor: James Hendler",
