Abstract
In this paper a novel algorithmic scheme for differential evolution is proposed with two populations and new mutation strategies. The populations contain latest and best individuals, and the sizes of these populations are controlled independently. The LLNADE algorithm uses the parameter adaptation scheme proposed in LSHADE, and the sizes of both populations are reduced at the same time. The experiments described in the paper are performed on the CEC 2022 benchmark suite. The total standard score is used for comparison of different algorithms on a set of benchmark problems. The experiments are performed with six different mutation strategies, which utilize individuals from both populations. The most efficient mutation strategy utilizes directed search from newest to top individuals. It is shown that LLNADE is capable of demonstrating results comparable with stateoftheart algorithms. Comparison on various test functions and dimensions have shown that LLNADE performs in a way that is not similar to other differential evolution algorithms, achieving better results on some problems, but worse on other.
Keywords: Differential evolution, population size, parameter adaptation
Introduction
The development of modern optimization methods is one of the important directions of computational intelligence research nowadays, as such methods are often utilized in other learning or search algorithms. The heuristic optimization, which includes evolutionary algorithms (EAs), focuses on black box optimization, including singleobjective, multiobjective, constrained and other types of problems (Sloss & Gustafson, 2020). The differential evolution (DE) (Price et al., 2006) today represents a popular family of approaches, which are relatively simple and easy to implement, and at the same time very efficient in many scenarios. This can be seen by the success of the DEbased algorithms in optimization competitions in the last several years, such as Congress on Evolutionary Computation competition on singleobjective numerical optimization, where DE is taking leading places (Škvorc et al., 2019).
One of the problems of DE is the sensitivity to parameter values, which lead to numerous studies on parameter adaptation schemes, with SHADE being one of the most popular approaches (Tanabe & Fukunaga, 2013). However, few attempts have been made in changing the basics of the DE algorithmic scheme. A recent study on Unbounded DE (UDE) (Kitamura & Fukunaga, 2022) has shown that it is possible to apply specific selection mechanisms with infinitely growing population to achieve competitive results.
In this paper the dual population algorithm is proposed, which further develops the ideas of UDE. LLNADE (Linear and Linear populations sizes reduction Newest and top Adaptive Differential Evolution) maintains the newest population, which contains recently discovered solutions, and top population, that keeps the best solutions throughout the whole search process. The numerical experiments are performed on the CEC 2022 benchmark problems (Kumar et al., 2021). The main features of the proposed algorithm are the new mutation strategies, combining top and newest solutions, and the novel selection (replacement) scheme for the population of newest individuals.
Problem Statement
This paper is focused on the problem of developing new algorithmic schemes for differential evolution for solving numerical optimization tasks. Most known algorithmic schemes rely on a single population and an archive, while other possibilities should be discovered.
Research Questions
The problem statement raises a set off questions, including the following. First of all, is it possible to develop an algorithmic scheme with more than one population and find an efficient control strategy. Secondly, if the first population contains new individuals, and the second keeps the best, what should be the mutation strategies in such design? In third place, what would be the performance of such approach compared to the stateoftheart algorithms?
Purpose of the Study
The purpose of this study is to propose a new efficient differential evolution algorithm and estimate its efficiency on a set of benchmark problems compared to the best known alternative approaches.
Research Methods
Differential evolution
The differential evolution algorithm was proposed by Storn and Price 1995. The differential evoltuion is a populationbased 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 differencebased mutation. There are several popular mutation strategies, with currenttopbest 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, jth coordinate of the ith 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 midpointtarget, 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 LLNADE, 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 LLNADE 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 LLNADE uses variants of the mutation strategy used in JADE, SHADE and LSHADE, i.e. currenttopbest mutation strategy. LLNADE 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:
 rnewtoptop/t/t: vi,j=xr1,jnew+F×xpbest,jtopxi,jnew+F×xr2,jtopxr3,jtop
 rnewtoptop/t/n: vi,j=xr1,jnew+F×xpbest,jtopxi,jnew+F×xr2,jtopxr3,jnew,
 rnewtoptop/n/t: vi,j=xr1,jnew+F×xpbest,jtopxi,jnew+F×xr2,jnewxr3,jtop,
 rnewtoptop/n/n: vi,j=xr1,jnew+F×xpbest,jtopxi,jnew+F×xr2,jnewxr3,jnew,
 rnewtopnew/n/n: vi,j=xr1,jnew+F×xpbest,jnewxi,jnew+F×xr2,jnewxr3,jnew,
 rtoptoptop/t/t: vi,j=xr1,jtop+F×xpbest,jtopxi,jtop+F×xr2,jtopxr3,jtop
Here rnew and rtop 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 ith 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 LLNADE 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 LLNADE works as shown below:
${x}_{nc}=\left\{\begin{array}{c}{u}_{i}iff\left({u}_{i}\right)\le f\left({x}_{r1}^{tn}\right)\\ {x}_{nc}otherwise\end{array}\right.$,
where $tn$ 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. LLNADE also uses linear population size reduction, same as in LSHADE algorithm (Tanabe and Fukunaga, 2014), however here it is used for two populations, newest and top, at the same time.
Findings
The computational experiments with LLNADE were performed on the CEC 2022 benchmark suite, developed for the Single Objective Bound Constrained Numerical Optimization Competition (Kumar et al., 2021). The benchmark contained 12 functions, defined for 10D and 20D, 30 independent runs were required for each of them. The algorithm was developed in C++ and ran on OpenMPIpowered cluster. For the first set of experiments the population sizes ${N}^{new}$ and ${N}^{top}$ changed from 5D to 60D with a step of 5D, and 6 mutation strategies were considered. This resulted in a total of 864 experiments. To compare the efficiency, the MannWhitney rank sum test with tiebreaking and normal approximation was applied with significance level of 0.01. In addition, the total standard score, summed over 12 functions, was calculated to compare a pair of approaches. The parameters of LLNADE used in the experiments are the following: ${N}^{init}=100D,H=7,{M}_{F,r}=0.3,{M}_{Cr,r}=0.8,p{b}_{max}=0.3,p{b}_{min}=0.01$. For the first set of experiments the NLSHADELBC algorithm (Stanovov et al., 2022) was chosen as the baseline approach, as it is announced to be second best algorithm in CEC 2022 competition. Figures 1 and 2 show the total standard score of comparing LLNADE with NLSHADELBC with different population sizes and strategies. Lighter areas mean better results, i.e. larger total score.
Considering the results in Figures 1, it can be concluded that for all mutation strategies for 10D functions the area of highest efficiency is around 15D or 20D for both ${N}^{new}$ and ${N}^{top}$. For rnewtoptop/t/n and rnewtoptop/t/t there is a clearer dependence of two populations sizes, while rnewtoptop/n/t and rnewtoptop/n/n are characterized by smaller influence of ${N}^{top}$. Speaking of the efficiency of the proposed algorithms, LLNADE is able to outperform NLSHADELBC using all mutation strategies except the last one, rtoptoptop/t/t. The efficiency of rnewtopnew/n/n is also lower compared to the strategies which use both populations.
Figure 2 shows similar results, i.e. total standard score of MannWhitney tests is larger than 0 for population sizes of around 20D. An important difference compared to 10D case is that the strategy using only newest vectors rnewtopnew/n/n may have the same level of efficiency compared to strategies using both populations. Also, increasing the population size significantly decreases the efficiency of the algorithm, probably because the convergence speed is also considered.
To conclude the experiments section, we provide the comparison of LLNADE using rnewtoptop/n/t strategy and ${N}^{new}={N}^{top}=15D$ with best participants of CEC 2022 competition, the results are shown in Table 1. The top 3 algorithms are EA4eig (Bujok & Kolenovsky, 2022) combining several DE variants and CMAES, mentioned earlier NLSHADELBC (Stanovov et al., 2022) and NLSHADERSPMID (Biedrzycki et al., 2022), an advanced version of the NLSHADERSP with kmeans algorithm. The numbers in Table 1 are the numbers of wins/ties/losses over 12 tested functions.
The results in Table 3 show that LLNADE has comparable or even better performance against the top 3 methods of the recent CEC competition, which shows that the proposed approach can be promising.
Conclusion
In this paper a new differential evolution algorithm was proposed, which used a new algorithmic scheme with two populations and novel mutations. The experiments performed in this study have shown that the proposed algorithm LLNADE is highly competitive compared to the best methods in the CEC 2022 benchmark, especially on complex functions. One of the disadvantages of LLNADE is that it requires more parameters to be set compared to known alternatives. The LLNADE is a nonhybrid method, and it does not increase the computational complexity compared to modern DE variants, and it can be improved by implementing modifications, developed for other DE algorithms.
Acknowledgments
This research was funded by the Ministry of Science and Higher Education of the Russian Federation, Grant No. 0751520221121.
References
Biedrzycki, R., Arabas, J., & Warchulski, E. (2022, July). A version of nlshadersp algorithm with midpoint for cec 2022 single objective bound constrained problems. In 2022 IEEE Congress on Evolutionary Computation (CEC) (pp. 18). IEEE. DOI:
Bujok, P., & Kolenovsky, P. (2022, July). Eigen crossover in cooperative model of evolutionary algorithms applied to cec 2022 single objective numerical optimisation. In 2022 IEEE Congress on Evolutionary Computation (CEC) (pp. 18). IEEE. DOI:
Kitamura, T., & Fukunaga, A. (2022). Differential Evolution with an Unbounded Population. In 2022 IEEE Congress on Evolutionary Computation (CEC) (pp. 18). IEEE. DOI:
Kumar, A., Price, K., Mohamed, A. K. A. A., & Suganthan, P. N. (2021). Problem Definitions and Evaluation Criteria for the CEC 2022 Special Session and Competition on Single Objective Bound Constrained Numerical Optimization. Technical Report Nanyang Technological University, Singapoure.
Price, K., Storn, R. M., & Lampinen, J. A. (2006). Differential evolution: a practical approach to global optimization. Springer Science & Business Media.
Škvorc, U., Eftimov, T., & Korošec, P. (2019). CEC realparameter optimization competitions: Progress from 2013 to 2018. In 2019 IEEE congress on evolutionary computation (CEC) (pp. 31263133). IEEE. DOI:
Sloss, A. N., & Gustafson, S. (2020). 2019 Evolutionary Algorithms Review. In W. Banzhaf, E. Goodman, L. Sheneman, L. Trujillo, & B. Worzel (Eds.), Genetic Programming Theory and Practice XVII. Genetic and Evolutionary Computation (pp. 307344). Springer, Cham. DOI:
Stanovov, V., Akhmedova, S., & Semenkin, E. (2022). NLSHADELBC algorithm with linear parameter adaptation bias change for CEC 2022 Numerical Optimization. In 2022 IEEE Congress on Evolutionary Computation (CEC) (pp. 0108). IEEE. DOI:
Tanabe, R., & Fukunaga, A. (2013). Successhistory based parameter adaptation for differential evolution. In 2013 IEEE congress on evolutionary computation (pp. 7178). IEEE. DOI:
Tanabe, R., & Fukunaga, A. (2014). Improving the search performance of SHADE using linear population size reduction. In Proceedings of the IEEE Congress on Evolutionary Computation, CEC (pp. 16581665). DOI:
Copyright information
This work is licensed under a Creative Commons AttributionNonCommercialNoDerivatives 4.0 International License
About this article
Publication Date
27 February 2023
Article Doi
eBook ISBN
9781802969603
Publisher
European Publisher
Volume
1
Print ISBN (optional)

Edition Number
1st Edition
Pages
1403
Subjects
Hybrid methods, modeling and optimization, complex systems, mathematical models, data mining, computational intelligence
Cite this article as:
Stanovov, V., Akhmedova, S., & Semenkin, E. (2023). Adaptive Differential Evolution With Two Populations of New and Best Individuals. In P. Stanimorovic, A. A. Stupina, E. Semenkin, & I. V. Kovalev (Eds.), Hybrid Methods of Modeling and Optimization in Complex Systems, vol 1. European Proceedings of Computers and Technology (pp. 102110). European Publisher. https://doi.org/10.15405/epct.23021.13