<jupyter_start><jupyter_text>Differential Evolution **TODO*** Livre metaheuristiques p.165* [Scipy's implementation](https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.differential_evolution.htmlscipy.optimize.differential_evolution)* https://en.wikipedia.org/wiki/Differential_evolution* http://www.scholarpedia.org/article/Metaheuristic_OptimizationDifferential_Evolution* [Practical advises](http://www1.icsi.berkeley.edu/~storn/code.htmlprac) Differential Evolution (DE) was developed by <NAME> and <NAME> in 1995 [Storn95] [Storn97].This algorithm has been made for continuous problems.* **[Storn95]**: <NAME>., & <NAME>. (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](ftp://ftp.icsi.berkeley.edu/pub/techreports/1995/tr-95-012.pdf).* **[Storn97]**: <NAME>., & <NAME>. (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. mutation2. crossover3. selectionThe 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](http://www.scholarpedia.org/article/Metaheuristic_OptimizationDifferential_Evolution)).* $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**<jupyter_code># import python packages here...<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.19490096923725242, 'fraction_numerical': 0.02001685630004214, 'mean_word_length': 5.733333333333333, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 12, 'https://': 2, 'lorem ipsum': 0, 'www.': 3, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '380358', 'license': 'MIT', 'n_tokens_mistral': 1625, 'n_tokens_neox': 1502, 'n_words': 423, 'path': 'nb_sci_ai/ai_optimization_differential_evolution_en.ipynb', 'repo_name': 'jdhp-docs/python-notebooks', 'size': '4758'}