Differential Evolution

An Introduction to Differential Evolution

Kelly Fleetwood

Synopsis

• Introduction
• Basic Algorithm
• Example
• Performance
• Applications

The Basics of Differential Evolution

• Stochastic, population-based optimisation algorithm
• Introduced by Storn and Price in 1996
• Developed to optimise real parameter, real valued functions
• General problem formulation is:
For anobjective function f : X ⊆ RD → R where the feasible region
X = ∅, the minimisation problem is to find
x∗ ∈ X such that f (x∗ ) ≤ f (x) ∀x ∈ X
where:
f (x∗ ) = −∞

Why use Differential Evolution?

• Global optimisation is necessary in fields such as engineering, statistics
and finance
• But many practical problems have objective functions that are nondifferentiable, non-continuous, non-linear,noisy, flat, multi-dimensional
or have many local minima, constraints or stochasticity
• Such problems are difficult if not impossible to solve analytically
• DE can be used to find approximate solutions to such problems

Evolutionary Algorithms

• DE is an Evolutionary Algorithm
• This class also includes Genetic Algorithms, Evolutionary Strategies and
Evolutionary ProgrammingInitialisation

Mutation

Recombination

Selection

Figure 1: General Evolutionary Algorithm Procedure

Notation

• Suppose we want to optimise a function with D real parameters
• We must select the size of the population N (it must be at least 4)
• The parameter vectors have the form:
xi,G = [x1,i,G , x2,i,G , . . . xD,i,G ] i = 1, 2, . . . , N.
where G is the generation number.Initialisation

Initialisation

Mutation

Recombination

Selection

• Define upper and lower bounds for each parameter:
xL ≤ xj,i,1 ≤ xU
j
j
• Randomly select the initial parameter values uniformly on the intervals
[xL , xU ]
j
j

Mutation

Initialisation

Mutation

Recombination

Selection

• Each of the N parameter vectors undergoes mutation, recombination and
selection• Mutation expands the search space
• For a given parameter vector xi,G randomly select three vectors xr1,G ,
xr2,G and xr3,G such that the indices i, r1, r2 and r3 are distinct

Mutation

Initialisation

Mutation

Recombination

Selection

• Add the weighted difference of two of the vectors to the third
vi,G+1 = xr1,G + F (xr2,G − xr3,G )
• The mutation factor F is a constant from[0, 2]
• vi,G+1 is called the donor vector

Recombination

Initialisation

Mutation

Recombination

Selection

• Recombination incorporates successful solutions from the previous generation
• The trial vector ui,G+1 is developed from the elements of the target vector,
xi,G , and the elements of the donor vector, vi,G+1
• Elements of the donor vector enter the trial vector withprobability CR

Recombination

Initialisation

uj,i,G+1

Mutation

Recombination

Selection


v
j,i,G+1 if randj,i ≤ CR or j = Irand
=
 xj,i,G
if randj,i > CR and j = Irand
i = 1, 2, . . . , N ; j = 1, 2, . . . , D

• randj,i ∼ U [0, 1], Irand is a random integer from [1, 2, ..., D]
• Irand ensures that vi,G+1 = xi,G

Selection

Initialisation

MutationRecombination

Selection

• The target vector xi,G is compared with the trial vector vi,G+1 and the
one with the lowest function value is admitted to the next generation

u
i,G+1 if f (ui,G+1 ) ≤ f (xi,G )
xi,G+1 =
i = 1, 2, . . . , N
 xi,G
otherwise
• Mutation, recombination and selection continue until some stopping criterion is reached

Example: Ackley’s function

• DE with N = 10, F= 0.5 and CR = 0.1
• Ackley’s function
f (x1 , x2 ) = 20+e−20exp −0.2

12
(x1 + x2 ) −exp
2
n

1
(cos(2πx1 ) + cos(2πx2 ))
n

• Find x∗ ∈ [−5, 5] such that f (x∗ ) ≤ f (x) ∀x ∈ [−5, 5]
• f (x∗ ) = 0; x∗ = (0, 0)

Example: Ackley’s function

15

f(x)

10

5

0

−5
5

0

x

2

−5

−5

−4

−3

−2

−1

x1

0

1

2

3

4

5

Example:...