|Norvig I 155
Genetic Programming/Russell/Norvig: The field of genetic programming is closely related to genetic algorithms. The principal difference is that the representations that are mutated and combined are programs rather
Norvig I 156
than bit strings. The programs are represented in the form of expression trees; the expressions can be in a standard language such as Lisp or can be specially designed to represent circuits, robot controllers, and so on. Crossover involves splicing together subtrees rather than substrings.
This form of mutation guarantees that the offspring are well-formed expressions, which would not be the case if programs were manipulated as strings. Interest in genetic programming was spurred by John Koza’s work (Koza, 1992(1), 1994(2)), but it goes back at least to early experiments with machine code by Friedberg (1958)(3) and with finite-state automata by Fogel et al. (1966)(4).
VsGenetic Programming: As with genetic algorithms, there is debate about the effectiveness of the technique. Koza et al. (1999)(5) describe experiments in the use of genetic programming to design circuit devices. Good overview texts on genetic algorithms are given by Mitchell (1996)(6), Fogel (2000)(7), and Langdon and Poli (2002)(8), and by the free online book by Poli et al. (2008)(9).
1. Koza, J. R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press
2. Koza, J. R. (1994). Genetic Programming II: Automatic discovery of reusable programs. MIT Press.
3. Friedberg, R. M. (1958). A learning machine: Part I. IBM Journal of Research and Development, 2, 2–13.
4. Fogel, L. J., Owens, A. J., and Walsh, M. J. (1966). Artificial Intelligence through Simulated Evolution.
5. Koza, J. R., Bennett, F. H., Andre, D., and Keane, M. A. (1999). Genetic Programming III: Darwinian invention and problem solving. Morgan Kaufmann
6. Mitchell, M. (1996). An Introduction to Genetic Algorithms. MIT Press.
7. Fogel, D. B. (2000). Evolutionary Computation: Toward a New Philosophy of Machine Intelligence.
8. Langdon, W. and Poli, R. (2002). Foundations of Genetic Programming. Springer
9. Poli, R., Langdon, W., and McPhee, N. (2008). A Field Guide to Genetic Programming. Lulu.com._____________Explanation of symbols: Roman numerals indicate the source, arabic numerals indicate the page number. The corresponding books are indicated on the right hand side. ((s)…): Comment by the sender of the contribution. The note [Author1]Vs[Author2] or [Author]Vs[term] is an addition from the Dictionary of Arguments. If a German edition is specified, the page numbers refer to this edition.
Stuart J. Russell
Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010