Genetic programming

From Wikipedia, the free encyclopedia

Genetic programming (GP) is a patented^[1] automated methodology inspired by biological evolution to find computer programs that best perform a user-defined task. It is therefore a particular machine learning technique that uses an evolutionary algorithm to optimize a population of computer programs according to a fitness landscape determined by a program's ability to perform a given computational task. The first experiments with GP were reported by Stephen F. Smith (1980)^[2] and Nichael L. Cramer (1985),^[3] as described in the famous book Genetic Programming: On the Programming of Computers by Means of Natural Selection by John Koza (1992).

Computer programs in GP can be written in a variety of programming languages. In the early (and traditional) implementations of GP, program instructions and data values were organized in tree-structures, thus favoring the use of languages that naturally embody such a structure (an important example pioneered by Koza is Lisp). Other forms of GP have been suggested and successfully implemented, such as the simpler linear representation which suits the more traditional imperative languages [see, for example, Banzhaf et al. (1998)]. The commercial GP software Discipulus,^[4] for example, uses linear genetic programming combined with machine code language to achieve better performance. Differently, the MicroGP^[5] uses an internal representation similar to linear genetic programming to generate programs that fully exploit the syntax of a given assembly language.

GP 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, nearly 40 human-competitive results have been gathered, in areas such as quantum computing, electronic design, game playing, sorting, searching and many more.^[6] These results include the replication or infringement of several post-year-2000 inventions^{[citation needed]}, 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.

Meta-Genetic Programming is the technique of evolving a genetic programming system using genetic programming itself. Critics have argued that it is theoretically impossible, but more research is needed.^{[citation needed]}

1 Chromosome representation
2 Genetic operators
- 2.1 Crossover
- 2.2 Mutation
3 Notes
4 See also
5 Bibliography
6 External links

[edit] Chromosome representation

Genetic Programming evolves computer programs, represented in memory using trees. Trees can be easily evaluated in a recursive manner. Every tree node has an operator function and every terminal node has on operand, making mathematical expressions easy to evolve and evaluate.

[edit] Genetic operators

[edit] Crossover

The main operators used in the evolution process are crossover and mutation. Crossover is applied on an individual by simply switching one of its nodes with another node from another individual in the population. Of course, replacing a node means replacing the whole branch. This adds greater effectiveness to the crossover operator. The expressions resulting from crossover are very much different from their initial parents.

The following code will suggest an easy to implement individual deformation using crossover:

individual.Children[randomChildIndex] = otherIndividual.Children[randomChildIndex];

[edit] Mutation

Mutation affects an individual in the population. It can replace a whole node in the selected individual, or it can replace just the node's information.

A simple piece of code:

individual.Information = randomInformation;

individual = generateNewIndividual;

[edit] Notes

[edit] See also

[edit] Bibliography

Banzhaf, W., Nordin, P., Keller, R.E., Francone, F.D. (1998), Genetic Programming: An Introduction: On the Automatic Evolution of Computer Programs and Its Applications, Morgan Kaufmann
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.), Carnegie Mellon University
Koza, J.R. (1990), Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems, Stanford University Computer Science Department technical report STAN-CS-90-1314. A thorough report, possibly used as a draft to his 1992 book.
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
Koza, J.R., Keane, M.A., Streeter, M.J., Mydlowec, W., Yu, J., Lanza, G. (2003), Genetic Programming IV: Routine Human-Competitive Machine Intelligence, Kluwer Academic Publishers
Langdon, W. B., Poli, R. (2002), Foundations of Genetic Programming, Springer-Verlag
Smith, S.F. (1980), A Learning System Based on Genetic Adaptive Algorithms, PhD dissertation (University of Pittsburgh)