Genetic programming: Difference between revisions

Revision as of 03:53, 28 November 2004

Revision as of 08:46, 28 November 2004

Line 1:

'''Genetic programming''' ('''GP''') is aan subfieldautomated 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''. Roughly speaking, it is a methodmethodology inspired by [[biological evolution]] used to find [[computer [[programming|programs]] that best perform a user-defined task, without the user ever having to write the program itself. In mathematical terms, GPIt is a [[stochastic]],particular population-basedinstance of [[combinatorialevolutionary optimizationalgorithms]], algorithmin wherewhich the individualspopulation inis thecomposed population areof computer programs. Itand usesthe [[evolutionfitness landscape]]ary operatorsis includingdetermined [[crossoverby (geneticthe algorithm)|crossover]],ability selection,of replicationa and [[mutation]]sprogram to evolveperform thea programs,given whichcomputational aretask. usuallyIt representedwas pioneered by [[treesNichael Lynn Cramer]] orin prefix-notation1985 expressionsand first explored in depth by ([[s-expressionJohn Koza]]s). Toin workhis effectively,1992 itbook requires''Genetic anProgramming: appropriateOn selectionthe Programming of operators,Computers fitnessby functionMeans andof primitivesNatural Selection''.

In the early implementations of GP, the use of [[declarative_programming|declarative languages]] such as [[Lisp_programming_language|Lisp]] led naturally to a [[tree_structure|tree-structure]] representation of computer programs, and this is still the predominant form of GP. Nonetheless, other forms of GP such as the simpler [[linear_genetic_programming|linear representation]] which suits the more traditional [[imperative languages]] have been suggested and succesfully implemented [see, for example, Banzhaf ''et al.'' (1997)]. [[linear_genetic_programming|Linear genetic programming]] is in fact the basis of the only commercial GP software available, [http://www.aimlearning.com Discipulus].

Genetic programming uses methods which are similar to [[genetic algorithm]]s (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. Although most implementations of GP use the aforementioned [[trees]], other representations are possible, the simplest of which gives rise to the so-called [[linear genetic programming]] paradigm [see, for example, Banzhaf ''et al.'' (1997)].

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_programming_language|Lisp]] to program their GPs.

Line 9:

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 [[Evolvableevolvable hardware]] as well as computer programs.

== Bibliography ==