In artificial intelligence, genetic
programming is an evolutionary algorithm-based methodology inspired by
biological evolution to find computer programs that perform a user-defined
task. Essentially GP is a set of instructions and a fitness function to
measure how well a computer has performed a task. It is a specialization
of genetic algorithms where each individual is a computer program. It is
a machine learning technique used to optimize a population of computer
programs according to a fitness landscape determined by a program’s
ability to perform a given computational task.
History In 1954, GP began with the evolutionary
algorithms first used by Nils Aall Barricelli applied to evolutionary
simulations. In the 1960s and early 1970s, evolutionary algorithms became
widely recognized as optimization methods. Ingo Rechenberg and his group
were able to solve complex engineering problems through evolution strategies as
documented in his 1971 PhD thesis and the resulting 1973 book. John Holland
was highly influential during the 1970s. In 1964, Lawrence J. Fogel, one of the
earliest practitioners of the GP methodology, applied evolutionary
algorithms to the problem of discovering finite-state automata. Later GP-related
work grew out of the learning classifier system community, which developed sets
of sparse rules describing optimal policies for Markov decision processes.
In 1981 Richard Forsyth evolved tree rules to classify heart disease. The
first statement of modern “tree-based” genetic programming was given by Nichael
L. Cramer. This work was later greatly expanded by John R. Koza, a main
proponent of GP who has pioneered the application of genetic programming in
various complex optimization and search problems. Gianna Giavelli, a student of
Koza’s, later pioneered the use of genetic programming as a technique to
model DNA expression. In the 1990s, GP was mainly used to
solve relatively simple problems because it is very computationally intensive.
Recently GP has produced many novel and outstanding results in areas such as
quantum computing, electronic design, game playing, sorting, and searching,
due to improvements in GP technology and the exponential growth in CPU power.
These results include the replication or development of several post-year-2000
inventions. GP has also been applied to evolvable hardware as well as computer
programs. Developing a theory for GP has been very
difficult and so in the 1990s GP was considered a sort of outcast among
search techniques. Program representation
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 an operand,
making mathematical expressions easy to evolve and evaluate. Thus traditionally
GP favors the use of programming languages that naturally embody tree
structures. 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.]. The commercial GP software Discipulus uses automatic induction of
binary machine code to achieve better performance. µGP uses directed
multigraphs to generate programs that fully exploit the syntax of a given
assembly language Most non-tree representations have
structurally noneffective code. Such non-coding genes may seem to be useless,
because they have no effect on the performance of any one individual.
However, experiments seem to show faster convergence when using program
representations — such as linear genetic programming and Cartesian
genetic programming — that allow such non-coding genes, compared to tree-based
program representations that do not have any non-coding genes.
Genetic operators The main operators used in evolutionary
algorithms such as GP are crossover and mutation.
=Crossover=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 different from their
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. To
maintain integrity, operations must be fail-safe or the type of information the
node holds must be taken into account. For example, mutation must be aware of
binary operation nodes, or the operator must be able to handle missing values.
Other approaches The basic ideas of genetic programming
have been modified and extended in a variety of ways:
Extended Compact Genetic Programming Embedded Cartesian Genetic Programming
Probabilistic Incremental Program Evolution
Strongly Typed Genetic Programming Meta-Genetic Programming
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. 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.
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. For general problem classes there may be
no way to show that Meta GP will reliably produce results more
efficiently than a created algorithm other than exhaustion.
See also Bio-inspired computing
Gene expression programming Genetic representation
Grammatical evolution Fitness approximation
Inductive programming Linear genetic programming
Multi expression programming Propagation of schema
References and notes External links
Riccardo Poli, William B. Langdon,Nicholas F. McPhee, John R.
Koza, “A Field Guide to Genetic Programming”
Aymen S Saket & Mark C Sinclair The Hitch-Hiker’s Guide to Evolutionary
Computation GP bibliography