A Comparative Performance Analysis of Differential Evolution and Dynamic Differential Evolution Variants 1
G. Jeyakumar C. Shunmuga Velayutham Amrita School of Engineering Amrita Vishwa Vidyapeetham, Coimbatore Tamil Nadu, India
[email protected] 2
[email protected] 2
population. Inevitably, it results in slower convergence. To alleviate this problem, a dynamic version of DE called Dynamic Differential Evolution (DDE) has been proposed in [6]. DDE updates the population dynamically and responds to any improvement immediately. Interestingly, little research effort has been devoted to understand and compare the efficacy of DDE variants (which could be conceived by the natural extension of dynamicity to the existing DE variants). In this paper, an empirical analysis of the performance of fourteen DDE variants on six benchmark problems has been carried out along with the comparative performance analysis against the classical counterparts. Despite the fact that a very limited set of 6 benchmark problem will not guarantee reliable conclusion, the analysis indeed give insights about the efficacy of DDE variants and their superiority in performance over their classical counterparts. The remainder of the paper is organized as follows. Section 2 describes the DDE. After a brief review of the related work in Section 3, Section 4 details the design of experiments. Section 5 discusses the simulation results and finally Section 6 concludes the paper.
Abstract—In this paper we present an empirical , comparative performance, analysis of fourteen variants of Differential Evolution (DE) and Dynamic Differential Evolution (DDE) algorithms to solve unconstrained global optimization problems. The aim is to compare DDE, which employs a dynamic evolution mechanism, against DE and to identify the competitive variants which perform reasonably well on problems with different features. The fourteen variants of DE and DDE are benchmarked on 6 test functions grouped by features – unimodal separable, unimodal nonseparable, multimodal separable and multimodal non-separable. The analysis identifies the competitive variants and shows that DDE variants consistently outperform their classical counter parts. Keywords : Differential Evolution; Dynamic Differential Evolution; differential mutation strategies; mean objective function value; probability of convergence
I.
INTRODUCTION
Differential Evolution (DE), proposed by Storn and Price [1, 2], is a very simple but very powerful stochastic global optimizer for continuous search domain. It has been proven a robust global optimizer and has been successfully applied to many global optimization problems [3, 4] with superior performance in both widely used benchmark function and real-world applications [5]. Like all Evolutionary Algorithms (EA’s), DE is a stochastic population-based search method that employs repeated cycles of recombination and selection to guide the population towards the vicinity of global optimum. However, it has some unique characteristics that makes it different from other members of EA family. DE uses a differential mutation operation based on the distribution of parent solutions in the current population, coupled with recombination with a predetermined parent to generate a trial vector (offspring) followed by a one-to-one greedy selection scheme between the trial vector and the parent. Depending on the way the parent solutions are perturbed to generate a trial vector, there exists many trial vector generation strategies and consequently many DE variants. The conceptual and algorithmic simplicity, high convergence characteristics and robustness of DE has made it one of the popular techniques for real-valued parameter optimization. Nevertheless, from the point of view of population updating, DE is static i.e. DE responds to the population progress after a time lag. The whole population in DE remains unchanged until it is replaced by a new
c 978-1-4244-5612-3/09/$26.00 2009 IEEE
II.
DYNAMIC DIFFERENTIAL EVOLUTION
The algorithmic description of a classical DE is depicted in “Fig. 1”. As can be seen from the DE algorithm, the repeated cycles of differential mutation and crossover do not make use of any progress taking place in the current generation consequently, employing the optimal individuals from last generation to produce trial vectors. Even if better fit individuals are generated in the current generation, they are reserved for use in the next generation. The dynamic differential evolution employs a dynamic evolution mechanism in place of the above said static evolution mechanism of classical DE. Except this significant difference, DDE inherits all the basic operations of DE and its three crucial control parameters viz., population size (NP), scaling factor (F) and crossover rate (CR). The dynamic evolution mechanism in DDE updates both the current optimal individual with the new competitive individual (if better than the current optimal) and the non optimal individuals dynamically. Consequently, the trial vectors are always generated using the newly updated population and thus DDE always responds to any progress immediately. Owing to the dynamicity in population
463
Population Initialization X(0) { x1(0),..,xNP(0) } g 0 Compute { f(x1(g)),....f(xNP(g)) } while the stopping condition is false do for i = 1 to NP do yi generatemutant(X(g)) zi crossover(xi(g), yi) if f(zi) < f(xi(g)) then xi(g+1) zi else xi(g+1) xi(g) end if end for g g+1 Compute{ f(x1(g)),......f(xNP(g))} end while
Figure 1.
General structure of DE algorithm
updating, the creation of every NP trial vectors is considered as one generation of DDE in the current work. By extending the dynamic evolution mechanism to the seven commonly used differential mutation strategies, as listed in Table I, and two crossover schemes (binomial and exponential), we get fourteen possible variants of DDE. Following the standard DE nomenclature used in the literature, the fourteen DDE variants can be written as follows. DDE/rand/1/bin, DDE/rand/1/exp, DDE/best/1/bin, DDE/best/1/exp, DDE/rand/2/bin, DDE/rand/2/exp, DDE/best/2/bin, DDE/best/2/exp, DDE/current-torand/1/bin, DDE/current-to-rand/1/exp, DDE/current-tobest/1/bin, DDE/current-to-best/1/exp , DDE/rand-tobest/1/bin and DDE/rand-to-best/1/exp. In this paper, an empirical comparative performance analysis between DE and DDE variants has been attempted. RELATED WORKS
III.
Qing proposed the dynamic differential evolution in [6] and analyzed the performance of DDE/best/1 variant on a function minimization problem with 8, 16, 24, 50 and 100 optimization parameters and on a benchmark electromagnetic inverse scattering problem. The study concluded that DDE significantly outperforms the classical DE. TABLE I. Nomenclature rand/1
A recent study by Qing [7] compared DDE/rand/1/bin and DDE/best/1/bin against their classical counterparts. The test bed involved around 37 test functions with dimension less than 10 and three application problems with 6, 8, 9, 16 and 24 dimensions. Only the representative results on the test bed have been presented. The work concluded DDE/best/1/bin as the most competitive variant among the scrutinized four strategies. Menzura-Montes et. al. [8] empirically compared the performance of eight DE variants, involving arithmetic recombination along with binomial and exponential, on unconstrained optimization problems. The study concluded rand/1/bin, best/1/bin , current-to-rand/1/bin and rand/2/dir as the most competitive variants. IV.
In this paper, we investigate the performance of DDE variants and compare them against classical DE variants, by implementing fourteen variants on a set of benchmark problems with high dimensionality and different features. We have chosen six test functions [8, 9], of dimensionality 30, grouped by the feature - unimodal separable, unimodal nonseparable, multimodal separable and multimodal nonseparable. The details of the benchmark problems are described as follows. • f01 - Schwefel’s Problem 2.21 ݂ ݄ܿݏሺݔሻ ൌ ݉ܽ ݅ݔሼȁ ݅ݔȁǡ ͳ ݅ ͵Ͳሽ െͳͲͲ ݔ ͳͲͲǢ כݔൌ ሺͲǡͲǤ ǤͲሻǢ݂ ݄ܿݏሺ כݔሻ ൌ Ͳ •
ܸǡீ ൌ ܺ௦௧ǡீ ܨቀܺభ ǡீ െ ܺమ ǡீ ቁ
rand/2
ܸǡீ ൌ ܺభ ǡீ ቀܺమǡீ െ ܺయ ǡீ ܺర ǡீ െ ܺఱ ǡீ ቁ
best/2
ܸǡீ ൌ ܺ௦௧ǡீ ቀܺభǡீ െ ܺమ ǡீ ܺయ ǡீ െ ܺర ǡீ ቁ
current-to-rand/1
ܸǡீ ൌ ܺǡீ ቀܺయǡீ െ ܺǡீ ቁ ܨቀܺభ ǡீ െ ܺమ ǡீ ቁ
current-to-best/1
ܸǡீ ൌ ܺǡீ ൫ܺ௦௧ǡீ െ ܺǡீ ൯ ቀܺభ ǡீ െ ܺమ ǡீ ቁ
rand-to-best/1
ܸǡீ ൌ ܺయ ǡீ ቀܺ௦௧ǡீ െ ܺయ ǡீ ቁ ቀܺభ ǡீ െ ܺమ ǡீ ቁ
ʹ
െͳͲͲ ݔ ͳͲͲ; כݔൌ ሺͲǡͲǤ ǤͲሻǢ݂ ܵܦ݄ܿݏሺ כݔሻ ൌ Ͳ •
f03 – Generalized Schwefel’s Problem 2.26 ݂݄ܵܿ ሺݔሻ ൌ σ͵Ͳ ݅ൌͳ൫ ݅ݔ൫ඥȁ ݅ݔȁ൯൯ െͷͲͲ ݔ ͷͲͲ; כ ݔൌ ሺͶʹͲǤͻͺǡ ǥ ǡͶʹͲǤͻͺሻǢ ݂௦ ሺ כ ݔሻ ൌ െͳʹͷͻǤͷ
•
DIFFERENTIAL MUTATION STRATEGIES ܸǡீ ൌ ܺభ ǡீ ܨቀܺమ ǡீ െ ܺయ ǡீ ቁ
f02 – Schwefel’s Problem 1.2 ݅ ݂ ܵܦ݄ܿݏሺݔሻ ൌ σ͵Ͳ ݅ൌͳ൫σ݆ൌͳ ݆ݔ൯
f04 – Generalized Restrigin’s Function ଶ ݂ܴܽ ݏሺݔሻ ൌ σ͵Ͳ ݅ൌͳൣݔ െ ͳͲ
ሺʹߨݔ ሻ ͳͲ൧ െͷǤͳʹ ݔ ͷǤͳʹ; כݔൌ ሺͲǡͲǤ ǤͲሻǢ ݂ܴܽ ݏሺ כݔሻ ൌ Ͳ
Variant
best/1
DESIGN OF EXPERIMENTS
•
f05 - Generalized Rosenbrock's Function ଶଽ
݂ோ௦ ሺݔሻ ൌ ȁͳͲͲሺݔାଵ െ ݔଶ ሻଶ ሺݔ െ ͳሻଶ ȁ ୀଵ
െ͵Ͳ ݔ ͵ͲǢ כ ݔൌ ሺͳǡ ǥ ǡͳሻǢ݂ோ௦ ሺ כ ݔሻ ൌ Ͳ •
f06-Generalized Griewank's Function ݂ீ ሺݔሻ ൌ
ଵ ସ
௫
ଶ ଷ σଷ ୀଵ ݔ െ ςୀଵ ܿ ݏቀ ቁ ͳ
ξ
െͲͲ ݔ ͲͲǢ (= כ ݔ0,…,0); ݂ீ ሺ כ ݔሻ ൌ Ͳ
464
2009 World Congress on Nature & Biologically Inspired Computing (NaBIC 2009)
TABLE II.
All the test functions have an optimum value at zero except f03. In order to show the similar results, the description of f03 was adjusted to have its optimum value at zero by just adding the optimal value for the function with 30 decision variables (12569.486618164879) [8]. The parameters for all the DE and DDE variants were: population size NP = 60 and maximum number of generations = 3000 (consequently, the maximum number of function evaluations calculate to 180,000). The moderate population size and number of generations were chosen to demonstrate the efficacy of both DE and DDE variants in solving the chosen problems. The variants will stop before the maximum number of generations is reached only if the tolerance error (which has been fixed as an error value of 1 x 10-12 ) with respect to the global optimum is obtained. Following [8,10], we defined a range for the scaling factor, F ∈ [0.3,0.9] and this value is generated anew at each generation for all variants. We use the same value for K as F. The crossover rate, CR, was tuned for each variant-test function combination. Eleven different values for the CR viz. {0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0}were tested for each variant-test function combination for DE and DDE separately. For each combination of variant-test function-CR value, 50 independent runs were conducted. Based on the obtained results, a bootstrap test was conducted in order to determine the confidence interval for the mean objective function value. The CR value corresponding to the best confidence interval was chosen to be used in our experiment. The fourteen variants of both DE and DDE along with the CR values for each test function are presented in Tables II and III. As EA’s are stochastic in nature, 100 independent runs were performed per variant per test function (by initializing the population for every run with uniform random initialization within the search space). For the sake of performance analysis among the variants, we present the mean objective function values (MOV) and the probability of convergence [11] for each variant-test function combination. V.
RESULTS AND DISCUSSION
The simulation results for the unimodal separable function f01 is presented in Table IV with the variants sorted by their performance. For the function f01, the result shows that the best results were provided by */rand-to-best/1/bin, */best/2/bin and */rand/1/bin variants. The worst performance was provided by */rand/2/exp, */current-tobest/1/exp, */current-to-rand/1/exp and DE/best/1/exp variants. It is interesting to note that the best and worst performance for f01 were provided by similar set of DE and DDE variants. Except for three variants showing moderate performance, in all other cases DDE performs better than DE in terms of MOV. This could be observed even in the case of worst performing variants. Table IV also shows the simulation results for the unimodal nonseparable function f02. The best performance was shown by */best/2/bin, */best/2/exp, DDE/best/1/exp,
CR VALUES USED FOR DE VARIANTS
rand/1/bin
f01 0.9
f02 0.9
f03 0.5
DE f04 0.1
f05 0.9
f06 0.1
rand/1/exp
0.1
0.1
0.0
0.1
0.1
0.9
best/1/bin
0.8
0.3
0.1
0.1
0.1
0.1
best/1/exp
0.0
0.1
0.7
0.1
0.2
0.8
rand/2/bin
0.9
0.9
0.2
0.1
0.3
0.1
rand/2/exp
0.0
0.1
0.3
0.1
0.1
0.9
best/2/bin
0.1
0.8
0.7
0.1
0.1
0.1
best/2/exp
0.1
0.1
0.3
0.1
0.1
0.9
current-to-rand/1/bin
0.3
0.9
0.4
0.1
0.1
0.1
current-to-rand/1/exp
0.0
0.0
0.3
0.1
0.1
0.9
Variant
current-to-best/1/bin
0.2
0.9
0.8
0.1
0.1
0.2
current-to-best/1/exp
0.0
0.0
0.2
0.1
0.1
0.9
rand-to-best/1/bin
0.9
0.9
0.8
0.9
0.3
0.1
rand-to-best/1/exp
0.1
0.1
0.4
0.1
0.1
0.9
TABLE III.
CR VALUES USED FOR DDE VARIANTS
rand/1/bin
f01 0.2
f02 0.9
f03 0.2
DDE f04 0.1
rand/1/exp
0.9
0.9
0.3
best/1/bin
0.9
0.6
best/1/exp
0.9
0.9
rand/2/bin
0.2
rand/2/exp best/2/bin
Variant
f05 0.9
f06 0.1
0.9
0.9
0.9
0.1
0.1
0.9
0.9
0.6
0.9
1.0
0.9
0.9
0.3
0.1
0.9
0.1
0.9
0.9
0.6
0.9
0.9
0.9
0.1
0.9
0.0
0.1
0.6
0.1
best/2/exp
0.9
0.9
0.4
0.9
0.9
0.9
current-to-rand/1/bin
0.2
1.0
0.5
0.1
0.1
0.5
current-to-rand/1/exp
1.0
1.0
0.0
0.9
1.0
0.9
current-to-best/1/bin
0.2
1.0
0.0
0.1
0.1
0.2
current-to-best/1/exp
1.0
1.0
0.0
0.9
0.9
0.9
rand-to-best/1/bin
0.3
0.9
0.1
0.1
0.8
0.1
rand-to-best/1/exp
0.9
0.9
0.3
0.9
0.9
0.9
DDE/best/1/bin and DDE/rand/1/bin variants. The worst performing variants were */rand/2/exp, */current-to-best/*, */current-to-rand/* and DE/best/1/*. The top 4 variants for f01 displayed similar high performance in the case of f02 too as can be seen in Table IV. For the unimodal nonseparable function all DDE variants have outperformed their classical counterparts. The superiority of DDE is evident in the case of worst performing variants. The simulation results for multimodal separable functions f03 and f04 are presented in Table V with the variants sorted by their performance. In case of f03 the best performance is provided by */best/1/bin variants. The DDE/best/1/exp has performed poorly in comparison with its classical counterpart. Nevertheless, DDE performs better than DE in most of the variants. In case of f04 */rand-tobest/1/bin and */rand/1/bin have once again emerged as best performing variants along with */rand/2/bin. Similarly,
2009 World Congress on Nature & Biologically Inspired Computing (NaBIC 2009)
465
TABLE IV.
MOV OBTAINED FOR UNIMODAL SEPARABLE AND NONSEPARABLE FUNCTIONS
Unimodal Separable Function – f01 DE
Unimodal Nonseparable Function – f02
DDE
DE
Variant
MOV
Variant
MOV
Variant
rand-to-best/1/bin
0.00
rand-to-best/1/bin
0.00
best/2/bin
best/2/bin
0.00
best/2/bin
0.00
rand/1/bin
0.00
rand/1/bin
best/2/exp
0.05
rand/2/bin
0.06
best/1/bin
DDE Variant
MOV
0.00
best/2/bin
0.00
best/2/exp
0.00
best/2/exp
0.00
0.00
rand-to-best/1/bin
0.07
best/1/exp
0.00
best/2/exp
0.04
rand/1/bin
0.07
best/1/bin
0.00
rand/2/bin
0.05
rand-to-best/1/exp
0.20
rand/1/bin
0.00
1.96
best/1/bin
1.81
rand/1/exp
0.31
rand-to-best/1/bin
0.01
rand-to-best/1/exp
3.38
rand/1/exp
3.32
rand/2/bin
1.64
rand/1/exp
0.13
current-to-rand/1/bin
3.68
rand-to-best/1/exp
3.48
best/1/bin
13.27
rand-to-best/1/exp
0.14
current-to-best/1/bin
3.71
current-to-rand/1/bin
3.70
best/1/exp
57.39
rand/2/bin
1.17
rand/1/exp
3.76
current-to-best/1/bin
3.77
rand/2/exp
269.86
current-to-best/1/bin
61.54
rand/2/exp
32.90
best/1/exp
9.40
current-to-best/1/exp
2972.62
current-to-rand/1/bin
61.85
best/1/exp
37.36
rand/2/exp
31.34
current-to-rand/1/exp
3110.90
current-to-rand/1/exp
62.17
current-to-best/1/exp
56.67
current-to-best/1/exp
51.63
current-to-rand/1/bin
3210.36
current-to-best/1/exp
63.70
current-to-rand/1/exp
57.52
current-to-rand/1/exp
52.10
current-to-best/1/bin
3444.00
rand/2/exp
233.07
TABLE V.
MOV
MOV OBTAINED FOR MULTIMODAL SEPARABLE FUNCTIONS
Multimodal Separable Function – f03
Multimodal Separable Function – f04
DE
DE
DDE
DDE
Variant
MOV
Variant
MOV
Variant
best/1/bin
0.00
best/1/bin
0.00
rand-to-best/1/bin
0.00
rand-to-best/1/bin
0.00
best/1/exp
0.01
best/2/exp
0.07
rand/2/bin
0.00
rand/2/bin
0.00
best/2/exp
0.08
rand-to-best/1/exp
0.09
rand/1/bin
0.00
rand/1/bin
0.00
current-to-best/1/exp
0.10
best/2/bin
0.10
best/2/bin
0.69
best/2/bin
0.65
rand/1/exp
0.10
current-to-rand/1/exp
0.10
best/1/bin
4.33
best/1/bin
3.63
rand-to-best/1/exp
0.12
rand/1/exp
0.11
current-to-best/1/bin
37.04
current-to-rand/1/bin
37.49
current-to-rand/1/exp
0.12
current-to-best/1/bin
0.11
current-to-rand/1/bin
37.75
current-to-best/1/bin
38.26
rand/1/bin
0.13
current-to-best/1/exp
0.12
rand/1/exp
47.93
rand-to-best/1/exp
47.40
current-to-rand/1/bin
0.14
rand-to-best/1/bin
0.13
rand-to-best/1/exp
48.09
rand/1/exp
47.67
best/2/bin
0.17
current-to-rand/1/bin
0.14
best/1/exp
50.74
best/1/exp
52.06
current-to-best/1/bin
0.19
rand/1/bin
0.15
best/2/exp
80.63
best/2/exp
79.78
rand-to-best/1/bin
0.22
rand/2/bin
0.21
rand/2/exp
101.38
rand/2/exp
102.78
rand/2/bin
0.22
rand/2/exp
0.23
current-to-best/1/exp
232.80
current-to-rand/1/exp
232.59
rand/2/exp
0.27
best/1/exp
4.46
current-to-rand/1/exp
235.14
current-to-best/1/exp
232.94
*/rand/2/exp, */current-to-rand/1/exp and */current-tobest/1/exp have once again displayed poor performance, as in the case of f01 and f02. DDE variants still maintain an edge over the classical counterparts in performance. Table VI lists the simulation results obtained in the case of multimodal nonseparable functions f05 and f06. Test function f05 was not solved by any variant. However, */best/2/* variants have displayed relatively better performance. */rand/2/exp, */current-to-rand/1/exp and */current-to-best/1/exp were the consistent poor performing variants. Interestingly */best/1/* and */rand/2/exp variants have also shown poor performance in both the cases (DE and DDE). However in case of f06, five variants displayed best performance */rand-to-best/1/bin, */best/2/bin and
466
MOV
Variant
MOV
*/rand/1/bin were the consistent best performing variants. This best performance is shared by */rand/2/bin and */current-to-best/1/bin variants. As with f05, */best/1/* variants have shown a relatively poor performance. Based on the overall results in Table IV, V and VI the most competitive variants were */rand-to-best/1/bin, */best/2/bin and */rand/1/bin. The variants */rand/2/bin and */best/2/exp also showed good performance consistently. On the other hand, the worst overall performance were consistently displayed by variants */current-to-best/1/exp and */current-to-rand/1/exp. The variants DDE/current-torand/1/bin and */rand/2/exp were also displaying poor performance. */best/1/* variants show good performance for unimodal nonseparable and multimodal separable functions.
2009 World Congress on Nature & Biologically Inspired Computing (NaBIC 2009)
TABLE VI.
MOV OBTAINED FOR MULTIMODAL NON SEPARABLE FUNCTIONS
Multimodal NonSeparable Function – f05 DE
Multimodal NonSeparable Function – f06
DDE
Variant
MOV
DE
Variant
MOV
DDE
Variant
MOV
Variant
MOV
best/2/exp
1.12
best/2/exp
0.78
rand/2/bin
0.00
rand/2/bin
0.00
best/2/bin
2.32
best/2/bin
1.87
rand-to-best/1/bin
0.00
Rand-to-best/1/bin
0.00
rand-to-best/1/bin
17.37
rand-to-best/1/bin
15.92
best/2/bin
0.00
best/2/bin
0.00
rand/2/bin
19.01
rand/2/bin
16.17
rand/1/bin
0.00
rand/1/bin
0.00
rand/1/bin
21.99
rand/1/bin
17.20
current-to-best/1/bin
0.00
current-to-best/1/bin
0.00
rand-to-best/1/exp
24.54
rand-to-best/1/exp
32.52
current-to-rand/1/bin
0.00
best/2/exp
0.03
rand/1/exp
25.48
rand/1/exp
41.34
best/2/exp
0.03
rand/1/exp
0.05
current-to-rand/1/bin
52.81
current-to-best/1/bin
56.01
rand/1/exp
0.05
Rand-to-best/1/exp
0.06
current-to-best/1/bin
56.91
current-to-rand/1/bin
56.68
rand-to-best/1/exp
0.05
current-to-rand/1/bin
0.14
rand/2/exp
0.21
rand/2/exp
0.19
rand/2/exp
2741.32
rand/2/exp
best/1/exp
64543.84
best/1/bin
32747.01
current-to-best/1/exp
1.21
current-to-rand/1/exp
1.21
current-to-best/1/exp
119685.68
current-to-rand/1/exp
254655.74
current-to-rand/1/exp
1.21
current-to-best/1/exp
1.22
current-to-rand/1/exp
199243.32
current-to-best/1/exp
271844.82
best/1/bin
3.72
best/1/bin
2.64
best/1/bin
585899.88
best/1/exp
449714.63
best/1/exp
5.91
best/1/exp
5.11
TABLE VII. Sno
1877.42
NUMBER OF SUCCESSFUL RUNS AND PROBABILITY OF CONVERGENCE CALCULATED FOR THE DE VARIANTS f01
f02
f03
f04
f05
f06
nc
Pc (%)
1
best/2/bin
Variant
100
100
1
47
38
100
386
64.33
2
rand-to-best/1/bin
100
79
0
100
0
100
379
63.17
3
rand/1/bin
100
73
4
100
0
100
377
62.83
4
best/1/bin
79
86
88
3
0
1
257
42.83
5
rand/2/bin
0
0
1
100
0
100
201
33.50
6
best/2/exp
1
100
17
0
29
44
191
31.83
7
best/1/exp
0
58
85
0
0
0
143
23.83
8
current-to-best/1/bin
0
0
3
0
0
96
99
16.50
9
current-to-rand/1/bin
0
0
2
0
0
96
98
16.33
10
rand-to-best/1/exp
0
10
6
0
0
69
85
14.17
11
rand/1/exp
0
4
7
0
0
68
79
13.17
12
rand/2/exp
0
0
2
0
0
3
5
0.83
13
current-to-best/1/exp
0
0
5
0
0
0
5
0.83
14
current-to-rand/1/exp
0
0
3
0
0
0
3
0.50
It is worth noting that binomial recombination showed a better performance over the exponential recombination. Also, the DDE variants have consistently outperformed the DE variants in terms of mean objective function value. When we compared the successful runs of both DE and DDE variants on the total runs, in case of 8 variants DDE converged with approximately 600 to 10,000 function evaluations more than that of the DE counterparts whereas for remaining 6 variants, DE converged with approximately 900 to 90,000 function evaluations more than that of DDE counterparts. To investigate on the influence of setting K = F, we let both K and F generated anew in the range [0.3, 0.9], at each generation for the best and worst performing variants
(with parameter K) of both DE and DDE. The simulations showed almost similar results for both DE and DDE. Next in our experiment, the probability of convergence (Pc), the percentage of successful runs to total runs, is calculated for each variant-function combination. This measure identifies variants having higher convergence capability to global optimum. It is calculated as the mean percentage of number of successful runs out of total number of runs i.e. Pc = (nc / nt)% where nc is total number of successful runs made by each variant for all the functions and nt is total number of runs, in our experiment nt = 6 * 100 = 600. The convergence probability for both DE and DDE variants were calculated separately and the results are shown
2009 World Congress on Nature & Biologically Inspired Computing (NaBIC 2009)
467
TABLE VIII.
NUMBER OF SUCCESSFUL RUNS AND PROBABILITY OF CONVERGENCE CALCULATED FOR THE DDE VARIANTS Sno
f01
f02
f03
f04
f05
f06
nc
Pc (%)
1
best/2/bin
Variant
100
100
11
49
48
96
404
67.33
2
rand-to-best/1/bin
100
84
6
100
0
100
390
65.00
3
rand/1/bin
100
85
1
100
2
100
388
64.67
4
best/2/exp
2
100
14
0
58
44
218
36.33
5
rand/2/bin
0
0
2
100
0
100
202
33.67
6
best/1/bin
0
99
80
3
0
0
182
30.33
7
best/1/exp
0
100
78
0
0
0
178
29.67
8
current-to-best/1/bin
0
0
6
0
0
91
97
16.17
9
rand/1/exp
0
6
6
0
0
69
81
13.50
10
rand-to-best/1/exp
0
6
5
0
0
59
70
11.67
11
rand/2/exp
0
0
2
0
0
6
8
1.33
12
current-to-best/1/exp
0
0
7
0
0
0
7
1.17
13
current-to-rand/1/bin
0
0
5
0
0
0
5
0.83
14
current-to-rand/1/exp
0
0
0
0
0
0
0
0.00
in Tables VII and VIII respectively, with the variants sorted by the convergence probability. The tables present the number of successful runs made by each variant for each function, the total number of successful runs and the probability of convergence. As can be seen from the table, the competitive variants identified earlier viz. */best/2/bin , */rand-to-best/1/bin and */rand/1/bin have higher probability of convergence. Similar trend could be observed for */rand/2/bin and */best/2/exp variants. The worst performing variants */current-to-best/1/exp, */current-to-rand/1/exp and */rand/2/exp were found to have the least probability of convergence. It is worth noting that DDE has given overall more number of successful runs that that of DE. Consequently, DDE variants have higher probability of convergence compared to classical DE variants, irrespective of their recombination type. VI.
CONCLUSION
In this paper we presented an empirical comparative performance analysis of fourteen variants of DDE against those of DE. The variants were tested on 6 test functions of dimension 30, grouped by their modality and decomposability. The experiments identified */best/2/bin, */rand-to-best/1/bin and */rand/1/bin variants as the most competitive variants in terms of the mean objective function values. The worst performing variants were */current-tobest/1/exp, */current-to-rand/1/exp and */rand/2/exp. Infact the calculation of probability of convergence reiterated the observation about the performance of above said variants. It was also observed that binomial recombination showed a better performance over the exponential recombination. Overall, DDE variants often outperformed DE variants and consistently showed superior performance. Our future work would involve validating above observations by testing DE and DDE variants on a larger suite of test functions.
468
REFERENCES [1]
R. Storn and K. Price , “Differential Evolution – A simple and efficient heuristic strategy for global optimization and continuous spaces,” Journal of Global Optimization, Vol. 11, No. 4, pp. 341-359, 1997. [2] R. Storn and K. Price . “Differential Evolution – A simple and efficitent adaptive scheme for global optimization over continuous spaces”, Technical Report TR-95-012, ICSI , March 1995. [3] K. V. Price. “An Introduction to Differential Evolution,” In D. Corne, M. Dorigo , and F. Glover, editors, New Ideas in Optimization, pp. 79-108. Mc Graw-Hill, UK, 1999. [4] K. Price, R. M. Storn , and J. A. Lampinen, Differential Evolution : A Practical Approach to Global Optimization, Springer-Verlag, 2005. [5] J. Vesterstrom and R. Thomsen, “A comparative study of Differential Evolution, Particle Swarm Optimization and Evolutionary Algorithm on numerical benchmark problems,” In Proceedings of the IEEE Congress on Evolutionary Computation (CEC’2004), Vol. 3, pp. 1980-1987, June 2004. [6] Anyong Qing, “Dynamic Differential Evolution Strategy and applications in electromagnetic inverse scattering problems,” IEEE Transactions on Geoscience and Remote Sensing, Vol. 44, No. 1, January 2006. [7] Anyong Qing , “A studuy on base vector for Differential Evolution,” 2008 IEEE World Congress on Computational Intelligence/2008 IEEE Congress on Evolutionary Computation, Hong Kong, June 1-6 , pp. 550-556. 2008. [8] Efren Mezura-Montes, Jesus Velazquez-Reyes and Carios A. Coello Coello, “A comparative study on Differential Evolution variants for global optimization,” Gennetic and Evolutionary Computation Conferrence , GECCO’06, July 8-12, 2006. [9] X. Yao, Y. Liu, K. H Liang and G. Lin, “Fast evolutionary algorithms”, In G. Rozenberg, T. Back, and A. Eiben, editors, Advances in Evolutionary Computing : Theory and Applications, pp. 45-94, Springer-Verlag, New York, NY, USA, 2003. [10] Efren Mezura-Montes , Personal Communication, Unpublished [11] Vitaliy Feoktistov. Differential Evolution In Search of Solutions., Springer, 2006.
2009 World Congress on Nature & Biologically Inspired Computing (NaBIC 2009)
