Differential Evolution


The Differential Evolution algorithm can be used instead of 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 lsq to optimize the potential.

Please note that this algorithm is not tested as well as the 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 Quotes.