Evolution Strategy (ES) has
been developed at Berlin Technical University by Ingo Rechenberg
and Hans Peter Schwefel [1-9] .
The ES-algorithms consider the individuals i.e. its phenotype to be the object
to be optimized.
The characteristic data of
the individual are the parameters to be optimized in a
evolution-based process. These parameters are arranged in vectors of real
numbers on whom operators for recombination
(cross-over) and mutation are defined.
In the beginning the
concept of Evolution Strategy was not developed as an algorithm to be used with
computers but merely as method to find optimal parameter settings in laboratory
experiments. Evolution Strategy is not based on detailed simulation of the
methods found with natural evolution. Which can already be
concluded by looking at the opposing terms: evolution and strategy. In
biological evolution there is no strategy, oriented towards a specific goal to
be achieved or a special result to be found. Evolutions Strategy merely
concentrates on translating the fundamental mechanisms of biological evolution
for technical optimization problems.
The key experiment of
Evolution Strategy was the evolution of a joint plate with minimal
flow-resistance by Rechenberg in 1964. Later on,
especially by the works of H.P.Schwefel, Evolution
Strategy was introduced as a method to solve optimization problems with
computers.
data structure - ES-Chromosome -
genotype structure
In the
beginning the parameters to be optimized where represented by integer
variables.
Nowadays in computer implementations the parameters are represented by real
numbers. This vector of real numbers is referred to as object-parameters .
Together with another vector of real numbers, the strategy-parameters the
data-structure for single individual is defined. While the object-parameters
contain the variables to be optimized the strategy parameters control the
mutation of the object-parameters.
The individuals
data-structure is usually referred to as ES-Chromosome. Formally a
population P of n individuals could be described as follows:
P = (c)=(c1,c2,...,cn-1,cn)
where the i.th ES-chromosome ci is defined
as:
ci = (op,sp)
with object-parameters op and strategy-parameters sp:
op = (o1,o2,...,om-1,om)
sp = (s1,s2,...,sm-1,sm)
Mutation -
genotype-variation
Similar to the biolocial principle, that descendants resemble their
parents in a certain way and small changes from one generation to another are
more often found than big changes, the mutation operator is defined as component
wise addition of normal distributed random numbers . Both parts of the ES-chromosome:
the object-parameters and the strategy-parameters are mutated.
object-parameters mutation
A mutants
object-parameters vector is calculated as follows:
opmut = op+N0(sp)
opmut = (o1+N0(s1),
o2+N0(s2), ..., om-1+N0(sm-1),
om+N0(sm))
where N0(si)
is the Gaussian distribution of mean-value 0 and standard deviation si.
strategy-parameters mutation
The adaptation of the
step-size of mutation is done by adapting the standard deviation si. This may be done (for example) as follows:
spmut = (s1*A1, s2*A2,
..., sm-1*Am-1, sm*Am)
where Ai is
randomly chosen from alpha or 1/alpha depending on the value of
equal-distributed random variable E out of [0,1]:
Ai = alpha if E < 0.5
Ai = 1/alpha if E >= 0.5
alpha is usually referred to as
strategy-parameters adaptation value. Rechenberg
recommends a value of 1.3 for alpha if the number of parameters m is less than
100 otherwise a smaller value for alpha should be chosen.
Recombination
(cross-over)
Similar to effects of
gene-recombination in nature, several recombination operators are defined in
Evolution Strategy. The discrete recombination (see below) resembles the
uniform cross-over of Genetic Algorithms (GA).
Discrete Recombination
For two 'chromosomes' c1=(opc1,spc1) and c2=(opc2,spc2)
a discrete recombination operator rdiscrete
is defined as follows:
rdiscrete(c1,c2) = c = (op,sp)
with opi = {opc1,i | opc2,i}
and spi = {spc1,i | spc2,i}
where z = { x | y } denotes that z is randomly assigned a value of either x or
y
(selection probability is 50% for x and 50% for y).
Thus each component of the recombinated chromosome is with same probability from
either parent chromosome c1 or c2. (This recombination type may be extended to
the general case of n (n>2) parents: global discrete recombination.)
Intermediate
Recombination
The intermediate
recombination operator rintermediate is
mainly used to adapt the strategy parameters. The problem with this operator is
that the diversity of individuals (i.e. the diversity of object-parameters,
strategy-parameters pairs) may be reduced. This may be avoided by using further
mutation.
For two 'chromosomes' c1=(opc1,spc1)
and c2=(opc2,spc2) an intermediate
recombination operator rintermediate is
defined as follows:
rintermediate(c1,c2) = c = (op,sp)
with opi = 1/2*(opc1,i + opc2,i)
and spi = 1/2*(spc1,i + spc2,i).
Thus each component of the recombinated chromosome is the mean-value of the components
of its parents. (This recombination type may be extended to the general case of
n (n>2) parents: global intermediate recombination.)
Evolution Process
Let p be the number of
parents in generation i. And let c be the number of
children in generation i, i.e. the c descendants of
the p parents.
There are basically four different types of evolution-processes used with
Evolution Strategy: p,c,
p+c, p/r,c
and p/r+c. They differ in how the parents for
the next generation are selected and whether to use recombination or not.
The first and simplest
evolution process is a 1+1-ES used in laboratory experiments. The parent
individual 'produces' a child by mutation. The child is assigned a fitness
value. If the child proves to be better than its parent it becomes next
generation parent otherwise the parent stays the same, i.e. its parameters are
reset to the state before mutation.