An Efficient Reconstructed Differential Evolution Variant by Some of the Current State-of-the-art Strategies for Solving Single Objective Bound Constrained Problems
Sichen Tao Ruihan Zhao Kaiyu Wang Shangce Gao

UTF8gbsn
	
	
	
	
	
	
	An Efficient Reconstructed Differential Evolution Variant by Some of the Current State-of-the-art Strategies for Solving Single Objective Bound Constrained Problems
    
		1st Sichen Tao Faculty of Engineering 
 University of Toyama 
 Toyama, Japan 
 taosc73@hotmail.com 
 d2278002@ems.u-toyama.ac.jp
		2nd Ruihan Zhao School of Mechanical Engineering 
 Tongji University 
 Shanghai, China 
 2110415@tongji.edu.cn
		3rd Kaiyu Wang Faculty of Engineering 
 University of Toyama 
 Toyama, Japan 
 greskofairy@gmail.com
            4th Shangce Gao Faculty of Engineering 
 University of Toyama 
 Toyama, Japan 
 gaosc@eng.u-toyama.ac.jp
	
    
======================================================================================================================================================================================================================================================================================================================================================================================================================================================================================





Complex single-objective bounded problems are often difficult to solve. In evolutionary computation methods, since the proposal of differential evolution algorithm in 1997, it has been widely studied and developed due to its simplicity and efficiency. These developments include various adaptive strategies, operator improvements, and the introduction of other search methods. After 2014, research based on LSHADE has also been widely studied by researchers. However, although recently proposed improvement strategies have shown superiority over their previous generation's first performance, adding all new strategies may not necessarily bring the strongest performance. Therefore, we recombine some effective advances based on advanced differential evolution variants in recent years and finally determine an effective combination scheme to further promote the performance of differential evolution. In this paper, we propose a strategy recombination and reconstruction differential evolution algorithm called reconstructed differential evolution (RDE) to solve single-objective bounded optimization problems. Based on the benchmark suite of the 2024 IEEE Congress on Evolutionary Computation (CEC2024), we tested RDE and several other advanced differential evolution variants. The experimental results show that RDE has superior performance in solving complex optimization problems.


  
	Evolutionary Computation, Evolutionary Algorithm, Meta-heuristics, Differential Evolution, Optimization Problems




§ INTRODUCTION

Optimization has become a fundamental tool in applied mathematics, engineering, economics, medical science and other scientific fields, including energy systems, bioinformatics, finance, manufacturing and production, transportation and logistics, telecommunications networks etc<cit.><cit.>. Real-world optimization problems are usually related to one or more of the following: nonlinear complex constraints, multimodal, multidimensional, non-differentiable, and noisy search spaces. Traditional deterministic methods often perform poorly in complex optimization problems. In contrast, evolutionary computation methods have been discovered and considered as an excellent alternative to traditional optimization techniques in the past 40 years of research<cit.>. They can avoid local optima as much as possible within reasonable computing time and find at least sufficiently good solutions<cit.><cit.>. Additionally, evolutionary algorithms are simple and easy to use. They are usually based on some simple biological or object concepts without requiring differentiation of problem functions. They have certain generality that can be used to solve various types of optimization problems.

Several classic optimization methods based on evolutionary thinking have been proposed, such as genetic algorithm<cit.>, particle swarm optimization<cit.>, and differential evolution (DE)<cit.>. Their various advanced variants have also been fully developed, tested, and researched over the past 20 years. In the IEEE Congress on Evolutionary Computation (IEEE CEC) in recent decades, various types of optimization problems have been widely tested and competed. Among them, since SHADE was proposed in 2013<cit.>, new variants of differential evolution algorithms have consistently ranked high in annual competitions. The encoding of these algorithms is not very complex but they exhibit excellent performance on relatively complex space optimization problems and continue to achieve performance improvements. A notable improvement path has emerged from this research. In 2014, LSHADE<cit.> improved the upper limit performance of DE variants in the CEC2014 standard test set by introducing linear population changes. In 2018, LSHADE-RSP<cit.> achieved second place in the competition by introducing a rank-based selection pressure strategy. In 2021, an improved LSHADE-RSP (iLSHADE-RSP) using Cauchy perturbation search was shown to further improve the upper limit performance of this series of DEs <cit.>. Additionally, in 2019 an enhanced mutation strategy called EB mutation strategy <cit.> was reported to effectively improve the performance of LSHADE and its previous generations' algorithms as well.

In this study, based on recent research that has brought effective performance improvements to DE advanced variants, we construct and propose a new DE variant called Reconstructed Differential Evolution (RDE). We studied multiple parameter adaptive strategies and developed the RSP strategy. In addition, the EB mutation strategy was also introduced to participate in the optimization process with LSHADE series mutation strategies, and adaptive control of dual-operator population resources was achieved through an evaluation method based on fitness progress. We tested RDE on the benchmark suite of the 2024 IEEE Congress on Evolutionary Computation (CEC2024) and compared it with other advanced evolutionary algorithms. The experimental results show that RDE has excellent performance and development potential in solving single-objective bounded optimization problems.



§ RECONSTRUCT DIFFERENTIAL EVOLUTION
 


 §.§ The Basic DE of RDE

In this section, we elaborate on one of the classic variants of DE and use it as the basis for our research in this paper. In the following sections, we will gradually develop based on this basic DE.

Like other evolutionary algorithms, DE typically generates an initial population of N individuals based on the following formula.

    x_i,j = rand(x_L,j,x_U,j)

where the function rand(a,b) returns a random number within the range of [a,b]. x_L,j and x_U,j respectively represent the lower bound and upper bound of dimension j.

The core of differential evolution is the mutation operator. Since the original differential evolution (DE) was proposed in 1997 <cit.>, various improved mutation operators have been introduced, including DE/rand/1, DE/rand/2, DE/best/1, DE/best/2, and DE/current-to-best/1. The most famous one is the DE/current-to-pbest/1 mutation strategy introduced by JADE in 2009 <cit.>. This strategy is also the most commonly used efficient strategy for LSHADE and its descendant variants. Therefore, we use it as the basis of our research in this paper. Its expression is as follows:

    v_i,j^(k+1)=x_i,j^(k)+F(x_p,j^(k) - x_i,j^(k))+F(x_r1,j^(k)-x_r2,j^(k))

where k represents the number of iterations. x_i,j refers to the value of the j-th dimension of the i-th individual. r1 and r2 are two different random indices used for randomly selecting individuals from the population. p is a randomly selected index value from the top 100p% individuals in the population sorted by fitness values, with a range of (0,1]. F is a scale factor used to control the size of differential vectors, with a range of [0,1].

Another major part of LSHADE is crossover, which is controlled by a crossover probability Cr ranging from 0 to 1. For each dimension of every new trial solution generated after mutation for each individual in the population, there is a probability of (1-Cr) that it will be replaced by the value of the same dimension from its parent. This inheritance comes from earlier genetic algorithms in evolutionary computation <cit.>. The expression is as follows:

    u_i,j^(k) = {[ v_i,j^(k),   j = j_rand   or  rand < Cr;                 x_i,j^(k),    otherwise ].

where u_i,j is the new individual generated by executing crossover strategy between v_i,j and x_i,j. j_rand represents a random integer within the range of [0,D] (where D is the dimension of the optimization problem). The purpose of j_rand is to ensure that at least one dimension adopts the value generated by mutation strategy.

Finally, there is the selection part. LSHADE compares the fitness values of offspring individuals with their corresponding parent individuals and keeps the one with better fitness value. The algorithm will perform this selection operation on each individual in the population separately. Its expression is as follows.

    x_i^(k+1) = {[ u_i^(k),   f(u_i^(k)) ≤ f(x_i^(k));              x_i^(k),    otherwise ].
    
where f(u_i^(k)) and f(x_i^(k)) indicates the evaluation function of the individual u_i^(k) and x_i^(k).



 §.§ The Reconstructured Differential Evolution

In this section, we will combine different strategies of basic DE with various advanced DE variants proposed in recent years, and develop and propose a reconstructed DE (RDE).



  §.§.§ External Archive

In the mutation strategy of the basic DE framework we adopt, a random index r2 is used to select useful individuals from a joint population consisting of the current population and an external archive. This approach further balances the algorithm's development and exploratory performance, and enhances its stability. The external archive preserves some parent individuals from history that have already been replaced in the current archive. The use of an external archive has been adopted by a series of advanced DE algorithms starting with SHADE. The size of this archive is defined as Ar· N, where N represents the number of individuals in the population.



  §.§.§ Introducing the DE/current-to-order-pbest/1 Mutation Strategy

In a study conducted in 2019, a new mutation strategy called DE/current-to-order-pbest/1 was proposed. It sorts and recombines the first, third, and fourth terms of two differential groups in DE/current-to-pbest/1 according to their fitness values, organizes them in order of better, medium, and worse solutions, and generates applicable solutions accordingly. The expression is as follows:


    v_i,j^(k+1)=x_i,j^(k)+F(x_ord_pbest,j^(k) - x_i,j^(k))
    
        +F(x_ord_median,j^(k)-x_ord_worst,j^(k))


x_ord_pbest,j^(k), x_ord_median,j^(k) and x_ord_worst,j^(k) represent the individuals in the corresponding positions after sorting, which correspond to better, medium and worse fitness values among the three.



  §.§.§ Hybridization of Two Mutation Strategies

We use both effective mutation strategies mentioned above to update individuals in the population. Here, we propose a simple adaptive strategy to dynamically control the allocation ratio of population resources between the two strategies. We use γ_1 ∈ [0,1] to represent the resource allocation ratio for DE/current-to-order-pbest/1 strategy, and the resource allocation ratio for DE/current-to-pbest/1 is γ_2 = (1-γ_1). We use ω_m1 and ω_m2 to represent the average fitness improvement caused by the two mutation strategies respectively, and determine the allocation ratio of next generation based on their proportion. The expression is as follows:

    ω_m1^(k) = ∑_i=1^N_1 (f_m1,i^(k) - f_m1,i^(k-1))/N_1


    ω_m2^(k) = ∑_i=1^N_2 (f_m2,i^(k) - f_m2,i^(k-1))/N_2



    γ_1^(k+1) = {[    0.5,   ω_m1^(k) = ω_m2^(k-1) = 0 or k = 1; ω_m1^(k)/ω_m1^(k) + ω_m2^(k-1),    otherwise ].

where when the average fitness improvement caused by both strategies is zero, let γ_1 = γ_2 = 0.5. When initializing the population, γ_1^(1) = γ_2^(1) = 0.5.



  §.§.§ Extened Rank-based Selective Pressure Strategy

In LSHADE-RSP<cit.>, a fitness-based rank pressure method<cit.> is proposed to correct the probability of different individuals being selected in DE, with rank indicators assigned as follows:

    Rank_i = k_r · (N - i) + 1

where the i here indicates the original rank calculated by the fitness values of different individuals in a population. Rank_i indicates the corrected rank value of the individual ranked ith. By this equation, the scaling factor k_r is responsible for the greediness of the rank selection.

Then, the probability of selecting corresponding individuals is no longer equal and is modified by the following formula:

    pr_i = Rank_i / (Rank_1 + Rank_2 + ... + Rank_N)

pr_i represents the probability of the individual ranked i being selected in each random selection of the mutation strategy.

The strategy is used in LSHADE-RSP to influence the selection probability of the last two terms in the differential term, namely r_1 and r_2 in Eq. <ref>. However, we extend it to three random selection behaviors of two differential terms in the new variant proposed in this paper, including p, r_1, and r_2 in Eq. <ref>. Correspondingly, in DE/current-to-order-pbest/1 Mutation Strategy, pre-sorting selection is also based on this Extended Rank-based Selective Pressure Strategy. Note that the selection behavior in the historical archive of LSHADE-RSP did not execute RSP. Here we also make corrections to the selection probability of historical archives using the same method.



  §.§.§ Success Historical Memory based Parameter Adaptive Strategy

In order to adaptively adjust the values of parameters F and Cr, the Success Historical Memory based Parameter Adaptive Strategy in jSO<cit.> is used in RDE. Firstly, two archives with H entries are used to store reference values for F and Cr (H_F = H_Cr = H), which are updated in real-time. The values stored at position h, denoted as μ_F,h and μ_Cr,h respectively (h ∈ [1,H]), are used to determine the value of F_i and Cr_i for each individual in the population using the following formulae during each generation:

    Cr_i^(k) = CauchyRand(μ_F,h,0.1)


    F_i^(k) = NormalRand(μ_Cr,h,0.1)


    h = mod(k/H)

Among them, CauchyRand(a,b) returns a random number obtained from a Cauchy distribution with median of a and scale factor of b. NormalRand(a,b) returns a random number obtained from a normal distribution with mean of a and variance of b. mod(a/b) returns the remainder obtained when dividing a by b.

Then, the used archive slot is immediately updated, expressed as follows:

    μ_F,j^(k) = ∑_n = 1^|S_F^(k)|ω_n^(k)s_F,n^(k)^2/∑_n = 1^|S_F^(k)|ω_n^(k)s_F,n^(k)



    μ_Cr,j^(k) = ∑_n = 1^|S_Cr^(k)|ω_n^(k)s_Cr,n^(k)^2/∑_n = 1^|S_Cr^(k)|ω_n^(k)s_Cr,n^(k)


where s_F,n^(k) and s_Cr,n^(k) represent the nth values of F and Cr of one successful trial in the kth iteration. |S_r^(k)| and |S_s^(k)| represent the length of success history vectors S_r^(k) and S_s^(k) in the kth iteration. ω_h^(k) is calculated as follows:


    ω_n^(k) = f_n^(k) - f_n^(k-1)/∑_g = 1^|S^(k)|f_g^(k) - f_g^(k-1)


where ω_n represents the nth individual's fitness successful weight for evaluations in Eq. (<ref>) and Eq. (<ref>).

where a strategy used in iLSHADE<cit.>, jSO<cit.> and LSHADE-RSP<cit.> is introduced. The last positions of F and Cr in the archive are fixed during the optimization process, with their values set to 0.9 as follows:

    H_F, H = H_Cr, H = 0.9

In addition, some related constraints have also been adopted. In the early stages, excessively large F and excessively small Cr were not allowed. Their formulas are expressed as follows:

    F_i^(k)=0.7,   if nfes < 0.6 · max_nfes and F_i^(k) > 0.7


    Cr_i^(k) = {[     0.7,      if nfes < 0.25 · max_nfes;                       and F_i^(k) < 0.7; 0.6,      else if nfes < 0.5 · max_nfes;                       and F_i^(k) < 0.6 ].


where nfes and max_nfes represent the current fitness evaluation number and the maximum fitness evaluation number.



  §.§.§ Linear p Value Reduction

After each generation of iteration k, the value of p for "pbest" selection strategy in Eq. (<ref>) and Eq. (<ref>) is linearly reduced. The formula is expressed as follows:

    p^(k) = p_max· (1 - 0.5 ·nfes/max_nfes)

where p_max represents the initialized p value. p^(k) denotes the p value for the "pbest" selection strategy at the kth iteration.



  §.§.§ Linear Population Size Reduction

We introduced the linear population size reduction strategy from LSHADE.

    N^(k+1) = round ((N_min^(k) - N_max^(k)/max_nfes) · nfes + N_max^(k))

where round() returns one rounded integer. N_max and N_min denote the beginning and the ending size of the population, respectively. The value of N_min is determined by the minimum number of population individuals that can undergo differential evolution mutation operator.



  §.§.§ Cauthy Perturbation

A Cauthy perturbation strategy called iLSHADE-RSP, proposed in 2021, is used to replace individuals that undergo parent crossover with a probability of p_r. We introduce this strategy into RDE to appropriately enhance population diversity during the optimization process. The strategy is expressed as follows:

    u_i,j^(k) = {[         v_i,j^(k),   j = j_rand  or  rand < Cr_i; CauchyRand(x_i,j^(k),0.1),   else if  rand < p_r;                           x_i,j^(k),   otherwise ].

where rand denotes a random value from 0 to 1. p_r represents a parameter to control the Cauthy perturbation strategy here.
 



  §.§.§ The pseudo-code of RDE

The pseudo-code of RDE is given in Algorithm <ref>.



§ EXPERIMENTAL RESULTS



 §.§ Benchmark Functions

The performance of the proposed algorithm RDE is tested on the CEC 2024 Competition for Single-Objective Real Parameter Numerical Optimization<cit.>. The benchmark suite, CEC2024, comprises 29 test functions (with 30D) with diverse features, including unimodal functions (f_1-f_2), multimodal functions (f3-f9), hybrid funtions (f10-f19), and composition functions (f20-f29). The variables in hybrid functions are randomly divided into subcomponents, and different basic functions are used for each subcomponent. The composition functions utilize basic benchmark functions to create problems with a randomly located global optimum and several randomly located deep local optima, making them more challenging to solve.



 §.§ Parameter Settings

In this study, the algorithm parameter settings are set as follows:

    
  1) population maximum and minimum sizes N_min = 4 and N_max = 18· D;
    
  2) success history archive memory size H = 5;
    
  3) rank greediness factor k_r = 3;
    
  4) external archive size Ar = 1;
    
  5) differential mutation p value: p_max = 0.25;
    
  6) initialized sub-population resource ratios γ_1 = γ_2 = 0.5;
    
  7) initialized scale factor and crossover rate in memory archive μ_F = 0.3 and μ_Cr = 0.8;
    
  8) Cauthy pertubation strategy rate p_r = 0.2;






 §.§ Experimental Settings

According to the guidelines of CEC2024, 25 independent runs are implemented. The maximum evaluation number is set to max_nfes = 10000· D, where the D is the dimensionality of the optimization problems. The search range is set to [-100, 100]^D. Fitness errors
less than 1× 10^−8 are considered to 0. The experiments were performed using the following system: CPU: Intel® Core™i7-12700kf 3.6GHz, 32GB DDR4-3600MHz RAM, Programming Language: C++, and Operator System: Windows 10.





 §.§ Statistical Results

The Wilcoxon rank-sum test is utilized to determine if there is a statistically significant difference between two algorithms in solving a problem, with a significance level of α = 0.05. Each problem is tested 51 times independently in a row. The symbol “+" denotes the superior algorithm when there is a significant difference between the pair, while “-" indicates the relatively inferior one. “=" signifies that no significant difference exists between the pair of algorithms.

The performance of the RDE was compared to the other compatitors which showed excellent performance on previous CEC benchmark suites, including:

    
  1) LSHADE-RSP<cit.>: LSHADE Algorithm with Rank-Based Selective Pressure Strategy for Solving CEC 2017 Benchmark Problems;
    
  2) iLSHADE-RSP<cit.>: An improved LSHADE-RSP algorithm with the Cauchy perturbation;
    
  3) HSES<cit.>: Hybrid Sampling Evolution Strategy for Solving Single Objective Bound Constrained Problems;
    
  4) EBOwithCMAR<cit.>: Effective Butterfly Optimizer using Covariance Matrix Adapted Retreat phase;
    
  5) LSHADE<cit.>: Improving the search performance of SHADE using linear population size reduction.


As shown in Table <ref>, RDE demonstrates superiority over competitive algorithms on CEC2024. In addition, RDE also performs well on relatively more complex composition functions (f20-f29), indicating the effectiveness of recombination research. Compared with LSHADE-RSP, iLSHADE-RSP, HSES, EBOwithCMAR and LSHADE, RDE achieves better solutions on 13, 15, 11, 14 and 17 problems respectively and fails to beat opponents on 4, 3, 7, 5 and 3 problems respectively. Although RDE shows significant advantages over advanced variants of the DE series, the performance gap is not significantly widened compared to HSES.



 §.§ Algorithm Complexity

Table <ref> shows that the algorithm complexity of the proposed RDE is 4.95. T_0 is the time result by running the assessing test program in <cit.>. T_1 is the time cost result by running the 18th function and T_2 is the time cost result of averaging 5 runs of the algorithm on f_18, respectively. Both of them are with 200000 evaluations.



§ CONCLUSION

In this study, we conducted a combined research on recent advances in advanced DE variants and proposed an effective combination improvement scheme to further promote the performance of DE in complex optimization problems. On the CEC2024 benchmark suite, RDE showed significant performance advantages over some advanced variants of DE. Although the ES variant HSES achieved similar performance in 2018, due to the simplicity, efficiency and stable performance of DE, it seems to have received more attention and development from researchers. Although we also attempted to combine other recent DE improvement strategies besides those shown in this paper, no significant results were obtained. Therefore, various sub-strategies mentioned in this paper may be worth prioritizing for future development of DE. It is worth noting that compared with algorithms such as iLSHADE-RSP, RDE adopts fewer strategies but has better performance.



§ ACKNOWLEDGMENT

This research was partially supported by the Japan Society for the Promotion of Science (JSPS) KAKENHI under Grant JP22H03643, Japan Science and Technology Agency (JST) Support for Pioneering Research Initiated by the Next Generation (SPRING) under Grant JPMJSP2145, and JST through the Establishment of University Fellowships towards the Creation of Science Technology Innovation under Grant JPMJFS2115.

IEEEtran



