Genetic programming: Difference between revisions

Revision as of 20:23, 28 November 2004

Revision as of 23:22, 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 therefore a particular instance[[machine oflearning]] technique that uses an [[evolutionary algorithmsalgorithm]], into whichoptimize thea population is composed of computer programs andaccording theto a [[fitness landscape]] is determined by the ability of a program's ability to perform a given computational task. ItThe wasfirst pioneeredexperiments with GP were reported by [[Nichaelhttp://www-2.cs.cmu.edu/~sfs/ LynnStephen Cramer]F. Smith] in 1985(1980) and first[http://www.sover.net/~nichael/ exploredNichael inL. depthCramer] by(1985), [[Johnas Koza]]described in histhe 1992famous 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_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 naturally embody such a structure (an important example pioneered 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, nearly 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.

Line 18:

*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

*Smith, S.F. (1980), ''A Learning System Based on Genetic Adaptive Algorithms'', PhD dissertation (University of Pittsburgh)

== External links ==