Differential Evolution

Differential Evolution (DE) was developed by R. Storn and K. Price in 1995 [Storn95] [Storn97].

This algorithm has been made for continuous problems.

• [Storn95]: Storn, R., & Price, K. (1995). Differential evolution - a simple and efficient adaptive scheme for global optimization over continuous spaces. Technical Report TR95-012, International Computer Science Institute, Berkeley, California. PDF document.
• [Storn97]: Storn, R., & Price, K. (1997). Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces. Journal of global optimization, 11(4), 341-359.

The Differential Evolution (DE) algorithm

Simplified notations

FOREACH generation

$\quad$ FOREACH individual $i$ (a solution vector) of the population (a set)

$\quad\quad$ 1. MUTATION:

$\quad\quad\quad$ 1.1 Randomly choose 3 different individuals $\boldsymbol{x}_{r1}$, $\boldsymbol{x}_{r2}$ and $\boldsymbol{x}_{r3}$

$\quad\quad\quad\quad$ $\boldsymbol{x}_{r2}$ and $\boldsymbol{x}_{r3}$ are used to automatically define the direction and the amplitude of the mutation

$\quad\quad\quad\quad$ (i.e. the search amplitude and direction)

$\quad\quad\quad$ 1.2 Compute mutant $\boldsymbol{v}_{i} \leftarrow \boldsymbol{x}_{r1} + F . (\boldsymbol{x}_{r2} - \boldsymbol{x}_{r3})$

$\quad\quad$ 2. CROSSOVER:

$\quad\quad\quad$ Compute the "test" individual $\boldsymbol{u}_{i}$ randomly taking each of its (vector) components in either $\boldsymbol{x}_i$ or $\boldsymbol{v}_i$

$\quad\quad$ 3. SELECTION:

$\quad\quad\quad$ The test individual $\boldsymbol{u}_{i}$ replace $\boldsymbol{x}_{i}$ in the next generation if it has a better score.

Differential evolution consists of three main steps:

1. mutation
2. crossover
3. selection

The following sections provides more details about those three steps.

Mutation

Crossover

Selection

Notations:

• $D$ : the dimension of input vectors, $D \in \mathbb{N}^*_+$.
• $t$ : the current iteration index (or generation index), $t \in \mathbb{N}^*_+$.
• $T$ : the total number of iteration (or generation), $T \in \mathbb{N}^*_+$.
• $N$ : the size of the population, $N > 3$.
• $F$ : the differential weight. In principle, $F \in [0,2]$, but in practice, a scheme with $F \in [0,1]$ is more efficient and stable (scholarpedia).
• $Cr$ : the crossover probability parameter, $Cr \in [0,1]$.

---

Algorithm's parameters: $N$, $Cr$ and $F$

---

Input:

• An initial population $(\boldsymbol{x}_{1,1}, \boldsymbol{x}_{2,1}, \dots, \boldsymbol{x}_{N,1})$ with $\boldsymbol{x}_{0,i} \in \mathbb{R}^D$

---

for all generation $t = 1, \dots, T$ do

$\quad$ for all individuals $i = 1, \dots, N$ do

$\quad\quad$ 1. Mutation:

$\quad\quad\quad$ Randomly choose 3 different individuals $\boldsymbol{x}_{r1,t}$, $\boldsymbol{x}_{r2,t}$ and $\boldsymbol{x}_{r3,t}$ in the population

$\quad\quad\quad$ Make a donor vector $\boldsymbol{v}_{i,t}$ as the following

$\quad\quad\quad \boldsymbol{v}_{i,t} \leftarrow \boldsymbol{x}_{r1,t} + F (\boldsymbol{x}_{r2,t} - \boldsymbol{x}_{r3,t})$

$\quad\quad$ 2. Crossover: make a test individual $\boldsymbol{u}_{i,t}$ from $\boldsymbol{x}_{i,t}$ and $\boldsymbol{v}_{i,t}$

$\quad\quad\quad$ Randomly choose a dimension index $d_{r,i}$.

$\quad\quad\quad$ for all dimension $d = 1, \dots, D$ do

$$ u_{d,i,t} \leftarrow \left\{ \begin{align} v_{d,i,t} \quad & \text{ if } \mathcal{B}(Cr) = 1 \text{ or if } d = d_{r,i}\\ x_{d,i,t} \quad & \text{ otherwise.} \end{align} \right. $$

$\quad\quad\quad\quad$ where $\mathcal{B}(Cr)$ is a Bernoulli random variable of parameter $Cr$

$\quad\quad\quad\quad$ and where $u_{d,i,t}$, $v_{d,i,t}$ and $x_{d,i,t}$ are respectively the $d^{th}$ component of $\boldsymbol{u}_{i,t}$, $\boldsymbol{v}_{i,t}$ and $\boldsymbol{x}_{i,t}$

$\quad\quad$ 3. Selection:

$\quad\quad\quad$ If $f(\boldsymbol{u}_{i,t}) < f(\boldsymbol{x}_{i,t})$

$\quad\quad\quad\quad \boldsymbol{x}_{i,t+1} \leftarrow \boldsymbol{u}_{i,t}$

$\quad\quad\quad$ Else

$\quad\quad\quad\quad \boldsymbol{x}_{i,t+1} \leftarrow \boldsymbol{x}_{i,t}$

$\quad$ end for

end for