Genetic programming (GP) is a subfield of evolutionary computation pioneered by Nichael Lynn Cramer in 1985 and first explored in depth by John Koza in his 1992 book Genetic Programming: On the Programming of Computers by Means of Natural Selection. It is a method used to allow computer programs to evolve according to some user-defined goal. It uses evolutionary operators including crossover, selection, replication and mutations to evolve the programs, which are usually represented by trees or prefix-notation expressions (s-expressions). To work effectively, it requires an appropriate selection of operators, fitness function and primitives.
Genetic programming uses methods which are similar to genetic algorithms (GA), but is based on programs which perform tasks whose results can then be evaluated via a fitness function, as in a GA. Instead of using populations of parameter lists to be evaluated by some evaluation procedure, GP uses populations of programs which are to be run to perform the required task. A technical difference between GAs and GPs is that GAs use list structures, often of fixed size, to store their data, while GPs use tree structures which can vary in size and shape.
The application of a tree representation (and required genetic operators) for using genetic algorithms to generate programs was first described in 1985 by Cramer. Koza, though he did not first explore genetic programming, is indisputably the field's most prolific and persuasive author. Koza and other early GP researchers used the artificial inteligence language Lisp to program their GPs.
GPs is very computationally intensive and so in the 1990s it was mainly used to solve relatively simple problems. However, more recently, thanks to various improvements in GP technology and to the well known exponential growth in CPU power, GP has started delivering a number of outstanding results. At the time of writing over 40 human-competitive results have been gathered, in areas such as quantum computing, electronic design, game playing, sorting, searching and many more. These results include the replication or infringement of several post-year-2000 inventions, and the production of two patentable new inventions.
Developing a theory for GP has been very difficult and so in the 1990s genetic programming was considered a sort of pariah amongst the various techniques of search. However, after a series of breakthroughs in the early 2000s, the theory of GP has had a formidable and rapid development. So much so that it has been possible to build exact probabilistic models of GP (schema theories and Markov chain models) and to show that GP is more general than, and in fact includes, genetic algorithms.
Genetic Programming techniques have now been applied to Evolvable hardware as well as computer programs.
Bibliography
- Cramer, Nichael Lynn (1985), "A representation for the Adaptive Generation of Simple Sequential Programs" in Proceedings of an International Conference on Genetic Algorithms and the Applications, Grefenstette, John J. (ed.), CMU
- Koza, J.R. (1992), Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press
- Koza, J.R. (1994), Genetic Programming II: Automatic Discovery of Reusable Programs, MIT Press
- Koza, J.R., Bennett, F.H., Andre, D., and Keane, M.A. (1999), Genetic Programming III: Darwinian Invention and Problem Solving, Morgan Kaufmann