Genetic programming

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
Part of a series on the
Evolutionary algorithm
Genetic algorithm
Genetic programming
Not to be confused with Generic programming or Genetic engineering.

In artificial intelligence, genetic programming (GP) is a technique whereby computer programs are encoded as a set of genes that are then modified (evolved) using an evolutionary algorithm (often a genetic algorithm, "GA") – it is an application of (for example) genetic algorithms where the space of solutions consists of computer programs. The results are computer programs that are able to perform well in a predefined task. The methods used to encode a computer program in an artificial chromosome and to evaluate its fitness with respect to the predefined task are central in the GP technique and still the subject of active research.

History[edit]

The first record of the proposal to evolve programs is probably that of Alan Turing[1] in the 1950s. However, there was a gap of some thirty years before Richard Forsyth[2] demonstrated the successful evolution of small programs, represented as trees, to perform classification of crime scene evidence for the UK Home Office.

Although the idea of evolving programs, initially in the computer language Lisp, was current amongst John Holland’s students[3], it was not until they organised the first Genetic Algorithms conference in Pittsburgh that Nichael Cramer[4] published evolved programs in two specially designed languages. In 1988 John Koza (also a PhD student of John Holland) patented his invention of a GA for program evolution[5]. This was followed by publication in the International Joint Conference on Artificial Intelligence IJCAI-89[6].

Koza followed this with 205 publications on “Genetic Programming” (GP), name coined by David Goldberg, also a PhD student of John Holland[7]. However, it is the series of 4 books by Koza, starting in 1992[8] with accompanying videos[9], that really established GP. Subsequently, there was an enormous expansion of the number of publications with the Genetic Programming Bibliography, surpassing 10,000 entries[10]. In 2010, Koza[11] listed 77 results where Genetic Programming was human competitive.

In 1996 Koza started the annual Genetic Programming conference[12] which was followed in 1998 by the annual EuroGP conference[13], and the first book[14] in a GP series edited by Koza. 1998 also saw the first GP textbook[15]. GP continued to flourish, leading to the first specialist GP journal[16] and three years later (2003) the annual Genetic Programming Theory and Practice (GPTP) workshop was established by Rick Riolo[17][18]. 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[19].

Foundational Work in GP[edit]

Early work that set the stage for current genetic programming research topics and applications is diverse, and includes software synthesis and repair, predictive modelling, data mining[20], financial modeling[21], soft sensors[22], design[23], and image processing[24]. Applications in some areas, such as design, often make use of intermediate representations[25], such as Fred Gruau’s cellular encoding[26]. Industrial uptake has been significant in several areas including finance, the chemical industry, bioinformatics[27][28] and the steel industry[29].

Methods[edit]

Program representation[edit]

A function represented as a tree structure.
Main article: genetic representation

GP evolves computer programs, traditionally represented in memory as tree structures.[30] 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 languages that naturally embody tree structures (for example, Lisp; other functional programming languages are also suitable).

Non-tree representations have been suggested and successfully implemented, such as linear genetic programming which suits the more traditional imperative languages [see, for example, Banzhaf et al. (1998)].[31] The commercial GP software Discipulus uses automatic induction of binary machine code ("AIM")[32] to achieve better performance. µGP[33] uses directed multigraphs to generate programs that fully exploit the syntax of a given assembly language. Other program representations on which significant research and development have been conducted include programs for stack-based virtual machines[34][35][36], and sequences of integers that are mapped to arbitrary programming languages via grammars[37][38]. 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 (introns). 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.[39][40]

Selection[edit]

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[18]. The most commonly used selection method in GP is Tournament selection, although other methods such as Fitness proportionate selection, Lexicase Selection[41], and many others have been demonstrated to perform better for many GP problems.

Variation[edit]

Various genetic operators (i.e., crossover and mutation) are applied to the individuals selected in the selection step described above to breed new individuals. The rate at which these operators are applied determine the diversity in the population.

Applications[edit]

GP has been successfully used as an automatic programming tool, a machine learning tool and an automatic problem-solving engine[18]. GP is especially useful in the domains where the exact form of the solution is not known in advance or an approximates 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)[42]. Since 2004, the annual Genetic and Evolutionary Computation Conference (GECCO) holds Human Competitive Awards (called Humies) competition[43], 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[edit]

Meta-genetic programming is the proposed 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[44]. 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.[45][46]

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[edit]

References[edit]

  1. ^ "Computing Machinery and Intelligence". www.cs.bham.ac.uk. Retrieved 2018-05-19.
  2. ^ "BEAGLE A Darwinian Approach to Pattern Recognition". www.cs.bham.ac.uk. Retrieved 2018-05-19.
  3. ^ A personal communication with Tom Westerdale
  4. ^ "A representation for the Adaptive Generation of Simple Sequential Programs". www.cs.bham.ac.uk. Retrieved 2018-05-19.
  5. ^ "Non-Linear Genetic Algorithms for Solving Problems". www.cs.bham.ac.uk. Retrieved 2018-05-19.
  6. ^ "Hierarchical genetic algorithms operating on populations of computer programs". www.cs.bham.ac.uk. Retrieved 2018-05-19.
  7. ^ 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.
  8. ^ "Genetic Programming: On the Programming of Computers by Means of Natural Selection". www.cs.bham.ac.uk. Retrieved 2018-05-19.
  9. ^ "Genetic Programming:The Movie". www.cs.bham.ac.uk. Retrieved 2018-05-19.
  10. ^ "The effects of recombination on phenotypic exploration and robustness in evolution". www.cs.bham.ac.uk. Retrieved 2018-05-19.
  11. ^ "Human-competitive results produced by genetic programming". www.cs.bham.ac.uk. Retrieved 2018-05-20.
  12. ^ "Genetic Programming 1996: Proceedings of the First Annual Conference". www.cs.bham.ac.uk. Retrieved 2018-05-19.
  13. ^ "Genetic Programming". www.cs.bham.ac.uk. Retrieved 2018-05-19.
  14. ^ "Genetic Programming and Data Structures: Genetic Programming + Data Structures = Automatic Programming!". www.cs.bham.ac.uk. Retrieved 2018-05-20.
  15. ^ "Genetic Programming -- An Introduction; On the Automatic Evolution of Computer Programs and its Applications". www.cs.bham.ac.uk. Retrieved 2018-05-20.
  16. ^ Banzhaf, Wolfgang (2000-04-01). "Editorial Introduction". Genetic Programming and Evolvable Machines. 1 (1–2): 5–6. doi:10.1023/A:1010026829303. ISSN 1389-2576.
  17. ^ "Genetic Programming Theory and Practice". www.cs.bham.ac.uk. Retrieved 2018-05-20.
  18. ^ a b c "A Field Guide to Genetic Programming". www.gp-field-guide.org.uk. Retrieved 2018-05-20.
  19. ^ "Genetic Programming -- An Introduction; On the Automatic Evolution of Computer Programs and its Applications". www.cs.bham.ac.uk. Retrieved 2018-05-20.
  20. ^ "Data Mining and Knowledge Discovery with Evolutionary Algorithms". www.cs.bham.ac.uk. Retrieved 2018-05-20.
  21. ^ "EDDIE beats the bookies". www.cs.bham.ac.uk. Retrieved 2018-05-20.
  22. ^ "Applying Computational Intelligence How to Create Value". www.cs.bham.ac.uk. Retrieved 2018-05-20.
  23. ^ "Human-competitive machine invention by means of genetic programming". www.cs.bham.ac.uk. Retrieved 2018-05-20.
  24. ^ "Discovery of Human-Competitive Image Texture Feature Extraction Programs Using Genetic Programming". www.cs.bham.ac.uk. Retrieved 2018-05-20.
  25. ^ "Three Ways to Grow Designs: A Comparison of Embryogenies for an Evolutionary Design Problem". www.cs.bham.ac.uk. Retrieved 2018-05-20.
  26. ^ "Cellular encoding as a graph grammar - IET Conference Publication" (PDF). ieeexplore.ieee.org. April 1993. pp. 17/1–1710. Retrieved 2018-05-20.
  27. ^ "Genetic Algorithm Decoding for the Interpretation of Infra-red Spectra in Analytical Biotechnology". www.cs.bham.ac.uk. Retrieved 2018-05-20.
  28. ^ "Genetic Programming for Mining DNA Chip data from Cancer Patients". www.cs.bham.ac.uk. Retrieved 2018-05-20.
  29. ^ "Genetic Programming and Jominy Test Modeling". www.cs.bham.ac.uk. Retrieved 2018-05-20.
  30. ^ Nichael L. Cramer "A Representation for the Adaptive Generation of Simple Sequential Programs".
  31. ^ Garnett Wilson and Wolfgang Banzhaf. "A Comparison of Cartesian Genetic Programming and Linear Genetic Programming".
  32. ^ (Peter Nordin, 1997, Banzhaf et al., 1998, Section 11.6.2-11.6.3)
  33. ^ Giovanni Squillero. "µGP (MicroGP)".
  34. ^ Perkis, T. (1994). Stack-based genetic programming. Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence. IEEE. pp. 148–153. CiteSeerX 10.1.1.27.7055. doi:10.1109/icec.1994.350025. ISBN 978-0780318991.
  35. ^ Spector, Lee; Robinson, Alan (2002-03-01). "Genetic Programming and Autoconstructive Evolution with the Push Programming Language". Genetic Programming and Evolvable Machines. 3 (1): 7–40. doi:10.1023/A:1014538503543. ISSN 1389-2576.
  36. ^ Spector, Lee; Klein, Jon; Keijzer, Maarten (2005-06-25). The Push3 execution stack and the evolution of control. ACM. pp. 1689–1696. CiteSeerX 10.1.1.153.384. doi:10.1145/1068009.1068292. ISBN 978-1595930101.
  37. ^ Ryan, Conor; Collins, JJ; Neill, Michael O (1998). Lecture Notes in Computer Science. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 83–96. CiteSeerX 10.1.1.38.7697. doi:10.1007/bfb0055930. ISBN 9783540643609.
  38. ^ O'Neill, M.; Ryan, C. (2001). "Grammatical evolution". IEEE Transactions on Evolutionary Computation. 5 (4): 349–358. doi:10.1109/4235.942529. ISSN 1089-778X.
  39. ^ Julian F. Miller. "Cartesian Genetic Programming". p. 19.
  40. ^ Janet Clegg; James Alfred Walker; Julian Francis Miller. A New Crossover Technique for Cartesian Genetic Programming". 2007.
  41. ^ Spector, Lee (2012). Assessment of problem modality by differential performance of lexicase selection in genetic programming: a preliminary report. Proceedings of the 14th Annual Conference Companion on Genetic and Evolutionary Computation. Gecco '12. ACM. pp. 401–408. doi:10.1145/2330784.2330846. ISBN 9781450311786.
  42. ^ Koza, John R (2010). "Human-competitive results produced by genetic programming". Genetic Programming and Evolvable Machines. 11 (3–4): 251–284. doi:10.1007/s10710-010-9112-3.
  43. ^ "Humn =Human-Competitive Awards".
  44. ^ "1987 THESIS ON LEARNING HOW TO LEARN, METALEARNING, META GENETIC PROGRAMMING,CREDIT-CONSERVING MACHINE LEARNING ECONOMY".
  45. ^ Spector, Lee; Robinson, Alan (2002-03-01). "Genetic Programming and Autoconstructive Evolution with the Push Programming Language". Genetic Programming and Evolvable Machines. 3 (1): 7–40. doi:10.1023/A:1014538503543. ISSN 1389-2576.
  46. ^ GECCO '16 Companion : proceedings of the 2016 Genetic and Evolutionary Computation Conference : July 20-24, 2016, Denver, Colorado, USA. Neumann, Frank (Computer scientist), Association for Computing Machinery. SIGEVO. New York, New York. ISBN 9781450343237. OCLC 987011786.

External links[edit]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Genetic_programming&oldid=882146679"