- Genetic programming
artificial intelligence, genetic programming (GP) is an evolutionary algorithmbased methodology inspired by biological evolutionto find computer programs that perform a user-defined task. It is a specialization of genetic algorithmswhere each individual is a computer program. Therefore it is a machine learningtechnique used to optimize a population of computer programs according to a fitness landscapedetermined by a program's ability to perform a given computational task.
The roots of GP begin with the
evolutionary algorithmsfirst utilized by Nils Aall Barricelliin 1954 as applied to evolutionary simulations but evolutionary algorithmsbecame widely recognized as optimization methods as a result of the work of Ingo Rechenbergin the 1960s and early 1970s - his group was able to solve complex engineering problems through evolution strategies(1971 PhD thesis and resulting 1973 book). Also highly influential was the work of John Holland in the early 1970s, and particularly his 1975 book.
The first results on the GP methodology were reported by
Stephen F. Smith(1980) [ [http://www-2.cs.cmu.edu/~sfs/ Stephen F. Smith ] ] . In 1981 Forsyth reported the evolution of small programs in forensic science for the UK police. The first statement of modern Genetic Programming (that is, procedural languages organized in tree-based structures and operated on by suitably defined GA-operators) was given by Nichael L. Cramer(1985), [ [http://www.sover.net/~nichael/nlc-publications/icga85/index.html Nichael Cramer's HomePage ] ] and independently by Jürgen Schmidhuber(1987). This work was later greatly expanded by John R. Koza, a main proponent of GP who has pioneered the application of genetic programming in various complex optimization and search problems [ [http://www.genetic-programming.com/ genetic-programming.com-Home-Page ] ] . It should be noted that in his seminal work Koza (1992, see bibliography) posits GP as a generalization of genetic algorithms rather than a specialization.
GP is very computationally intensive and so in the 1990s it was mainly used to solve relatively simple problems. But more recently, thanks to improvements in GP technology and to the exponential growth in CPU power, GP produced many novel and outstanding results in areas such as
quantum computing, electronic design, game playing, sorting, searchingand many more. [ [http://www.genetic-programming.com/humancompetitive.html humancompetitive ] ] These results include the replication or development of several post-year-2000 inventions. GP has also been applied to evolvable hardwareas well as computer programs. There are several GP patents listed in the web site [ [http://www.genetic-programming.com/patents.html jkpubs2001 ] ] .
Developing a theory for GP has been very difficult and so in the 1990s GP was considered a sort of outcast among search techniques. But 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 chainmodels). Fact|date=February 2007
GP evolves computer programs, traditionally represented in memory as
tree structures. Trees can be easily evaluated in a recursive manner. Every tree node has an operator function and every terminal node has an operand, making mathematical expressions easy to evolve and evaluate. Thus traditionally GP favors the use of programming languagesthat naturally embody tree structures (for example, Lisp; other functional programming languagesare also suitable).
Non-tree representations have been suggested and successfully implemented, such as the simpler
linear genetic programmingwhich suits the more traditional imperative languages[see, for example, Banzhaf "et al." (1998)] . The commercial GP software Discipulus, [ [http://www.aimlearning.com Genetic Programming is a powerful regression and classification tool with significant advantages over neural networks, decision trees, support vector machines and robust regression. It is fast, powerful and has a proven track record of results ] ] uses AIM, automatic induction of binary machine code [( Peter Nordin, 1997, Banzhaf et al., 1998, Section 11.6.2-11.6.3)] to achieve better performance. [ [http://www.aimlearning.com/aigp31.pdf aigp3.dvi ] ] MicroGP [ [http://www.cad.polito.it/research/microgp.html Research: MicroGP ] ] uses a representation similar to linear GP to generate programs that fully exploit the syntax of a given assembly language.
The main operators used in
evolutionary algorithmssuch as GP are crossover and mutation.
Crossover is applied on an individual by simply switching one of its nodes with another node from another individual in the population. With a tree-based representation, replacing a node means replacing the whole branch. This adds greater effectiveness to the crossover operator. The expressions resulting from crossover are very much different from their initial parents.
The following code suggests a simple implementation of individual deformation using crossover:
individual.Children [randomChildIndex] = otherIndividual.Children [randomChildIndex] ;
Mutation affects an individual in the population. It can replace a whole node in the selected individual, or it can replace just the node's information. To maintain integrity, operations must be
fail-safeor the type of information the node holds must be taken into account. For example, mutation must be aware of binary operation nodes, or the operator must be able to handle missing values.
A simple piece of code:
individual. Information = randomInformation;
individual = generateNewIndividual;
Meta-Genetic Programming is the proposed meta learning technique of evolving a genetic programming system using genetic programming itself. [ [http://www.helpmefigurethisout.com/ Welcome to www.helpmefigurethisout.com ] ] . It suggests that chromosomes, crossover, and mutation were themselves evolved, therefore like their real life counterparts should be allowed to change on their own rather than being determined by a human programmer. Meta-GP was proposed by
Jürgen Schmidhuberin 1987 [ [http://www.idsia.ch/~juergen/diploma.html 1987 THESIS ON LEARNING HOW TO LEARN, METALEARNING, META GENETIC PROGRAMMING, CREDIT-CONSERVING MACHINE LEARNING ECONOMY ] ] ; it is a recursive but terminating algorithm, allowing it to avoid infinite recursion.
Critics of this idea often say this approach is overly broad in scope. However, it might be possible to constrain the fitness criterion onto a general class of results, and so obtain an evolved GP that would more efficiently produce results for sub-classes. This might take the form of a Meta evolved GP for producing human walking algorithms which is then used to evolve human running, jumping, etc. The fitness criterion applied to the Meta GP would simply be one of efficiency.
For general problem classes there may be no way to show that Meta GP will reliably produce results more efficiently than a created algorithm other than exhaustion. The same holds for standard GP and other search algorithms.
Gene expression programming
References and notes
*Banzhaf, W., Nordin, P., Keller, R.E., Francone, F.D. (1998), "Genetic Programming: An Introduction: On the Automatic Evolution of Computer Programs and Its Applications", Morgan Kaufmann
*Barricelli, Nils Aall (1954), "Esempi numerici di processi di evoluzione," Methodos, pp. 45-68.
*Crosby, Jack L. (1973), "Computer Simulation in Genetics," John Wiley & Sons, London.
*Cramer, Nichael Lynn (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.), Carnegie Mellon University
*Fogel, David B. (2000) "Evolutionary Computation: Towards a New Philosophy of Machine Intelligence" IEEE Press, New York.
*Fogel, David B. (editor) (1998) "Evolutionary Computation: The Fossil Record," IEEE Press, New York.
*Forsyth, Richard (1981), [http://www.cs.bham.ac.uk/~wbl/biblio/gp-html/kybernetes_forsyth.html BEAGLE A Darwinian Approach to Pattern Recognition] Kybernetes, Vol. 10, pp. 159-166.
*Fraser, Alex S. (1957), "Simulation of Genetic Systems by Automatic Digital Computers. I. Introduction." Australian Journal of Biological Sciences vol. 10 484-491.
*Fraser, Alex and Donald Burnell (1970), "Computer Models in Genetics," McGraw-Hill, New York.
*Holland, John H (1975), "Adaptation in Natural and Artificial Systems", University of Michigan Press, Ann Arbor
*Koza, J.R. (1990), "Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems", Stanford University Computer Science Department technical report [http://www.genetic-programming.com/jkpdf/tr1314.pdf STAN-CS-90-1314] . A thorough report, possibly used as a draft to his 1992 book.
*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
*Koza, J.R., Keane, M.A., Streeter, M.J., Mydlowec, W., Yu, J., Lanza, G. (2003), "Genetic Programming IV: Routine Human-Competitive Machine Intelligence", Kluwer Academic Publishers
*Langdon, W. B., Poli, R. (2002), "Foundations of Genetic Programming", Springer-Verlag
*Nordin, J.P., (1997) Evolutionary Program Induction of Binary Machine Code and its Application. Krehl Verlag, Muenster, Germany.
*cite book | author=Poli, R., Langdon, W. B., McPhee, N. F. |year=2008 |title=A Field Guide to Genetic Programming | publisher=Lulu.com, freely available from the internet | isbn = 978-1-4092-0073-4
*Rechenberg, I. (1971): Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (PhD thesis). Reprinted by Fromman-Holzboog (1973).
* Schmidhuber, J. (1987). Evolutionary principles in self-referential learning. (On learning how to learn: The meta-meta-... hook.) Diploma thesis, Institut f. Informatik, Tech. Univ. Munich.
*Smith, S.F. (1980), "A Learning System Based on Genetic Adaptive Algorithms", PhD dissertation (University of Pittsburgh)
*Smith, Jeff S. (2002), [http://www.softtechdesign.com/GA/EvolvingABetterSolution-GA.html Evolving a Better Solution] , Developers Network Journal, March 2002 issue
* [http://www.gp-field-guide.org.uk/ A Field Guide to Genetic Programming] by Poli, Langdon, and McPhee. Available as a free PDF, or in printed form from Lulu.com.
* [http://uk.geocities.com/markcsinclair/abstracts.html#aiy97/ Aymen S Saket & Mark C Sinclair]
* [http://tech.groups.yahoo.com/group/genetic_programming/ Mailing list email@example.com]
* [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]
Jürgen Schmidhuber's [http://www.idsia.ch/~juergen/gp.html GP Site, with pre-Koza GP papers (1987)]
Jürgen Schmidhuber's [http://www.idsia.ch/~juergen/diploma.html Meta-GP thesis (1987)]
* [http://www.cs.bham.ac.uk/~wbl/biblio/README.html GP bibliography]
* [http://www.cs.ucl.ac.uk/staff/W.Langdon/homepages.html People who work on GP]
* [http://www.it-weise.de/projects/book.pdf Global Optimization Techniques and Genetic Programming Applied to Distributed Computing]
* [http://www.dna-evolutions.com/dnaappletsample.html Demo applet of a genetic algorithm solving TSPs and VRPTW problems] (.NET and Java)
* [http://uk.geocities.com/markcsinclair/ps/galesia97_aiy.ps.gz GP for the Optimization of the European Optical Network, Aymen Saket & Mark C Sinclair]
* [http://www.jaga.org JAGA - Extensible and pluggable open source API for implementing genetic algorithms and genetic programming applications] (Java)
* [http://gpe.sourceforge.net/ GPE - Framework for conducting experiments in Genetic Programming] (.NET)
* [http://www.lalena.com/ai/ant/ lalena.com - A Genetic Program for simulating ant food collection behaviors. Free download] (.NET)
* [http://dgpf.sourceforge.net/ DGPF - simple Genetic Programming research system] (Java)
* [http://jgap.sourceforge.net JGAP - Java Genetic Algorithms and Genetic Programming, an open-source framework] (Java)
* [http://cui.unige.ch/spc/tools/n-genes/ n-genes - Java Genetic Algorithms and Genetic Programming (stack oriented) framework] (Java)
* [http://pmdgp.sourceforge.net/ PMDGP - object oriented framework for solving genetic programming problems] (C++)
* [http://drp.rubyforge.org DRP - Directed Ruby Programming, Genetic Programming & Grammatical Evolution Library] (Ruby)
* [http://gplab.sourceforge.net GPLAB - A Genetic Programming Toolbox for MATLAB] (MATLAB)
* [http://www.staff.ncl.ac.uk/d.p.searson/gptips.htm GPTIPS - Genetic Programming Tool for MATLAB] (MATLAB)
* [http://emergent.brynmawr.edu/pyro/?page=PyroModuleEvolutionaryAlgorithms PyRobot - Evolutionary Algorithms (GA + GP) Modules, Open Source] (Python)
* [http://perlgp.org PerlGP - Grammar-based genetic programming in Perl] (Perl)
* [http://lancet.mit.edu/ga/ GAlib - Object oriented framework with 4 different GA implementations and 4 representation types (arbitrary derivations possible)] (C++)
* [http://www.softtechdesign.com/GA/EvolvingABetterSolution-GA.html Java GALib - Source Forge open source Java genetic algorithm library, complete with Javadocs and examples (see bottom of page)] (Java)
* [http://www.cis.nctu.edu.tw/~gis91815/lagep/lagep.html LAGEP. Supporting single/multiple population genetic programming to generate mathematical functions. Open Source, OpenMP used.] (C/C++)
* [http://www.cs.bham.ac.uk/~cmf/GPLib/index.html GPLib, a GP library from the University of Birmingham, UK] (C++)
* [http://jgprog.sourceforge.net/ Groovy Java Genetic Programming] (Java)
* [http://www.progranism.com/ Progranisms, self copying/evolving programs]
Possibly most used:
* [http://cs.gmu.edu/~eclab/projects/ecj/ ECJ - Evolutionary Computation/Genetic Programming research system] (Java)
* [http://beagle.sf.net/ Beagle - Open BEAGLE, a versatile EC framework] (C++ with STL)
* [http://eodev.sourceforge.net/ EO Evolutionary Computation Framework] (C++ with static polymorphism)
* [http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/weinbenner/gp.html GPC++ - Genetic Programming C++ Class Library] (C++)
* [http://www.icuintelligence.com ICU Intelligence AB]
* [http://www.irobis.com/ Institute of Robotics in Scandinavia AB (iRobis)]
* [http://www.aitellu.com/Aitellu/en Aitellu AB]
* [http://www.gepsoft.com/ Gepsoft Limited]
* [http://www.aimlearning.com/ RML Technologies, Inc.]
* [http://www.quantumtrader.com/ Quantum Trader (Trading System application)]
Wikimedia Foundation. 2010.
Look at other dictionaries:
Genetic programming — Die Genetische Programmierung (GP) ist wie der Genetische Algorithmus (GA) und die Evolutionsstrategie (ES) ein heuristisches Optimierungsverfahren und gehört in die Klasse der Evolutionären Algorithmen (EA). GP wird wie andere EA verwendet, um… … Deutsch Wikipedia
genetic programming — noun A search heuristic that explores the space of computer programs and is based on biological evolution … Wiktionary
Linear genetic programming — is unrelated to linear programming . Linear Genetic Programming (LGP) is a particular subset of genetic programming wherein computer programs in population are represented as a sequence of instructions from imperative programming language or… … Wikipedia
Genetic representation — is a way of representing solutions/individuals in evolutionary computation methods. Genetic representation can encode appearance, behavior, physical qualities of individuals. Designing a good genetic representation that is expressive and… … Wikipedia
Genetic algorithm — A genetic algorithm (GA) is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems. Genetic algorithms belong to the larger class of… … Wikipedia
Gene expression programming — (GEP) is an evolutionary algorithm that evolves populations of computer programs in order to solve a user defined problem. GEP has similarities, but is distinct to, the evolutionary computational method of Genetic Programming. In Genetic… … Wikipedia
Evolutionary programming — is one of the four major evolutionary algorithm paradigms. It was first used by Lawrence J. Fogel in 1960 in order to use simulated evolution as a learning process aiming to generate artificial intelligence. Fogel used finite state machines as… … Wikipedia
Schema (genetic algorithms) — A schema is a template in computer science used in the field of genetic algorithms that identifies a subset of strings with similarities at certain string positions. Schemata are a special case of cylinder sets; and so form a topological… … Wikipedia
Quality control and genetic algorithms — In engineering and manufacturing, quality control is involved in developing systems to ensure products or services are designed and produced to meet or exceed customer requirements. Genetic algorithms are search techniques, used in computing to… … Wikipedia
Inferential programming — In ordinary computer programming, the programmer keeps the program s intended results in mind and painstakingly constructs a computer program to achieve those results. Inferential programming refers to (still mostly hypothetical) techniques and… … Wikipedia