L'Évolution Différentielle

L'Évolution Différentielle (Differential Evolution ou DE en anglais) est une méthode d'optimisation pour des problèmes continus développée par R. Storn et K. Price en 1995 [Storn95] [Storn97].

• [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.

L'algorithme

Notation simplifiée

À chaque génération

$\quad$ Pour tous les individus $i$ de la population

$\quad\quad$ 1. MUTATION:

$\quad\quad\quad$ 1.1 On choisi 3 individus différents au hasard $\boldsymbol{x}_{r1}$, $\boldsymbol{x}_{r2}$ et $\boldsymbol{x}_{r3}$

$\quad\quad\quad\quad$ $\boldsymbol{x}_{r2}$ et $\boldsymbol{x}_{r3}$ vont permettre de déterminer automatiquement la direction et l'amplitude le la mutation

$\quad\quad\quad\quad$ (i.e. la direction de recherche et son amplitude)

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

$\quad\quad$ 2. CROISEMENT:

$\quad\quad\quad$ On crée un individu "test" $\boldsymbol{u}_{i}$ dont les composantes sont aléatoirement prises soit dans $\boldsymbol{x}_i$ soit dans $\boldsymbol{v}_i$

$\quad\quad$ 3. SELECTION:

$\quad\quad\quad$ Si cet individu test $\boldsymbol{u}_{i}$ est meilleur que $\boldsymbol{x}_{i}$, il le remplace à la génération suivante.

Notation plus formelle

Ci-dessous une écriture plus formelle de l'algorithme.

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$

---

pour chaque generation $t = 1, \dots, T$

$\quad$ pour chaque individu $i = 1, \dots, N$

$\quad\quad$ 1. MUTATION:

$\quad\quad\quad$ Choisi aléatoirement 3 individus différents $\boldsymbol{x}_{r1,t}$, $\boldsymbol{x}_{r2,t}$ et $\boldsymbol{x}_{r3,t}$ dans la population

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

$\quad\quad\quad$ où $F$ est un "facteur d'amplification" de la mutation.

$\quad\quad\quad$ L'algorithme extrait des informations de direction et de distance à produire pour sa composante aléatoire à partir des deux individus $\boldsymbol{x}_{r2,t}$ et $\boldsymbol{x}_{r3,t}$.

$\quad\quad$ 2. CROISEMENT: l'individu $\boldsymbol{x}_{i,t}$ est "mélangé" avec le mutant $\boldsymbol{v}_{i,t}$ pour former un individu test $\boldsymbol{u}_{i,t}$

$\quad\quad\quad$ Choisi aléatoirement une dimension $d_{r,i}$.

$\quad\quad\quad$ La $d^{ieme}$ composante $v_{d,i,t}$ de $\boldsymbol{v}_{i,t}$ sera toujours transmise à $\boldsymbol{u}_{i,t}$ afin de s'assurer qu'il obtienne au moins un élément de $\boldsymbol{v}_{i,t}$.

$\quad\quad\quad$ pour chaque dimension $d = 1, \dots, D$

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

$\quad\quad\quad\quad$ où $\mathcal{B}(Cr)$ est une variable aléatoire suivant une loi de Bernoulli de paramètre $Cr$

$\quad\quad\quad\quad$ et ou $u_{d,i,t}$, $v_{d,i,t}$ et $x_{d,i,t}$ sont respectivement les $d^{ieme}$ composantes de $\boldsymbol{u}_{i,t}$, $\boldsymbol{v}_{i,t}$ et $\boldsymbol{x}_{i,t}$

$\quad\quad$ 3. SELECTION:

$\quad\quad\quad$ si $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$ sinon

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

$\quad$ fin pour

fin pour