Adaptive Differential Evolution with Variable Population Size for Solving High-Dimensional
Problems
Hui Wang∗†,Shahryar Rahnamayan‡and Zhijian Wu∗
∗State Key Laboratory of Software Engineering,Wuhan University,Wuhan430072,China
Email:wang ,
†School of Information Engineering,Nanchang Institute of Technology,Nanchang330099,China
‡Faculty of Engineering and Applied Science,University of Ontario Institute of Technology(UOIT)
2000Simcoe Street North,Oshawa,ON L1H7K4,Canada
Email:shahryar.rahnamayan@uoit.ca
Abstract—In this paper,we prent a novel Differential Evo-lution(DE)algorithm to solve high-dimensional global opti-mization problems effectively.The propod approach,called DEVP,employs a variable population size mechanism,which adjusts population size adaptively.Experiments are con
ducted to verify the performance of DEVP on19high-dimensional global optimization problems with dimensions50,100,200, 500and1000.The simulation results show that DEVP out-performs classical DE,CHC(Crossgenerational elitist lection, Heterogeneous recombination,and Cataclysmic mutation),G-CMA-ES(Restart Covariant Matrix Evolutionary Strategy)and GODE(Generalized Opposition-Bad DE)on the majority of test problems.
Index Terms—Differential Evolution(DE),variable population size,global optimization,large-scale,high-dimensional.
I.I NTRODUCTION
Many real world problems can be converted into optimiza-tion problems.Therefore,optimization has been an active area of rearch for veral decades.As the complexity of problems increa(such as high dimensions),traditional optimization algorithms struggle to achieve satisfactory solutions,and better algorithms are always required.An unconstrained optimization problem can be formulated as a minimization problem as follows:
Min f(x),
where x=[x1,x2,...,x D]and D is the dimension size of the problem.
In the past decades,different kinds of nature-inspired al-gorithms have been designed and applied to solve optimiza-tion problems.Simulated Annealing(SA)[1],Evolutionary Algorithms(EAs)[2],Differential Evolution(DE)[3],Par-ticle Swarm Optimization(PSO)[4],Ant Colony Optimiza-tion(ACO)[5],and Estimation of Distribution Algorithms (EDA)[6]are some examples among many others.However, the algorithms suffer from the cur of dimensionality.It implies that their performance deteriorates quickly as the dimension of the problem increas.The main reason is that in general the complexity of the problem increas exponentially with its dimension.The majority of evolutionary algorithms lo the power of arching the optima solution when the dimension increas.So,more efficient arch strategies are required to explore all the promising regions in a given time budget[7].
The DE algorithm,propod by Storn and Price[3],is an effective,robust,and simple global optimization algorithm. According to frequently reported experimental studies,DE has shown better performance than many other evolutionary algorithms in terms of convergence speed and robustness over veral benchmark functions and real-world problems[8]. Therefore,some rearchers applied DE and its variants to solve some challenging problems,such as large-scale global optimization problems[9].Yang et al.propod a multi-level cooperative co-evolution algorithm(
MLCC)bad on lf-adaptive neighborhood arch DE to solve large-scale problems[10].The prented results showed that MLCC could achieve promising solutions.Brest et al.introduced a population size reduction mechanism into lf-adaptive DE, where the population size decreas during the evolutionary process[11].Recently,Brest and Mauˇc ec propod another version of jDEdynNP-F by employing three new mutation schemes[12].Rahnamayan and Wang prented a experimen-tal study of opposition-bad DE(ODE)[13]on large-scale problems[14].The reported results show that ODE signifi-cantly improves the performance of standard DE.Muelas et al.[15]ud a local arch mechanism to improve the solutions obtained by DE.Wang et al.[16],[17]ud an enhanced ODE bad on generalized opposition-bad learning(GODE)to solve scalable benchmark functions.Zhao et al.[18]combined lf-adaptive DE and multiple trajectory arch(MTS)for large-scale optimization,which incorporates DE/current-to-p best[19]mutation strategy and hybridized with modified MTS.Wang et al.[20]propod a quential DE enhanced by neighborhood arch(SDENS),which is bad on global and local mutation[21].
In this paper,we prent a novel DE algorithm to solve high-dimensional global optimization problems.The propod
approach,called DEVP,employs a variable population size mechanism,in which the population size is
variable in terms of the arch status of current population.In order to verify the performance of DEVP,we test it on 19large-scale global optimization problems with D =50,100,200,500and 1000.Experimental results show that DEVP outperforms DE,CHC,G-CMA-ES,and GODE on the majority of test problems.The rest of the paper is organized as follows.In Section II,,the DE algorithm is briefly introduced.Section III describes our propod approach,DEVP.In Section IV ,the test suite,parameter ttings,results and discussions are prented.Fi-nally,the work is concluded in Section V .
II.A B RIEF R EVIEW OF D IFFERENTIAL E VOLUTION There are veral variants of DE [3].According to suggestions of [22],the rand/1/exp strategy shows a better performance to solve some high-dimensional problems.Our propod algorithm is also bad on this DE scheme.Let us assume that X i (t )(i =1,2,...,N p )is the i th individual in population P (t ),where N p is the population size,t is the generation index,and P (t )is the population in the t th generation.The main idea of DE is to generate trial vectors.Mutation and crossover are ud to produce new trial vectors,and lection determines which of the vectors will be successfully lected into the next generation.
Mutation –For each vector X i (t )in Generation t ,a mutant vector V is generated by
V i (t )=X i 1(t )+F (X i 2(t )−X i 3(t )),
(1)
i =i 1=i 2=i 3,
where i =1,2,...,N p and i 1,i 2,and i 3are mutually different random integer indices within [1,N p ].The population size N p satisfies N p ≥4becau i ,i 1,i 2,and i 3are different.F ∈(0,2]is a real number that controls the amplification of the difference vector (X i 2(t )−X i 3(t )).
Crossover –Like genetic algorithms,DE also employs a crossover operator to build trial vectors (U i (t )={U i,1(t ),U i,2(t ),...,U i,D (t )})by recombining two different vectors.In this paper,we u the rand/1/exp strategy to generate the trial vectors.
Selection –A greedy lection mechanism is ud as follows:
X i (t )={
U i (t ),if f (U i (t ))≤f (X i (t ))
X i (t ),otherwi .(2)
Without loss of generality,this paper only considers min-imization problem.If,and only if,the trial vector U i (t )is better than X i (t ),then X i (t )is t to U i (t );otherwi,the X i (t )remains unchanged.
III.DE WITH V ARIABLE P OPULATION S IZE (DEVP)The population size,N p as well as other two control param-eters,Cr and F greatly affect the performance of DE [23].Choosing an appropriate population size highly affects the quality of the obtained solution and the efficiency of the
arch process.The value of N p should not be too small in order to avoid stagnation and to provide sufficient exploration.Larger N p increas the chance of arching better candidate solutions,but a larger population implies a larger number of function evaluations which retards the convergence rate.
According to newly reported results [24],a reasonable choice of the population size is between N p =3×D and N p =8×D ,where N p must be at least 4for DE/rand/1and 5for DE/best/2,to ensure that DE will have enough mutually different vectors.However,the empirical parameter studies were conducted on veral simple (low dimensions,D ≤20)benchmark functions.As dimension increas,the empirical ttings may not work.
In this paper,we propo an adaptive DE algorithm (DEVP)by employing a variable population size (
VP)mechanism,in which the population size is variable,becau the VP method can increa or decrea the number of individuals according to the arch status of current population.If the fitness value of the best individual Best does not improve in m generations (m is a predefined number),we consider that the population maybe trapped in local minima.So,that is a right time to add new individuals to the current population and break the stagnation.If the fitness value of the best individual Best improves more than once in m generations,we consider that the current population is large enough to find better candidate solutions.To accelerate the convergence speed,we can reduce the population size by deleting the worst individual from the current population.The implementation of the VP mechanism is described as follows.
∙If the fitness value of the Best does not improve in m generations,then a new individual X ∗is generated by:
X ∗=Best +F (X i 4−X i 5),
(3)
where Best is the best individual found so far,X i 4and X i 5are two different individuals,i 4and i 5are two different random integers within {1,2,...,N p },and F is the same ud as in equation (1).
If the current population size is less than max N p (the maximum value of population size),then the new individual X ∗will be added into the current population,and N p =N p +1.If the current population size is up to the maximum value (N p ==max N p ),then lect a fitter individual between X ∗and the worst individual X w in current population as the new X w .
∙If the fitness value of the Best improves more than once in m generation,and if N p is more than min N p (the minimum value of population size),then the worst individual X w in current population will be deleted,and N p =N p −1.
To illustrate the mechanism of the variable population size,Fig.1prents the changes of population size N p achieved by DEVP on function F 2(Schwefel’s Problem 2.21)with D =500provided by CEC-2008[7].The initial population size N p =60,the minimum population size min N p =50,and the maximum population size max N p =100.The
Fig.1.The changes of population size achieved by DEVP when solving Schwefel’s Problem2.21with D=500.
parameter ttings are bad on our empirical studies.From Fig.1,it can be en that the VP mechanism dynamically ad-justs the population size throughout the evolutionary process. The parameter m may affect the performance of the algorithm. According to our empirical studies,m is t to20in this paper. The framework of DEVP is shown in Algorithm1,where
P(t)is the current population,X i is the i th individual in current population,Best is the best individual found so far,
X w is the worst individual in current population,X∗is a newly generated individual,N p is the population size,min N p is the minimum population size,max N p is the maximum population size,D is the dimension size,CR∈(0,1)is the predefined crossover probability,rand j()is a random number within[0,1],FEs is the number offitness evaluations,and MAX FEs is the maximum number offitness evaluations.
IV.E XPERIMENTAL V ERIFICATIONS
A.Benchmark Functions
位置英文
There are19scalable continuous functions ud for the following experiments.Functions F1−F6were chon from thefirst six functions provided by CEC2008Special Session and Competition on Large Scale Global Optimization[7]. Functions F7−F11were propod for ISDA2009Work-shop on Evolutionary Algorithms and other Metaheuristics for Continuous Optimization Problems–A Scalability Test[25]. The rest eight functions F12−F19are hybrid composition functions built by combining two functions belonging to the t functions F1−F11.The detailed descriptions of F1−F19 can be found in[26].In this paper,we focus on investigating the optimization performance of DEVP on problems with D=50,100,200,500and1000.
B.Parameter Settings and Involved Algorithms Experiments were conducted to comparefive algorithms including DE,CHC,G-CMA-ES,GODE and the propod DEVP algorithm on the mentioned test suite.The algorithms and parameters ttings are described as follows.
Algorithm1:Differential Evolution with Variable Popu-lation Size(DEVP)
Randomly initialize each individual X i in the population P(t);
1
Calculate thefitness value of each X i;
2
FEs=N p;高考资讯
3
while FEs≤MAX FEs do
4
/*Execute the classical DE*/
for i=1to N p do
5
Randomly lect3parents X i
1
,X i2and X i3from P,where
英文名翻译
6
i=i1=i2=i3;
V i=X i1,+F(X i2−X i3);
7
U i=X i;
8
for j=0;rand j()<CR&&j<D;j++do
9
U i,j=V i,j;
10
end
11
Calculate thefitness value of U i;
12
FEs++;
13
if f(U i)≤f(X i)then
14
X i=U i
15
tpp是什么意思
buffetend
16
el
17
X i=X i;
18
end
19
end
20
/*Variable population size mechanism*/
if The Best does not improve in m generations then
21
Create a new individual X∗according to equation(3);
22
Calculate thefitness value of X∗;
23
FEs++;
24
/*Increa the population size*/
if N p<max N p then
25
N p=N p+1;
26
X N p=X∗;
27
end
28上海英语口语培训班
el
29
if f(X∗)<f(X w)then
30
X w=X∗;
31
end
32
end
33
end
34
if The Best improves more than once in m generations then
35
中大自考/*Decrea the population size*/
if N p>min N p then
36
Delete the worst individual X w in current population;
37
N p=N p−1;
38
end
39
end
40
end
41
∙DE:The classical DE model without parameter adap-tation,as the parent algorithm,is considered for the performance comparisons.The crossover operator applied is rand/1/exp.According to the latest report in[22],the results obtained on the test suite by using rand/1/exp scheme are clearly better than
the ones obtained by employing the rand/1/bin scheme.In DE,the F,Cr and N p werefixed to0.5,0.9and60,respectively.
∙CHC:The main idea of the CHC algorithm(Crossgenera-tional elitist lection,Heterogeneous recombination,and Cataclysmic mutation)[27]focus on the combination of
a high pressure lection strategy and veral components
including a strong diversity.The initial threshold is t at L
4
,where L is the length of the string(L=20∗D in the experiments).When no offspring are inrted into the new population the threshold is reduced by1.When the population converges or the arch stops making progress
(i.e.,the difference threshold has dropped to zero and no
new offspring are being generated which are better than any members of the parent population),the population is
re-initialized.The restart population consists of random individuals except for one instance of the best individual found so far.Finally,a real-parameter crossover operator, called BLX-α[28],is considered to substitute the original crossover operator.The instance of CHC us BLX-αwithα=0.5.
∙G-CMA-ES:The G-CMA-ES is a restart Covariant Ma-trix Evolutionary Strategy(CMA-ES)with Increasing Population Size[29].It detects premature convergence and launches a restart strategy that doubles the population size on each restart;by increasing the population size the arch characteristic becomes more global after each restart,which empowers the operation of the CMA-ES on multimodal functions.The parameter ttings of G-CMA-ES were the ones suggested by Auger and Hann[29].
The initial solution is uniform randomly chon from the domain and the initial distribution size(σ)is a third of the domain size.
∙GODE:For GODE[17],we u the following parameter ttings.The F,Cr and N p werefixed to0.5,0.9and 60,respectively.The probability of opposition is t to
0.05.Like DE,the rand/1/exp strategy is employed.例如的英文缩写
∙DEVP:For common parameters between DEVP and DE, the same values are ud.In DEVP,the rand/1/exp was also employed.The parameters F and Cr werefixed to
0.5and0.9,respectively.For the initial population size
(N p),the minimum population size(min N p),and the maximum population size(max N p),we ud empirical ttings in this paper,N p=60,m=20,min N p=50 and max N p=100.
In the following experiments,each algorithm is run25 times for each test function.The maximum number offitness evaluations MAX FEs is5000×D.Each run stops when the maximum number of evaluations is achieved.Throughout the experiments,the average of error of the best individual found in the25runs was recorded(For a solution x,the error measure is defined as F(x)−F(op),where op is the global optimum of the function).According to the suggestions of[22],all the results below1E–14have been approximated to0.0.
C.Numerical Results
The comparison results among DE,CHC,G-CMA-ES, GODE and DEVP on problems with D=50,D=100, D=200,D=500and D=1000are prented in Tables I,II,III,IV and V,respectively(we did n
popular的反义词ot include the results of G-CMA-ES for D=1000due to the large time for runs on some functions).The best results among thefive (four for D=1000)algorithms are shown in bold.
From the results,it can be en that DEVP outperforms DE on other four algorithms(three for D=1000)on8functions, F4,F6,F9,F11,F12,F14,F16and F18.For F1,F5,F7 (except for D=1000),F10,F15(except for D=1000)and F19,DE,GODE and DEVP can arch the global optimum. For F2and F8(except for D=1000),only G-CMA-ES canfind promising solutions,while other three algorithms
TABLE I
R ESULTS ACHIEVED BY DE,CHC,G-CMA-ES,GODE AND DEVP ON
D=50.
D=50DE CHC G-CMA-ES GODE DEVP Functions Mean Mean Mean Mean Mean F10.00E+00 1.67E–110.00E+000.00E+000.00E+00 F2 3.60E–01 6.19E+01 2.75E–11 2.57E–01 1.19E–01 F3 2.89E+01 1.25E+067.97E–01 3.06E+01 3.19E+01 F4 3.98E–027.43E+01 1.05E+02 1.05E–130.00E+00 F50.00E+00 1.67E–03 2.96E–040.00E+000.00E+00 F6 1.43E–13 6.15E–07 2.09E+
01 1.24E–140.00E+00 F70.00E+00 2.66E–09 1.01E–100.00E+000.00E+00 F8 3.44E+00 2.24E+020.00E+00 1.67E–01 4.27E–03 F9 2.73E+02 3.10E+02 1.66E+017.77E–060.00E+00 F100.00E+007.30E+00 6.81E+000.00E+000.00E+00 F11 6.23E–05 2.16E+00 3.01E+01 6.44E–060.00E+00 F12 5.35E–139.57E–01 1.88E+02 1.33E–130.00E+00 F13 2.45E+01 2.08E+06 1.97E+02 2.55E+01 2.88E+01 F14 4.16E–08 6.17E+01 1.09E+02 6.24E–09 1.64E–13 F150.00E+00 3.98E–019.79E–040.00E+000.00E+00 F16 1.56E–09 2.95E–09 4.27E+02 1.57E–10 1.62E–14 F177.98E–01 2.26E+04 6.89E+02 1.17E+00 3.11E+00 F18 1.22E–04 1.58E+01 1.31E+02 2.97E–07 1.41E–10 F190.00E+00 3.59E+02 4.76E+000.00E+000.00E+00
TABLE II
R ESULTS ACHIEVED BY DE,CHC,G-CMA-ES,GODE AND DEVP ON
D=100.
D=100DE CHC G-CMA-ES GODE DEVP Functions Mean Mean Mean Mean Mean F10.00E+00 3.56E–110.00E+000.00E+000.00E+00 F2 4.45E+008.58E+01 1.51E–10 3.65E+00 3.55E+00 F38.01E+01 4.19E+06 3.88E+008.14E+018.33E+01 F47.96E–02 2.19E+02 2.50E+028.32E–14 6.73E–02 F50.00E+00 3.83E–03 1.58E–030.00E+000.00E+00 F6 3.10E–13 4.10E–07 2.12E+01
2.60E–14 2.07E–14 F70.00E+00 1.40E–02 4.22E–040.00E+000.00E+00 F8 3.69E+02 1.69E+030.00E+007.53E+01 3.71E+01 F9 5.06E+02 5.86E+02 1.02E+02 1.46E–050.00E+00 F100.00E+00 3.30E+01 1.66E+010.00E+000.00E+00 F11 1.28E–047.32E+01 1.64E+02 1.58E–050.00E+00 F12 5.99E–11 1.03E+01 4.17E+027.57E–12 5.72E–14 F13 6.17E+01 2.70E+06 4.21E+02 6.32E+01 6.22E+01 F14 4.79E–02 1.66E+02 2.55E+02 4.13E–08 1.23E–12 F150.00E+008.13E+00 6.30E–010.00E+000.00E+00 F16 3.58E–09 2.23E+018.59E+02 3.75E–108.55E–14 F17 1.23E+01 1.47E+05 1.51E+03 1.11E+01 1.03E+01 F18 2.98E–047.00E+01 3.07E+02 1.11E–06 5.88E–10 F190.00E+00 5.45E+02 2.02E+010.00E+000.00E+00
TABLE III
R ESULTS ACHIEVED BY DE,CHC,G-CMA-ES,GODE AND DEVP ON
D=200.
D=200DE CHC G-CMA-ES GODE DEVP Functions Mean Mean Mean Mean Mean F10.00E+008.34E–010.00E+000.00E+000.00E+00 F2 1.92E+01 1.03E+02 1.16E–09 1.53E+01 2.92E+01 F3 1.78E+02 2.01E+078.91E+01 1.80E+02 1.93E+02 F4 1.27E–01 5.40E+02 6.48E+02 4.17E–130.00E+00 F50.00E+008.76E–030.00E+000.00E+000.00E+00 F6 6.54E–13 1.
23E+00 2.14E+01 5.45E–14 4.91E–14 F70.00E+00 2.59E–01 1.17E–010.00E+000.00E+00 F8 5.53E+039.38E+030.00E+00 2.10E+03 1.21E+04 F9 1.01E+03 1.19E+03 3.75E+02 3.23E–050.00E+00 F100.00E+007.13E+01 4.43E+010.00E+000.00E+00 F11 2.62E–04 3.85E+028.03E+02 3.12E–050.00E+00 F129.76E–107.44E+019.06E+02 1.20E–10 1.28E–13 F13 1.36E+02 5.75E+069.43E+02 1.38E+02 1.37E+02 F14 1.38E–01 4.29E+02 6.09E+028.17E–02 3.36E–12 F150.00E+00 2.14E+01 1.75E+000.00E+000.00E+00 F167.46E–09 1.60E+02 1.92E+039.54E–10 1.20E–13 F17 3.70E+01 1.75E+05 3.36E+03 3.74E+01 3.94E+01 F18 4.73E–04 2.12E+02 6.89E+02 1.91E–06 1.67E–09 F190.00E+00 2.06E+037.52E+020.00E+000.00E+00
(a)F1(D=1000)
(c)F9(D=1000)(d)F16(D=1000) Fig.2.The average convergence curves of DEVP on F1,F6,F9and F16with D=1000.
TABLE IV
R ESULTS ACHIEVED BY DE,CHC,G-CMA-ES,GODE AND DEVP ON
D=500.
D=500DE CHC G-CMA-ES GODE DEVP Functions Mean Mean Mean Mean Mean F10.00E+00 2.84E–120.00E+000.00E+000.00E+00
F2 5.35E+01 1.29E+02 3.48E–04 5.81E+017.23E+01
F3 4.76E+02 1.14E+06 3.58E+02 4.76E+02 4.75E+02
F4 3.20E–01 1.91E+03 2.10E+03 1.62E–039.22E–03
F50.00E+00 6.98E–03 2.96E–040.00E+000.00E+00
F6 1.65E–12 5.16E+00 2.15E+01 1.43E–13 1.37E–13
F70.00E+00 1.27E–017.21E+1530.00E+000.00E+00
F8 6.09E+047.22E+04 2.36E–06 3.93E+04 1.11E+05
F9 2.52E+03 3.00E+03 1.74E+037.84E–050.00E+00 F100.00E+00 1.86E+02 1.27E+020.00E+000.00E+00 F11 6.76E–04 1.81E+03 4.16E+038.25E–050.00E+00 F127.07E–09 4.48E+02 2.58E+037.39E–10 2.65E–13
F13 3.59E+02 3.22E+07 2.87E+03 3.59E+02 3.60E+02
F14 1.35E–01 1.46E+03 1.95E+037.67E–02 4.94E–02 F150.00E+00 6.01E+01 2.82E+2620.00E+000.00E+00 F16 2.04E–089.55E+02 5.45E+03 2.24E–09 4.68E–13
F17 1.11E+028.40E+059.59E+03 1.12E+02 1.29E+02
F18 1.22E–037.32E+02 2.05E+03 5.06E–06 4.89E–09
F190.00E+00 1.76E+03 2.44E+060.00E+000.00E+00
fail to solve them.For the rest of three functions,F3,F13 and F17,all thefive algorithms can hardly a
rch reasonable results.For F7and F15,DEVP as well as GODE cannot solve them when the dimension increas to1000.The main reason is that thefitness values of the two functions are larger than the maximum value(10308)that double precision
TABLE V
R ESULTS ACHIEVED BY DE,CHC,GODE AND DEVP ON D=1000.
D=1000DE CHC GODE DEVP
Functions Mean Mean Mean Mean
纳尼亚传奇3主题曲F10.00E+00 1.36E–110.00E+000.00E+00
F28.46E+01 1.44E+029.02E+01 1.02E+02
F39.69E+028.75E+039.70E+029.70E+02
F4 1.44E+00 4.76E+03 1.03E+00 4.52E–01
F50.00E+007.02E–030.00E+000.00E+00
F6 3.29E–12 1.38E+01 2.88E-13 2.86E–13
F70.00E+00 3.52E–01INF INF
F8 2.46E+05 3.11E+05 1.86E+05 4.18E+05
F9 5.13E+03 6.11E+03 1.70E–040.00E+00
F100.00E+00 3.83E+020.00E+000.00E+00
F11 1.35E–03 4.82E+03 1.73E–040.00E+00
F12 1.68E–08 1.05E+03 1.87E–09 5.39E–13
F137.30E+02 6.66E+077.31E+027.31E+02
F14 6.90E–01 3.62E+03 6.06E–01 1.52E–01
F150.00E+008.37E+01INF INF
F16 4.18E–08 2.32E+03 4.59E–099.69E–13
F17 2.36E+02 2.04E+07 2.36E+02 2.43E+02
F18 2.37E–03 1.72E+03 3.29E–05 1.17E–08
F190.00E+00 4.20E+030.00E+000.00E+00
float number can reprent.This problem can be solved by using higher precision data types,such as“long double”in C/C++.Although we ud“long double”to reprent the fitness value,DEVP was implemented in Microsoft Visual C++6.0,which us the same size of bytes(8bytes)to reprent“double”and“long double”.So,we did not list the
