Editing Genetic programming (section)

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