This paper proposed a multiple-subpopulation based on differential evolution with an adaptive parameter control and population reduction, called EMPADE, for global optimization. In EMPADE, an adaptive parameter control method based on population diversity and fitness value is proposed to set the parameters F. Further, a mutation strategy named DE/currentpbad/1 with archives is designed. In addition, a population size reduction strategy is devised to adaptively eliminate poor performance Individuals. The proposed algorithm has been tested by solving CEC2014 benchmark problems. The experimental results show that the EMPADE algorithm strategy is feasible and effective, and has greater competitiveness compared with other related algorithms.
Differential evolution (DE), initially introduced by Storn and Price [1], has become a powerful tool to solve global optimization problems [2]. Applications of DE for real problems includes pattern recognition [3], power systems [4] and vehicle routing [5].
The selection of mutation operator is concerned by many researchers. For example, in JADE [6], a parameter adaptation strategy along with DE/current-to-pbest mutation strategy is employed to generate offspring. CoDE CoDE adopts multiple compound mutation operators (DE/rand/1, DE/rand/2 and DE/current-to-rand/1) and DE variants of parameter control mode [8]. In the above methods, mutation strategies are performed on a single population, rather than multiple populations.
Recently, multi-population based DE algorithms have also been proposed. These algorithms generally divide initial population into multiple sub-populations and share information among different subpopulations through individual migration. For example, in MPEDE [9] and EDEV[10], the authors tried to divide the population into a large reward sub-population and three small indicator sub-populations. In these methods, three different mutation strategies are employed in an ensemble manner. In SAMDE[11], the entire population is divided into three subpopulations of the same size, each employing a different mutation strategy. After each generation, the population is randomly reorganized. However, random recombination of the population could lead to lead to unreasonable allocation of computing resources. Further, parameter control in these methods does not consider the diversity and performance of subpopulations, restricting their performance [6].
In this paper, we propose multiple-population based differential evolution with adaptive parameter control and population reduction strategies, called EMPADE, for global optimization. In each generation, three subpopulations with the same size will be divided according to the Euclidean distance, and the three subpopulations will use different and fixed mutation operators, that is, similar individuals will form a new population in each generation, so that the mutation operator can act on individuals. A mutation strategy named
DE/current-pbad/1 has also been devised and performed on the top-ranked subpopulation. At the same time, a parameter adaptive method based on the diversity and fitness value of subpopulation is proposed, which can better address different problems. Additionally, a population reduction strategy is proposed to adaptively remove unpromising individuals. Experiments show that the performance of EMPADE is better or competitive than related method.
The rest of this paper is arranged as follows. The details of EMPADE are described in Section 2. Section 3 gives the related experiments and results of EMAPDE algorithm. Finally, we conclude this paper in Section 4.
In this section, we introduce the detailed process and strategies of our algorithm. First, initializing a population randomly, calculating the Euclidean distance of each individual in the population to the best individual. Then, dividing the population into three sub-populations of the same size according to the sort, in which the top-ranked subpopulation has a low diversity, and the bottom-ranked subpopulation has high diversity. The first third uses a devised mutation strategy called DE/current-to-pbad/1, which can improve the subpopulation diversity. The middle part uses mutation strategy DE/current-to-rand/1, which is able to converge fast while maintaining diversity. The last third uses mutation strategy DE/current-to-pbest/1, which can accelerate convergence. The program runs repeatedly until the termination conditions are met: three populations are run in parallel to search the space. At the end of each generation, update the control parameters F and CR and employing the proposed adaptive elimination operation to update the population size. This is followed by re-sorting and redividing the population into three sub-populations according to Euclidean distance. The overview of the proposed algorithm is shown in Algorithm I.
In the following subsections, we will describe the details of a cooperative mechanism strategy based on multi group mutation in Section 2.1, a parameter adaptive strategy for multi population in Section 2.2, and an adaptive elimination operation in Section 2.3.
Algorithm I EMPADE algorithm.
Set the initial population size individual(pi).
, minimum population and probability of excellent 1) 2) 3) 4) 5) a) b) c) d) e) return to ,
, and
).
Adjust population size.
the same size.
Calculate the Euclidean distance of each individual to the best individual and sort the individuals.
Assign different mutation operators to three subpopulations. = /3, p = 1, 2,3.
Run the following processes circularly until the termination conditions are met.
Information sharing: the individuals with the best fitness values of three sub populations are replaced by the best ones in the whole population The three sub populations Pi evolve in parallel with different mutation mi operators and Calculate the proportional parameters of control mF and mCr of each sub population (
Sort the individuals according to Euclidean distance, and redivide three subpopulations of 6)
Output results after calculating resource consumption. 2.1.
When the entire population is divided into three equally sized sub-populations according to their Euclidean distances to the best individual, the highest ranked population will have the least diversity. If traditional mutation operators such as DE/rand/1 and DE/rand/2 are used, it cannot help to improve its diversity, since the Euclidean distance among individuals in the subpopulation is small.
In view of the fact that and cannot maintain diversity in the subpopulation, a new mutation operator, called DE/current-to-pbad with archive, is proposed. Compared with the current subpopulation, the recently explored inferior solutions can improve the diversity of subpopulation. , − , is good for individuals to evolve toward diversity, and random , − , makes the individual change value larger, which is good for jumping out of the local optimum. In DE/current-to-pbad/1, a mutation vector is generated in the following manner. , = , + ∗ , − , + , − , , i ∈ 1,2, … , (1) where ,
represents an individual randomly selected from the last individuals of the current sub population, ∈
(0,1).
In summary, we calculate and sort the Euclidean distance for each generation, and divide three subpopulations. And P1 (”DE/current-pbad/1” for the top ranking), P2(”DE/current-to-rand/1” for the general ranking) and P3(”DE/current-to-pbest/1” for the worst ranking). 2.2.
and p subpopulation, and p is 1,2,3)
The parameter control of each subpopulation is very meaningful for improving the performance of the algorithm. In EMPADE, a adaptive parameter control mechanism based on multi subpopulation is designed that control parameters of each subpopulation can be adaptively changed according to the population diversity and the best fitness value. The adaptive scheme can coordinate the exploration and exploitation capabilities of each subpopulation to generate better offspring in the process of evolution. are shown as follows, respectively. (And in the paper, p represents the increased and
∗ diversity of subpopulation. 2.3.
Adaptive elimination operation where
∈ (0,1)is the proportion of each sub population to the diversity of all sub-populations, and
∈ (0,1) is the ratio of the best fitness value of the current subpopulation to the sum of the best fitness values of the three sub-populations. When the diversity of population is small, (CR) decreased, then mF will increase and mCr will decrease to increase the (2) (3) (F)
The current multi population algorithms often migrate individuals or copy individuals in different subpopulations, and the poorly performing individuals in the entire population are not eliminated. Although the diversity of population can be maintained, the overall performance of the algorithm will be affected. The linear population size reduction scheme proposed in LSHADE was proven to be excellent scheme for population size adaptation[12][13]. However, the rapid decline of the population at the beginning may lead to the loss of diversity of the population. Here, we designed a parabolic population elimination operation to eliminate under-performing individuals at each generation while maintaining the diversity of population at the early stage. The adaptive elimination operation is calculated as: max _ (4) where represents the minimum population, represents the original population. The poor individuals in the whole population will be randomly selected and removed.
All the algorithms in the experiment are run on the same computer, and are aimed at the cec2014 dataset. We will run each function 51 times, record its average value and standard deviation, and mark the best one as bold. The rank sum test of the algorithm takes 0.05 as the confidence interval. The sign ‘+’ means better than the correlation algorithm, ‘-’ means worse than the correlation algorithm, and ‘=’means similar to the correlation algorithm. The error of the experimental results is f-f *, where f * represents the best fitness value of the function. 3.1.
The strategy mechanisms are been explored by comparing EMPADE with EMPADE 1, in which a cooperative mechanism strategy of adaptive multi group mutation operator is employed. EMPADE 2 uses an adaptive elimination operation based on EMPADE 1 and EMPADE uses a parameter adaptive strategy for multi population based on EMPADE 2. The results on 30D are shown in Table II. Compared with other algorithms, 25 of the 30 benchmark functions have the best results. The EMPADE could be significantly better than three algorithms to be compared, especially on unimodal and hybrid functions. The results therefore indicated the strategies proposed are effective. 3.3.
EMPADE is compared to four DE variants: JADE[6], EPSDE[7], MPEDE[9], EDEV[10]. And Table II show the comparison results of the four algorithms. Looking at the experimental results on 30D, − EMPADE achieves the best mean values on 22 functions out of 30 functions. For unimodal functions ∗ F1–F3, EMPADE shows the best performance, the best mean fitness value can be found on all functions. EPSDE, MPEDE and EDEV can find the best mean fitness value on F2 and F3. And JADE can also find the best mean fitness value on F2. For the multi-modal benchmark functions F4-F16, compared with other algorithms, EMPADE still has the best performance and can be more competitive on eleven functions (F4, F5, F6, F7, F8, F9, F11, F12, F14, F15, F16), and finds the best fitness values on F4, F7 and F8. JADE also has a good performance and can achieve good results on ten functions (F4, F5, F7, F8, F10, F11, F12, F13, F14, F16), and finds the best fitness values on F4 and F8. EPSDE, MPEDE and EDEV have competitive performance on one function (F8), three functions (F6, F7, F8) and three functions (F7, F8, F13), respectively, and they can all find the best mean fitness value on F8. For the hybrid functions F17-F22, EMPADE is the most competitive, better than other related algorithms in all functions. For the complex composition functions F23-F30, EDEV achieves the best results, with excellent performance on 7 functions (F23, F25, F26, F27, F28, F29 and F30). JADE, EPSDE, MPEDE and EMPADE perform well on one function (F27), three functions (F23, F25, F29), one function (F26) and two functions (F24, F26), respectively.
Based on the above experiments and results, it can be concluded that EMPADE is better or competitive than related algorithms. especially in low dimensional unimodal functions, multimodal functions and hybrid functions.
This paper proposes an adaptive DE based on multi-subpopulation. In the proposed method, we design an adaptive parameter control scheme, which can comprehensively consider the optimal solution and diversity of each sub-population. This strategy can improve the robustness of multiple population based on DE. Further, a mechanism of eliminating poor individuals is proposed to preserve the population diversity at the early stage as well as improve the convergence speed of the population. In addition, we propose a mutation strategy to solve the problem of insufficient diversity of the top-ranked sub-populations when obtaining sub-populations based on Euclidean distance. The experimental results clearly show the significance of the proposed strategy, and the obtained algorithm can achieve better or comparable performance than related method.
[5] L. Song and D. Yun, “An improved differential evolution algorithm with local search for capacitated vehicle routing problem,” in 2018 Tenth International Conference on Advanced Computational Intelligence (ICACI), 2018. [6] J. Zhang and A. C. Sanderson, “Jade: adaptive differential evolution with optional external archive,”
IEEE Transactions on evolutionary computation, vol. 13, no. 5, pp. 945–958, 2009. [7] R. Mallipeddi and P. N. Suganthan, “Differential evolution algorithm with ensemble of parameters and mutation and crossover strategies,” in Swarm, Evolutionary, and Memetic Computing - First International Conference on Swarm, Evolutionary, and Memetic Computing, SEM- CCO 2010, Chennai, India, December 16-18, 2010. Proceedings, 2010. [8] W. Yong, Z. Cai, and Q. Zhang, “Differential evolution with composite trial vector generation strategies and control parameters,” IEEE Trans- actions on Evolutionary Computation, vol. 15, no. 1, pp. 55–66, 2011. [9] G. Wu, R. Mallipeddi, P. N. Suganthan, W. Rui, and H. Chen, “Differential evolution with multipopulation based ensemble of mutation strategies,” Information Sciences An International Journal, vol. 329, no. C, pp. 329–345, 2016. [10] Guohua, Wu, Xin, Shen, Haifeng, Li, Huangke, Chen, Anping, and Lin, “Ensemble of differential evolution variants,” Information Sciences: An International Journal, vol. 423, pp. 172–186, 2018. [11] L. Zhu, Y. Ma, and Y. Bai, “A self-adaptive multi-population differential evolution algorithm,”
Natural Computing, vol. 19, no. 1, pp. 211–235, 2020. [12] Z. Meng, J. S. Pan, and K. K. Tseng, “Pade: An enhanced differential evolution algorithm with novel control parameter adaptation schemes for numerical optimization,” Knowledge-Based Systems, 2019. [13] J. Wei, Z. Wang, Y. Xu, and Z. Chen, “A differential evolution with multi-factor ranking based parameter adaptation for global optimization,” in 2021 IEEE Congress on Evolutionary Computation (CEC),2021