Genetic programming: Difference between revisions

Revision as of 09:22, 28 November 2004

Revision as of 20:16, 28 November 2004

Line 1:

'''Genetic programming''' ('''GP''') is an automated methodology inspired by [[biological evolution]] to find [[computer programs]] that best perform a user-defined task. It is a particular instance of [[evolutionary algorithms]], in which the population is composed of computer programs and the [[fitness landscape]] is determined by the ability of a program to perform a given computational task. It was 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''.

Computer programs in GP can be written in a variety of [[programming_language|programming languages]]. In the early (and traditional) implementations of GP, program instructions and data values were organized in [[tree_structure|tree-structures]], thus favoring the use of [[declarative_programming|declarative languages]] that alreadynaturally embody such a tree-like structure (suchan asimportant theexample language usedpioneered by Koza, is [[Lisp_programming_language|Lisp]]). Nonetheless, other forms of GP have been suggested and succesfully implemented, such as the simpler [[linear_genetic_programming|linear representation]] (which suits the more traditional [[imperative languages]]) [see, for example, Banzhaf ''et al.'' (1997)]. The popular commercial GP software [http://www.aimlearning.com Discipulus], for example, uses [[linear genetic programming]] combined with [[machine code]] language to achieve better performance.

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 [[Moore's_law|exponential growth]] in CPU power, GP has started delivering a number of outstanding results. At the time of writing, overnearly 40 [http://www.genetic-programming.com/humancompetitive.html 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.

Line 13:

*Banzhaf, W., Nording, P., Keller, R.E., Francone, F.D. (1997), ''Genetic Programming: An Introduction: On the Automatic Evolution of Computer Programs and Its Applications'', Morgan Kaufmann

*Cramer, Nichael Lynn (1985), "[http://www.sover.net/~nichael/nlc-publications/icga85/index.html 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. (1990), "Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems", Stanford University Computer Science Department technical report [http://www.genetic-programming.com/jkpdf/tr1314.pdf 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

*Langdon, W. B., Poli, R. (2001), ''Foundations of Genetic Programming'', Springer-Verlag

== External links ==