~~NOTOC~~
====== Differential Evolution ======
----
The Differential Evolution algorithm can be used instead of [[algorithms:simann]] in the optimization part of //potfit//. Enabling it with the ''evo'' compilation switch will create a binary that first uses Differential Evolution and then subsequently the [[algorithms:lsq]] to optimize the potential.

Please note that this algorithm is not tested as well as the [[algorithms:simann]] and may perform very poor with tabulated potentials. It however works well with analytic potentials because of the predefined range of the potential parameters.

=====  How does it work?  =====

Differential Evolution (DE) is a genetic algorithm, it works with populations and generations.

At the beginning, $NP$ D-dimensional vectors $\boldsymbol x_{i,G=0}\;,i=1,2,\ldots,NP$ (which each holds all the parameters for the potential) are created as the initial population. The index $G$ indicates the number of the generation. For //potfit// this means that we have to generate $NP-1$ potentials in addition to the starting potential given by the user. The initialization of the population is done with normally distributed random numbers being added to the starting potential.

A DE step consists of several substeps, called mutation, crossover and selection. 

===  Mutation  ===

For each potential $\boldsymbol x_{i,G}\;i=1,2,\ldots,NP$ a mutant vector $\boldsymbol v$ is generated according to

$$\boldsymbol v_{i,G+1}=\boldsymbol x_{r_1,G}+F\left(\boldsymbol x_{r_2,G}-\boldsymbol x_{r_3,G}\right)$$

with random indexes $r_1,r_2,r_3 \in {1,2,\ldots,NP}$, integer, mutually different and $F>0$. $F$ is a real and constant factor $\in[0,2]$ which controls the amplification of the differential variation $\left(\boldsymbol x_{r_2,G}-\boldsymbol x_{r_3,G}\right)$.

===  Crossover  ===

To achieve a greater diversity of the new vectors, a new trial vector $\boldsymbol u$ is created according to

$$u_{i,G+1,j}= \begin{cases}
v_{i,G+1,j} \quad \text{if} \quad \text{rand}_j[0,1] \leq CR \;\text{or}\; j=\text{rand}(i)\\
x_{i,G,j} \;\;\quad \text{if} \quad \text{rand}_j[0,1] > CR \;\text{or}\; j\neq\text{rand}(i)
\end{cases},\;j=1,2,\ldots,D.
$$

Here $\text{rand}_j$ is the $j$th evaluation of a uniform random number generator and $CR$ is the crossover constant $\in[0,1]$. $\text{rand}(i)$ is a randomly chosen index
$\in 1,2,\ldots,D$ which ensures that $\boldsymbol u_{i,G+1}$ gets at least one parameter from $\boldsymbol v_{i,G+1}$.

===  Selection  ===

To decide wheter or not the trial vector $\boldsymbol u_{i,G+1}$ should become a member of generation $G+1$, it is compared to the target vector $\boldsymbol x_{i,G}$. If the new vector yields a smaller target function than $\boldsymbol x_{i,G}$, then $\boldsymbol u_{i,G+1}$ replaces $\boldsymbol x_{i,G}$, otherwise $\boldsymbol x_{i,G}$ is retained.

For more information on DE, please take a look at the references in the DE section of [[:references#Differential_Evolution|Quotes]].