koorio.com

海量文库 文档专家

海量文库 文档专家

- Self-adapting control parameters in differential evolution
- Differential Evolution Algorithm With Strategy Adaptation for Global Numerical Optimization
- DE-AEC A differential evolution algorithm based on adaptive evolution control
- Self-adapting control parameters modified differential evolution for trajectory planning of ma
- Improved differential evolution algorithm with adaptve mutation and control parameters
- A Low-Complexity Routing Algorithm with Power Control for Self-Organizing Short-RangeWireless
- Synthesis of linear aperiodic arrays using a self-adaptive hybrid differential evolution algorithm
- Control and synchronization of chaotic systems by differential evolution algorithm

Computers & Operations Research 38 (2011) 394–408

Contents lists available at ScienceDirect

Computers & Operations Research

journal homepage: www.elsevier.com/locate/caor

A differential evolution algorithm with self-adapting strategy and control parameters

Quan-Ke Pan a, P.N. Suganthan b,?, Ling Wang c, Liang Gao d, R. Mallipeddi b

a

College of Computer Science, Liaocheng University, Liaocheng 252059, PR China School of Electrical and Electronic Engineering, Nanyang Technological University, 50 Nanyang Avenue, Singapore 639798, Singapore c Tsinghua National Laboratory for Information Science and Technology (TNList), Department of Automation, Tsinghua University, Beijing 100084, PR China d State Key Laboratory of Digital Manufacturing Equipment & Technology in Huazhong University of Science & Technology, Wuhan 430074, PR China

b

a r t i c l e in f o

Available online 23 June 2010 Keywords: Differential evolution Evolutionary algorithm Global numerical optimization Parameter adaptation Strategy adaptation Continuous optimization

a b s t r a c t

This paper presents a Differential Evolution algorithm with self-adaptive trial vector generation strategy and control parameters (SspDE) for global numerical optimization over continuous space. In the SspDE algorithm, each target individual has an associated strategy list (SL), a mutation scaling factor F list (FL), and a crossover rate CR list (CRL). During the evolution, a trial individual is generated by using a strategy, F, and CR taken from the lists associated with the target vector. If the obtained trial individual is better than the target vector, the used strategy, F, and CR will enter a winning strategy list (wSL), a winning F list (wFL), and a winning CR list (wCRL), respectively. After a given number of iterations, the FL, CRL or SL will be re?lled at a high probability by selecting elements from wFL, wCRL and wSL or randomly generated values. In this way, both the trial vector generation strategy and its associated parameters can be gradually self-adapted to match different phases of evolution by learning from their previous successful experience. Extensive computational simulations and comparisons are carried out by employing a set of 19 benchmark problems from the literature. The computational results show that overall the SspDE algorithm performs better than the state-of-the-art differential evolution variants. & 2010 Elsevier Ltd. All rights reserved.

1. Introduction The differential evolution (DE) algorithm is a simple yet powerful search technique introduced by Storn and Price [24] for solving complex continuous nonlinear functions. Starting from a population of randomly initialized solutions, the DE algorithm employs simple mutation and crossover operators to generate new candidate solutions, and utilizes a one-to-one competition scheme to deterministically decide whether the offspring will replace their parents in the next generation. Due to its simplicity, easy implementation, and fast convergence, the DE algorithm has gained much attention with successful applications in mechanical engineering, sensor networks, scheduling, pattern recognition and in other domains [8,9,14,15,21,25,28,32]. There exist many different DE trial vector generation strategies. These strategies often possess different searching capabilities in various search phases of the evolution process. Moreover, their associated control parameters, namely the scaling factor, F, and the crossover rate, CR, may signi?cantly in?uence the searching accuracy and convergence speed of the DE algorithm

? Corresponding author.

E-mail address: epnsugan@ntu.edu.sg (P.N. Suganthan). 0305-0548/$ - see front matter & 2010 Elsevier Ltd. All rights reserved. doi:10.1016/j.cor.2010.06.007

[3,4,10,18,30]. Therefore, it is of signi?cance to determine suitable trial vector generation strategies and their associated parameter values for the DE algorithm when it is used to solve real problems in scienti?c and engineering ?elds. Several empirical guidelines exist in literature for choosing suitable trial vector generator strategies and parameter settings. For example, Storn and Price [17,23] stated that the control parameters of the DE algorithm were not dif?cult to choose, and suggested that a reasonable NP value should be between 5n and 10n, and an effective F value should be in the range [0.4,1], where NP is the population size, and n is dimensionality of the problem to be solved. If the problem is near unimodal or fast convergence is desired, CR ? 0.9 is a good initial choice. Furthermore, Price [16] recommends that it is good to set NP ? 20n, K ? 0.5, and F ? 0.8 when the trial vector generation strategy DE/Current-to-rand/1 is used, where K is a scaling factor in DE/Current-to-rand/1. However, based on parameter settings for the DE algorithm on Sphere, Rosenbrock and Rastrigin functions, Gamperle [4] reported that choosing the proper control parameters for the DE algorithm was more dif?cult than expected, and they advised that NP should be in the range [3n,8n], and F should be equal to 0.6 and CR is between 0.3 and 0.9. Recently, Ronkkonen et al. [22] suggested using F values in [0.4,0.95], and the CR value in [0,0.2] for separable functions while CR in [0.9,1] for dependent functions. Obviously, the rules for

Q.-K. Pan et al. / Computers & Operations Research 38 (2011) 394–408

395

choosing the control parameters of the DE algorithm are quite different as their validity is restricted to the problems, strategies, and parameters values considered in the respective investigation. The best trial vector generation strategy and the associated parameter values can be different for different problems and even for the same problem during different stages of the search process. Therefore, researchers have developed some DE variants with adaptive control parameters and trial vector generation strategies to suit various requirements during the evolution process. Liu and Lampinen [12] proposed a fuzzy adaptive differential evolution (FADE) algorithm, where a fuzzy logic controller was used to dynamically adapt the mutation and crossover parameters. In order to retain population diversity, Zaharie [30] proposed an adaptive DE (ADE) algorithm with multiple populations, and an adaptive Pareto DE algorithm for solving multi-objective optimization problems [31]. By encoding a crossover rate into each individual, Abbass [1] developed another self-adaptive DE algorithm for solving multi-objective optimization problems. Omran et al. [13] presented a selfadaptation method to control the scaling factor F analogous to the adaptation of the crossover rate CR in [1]. This approach (called SDE) was tested on four benchmark functions and performed better than other versions of the DE algorithm. Teo [27] proposed a DE algorithm with self-adapting populations, based on Abbass’s self-adaptive Pareto DE algorithm [1]. Recently, Brest et al. [2] presented a DE algorithm, called JDE, with selfadapting parameters F and CR by encoding the parameters into each individual and adapting them by means of evolution. The authors’ experimental results showed that the JDE algorithm was better or at least comparable to the standard DE algorithm and evolutionary algorithms from the literature in terms of the quality of the solutions found. In addition, the JDE algorithm gave better results in comparison with the FADE algorithm. Based on their former work [20], Qin et al. [19] developed a self-adaptive DE (SaDE) algorithm for constrained real-parameter optimization, in which both trial vector generation strategies and the associated control parameter values were gradually self-adapted according to the learning experiences. Later, the authors extended the SaDE algorithm to solve unconstrained optimization problems [7], and their experiments demonstrated [19] that the SaDE algorithm performed much better than both the conventional DE algorithm and several state-of-art adaptive parameter DE variants including the ADE, SDE and JDE algorithms. In this paper, we propose a self-adaptive DE algorithm, namely SspDE, with each target individual having its own trial vector generation strategy, scaling factor F and crossover rate CR. During the evolution, both strategy and control parameters of each target individual can be gradually self-adapted from their previous experience in generating promising solutions. Computational experiments and comparisons show that the proposed algorithm overall performs better than the state-of-the-art DE variants such as JDE and SaDE, when applied to optimize 19 benchmark global optimization problems. The rest of the paper is organized as follows: in Section 2, the traditional DE algorithm is introduced. In Section 3, the SspDE algorithm is described in detail. Section 4 lists the benchmark problems. Experimental design and comparisons are presented in Section 5. Finally, Section 6 gives the concluding remarks.

uniformly between prede?ned search ranges [Xmin, Xmax], where 2 n 2 n Xmin ? ?x1 andXmax ? ?x1 Then max , xmax , . . . , xmax ?. min , xmin , . . . , xmin ? mutation and crossover operators are employed to generate new candidate vectors, and a selection scheme is applied to determine whether the offspring or the parent survives to the next generation. The above process is repeated until a termination criterion is reached. 2.1. Mutation

2 n A mutant individual, denoted as Vi, G ? ?v1 i, G , vi, G , . . . , vi, G ?, i ? 1,2, y, NP, is generated by using a mutation operator. There are many mutation strategies in the literature [6]. Among them, the commonly used operator is ‘DE/rand/1’, which is described as

Vi, G ? Xa, G ? F ? ?Xb, G ?Xc, G ?

?1?

where a, b and c are three randomly chosen indices in the range [1, NP] such that a, b, c and i are pairwise different ?a a b a c a i A f1, . . . , NP g?. F 4 0 is a mutation scaling factor which affects the differential variation between two individuals. 2.2. Crossover After the mutation phase, a crossover operator is applied to each mutant individual and its corresponding target individual to 2 n yield a trial vector, Ui, G ? ?u1 i, G , ui, G , . . . , ui, G ?. Binomial and exponential crossovers are two commonly used crossover schemes [18]. The binomial crossover is represented as follows: 8 j < vi, G if or j ? nj j ?2? ui, G ? : xj otherwise i, G where the index nj refers to a randomly chosen dimension in the set {1,2, y, n}, which is used to ensure that at least one dimension of the trial individual, Ui,G, differs from its target vector, Xi, G. CR is a crossover rate in the range [0,1], and rjA[0,1] is a uniform random number. If the parameter values of the obtained trial individuals exceed the pre-speci?ed upper bound or lower bound, we can set them equal to upper bound or lower bound, respectively. 2.3. Selection In order to decide whether or not the trial individual Ui,G should become a member of the target population in the next generation, a one-to-one greedy selection between a parent and its corresponding offspring is employed in DE as this strategy enhances diversity in comparison to other selection strategies such as tournament selection, rank based selection and ?tness proportional selection. The one-to-one selection scheme is based on the survival of the ?tter between the trial individual Ui,G and its target counterpart Xi,G. For minimization problems, it can be formulated as follows [18]: ( Ui, G if f ?Ui, G ? r f ?Xi, G ? ?3? Xi, G ? 1 ? Xi, G otherwise where f(Ui,G) and f(Xi,G) are the objectives of Ui,G and Xi,G, respectively. 2.4. The algorithmic description

2. The DE algorithm The traditional DE algorithm starts with initializing a population of NP target individuals PG ? {X1,G,X2,G, y, XNP,G}, where 2 n individual Xi, G ? ?x1 i, G , xi, G , . . . , xi, G ?, i ? 1,2, y, NP, is an n-dimensional vector with parameter values determined randomly and

Based on the above initialization, mutation, crossover and selection operations, the algorithmic description of the conventional DE algorithm is summarized in Table 1.

396

Q.-K. Pan et al. / Computers & Operations Research 38 (2011) 394–408

Table 1 A algorithmic description of the DE algorithm. Step 1: Initialization. Set the generation number G ? 0, and randomly initialize a population of NP target individuals, PG ? fX1, G , X2, G , . . . , XNP, G g, with 2 n Xi, G ? ?x1 i, G , xi, G , . . . , xi, G ?, i ? 1, 2, . . . , NP uniformly distributed in the range ?Xmin , Xmax ? Step 2: Evaluate each target individual in PG ? fX1, G , X2, G , . . . , XNP, G g Step 3: Generate NP trial individuals. For i ? 1 to NP repeat Steps 3.1–3.2 2 n Step 3.1: Mutation. Generate a mutant vector Vi, G ? ?v1 i, G , vi, G , . . . , vi, G ? for Xi,G, i ? 1,2, y, NP by using a mutation operator. 2 n Step 3.2: Crossover. Generate a trial vectorUi, G ? ?u1 i, G , ui, G , . . . , ui, G ? for Xi,G, i ? 1,2, y, NP by applying a crossover operator on Vi,G and Xi,G Step 4: Selection for next generation. Evaluate each Ui,G, i ? 1,2, y, NP, and determine the members of the target population of the next generation by using the one-to-one selection scheme Step 5: Increment the generation count G ? G +1. If a termination criterion is not satis?ed, go to step 3; Otherwise, stop the procedure and output Xbest and f(Xbest)

DE/rand/2/bin: 8 j j j < xa, G ? F ?xj ?xj c, G ? ? F ?xd, G ?xe, G ? b, G j ui, G ? : xj i, G DE/current-to-rand/1: Ui, G ? Xi, G ? K ?Xa, G ?Xi, G ? ? F ?Xb, G ?Xc, G ?

if rj r CR or j ? nj otherwise

?6?

?7?

3. The self-adaptive DE algorithm Since the trial vector generation strategy along with its associated control parameters CR and F determine the performance of the DE algorithm, it is important to select a suitable trial vector generation strategy along with appropriate parameter values when applying the DE algorithm to solve a given problem. For this propose, it is common to perform a trial-and-error search. However, this may expend a huge amount of computational costs. To address this problem, Qin et al. [20] developed a self-adaptive DE (SaDE) algorithm where both trial vector generation strategies and control parameter values can be gradually self-adapted according to the past experiences. Following the successful application of the SaDE algorithm, in this paper, we develop another DE algorithm with self-adaptive trial vector generation strategy and the associated control parameters, called SspDE. Unlike the SaDE algorithm, the SspDE algorithm utilizes a different learning mechanism and a different method to determine trial vector generation strategies and their parameters. The core idea behind the SspDE algorithm is elucidated as follows.

where a, b, c, d, e are randomly chosen indices in the range [1, NP] such that a a b a c a d a e a i A f1, . . . , NP g; K is a scaling factor. Among the above four strategies, ‘DE/rand-to-best/2/bin’ relies on the best solution found so far. It usually has a faster convergence speed and performs well when solving unimodal problems. However, it is more likely to get trapped in a local optimum and thereby leading to premature convergence when solving multi-modal problems. ‘DE/rand/1/bin’ and ‘DE/rand/2/ bin’ usually demonstrate slow convergence speed with superior exploration capability. Therefore, they are usually more suitable for solving multi-modal problems than ‘DE/rand-to-best/2/bin’. ‘DE/current-to-rand/1’ is a rotation-invariant strategy [5]. Obviously, these four trial vector strategies constitute a strategy candidate pool with diverse characteristics. They will be adaptively selected during different stages of evolution of the proposed DE algorithm.

3.2. Selection of ranges for parameters In the conventional DE algorithm, the choice of numerical values for control parameters F, CR and NP highly depends on the problem under consideration. Since NP highly relies on the complexity of given problems, we leave it as a user-speci?ed parameter in the proposed SspDE algorithm. With reference to the other two parameters, CR is usually more sensitive to problems with different characteristics such as unimodality and multimodality, while F is closely related to the convergence speed [19]. In order to maintain both exploitation (with small F value) and exploration (with large F value) power throughout the evolution process, SspDE sets the ranges of F and CR values as [0.1,1] and [0,1], respectively, as suggested in the literature [2]. Moreover, following suggestions in [16], the parameter K in the strategy ‘DE/ current-to-rand/1’ is randomly generated within [0,1].

3.1. Selection of trial vector generation strategies In the DE literature, many trial vector generation strategies, i.e., mutation and crossover operators, are used to produce trial individuals. The DE algorithm employing different trial vector generation strategies usually performs differently during different stages of evolution [19]. Some strategies have better exploration capability, while others favor exploitation. Hence, adaptively selecting a suitable strategy for a certain evolution stage according to the current experience can improve the DE algorithm’s performance. Obviously, the strategy candidate pool should have diverse characteristics, that is, the used strategies should demonstrate distinct capabilities in order to tackle different problems and different stages of evolution. Therefore, the following trial vector generation strategies are selected to be used in the proposed SspDE algorithm: DE/rand/1/bin: uj i, G 8 j < xa, G ? F ?xj ?xj c, G ? b, G : xj

i, G

3.3. Trial vector generation strategy and parameter adaptation Adaptation of the trial vector generation strategies and control parameters can be described as follows. During initialization, for each target individual, Xi,G, in the initial population PG, we randomly generate three control lists using a uniform distribution. These lists are a mutation scaling factor F list denoted as FLi ? ?Fi1 , Fi2 , . . . , FiLP ? with Fij A ?0:1, 1?, a crossover rate CR list j 2 LP denoted as CRLi ? ?CR1 i , CRi , . . . , CRi ? with CRi A ?0, 1?, and a trial j 2 vector generation strategy list, SLi ? ?s1 , s , . . . , sLP i i i ?, with si belonging to the strategy set determined in Section 3.1, where LP is the size of these lists. Therefore, every target vector has a set of parameter values for LP generations to generate an offspring. The proposed DE algorithm is started with a counter lp ? 1. During the evolution process, for each target individual Xi,G, the parameters F and CR and trial vector generation strategy S are respectively set as F ? Filp , CR ? CRlp , S ? slp , and then they are used i i to produce a new trial vector Uik . If the obtained Uik ,G , G is better than its target counterpart, Xi,G, the associated F, CR and S will enter a winning F list, wFLi, a wining CR list, wCRLi, and a winning strategy list, wSLi, respectively. The generation counter is incremented (lp ? lp + 1) and the above evolution process is repeated. Once the

?

if rj r CR or j ? nj otherwise

?4?

DE/rand-to-best/2/bin:

uj i, G 8 j j j j < xi, G ? F ?xj ?xj ? ? F ?xj a, G ?xb, G ? ? F ?xc, G ?xd, G ? i, G best , G : xj

i, G

if rj r CR or j ? nj otherwise

?

?5?

Q.-K. Pan et al. / Computers & Operations Research 38 (2011) 394–408

397

Table 2 The algorithmic description of the SspDE algorithm.

398

Q.-K. Pan et al. / Computers & Operations Research 38 (2011) 394–408

Table 2. (continued )

generation counter lp is equal to the list size LP, we set lp ? 1. A reassignment procedure for the F list, CR list and SL list is invoked. During the reassignment procedure, the FLi, CRLi and SLi for each Xi,G is reassigned with a probability RP by selecting elements from wFLi, wCRLi and wSLi or by randomly generating with a uniform distribution. More speci?cally, for each Fij A FLi , j ? 1,2, y, LP, a uniform random number rA[0,1] is generated. If r o RP, a randomly selected F value from wFLi is assigned to Fij ; otherwise, a randomly generated F value between 0.1 and 1 is assigned to Fij . The CRLi and SLi are also reassigned in the same manner. Note that the wFLi, wCRLi and wSLi are reset to zero after the reassignment process to avoid long-term accumulation effects. If wFLi, wCRLi and wSLi are empty (this may happen when the search is performed near an optimum with negligible population diversity), the last FLi, CRLi and SLi are used again. The above process is repeated until the termination criterion is reached. Obviously, the more successful a trial vector generation strategy, F and CR are in previous generations in generating promising solutions, the higher their probability of being used in the future generations to generate new solutions. As a result, the proper parameters F and CR and trial vector generation strategies can be gradually learned to suit the particular problem and the particular phase of search process. 3.4. The proposed DE algorithm with self-adaptive strategy and parameters By incorporating the above-mentioned adaptation schemes for trial vector generation strategy and control parameters into the conventional DE framework, a self-adaptive DE algorithm, namely SspDE, is developed. In the proposed SspDE algorithm, the trial vector generation strategy and control parameters of each target individual can be gradually self-adapted according to their

previous successful experiences. As a result, a more suitable strategy along with its parameter setting can be determined adaptively to suit the phase of the search process. The SspDE is presented in Table 2.

4. Benchmark functions This section lists the global minimization benchmark functions used to evaluate the proposed SspDE algorithm against other DE variants. These benchmark functions provide a balance between unimodal and multi-modal functions, taken from evolutionary computation literature [11,26,29]. These functions can be formulated as follows: Min f ?x? st : x?j? A ?LB?j?, UB?j??, j ? 1, 2, . . . , n, ?8?

where f(x) is the objective function, x ? (x(1), x(2), y, x(n)) is the set of design variables, n is the number of design variables. The following problems are used: (1) Rosenbrock’s function, de?ned as f1 ?x? ?

n?1 X i?1

?100?x?i ? 1??x2 ?i??2 ? ?x?i??1?2 ?

with global optimum x* ? (1,1, y, 1) and f(x*) ? 0 for ? 100 r x(i) r 100. (2) Schwefel’s function, de?ned as f2 ?x? ? 418:9829 ? n?

n X i?1

x?i?sin?jx?i?j1=2 ?

with global optimum x* ? (420.96, 420.96, y, 420.96) and f(x*) ? 0 for ? 500 r x(i) r 500.

Q.-K. Pan et al. / Computers & Operations Research 38 (2011) 394–408

399

(3) Schwefel’s Problem 2.22, de?ned as f3 ?x? ?

n X i?1

jx?i?j ?

n Y i?1

jx?i?j

with global optimum x* ? 0 and f(x*) ? 0 for ? 10 r x(i) r 10. (4) Schwefel’s Problem 2.21, de?ned as f4 ?x? ? maxfjx?i?j, 1 r i r ng, with global optimum x* ? 0 and f(x*) ? 0 ? 100 r x(i) r 100. (5) Generalized Penalized Function 1, de?ned as for

(11) Shifted Ackley’s function, de?ned as v?????????????????????1 0 u n u1 X @ f11 ?x? ? ?20 exp ?0:2t z2 ?i?A ni?1 ! n 1X cos?2pz?i?? ? 20 ? e ?exp ni?1 with z ? x ? o; o ? (o(1),o(2),y,o(n)) is the shifted global optimum; global optimum x* ? o and f(x*) ? 0 for ? 32 r x(i) r 32. (12) Shifted Rastrigin function, de?ned as f12 ?x? ?

n X i?1

f5 ?x? ?

p

n

( 10 sin ?py?1?? ? )

n X i?1 2

n X i?1

?y?i??1? ?1 ? 10 sin ?py?i ? 1???

2

2

?z2 ?i??10 cos?2pz?i?? ? 10?

? ?y?n??1?2 ?

m?x?i?, 10, 100, 4?

x?i? 4 a ?a r x?i? r a x?i? o ?a

8 m > < k?x?i??a? , 1 y?i? ? 1 ? ?x?i? ? 1?, m?x?i?, a, k, m? ? 0, > 4 : k??x?i??a?m ,

with z ? x ? o; o ? (o(1),o(2),y,o(n)) is the shifted global optimum; global optimum x* ? o and f(x*) ? 0 for ? 5 r x(i) r 5. (13) Shifted Non-continuous Rastrigin’s function, de?ned as f13 ?x? ?

n X i?1

?y2 ?i??10 cos?2py?i?? ? 10?

with global optimum x* ? (1,1, y, 1) and f(x*) ? 0 for ? 50 r x(i) r 50. (6) Generalized Penalized Function 2, de?ned as f6 ?x? ? 0:1fsin ?3px?1?? ?

2 n ?1 X i?1

( y?i? ?

z?i?, round?2z?i??=2

jz?i?j o 1=2 otherwise

for i ? 1, 2, . . . , n

?x?i??1?2 ?1 ? sin ?3px?i ? 1???

n X i?1

2

? ?x?n??1?2 ?1 ? sin2 ?2px?n???g ?

m?x?i?, 5, 100, 4?

with z ? x ? o; o ? (o(1),o(2),y,o(n)) is the shifted global optimum; global optimum x* ? o and f(x*) ? 0 for ? 5 r x(i) r 5. (14) Shifted Rosenbrock function, de?ned as f14 ?x? ?

n ?1 X i?1

with global optimum x* ? (1,1,y,1) and f(x*) ? 0 for ? 50 r x(i) r 50. (7) Schwefel’s Problem 1.2, de?ned as 0 12 n i X X @ f7 ?x? ? x?j?A

i?1 j?1

?100?z?i ? 1??x2 ?i??2 ? ?z?i??1?2 ?

with z ? x ? o; o ? (o(1),o(2),y,o(n)) is the shifted global optimum; global optimum x* ? o and f(x*) ? 0 for ? 100 r x(i) r 100. (15) Shifted Schwefel’s Problem 2.21, de?ned as f15 ?x? ? maxfjz?i?, 1 r i r ng with z ? x ? o; o ? (o(1),o(2),yo(n)) is the shifted global optimum; global optimum x* ? o and f(x*) ? 0 for ? 100 r x(i) r 100. (16) Shifted Rotated Griewank’s Function without bounds, de?ned as n n Y X z2 ?i? z?i? ? ?1 f16 ?x? ? cos 4000 i i?1 i?1 with z ? (x ? o) ? M, and o ? (o(1),o(2),yo(n)) is the shifted global optimum, M is a orthogonal rotation matrix [11]; global optimum x* ? o and f(x*) ? 0 for ? N o x(i) o + N. (17) Rotated Rastrigin’s Function, de?ned as f17 ?x? ?

n X i?1

with global optimum x* ? 0 ? 100 r x(i) r 100. (8) Shifted Sphere function, de?ned as f8 ?x? ?

n X i?1

and

f(x*) ? 0

for

z2 ?i?

with z ? x ? o; o ? (o(1),o(2),y,o(n)) is the shifted global optimum; global optimum x* ? o and f(x*) ? 0 for ? 100 r x(i) r 100. (9) Shifted Schwefel’s Problem 1.2, de?ned as 0 12 n i X X @ f9 ?x? ? z?j?A

i?1 j?1

with z ? x ? o; o ? (o(1),o(2),y,o(n)) is the shifted global optimum; global optimum x* ? o and f(x*) ? 0 for ? 100 r x(i) r 100. (10) Shifted Schwefel’s Problem 1.2 with noise in ?tness, de?ned as 0 12 n i X X @ f10 ?x? ? z?j?A ?1 ? 0:4jN?0, 1?j?

i?1 j?1

?z2 ?i??10 cos?2pz?i?? ? 10?

with z ? x ? M; M is a orthogonal rotation matrix [11]; x* ? 0 is the global optimum, and f(x*) ? 0 for ? 5 r x(i) r 5. (18) Rotated Schwefel’s function, de?ned as f2 ?x? ? 418:9829 ? n? ( with z?i? ? y?i? y?i?%500

n X i?1

z?i?sin?jz?i?j1=2 ?

with z ? x ? o; o ? (o(1),o(2)y,o(n)) is the shifted global optimum; global optimum x* ? o and f(x*) ? 0 for ? 100x r (i) r 100; N(0,1) is a random number generated by a normal distribution with mean 0 and variance 1.

if y?i? r 500 otherwise

where % is the modulus

operator used to divide two numbers and return only the remainder; y ? M ? (x ? 420.96) +20.96; global optimum

400

Q.-K. Pan et al. / Computers & Operations Research 38 (2011) 394–408

Table 3 Median and h values for 10-dimensional functions. Function 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 DE/rand/1/bin (CR ? 0.3, F ? 0.5) 4.63e+ 000(1) 1.27e ? 004(0) 3.59e ? 024(1) 3.53e ? 009(1) 4.71e ? 032(0) 1.35e ? 032(0) 1.02e ? 002(1) 0.00e+ 000(0) 5.20e ? 003(1) 8.20e ? 002(1) 0.00e+ 000(0) 0.00e+ 000(0) 0.00e+ 000(0) 4.73e+ 000(1) 3.39e ? 009(1) 2.85e ? 001(1) 1.99e+ 001(1) 9.93e+ 002(1) 1.33e ? 002(1) DE/rand/1/bin (CR ? 0.9, F ? 0.5) 2.13e ? 011(1) 1.46e ? 002(1) 7.50e ? 019(1) 1.17e ? 013(1) 4.71e ? 032(0) 1.35e ? 032(0) 9.39e ? 022(1) 0.00e+ 000(0) 6.34e ? 022(1) 8.65e ? 020(1) 0.00e+ 000(0) 1.75e +001(1) 9.79e +000(1) 4.26e ? 011(1) 8.53e ? 014(1) 4.06e ? 001(1) 2.73e +001(1) 8.46e +002(1) 1.59e ? 022(1) JDE 4.03e ? 002(1) 1.27e ? 004(0) 6.99e ? 027(1) 5.42e ? 014(1) 4.71e ? 032(0) 1.35e ? 032(0) 1.14e ? 016(1) 0.00e +000(0) 5.22e ? 017(1) 2.95e ? 015(1) 0.00e +000(0) 0.00e +000(0) 0.00e +000(0) 7.85e ? 003(1) 3.55e ? 014(1) 5.71e ? 002(1) 1.02e +001(1) 6.58e + 002(1) 6.13e ? 017(1) SaDE 1.35e ? 010(1) 1.27e ? 004(0) 1.63e ? 026(1) 2.59e ? 019(1) 4.71e ? 032(0) 1.35e ? 032(0) 3.71e ? 023(1) 0.00e +000(0) 2.30e ? 024(0) 1.83e ? 022( ? 1) 0.00e +000(0) 0.00e +000(0) 0.00e +000(0) 6.49e ? 010(1) 0.00e +000(0) 2.25e ? 002(1) 4.89e + 000(1) 4.11e + 002(1) 3.11e ? 024(1) SspDE 4.00e ? 014 1.27e ? 004 5.83e ? 032 5.83e ? 024 4.71e ? 032 1.35e ? 032 8.02e ? 025 0.00e +000 4.69e ? 025 1.27e ? 021 0.00e +000 0.00e +000 0.00e +000 1.02e ? 013 0.00e +000 9.23e ? 003 3.21e +000 3.37e +002 1.46e ? 025

x* ? (420.96,420.96,y,420.96) and f(x*) ? 0 for ? 500 r x(i) r 500. (19) Rotated Schwefel’s Problem 1.2, de?ned as 0 12 n i X X @ f7 ?x? ? z?j?A

i?1 j?1

with z ? x ? M; M is a orthogonal rotation matrix; x* ? 0 is the global optimum, and f(x*) ? 0 for ? 100 r x(i) r 100. Among the above 19 benchmark problems, functions f1 ? f7 are conventional benchmark functions commonly used in the literature. Functions f8 ? f15 are shifted functions so that the new global optimum has different numerical values for different dimensions. Functions f16 ? f19 are rotated functions by right multiplying the set of design variables x ? (x(1), x(2), y, x(n)) by an orthogonal rotation matrix, to avoid local optima lying along the coordinate axes while retaining other properties of the test function. Moreover, functions f3, f4, f7, f8, f9, f10 and f19 are unimodal. Others are dif?cult multi-modal problems where the number of local optima increases with the problem dimension.

set as LP ? 50 and RP ? 0.8, respectively. The population size for all the algorithms was set as NP ? 100. In the experiments, each problem was run for 30 independent replications. The median values over these 30 replications are reported. Mann–Whitney U tests [33] with a signi?cance level equal to 0.05 were conducted to show whether the results obtained by the SspDE algorithm are statistically different from those obtained by the other DE algorithms. For this criterion, the notation Median(h) is used in the tables, where h is the result of the Mann–Whitney U test performed between the SspDE and a compared DE algorithm. An h value equal to 1 or ? 1 indicates that result obtained by the SspDE algorithm is signi?cantly better or worse than that by the compared counterpart, while an h value of zero implies that the results by the two compared algorithms are not statistically different. 5.2. Comparison between SspDE and other DE algorithms 5.2.1. Comparison on 10-dimensional problems Table 3 presents the median values of the 30 runs of the DE algorithms on the 19 test functions with dimension n ? 10. It is clear that on average the proposed SspDE algorithm performs much better than the other compared algorithms. For the unimodal functions f3, f4, f7 and f19, the SspDE algorithm produces smaller median values than all the other compared algorithms, and the Mann ? Whitney U test shows statistically signi?cant differences. All the compared algorithms achieve the global optimum for function f8. The SspDE algorithm outperforms the JDE, DE/rand/1/bin (F ? 0.5, CR ? 0.3) and DE/ rand/1/bin (F ? 0.5, CR ? 0.9) algorithms on functions f9 and f10. However, SspDE is surpassed by the SaDE algorithm on function f10 and produces no signi?cant difference on function f9 with the SaDE algorithm. For the multi-modal functions with many local minima, namely f1 and f14 ? f18, it is clear that the best results are yielded by the SspDE algorithm. All the algorithms are able to ?nd the global optimum for functions f11 ? f13 except the DE/rand/1/bin (F ? 0.5, CR ? 0.9) algorithm which fails on functions f12 and f13. With regard to functions f2, f5 and f6, almost no signi?cant difference was observed on the compared algorithms. On the rotated functions f16 ? f19, it can be easily seen that the proposed SspDE algorithm is superior to all the other compared algorithms.

5. Computational results 5.1. Experimental setup To test the performance of the proposed SspDE algorithm, experiments are conducted on the suite of 19 numerical functions listed in Section 4 with dimensions n ? 10, 30, 50, and 100, respectively. The maximum number of function evaluations is set to 10,000n. We compare the proposed SspDE algorithm with two representative self-adaptive DE algorithms, namely JDE [2] and SaDE [19], which were shown by the respective authors to perform better than FADE [12], ADE [30] and SDE [13] algorithms. We also compare the SspDE algorithm with two well-tuned conventional DE algorithms, i.e., DE/rand/1/bin (F ? 0.5, CR ? 0.3) [2,12,24] and DE/rand/1/bin (F ? 0.5, CR ? 0.9) [19]. All the above algorithms are coded in Visual C+ + and the experiments were executed on a Lenovo Y450 laptop with a 2.13 GHz Intel(R) Core(TM) 2 Duo CPU and 2 GB RAM. For the JDE and SaDE algorithms, the parameters were ?xed as those in the original papers, while for the proposed SspDE algorithm, LP and RP were

Q.-K. Pan et al. / Computers & Operations Research 38 (2011) 394–408

401

Table 4 Median and h values for 30-dimensional functions. Function 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 DE/rand/1/bin (CR ? 0.3, F ? 0.5) 2.29e +001(1) 3.82e ? 004(0) 2.32e ? 025(1) 3.31e ? 004(1) 1.57e ? 032(0) 1.35e ? 032(0) 1.62e +004(1) 0.00e +000(0) 6.90e+ 003(1) 1.55e +004(1) 7.11e ? 015(1) 4.46e +001(1) 3.04e+ 001(1) 2.36e +001(1) 1.98e ? 004(0) 1.27e ? 001(1) 1.94e +002(1) 7.17e +003(1) 1.50e+ 004(1) DE/rand/1/bin (CR ? 0.9, F ? 0.5) 2.48e + 000(1) 4.39e + 003(1) 1.48e ? 015(1) 1.54e ? 002(1) 1.64e ? 032(1) 4.06e ? 032(1) 2.95e ? 005(1) 0.00e + 000(0) 4.11e ? 005(1) 8.33e ? 003(1) 7.11e ? 015(1) 1.25e + 002(1) 1.01e + 002(1) 2.41e + 000(0) 4.26e ? 003(1) 0.00e + 000( ? 1) 1.82e + 002(1) 7.22e + 003(1) 5.71e ? 006(1) JDE 1.08e+ 001(1) 3.82e ? 004(0) 1.79e ? 036(1) 1.72e ? 001(1) 1.57e ? 032(0) 1.35e ? 032(0) 9.79e ? 007(1) 0.00e+ 000(0) 1.19e ? 006(1) 2.26e ? 002(1) 3.55e ? 015(0) 0.00e+ 000(0) 0.00e+ 000(0) 1.04e+ 001(1) 1.49e ? 001(1) 9.86e ? 003(0) 4.91e+ 001(1) 4.18e+ 003(1) 4.22e ? 007(1) SaDE 4.67e ? 010(1) 3.82e ? 004(0) 2.75e ? 033(1) 3.55e ? 002(1) 1.57e ? 032(0) 1.35e ? 032(0) 7.52e ? 016(1) 0.00e+ 000(0) 4.34e ? 015(1) 3.94e ? 003(1) 3.55e ? 015(0) 0.00e+ 000(0) 0.00e+ 000(0) 9.87e ? 008(0) 3.06e ? 001(1) 9.86e ? 003(0) 2.34e +001(1) 3.58e +003(1) 6.84e ? 016(1) SspDE 1.82e ? 011 3.82e ? 004 3.00e ? 048 7.68e ? 005 1.57e ? 032 1.35e ? 032 1.21e ? 018 0.00e +000 3.85e ? 018 7.31e ? 007 3.55e ? 015 0.00e +000 0.00e +000 4.41e ? 008 3.07e ? 005 1.11e ? 002 1.55e +001 3.11e +003 2.98e ? 019

Table 5 Median and h values for 50-dimensional functions. Function 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 DE/rand/1/bin (CR ? 0.3, F ? 0.5) 4.12e+ 001(1) 7.03e+ 003(1) 2.15e ? 023(1) 9.75e ? 002( ? 1) 9.42e ? 033(0) 1.35e ? 032(0) 7.34e+ 004(1) 0.00e+ 000(0) 7.05e+ 004(1) 8.75e+ 004(1) 1.07e ? 014( ? 1) 1.50e+ 002(1) 9.41e+ 001(1) 4.13e+ 001(1) 4.97e ? 002( ? 1) 4.53e ? 005(0) 3.99e+ 002(1) 1.37e+ 004(1) 1.69e+ 005(1) DE/rand/1/bin (CR ? 0.9, F ? 0.5) 2.28e+ 001(1) 7.36e+ 003(1) 3.88e ? 017(1) 6.12e+ 000(1) 9.42e ? 033(0) 1.35e ? 032(0) 1.61e+ 000(1) 2.02e ? 028(1) 3.26e+ 000(1) 2.44e+ 002(1) 7.11e ? 015( ? 1) 1.87e+ 002(1) 1.73e+ 002(1) 2.36e+ 001(1) 1.36e+ 001(0) 0.00e+ 000( ? 1) 3.59e+ 002(1) 1.37e+ 004(1) 3.90e+ 000(1) JDE 2.42e+ 001(1) 6.36e ? 004(0) 8.93e ? 044(1) 6.10e+ 000(1) 9.42e ? 033(0) 1.35e ? 032(0) 5.14e ? 003(1) 0.00e+ 000(0) 1.69e ? 002(1) 2.62e+ 002(1) 7.11e ? 015( ? 1) 0.00e+ 000( ? 1) 0.00e+ 000( ? 1) 2.33e+ 001(1) 5.77e+ 000( ? 1) 0.00e+ 000( ? 1) 1.02e+ 002(1) 8.41e+ 003(1) 2.88e ? 002(1) SaDE 2.39e + 000(1) 6.36e ? 004(0) 8.89e ? 035(1) 3.80e + 000(0) 9.42e ? 033(0) 1.35e ? 032(0) 1.96e ? 007(1) 0.00e + 000(0) 1.06e ? 006(1) 7.67e + 002(1) 7.11e ? 015( ? 1) 0.00e + 000( ? 1) 0.00e + 000( ? 1) 3.99e + 000(0) 2.26e + 001(1) 0.00e + 000( ? 1) 4.02e + 001(1) 6.92e + 003(1) 3.80e ? 007(1) SspDE 4.20e ? 006 6.36e ? 004 4.16e ? 053 3.53e + 000 9.42e ? 033 1.35e ? 032 2.26e ? 011 0.00e +000 9.23e ? 011 4.45e +001 8.79e ? 001 1.78e ? 015 1.78e ? 015 3.99e +000 1.18e + 001 1.11e ? 016 2.84e +001 6.07e +003 4.77e ? 010

5.2.2. Comparison on 30-dimensional problems Table 4 reports the median values of the 30 runs of the 19 test functions with dimension n ? 30. The 30-dimensional problems become more dif?cult than their 10-dimensional counterparts. Hence, the results are not as good as those for 10-dimensional functions even though the maximum function evaluation is increased from 100,000 to 300,000. However, it can be easily seen that overall the SspDE algorithm outperforms all the other compared DE algorithms. In particular, the SspDE algorithm yields much smaller median values than the other compared algorithms on all the unimodal functions except f8, where all the DE algorithms are able to ?nd the global optimum within 300,000 function evaluations. For the 12 multi-modal functions, the SspDE algorithm produces 8, 10, 5 and 4 signi?cantly better results than the DE/rand/1/bin (F ? 0.5, CR ? 0.3), DE/rand/1/bin (F ? 0.5, CR ? 0.9), JDE and SaDE algorithms, respectively. No result obtained by the SspDE algorithm is signi?cantly worse than those by the compared algorithms except on function f16, where DE/rand/1/bin (F ? 0.5, CR ? 0.9) ?nds the

global optimum. On the rotated functions f17 ? f19, the SspDE algorithm obviously performs the best. 5.2.3. Comparison on 50-dimensional problems Results of 50-dimensional problems are reported in Table 5. It can be observed that the SspDE algorithm is the winner for all the seven unimodal functions and the rotated functions f17 ? f19. However, on the 12 multi-modal functions, no algorithm performs consistently better than the others. Overall, the SspDE algorithm yields 12, 14, 10 and 9 signi?cantly better, and 3, 2, 5 and 4 signi?cantly worse results than the DE/rand/1/bin (F ? 0.5, CR ? 0.3), DE/rand/1/bin (F ? 0.5, CR ? 0.9), JDE and SaDE algorithms, respectively. 5.2.4. Comparison on 100-dimensional problems Results for the 100-dimensional problems are reported in Table 6. It can be seen that the superiority of the SspDE algorithm against the JDE and SaDE algorithms declines. But, on average the

402

Q.-K. Pan et al. / Computers & Operations Research 38 (2011) 394–408

Table 6 Median and h values for 100-dimensional functions. Function 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 DE/rand/1/bin (CR ? 0.3, F ? 0.5) 9.01e+ 001(1) 2.22e+ 004(1) 5.11e ? 017(1) 2.40e+ 001(1) 5.73e ? 023(0) 2.04e ? 023(0) 3.30e+ 005(1) 8.01e ? 028(1) 3.58e+ 005(1) 4.34e+ 005(1) 3.20e ? 014( ? 1) 5.10e+ 002(1) 3.93e+ 002(1) 8.94e+ 001(1) 7.00e+ 000( ? 1) 1.54e ? 001(1) 9.96e+ 002(1) 3.18e+ 004(1) 7.08e+ 005(1) DE/rand/1/bin (CR ? 0.9, F ? 0.5) 1.27e+ 002(1) 1.02e+ 004(1) 3.60e ? 021(1) 9.53e+ 001(1) 4.71e ? 033( ? 1) 2.77e ? 030(0) 2.41e+ 003(1) 1.55e ? 027(1) 4.59e+ 003(1) 3.64e+ 004(1) 1.42e ? 014( ? 1) 7.44e+ 001(1) 2.86e+ 002(1) 1.30e+ 002(1) 4.63e+ 001( ? 1) 3.33e ? 016( ? 1) 8.12e+ 002(1) 3.16e+ 004(1) 6.08e+ 003(1) JDE 1.04e + 002(1) 1.27e ? 003( ? 1) 2.98e ? 057( ? 1) 2.27e + 001(1) 4.71e ? 033( ? 1) 1.35e ? 032( ? 1) 5.96e + 000(1) 0.00e + 000(0) 3.12e + 001(1) 2.41e + 004(1) 1.42e ? 014( ? 1) 0.00e + 000( ? 1) 0.00e + 000( ? 1) 1.07e + 002(1) 3.24e + 001( ? 1) 1.78e ? 015( ? 1) 1.98e + 002(1) 2.05e + 004(1) 2.52e + 001(1) SaDE 8.58e + 001(1) 1.27e ? 003( ? 1) 5.48e ? 032(1) 1.21e + 001( ? 1) 4.71e ? 033( ? 1) 1.35e ? 032( ? 1) 1.41e ? 002(1) 0.00e + 000(0) 1.42e ? 001(1) 3.37e + 004(1) 9.56e ? 001( ? 1) 9.77e ? 015( ? 1) 1.07e ? 014( ? 1) 1.08e +002(1) 5.33e + 001(0) 4.44e ? 015(0) 9.26e + 001(1) 1.66e + 004(0) 2.44e ? 001(1) SspDE 3.99e+ 000 2.37e +002 3.78e ? 048 1.32e +001 1.94e ? 032 2.52e ? 032 4.33e ? 005 0.00e+ 000 3.90e ? 004 1.61e+ 004 3.17e +000 2.04e+ 001 1.30e+ 001 1.64e+ 001 5.34e +001 3.50e ? 015 7.16e+ 001 1.62e+ 004 1.13e ? 003

Table 7 Comparison of the DE algorithms with population size NP ? 60. Function 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 DE/rand/1/bin (CR ? 0.3, F ? 0.5) 2.20e+ 001(1) 3.82e ? 004(0) 7.25e ? 044(1) 5.45e ? 008( ? 1) 1.57e ? 032(0) 1.35e ? 032(0) 8.91e +003(1) 0.00e+ 000(0) 2.92e +003(1) 8.28e +003(1) 7.11e ? 015(1) 3.26e +001(1) 2.47e +001(1) 2.20e+ 001(1) 4.06e ? 008( ? 1) 2.25e ? 002(0) 1.89e +002(1) 7.11e +003(1) 9.87e +003(1) DE/rand/1/bin (CR ? 0.9, F ? 0.5) 1.84e + 001(1) 1.91e + 003(1) 1.28e ? 036(1) 4.28e + 000(1) 1.57e ? 032(0) 1.35e ? 032(0) 7.01e ? 012(1) 5.05e ? 029(1) 4.31e ? 012(1) 1.19e ? 005(1) 7.11e ? 015(1) 1.29e + 001(1) 2.21e + 001(1) 1.92e + 001(1) 1.28e + 001(1) 4.93e ? 003( ? 1) 1.72e + 002(1) 6.83e + 003(1) 8.89e ? 013(1) JDE 6.86e ? 001(1) 3.82e ? 004(0) 5.56e ? 062(1) 3.03e+ 000(1) 1.57e ? 032(0) 1.35e ? 032(0) 3.13e ? 010(1) 0.00e+ 000(0) 1.01e ? 009(1) 1.81e ? 002(1) 3.55e ? 015(0) 0.00e+ 000(1) 0.00e+ 000(1) 2.15e ? 001(0) 4.01e+ 000(1) 9.86e ? 003(0) 4.17e+ 001(1) 3.84e+ 003(1) 1.65e ? 010(1) SaDE 6.57e ? 022(0) 3.82e ? 004(0) 3.10e ? 051(1) 1.72e+ 000(1) 1.57e ? 032(0) 1.35e ? 032(0) 1.51e ? 019(1) 0.00e+ 000(0) 4.53e ? 017(1) 3.77e ? 002(1) 3.55e ? 015(0) 0.00e+ 000(1) 0.00e+ 000(1) 6.34e ? 019(0) 7.11e+ 000(1) 9.86e ? 003(0) 2.10e+ 001(1) 3.44e+ 003(1) 1.88e ? 019(1) SspDE 1.44e ? 021 3.82e ? 004 2.97e ? 074 5.78e ? 002 1.57e ? 032 1.35e ? 032 8.25e ? 025 0.00e+ 000 9.02e ? 024 1.93e ? 006 3.55e ? 015 0.00e+ 000 0.00e+ 000 3.99e +000 1.18e ? 001 1.72e ? 002 1.99e+ 001 3.27e+ 003 7.41e ? 025

SspDE algorithm performs much better than the DE/rand/1/bin (F ? 0.5, CR ? 0.3) and DE/rand/1/bin (F ? 0.5, CR ? 0.9) algorithms, and produces comparable results when compared with the JDE and SaDE algorithms on 100-dimensional problems. From the above comparisons, it is concluded that overall the proposed SspDE algorithm is much more ef?cient and effective than the DE/rand/1/bin (F ? 0.5, CR ? 0.3), DE/rand/1/bin (F ? 0.5, CR ? 0.9), JDE and SaDE algorithms in ?nding better solutions for the unconstrained optimization problems with dimensions 10, 30 and 50, respectively. The SspDE algorithm is able to achieve comparable results when compared with the JDE and SaDE algorithms on 100-dimensional problems. 5.3. Parameter sensitivity study 5.3.1. Sensitiveness to population size In this section, an experiment is conducted to investigate the sensitivity of the SspDE algorithm to variations in population size. The population size of all the DE algorithms is set as NP ? 60, 80, 100, 120 and 140, respectively. We use those algorithms to solve

the 30-dimensional functions and the maximum number of function evaluations is ?xed at 300,000. Results, reported in Tables 7–10 (for NP ? 60, 80, 120 and 140, respectively) and Table 4 (for NP ? 100), show that the performance of all algorithms changes with the population size for a given maximum number of function evaluations. However, on average, the SspDE algorithm exhibits superior performance than the other compared DE algorithms in ?nding better solutions with different population sizes. 5.3.2. Sensitiveness to the RP values The impact of the re?lling probability RP is investigated based on the 30-dimensional functions. We ?x the parameters of the SspDE algorithm the same as those in Section 5.1 except that the RP varies from 0.65 to 0.90 with a step equal to 0.05. The overall comparison results of the SspDE algorithm against the other compared algorithms are shown in Table 11. In the table, ‘SspDE better’ (‘SspDE worse’) means the number of median values yielded by the SspDE algorithm signi?cantly better (worse) than that by the others. It can be easily seen from Table 11 that on

Q.-K. Pan et al. / Computers & Operations Research 38 (2011) 394–408

403

Table 8 Comparison of the DE algorithms with population size NP ? 80. Function 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 DE/rand/1/bin (CR ? 0.3, F ? 0.5) 2.27e +001(1) 3.82e ? 004(0) 3.28e ? 032(1) 1.43e ? 005( ? 1) 1.57e ? 032(0) 1.35e ? 032(0) 1.25e +004(1) 0.00e +000(0) 5.38e +003(1) 1.12e +004(1) 7.11e ? 015(1) 3.89e +001(1) 2.85e +001(1) 2.27e +001(1) 9.12e ? 006( ? 1) 3.85e ? 002(1) 1.90e+ 002(1) 7.20e+ 003(1) 1.22e +004(1) DE/rand/1/bin (CR ? 0.9, F ? 0.5) 2.02e + 000(1) 1.82e + 003(1) 6.84e ? 023(1) 5.57e ? 001(1) 1.57e ? 032(0) 1.35e ? 032(0) 2.49e ? 008(1) 0.00e + 000(0) 2.99e ? 008(1) 1.71e ? 004(1) 7.11e ? 015(1) 4.67e + 001(1) 5.23e + 001(1) 2.43e + 000(0) 2.31e + 000(1) 0.00e +000( ? 1) 1.78e + 002(1) 7.05e + 003(1) 8.53e ? 009(1) JDE 6.05e+ 000(1) 3.82e ? 004(0) 4.47e ? 046(1) 4.73e ? 001(1) 1.57e ? 032(0) 1.35e ? 032(0) 2.06e ? 008(1) 0.00e+ 000(0) 5.14e ? 008(1) 7.22e ? 003(1) 3.55e ? 015(0) 0.00e+ 000(0) 0.00e+ 000(0) 5.76e+ 000(1) 4.04e ? 001(1) 9.86e ? 003(0) 5.28e+ 001(1) 4.07e+ 003(1) 2.25e ? 008(1) SaDE 1.65e ? 015(0) 3.82e ? 004(0) 1.08e ? 040(1) 2.60e ? 001(1) 1.57e ? 032(0) 1.35e ? 032(0) 2.50e ? 017(1) 0.00e+ 000(0) 4.15e ? 016(1) 2.83e ? 002(1) 3.55e ? 015(0) 0.00e+ 000(0) 0.00e+ 000(0) 3.99e +000(0) 1.77e +000(1) 9.86e ? 003(0) 2.24e +001(1) 3.47e +003(1) 1.17e ? 016(1) SspDE 9.20e ? 016 3.82e ? 004 1.98e ? 058 9.14e ? 004 1.57e ? 032 1.35e ? 032 1.61e ? 021 0.00e +000 1.18e ? 020 1.93e ? 006 3.55e ? 015 0.00e +000 0.00e +000 3.99e + 000 2.14e ? 003 1.23e ? 002 1.76e +001 3.32e +003 8.01e ? 022

Table 9 Comparison of the DE algorithms with population size NP ? 120. Function 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 DE/rand/1/bin (CR ? 0.3, F ? 0.5) 2.37e + 001(1) 3.82e ? 004(1) 8.03e ? 021(1) 2.84e ? 003(1) 1.57e ? 032(0) 1.35e ? 032(0) 1.72e + 004(1) 0.00e + 000(0) 9.21e + 003(1) 1.74e + 004(1) 7.11e ? 015(1) 4.96e + 001(1) 3.26e + 001(1) 2.40e + 001(1) 1.82e ? 003(1) 1.41e ? 001(1) 1.99e + 002(1) 7.27e + 003(1) 1.84e + 004(1) DE/rand/1/bin (CR ? 0.9, F ? 0.5) 5.60e+ 000(1) 5.88e +003(1) 1.59e ? 011(1) 4.17e ? 005(0) 2.03e ? 024(1) 1.30e ? 023(1) 3.85e ? 003(1) 9.11e ? 024(1) 4.19e ? 003(1) 1.85e ? 001(1) 1.27e ? 012(1) 1.49e +002(1) 1.21e +002(1) 5.69e +000(1) 2.00e ? 005(0) 7.07e ? 012( ? 1) 1.86e +002(1) 7.11e +003(1) 1.48e ? 003(1) JDE 1.31e+ 001(1) 3.82e ? 004(0) 4.35e ? 030(1) 2.17e ? 002(1) 1.57e ? 032(0) 1.35e ? 032(0) 9.49e ? 006(1) 0.00e+ 000(0) 1.87e ? 005(1) 3.35e ? 002(1) 3.55e ? 015(0) 0.00e+ 000(0) 0.00e+ 000(0) 1.33e+ 001(1) 1.91e ? 002(1) 9.86e ? 003( ? 1) 6.54e+ 001(1) 4.33e+ 003(1) 7.46e ? 006(1) SaDE 1.13e ? 004(1) 3.82e ? 004(0) 1.03e ? 028(1) 1.29e ? 003(1) 1.57e ? 032(0) 1.35e ? 032(0) 1.40e ? 014(1) 0.00e+ 000(0) 4.61e ? 013(1) 2.03e ? 003(1) 3.55e ? 015(0) 0.00e+ 000(0) 0.00e+ 000(0) 1.75e ? 002(1) 1.32e ? 002(1) 9.86e ? 003(0) 2.46e+ 001(1) 3.53e+ 003(1) 1.44e ? 015(1) SspDE 1.35e ? 007 3.82e ? 004 6.75e ? 041 1.44e ? 004 1.57e ? 032 1.35e ? 032 1.38e ? 016 0.00e +000 3.79e ? 016 4.74e ? 007 3.55e ? 015 0.00e +000 0.00e +000 1.75e ? 005 3.30e ? 005 1.23e ? 002 1.48e +001 3.15e +003 7.66e ? 017

Table 10 Comparison of the DE algorithms with population size NP ? 140. Function 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 DE/rand/1/bin (CR ? 0.3, F ? 0.5) 2.47e + 001(1) 1.15e ? 001(1) 1.29e ? 017(1) 1.24e ? 002(1) 1.47e ? 029(1) 5.36e ? 029(1) 1.91e + 004(1) 0.00e + 000(1) 1.10e + 004(1) 1.84e + 004(1) 1.07e ? 014(1) 5.34e + 001(1) 3.38e + 001(1) 2.56e + 001(1) 8.08e ? 003(1) 2.08e ? 001(1) 1.96e + 002(1) 7.32e + 003(1) 1.91e + 004(1) DE/rand/1/bin (CR ? 0.9, F ? 0.5) 9.58e +000(1) 6.37e +003(1) 1.59e ? 008(1) 7.49e ? 004(1) 1.36e ? 018(1) 3.82e ? 018(1) 1.45e ? 001(1) 2.61e ? 018(1) 1.01e ? 001(1) 2.20e+ 000(1) 6.89e ? 010(1) 1.63e +002(1) 1.21e +002(1) 9.69e +000(1) 4.05e ? 004(1) 2.05e ? 008( ? 1) 1.90e+ 002(1) 7.13e +003(1) 4.45e ? 002(1) JDE 1.48e+ 001(1) 3.82e ? 004(0) 1.38e ? 025(1) 3.43e ? 003(1) 1.57e ? 032(0) 1.35e ? 032(0) 6.12e ? 005(1) 0.00e+ 000(0) 2.17e ? 004(1) 8.49e ? 002(1) 3.55e ? 015(0) 0.00e+ 000(0) 0.00e+ 000(0) 1.51e+ 001(1) 1.57e ? 003(1) 9.86e ? 003( ? 1) 7.24e+ 001(1) 4.54e+ 003(1) 5.60e ? 005(1) SaDE 8.90e ? 002(1) 3.82e ? 004(0) 2.63e ? 025(1) 9.10e ? 005(0) 1.57e ? 032(0) 1.35e ? 032(0) 1.07e ? 013(1) 0.00e+ 000(0) 1.20e ? 012(1) 2.86e ? 004(1) 3.55e ? 015(0) 0.00e+ 000(0) 0.00e+ 000(0) 2.15e+ 000(1) 3.40e ? 003(1) 9.86e ? 003(0) 2.31e+ 001(1) 3.33e+ 003(1) 3.54e ? 015(0) SspDE 3.43e ? 005 3.82e ? 004 1.52e ? 035 3.35e ? 005 1.57e ? 032 1.35e ? 032 2.39e ? 015 0.00e +000 2.45e ? 014 2.43e ? 006 3.55e ? 015 0.00e +000 0.00e +000 3.95e ? 004 7.60e ? 005 9.86e ? 003 1.41e +001 3.17e +003 3.68e ? 015

404

Q.-K. Pan et al. / Computers & Operations Research 38 (2011) 394–408

Table 11 Comparison of the SspDE algorithm with different RP values. SspDE RP ? 0.65 SspDE better SspDE worse RP ? 0.70 SspDE better SspDE worse RP ? 0.75 SspDE better SspDE worse RP ? 0.80 SspDE better SspDE worse RP ? 0.85 SspDE better SspDE worse RP ? 0.90 SspDE better SspDE worse DE/rand/1/bin (CR ? 0.3, F ? 0.5) DE/rand/1/bin (CR ? 0.9, F ? 0.5) JDE SaDE

13 2

15 2

10 1

7 1

13 2

15 2

10 0

9 0

13 2

15 1

12 0

10 0

14 0

16 1

11 0

10 0

15 0

16 1

11 0

10 0

15 0

10 1

11 0

9 0

Table 12 Comparison of the SspDE algorithm with different LP values. SspDE LP ? 30 SspDE better SspDE worse LP ? 50 SspDE better SspDE worse LP ? 70 SspDE better SspDE worse LP ? 90 SspDE better SspDE worse LP ? 110 SspDE better SspDE worse LP ? 130 SspDE better SspDE worse DE/rand/1/bin (CR ? 0.3, F ? 0.5) DE/rand/1/bin (CR ? 0.9, F ? 0.5) JDE SaDE

14 0

17 1

11 0

9 0

14 0

16 1

11 0

10 0

13 0

15 1

12 0

9 0

13 1

15 1

11 0

10 0

13 1

16 1

12 0

10 0

13 2

15 1

11 0

10 0

Table 13 The DE algorithm with different con?gurations. Algorithms DE1 DE2 DE3 DE4 DE5 DE6 DE7 DE8 DE9 F 0.5 0.5 0.5 0.8 0.2 0.5 0.5 0.5 0.5 CR 0.8 0.5 0.2 0.5 0.5 0.5 0.5 0.5 0.5 Strategies Randomly select from the strategy set determined in Section 3.1

DE/rand/1/bin DE/rand-to-best/2/bin DE/rand/2/bin DE/current-to-rand/1

Q.-K. Pan et al. / Computers & Operations Research 38 (2011) 394–408

405

Table 14 The median value for the DE algorithm with different con?gurations. Algorithms DE1 DE2 DE3 DE4 DE5 DE6 DE7 DE8 DE9 f4 6.19e ? 015 1.30e ? 013 2.96e ? 011 6.58e ? 003 8.07e ? 003 3.00e ? 011 4.65e ? 013 3.99e ? 006 4.70e ? 023 f12 1.70e+ 001 4.76e+ 000 0.00e + 000 1.26e+ 001 0.00e + 000 1.32e ? 007 1.23e+ 000 6.53e+ 000 2.29e+ 001 f17 2.71e+ 001 2.59e+ 001 1.71e+ 001 3.95e+ 001 1.18e+ 001 2.64e+ 001 2.51e+ 001 3.12e+ 001 2.30e+ 001 f19 1.28e ? 017 1.35e ? 010 3.46e ? 008 2.80e +000 7.91e ? 003 7.35e ? 006 8.99e ? 010 1.95e ? 001 2.16e ? 025

1 F and CR values, or the average percentage of strategies 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0 1 2 3 4 5 6 Function evaluations 7 8 9 10 x 104

F CR DE/rand/1 DE/rand-to-best/2 DE/rand/2 DE/current-to-rand/1

Fig. 1. Self-adaptation characteristics of parameters and strategies for function f4.

1 F and CR values, or the average percentage of strategies 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0 1 2 3 4 5 6 Function evaluations 7 8 9 10 x 104

F CR DE/rand/1 DE/rand-to-best/2 DE/rand/2 DE/current-to-rand/1

Fig. 2. Self-adaptation characteristics of parameters and strategies for function f12.

406

Q.-K. Pan et al. / Computers & Operations Research 38 (2011) 394–408

average the SspDE algorithm performs better than the other compared DE algorithms when the RP value is selected in the range [0.65,0.90]. 5.3.3. Sensitiveness to the LP values Overall comparison results of the SspDE algorithm with different LP values on the 30-dimensional functions are presented in Table 12. From Table 12, it can be seen that the SspDE algorithm exhibits higher performance than the other compared DE algorithms when the LP value is in the range [30,130]. 5.4. The self-adaptation property of the SspDE algorithm In order to show the self-adaptation property of the SspDE algorithm, the impact of the trial vector generation strategies and

1 F and CR values, or the average percentage of strategies

control parameters on the performance of the DE algorithm is investigated. We use the DE algorithms with nine different con?gurations, shown in Table 13, to solve the 10-dimensional functions f4, f12, f17 and f19. The population size is set as NP ? 100, and the maximum number of function evaluations is set to 100,000. Each problem is tested with 30 independent replications. The median values over these 30 replications are reported in Table 14. It can be seen from Table 14 that there is no speci?c trial vector generation strategy or value of F and CR, which is effective for all problems. A large CR value is better for functions f4 and f19, whereas a small CR value is favorable for functions f12 and f17. A small F value generates better results for functions f12 and f17, but for function f4 and f19, F ? 0.5 is better. The trial vector generation strategies ‘DE/rand-to-best/2/bin’ and ‘DE/current-to-rand/1’

F

0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0 1 2 3 4 5 6 Function evaluations

CR DE/rand/1 DE/rand-to-best/2 DE/rand/2 DE/current-to-rand/1

7

8

9

x 104 10

Fig. 3. Self-adaptation characteristics of parameters and strategies for function f17.

1 F and CR values, or the average percentage of strategies 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0 1 2 3 4 5 6 Function evaluations 7 8 9 x 104 10

F CR DE/rand/1 DE/rand-to-best/2 DE/rand/2 DE/current-to-rand/1

Fig. 4. Self-adaptation characteristics of parameters and strategies for function f19.

Q.-K. Pan et al. / Computers & Operations Research 38 (2011) 394–408

407

perform better for function functions f4, f17 and f19, but fail for function f12. In the SspDE algorithm, the percentage usage of each strategy and the values of CR and F change as evolution progresses. We plot these variations in Figs. 1–4 to show the self-adaptation of the SspDE algorithm. For the CR and F, we present the variation of overall average value in all the CR and F lists. For the trial vector generation strategies, we show the variation of average percentage of each strategy in all the strategy lists. From Figs. 1–4, it can be observed that the SspDE algorithm can self-adaptively determine the suitable trial vector generation strategy and parameter values for CR and F to match different phases during the evolution. For function f4 the value of CR is increasing from 0.5 to 0.58 in the ?rst 40,000 function evaluations and keeps the value to the end. F is rapidly decreasing to a value about 0.5. As expected, ‘DE/current-to-rand/1’ occupies largest proportion among all the strategies, and ‘DE/rand-to-best/2/bin’ is with higher proportion than the other two strategies. For function f12, CR and F gradually decrease to small values, and the percentage usage of strategies keeps the same rank as shown in Table 14. For the rotated functions f17 and f19, the variation tendency of the strategies and parameters is in accordance with those shown in Table 14, except that ‘DE/rand-to-best/2/bin’ occupies higher proportion than ‘DE/current-to-rand/1’. By multiplying an orthogonal rotation matrix, functions are much more complex and dif?cult since their decision variables become highly relative. It is much more dif?cult for the strategies favoring exploration to ?nd better solutions. Thus, ‘DE/rand-to-best/2/bin’ which has better exploration ability dominates others.

References

[1] Abbass HA. The self-adaptive Pareto differential evolution algorithm. In: Proceedings of the 2002 congress on evolutionary computation, 2002, Honolulu, HI, USA, May 2002, p. 831–6. [2] Brest J, Greiner S, Boskovic B, Mernik M, Zumer V. Self-adapting control parameters in differential evolution: a comparative study on numerical benchmark problems. IEEE Transactions on Evolutionary Computation 2006;10:646–57. [3] Das S, Konar A, Chakraborty UK. Two improved differential evolution schemes for faster global search. In: ACM-SIGEVO proceedings of genetic and evolutionary computation conference (GECCO-2005), Washington DC, USA, 2005, p. 991–8. ¨ ¨ [4] Gamperle R, Muller SD, Koumoutsakos P. A parameter study for differential evolution. In: Grmela A, Mastorakis NE, editors. Advances in intelligent systems, fuzzy systems, evolutionary computation. Interlaken, Switzerland: WSEAS Press; 2002. p. 293–8. [5] Hansen N. Compilation of results on the 2005 CEC benchmark function set, May 4, 2006 /http://www.ntu.edu.sg/home/epnsugan/index_?les/CEC-05/ compareresults.pdfS. [6] /http://www.icsi.berkeley.edu/ $ storn/code.htmlS. [7] Huang VL, Qin AK, Suganthan PN. Self-adaptive differential evolution algorithm for constrained real-parameter optimization, IEEE-CEC-06, July 2006, Canada. [8] Ilonen J, Kamarainen JK, Lampinen J. Differential evolution training algorithm for feed-forward neural networks. Neural Processing Letters 2003;17:93–105. [9] Joshi R, Sanderson AC. Minimal representation multisensor fusion using differential evolution. IEEE Transactions on Systems, Man, and Cybernetics (Part A) 1999;29:63–76. [10] Lampinen J, Zelinka I. On stagnation of the differential evolution algorithm. In: Oˇ smera P, editor. Proceedings of MENDEL 2000, sixth international Mendel conference on soft computing, 2002, p. 76–83. [11] Liang JJ, Suganthan PN, Deb K. Novel composition test functions for numerical global optimization. In: IEEE swarm intelligence symposium 2005, Pasadena, California, June 2005, p. 68–75. [12] Liu J, Lampinen J. A fuzzy adaptive differential evolution algorithm. Soft Computing 2005;9:448–62. [13] Omran MGH, Salman A, Engelbrecht AP. Self-adaptive differential evolution. In: Computational intelligence and security, PT 1, Proceedings of the lecture notes in arti?cial intelligence, 2005, p. 192–9. [14] Onwubolu GC. Design of hybrid differential evolution and group method of data handling networks for modeling and prediction. Information Sciences 2008;178:3616–34. [15] Pan QK, Wang L, Qian B. A novel differential evolution algorithm for bicriteria no-wait ?ow shop scheduling problems. Computers and Operations Research 2009;36:2498–511. [16] Price KV. An introduction to differential evolution. In: Corne D, Dorigo M, Glover F, editors. New ideas in optimization. London (UK): McGraw-Hill; 1999. p. 79–108. [17] Price K, Storn R. Differential evolution: a simple evolution strategy for fast optimization. Dr. Dobb’s Journal of Software Tools 1997;22:18–24. [18] Price K, Storn R, Lampinen J. Differential evolution—a practical approach to global optimization. Berlin: Springer; 2005. [19] Qin AK, Huang VL, Suganthan PN. Differential evolution algorithm with strategy adaptation for global numerical optimization. IEEE Transactions on Evolutionary Computations 2009;13:398–417. [20] Qin AK, Suganthan PN. Self-adaptive differential evolution algorithm for numerical optimization. In: IEEE congress on evolutionary computation (CEC 2005), Edinburgh, Scotland, IEEE Press, September 2005, p. 1785–91. [21] Rogalsky T, Derksen RW, Kocabiyik S. Differential evolution in aerodynamic optimization. In: Proceedings of 46th annual conference of Canadian Aeronautics and Space Institute, Montreal, Quebec, May, 1999, p. 29–36. ¨ ¨ [22] Ronkk onen J, Kukkonen S, Price KV. Real-parameter optimization with differential evolution. In: 2005 IEEE congress on evolutionary computation (CEC 2005), Edinburgh, Scotland, IEEE Press, September 2005, p. 506–13. [23] Storn R, Price K. Differential evolution-a simple and ef?cient adaptive scheme for global optimization over continuous spaces. Technical report TR-95-012, ICSI /http://http.icsi.berkeley.edu/ $ storn/litera.htmlS, 1995. [24] Storn R, Price KV. Differential evolution—a simple and ef?cient heuristic for global optimization over continuous spaces. Journal of Global Optimization 1997;11:341–59. [25] Storn R. On the usage of differential evolution for function optimization. In: Biennial conference of the North American Fuzzy Information Processing Society (NAFIPS), Berkeley, 1996, p. 519–23. [26] Suganthan PN, Hansen N, Liang JJ, et al. Problem de?nitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization. Technical report, Nanyang Technological University, Singapore, May 2005 and Kangal report #2005005, IIT Kanpur, India. [27] Teo J. Exploring dynamic self-adaptive populations in differential evolution. Soft Computing 2006;10:637–86. [28] Wang L, Pan Q-K, Suganthan PN. A novel hybrid discrete differential evolution algorithm for blocking ?ow shop scheduling problems. Computers and Operations Research 2008, doi:10.1016/j.cor.2008.12.004. [29] Yao X, Liu Y, Lin G. Evolutionary programming made faster. IEEE Transactions on Evolution Computation 1999;3:82–102. [30] Zaharie D. Control of population diversity and adaptation in differential evolution algorithms. In: Matousek R, Osmera P, editors. Proceedings of

6. Conclusions Differential evolution (DE) is an ef?cient and powerful search and optimization algorithm widely used in scienti?c and engineering ?elds. In the DE algorithm, trial vector generation strategy and control parameters play a key role in the algorithm’s performance. However, it is dif?cult to select a suitable strategy and the associated parameters, since their best settings can be different for different problems and even for the same problem during different phases of evolution. Therefore, we developed an SspDE algorithm with strategy and control parameter adaptation. In the proposed algorithm, each target individual has its own strategy and control parameters, and during the process of evolution, both strategy and control parameters of each target individual can be gradually self-adapted to match different search phases according to their previous successful experience. We compared the proposed algorithm with two recently developed self-adaptive DE algorithms, and two well-tuned conventional DE algorithms, and demonstrated that the proposed algorithm was overall more effective in obtaining better quality solutions. Our future work will generalize the proposed DE algorithm to solve constraint and multi-objective optimization problems. Acknowledgements Authors acknowledge the ?nancial support offered by the A*Star (Agency for Science, Technology and Research, Singapore) under the Grant #052 101 0020. This research is also partially supported by National Science Foundation of China under Grants 60874075, 70871065, 60834004, Program for New Century Excellent Talents in University (NCET-10-0505), and Open Research Foundation from State Key Laboratory of Digital Manufacturing Equipment and Technology (Huazhong University of Science and Technology).

408

Q.-K. Pan et al. / Computers & Operations Research 38 (2011) 394–408

Mendel 2003, ninth international conference on soft computing, Brno, Czech Republic, June 2003, p. 41–6. [31] Zaharie D, Petcu D. Adaptive pareto differential evolution and its parallelization. In: Proceedings of the ?fth international conference on parallel processing and applied mathematics, Czestochowa, Poland, September 2003, p. 261–8.

[32] Zhang M, Luo WJ, Wang X. Differential evolution with dynamic stochastic selection for constrained optimization. Information Sciences 2008;178: 3043–74. [33] Conover WJ. Practical nonparametric statistics. 2nd ed. John Wiley & Sons; 1980. (p. 225–6).