Genetic programming applies the evolutionary loop to programs. Instead of a fixed-length string of parameters, each candidate is a program, classically a tree whose internal nodes are functions such as addition or a conditional and whose leaves are inputs and constants. A program's fitness is measured by running it on a set of test cases and comparing its outputs with the desired ones. Variation works on the structure itself. Crossover swaps subtrees between two parents, and mutation replaces a subtree with a new random one. The size and shape of the solution are therefore not fixed in advance; they are part of what evolution searches over.
The idea has early roots in Friedberg's experiments of the late 1950s and in Cramer's tree-based representation of 1985. John Koza's 1992 book turned it into a general method and showed it producing working programs for problems ranging from curve fitting to control. One of its earliest applications, and still one of the most widely used, is symbolic regression, where it searches for a formula rather than fitting the coefficients of a chosen one. Its freedom of form also causes its best-known problem: programs tend to grow without improving, a phenomenon called bloat. This topic covers how program trees are built and varied, works through symbolic regression, examines bloat and the methods used to control it, and surveys the linear, graph, and grammar-based representations developed as alternatives to trees.
Articles
Representing and varying programs
- Program trees in genetic programming: function and terminal sets, closure and sufficiency, the preparatory steps of a run, typed genetic programming, and how evolving programs differs from evolving bit strings.
- Initialization and variation in genetic programming: the full, grow, and ramped half-and-half methods and the tree shapes they produce, subtree crossover and its biases, and the mutation operators used alongside it.
Applying it
- Symbolic regression: searching for a formula that fits data, worked through with repeated runs, and the questions of generalization and overfitting.
- Bloat in genetic programming: why programs grow without improving, the theories that explain it, and the depth limits and parsimony methods used to control it, measured on a regression task.
Other representations
- Genetic programming beyond trees: linear, Cartesian, grammatical, and stack-based genetic programming, each decoded on a small example, and the record of human-competitive results.
Related topics
Genetic programming uses the selection schemes and population machinery of genetic algorithms with a different representation. Neuroevolution faces a similar problem of evolving structure as well as parameters, for neural networks rather than programs, and recent work combines program evolution with language models that propose the variations.
References
- Koza, J. R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press.
- Poli, R., Langdon, W. B., and McPhee, N. F. (2008). A Field Guide to Genetic Programming. Lulu.com.