Biomedical Engineering Reference
In-Depth Information
designed
[20]
. Hicklin
[21]
, and Fujiki and
Dickinson
[22]
wrote precursor systems for par-
ticular applications using the standard pro-
gramming language LISP before Koza in 1989
finally documented a method that both used a
universal language and was applied to many
different problems
[23]
. GP came into its own
with the publication of John Koza's topic in
1992
[15]
. It is his achievement to have
recognized the power and generality of this
method and to document, with numerous
examples, how the approach can be used in
different application areas. In the introduction
to his topic he wrote: “In particular, I describe
a single, unified, domain-independent approach
to the problem of program induction—namely
genetic programming.”
Now that we have reviewed the gradual
development of ideas, it is time to discuss the
principles of GP. GP works with a population of
computer programs that are executed or inter-
preted in order to judge their behavior. Usually,
fitness measurements sample the behavioral
space of a program to determine the degree to
which the outcome of the behavior of a program
individual is what it is intended for. For instance,
the deviation between the quantitative output of
a program and its target value (defined through
an error function) could be used to judge the
behavior of the program. This is a straightfor-
ward procedure if the function of the target pro-
gram can be clearly defined. Results may also be
defined as side effects of a program, such as
consequences of the physical behavior of a robot
controlled by a genetically developed program.
Sometimes an explicit fitness measure is missing
altogether—for instance, in a game situation—
and the results of the game (winning or losing)
are taken to be sufficient scoring for the pro-
gram's strategy. Again, very much following the
original intuition of Holland, various programs
are applied to the same problem and their
performances relative to each other are used to
determine which programs are to be conserved
for future generations and which are to be
discarded.
The outcomes of fitness evaluation are used
to select programs. There are several different
methods for selection, both deterministic and
stochastic. Selection determines (a) which pro-
grams are allowed to survive (overproduction
selection) and (b) which programs are allowed
to reproduce (mating selection). Once a set of
programs has been selected for further repro-
duction, the following operators are applied:
• reproduction,
• mutation,
• crossover.
Reproduction
simply copies an individual to
an offspring population (the next generation),
mutation
varies the structure of an individual
under control of a random-number generator,
and
crossover
or
recombination
mixes the struc-
tures of two (or more) programs to generate
one or more new programs for the offspring
population. Additional variation operators are
applied in different applications. Most of these
contain knowledge in the form of heuristic
search recipes that are adapted to the problem
domain.
The material under evolution is, as we said,
computer code. However, the representation of
this code and the implementation of variation
operators is important in order to avoid the brit-
tleness of the code.
4
The two most popular rep-
resentations for computer programs under
evolution nowadays are expression trees of
functional programming languages and (linear)
sequences of instructions from imperative pro-
gramming languages
[24]
.
Figure 17.2
shows
how these two representations can be subjected
to a crossover or recombination operation. There
are many other representations for GP, notably
4
The
brittleness
of a computer code refers to the fact that the code can be easily broken, even with the slightest
(possibly random) variation, with the result that it does not work at all.
