# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python [default]
#     language: python
#     name: python3
# ---

# + [markdown] tags=["meta", "draft"]
# # Differential Evolution

# + [markdown] tags=["hide"]
# **TODO**
# * Livre metaheuristiques p.165
# * [Scipy's implementation](https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.differential_evolution.html#scipy.optimize.differential_evolution)
# * https://en.wikipedia.org/wiki/Differential_evolution
# * http://www.scholarpedia.org/article/Metaheuristic_Optimization#Differential_Evolution
# * [Practical advises](http://www1.icsi.berkeley.edu/~storn/code.html#prac)
# -

# 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. 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](http://www.scholarpedia.org/article/Metaheuristic_Optimization#Differential_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**

# + tags=["hide"]
# import python packages here...

StarcoderdataJupyterScriptsDedupFiltered