Genetic programming: Difference between revisions

Revision as of 15:49, 19 August 2003

Revision as of 10:59, 23 September 2003

Line 1:

'''Genetic programming''' ('''GP''') is a subfield of [[evolutionary computation]] 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 be evolved according to some user-defined goal. It uses [[evolution]]ary patterns, using [[crossover]], selection, replication and [[mutation|mutations]] to evolve the programs which are usually represented by [[Lisp programming language|LISP]] expressions. In order to work effectively, it requires an appropriate selection of operators and variables.

Genetic programming uses methods which are similar to [[genetic algorithm]]s (GA), but is based on programs which perform tasks the results of which can then be evaluated to deliver a fitness function similar to GAs. Instead of using pools of parameter lists to be evaluated by some evaluation procedure, GP uses pools 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 fixed size, for the storage of 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 algorithm]]s to generate programs was first described in 1985 by [http://www.sover.net/~nichael/ [Nichael Lynn Cramer]]. As such, Koza did not invent Geneticgenetic programming, but he is indisputably the field's most prolific and persuasive author.

So far GPs have successfully solved some '''toy''' problems, such as the lawn mower problem, 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, due to the lack of solid theory regarding the performance of genetic programming vs. traditional search methods (such as hill-climbing), genetic programming remains a sort of pariah amongst the various techniques of search. While genetic programming has achieved results that are as good as and sometimes better than human-generated results, more work needs to be done on the theory in order to bring the technique into more widespread use.

==Resources==

'''References''':

* [http://www.cs.ucl.ac.uk/research/genprog/gp2faq/gp2faq.html Genetic Programming FAQ]

* [http://www.faqs.org/faqs/ai-faq/genetic/part1/preamble.html The Hitch-Hiker's Guide to Evolutionary Computation]

* [http://www.genetic-programming.com John Koza's Genetic Programming Site]

===Bibliography===

*Nichael, Lynn Cramer (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 (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

===External links===

Koza, J.R (1992), Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press

*[http://www.sover.net/~nichael/ Nichael Lynn Cramer]

* [http://www.cs.ucl.ac.uk/research/genprog/gp2faq/gp2faq.html Genetic Programming FAQ]

Koza, J.R (1994), Genetic Programming II: Automatic Discovery of Reusable Programs, MIT Press

* [http://www.faqs.org/faqs/ai-faq/genetic/part1/preamble.html The Hitch-Hiker's Guide to Evolutionary Computation]

* [http://www.genetic-programming.com John Koza's Genetic Programming Site]

Koza, J.R, Bennett, F.H, Andre, D, and Keane, M.A (1999), Genetic Programming III: Darwinian Invention and Problem Solving, Morgan Kaufmann