Genetic programming: Difference between revisions

Revision as of 02:21, 28 November 2004

Revision as of 03:53, 28 November 2004

Line 1:

'''Genetic programming''' ('''GP''') is a subfield 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''. ItRoughly speaking, it is a method inspired by [[biological evolution]] used to allowfind computer [[programming|programs]] tothat evolvebest accordingperform to somea user-defined goaltask, without the user ever having to write the program itself. In mathematical terms, GP is a [[stochastic]], population-based [[combinatorial optimization]] algorithm where the individuals in the population are computer programs. It uses [[evolution]]ary operators including [[crossover (genetic algorithm)|crossover]], selection, replication and [[mutation]]s to evolve the programs, which are usually represented by [[trees]] or prefix-notation expressions ([[s-expression]]s). To work effectively, it requires an appropriate selection of operators, fitness function and primitives.

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. AAlthough technicalmost differenceimplementations betweenof GAsGP anduse GPsthe isaforementioned that[[trees]], GAsother userepresentations listare structurespossible, oftenthe simplest of fixedwhich size,gives rise to storethe theirso-called data,[[linear whilegenetic GPsprogramming]] useparadigm tree[see, structuresfor which can varyexample, inBanzhaf size''et andal.'' shape(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.