Adaptive Differential Evolution With Two Populations of New and Best Individuals

Differential evolution

The differential evolution algorithm was proposed by Storn and Price 1995. The differential evoltuion is a population-based heuristic for numerical optimization. The algorithm begins with initialization of a set of $N$ individuals $x_i=\left(x_{i,1},x_{i,2},\dots ,x_{i,D}\right),$ where $D$ is the dimensionality of the search space:

$x_i=x_{lb,j}+rand\times \left(x_{ub,j}-x_{lb,j}\right).$

Here rand is a uniformly distributed random number in $\left[0,1\right]$, $x_{lb,j}$ and $x_{ub,j}$ are the lower and upper boundaries of variable $j,j=1,\dots ,D$.

The main search operator of DE algorithm is the difference-based mutation. There are several popular mutation strategies, with current-to-pbest being one of the best:

$v_{i,j}=x_{i,j}+F\times \left(x_{pbest,j}-x_{i,j}\right)+F\times \left(x_{r1,j}-x_{r2,j}\right)$,

where $v_i$ is called mutant vector, $x_{i,j}$, is the value from current population, j-th coordinate of the i-th solution, the indexes i, r1 and r2 are different from each other, and $F$ is the scaling factor parameter, chosen from $\left[0,1\right]$, pbest is the index of one of the pb*100% individuals, sorted by fitness, and different from i, r1 and r2.

The most widely used crossover operator in DE is the binomial crossover, which is applied after mutation:

$u_{i,j}=\left\{\begin{array}{c}{v}_{i,j}ifrand<c_{r}orj=jrand\\ x_{i,j}otherwise\end{array}\right.$,

where $c_r\in \left[0,1\right]$ is the crossover rate, and $jrand$ is a randomly chosen index from $\left[1,D\right]$, required to make sure that at least one index is taken from the donor vector, $u_i$ is called trial vector.

After applying bound constraint handling method, such as midpoint-target, the fitness value of the trial vector is calculated, and the selection step is applied:

$x_i=\left\{\begin{array}{c}{u}_{i}iff\left(u_i\right)\le f\left(x_i\right)\\ x_{i}otherwise\end{array}\right.$

The greedy selection in original DE allows it to always increase the average fitness of the population or at least to keep it at the same level.

Proposed approach

As mentioned above, the main idea of LL-NADE, namely the usage of newest and top individuals, is inspired by UDE, which has shown that proper selection strategies in combination with the whole search history could be helpful in achieving better performance. The LL-NADE algorithm first initializes a population of $N_{init}$ individuals $x_i^{init}$, $i=1,\dots ,N_{init}$. After that, the individuals in this population are evaluated and sorted by their fitness values, $N_{new}$ individuals are copied to the newest population $x^{new}$, and $N_{top}$ individuals are copied to the top population $x^{top}$. The $N_{init}$ parameter should be set larger than both $N_{new}$ and $N_{top}$. The LL-NADE uses variants of the mutation strategy used in JADE, SHADE and L-SHADE, i.e. current-to-pbest mutation strategy. LL-NADE also applies adaptation of parameters proposed in the SHADE algorithm, however the archive is not used. The modified mutation strategies use individuals from both populations and work as follows:

• r-new-to-ptop/t/t: vi,j=xr1,jnew+F×xpbest,jtop-xi,jnew+F×xr2,jtop-xr3,jtop
• r-new-to-ptop/t/n: vi,j=xr1,jnew+F×xpbest,jtop-xi,jnew+F×xr2,jtop-xr3,jnew,
• r-new-to-ptop/n/t: vi,j=xr1,jnew+F×xpbest,jtop-xi,jnew+F×xr2,jnew-xr3,jtop,
• r-new-to-ptop/n/n: vi,j=xr1,jnew+F×xpbest,jtop-xi,jnew+F×xr2,jnew-xr3,jnew,
• r-new-to-pnew/n/n: vi,j=xr1,jnew+F×xpbest,jnew-xi,jnew+F×xr2,jnew-xr3,jnew,
• r-top-to-ptop/t/t: vi,j=xr1,jtop+F×xpbest,jtop-xi,jtop+F×xr2,jtop-xr3,jtop

Here r-new and r-top mean that for a target solution a random individual will be chosen from the population of newest solutions or the population of top solutions. Next, pnew and ptop mean that one of the $pb\%$ individuals, sorted by fitness, will be chosen from either newest or top population. Finally, t/n stands for using top or newest individuals in the last difference. Unlike most DE algorithms, here the target vector is chosen randomly, instead of being the i-th vector from the population.

For the $pb$ parameter the following control scheme is used: at the start the $pb$ value is set to $p{b}_{max}$, and it is decreased to $p{b}_{min}$ by the end of the search linearly as follows:

$p{b}_{g+1}=round\left(\frac{p{b}_{min}-p{b}_{max}}{NF{E}_{max}}NFE\right)+p{b}_{max}$,

where $g$ is the generation number. Note that if the $pb*N_{new}$ or $pb*N_{top}$, value, depending on the mutation strategy drops to 1, then it is set to 2, so there is always a choice between two best solutions.

One other important feature of the LL-NADE algorithm is the new selection (replacement) mechanism. The selection used in the algorithm depends on the chosen mutation strategy, i.e. if the target vector is from newest or top population. If the newly generated vector is better than the target vector, it is saved to the newest population. The place for the new solution is saved is determined by index $nc$, which is iterated from 1 to $N_{new}$, and is incremented only if there is a successful solution. The replacement mechanism in LL-NADE works as shown below:

$x_{nc}=\left\{\begin{array}{c}{u}_{i}iff\left(u_i\right)\le f\left(x_{r1}^{t|n}\right)\\ x_{nc}otherwise\end{array}\right.$,

where $t|n$ for the target vector means that it can be chosen from newest population or top population. The new solutions, which replace old ones in the population, can be used for generating other vectors in the same generations. Besides, successful vectors are stored in $x^{temp}$, a temporary population. At the end of each generation $x^{temp}$ and $x^{top}$ are joined, sorted, and only $N_{top}$ solutions are copied back to $x^{top}$. This ensures that the top population always contains the best solutions from the whole search process. LL-NADE also uses linear population size reduction, same as in L-SHADE algorithm (Tanabe and Fukunaga, 2014), however here it is used for two populations, newest and top, at the same time.