Enhancing Differential Evolution Performance with Local
Search for High Dimensional Function Optimization
Nasimul Noman

Hitoshi Iba

Graduate School of Frontier Sciences
The University of Tokyo

Graduate School of Frontier Sciences
The University of Tokyo

noman@iba.k.u-tokyo.ac.jp

iba@iba.k.u-tokyo.ac.jp

ABSTRACTIn this paper, we proposed Fittest Individual Reﬁnement(FIR), a crossover based local search method for Diﬀerential Evolution (DE). The FIR scheme accelerates DE byenhancing its search capability through exploration of theneighborhood of the best solution in successive generations.
The proposed memetic version of DE (augmented by FIR) is
expected to obtain an acceptable solution with a lower number of evaluations particularly for higher dimensional functions. Using two diﬀerent implementations DEﬁrDE andDEﬁrSPX we showed that proposed FIR increases the convergence velocity of DE for well known benchmark functions
as well as improves the robustness of DE against variation of
population. Experiments using multimodal landscape generator showed our proposed algorithms consistently outperformed their parent algorithms. A performance comparison
with reported results of well known real coded memetic algorithms is also presented.
Categories and Subject Descriptors: G.1.6 [Problem
Solving, Control Methods, and Search]: Heuristic methods
General Terms: Algorithms, Experimentation, Performance.
Keywords: Diﬀerential Evolution, Local Search, Memetic
Algorithm, Function Optimization, Landscape Generator.

1.

INTRODUCTION

In last few decades Evolutionary Algorithms (EAs) havebecome very popular as function optimizers, because they
are easy to implement, and exhibit fair performance for awide range of functions. However, continued developmentin the community has established that pure Genetic Algorithms (GAs) are often not good enough for ﬁne tuning
in complex search spaces. As well as new developments
have shown that hybridization with other strategies, such as
metaheuristics or local searches, can improve the eﬃciencyof search [2, 3]. GAs hybridized with local reﬁnement procedures are known as Memetic Algorithms (MAs) [10, 11].

MAs are population based heuristic search approaches for
optimization problems closely related to GAs [9]. One MA
model that has received attention uses crossover based local search (XLS) procedure. This is particularly attractive
for real-coding since there are real-parameter crossover operators that have a self-adaptive nature in that they cangenerate oﬀspring adaptively according to the distributionof parents without any adaptive parameter [1]. This kind ofcrossover operator shows promise for building eﬀective XLS.
Diﬀerential Evolution (DE) is an eﬀective, eﬃcient and robust optimization method [14] capable of handling nonlinear
and multimodal objective functions. The beauty of DE is its
simple and compact structure which uses a stochastic direct
search approach and utilizes common concepts of EAs. Furthermore DE uses few, easily chosen, parameters and works
surprisingly very reliably with excellent overall results overa wide set of benchmark and real-world problems. Experimental results have shown that DE has good convergenceproperties and outperforms other well known EAs [14, 13].
Despite having a relatively high convergence performancein comparison with the other EAs for nonlinear optimization of multi-modal functions, DE’s convergence velocity is
still low for optimizing computationally most expensive objective functions, specially at higher dimensions. In this paper, DE algorithm has been hybridized with XLS strategies
in an attempt to accelerate the convergence velocity of DE
so that better solutions can be obtained with higher speed
and increased robustness. The paper is organized as follows.
In the next section we brieﬂy focus on several MA models
with their properties and review DE. In Section 3, our proposed Fittest Individual Reﬁnement (FIR) strategy and thememetic version of DE is presented. Section 4 reports experiments with benchmark functions. Simulations using alandscape generator are presented in Section 5. Finally Section 6 summarizes the ﬁndings of our work and concludes.

2. XLS BASED MA AND DE
2.1 XLS Based Memetic Algorithms (MAs)
MAs are evolutionary algorithms that apply a separate
Local Search (LS) process to reﬁne individuals, e. g. to improve their ﬁtness. MAs are motivated to provide an eﬀective global optimization method by taking advantage of boththe exploration abilities of GA and the exploitation abilities
of LS. MAs have evolved in mainly two groups depending on
the type of LS employed, namely Local Improvement Process(LIP) and Crossover based LS (XLS) [8]. The ﬁrst category
reﬁnes the solutions of each generation by applying eﬃcient

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.
GECCO’05, June 25–29, 2005, Washington, DC, USA
Copyright 2005 ACM 1-59593-010-8/05/0006 ...$5.00.

967

3. DE WITH CROSSOVER BASED LS

LIPs e.g. hill-climbers. LIPs can be applied to every member of population or with some speciﬁc probability and withvarious replacement strategies.
The other group employs crossover operators for local reﬁnement. A crossover operator is recombination operator
that produces oﬀspring around the parents. For this reason,
it may be considered to be a move operator for LS strategy. Moreover now there are many sophisticated crossover
operators that can generate oﬀsprings adaptively according
to the distribution of parents without any adaptive parameter. So they can be employed to create oﬀspring distributed
densely around the parents, favoring local tuning. The mostcommon examples of XLS based MAs in literature are Minimal Generation Gap (MGG) [4] and Generalized Generation
Gap (G3) [5]. Both of them employ same parents to spawn
multiple oﬀsprings. The idea is to induce an LS on theneighborhood of the parents involved in crossover. In thisway, this type of crossover operators constitute an XLS [8].

As mentioned earlier in Section 2.1, XLS are applied tosearch the neighborhood of the parents locally to improve
the parents. We have applied the same strategy to the neighborhood of a single individual. In other words we can say weused XLS for exploring the neighborhood of an individualby mating it repeatedly with diﬀerent individuals. A similar model of XLS has been proposed by Yang and Kao [16]where they search the neighborhood of each individual andthey have named it Family Competition (FC).
In our proposed scheme of DE with XLS the basic DE(DE/rand/1/exp) is extended by applying some crossoverbased local search (XLS) to search the neighborhood of thebest individual. That is in our XLS procedure the bestindividual xbest
G becomes the family father and its family is
explored. This family father and other individual(s), randomly chosen from the rest of the current population, aremated to generate oﬀspring. And this procedure is repeated
L times. Finally, L solutions (C1 , C2 , · · · , CL ) are produced
and among these oﬀsprings and family father xbest
the inG
dividual with the best score replaces the family father innext generation. We call it crossover based local search forFittest Individual Reﬁnement (FIR). In this paper we haveaugmented DE algorithm by applying FIR in the general
template of MA and call it DEFIR. The formal algorithm
for DEFIR can be described, as follows

2.2 Differential Evolution (DE)DE is a stochastic search algorithm, related to Evolutionary Computation (EC), which exploits a population ofpotential solutions, individuals, to probe the search space.
New individuals are generated by combination of randomly
chosen individuals from the population. Speciﬁcally, foreach individual xiG , i = 1, · · · , N , where G denotes the curi
is generated accordrent generation, a new individual yG+1
ing to the following equationiyG+1= xjG + F (xkG − xlG )1. Randomly Initialize the population PG
2. REP EAT U ntil Search Converged

(1)

3.

PG+1 = {φ}where j, k and l are random integers such that j, k andl {1, · · · , N } and i = j = k = l and F is called scaling factor
or ampliﬁcation factor. This operation is similar to what iscommonly known as mutation to EC community. In orderiisto achieve higher diversity the mutated individual yG+1i
mated with xG using a crossover operation to generate theoﬀspring or trial individual xiG+1 . The genes of xiG+1 are ini
herited from xiG and yG+1
determined by a parameter calledcrossover factor (CF ) which regulates how many consecutive genes of the mutated individual on average are copied tothe oﬀspring. Finally the oﬀspring is evaluated and replaces
its parent xiG in next generation if and only if its ﬁtness isbetter than that of its parent. This is the selection process.
The above scheme is not the only variant of DE whichhas proven to be useful. In order to distinguish among its
variants the notation DE/a/b/c is used, where  a speciﬁes the vector to be mutated which can be random or thebest vector;  b is the number of diﬀerence vectors used and 
c denotes the crossover scheme, binomial or exponential.
Using this notation the DE-strategy described above canbe denoted as DE/rand/1/exp. Other well known variants
are DE/best/1/exp, DE/rand/2/exp and DE/best/2/exp
which can be implemented by simply replacing equation (1)by the equation (2), (3) and (4) respectively. Also each ofthem has a mate based on binomial crossover.

4.

REP EAT f or each individual I PGi= xbest+ F (xjG − xkG )
yG+1
G

(2)

i
n
yG+1
= xjG + F (xkG − xlG ) + F (xmG − xG )

(3)

i
yG+1
= xbest+ F (xjG − xkG ) + F (xlG − xm
G
G)

(4)

5.
6.

REP RODU CE I  f rom I
PG+1 = PG+1
Best(I, I  )7.

EN DREP EAT

8.

PG+1 = F IR(PG+1 )9. EN DREP EAT
The only structural diﬀerence between basic DE and DEFIR algorithm is application of FIR in each generation forreﬁning the best individual. Now for implementing FIR, currently we propose two schemes: DEﬁrDE and DEﬁrSPX.
In DEﬁrDE scheme, the oﬀspring is generated in the same
way oﬀspring generated in DE/rand/1/exp. In each genwe select three indieration G for the best individual xbest
Gviduals xjG , xkG and xlG such that j, k and l {1, · · · , N } andiis genbest = j = k = l. Then a mutated individual yG+1
erated using equation (1). Finally the oﬀspring C is generated by crossover operation between mutated individualiand the best individual xbest
yG+1
G . This procedure is repeated L times and then selection is performed.
On the other hand DEﬁrSPX scheme generates the oﬀspring using simplex crossover (SPX) operation [12]. To
review, SPX operator uses multi-parent, p parental vectors,
for recombination as follows
1. Choose p parents xiG , i = 1, · · · , p according to thegenerational model used (G denotes the generation)and calculate their center of mass O
p
1 i
O=
x
(5)
p i=1 G

represents the best individual in current generwhere, xbest
Gation and m and n {1, · · · , N } and i = j = k = l = m = n.

968




n
1 
fAck (.
x) = 20 + exp(1) − 20exp −0.2
x2 n i=1 i

2. Generate random numbers ri
1

ri = u i+1 , (i = 1, · · · , p − 1)(6)1cos(2πxi )n i=1nwhere u is a uniform random number− exp[0, 1]− 32.768 ≤ xi ≤ 32.768;

3. Calculate yi and CiCi =yi = O + ε(xiG − O),∗fAck= fAck (0, · · · , 0) = 0(i = 1, · · · , p) (7)0,(i = 1)ri−1 (yi−1 − yi + Ci−1 ), (i = 2, · · · , p)

(8)
x) =
fGrw (.

where ε is expansion rate, a control parameter of SPX.

n
n

xi
x2i
cos √ + 1
−
4000
i
i=1
i=1
∗
fGrw
= fGrw (0, · · · , 0) = 0− 600 ≤ xi ≤ 600;

4. Generate an oﬀspring C
C = yp + Cp

(9)x) = 10n +fRas (.

− 5.12 ≤ xi ≤ 5.12;x) =fRos (.

(100(xi+1 − x2i )2 + (1 − xi )2 )∗fRos
= fRos (1, · · · , 1) = 0

fSph and fRos are unimodal functions on the other hand
fAck , fGrw and fRas are multimodal functions. f ∗ denotes
the global minimum for the function.

4.2 Experimental Setup
In our ﬁrst set of experiments we investigated the performance of DE, DE(best), DEﬁrDE, DEﬁrSPX for the benchmark functions mentioned above. Targeting high dimensional optimization, dimensions of the search spaces werechosen as 50, 100 and 200. In order to make the performancecomparison fairer we used the same sets of initial random
populations for evaluating all algorithms. Each experiment
was repeated 30 times. Maximum number of evaluations
allowed for each algorithm was 500, 000. For DEs we chose
most commonly used parameter setting and did not tune
to best parameter values for each problem. The value of
F was set to 0.5 and CF was chosen 0.8. Based on somepreliminary experiments, for FIR algorithms, L = 25 whenpopulation size P ≤ 200 otherwise L = 50, was chosen. The
performance of DE variants is highly dependent on the chosen population size. Therefore to investigate the sensitivity of the proposed algorithms to the change of population
size we experimented with three diﬀerent population sizes
P = N , P = 5N and P = 10N , where N is the dimensionof the problem. For simplex crossover operation number ofparents p = 3 was chosen.
We evaluated the algorithms by calculating average (AVG)and standard deviation (SD) of their attained minimum ﬁtness value within the maximum number of allowed evaluations. If the ﬁtness value was less than 10−6 range of actual
optimum point, we assume solution is detected. The experiments were performed on a computer with 1700 MHz
Intel Pentium processor and 512 MB of RAM in JBuilder X
environment.

4.1 Test Suite
We use 5 test functions commonly used in the literature,
which includes Sphere model (fSph ), Ackley function (fAck ),Griewank’s function (fGrw ), Generalized Rastrigin’s function (fRas ) and Generalilzed Rosenbrock’s function (fRos ).
All benchmarks chosen are minimization problems. The definitions of the functions are as follows
x2i ,

i=1

− 100 ≤ xi ≤ 100;∗fRas
= fRas (0, · · · , 0) = 0

i=1

EXPERIMENTS

n


n−1


− 50 ≤ xi ≤ 50;

In our experiments, we investigate the performance ofthe proposed DEﬁrDE and DEﬁrSPX algorithms comparing
with DE/rand/1/exp (DE) and DE/best/1/exp (DE(best))
algorithms. As mentioned in Section 3 DEﬁrDE and DEﬁrSPX algorithms are implemented by augmenting FIR with
DE/rand/1/exp. A brief performance comparison is also
performed by comparing the proposed algorithms with some
reported results of other Real Coded Genetic Algorithms(RCGAs) and Real Coded Memetic Algorithms (RCMAs).

fSph (.
x) =x2i − 10 cos(2πxi )i=1

In DEﬁrSPX scheme we select the best individual and other(p − 1) random individuals from current generation. Then
SPX is applied on these p parents to generate oﬀspring. Selection is performed after repeating this procedure L times.
The justiﬁcation for the design of DEFIR is as follows.
The basic strategy of EAs is many points, few neighbors, i.e.
they work by searching the single neighborhood of multiple
individuals in parallel over successive generations of populations. On the other hand the XLS based MAs work with few
points, many neighbors strategy, i.e. they work by searching
on a greater neighborhood of one individual in successive
generations. DE applies a more directive search in a greedy
way. Augmenting this FIR process in the structure of DE wemake the search more directive or greedier in a sense. With
the progress of the search by exploring the neighborhood of
the best individual we hope to ﬁnd the global optimal at ahigher speed. This is similar to few points, many neighbors
strategy but a greedier one. Hence analogously it can becalled best point neighborhood strategy.

4.

n


∗
fSph
= fSph (0, · · · , 0) = 0969

1.E+2
1.E+1DE
DE(best)DEfirDE
DEfirSPX

1.E+0
1.E-1

Fitness

The second set of experiments was conducted to compare
proposed algorithms with some other real coded GAs andMAs proposed in the literature. Comparison was performed
with some of the results reported by Lozano et al. in theirwork [8]. The performance of DE, DE(best), DEﬁrDE, DEﬁrSPX were compared with CHC algorithm, Generalized
Generation Gap(G3 − 1), hybrid steady-state RCMA (SW100), Family Competition (FC) and RCMA with crossover
Hill Climbing (RCMA-XHC). For these experiments the setup
of parameters were as follows, N = 25, P = 60, L = 15, F = 0.5,
CF = 0.8 and number of maximum evaluations 100, 000.

1.E-2
1.E-3
1.E-4
1.E-5
1.E-6
1.E-7
0

1000002000004.3 Results

300000400000500000

Number of evaluations

Results of our ﬁrst set of experiments are reported in Table 1. For each function the results are arranged as AVG± SD (Number of Convergence). In all ﬁgures, the graphs
represent the mean of the best evaluation in 30 runs. Because of limited space, only some representative graphs fordiﬀerent functions are presented.
As shown in Table 1, for (fSph , fAck , fGrw and fRas ) functions DEﬁrDE and DEﬁrSPX succeeded to reach the optimal value in all trials for some cases in which DE and/orDE(best) failed in all trails or at least in some trials. Even incases, where DE or DE(best) could reach the optimal value
in all trails they took higher number of evaluations comparedto that needed for DEﬁrDE or/and DEﬁrSPX. This can be
veriﬁed looking at the graphs of Figure 1, 5, 6, 7 and 8. And
if we look at cases where none of the four schemes could
hit the global optimal, we ﬁnd that the proposed DEﬁrDE
and DEﬁrSPX scheme attained AVGs which are signiﬁcantly
better than that achieved by their parent algorithms (Figure
2, 3, 4, 9 and 10). For example in Rosenbrock function noneof the above schemes were able to reach the optimal within
the maximum number of evaluations. But in all experiments
DEﬁrDE and/or DEﬁrSPX were able to reach the minimum
ﬁtness values. Another observation from Table 1 is, with
the increase of dimension, the performance diﬀerence between proposed schemes and their parent schemes becomes
more signiﬁcant. And this testiﬁes our claim that the proposed FIR schemes will speedup DE for higher dimensional
function optimization.
If we look at the graphs of Figure 1 to 10, then it is foundthat in every case DEﬁrSPX started with the steepest convergence curve but in some cases, with the progress of thesearch it becomes ﬂattened. This is because at the beginningof the search SPX performs local searching using individuals randomly scattered in the search space and becomes very
successful in generating oﬀspring with high ﬁtness, but atlater generations it generates individuals densely around the
populations which slows down the eﬀect of local search. On
the other hand DEﬁrDE strategy, makes use of the operatorsof DE, starts slowly compared to DEﬁrSPX but continue toimprove the ﬁtness to the end of the search and in later
generations approaches to DEﬁrSPX steadily (Fig 2, 3, 4, 9
and 10). Though for both multimodal (fGrw , fRas , fAck )and unimodal (fSph , fRos ) functions DEﬁrDE and DEﬁrSPX exhibited superior performance, results show that they
were more eﬀective to multimodal functions compared tounimodal one.
Storn and Price suggested a larger population size (between 5N to 10N) for DE [14], although later many others
found DE’s performance good even with a smaller population. To check the sensitivity of the proposed schemes to the

Figure 1: Sphere Function N = 100 P = 100
200
180
160
140

Fitness

120
100

DE
DE(best)DEfirDE
DEfirSPX

80
60
40
20
0
0

100000200000300000400000500000

Number of evaluations

Figure 2: Sphere Function N = 100 P = 1000
76DE
DE(best)DEfirDE
DEfirSPX

Fitness

5

4

3

2

1

0
0

100000200000300000400000500000

Number of evaluations

Figure 3: Ackley Function N = 200 P = 200
20

Fitness15

10DE
DE(best)DEfirDE
DEfirSPX

500100000200000300000400000500000

Number of evaluations

Figure 4: Ackley Function N = 200 P = 1000

970

Table 1: AVG ± SD (Number of Convergence) of final results for fSph , fAck , fGrw , fRas and fRos
NP
DE
DE(best)
DEﬁrDE
DEﬁrSPX
N
0±0 (30)
309.74±481.05 (0)0±0 (30)0±0 (30)505N
0±0 (30)0±0 (30)0±0 (30)0±0 (30)
10N
0.0535±0.0520 (0)0.0027±0.0013 (0)0.0026±0.0023 (0)1.0E-4±4.75E-5 (0)N
1.58E-6±3.75E-6 (28)0.0046±0.0247 (28)0±0 (30)0±0 (30)
fSph 100 5N
59.926±16.574 (0)30.242±5.93 (0)11.731±5.0574 (0)1.2614±0.4581 (0)10N
2496.82±246.55 (0)1729.40±172.28 (0)358.57±108.12 (0)104.986±22.549 (0)N
50.005±16.376 (0)26.581±7.4714 (0)17.678±9.483 (0)0.8568±0.2563 (0)200 5N
5.45E4±2605.73 (0)4.84E4±1891.24 (0)9056.0±1840.45 (0)2782.32±335.69 (0)10N
1.82E5±6785.18 (0)1.74E5±6119.01 (0)44090.5±6122.35 (0)9850.45±1729.9 (0)N
0 ±0 (30)0.2621 ± 0.5524 (1)0 ± 0 (30)0 ± 0 (30)50
5N
9.36E-6 ±3.67E-6 (0)6.85E-6 ± 6.06E-6 (0)2.28E-5 ± 1.45E-5 (0)3.0E-6 ± 1.07E-6 (0)10N
0.0104 ±0.0015 (0)0.0067 ± 0.0015 (0)0.0060 ± 0.0015 (0)0.0019 ± 4.32E-4 (0)N
1.02E-6 ±1.6E-7 (24)
9.5E-7 ± 1.1E-7 (29)
1.2E-6 ± 6.07E-7 (22)0 ±0 (30)fAck 100 5N
1.6761±0.0819 (0)1.2202±0.0965 (0)0.5340±0.1101 (0)0.3695±0.0734 (0)10N
7.7335±0.1584 (0)6.7251±0.1373 (0)3.7515±0.2773 (0)3.4528±0.1797 (0)N
0.5208±0.0870 (0)0.4322 ±0.0427 (0)0.3123±0.0426 (0)0.1589±0.0207 (0)200 5N
15.917±0.1209 (0)15.46±0.1205 (0)9.2373±0.4785 (0)6.6861±0.3286 (0)10N
19.253±0.0698 (0)19.138±0.0772 (0)14.309±0.3706 (0)9.4114±0.4581 (0)N
0 ± 0 (30)0.1651 ± 0.2133 (0)0 ± 0 (30)0 ± 0 (30)50
5N
9.95E-7 ± 4.3E-7 (29)0 ± 0 (30)0 ± 0 (30)0 ± 0 (30)10N
0.0053 ± 0.010 (0)0.0012 ± 0.0028 (0)4.96E-4 ± 6.68E-4 (0)5.27E-4 ± 0.0013 (0)N
0 ± 0 (30)0 ± 0 (30)0 ± 0 (30)0 ± 0 (30)fGrw 100 5N
1.1316 ± 0.0124 (0)1.0530 ± 0.0100 (0)0.7725 ± 0.1008 (0)0.5433 ± 0.1331 (0)10N
20.037 ± 0.9614 (0)13.068 ± 0.8876 (0)3.7439 ± 0.7651 (0)2.2186 ± 0.3010 (0)N
0.7687 ± 0.0768 (0)0.5707 ± 0.0651 (0)0.5984 ± 0.1419 (0)0.1631 ± 0.0314 (0)200 5N
490.29 ± 21.225 (0)441.97 ± 15.877 (0)78.692 ± 11.766 (0)28.245 ± 4.605 (0)10N
1657.93 ± 47.142 (0)1572.51 ± 53.611 (0)368.90 ± 41.116 (0)85.176 ± 12.824 (0)N
0 ± 0 (30)0.61256 ± 1.1988(8)0 ± 0 (30)0 ± 0 (30)50
5N
0 ± 0 (30)0 ± 0 (30)0 ± 0 (30)0 ± 0 (30)10N
0 ± 0 (30)0 ± 0 (30)0 ± 0 (30)0 ± 0 (30)N
0 ± 0 (30)0 ± 0 (30)0 ± 0 (30)0 ± 0 (30)fRas 100 5N
2.6384 ± 0.7977 (0)0.7585 ± 0.2524 (0)0.1534 ± 0.1240 (0)0.0094 ± 0.0068 (0)10N
234.588± 13.662 (0)198.079 ± 18.947 (0)17.133 ± 7.958 (0)27.0537 ± 20.889 (0)N
0.4245 ± 0.2905 (0)0.2255 ± 0.1051 (0)0.1453 ± 0.2771 (0)0.0024 ± 0.0011 (0)200 5N
1878.61± 60.298 (0)1761.55 ± 43.3824 (0)352.93 ± 46.11 (0)369.88 ± 136.87 (0)10N
5471.35± 239.67 (0)5094.97 ± 182.77 (0)1193.83± 145.477 (0)859.03± 99.76 (0)N
79.8921 ± 102.611 (0)3.69E5 ± 5.011E5 (0)72.0242 ± 47.1958 (0)65.8951 ± 37.8933 (0)50
5N52.4066 ± 19.9109 (0)54.5985 ± 25.6652 (0)53.1894 ± 26.1913 (0)45.8367 ± 10.2518 (0)10N 90.0213 ± 33.8734 (0)58.1931 ± 9.4289 (0)66.9674 ± 23.7196 (0)52.0033 ±13.6881 (0)N
120.917 ± 41.8753 (0)178.465 ± 60.938 (0)107.5604 ± 28.2529 (0)99.1086 ± 18.5735 (0)fRos 100 5N
12312.16± 3981.44 (0) 7463.633 ± 2631.92 (0) 2923.108 ± 1521.085 (0)732.85 ± 142.22 (0)10N 3.165E6 ± 6.052E5 (0) 1.798E6 ± 3.304E5 (0)2.822E5 ± 3.012E5 (0)16621.32 ± 6400.43 (0)N
9370.17 ± 3671.11 (0)6725.48 ± 1915.38 (0)5302.79 ± 2363.74 (0)996.69 ± 128.483 (0)200 5N
4.22E8 ± 3.04E7 (0)3.54E8 ± 3.54E7 (0)2.39E7 ± 6.379E6 (0)1.19E6± 4.10E5 (0)10N
3.29E9 ± 2.12E8 (0)3.12E9 ± 1.65E8 (0)3.48E8 ±1.75E8 (0)1.21E7 ± 4.73E6 (0)Func

Table 2: Comparison with other RCMA models
Algorithm
Griewank Rastrigin Rosenbrock
CHC
6.5E-003 1.6E+001
1.9E+001
G3-1
5.1E-001 7.4E+001
2.8E+001
SW-1002.7E-002 7.6E+000
1.0E+001
FC
3.5E-004 5.5E+000
2.3E+001
RCMA-XHC 1.3E-002 1.4E+000
2.2E+000DE
5.1E-003
1.5E-007
3.4E+002
DE(best)8.4E-002
6.0E-001
3.0E+004
DEﬁrDE
2.1E-003
1.8E-015
2.9E+002
DEﬁrSPX
7.6E-005
3.9E-012
6.1E+001

971

1.E+5

1E+0

9.E+4
1E-1
8.E+4
DE
DE(best)DEfirDE
DEfirSPX

1E-3

7.E+4
6.E+4

Fitness

Fitness

1E-2

1E-4

5.E+4
DE
DE(best)DEfirDE
DEfirSPX

4.E+4
3.E+4

1E-5

2.E+4
1E-6
1.E+4
0.E+0

1E-7
0

1000002000003000004000000500000100000200000300000400000500000

Number of evaluations

Number of evaluations

Figure 9: Rosenbrock Function N = 100 P = 500

Figure 5: Griewank Function N = 50 P = 50
1E+1

1.E+7

DE
DE(best)DEfirDE
DEfirSPX

1E+0
1E-1

9.E+6
8.E+6
7.E+6
6.E+6

Fitness

Fitness

1E-2
1E-3
1E-4

5.E+6
4.E+6
DE
DE(best)DEfirDE
DEfirSPX

3.E+6

1E-5

2.E+6

1E-6

1.E+6

1E-7
0

1000002000003000004000000.E+05000000

Number of evaluations

100000200000300000400000500000

Number of evaluations

Figure 6: Griewank Function N = 50 P = 250

Figure 10: Rosenbrock Function N = 100 P = 1000

1.E+0

1.E-1

Fitnessvariation of population size we experimented with three different population sizes (P=N, P=5N and P=10N) for eachdimension and function and the results are reported in Table
1. In our study we found that for high dimensional optimization if the maximum number of evaluation is ﬁxed then the
choice of population size may be crucial for the performanceof DE and DE(best). For example in most cases when we
found convergence for all 30 trails with a smaller population
size (say P=N), we failed to reach even a single convergencewith much high population size (say P = 10N). In our study
we found that DE works better with a population size nearto dimension of the problem (in our case P=N), but in somecases performance of DE(best) is better with a medium sized
population (in our case P=5N). Since DEﬁrDE and DEﬁrSPX is just an augmentation of basic DE with XLS, it isexpected that their sensitivity to the variation of population will be more or less similar to basic DE and the resultsof Table 1 show that. However we found the performance ofDEﬁrDE and DEﬁrSPX less susceptible to population variation compared to that of DE or DE(best) (Table 1). So it
can be stated that use of FIR has increased the robustnessof DE against the variation of population size.
Table 2 compares the result of our second set of experiments with results reported in [8]. Here the values are theaverage (over 30 runs) of the best ﬁtness function found at
the end of each run. In case of Griewank and Rastrigin function the proposed DEﬁrDE and DEﬁrSPX was better thanother algorithms. In case of Rosenbrock function other RCMAs’ performances were better than that of all DE basedalgorithms, but the results of DEﬁrDE and DEﬁrSPX areDE
DE(best)DEfirDE
DEfirSPX

1.E-2

1.E-3

1.E-4

1.E-5

1.E-6

1.E-7
0

100000200000300000400000500000

Number of evaluations

Figure 7: Rastrigin Function N = 50 P = 250
1.E+0

1.E-1

Fitness

1.E-2

1.E-3

1.E-4

DE
DE(best)DEfirDE
DEfirSPX

1.E-5

1.E-6

1.E-7
0

100000200000300000400000500000

Number of evaluations

Figure 8: Rastrigin Function N = 50 P = 500

972

200

400

180

350

160

DE
DEbestDEfirDE
DEfirSPX

120

250

Fitness

Fitness

140

DE
DEbestDEfirDE
DEfirSPX

300

100
80

200
150

60
100

40
50

20
0

0

0

1000002000003000004000005000000

Number of evaluations

100000200000300000400000500000

Number of evaluations

Figure 11: Mean Performance of the algorithms for
P = 200 N = 100

Figure 12: Mean Performance of the algorithms for
P = 200 N = 200

comparable to that of other RCMAs. One further point
about this second sets of experiments, the performances of
DEﬁrDE and DEﬁrSPX were better than that of DE andDE(best) for all test functions just like in the other set ofexperiments.

i.e. all the variables are restricted to the interval [0.0, 1.0]
with a logistic transformation included as sigmoid. We haveadapted the ﬁtness function in our experiments excluding
the sigmoid function as follows
N


1 P
j 2
f (.
x) =
min
(xj − Pi )(11)
N i=1 j=1

5.

EXPERIMENT WITH LANDSCAPE GENERATOR

We have chosen the peaks in a wider interval [-50, 50] andallow the variables to range in this interval. So the ﬁtness
value is decided by the distance between the individual to beevaluated and the closest peak. The purpose of the searchis to minimize the ﬁtness value and the minimum value iszero. In our experiment we employed this multimodality
generator to investigate the eﬀects of number of peaks (P)and problem dimension (N) on the performance of four algorithms, DE, DE(best), DEﬁrDE and DEﬁrSPX. We studied four scenarios (N = 100, P = 100), (N = 100, P = 200),(N = 200, P = 100) and (N = 200, P = 200). For each setting of N and P, 20 random problems were generated on eachof which each algorithm was run once. Like other experiments, all algorithms were evaluated using same random initial population. The parameter settings were P = N, L = 25
and the rest of the parameters were just as before. Each algorithm was allowed to evolve for maximum 500,000 times.
As expected, all of the algorithms interacted with time,
problem dimension and problem diﬃculty. However theirrelative performance for each set of (N, P) was more or lessconsistent. Because of space, results of two experiments areshown in Figure 11 and 12. Although performance of all thealgorithms faded with time, starting with a steeper curve
DEﬁrDE and DEﬁrSPX attain better ﬁtness compared to
DE and DEbest. The most notable impact on the performance of the algorithm was the dimensionality of the problem. With increasing number of peaks the performance of
all algorithms deteriorated except for DEﬁrDE which wasslightly improved. Moreover the overall performance of DEﬁrDE was better than DEﬁrSPX, which is just opposite whatobserved in other experiments. The possible reason for substandard performance of DEﬁrSPX is use of crossover operation for local search. Earlier, it has been hypothesized thatcrossover may hurt GA performance on problems with multiple peaks [8]. However, the results of these experiments
were helpful to establish our claim about use of FIR strategy for improving the performance of DE at least for highly
multimodal problems.

According to No Free Lunch (NFL) theorems [15] no algorithm is superior to others when their average performanceover all possible problems is considered. Therefore any general comment made about the performance of any algorithm
based on results of experiments with a couple of test problems is similar to general conclusion made about a very large
data set depending on a few samples; and such conclusion
is often incomplete and misleading. In fact, algorithms operate on landscapes, not on problems, so the information
about how a algorithm interacts with landscapes and therelationship between its performance and properties of landscapes will be more useful to predict its performance onother problems. Therefore it is more useful to use landscape
generators, which do not take into account any speciﬁc problem rather landscapes on which an algorithm will conduct
searching, as the ground for algorithms evaluation and testing. Another advantage of using landscape generators is thatthey can remove the opportunity to hand-tune algorithms
to a speciﬁc problem and, by allowing a large number ofproblem instances to be randomly generated, the predictive
power of the simulation results can be also increased [7].
Therefore we compared our proposed algorithms with theirparent algorithms evaluating them using a Continuous Multimodal Landscape Generator [6]. The original landscape
generator was for binary spaces, proposed in [7]. The idea
is to randomly choose P N-bit individuals as peaks in the
search space and each of these peaks have equal ﬁtness value
1.0. Then the ﬁtness of a string is decided by its Hamming
distance to the closest peak. The continuous multimodal
landscape generator is a logical extension of it for continuous
space. The original model creates P peaks on N dimensions
uniformly distributed through the interval [0.0, 1.0]. Individuals are evaluated using the following ﬁtness function:
 N


1 P
j 2
min
(sigmoid(xj ) − Pi )
(10)
f (.
x) =
N i=1 j=1

973

6.

DISCUSSIONS AND CONCLUSIONS

7. REFERENCES

It is well known that DE is a greedy search heuristics
with remarkable numerical optimization capability. But theconvergence rate of DE for expensive and high dimensional
objective functions is not high enough for real world situations. Therefore in an attempt to speed up DE we proposeda memetic version of DE using crossover based local search(XLS). In our proposed XLS which we call FIR, the search
space around the best individual is greedily explored in eachgeneration. To the best of our knowledge for the ﬁrst time
this type of XLS is being applied to any EA especially toDE.
As DE applies deterministic selection and lacks mutation
operator it tries to estimate the features of the search space
iteratively based on the distribution of its individuals. There
are EAs available in literature which exhibit very good performance without mutation like MGG. The reason behind
their success is the use of XLS whose performance depends
largely on the capability of the crossover operator used. Motivated by their methodology we proposed the FIR strategy for DE algorithm. For our FIR two implementations
were proposed DEﬁrDE and DEﬁrSPX where the ﬁrst uses
DE like recombination and the later uses simplex crossover(SPX) for searching the neighborhood of the best solution.
In our experiments comparing with two well known variantsof DE we found both of the schemes speed up DE for a setof well known test functions specially for higher dimensions.
Between DEﬁrDE and DEﬁrSPX the overall performanceof later was much better. This is expected because SPX,
a much sophisticated crossover operator that works well on
functions having multimodality and/or epsitasis [12], will
search the neighborhood of best solution more eﬀectively
than recombination process of DE. Therefore our DEﬁrSPX
scheme was more successful to accelerate the search and improve performance. Experimenting with various population
sizes we also found that use of FIR also increases the robustness of DE against the variation of population size. In realworld problems often a trade oﬀ has to be made between
algorithm’s convergence rate and robustness. Consequently
the proposed versions of DE can be used for a higher convergence rate without sacriﬁcing the search precision or searchrobustness in real world problems. Comparison with other
RCMA’s also proves the proposed schemes worthy.
Experimenting with random problems, yielded by a multimodal landscape generator, we veriﬁed the superiority of the
proposed schemes over their parent algorithms. We foundthat in highly multimodal environment performance of DEﬁrDE was better than DEﬁrSPX. This is because of theadverse eﬀect of increasing multimodality on the simplex
crossover operator which is used for local search. Nevertheless our experiments showed that both FIR schemes accelerate the basic DE algorithm in highly multimodal environments.
Though in the current work we only experimented withtwo variants of DE, we expect that it will also able to accelerate all other variants of DE in a similar way. Some future
experiment will try to verify this anticipation as well as judge
the potency of FIR scheme for other EAs. Implementationof FIR with other elegant crossover operations like UNDX,
some theoretical analysis of the FIR and exploring FIR onreal life problems are also to be tried.

[1] H. G. Beyer and K. Deb. On self-adaptive features inreal-parameter evolutionary algorithms. IEEE Transactions
on Evolutionary Computation, 5(3):250–270, June 2001.
[2] L. Davis. Handbook of Genetic Algorithms. Van Nostrand
Reinhold, New York, 1991.
[3] D. E. Goldberg and S. Voessner. Optimizing global-local
search hybrids. In Genetic and Evolutionary Computation
Conference (GECCO’99) Proceedings, pages 220–228. Morgan
Kaufmann, July 1999.
[4] M. Y. H. Satoh and S. Kobayashi. Minimal generation gap
model for gas considering both exploration and exploitation. In
Proceedings of IIZUKA’96, pages 494–497, 1996.
[5] A. A. Kalyanmoy Deb and D. Joshi. A computationallyeﬃcient evolutionary algorithm for real-parameter
optimization. Evolutionary Computation, 10(4):371–395,
Winter 2002.
[6] J. Kennedy. Continuous Valued Multimodality Generator for
Evolutionary Algorithms. Retrieved from:http://www.cs.uwyo.edu/ wspears/multi.kennedy.html (16thJanuary, 2005).
[7] J. Kennedy and W. M. Spears. Matching algorithms toproblems: An experimental test of the particle swarm andsome genetic algorithms on the multimodal problem generator.
In International Conference on Evolutionary Computation(ICEC’98) Proceedings, pages 78–83. IEEE, May 1998.
[8] N. K. Manuel Lozano, Francisco Herrera and D. Molina.
Real-coded memetic algorithms with crossover hill-climbing.
Evolutionary Computation, 12(3):273–302, Fall 2004.
[9] P. Merz and B. Freisleben. Fitness landscapes, memetic
algorithms, and greedy operators for graph bipartitioning.
Evolutionary Computation, 8(1):61–91, Spring 2000.
[10] P. Moscato. On evolution, search, optimization, genetic
algorithms and martial arts: Towards memetic algorithms. In
Technical Report 826, Caltech Concurrent Computation
Program. California Institute of Technology, Pasadena,
California, 1989.
[11] P. Moscato and M. G. Norman. A memetic approach for thetraveling salesman problem implementation of a computational
ecology for combinatorial optimization on message-passing
systems. In Parallel Computing and Transputer Applications,pages 177–186. IOS Press, Amsterdam, The Netherlands, 1992.
[12] M. Y. Shigeyoshi Tsutsui and T. Higuchi. Multi-parent
recombination with simplex crossover in real coded genetic
algorithms. In Genetic and Evolutionary Computation
Conference (GECCO’99) Proceedings, pages 657–664. Morgan
Kaufmann, July 1999.
[13] R. Storn. System design by constraint adaptation anddiﬀerential evolution. IEEE Transactions on Evolutionary
Computation, 3(1):22–34, April 1999.
[14] R. Storn and K. Price. Diﬀerential evolution a simple andeﬃcient heuristic for global optimization over continuous
spaces. Journal of Global Optimization, 11(4):341–359,
December 1997.
[15] D. H. Wolpert and W. G. Macready. No free lunch theorems
for optimization. IEEE Transactions on Evolutionary
Computation, 1(1):67–82, April 1997.
[16] J. M. Yang and C. Y. Kao. Integrating adaptive mutations andfamily competition into genetic algorithms as function
optimizer. Soft Computing, 4(2):89–102, June 2000.

974