Ceng 713, Evolutionary Computation, Lecture Notes

Evolution Strategies

Introduction

Developed in Germany late 60's and 70's (Rechenberg, 1965 & Schwefel, 1968)

Applicable to floating point optimization problems. Fast and gives good results.

Basically depends on normally distributed mutations on a solution vector.

General form:
Start with an individual
Get a normally distributed random vector
A scalar value for adjusting magnitude σ
A fitness function
Modify individual:
Adapt σ

Keeping a constant σ : Either slow steps in convergence or long steps, not to converge.

Adapting σ : Depending on the number of successful mutations in last period of steps.
1/5 rule:

if more than 1/5 of the steps are success, increase σ .

else decrease σ .

Schwefel (1995):

if t mod n = 0 determine s, number of successful mutations during steps t-10n to t-1.

Possible extensions:

Using a population size μ>1. Generate/mutate/select
over (μ+λ)

Select two parents/crossover/mutate truncation select over (μ+1) : steady state ES.

Contemporary ES

Different population size and selection strategies like (μ,λ), (μ+λ), (μ+1)

Not only mutation vectors but also scaling and rotation vectors incorporated. Each mutation:

Start with an initial Z ~ N(0,In)

Scale with a vector S(σ)

Rotate along each axis R(ω1),R(ω2),...,R(ωn)

Add to solution vector

Scaling and rotation parameters are adapted along with the solution vector.

2005-10-11T11:25:00