Editing Genetic programming (section)

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