Editing Genetic programming

{{Short description|Evolving computer programs with techniques analogous to natural genetic processes}}
{{Distinguish|generic programming|genetic engineering|DNA computing}}
{{Evolutionary algorithms}}

'''Genetic programming''' ('''GP''') is an [[evolutionary algorithm]], an artificial intelligence technique mimicking natural evolution, which operates on a population of programs. It applies the [[genetic operators]] [[selection (evolutionary algorithm)|selection]] according to a predefined [[fitness function|fitness measure]], [[mutation (evolutionary algorithm)|mutation]] and [[crossover (evolutionary algorithm)|crossover]].  

The crossover operation involves swapping specified parts of selected pairs (parents) to produce new and different offspring that become part of the new generation of programs. Some programs not selected for reproduction are copied from the current generation to the new generation. Mutation involves substitution of some random part of a program with some other random part of a program. Then the selection and other operations are recursively applied to the new generation of programs.

Typically, members of each new generation are on average more fit than the members of the previous generation, and the best-of-generation program is often better than the best-of-generation programs from previous generations.  Termination of the evolution usually occurs when some individual program reaches a predefined proficiency or fitness level.

It may and often does happen that a particular run of the algorithm results in premature convergence to some local maximum which is not a globally optimal or even good solution.  Multiple runs (dozens to hundreds) are usually necessary to produce a very good result.  It may also be necessary to have a large starting population size and variability of the individuals to avoid pathologies.

==History==
The first record of the proposal to evolve programs is probably that of [[Alan Turing]] in 1950 in "[[Computing Machinery and Intelligence]]". There was a gap of 25 years before the publication of John Holland's 'Adaptation in Natural and Artificial Systems' laid out the theoretical and empirical foundations of the science. In 1981, Richard Forsyth demonstrated the successful evolution of small programs, represented as trees, to perform classification of crime scene evidence for the UK Home Office.<ref>{{Cite web|url=https://www.cs.bham.ac.uk/~wbl/biblio/gp-html/kybernetes_forsyth.html|title=BEAGLE A Darwinian Approach to Pattern Recognition|website=www.cs.bham.ac.uk|language=en|access-date=2018-05-19}}</ref>

Although the idea of evolving programs, initially in the computer language [[Lisp (programming language)|Lisp]], was current amongst John Holland's students,<ref>A personal communication with [http://www.dcs.bbk.ac.uk/~tom/ Tom Westerdale]</ref> it was not until they organised the first [[Genetic algorithm|Genetic Algorithms]] (GA) conference in Pittsburgh that Nichael Cramer<ref>{{Cite web|url=https://www.cs.bham.ac.uk/~wbl/biblio/gp-html/icga85_cramer.html|title=A representation for the Adaptive Generation of Simple Sequential Programs|website=www.cs.bham.ac.uk|language=en|access-date=2018-05-19}}</ref> published evolved programs in two specially designed languages, which included the first statement of modern "tree-based" Genetic Programming (that is, procedural languages organized in tree-based structures and operated on by suitably defined GA-operators). In 1988, [[John Koza]] (also a PhD student of John Holland) patented his invention of a GA for program evolution.<ref>{{Cite web|url=https://www.cs.bham.ac.uk/~wbl/biblio/gp-html/Koza_1990_pat-GAsp.html|title=Non-Linear Genetic Algorithms for Solving Problems|website=www.cs.bham.ac.uk|language=en|access-date=2018-05-19}}</ref> This was followed by publication in the International Joint Conference on Artificial Intelligence IJCAI-89.<ref>{{Cite web|url=https://www.cs.bham.ac.uk/~wbl/biblio/gp-html/Koza89.html|title=Hierarchical genetic algorithms operating on populations of computer programs|website=www.cs.bham.ac.uk|language=en|access-date=2018-05-19}}</ref>

Koza followed this with 205 publications on “Genetic Programming” (GP), name coined by David Goldberg, also a PhD student of John Holland.<ref>Goldberg. D.E. (1983), Computer-aided gas pipeline operation using genetic algorithms and rule learning. Dissertation presented to the University of Michigan at Ann Arbor, Michigan, in partial fulfillment of the requirements for Ph.D.</ref> However, it is the series of 4 books by Koza, starting in 1992<ref>{{Cite web|url=https://www.cs.bham.ac.uk/~wbl/biblio/gp-html/koza_book.html|title=Genetic Programming: On the Programming of Computers by Means of Natural Selection|website=www.cs.bham.ac.uk|language=en|access-date=2018-05-19}}</ref> with accompanying videos,<ref>{{Cite web|url=https://www.youtube.com/watch?v=tTMpKrKkYXo| archive-url=https://ghostarchive.org/varchive/youtube/20211211/tTMpKrKkYXo| archive-date=2021-12-11 | url-status=live|title=Genetic Programming:The Movie|website=gpbib.cs.ucl.ac.uk| date=16 December 2020|language=en|access-date=2021-05-20}}{{cbignore}}</ref> that really established GP. Subsequently, there was an enormous expansion of the number of publications with the Genetic Programming Bibliography, surpassing 10,000 entries.<ref>{{Cite web|url=http://gpbib.cs.ucl.ac.uk/gp-html/Hu_2014_Alife.html|title=The effects of recombination on phenotypic exploration and robustness in evolution|website=gpbib.cs.ucl.ac.uk|language=en|access-date=2021-05-20}}</ref> In 2010, Koza<ref>{{Cite web|url=https://www.cs.bham.ac.uk/~wbl/biblio/gp-html/Koza_2010_GPEM.html|title=Human-competitive results produced by genetic programming|website=www.cs.bham.ac.uk|language=en|access-date=2018-05-20}}</ref> listed 77 results where Genetic Programming was human competitive.

The departure of GP from the rigid, fixed-length representations typical of early GA models was not entirely without precedent. Early work on variable-length representations laid the groundwork. One notable example is Messy Genetic Algorithms, which introduced irregular, variable-length chromosomes to address building block disruption and positional bias in standard GAs.<ref>Goldberg, D.E., Korb, B., & Deb, K. (1989). Messy Genetic Algorithms: Motivation, Analysis, and First Results. Complex Systems, 3, 493–530.</ref>

Another precursor was robot trajectory programming, where genome representations encoded program instructions for robotic movements—structures inherently variable in length.<ref>Davidor, Y. (1989). Analogous Crossover. In Proceedings of the 3rd International Conference on Genetic Algorithms (pp. 98–103). Morgan Kaufmann.</ref>

Even earlier, unfixed-length representations were proposed in a doctoral dissertation by Cavicchio, who explored adaptive search using simulated evolution. His work provided foundational ideas for flexible program structures.<ref>Cavicchio, D.J. (1970). Adaptive Search Using Simulated Evolution. Doctoral dissertation, University of Michigan, Ann Arbor.</ref>

In 1996, Koza started the annual Genetic Programming conference<ref>{{Cite web|url=https://www.cs.bham.ac.uk/~wbl/biblio/gp-html/koza_gp96.html|title=Genetic Programming 1996: Proceedings of the First Annual Conference|website=www.cs.bham.ac.uk|language=en|access-date=2018-05-19}}</ref> which was followed in 1998 by the annual EuroGP conference,<ref>{{Cite web|url=https://www.cs.bham.ac.uk/~wbl/biblio/gp-html/banzhaf_1998_GP.html|title=Genetic Programming|website=www.cs.bham.ac.uk|language=en|access-date=2018-05-19}}</ref> and the first book<ref>{{Cite web|url=https://www.cs.bham.ac.uk/~wbl/biblio/gp-html/langdon_book.html|title=Genetic Programming and Data Structures: Genetic Programming + Data Structures = Automatic Programming!|website=www.cs.bham.ac.uk|language=en|access-date=2018-05-20}}</ref> in a GP series edited by Koza. 1998 also saw the first GP textbook.<ref name="cs.bham.ac.uk">{{Cite web|url=https://www.cs.bham.ac.uk/~wbl/biblio/gp-html/banzhaf_1997_book.html|title=Genetic Programming -- An Introduction; On the Automatic Evolution of Computer Programs and its Applications|website=www.cs.bham.ac.uk|language=en|access-date=2018-05-20}}</ref> GP continued to flourish, leading to the first specialist GP journal<ref>{{Cite journal|last=Banzhaf|first=Wolfgang|date=2000-04-01|title=Editorial Introduction|journal=Genetic Programming and Evolvable Machines|language=en|volume=1|issue=1–2|pages=5–6|doi=10.1023/A:1010026829303|issn=1389-2576}}</ref> and three years later (2003) the annual Genetic Programming Theory and Practice (GPTP) workshop was established by Rick Riolo.<ref>{{Cite web|url=https://www.cs.bham.ac.uk/~wbl/biblio/gp-html/RioloWorzel_2003.html|title=Genetic Programming Theory and Practice|website=www.cs.bham.ac.uk|language=en|access-date=2018-05-20}}</ref><ref name="field guide">{{Cite web|url=http://www.gp-field-guide.org.uk/|title=A Field Guide to Genetic Programming|website=www.gp-field-guide.org.uk|access-date=2018-05-20}}</ref> Genetic Programming papers continue to be published at a diversity of conferences and associated journals. Today there are nineteen GP books including several for students.<ref name="cs.bham.ac.uk"/>

{| class="wikitable sortable"
|+ Timeline of EP - selected algorithms<ref name=overview>{{cite journal |last1=Slowik |first1=Adam |last2=Kwasnicka |first2=Halina |title=Evolutionary algorithms and their applications to engineering problems |journal=Neural Computing and Applications |date=1 August 2020 |volume=32 |issue=16 |pages=12363–12379 |doi=10.1007/s00521-020-04832-8 |language=en |issn=1433-3058|doi-access=free }}</ref>
|-
! Year !! Description !! Reference
|-
| 1992 || Introduction of GP as genetically bred populations of computer programs || <ref>{{cite journal |last1=Koza |first1=J. R. G. P. |title=On the programming of computers by means of natural selection |journal=Genetic Programming |date=1992}}</ref>
|-
| 2000 || [[Cartesian genetic programming]] || <ref>{{cite book |last1=Miller |first1=Julian F. |series=Natural Computing Series |chapter=Cartesian Genetic Programming |date=2011 |pages=17–34 |doi=10.1007/978-3-642-17310-3_2 |chapter-url=https://link.springer.com/chapter/10.1007/978-3-642-17310-3_2 |publisher=Springer |isbn=978-3-642-17309-7 |language=en}}</ref>
|-
| 2000 || Grammar-guided GP - Dynamic grammar pruning is applied in initialization|| <ref>{{cite book |last1=Ratle |first1=Alain |last2=Sebag |first2=Michèle |chapter=Genetic Programming and Domain Knowledge: Beyond the Limitations of Grammar-Guided Machine Discovery |title=Parallel Problem Solving from Nature PPSN VI |series=Lecture Notes in Computer Science |date=2000 |volume=1917 |pages=211–220 |doi=10.1007/3-540-45356-3_21 |chapter-url=https://link.springer.com/chapter/10.1007/3-540-45356-3_21 |publisher=Springer |isbn=978-3-540-41056-0 |language=en}}</ref>
|-
| 2001 || [[Gene expression programming]] || <ref>{{cite arXiv |last1=Ferreira |first1=Candida |title=Gene Expression Programming: a New Adaptive Algorithm for Solving Problems |date=2001 |eprint=cs/0102027 }}</ref>
|-
| 2012 || Multi-gene GP - Combination of classical method for parameter estimation and structure selection || <ref>{{cite journal |last1=Gandomi |first1=Amir Hossein |last2=Alavi |first2=Amir Hossein |title=A new multi-gene genetic programming approach to nonlinear system modeling. Part I: materials and structural engineering problems |journal=Neural Computing and Applications |date=1 February 2012 |volume=21 |issue=1 |pages=171–187 |doi=10.1007/s00521-011-0734-z |url=https://link.springer.com/article/10.1007/s00521-011-0734-z |language=en |issn=1433-3058|url-access=subscription }}</ref>
|-
| 2012 || Geometric semantic GP - Direct search in the space of the underlying semantics of the programs || <ref>{{cite book |last1=Moraglio |first1=Alberto |last2=Krawiec |first2=Krzysztof |last3=Johnson |first3=Colin G. |chapter=Geometric Semantic Genetic Programming |title=Parallel Problem Solving from Nature - PPSN XII |series=Lecture Notes in Computer Science |date=2012 |volume=7491 |pages=21–31 |doi=10.1007/978-3-642-32937-1_3 |chapter-url=https://link.springer.com/chapter/10.1007/978-3-642-32937-1_3 |publisher=Springer |isbn=978-3-642-32936-4 |language=en}}</ref>
|-
| 2015 || Surrogate GP || <ref>{{cite journal |last1=Kattan |first1=Ahmed |last2=Ong |first2=Yew-Soon |title=Surrogate Genetic Programming: A semantic aware evolutionary search |journal=Information Sciences |date=1 March 2015 |volume=296 |pages=345–359 |doi=10.1016/j.ins.2014.10.053 |url=https://www.sciencedirect.com/science/article/abs/pii/S0020025514010421 |issn=0020-0255|url-access=subscription }}</ref>
|-
| 2015 || Memetic semantic GP || <ref>{{cite book |last1=Ffrancon |first1=Robyn |last2=Schoenauer |first2=Marc |chapter=Memetic Semantic Genetic Programming |title=Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation |date=11 July 2015 |pages=1023–1030 |doi=10.1145/2739480.2754697 |chapter-url=https://dl.acm.org/doi/10.1145/2739480.2754697 |publisher=Association for Computing Machinery|isbn=978-1-4503-3472-3 |url=https://hal.inria.fr/hal-01169074/file/8parV_errors_old_vs_new.pdf }}</ref>
|-
| 2017 || Statistical GP -  statistical information used to generate well-structured subtrees || <ref>{{cite journal |last1=Amir Haeri |first1=Maryam |last2=Ebadzadeh |first2=Mohammad Mehdi |last3=Folino |first3=Gianluigi |title=Statistical genetic programming for symbolic regression |journal=Applied Soft Computing |date=1 November 2017 |volume=60 |pages=447–469 |doi=10.1016/j.asoc.2017.06.050 |url=https://www.sciencedirect.com/science/article/abs/pii/S1568494617303939 |issn=1568-4946|url-access=subscription }}</ref>
|-
| 2018 || Multi-dimensional GP -  novel program representation for multi-dimensional features || <ref>{{cite journal |last1=La Cava |first1=William |last2=Silva |first2=Sara |last3=Danai |first3=Kourosh |last4=Spector |first4=Lee |last5=Vanneschi |first5=Leonardo |last6=Moore |first6=Jason H. |title=Multidimensional genetic programming for multiclass classification |journal=Swarm and Evolutionary Computation |date=1 February 2019 |volume=44 |pages=260–272 |doi=10.1016/j.swevo.2018.03.015 |url=https://www.sciencedirect.com/science/article/abs/pii/S2210650217309136 |issn=2210-6502}}</ref>
|}

===Foundational work in GP===
Early work that set the stage for current genetic programming research topics and applications is diverse, and includes [[program synthesis|software synthesis]] and repair, predictive modeling, data mining,<ref>{{Cite web|url=https://www.cs.bham.ac.uk/~wbl/biblio/gp-html/freitas_2002_book.html|title=Data Mining and Knowledge Discovery with Evolutionary Algorithms|website=www.cs.bham.ac.uk|language=en|access-date=2018-05-20}}</ref> financial modeling,<ref>{{Cite web|url=https://www.cs.bham.ac.uk/~wbl/biblio/gp-html/tsang_1998_eddie.html|title=EDDIE beats the bookies|website=www.cs.bham.ac.uk|language=en|access-date=2018-05-20}}</ref> soft sensors,<ref>{{Cite web|url=https://www.cs.bham.ac.uk/~wbl/biblio/gp-html/Kordon_book.html|title=Applying Computational Intelligence How to Create Value|website=www.cs.bham.ac.uk|language=en|access-date=2018-05-20}}</ref> design,<ref>{{Cite web|url=https://www.cs.bham.ac.uk/~wbl/biblio/gp-html/DBLP_journals_aiedam_Koza08.html|title=Human-competitive machine invention by means of genetic programming|website=www.cs.bham.ac.uk|language=en|access-date=2018-05-20}}</ref> and image processing.<ref>{{Cite web|url=https://www.cs.bham.ac.uk/~wbl/biblio/gp-html/lam_doh_gecco2004.html|title=Discovery of Human-Competitive Image Texture Feature Extraction Programs Using Genetic Programming|website=www.cs.bham.ac.uk|language=en|access-date=2018-05-20}}</ref> Applications in some areas, such as design, often make use of intermediate representations,<ref>{{Cite web|url=https://www.cs.bham.ac.uk/~wbl/biblio/gp-html/bentley_1999_TWGDACEEDP.html|title=Three Ways to Grow Designs: A Comparison of Embryogenies for an Evolutionary Design Problem|website=www.cs.bham.ac.uk|language=en|access-date=2018-05-20}}</ref> such as Fred Gruau's cellular encoding.<ref>{{Cite journal|url=https://ieeexplore.ieee.org/document/243137|title=Cellular encoding as a graph grammar - IET Conference Publication|pages=17/1–1710|website=[[IEEE]]|language=en-US|access-date=2018-05-20|date=April 1993}}</ref> Industrial uptake has been significant in several areas including finance, the chemical industry, bioinformatics<ref>{{Cite web|url=https://www.cs.bham.ac.uk/~wbl/biblio/gp-html/taylor_1998_gadiirsab.html|title=Genetic Algorithm Decoding for the Interpretation of Infra-red Spectra in Analytical Biotechnology|website=www.cs.bham.ac.uk|language=en|access-date=2018-05-20}}</ref><ref>{{Cite web|url=https://www.cs.bham.ac.uk/~wbl/biblio/gp-html/langdon_2004_GPEM.html|title=Genetic Programming for Mining DNA Chip data from Cancer Patients|website=www.cs.bham.ac.uk|language=en|access-date=2018-05-20}}</ref> and the steel industry.<ref>{{Cite web|url=https://www.cs.bham.ac.uk/~wbl/biblio/gp-html/Kovacic_2009_MMP2.html|title=Genetic Programming and Jominy Test Modeling|website=www.cs.bham.ac.uk|language=en|access-date=2018-05-20}}</ref>

==Methods==
===Program representation===
[[Image:Genetic Program Tree.png|frame|A function represented as a [[tree structure]] ]]
{{Main | genetic representation}}

GP evolves computer programs, traditionally represented in memory as [[tree (data structure)|tree structure]]s.<ref name="sover1985">Nichael L. Cramer [http://www.sover.net/~nichael/nlc-publications/icga85/index.html "A Representation for the Adaptive Generation of Simple Sequential Programs"] {{Webarchive|url=https://web.archive.org/web/20051204112804/http://www.sover.net/~nichael/nlc-publications/icga85/index.html |date=2005-12-04 }}.</ref> Trees can be easily evaluated in a recursive manner. Every internal 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 language]]s that naturally embody tree structures (for example, [[Lisp (programming language)|Lisp]]; other [[Functional programming|functional programming languages]] are also suitable).

Non-tree representations have been suggested and successfully implemented, such as [[linear genetic programming]] which perhaps suits the more traditional [[imperative languages]].<ref>Genetic Programming: An Introduction,
Wolfgang Banzhaf, Peter Nordin, Robert E. Keller, Frank D. Francone,
Morgan Kaufmann,
1999.
ISBN 978-1558605107</ref><ref>Garnett Wilson and Wolfgang Banzhaf. [http://www.cs.mun.ca/~banzhaf/papers/eurogp08_clgp.pdf "A Comparison of Cartesian Genetic Programming and Linear Genetic Programming"]</ref> The commercial GP software ''Discipulus'' uses automatic induction of binary machine code ("AIM")<ref>([[Peter Nordin]], 1997, Banzhaf et al., 1998, Section 11.6.2-11.6.3)</ref> to achieve better performance. ''μGP''<ref>{{cite web|url=http://ugp3.sourceforge.net/|title=μGP (MicroGP)|author=Giovanni Squillero}}</ref> uses [[directed multigraph]]s to generate programs that fully exploit the syntax of a given [[assembly language]]. [[Multi expression programming]] uses [[Three-address code]] for encoding solutions. Other program representations on which significant research and development have been conducted include programs for stack-based virtual machines,<ref>{{Cite web|url=http://gpbib.cs.ucl.ac.uk/gp-html/ieee94_perkis.html|title=Stack-Based Genetic Programming|website=gpbib.cs.ucl.ac.uk|language=en|access-date=2021-05-20}}</ref><ref name="Spector 7–40">{{Cite journal|last1=Spector|first1=Lee|last2=Robinson|first2=Alan|date=2002-03-01|title=Genetic Programming and Autoconstructive Evolution with the Push Programming Language|journal=Genetic Programming and Evolvable Machines|language=en|volume=3|issue=1|pages=7–40|doi=10.1023/A:1014538503543|s2cid=5584377|issn=1389-2576}}</ref><ref>{{Cite book|last1=Spector|first1=Lee|last2=Klein|first2=Jon|last3=Keijzer|first3=Maarten|title=Proceedings of the 7th annual conference on Genetic and evolutionary computation |chapter=The Push3 execution stack and the evolution of control |date=2005-06-25|publisher=ACM|pages=1689–1696|doi=10.1145/1068009.1068292|isbn=978-1595930101|citeseerx=10.1.1.153.384|s2cid=11954638}}</ref> and sequences of integers that are mapped to arbitrary programming languages via grammars.<ref>{{Cite book|title=Lecture Notes in Computer Science|last1=Ryan|first1=Conor|last2=Collins|first2=JJ|last3=Neill|first3=Michael O|date=1998|publisher=Springer Berlin Heidelberg|isbn=9783540643609|location=Berlin, Heidelberg|pages=83–96|doi = 10.1007/bfb0055930|citeseerx = 10.1.1.38.7697}}</ref><ref>{{Cite journal|last1=O'Neill|first1=M.|last2=Ryan|first2=C.|s2cid=10391383|date=2001|title=Grammatical evolution|journal=IEEE Transactions on Evolutionary Computation|language=en-US|volume=5|issue=4|pages=349–358|doi=10.1109/4235.942529|issn=1089-778X}}</ref> [[Cartesian genetic programming]] is another form of GP, which uses a graph representation instead of the usual tree based representation to encode computer programs.

Most representations have structurally noneffective code ([[intron]]s). Such non-coding genes may seem to be useless because they have no effect on the performance of any one individual.  However, they alter the probabilities of generating different offspring under the variation operators, and thus alter the individual's [[variational properties]].
Experiments seem to show faster convergence when using program representations that allow such non-coding genes, compared to program representations that do not have any non-coding genes.<ref>Julian F. Miller.
[https://www.springer.com/cda/content/document/cda_downloaddocument/9783642173097-c2.pdf "Cartesian Genetic Programming"] {{Webarchive|url=https://web.archive.org/web/20150924123354/http://www.springer.com/cda/content/document/cda_downloaddocument/9783642173097-c2.pdf |archive-url=https://web.archive.org/web/20150924123354/http://www.springer.com/cda/content/document/cda_downloaddocument/9783642173097-c2.pdf |archive-date=2015-09-24 |url-status=live |date=2015-09-24 }}.
p. 19.</ref><ref>
Janet Clegg; James Alfred Walker; Julian Francis Miller.
[http://www.cs.bham.ac.uk/~wbl/biblio/gecco2007/docs/p1580.pdf A New Crossover Technique for Cartesian Genetic Programming"].
2007.</ref> Instantiations may have both trees with introns and those without; the latter are called canonical trees. Special canonical crossover operators are introduced that maintain the canonical structure of parents in their children.

===Initialisation===
The methods for creation of the initial population include:<ref>{{cite journal |last1=Walker |first1=Matthew |title=Introduction to Genetic Programming |journal=Massey University |date=2001}}</ref>
* '''Grow''' creates the individuals sequentially. Every GP tree is created starting from the root, creating functional nodes with children as well as terminal nodes up to a certain depth. 
* '''Full''' is similar to the ''Grow''. The difference is that all brunches in a tree are of same predetermined depth.
* '''Ramped half-and-half''' creates a populations consisting of <math>md-1</math> parts and a maximum depth of <math>md</math> for its trees. The first part has a maximum depth of 2, second of 3 and so on up to the <math>md-1</math>-th part with maximum depth <math>md</math>. Half of every part is created by ''Grow'', while the other part is created by ''Full''.

===Selection===
Selection is a process whereby certain individuals are selected from the current generation that would serve as parents for the next generation. The individuals are selected probabilistically such that the better performing individuals have a higher chance of getting selected.<ref name="field guide" /> The most commonly used selection method in GP is [[tournament selection]], although other methods such as [[fitness proportionate selection]], lexicase selection,<ref>{{Cite book|last=Spector|first=Lee|title=Proceedings of the 14th annual conference companion on Genetic and evolutionary computation |chapter=Assessment of problem modality by differential performance of lexicase selection in genetic programming |url=https://dl.acm.org/citation.cfm?id=2330846|pages=401–408|language=en-US|publisher=ACM|doi=10.1145/2330784.2330846|year=2012|isbn=9781450311786|series=Gecco '12|s2cid=3258264}}</ref> and others have been demonstrated to perform better for many GP problems.

Elitism, which involves seeding the next generation with the best individual (or best ''n'' individuals) from the current generation, is a technique sometimes employed to avoid regression.

===Crossover===
[[File:Genetic_programming_subtree_crossover.gif|thumb|Genetic programming subtree crossover]]
In Genetic Programming two fit individuals are chosen from the population to be parents for one or two children. In tree genetic programming, these parents are represented as inverted lisp like trees, with their root nodes at the top. In subtree crossover in each parent a subtree is randomly chosen. (Highlighted with yellow in the animation.) In the root donating parent (in the animation on the left) the chosen subtree is removed and replaced with a copy of the randomly chosen subtree from the other parent, to give a new child tree.

Sometimes two child crossover is used, in which case the removed subtree (in the animation on the left) is not simply deleted but is copied to a copy of the second parent (here on the right) replacing (in the copy) its randomly chosen subtree. Thus this type of subtree crossover takes two fit trees and generates two child trees.

The tree-based approach in Genetic Programming also shares structural and procedural similarities with earlier knowledge-based and topology-oriented crossover methods. Specifically, analogous crossover and homologous crossover, both implemented in robot trajectory planning, exhibit a resemblance to subtree operations in tree GP. These crossover mechanisms were described in the context of heuristic optimisation strategies in robotics.<ref>Davidor, Y. (1991). Genetic Algorithms and Robotics: A Heuristic Strategy for Optimization. World Scientific Series in Robotics and Intelligent Systems: Volume 1.</ref>

===Replication===
Some individuals selected according to fitness criteria do not participate in crossover, but are copied into the next generation, akin to asexual reproduction in the natural world. They may be further subject to mutation.

===Mutation===
[[File:Genetic programming mutation.gif|thumb|Animation of creating genetic programing child by mutating parent removing subtree and replacing with random code]]
There are many types of mutation in genetic programming. They start from a fit syntactically correct parent and aim to randomly create a syntactically correct child. In the animation
a subtree is randomly chosen (highlighted by yellow). It is removed and replaced by a randomly generated subtree.

Other mutation operators select a leaf (external node) of the tree and replace it with a randomly chosen leaf. Another mutation is to select at random a function (internal node) and replace it with another function with the same arity (number of inputs). Hoist mutation randomly chooses a subtree and replaces it with a subtree within itself. Thus hoist mutation is guaranteed to make the child smaller. Leaf and same arity function replacement ensure the child is the same size as the parent. Whereas subtree mutation (in the animation) may, depending upon the function and terminal sets, have a bias to either increase or decrease the tree size. Other subtree based mutations try to carefully control the size of the replacement subtree and thus the size of the child tree. 

Similarly there are many types of linear genetic programming mutation, each of which tries to ensure the mutated child is still syntactically correct.

==Applications==
GP has been successfully used as an [[automatic programming]] tool, a machine learning tool and an automatic problem-solving engine.<ref name="field guide" /> GP is especially useful in the domains where the exact form of the solution is not known in advance or an approximate solution is acceptable (possibly because finding the exact solution is very difficult). Some of the applications of GP are curve fitting, data modeling, [[symbolic regression]], [[feature selection]], classification, etc. John R. Koza mentions 76 instances where Genetic Programming has been able to produce results that are competitive with human-produced results (called Human-competitive results).<ref>{{Cite journal|last=Koza|first=John R|title=Human-competitive results produced by genetic programming|journal=Genetic Programming and Evolvable Machines|volume=11|issue=3–4|pages=251–284|language=en-US|doi=10.1007/s10710-010-9112-3|year=2010|doi-access=free}}</ref> Since 2004, the annual Genetic and Evolutionary Computation Conference ([[GECCO]]) holds Human Competitive Awards (called Humies) competition,<ref>{{cite web|url=http://www.human-competitive.org/awards|title=Humies =Human-Competitive Awards}}</ref> where cash awards are presented to human-competitive results produced by any form of genetic and evolutionary computation. GP has won many awards in this competition over the years.

==Meta-genetic programming==
Meta-genetic programming is the proposed [[meta-learning (computer science)|meta-learning]] technique of evolving a genetic programming system using genetic programming itself. 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 formally proposed by [[Jürgen Schmidhuber]] in 1987.<ref>{{cite web|url=http://www.idsia.ch/~juergen/diploma.html|title=1987 THESIS ON LEARNING HOW TO LEARN, METALEARNING, META GENETIC PROGRAMMING, CREDIT-CONSERVING MACHINE LEARNING ECONOMY}}</ref> [[Douglas Lenat|Doug Lenat]]'s [[Eurisko]] is an earlier effort that may be the same technique. It is a recursive but terminating algorithm, allowing it to avoid infinite recursion. In the "autoconstructive evolution" approach to meta-genetic programming, the methods for the production and variation of offspring are encoded within the evolving programs themselves, and programs are executed to produce new programs to be added to the population.<ref name="Spector 7–40"/><ref>{{Cite book|title=GECCO '16 Companion : proceedings of the 2016 Genetic and Evolutionary Computation Conference : July 20-24, 2016, Denver, Colorado, USA|others=Neumann, Frank (Computer scientist), Association for Computing Machinery. SIGEVO|date=20 July 2016|isbn=9781450343237|location=New York, New York|oclc=987011786}}</ref>

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.

==See also==
* [[Bio-inspired computing]]
* [[CMA-ES|Covariance Matrix Adaptation Evolution Strategy]] (CMA-ES)
* [[Evolutionary image processing]]
* [[Fitness approximation]]
* [[Genetic improvement]]
* [[Genetic representation]]
* [[Grammatical evolution]]
* [[Inductive programming]]
* [[Linear genetic programming]]
* [[Multi expression programming]]
* [[Propagation of schema]]

==References==
{{reflist|30em}}

==External links==
* [https://web.archive.org/web/20070813222058/http://uk.geocities.com/markcsinclair/abstracts.html#pro00a/ Aymen S Saket & Mark C Sinclair]
* [https://www.springer.com/computer/ai/journal/10710 ''Genetic Programming and Evolvable Machines''], a journal
* [http://www.modulusfe.com/products/trading-system-developer-components/evo2-genetic-algorithm/ ''Evo2 for genetic programming'']
* [http://gpbib.cs.ucl.ac.uk/ GP bibliography]
* [http://www.cems.uwe.ac.uk/~apipe/Int%20and%20Adapt%20Sys/Revision%20material%20CD%20image/evonet.dcs.napier.ac.uk/index20.html The Hitch-Hiker's Guide to Evolutionary Computation]
* Riccardo Poli, William B. Langdon, Nicholas F. McPhee, John R. Koza, "[http://www.gp-field-guide.org.uk/ A Field Guide to Genetic Programming]" (2008)
* [http://www.geneticprogramming.com Genetic Programming, a community maintained resource]

{{Evolutionary computation}}
{{Authority control}}

{{DEFAULTSORT:Genetic Programming}}
<!-- categories -->
[[Category:Genetic programming| ]]