Chapter 2
Evolutionary Methods and E volutionary
Computation
Science is – and how else can I say it – most fun when it plays
with interesting ideas, examines their implications, and recog-
nizes that old information might be explained in surprisingly
new ways. Evolutionary theory is now enjoying this uncom-
mon vigor (Stephen Jay Gould [44]).
2.1 What is evolutionary computation?
EAs (evolutionary algorithms) a nd EC (evolutionary computation) are
methods that apply the mechanism of biological evolution to problems in
computer science or in engineering. EAs consider the adaptation process of
organisms to their environments as a learning process. Organisms evolve over a
long period of time by repeating the evolution process whereby species that do
not adapt to the environment become extinct and species that adapt thrive.
This can be applied to practical problems by replacing “environment” with
“problem” or “information that was learned” and “fitness” with “goodness of
the solution.”
The most important o perators in EAs are selec tion and genetic operations.
Evolution of individuals does not happ e n if individuals that adapt better to
their environments are surviving but nothing else is happening. Mutation and
crossover by sexua l r e production result in the generation o f a diverse range of
individuals, which in turn promotes evolution. Selection is a procedure where
good individuals are selected fro m a population. Species that adapt better to
the environment are more likely to survive in na ture. T he sele c tion procedure
artificially carries out this process.
The typical examples of EAs are genetic algorithms (GAs) and genetic
programming (GP). They are the basic mechanisms for simulating complex
systems. The next sections describe these methods in detail with practical
applications.
13
14 Agent-Based Modeling and Simulation with Swarm
2.2 What are genetic algorithms?
GAs have the following characteristics:
• Candidate s olutions are represented by sequences of characters
• Mutation and crossover are us e d to generate solutions of the next gen-
eration
Elements that constitute GAs include data representation (genotype or
phenotype), selection, crossover, mutation, and alternation of generation. The
performance of a search is s ignificantly influenced by how these elements are
implemented, as discussed below.
2.2.1 Data r epresentation
The data structure in GAs is either genotype (GTYPE) or phenotype
(PTYPE). The GTYPE structure corresponds to chromosomes of organisms
(see Fig. 2.1), and is a sequence representing a candidate solution (for example,
a bit sequence having a fixed length). This structure is subject to genetic
operations such as crossover and mutation. The implementer can design how to
convert candida te solutions into sequences. For instance, a GTYPE structure
can be obtained by conversion of a candidate solution into a sequence of
integers that is then concatena ted. On the other hand, PTYPE structures
correspond to organisms, and are candidate solutions obtained by interpreting
GTYPE structures. The fitness values of candidate solutions are calculated
for PTYPE structures.
2.2.2 Selection
The GA is based on the concept of Darwinian evolution, where individuals
who adapt better to their e nvironments leave more offspring, while less fit
individuals are eliminated. Individuals who adapt to their environments a re
candidate solutions that are better solutions to a problem, and the measure
is the fitness of PTYPE structures.
The following selection methods have been proposed. In particular, the
tournament selection is frequently used because sca ling is not necessary. In all
methods, individuals who have higher fitness are more likely to be selected.
• Roulette selection
Roulette selection selects individuals w ith a probability in proportion to
their fitness. This is the most general method in EAs; however, proce-
dures such as scaling are necessary to perform searches efficiently.
Evolutionary Methods and Evolutionary Computation 15
FIGURE 2.1: GTYPE and PTYPE.
16 Agent-Based Modeling and Simulation with Swarm
• Tournament selection
Tournament selection is w idely used in EAs. The selection rate in
roulette selection is determined by the absolute value of fitness. How-
ever, the selection pressure may become too high or too low with roulette
selection in problems where the hierarchy of fitness is important but the
absolute value is not. Tourna ment selection uses only the hierarchy of
fitness; therefore the ab ove problem does not occur. The computational
cost of tournament selection is high beca use many individuals are se-
lected and fitness values are compared for the number of tournaments.
• Truncate selection
Individuals are sorted based on fitness and the top P
s
× M individuals
(P
s
is the selection rate) are selected in truncate selection. The selection
pressure is very high; therefore this method is not used in standard GP,
but is often used in the estimation of distribution algorithm (EDA),
which is an expansion o f the GA. The computation cost of this method
besides the cost for sorting is ver y low.
Selection significantly influences the diversity of the population and the
sp e e d of convergence; therefore the choice of the selection algorithm and its
parameters is very impor tant. For instance, good solutions are often observed
with a small number of fitness evaluations by using tournament selection be-
cause the selection pressure is very high with a large tournament size. However,
the calculations are more likely to quickly converge to and be trappe d in an
inappropriate local solution.
A different strategy is elitist selection (good individuals are always included
in the next ge neration). The fitness of the bes t individual never decreases in
this strategy with increasing number of genera tions if the environment against
which fitness is measured does not change. However, using elitist selection too
early in a search may result in a loc al solution, or premature convergence.
2.2.3 Genetic operations
When reproduction occurs, the o perators shown in Fig. 2.2 are applied to
the selected GTYPE to generate a new GTYPE for the subsequent generation.
These ope rators are called GA operators. To keep the explanation simple,
we express the GTYPE as a one-dimensional array here. Each operator is
analogous to the recombination or mutation of a gene in a biological organism.
Generally, the frequency with which these operators are a pplied, as well as the
sites at which they are applied, are determined r andomly.
Crossover is an analo gy of sexual reproduction where new offspring are gen-
erated by combining two parent individuals. There are a number of crossover
methods based on the level of granularity in separating each individual, for
example, the one-point crossover and the uniform crossover.
The cros sover shown in Fig. 2.2 has one crossover po int, so it is called a
Evolutionary Methods and Evolutionary Computation 17
FIGURE 2.2: GA operators.
one-point crossover. Following are some methods for performing the crossover
operation.
1. One-point crossover
2. Multi-p oint crossover (n-point crossover )
3. Uniform crossover
We have already explained the one-point crossover operation (Fig. 2.3(a)).
The n-p oint crossover op e ration has n crossover points, so if n = 1, this is
equivalent to the one-point crossover op e ration. With this crossover method,
genes are carried over from one parent alternately between crossover points.
A case in which n = 3 is shown in Fig. 2.3(b). Two-point crossovers, in which
n = 2, are often used. Uniform crossovers are a crossover method in which
any desired number of crossover p oints can be identified, so these are realized
using a mask for a bit string co nsisting of 0, 1. First, let’s randomly generate
a character string of 0s and 1s for this mask. The crossover is carried out
as follows. Suppose the two selected parents are designated as Parent A and
Parent B, and the offspring to be created are designated as Child A and Child
B. At this point, the genes for offspring Child A are carried over from Parent
A when the corresponding mask is 1, and are carried over from Parent B
when the mask is 0. Conversely, the genes for offspring Child B are c arried
over from Parent A when the corresponding mask is 0, and are carried over
from Parent B when the mask is 1 (Fig. 2.3(c)).
Mutation in organisms is considered to happen by mutation of nucleotide
bases in genes. The GA mimics mutation in organisms by changing the value of
a g e ne location (for example, changing 0 to 1 or 1 to 0). Mutation corre sp onds
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.