Differential Evolution

Author

Enrico Schumann¹

Keywords

Differential Evolution

Review Status

Reviewed; revised 2009-02-02.

The algorithm

A more recent contribution to population-based methods is Differential Evolution (DE) [1] which was developed for the optimisation of continuous objective functions. The pseudocode below describes the algorithm. Initially, the procedure randomly generates and evaluates $n_P$ solutions, stored in real-valued vectors of length $d$. In each generation, the algorithm creates a candidate solution for each existing solution $P^{(k)}_{\cdot ,i}$ (ie, for each current element of the population) through differential mutation (Line 7) and uniform crossover (Lines 8-10). Differential mutation generates a new solution by multiplying the difference between two randomly selected solution vectors by a scale factor $\mathtt{F}$, and adding the result to a third vector. Then an element-wise crossover takes place with probability $\mathtt{CR}$ between this ‘auxiliary’ solution $P^{(v)}_{\cdot , i}$ and the existing solution $P^{(k)}_{\cdot ,i}$. The resulting new candidate solution is denoted $P^{(u)}_{\cdot ,i}$: if it is better than $P^{(k)}_{\cdot ,i}$, it replaces it; if not, the old solution is kept. The algorithm terminates after a predefined number of generations.

(1)

\begin{eqnarray} \newcommand{\re}[1]{\scriptscriptstyle \mathrm{#1}} \nonumber {\scriptscriptstyle \phantom{0}1:\quad}&& \text{Initialise parameters } n_{\re{P}}, n_{\re{G}}, \mathtt{F} \text{ and } \mathtt{CR}\\ \nonumber {\scriptscriptstyle 2:\quad}&& \text{Initialise population } P^{(1)}_{j,i}, j=1,\ldots,d, i=1,\ldots,n_{\re{P}}\\ \nonumber {\scriptscriptstyle 3:\quad}&& \text{for } k = 1 \text{ to } n_{\re{G}}\\ \nonumber {\scriptscriptstyle 4:\quad}&& \quad P^{(0)} = P^{(1)}\\ \nonumber {\scriptscriptstyle 5:\quad}&& \quad \text{for } i = 1 \text{ to } n_{\re{P}}\\ \nonumber {\scriptscriptstyle 6:\quad}&& \quad \text{Generate } r_1, r_2, r_3 \in \{1,\ldots,n_{\re{P}}\}, r_1 \neq r_2 \neq r_3 \neq i\\ \nonumber {\scriptscriptstyle 7:\quad}&& \quad \text{Compute } P^{(v)}_{\cdot , i} = P^{(0)}_{\cdot , r_1} + \mathtt{F} \times (P^{(0)}_{\cdot , r_2} - P^{(0)}_{\cdot , r_3})\\ \nonumber {\scriptscriptstyle 8:\quad}&& \quad \quad \text{for } j = 1 \text{ to } d\\ \nonumber {\scriptscriptstyle 9:\quad}&& \quad \quad \quad \text{if } {u<\mathtt{CR}} \text{ then } P^{(u)}_{j,i} = P^{(v)}_{j,i} \text{ else } P^{(u)}_{j,i} = P^{(0)}_{j,i}\\ \nonumber {\scriptscriptstyle 10:\quad}&& \quad \quad \text{ end for } \\ \nonumber {\scriptscriptstyle 11:\quad}&& \quad \quad \text{if } {f(P^{(u)}_{\cdot ,i}) < f(P^{(0)}_{\cdot ,i})} \text{ then } P^{(1)}_{\cdot ,i} = P^{(u)}_{\cdot ,i} \text{ else } P^{(1)}_{\cdot ,i} = P^{(0)}_{\cdot ,i}\\ \nonumber {\scriptscriptstyle 12:\quad}&& \quad \text{end for } \\ \nonumber {\scriptscriptstyle 13:\quad}&& \text{end for} \end{eqnarray}

Internal Links

Concepts

…

Tutorials

…

Tips

…

Related Articles

…

External links

References

1. Storn, R. and K. Price (1997). Differential evolution - A simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization 11, 341-359.

Weblinks

Differential Evolution homepage by R. Storn and K. Price The R-package NMOF contains an implementation of Differential Evolution (the function DEopt). The package is available from R-Forge .

1. Marianna Lyra provided helpful comments.