Genetic programming

From Wikipedia, the free encyclopedia

Genetic programming (GP) is a patented[1] automated methodology inspired by biological evolution to find computer programs that perform a user-defined task. Therefore it is a machine learning technique that uses an evolutionary algorithm to optimize a population of computer programs according to a fitness landscape determined by a program's ability to perform a given computational task. The first experiments with GP were reported by Stephen F. Smith (1980)[2] and Nichael L. Cramer (1985),[3] as described in the famous book Genetic Programming: On the Programming of Computers by Means of Natural Selection by John Koza (1992). In 1981 Forsyth reported the evolution of small programs in forensic science for the UK police.

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 has started delivering a number of outstanding results. At the time of writing, nearly 40 human-competitive results have been gathered, in areas such as quantum computing, electronic design, game playing, sorting, searching and many more.[4] These results include the replication or infringement of several post-year-2000 inventions[citation needed], and the production of two patentable new inventions.

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 chain models) and to show that GP is more general than, and includes, genetic algorithms.[citation needed]

GP has now been applied to evolvable hardware as well as computer programs.

In 2006, John Koza, known as "Father of Genetic Programming" announced the creation of a machine that emulates the versatility of biological mechanisms, in order to resolve problems, obtaining the best solutions. This machine can adapt itself to different kind of problems and give creative solutions for them.[citation needed]

Contents

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 on 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 was pioneered by Koza; other functional programming languages are also suitable).

Non-tree representations have been suggested and successfully implemented, such as the simpler linear genetic programming which suits the more traditional imperative languages [see, for example, Banzhaf et al. (1998)]. The commercial GP software Discipulus,[5] uses linear GP combined with machine code language to achieve better performance. MicroGP[6] 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 the evolution process 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 will suggest an easy to implement 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.

A simple piece of code:

individual.Information = randomInformation;

or

individual = generateNewIndividual;

Meta-Genetic Programming is the technique of evolving a genetic programming system using genetic programming itself.[7] It proposes 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. It is a very new area of research, and documentation on the subject is sparse.

Critics of this idea often say this is a problem of infinite recursion, as well as being overly broad in scope, and so could not produce any meaningful results. They also cite the halting problem in the context of knowing if it can ever produce results. 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.

There may be no way to show that Meta GP will reliably produce results more efficient than a created algorithm other than exhaustion.

  1. ^ http://www.genetic-programming.com/patents.html
  2. ^ http://www-2.cs.cmu.edu/~sfs/
  3. ^ http://www.sover.net/~nichael/
  4. ^ http://www.genetic-programming.com/humancompetitive.html
  5. ^ http://www.aimlearning.com
  6. ^ http://www.cad.polito.it/research/microgp.html
  7. ^ http://www.helpmefigurethisout.com/

  • 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
  • Richard Forsyth (1981), BEAGLE A Darwinian Approach to Pattern Recognition Kybernetes, Vol. 10, pp. 159-166.
  • Cramer, Nichael Lynn (1985), "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
  • 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 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
  • Smith, S.F. (1980), A Learning System Based on Genetic Adaptive Algorithms, PhD dissertation (University of Pittsburgh)

Implementations:

Possibly most used:

Retrieved from "http://en.wikipedia.org../../../g/e/n/Genetic_programming.html"
Advanced Search
Included Web Search Engines


Safe Search

close

Top Matching Results

Occasionally Search.com will highlight specialized results that are based on the context of your query. Examples of specialized results include specific links to news, images, or video.

Top Matching Results may highlight information from other Search.com pages, content from the CNET Network of sites, or third party content. The listings are based purely on relevance. Search.com does not receive payment for listings in this section but our partners that provide this data may get paid for listing these products.

Sponsored Links

This section contains paid listings which have been purchased by companies that want to have their sites appear for specific search terms and related content. These listings are administered, sorted and maintained by a third party and are not endorsed by Search.com.

Search Results

Search.com sends your search query to several search engines at one time and integrates the results into one list which has been sorted by relevance using Search.com's proprietary algorithm. You can customize the list of search engines included in your metasearch from the preferences.

The search engines that are used in your metasearch may allow companies to pay to have their Web sites included within the results. To view the Paid Inclusion policy for a specific search engine, please visit their Web site. Search.com does not accept payment or share revenue with any search engine partner for listings in this section.