(from Christian Jacob's 'Softcomputing'-script)
Evolution Strategy (ES) was developed at Berlin Technical University by Ingo Rechenberg (Rechenberg 1973) and Hans Peter Schwefel (Schwefel 1981). The ES-algorithms consider the indivual i.e. its phenotype to be the object to be ompitmized.
The characteristical 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 oposing 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 optimazation 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 (Schwefel 1977), Evolution Strategy was introduced as a method to solve optimazation problems with computers.
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 (see mutation ).
The indiviudals data-structure is usually referred to as ES-Chromosome. Formaly a population P of n indiviudals 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-paramters op and strategy-parameters sp:
op = (o1,o2,...,om-1,om)
sp = (s1,s2,...,sm-1,sm)
Similar to the biolocial principle, that descendants resamble 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 startegy-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 adaption 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 usally refered to as strategy-parameters
adaption 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.
Similar to effects of gene-recombiniation in nature, several recombination operators are defined in Evolution Stategy. 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
(selction 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 indiviudals (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.)
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 indiviudal '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 generations parent otherwise the parent stays the same, i.e. its parameters are reset to the state before mutation.