Biomedical Engineering Reference
In-Depth Information
those that make use of developmental or genera-
tive processes that grow programs; see, for
instance, Refs.
25
and
26.
Once programs have been generated, they
are interpreted or compiled to produce behav-
ior, which is subsequently measured in terms
of its fitness. In this way, fitness advantages of
individual programs are exploited in a popula-
tion to lead to better solutions. In GP, as well
as in other evolutionary algorithms, differential
selection can be realized in many different
ways.
The simplest approach is a generational
selection scheme called
fitness-proportional
or
roulette-wheel selection
. The fitness of all indi-
viduals in the population is summed up. The
itness
f
i
of each individual
i
is then normalized
by the sum of all fitness values found, and this
normalized value determines the probability
p
i
of the individual
i
of being selected for repro-
duction/mutation/crossover. Thus,
p
i
=
f
i
/
∑
j
f
j
.
Based on the stochasticity of random events,
fitness proportional selection also allows weak
individuals to succeed in reproduction some of
the time.
Another selection method is called
tourna-
ment selection
. A subset of individuals of the
population is drawn randomly, and those indi-
viduals are compared to each other in terms of
fitness. The individuals with higher fitness are
allowed to replace (directly as in reproduction,
or with a variation as in mutation and crossover)
the individuals with lower fitness. Normally,
tournament selection is done with a minimum
number of
k
=
4 individuals, which carries the
lowest selection pressure. Larger tournaments,
however, have been used in the literature, up to
the extreme of holding tournaments among the
whole population, at which point the selection
scheme is called
truncation selection
.
Ranking selection
is another selection scheme
introduced to address some weaknesses of fit-
ness proportional selection. Each individual is
assigned a rank in the population, and selection
proceeds by selecting either by a linearly or an
exponentially associated probability based on
the rank of an individual. A detailed compari-
son of different selection schemes is given in
Ref.
27
.
The entire process of selection can be seen in
close analogy to the way humans breed animals.
To obtain animals with the desired characteris-
tics, the breeder has to select those individuals
from the population that carry the targeted traits
to a higher degree than others.
5
All selection schemes rely on a sufficiently
accurate determination of fitness to work
properly. Therefore, one of the most important
ingredients in GP is the definition of a fitness
measure to determine the appropriateness of
a program individual's behavior. Sometimes
the fitness measure has to be iteratively
improved in order for the evolved solutions to
actually perform the function they were
intended for.
Fitness calculation is actually one of the areas
where GP and other evolutionary algorithms
differ. GP has to judge the behavior of a pro-
gram, a structure that determines the behavior
of a computer under different inputs, i.e., an
active entity. This executed program has to pro-
duce outputs that adhere as closely as possible
to a prescribed behavior. Thus, while a GA (or
another optimization technique) is used to opti-
mize a particular instance of an optimization
problem, GP has to find behavior in a larger
search space, providing the correct behavior
under a multitude of input/output pairs. The
situation can be depicted by considering the dif-
ference between (1) optimizing a function, i.e.,
finding the minimum or maximum of a func-
tion, as in finding the center (
x
=
y
=
0) as the
function maximum in
Figure 17.3
in the GA task
and (2) constructing the function whose samples
are provided by the data points in
Figure 17.4
in
a typical GP task.
5
Darwin's original theory of evolution was inspired by humans breeding animals, especially pigeons and cattle.
