Genetic programming: Difference between revisions

Revision as of 15:28, 11 November 2004

Revision as of 09:25, 19 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''. It is a method used to allow computer [[programming|programs]] to evolve according to some user-defined goal. It uses [[evolution]]ary patternsoperators 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 variablesprimitives.

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 to deliver a fitness function similar to GAs. 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. A technical difference between GAs and GPs is that GAs use list structures, often of fixed size, to store their data, while GPs use tree structures which can vary in size and shape for each program used in the program pools.

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 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.

GPs 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 over 40 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.

So far GPs have successfully solved many of AI's toy problems, but the method is very computationally intensive, and may not compare favourably where simpler methods, such as [[genetic algorithm]]s or [[random optimisation]] can be used instead. It is possible that some more complex problems may be more amenable to solution using GPs than other optimization methods.

Unfortunately,Developing due to the lack of solida theory regardingfor theGP performancehas ofbeen geneticvery programmingdifficult vs.and traditionalso searchin methodsthe (such as [[hill climbing]]),1990s genetic programming remainswas considered a sort of pariah amongst the various techniques of search. WhileHowever, geneticafter programminga hasseries achievedof resultsbreakthroughs thatin arethe asearly good2000s, asthe andtheory sometimesof betterGP thanhas human-generatedhad resultsa formidable and rapid development. So, moremuch workso needsthat it has been possible to bebuild doneexact onprobabilistic themodels theoryof inGP order(schema theories and Markov chain models) and to bringshow thethat techniqueGP intois more widespreadgeneral than, and in fact includes, genetic usealgorithms.

Genetic Programming techniques have now been applied to [[Evolvable hardware]] as well as computer programs.