# Sufficient Conditions for Global Convergence of Differential Evolution Algorithm

Authors: Zhongbo Hu; Shengwu Xiong; Qinghua Su; Xiaowei Zhang
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

The differential evolution algorithm (DE) is one of the most powerful stochastic real-parameter optimization algorithms. The theoretical studies on DE have gradually attracted the attention of more and more researchers. However, few theoretical researches have been done to deal with the convergence conditions for DE. In this paper, a sufficient condition and a corollary for the convergence of DE to the global optima are derived by using the infinite product. A DE algorithm framework satisfying the convergence conditions is then established. It is also proved that the two common mutation operators satisfy the algorithm framework. Numerical experiments are conducted on two parts. One aims to visualize the process that five convergent DE based on the classical DE algorithms escape from a local optimal set on two low dimensional functions. The other tests the performance of a modified DE algorithm inspired of the convergent algorithm framework on the benchmarks of the CEC2005.


---

## Body

## 1. Introduction

The differential evolution algorithm (DE) is a population-based stochastic parallel evolutionary algorithm. DE emerged as a very competitive form of evolutionary computing since it was proposed by Storn and Price in 1995 [1]. DE or its variants have been achieving competitive ranking in various competitions held on the IEEE Congress on Evolutionary Computation (CEC) Conference Series [2, 3]. According to frequently reported comprehensive studies [4–6], DE outperforms many other optimization methods in terms of convergence speed and robustness over common benchmark functions. Compared to most other evolutionary algorithms, DE is much more simple and straightforward to implement, and has very few control parameters. Perhaps due to these advantages, it has got many practical applications, such as function optimization [7–11], multiobjective optimization [12], classification [13], and scheduling [14].Theoretical studies of algorithms are very important to understand their search behaviors and to develop more efficient algorithms. With the popularity of DE in applications, more and more researchers pay attention to the theoretical studies on DE. According to the research contents, the main results of theoretical studies on DE can be divided into three classes as follows.


### 1.1. Researches on the Timing Complexity of DE

DE is a population-based stochastic search algorithm. Its runtime-complexity analysis is a critical issue. Zielinski et al. [15] investigated the runtime complexity of DE for various stopping criteria including a fixed number of generations (Gmax) and maximum distance criterion (MaxDist). MaxDist means that algorithms stop the execution if the maximum distance from every vector to the best population member is below a given threshold.


### 1.2. Researches on the Dynamical Behavior of DE’s Population

This class focuses on investigating the evolving process of DE’s population. For instance, the development of the expected population variance and population distribution over time is an important issue. Zaharie [16–20] theoretically analyzed the influence of the variation operators (mutation and crossover) and their parameters on the expected population variance. In 2009, Zaharie [21] theoretically investigated the influence of the crossover operators (including classical binomial and exponential strategies) and the crossover probability on the expected population variance. Dasgupta et al. [22, 23] proposed a mathematical model of the underlying evolutionary dynamics of a one-dimensional DE-population, and the model showed that the fundamental dynamics of the each parameter vector in DE employs the gradient-descent type search strategy. Wang and Huang [24] developed a stochastic model of a one-dimensional DE-population to analyze the evolving process of the population distribution over time.


### 1.3. Researches on the Convergence Property of DE

This class investigates the limit behavior of DE’s population. The main issue is that under which assumptions can it be guaranteed that DE or its variants can reach an optimal solution [25]. Technically speaking, commonly used concepts include convergence in probability, almost sure convergence, and convergence in distribution.Xue et al. [26] performed a mathematical modeling and convergence analysis of continuous multi-objective differential evolution (MODE) under certain simplified assumptions, and this work was extended in [27]. Zhao et al. [28] proposed a hybrid differential evolution with transform function (HtDE) and proved its convergence. Sun [29] developed a Markov chain modeling and proved that the classical DE does not hold with convergence in probability. He et al. [30] defined the differential operator (DO) as a random mapping from the solution space to the Cartesian product of solution space and analyzed the asymptotic convergence of DE by using the random contraction mapping theorem. Ghosh et al. [31] established asymptotic convergence behavior of a classical DE (DE/rand/1/bin) algorithm by applying the concepts of Lyapunov stability theorems. And the analysis is based on the assumption that the objective function has the following two properties, (1) the objective function has the second-order continual derivative in the search space, and (2) it possesses a unique global optimum in the range of search.The studies of this paper are confined to the third class, convergence property of DE.We note that the conclusion of [30, 31] is in contradiction with [29]. According to the inference process, the asymptotic convergence in [30] refers to almost sure convergence. In fact, if DE does not hold with convergence in probability, then it does not hold with almost sure convergence. We also note that the value of the random mapping DO defined in [30] may be greater than 1, which is debatable. In [31], the asymptotic convergence analysis of DE/rand/1/bin, which was proved by applying Lyapunov stability theorems, should be a local convergence property. The reason is, according to Lyapunov stability theorems, the distribution of the initial population depends on the maximum region of the asymptotic stability. So for some functions, DE/rand/1/bin possesses asymptotic stability property if and only if initial individuals are closed enough to the global optimum. In addition, from the mutation operators of the classical DE, it can be derived that DE, if its population traps in a local optimum, cannot escape. This property was employed by [29] to prove that the classical DE does not possess global convergence in probability.Taking into account that a convergent algorithm may have stronger robustness than a divergent one. Zhao et al. [28] developed a convergent algorithm, HtDE and proved its convergence. Zhan and Zhang [32] proposed a DE with random walk. Xue et al. [26, 27] analyzed MODE’s convergence. However, the conditions for global convergence of DE have not been explored. In this paper, the following problems will be addressed. (i)
What are sufficient conditions for the global convergence of DE?(ii)
What is the algorithm framework of the convergent DE?(iii)
Which operators can assist the classical DE to hold with a certain asymptotic convergence?The discussion in this paper will be undertaken in a general measurable space, andinfinite production will be used as an analysis tool.This paper is organized as follows. Section2 introduces the classical DE. Section 3 proves a sufficient condition and a corollary for the convergence of DE to the global optima. Section 4 presents a DE algorithm framework satisfying the convergence conditions. Section 5 proves several operators satisfying the convergent algorithm framework. Section 6 gives numerical experiments to verify the robustness of the convergent DE. Section 7 analyzes and discusses the theoretical conclusions and the experimental results in detail. Section 8 summarizes this paper and indicates several directions for future research.


## 1.1. Researches on the Timing Complexity of DE

DE is a population-based stochastic search algorithm. Its runtime-complexity analysis is a critical issue. Zielinski et al. [15] investigated the runtime complexity of DE for various stopping criteria including a fixed number of generations (Gmax) and maximum distance criterion (MaxDist). MaxDist means that algorithms stop the execution if the maximum distance from every vector to the best population member is below a given threshold.


## 1.2. Researches on the Dynamical Behavior of DE’s Population

This class focuses on investigating the evolving process of DE’s population. For instance, the development of the expected population variance and population distribution over time is an important issue. Zaharie [16–20] theoretically analyzed the influence of the variation operators (mutation and crossover) and their parameters on the expected population variance. In 2009, Zaharie [21] theoretically investigated the influence of the crossover operators (including classical binomial and exponential strategies) and the crossover probability on the expected population variance. Dasgupta et al. [22, 23] proposed a mathematical model of the underlying evolutionary dynamics of a one-dimensional DE-population, and the model showed that the fundamental dynamics of the each parameter vector in DE employs the gradient-descent type search strategy. Wang and Huang [24] developed a stochastic model of a one-dimensional DE-population to analyze the evolving process of the population distribution over time.


## 1.3. Researches on the Convergence Property of DE

This class investigates the limit behavior of DE’s population. The main issue is that under which assumptions can it be guaranteed that DE or its variants can reach an optimal solution [25]. Technically speaking, commonly used concepts include convergence in probability, almost sure convergence, and convergence in distribution.Xue et al. [26] performed a mathematical modeling and convergence analysis of continuous multi-objective differential evolution (MODE) under certain simplified assumptions, and this work was extended in [27]. Zhao et al. [28] proposed a hybrid differential evolution with transform function (HtDE) and proved its convergence. Sun [29] developed a Markov chain modeling and proved that the classical DE does not hold with convergence in probability. He et al. [30] defined the differential operator (DO) as a random mapping from the solution space to the Cartesian product of solution space and analyzed the asymptotic convergence of DE by using the random contraction mapping theorem. Ghosh et al. [31] established asymptotic convergence behavior of a classical DE (DE/rand/1/bin) algorithm by applying the concepts of Lyapunov stability theorems. And the analysis is based on the assumption that the objective function has the following two properties, (1) the objective function has the second-order continual derivative in the search space, and (2) it possesses a unique global optimum in the range of search.The studies of this paper are confined to the third class, convergence property of DE.We note that the conclusion of [30, 31] is in contradiction with [29]. According to the inference process, the asymptotic convergence in [30] refers to almost sure convergence. In fact, if DE does not hold with convergence in probability, then it does not hold with almost sure convergence. We also note that the value of the random mapping DO defined in [30] may be greater than 1, which is debatable. In [31], the asymptotic convergence analysis of DE/rand/1/bin, which was proved by applying Lyapunov stability theorems, should be a local convergence property. The reason is, according to Lyapunov stability theorems, the distribution of the initial population depends on the maximum region of the asymptotic stability. So for some functions, DE/rand/1/bin possesses asymptotic stability property if and only if initial individuals are closed enough to the global optimum. In addition, from the mutation operators of the classical DE, it can be derived that DE, if its population traps in a local optimum, cannot escape. This property was employed by [29] to prove that the classical DE does not possess global convergence in probability.Taking into account that a convergent algorithm may have stronger robustness than a divergent one. Zhao et al. [28] developed a convergent algorithm, HtDE and proved its convergence. Zhan and Zhang [32] proposed a DE with random walk. Xue et al. [26, 27] analyzed MODE’s convergence. However, the conditions for global convergence of DE have not been explored. In this paper, the following problems will be addressed. (i)
What are sufficient conditions for the global convergence of DE?(ii)
What is the algorithm framework of the convergent DE?(iii)
Which operators can assist the classical DE to hold with a certain asymptotic convergence?The discussion in this paper will be undertaken in a general measurable space, andinfinite production will be used as an analysis tool.This paper is organized as follows. Section2 introduces the classical DE. Section 3 proves a sufficient condition and a corollary for the convergence of DE to the global optima. Section 4 presents a DE algorithm framework satisfying the convergence conditions. Section 5 proves several operators satisfying the convergent algorithm framework. Section 6 gives numerical experiments to verify the robustness of the convergent DE. Section 7 analyzes and discusses the theoretical conclusions and the experimental results in detail. Section 8 summarizes this paper and indicates several directions for future research.


## 2. Classical Differential Evolution

DE is a competitive algorithm for solving continuous optimization problem. Consider the optimization problem:(1)max{f(x);x∈S},
where S is a measurable space and f(x) is the objective function (or the fitness of x) which satisfies that for any bounded x∈S, f(x) is bounded. The optimal solution set is denoted as S*={x*∣f(x*)=max{f(x)},x∈S}, where x* is the optimum solution.Letμ(·) be a measure to space S. Perhaps μ(S*)=0, which means that S* is a set with measure 0. This is not convenient to analyze. In view of the accuracy of practical problems, without loss of generality, we can consider an expanded set Sδ*={x∣f(x*)-f(x)<δ}, where δ is a small positive value. We can choose an appropriateδ, which can meet the accuracy and make μ(Sδ*)>0. We use Sδ*   (μ(Sδ*)>0) to replace the setS*in this paper. Meanwhile, in order to simplify the calculation, let us suppose that the search space S=In, where I=[0,1], n is the dimension of S.The classical DE [2, 33, 34] works through a simple cycle of reproduction and selection operators after initialization. The reproduction operator includes mutation and crossover operators. The classical DE for solving the above problem (1) can be described in detail as follows.(1)
Initialization: Generate an initial population denoted byX(0), and let t←0.(2)
Reproduction: Generate a trial populationY(t) from the target population X(t).
Mutation: generate a new population fromX(t) by a mutation operator, denoted by V(t).Crossover: generate a new population fromX(t) and V(t) by a crossover operator, denoted by U(t), and let Y(t)←U(t).(3)
Selection: generate a new population fromX(t) and Y(t) by a selection operator, denoted by Z(t).(4)
If the termination condition is satisfied, then stop; else lett←t+1 and X(t)←Z(t); then go to Step 2.The initial population is generated by assigning random values in the search space to the variables of every solution.


### 2.1. Reproduction Operator

#### 2.1.1. Mutation Operator

After initialization, DE creates a donor vectorvit corresponding to each individualxitin the tth generation through the mutation operator. Several most frequently referred mutation strategies are presented as follows:DE/rand/1:vit=xr1t+F(xr2t-xr3t),DE/best/1:vit=xbestt+F(xr1t-xr2t),DE/cur-to-best/1:vit=xit+F(xbestt-xit)+F(xr1t-xr2t),DE/best/2:vit=xbestt+F(xr1t-xr2t)+F(xr3t-xr4t),DE/rand/2:vit=xr1t+F(xr2t-xr3t)+F(xr4t-xr5t),where xbestt denotes the best individual of the current generation, the indices r1,r2,r3,r4,r5∈Sr={1,2,…,NP}∖{i} are uniformly random integers mutually different and distinct from the running index i, NP is population size, and F∈(0,1] is a real parameter, called mutation factor or scaling factor.


#### 2.1.2. Crossover Operator

Following mutation, thecrossoveroperator is applied to further increase the diversity of the population. In crossover, the target vector, xit, is combined with elements from the donor vector, vit, to produce the trial vector, uit, using the binomial crossover,
(2)ui,jt={vi,jt,ifrand(0,1)≤Crorj=jrand,xi,jt,otherwise,
where Cr∈(0,1) is the probability of crossover and jrand is a random integer in [1,n]. Unless otherwise mentioned, rand(0,1) is a uniformly distributed random number confined in the range [0,1].


### 2.2. Selection Operator

Finally, the selection operator is employed to maintain the most promising trial individuals in the next generation. The classical DE adopts a simple selection scheme. It compares the objective values of the target vectorxit and trial vector uit. If the trial individual reduces the value of the objective function then it is accepted for the next generation; otherwise the target individual is retained in the population. The selection operator is defined as
(3)xig+1={uit,iff(uit)<f(xit),xit,otherwise.


## 2.1. Reproduction Operator

### 2.1.1. Mutation Operator

After initialization, DE creates a donor vectorvit corresponding to each individualxitin the tth generation through the mutation operator. Several most frequently referred mutation strategies are presented as follows:DE/rand/1:vit=xr1t+F(xr2t-xr3t),DE/best/1:vit=xbestt+F(xr1t-xr2t),DE/cur-to-best/1:vit=xit+F(xbestt-xit)+F(xr1t-xr2t),DE/best/2:vit=xbestt+F(xr1t-xr2t)+F(xr3t-xr4t),DE/rand/2:vit=xr1t+F(xr2t-xr3t)+F(xr4t-xr5t),where xbestt denotes the best individual of the current generation, the indices r1,r2,r3,r4,r5∈Sr={1,2,…,NP}∖{i} are uniformly random integers mutually different and distinct from the running index i, NP is population size, and F∈(0,1] is a real parameter, called mutation factor or scaling factor.


### 2.1.2. Crossover Operator

Following mutation, thecrossoveroperator is applied to further increase the diversity of the population. In crossover, the target vector, xit, is combined with elements from the donor vector, vit, to produce the trial vector, uit, using the binomial crossover,
(2)ui,jt={vi,jt,ifrand(0,1)≤Crorj=jrand,xi,jt,otherwise,
where Cr∈(0,1) is the probability of crossover and jrand is a random integer in [1,n]. Unless otherwise mentioned, rand(0,1) is a uniformly distributed random number confined in the range [0,1].


## 2.1.1. Mutation Operator

After initialization, DE creates a donor vectorvit corresponding to each individualxitin the tth generation through the mutation operator. Several most frequently referred mutation strategies are presented as follows:DE/rand/1:vit=xr1t+F(xr2t-xr3t),DE/best/1:vit=xbestt+F(xr1t-xr2t),DE/cur-to-best/1:vit=xit+F(xbestt-xit)+F(xr1t-xr2t),DE/best/2:vit=xbestt+F(xr1t-xr2t)+F(xr3t-xr4t),DE/rand/2:vit=xr1t+F(xr2t-xr3t)+F(xr4t-xr5t),where xbestt denotes the best individual of the current generation, the indices r1,r2,r3,r4,r5∈Sr={1,2,…,NP}∖{i} are uniformly random integers mutually different and distinct from the running index i, NP is population size, and F∈(0,1] is a real parameter, called mutation factor or scaling factor.


## 2.1.2. Crossover Operator

Following mutation, thecrossoveroperator is applied to further increase the diversity of the population. In crossover, the target vector, xit, is combined with elements from the donor vector, vit, to produce the trial vector, uit, using the binomial crossover,
(2)ui,jt={vi,jt,ifrand(0,1)≤Crorj=jrand,xi,jt,otherwise,
where Cr∈(0,1) is the probability of crossover and jrand is a random integer in [1,n]. Unless otherwise mentioned, rand(0,1) is a uniformly distributed random number confined in the range [0,1].


## 2.2. Selection Operator

Finally, the selection operator is employed to maintain the most promising trial individuals in the next generation. The classical DE adopts a simple selection scheme. It compares the objective values of the target vectorxit and trial vector uit. If the trial individual reduces the value of the objective function then it is accepted for the next generation; otherwise the target individual is retained in the population. The selection operator is defined as
(3)xig+1={uit,iff(uit)<f(xit),xit,otherwise.


## 3. Convergence Condition

There are different kinds of definitions of convergence for analyzing asymptotic convergence of algorithms. The following definition of convergence, that is, convergence in probability, is used in this paper.Definition 1.
Let{X(t),t=0,1,2,…} be a population sequence generated by using DE to solve the optimization problem (1). Then DE converges to the global optimum, if and only if
(4)limt→∞p{X(t)∩Sδ*≠∅}=1.
Let us give a sufficient condition for the convergence of DE.Theorem 2.
Consider using DE to solve the optimization problem (1). In the tkth target population X(tk), there exists at least one individual x, which corresponds to the trial individual y by a reproduction operator, such that
(5)p{y∈Sδ*}≥ζ(tk)>0,
and the series ∑k=1∞‍ζ(tk) diverges; then DE converges to the optimal solution setSδ*.
Where{tk,k=1,2,…} denotes any subsequence of natural number set, p{y∈Sδ*} denotes the probability that y belongs to the optimal solution set Sδ*, and ζ(tk) is a small positive value which may change as tk.Proof.
In DE, each target individual corresponds to a trial individual by its reproduction operator. According to the condition of Theorem2, we can get the probability that all the individuals of the tkth trial population Y(tk) do not belong to the optimal solution set Sδ*:(6)p{Y(tk)∩Sδ*=∅}≤1-ζ(tk),
so, we can get the probability that all the individuals of every trial population in previous (tk-1) iterations do not belong to the optimal solution set Sδ*:(7)∏i=1tk-1‍p{Y(i)∩Sδ*=∅}≤∏i=1k-1‍(1-ζ(i)).
And because of the elitist selection operation in DE, the optimal individual of trail populations will retain the next generation population. So we can get the probability that the tkth population X(tk) does not contain optima:
(8)p{X(tk)∩Sδ*=∅}=∏i=1tk-1‍p{Y(i)∩Sδ*=∅}≤∏i=1k-1‍(1-ζ(i)).
So for the classical DE with elitist selection, we have
(9)limt→∞p{X(t)∩Sδ*≠∅}≥limk→∞p{X(tk)∩Sδ*≠∅}=1-limk→∞p{X(tk)∩Sδ*=∅}=1-limk→∞∏i=1tk-1‍p{Y(i)∩Sδ*=∅}≥1-limk→∞∏i=1k-1‍(1-ζ(i))=1-∏i=1+∞‍(1-ζ(i)).
And from the property of the infinite product [35]:
(10)ifseries∑i=1+∞‍ζ(i)diverges,then∏i=1+∞‍(1-ζ(i))=0.
So for the divergent series ∑i=1+∞‍ζ(i), we can get that
(11)limt→∞p{X(t)∩Sδ*≠∅}=1.
According to Definition 1, this theorem holds.Corollary 3.
In Theorem2, if ζ(t) equals ever to a positive constant ζ>0, then DE converges to the optimal solution Sδ*.Proof.
Obviously, the series∑t=0+∞‍ζ(t) diverges when ζ(t) equals ever to a positive constant ζ>0. From Theorem 2, we can get that DE converges to the optimal solution Sδ*.Now we give several observations to the above conditions as follows.(i)
Theorem2 means that if the probability entering into the optimal set in a certain sub-sequence population is large enough, then the modified DE converges to the global optimal set in probability. And the population states need no ergodicity.(ii)
Corollary3 is just a special case of Theorem 2 and is very easy to check. There are some improved DE algorithms such as HtDE proposed by Zhao et al. [28], DE-RW proposed by Zhan and Zhang [32], DE-MC proposed by Braak [36], which satisfies the convergence condition of Theorem 2 (or Corollary 3).(iii)
He and Yu [37] and Rudolph [38] presented several important conclusions on convergence conditions for evolutionary algorithms. These conclusions do apply to DE algorithm. However, Comparing with these conclusions, Theorem 2 is more relaxed and easier to check.


## 4. Algorithm Framework Possessing Convergence

As the introduction section analyzed, it cannot be guaranteed that the classical DE holds with the global convergence. However, DE can converge to the global optimal solution if its reproduction operation satisfies the sufficient conditions given in Theorem2 or Corollary 3. A DE algorithm framework integrating an extra mutation component will be given in this section. Owing to the fact that the purpose of using the extra mutation is to assist the classical DE to converge, this paper addresses to the operator as AsCo-mutation operator.According to the sufficient conditions proved above, we can define the AsCo-mutation operator as follow.Definition 4.
AsCo-mutation is a mutation operator assisting the classical DE to converge. It satisfies the following conditions.(1)
To a certain sub-sequence{X(tk),k=1,2,…} of population sequence {X(t),t=1,2,…}, AsCo-mutation changes at least one individual in each {X(tk),k=1,2,…} with a positive probability.(2)
LetY(tk) denote the population generated by using AsCo-mutation; there exists at least one individual y in Y(tk), such that
(12)p{y∈Sδ*}≥ζ(tk)>0,and the series∑k=1+∞‍ζ(tk) diverges.
Taking into account the fact that the algorithm framework using AsCo-mutation will contain some convergent algorithms of DE family, this paper addresses to the algorithm framework as CDE. The algorithm framework CDE can be described as follows.(1)
Initialization: generate an initial population denoted byX(0), and let t←0.(2)
Reproduction: generate a trial populationY(t) from the target population X(t).
Mutation: generate a new population fromX(t) by a mutation operator, denoted by V(t).Crossover: generate a new population fromX(t) and V(t) by a crossover operator, denoted by U(t).AsCo-mutation: if the certain condition generating sub-sequence population is satisfied, then generate a new populationW(t) from U(t) by AsCo-mutation and let Y(t)←W(t); otherwise, let Y(t)←U(t).(3)
Selection: generate a new population fromX(t) and Y(t) by a selection operator, denoted by Z(t).(4)
If the termination condition is satisfied, then stop; else lett←t+1 and X(t)←Z(t); then go to Step 2.
On the basis of DE, the reproduction operator of CDE increases a step, AsCo-mutation. Obviously, the algorithm framework CDE satisfies Theorem2 when the AsCo-mutation satisfies the Definition 4. That is to say, CDE, which employs the AsCo-mutation given by the Definition 4, converges to the global optimum.


## 5. Several Mutation Operators Satisfying Convergence Condition

Like DE algorithm, most evolutionary algorithms for numerical optimization problems use vectors of floating point numbers for their chromosomal representations. For such representations, many mutation operators [39] have been proposed. The most common mutation operators include Uniform mutation [40] and Gaussian mutation [41, 42]. We introduce these operators and prove that they meet the definition of AsCo-mutation for CDE in turn.


### 5.1. Uniform Mutation

Uniform mutation replaces the solution vectorx with a uniformly distributed random vector ξ confined in the domain S(S=In). Each component of the vector ξ is a uniformly distributed (independent identically distributed) random number from [0,1]. So the density function of ξ can be expressed as:
(13)pξ(x)={1,ifx∈In,0,otherwise.As shown in the CDE algorithm framework, suppose that AsCo-mutation operator employed by CDE is Uniform mutation. Letw denote the new individual generated by Uniform mutation; then the probability that w belongs to the optimal solution set can be calculated as follow:
(14)p{w∈Sδ*}=∫Sδ*‍pξ(x)dm=μ(Sδ*)>0.The method that CDE uses Uniform mutation is flexible, such as mutating an arbitrary individual selected from the setU(t) at a given probability Pac and mutating more than one individual. Let k(k<NP) denote the number of mutated individuals, then the probability Pone/W that at least one of W(t) belongs to the optimal solution set can be calculated as follow:
(15)Pone/W≥1-[1-p{w∈Sδ*}·Pac]k=1-[1-μ(Sδ*)·Pac]k>0,
where the Pac is an empirical probability, Pac∈(0,1], and the diversity of the population will gradually enhance as Pac increases.In addition, the implementation of Uniform mutation operator can be also flexible. For example, in order to keep the tradeoff between exploration and exploitation, this paper presents the following operator.DE/um-best/1:
(16)
v
i
t
=
x
i
t
+
F
(
x
best
t
-
x
i
t
)
+
rand
(
0,1
)
(
x
r
b
1
t
-
x
r
b
2
t
)
,
where rand(0,1) denotes a uniform random number in [0,1]. The xrb1, xrb2 are boundary individuals at a given probability Pb, each element of which equals either the upper boundary or the lower boundary value. The rb1, rb2 are uniform random integers in [1,⌊NP(1+Pb)⌋]. That is, when the index rb1(rb2) is no less than NP, xrb1(xrb2) will takes a boundary individual. Obviously, if xrb1,j takes the upper boundary value of the jth dimension while xrb2,j takes the lower boundary value (and vice-versa), then the element vi,jt is ergodic in the jth dimension. Therefore the individualvitcan be ergodic in the search space like Uniform mutation operator.


### 5.2. Gaussian Mutation

Gaussian mutation modifies all components of the solution vectorx by adding a random noise:
(17)x~=x+η,
where η is a vector of independent random Gaussian numbers with a mean of zero and standard deviations σ. The density function of η can be expressed as:
(18)pη(y)=(1σ2π)n·∏i=1n‍exp(-yi22σ2)=(1σ2π)n·exp(-∑i=1n‍yi22σ2).Now, let us suppose that AsCo-mutation operator employed by CDE is Gaussian mutation. Then the probability thatw generated by Gaussian mutation belongs to the optimal solution set can be calculated as follow:
(19)p{w∈Sδ*}=∫S~δ*‍pη(y)dm,
whereS~δ*=Sδ*-x={z-x∣z∈Sδ*}.On the other hand, for any individualx∈S=In, such that S~δ*⊆[-1,1]n. So
(20)pη(y)≥(1σ2π)n·exp(-n2σ2),∀y∈S~δ*.
Implying that
(21)p{w∈Sδ*}≥μ(S~δ*)·(1σ2π)n·exp(-n2σ2)=μ(Sδ*)·(1σ2π)n·exp(-n2σ2)>0.Like uniform mutation, the used method of Gaussian mutation is flexible. As beforek(k<NP) denotes the number of individuals mutated by Gaussian mutation operator, Pac denotes the probability that each individual is mutated, and Pone/W denotes the probability that at least one of W(t) belongs to the optimal solution set. Then Pone/W can be calculated as follow:
(22)Pone/W≥1-[1-p{w∈Sδ*}·Pac]k≥1-[1-μ(Sδ*)·(1σ2π)n·exp(-n2σ2)]k>0.Obviously, letζ(t)=Pone/W, uniform mutation and Gaussian mutation operators satisfy Definition 4. And thus we can get the following Theorem 5.Theorem 5.
DE algorithm employing uniform mutation or Gaussian mutation operator converges in probability to the global optimum of the optimization problem (1).


## 5.1. Uniform Mutation

Uniform mutation replaces the solution vectorx with a uniformly distributed random vector ξ confined in the domain S(S=In). Each component of the vector ξ is a uniformly distributed (independent identically distributed) random number from [0,1]. So the density function of ξ can be expressed as:
(13)pξ(x)={1,ifx∈In,0,otherwise.As shown in the CDE algorithm framework, suppose that AsCo-mutation operator employed by CDE is Uniform mutation. Letw denote the new individual generated by Uniform mutation; then the probability that w belongs to the optimal solution set can be calculated as follow:
(14)p{w∈Sδ*}=∫Sδ*‍pξ(x)dm=μ(Sδ*)>0.The method that CDE uses Uniform mutation is flexible, such as mutating an arbitrary individual selected from the setU(t) at a given probability Pac and mutating more than one individual. Let k(k<NP) denote the number of mutated individuals, then the probability Pone/W that at least one of W(t) belongs to the optimal solution set can be calculated as follow:
(15)Pone/W≥1-[1-p{w∈Sδ*}·Pac]k=1-[1-μ(Sδ*)·Pac]k>0,
where the Pac is an empirical probability, Pac∈(0,1], and the diversity of the population will gradually enhance as Pac increases.In addition, the implementation of Uniform mutation operator can be also flexible. For example, in order to keep the tradeoff between exploration and exploitation, this paper presents the following operator.DE/um-best/1:
(16)
v
i
t
=
x
i
t
+
F
(
x
best
t
-
x
i
t
)
+
rand
(
0,1
)
(
x
r
b
1
t
-
x
r
b
2
t
)
,
where rand(0,1) denotes a uniform random number in [0,1]. The xrb1, xrb2 are boundary individuals at a given probability Pb, each element of which equals either the upper boundary or the lower boundary value. The rb1, rb2 are uniform random integers in [1,⌊NP(1+Pb)⌋]. That is, when the index rb1(rb2) is no less than NP, xrb1(xrb2) will takes a boundary individual. Obviously, if xrb1,j takes the upper boundary value of the jth dimension while xrb2,j takes the lower boundary value (and vice-versa), then the element vi,jt is ergodic in the jth dimension. Therefore the individualvitcan be ergodic in the search space like Uniform mutation operator.


## 5.2. Gaussian Mutation

Gaussian mutation modifies all components of the solution vectorx by adding a random noise:
(17)x~=x+η,
where η is a vector of independent random Gaussian numbers with a mean of zero and standard deviations σ. The density function of η can be expressed as:
(18)pη(y)=(1σ2π)n·∏i=1n‍exp(-yi22σ2)=(1σ2π)n·exp(-∑i=1n‍yi22σ2).Now, let us suppose that AsCo-mutation operator employed by CDE is Gaussian mutation. Then the probability thatw generated by Gaussian mutation belongs to the optimal solution set can be calculated as follow:
(19)p{w∈Sδ*}=∫S~δ*‍pη(y)dm,
whereS~δ*=Sδ*-x={z-x∣z∈Sδ*}.On the other hand, for any individualx∈S=In, such that S~δ*⊆[-1,1]n. So
(20)pη(y)≥(1σ2π)n·exp(-n2σ2),∀y∈S~δ*.
Implying that
(21)p{w∈Sδ*}≥μ(S~δ*)·(1σ2π)n·exp(-n2σ2)=μ(Sδ*)·(1σ2π)n·exp(-n2σ2)>0.Like uniform mutation, the used method of Gaussian mutation is flexible. As beforek(k<NP) denotes the number of individuals mutated by Gaussian mutation operator, Pac denotes the probability that each individual is mutated, and Pone/W denotes the probability that at least one of W(t) belongs to the optimal solution set. Then Pone/W can be calculated as follow:
(22)Pone/W≥1-[1-p{w∈Sδ*}·Pac]k≥1-[1-μ(Sδ*)·(1σ2π)n·exp(-n2σ2)]k>0.Obviously, letζ(t)=Pone/W, uniform mutation and Gaussian mutation operators satisfy Definition 4. And thus we can get the following Theorem 5.Theorem 5.
DE algorithm employing uniform mutation or Gaussian mutation operator converges in probability to the global optimum of the optimization problem (1).


## 6. Experimental Verification

It is proved in the previous sections that CDE algorithms possess convergence in probability, which only means it can be guaranteed that CDE algorithms reach an optimal solution when the iteration times approaches infinity, but does not mean that CDE can find out the optimal solution within finite iteration times. However, a convergent algorithm should generally hold stronger robustness. Thus this section gives experiments by being composed of two parts to verify CDE’s robustness. One aims to visualize the process escaping from a local optimal set of CDE on two low dimensional functions. The other is conducted to test a modified DE algorithm, which is inspired of the above convergence theory, on the benchmark functions of the CEC2005.


### 6.1. Experiments on Low Dimensional Functions

To achieve the aims mentioned above, experiments are conducted on two numerical functions which are chosen according to the experimental results of [43–46]. One is the DE deceptive function [45], which can lead the classical DE to trap in the local optimum. The other is the Rastrigin function. In [45, 46], nineteen benchmark functions including the rastrigin function were tested using the classical DE. Those results indicated that the optimization effect of the rastrigin function is one of the worst.


#### 6.1.1. Deceptive Function

Consider(23)f(x)={-3sinc(2x+10),if-10≤x<0,-x·sin(xπ),if0≤x≤10,
where the function sinc(t) is given by
(24)sinc(t)={1,ift=0,sinπtπt,ift≠0.The landscape of DE deceptive function is shown in Figure1. The global optimum of the function is x=-5.0 with the function value f(x)=-3. There is a deceptive local minimum x=8.5060 with function value f(x)=-2.9160in this test function.Figure 1
DE’s deceptive function.


#### 6.1.2. Rastrigin Function (2 Dimensions)

Consider(25)f(x)=20+∑i=12‍((xi)2-10cos(2πxi)),000000x∈[-5.12,5.12]2.The global optimum of the function isx=(0,0) with the function value f(x)=0. There are many local optima in this test function.Let CDE-um denote the CDE algorithm using uniform mutation operator. Suppose that CDE-um mutates the worst individual ofU(t) at probability 1, and the new individual is directly retained to the next generation. Experiments were conducted to compare five typical versions of the classic DE with CDE-um algorithm. All experiments were implemented for 50 independent replications. The convergence times and convergence ratio on the 50 replications were reported.In order to show the robustness of CDE-um, we reported the number of function evaluations (FES) to achieve the Ter_Err within Max_FES. Table1 gave the FES of 50 independent replications of five typical versions on the DE’s deceptive function, while Table 2 reported the FES on the Rastrigin function. Those typical versions included DE/best/1 versus CDE-um/best/1, DE/rand/1 versus CDE-um/rand/1, DE/cur-to-best/1 versus CDE-um/cur-to-best/1, and DE/best/2 versus CDE-um/best/2, as well as DE/rand/2 versus CDE-um/best/2. Table 3 analyzes the results of Tables 1 and 2. From the statistics of Table 3, we can see that the ratio (ConRa) converging to the optimum of CDE-um is much higher than the corresponding DE.Table 1
FES to achieve the Ter_Err for DE's deceptive function.
Alg.
best/1
rand/1
cur-to-best/1
best/2
rand/2
DE
CDE-um
DE
CDE-um
DE
CDE-um
DE
CDE-um
DE
CDE-um
FES
176
192
272
416
448
824
264
384
392
632
—
4240
—
184032
—
3328
—
424
560
504
—
147504
—
3920
—
2160
272
744
560
504
—
500832
304
464
—
1384
—
1808
336
1296
—
26200
—
312
—
560
—
1552
536
600
—
163976
448
6248
—
1360
—
320
—
808
—
1568
368
592
—
464
296
312
472
888
—
200
368
727168
—
2944
—
464
560
936
—
5448
320
312
592
664
392
912
424
472
—
66712
—
312
—
22736
304
392
—
768
—
98824
320
5040
—
520
272
1448
352
744
—
82080
—
177312
344
240
—
416
504
648
—
50208
288
520
592
4272
—
368
—
800
—
5408
272
320
—
824
272
408
360
704
—
3096
352
400
416
976
288
344
576
680
—
152256
304
352
—
832
288
320
—
528
—
1.41
E
+
06
—
312
—
4200
—
3592
432
624
—
312624
256
312
—
1192
288
256
480
672
—
370328
224
508880
—
1232
—
608
—
672
—
176
256
2144
—
1328
272
2600
368
784
—
205016
—
632248
—
1240
312
352
376
592
184
168
328
360
672
376
328
464
392
720
—
607768
312
688
—
2888
—
416
408
672
—
2200
—
2240
—
632
—
464
352
896
—
184240
—
1312
536
752
312
520
472
1080
160
406128
—
448
552
408
368
360
—
672
—
268560
—
817456
—
9792
—
2456
448
560
—
295208
—
360
—
1128
—
776
352
744
—
38936
336
336
—
672
—
416
—
728
—
160
296
402096
472
512
208
328
496
784
—
126144
—
368
—
520
336
4360
—
576
—
759336
312
184160
752
2456
—
376
—
840
—
292232
304
2064
392
680
—
480
320
5032
—
24032
—
336
632
936
272
2088
352
656
—
240
—
107664
—
2456
272
2696
456
552
—
555152
—
1432
—
1008
320
1096
336
1664
168
265536
264
105600
—
352
232
512
—
752
168
2256
296
1864
—
1680
360
352
384
760
—
55616
280
320
—
20664
—
904
—
832
—
1.11
E
+
06
336
248
—
592
—
376
352
824
176
263744
—
11136
—
800
408
448
616
69016
—
123896
352
400
456
2168
264
960
536
592
—
200
352
1456
288
672
288
384
544
792
—
784008
304
238752
—
1368
320
5320
520
2536
—
164408
—
29432
—
1072
304
1248
488
584
208
252816
—
4216
392
704
—
568
496
536
—
2088
—
3200
432
560
280
440
576
536
—
542560
—
312
616
472
440
368
—
848
192
1768
—
80536
—
640
—
432
—
672
—
743632
304
320
—
592
—
2976
408
680
“FES” denotes the number of function evaluations. “—” indicates that the algorithm cannot find the optimum within Max_FES.Table 2
FES to achieve the Ter_Err for Rastrigin function.
Alg.
best/1
rand/1
cur-to-best/1
best/2
rand/2
DE
CDE-um
DE
CDE-um
DE
CDE-um
DE
CDE-um
DE
CDE-um
FES
—
103376
—
1680
1184
824
1088
1232
2000
2400
—
1.60
E
+
06
1392
1472
1408
3328
976
1392
2112
2432
560
1.19
E
+
06
1664
1424
1264
2160
1264
1392
1584
2512
—
942224
—
1200
1392
1384
1168
1280
1936
2176
—
672
1440
1584
1280
560
1136
1280
1792
2480
—
452064
1696
1600
1184
1360
1120
1312
1856
2304
560
624
1536
1456
1600
464
1088
1184
2000
1792
720
688
1424
1648
1280
2944
—
1472
—
2352
—
576
1296
1552
1312
664
—
1296
1920
2128
672
576
1184
1248
1184
22736
1056
1296
1776
1936
—
198368
1424
1424
2720
520
1072
1280
2176
2368
—
60336
—
1856
1104
240
1200
1280
2000
2480
656
5.27
E
+
06
1424
1584
1136
4272
896
5840
1840
2304
—
267360
1552
28192
1376
824
1056
1056
1728
2288
—
3.16
E
+
06
1568
1344
1376
976
1136
1408
1792
2720
672
1.11
E
+
06
1296
1440
—
832
1136
1552
2416
2144
608
800
1408
1856
1200
4200
800016
1216
1936
2240
672
2.54
E
+
06
1600
1600
1456
1192
1088
1568
2112
2496
704
3.75
E
+
06
1536
3712
1184
1232
1168
1232
2096
2512
560
236592
1328
1648
1344
1328
1072
1408
1904
2240
—
3.91
E
+
06
1536
1808
1952
1240
—
1328
2336
2368
—
241776
1200
1872
1280
376
1216
1312
1744
2880
—
1072
1408
218208
1344
2888
1152
1248
2000
2512
—
4.70
E
+
06
1520
1408
1232
632
1264
1152
1904
2464
—
8.20
E
+
06
1344
689360
1136
752
1200
5568
1856
2352
—
640
1424
1488
1376
408
1184
1424
1808
2448
—
788880
1344
3.49
E
+
06
1376
9792
1216
1424
2416
2512
576
656
1408
1168
1056
1128
1168
1296
1856
2240
640
560
1408
1536
1184
672
960
1344
1856
2432
—
2.74
E
+
06
1376
228048
5136
512
1312
1312
1888
2512
—
672
1312
1520
1456
520
1232
1184
2112
2160
736
17952
—
1584
1536
2456
1200
3504
1920
2560
592
1.87
E
+
06
1264
1536
1408
680
1296
1136
2000
2432
—
15456
1328
24288
1280
936
1296
1264
1856
2272
624
2.39
E
+
06
1232
1680
1264
2456
1136
1152
2144
2448
—
1.72
E
+
06
1264
1504
1040
1008
1264
1504
1776
2352
544
656
1440
1616
1184
352
944
1200
1824
2432
640
5.25
E
+
06
1296
1520
1184
1680
960
1360
2064
2048
720
656
1600
2.27
E
+
06
1520
20664
976
1296
1744
2080
672
4.95
E
+
06
1536
1392
1120
592
1056
1232
1904
2464
—
784
1472
1456
1344
800
1072
1168
1776
2176
528
1.18
E
+
06
1472
9.47
E
+
06
1472
2168
1280
12944
1824
2672
640
576
1344
1648
1376
672
1056
10960
1984
2528
624
9.54
E
+
06
1680
1360
1328
1368
1120
1248
1952
2768
720
87056
1568
1392
1376
1072
1104
1136
1776
2464
640
640
1280
1696
1344
704
1088
1264
2096
2368
576
1.86
E
+
06
1328
1344
1232
560
1232
1312
2000
2240
—
848
—
1504
1344
472
1200
1136
2080
2176
544
688
1600
1440
1344
640
1056
1216
2000
2544
640
9.40
E
+
06
1392
1408
1136
592
1056
1344
2096
2336
“FES” denotes the number of function evaluations. “—” indicates that the algorithm cannot find the optimum within Max_FES.Table 3
Statistical analysis of Tables1  and 2.
Function
Deceptive function
Rastrigin function
Algorithm
RTs
CTs
ConRa
RTs
CTs
ConRa
DE/best/1
50
8
16%
50
27
54%
CDE-um/best/1
50
50
100%
50
50
100%
DE/rand/1
50
28
56%
50
45
90%
CDE-um/rand/1
50
50
100%
50
50
100%
DE/cur-to-best/1
50
17
34%
50
49
98%
CDE-um/cur-to-best/1
50
50
100%
50
50
100%
DE/best/2
50
29
58%
50
47
94%
CDE-um/best/2
50
50
100%
50
50
100%
DE/rand/2
50
37
74%
50
49
98%
CDE-um/rand/2
50
50
100%
50
50
100%
“RTs” denotes runing times. “CTs” denotes convergence times. “ConRa” denotes convergence ratio.Figures2, 3, and 4 showed the convergence times graphs in 50 independent replications within 800 iterations for DE’s deceptive function. We can see that all the convergence curves hold two common characteristics as follows.(i)
When the iteration times are smaller, the convergence times of five typical versions of the classical DE are slightly larger than the corresponding CDE-um. However, with the iteration times are increasing, the convergence times of CDE-um will become far larger than the corresponding DE. From this we can see that smaller increasing in the computational cost can make a greatly improving on the robustness of CDE-um algorithm.(ii)
When the iteration times are larger, all the convergence graphs of five typical versions of the classical DE become a straight line. However, all the graphs of CDE-um show the ladder’s rising status. This indirectly shows that the classical DE cannot escape from a local optimal set or a premature solution set if trapping in, but CDE-um enhances the ability to escape from the local optimal set or premature solution set.Figure 2
Convergence times figure in 50 runs for DE’s deceptive function using */cur-to-best/1 algorithms.Convergence times figure in 50 runs for DE’s deceptive function.
(a)
*/best/1
(b)
*/rand/1Convergence times figure in 50 runs for DE’s deceptive function.
(a)
*/best/2
(b)
*/rand/2The convergence graphs on the rastrigin function had the similar characteristics with DE’s deceptive function, so the graphics are omitted here.The population size is set to8×n. The maximum number of function evaluations (Max_FES) is set to 5,000,000.(i)
Mutation factor,F=0.5 [44, 47];(ii)
Crossover probability,Cr=0.9 [44, 47];(iii)
Termination error value (Ter_Err), Ter_Err=10-12.


### 6.2.  Experiments on Functions of CEC2005

Wang et al. [48] presented a composite differential evolution algorithm (CoDE), which employed three trial vector generation strategies, that is, rand/1/bin, rand/2/bin, and current-to-rand/1. The experimental studies on the 25 benchmark functions of CEC2005 have indicated that CoDE’s overall performance was better than the other seven outstanding competitors (please refer to [48] for details). Now we give a convergent CoDE algorithm (CCoDE-umbest) based on the above convergent algorithm framework. The CCoDE-umbest algorithm has the DE/um-best/1 operator, which was presented in Section 5.1, instead of the current-to-rand/1 of CoDE.This paper compared CCoDE-umbest with CoDE on the 25 benchmark functions of CEC2005. Table4 reported the average and standard deviation of the function error values obtained in 25 runs when FES = 1.5E + 5 and FES = 3.0E + 5, respectively. The two bottom lines in Table 4 gave the test statistics for sign test [49] on the mean errors. From Table 4, the probability values (0.012 for FES = 1.5E + 5, 0.041 for FES = 3.0E + 5) supporting the null hypothesis are less than the significance level at 0.05. So we can reject the null hypothesis, that is to say, the overall performance of CCoDE-umbest is better than CoDE on the benchmarks. It implies that the use of the convergent algorithm framework can improve the performance of CoDE.Table 4
The function error values achieved via CCoDE-umbest and CoDE on CEC2005's test functions.
FES
1.5
E
+
5
3.0
E
+
5
Alg.
CCoDE-umbest
CoDE
CCoDE-umbest
CoDE
Mean
Std.
Mean
Std.
Mean
Std.
Mean
Std.
f1
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
f2
1.83
E
-
04
1.21
E
-
04
5.16
E
-
04
2.28
E
-
04
1.14
E
-
11
1.13
E
-
11
7.42
E
-
11
8.58
E
-
11
f3
1.01
E
+
04
9.71
E
+
03
2.78
E
+
05
1.07
E
+
05
5.33
E
+
03
9.45
E
+
03
5.05
E
+
04
1.34
E
+
04
f4
8.19
E
-
03
5.36
E
-
03
1.84
E
-
02
1.07
E
-
02
1.67
E
-
08
1.39
E
-
08
7.72
E
-
08
6.33
E
-
08
f5
2.98
E
-
03
1.37
E
-
03
8.78
E
-
02
3.06
E
-
02
9.56
E
-
10
5.66
E
-
10
1.11
E
-
06
7.15
E
-
07
f6
2.88
E
-
05
2.40
E
-
05
5.62
E
-
03
3.56
E
-
03
3.41
E
-
14
3.22
E
-
14
5.91
E
-
09
4.29
E
-
09
f7
2.12
E
-
01
1.46
E
-
01
2.69
E
-
01
5.34
E
-
02
2.12
E
-
01
1.46
E
-
01
1.69
E
-
01
3.94
E
-
02
f8
2.01
E
+
01
7.89
E
-
02
2.03
E
+
01
5.47
E
-
02
2.01
E
+
01
7.08
E
-
02
2.03
E
+
01
6.77
E
-
02
f9
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
f10
8.81
E
+
00
3.05
E
+
00
2.05
E
+
01
3.25
E
+
00
8.80
E
+
00
3.05
E
+
00
1.40
E
+
01
2.52
E
+
00
f11
1.59
E
+
00
9.51
E
-
01
6.17
E
+
00
6.60
E
-
01
1.16
E
+
00
1.01
E
+
00
5.28
E
+
00
8.16
E
-
01
f12
2.76
E
+
00
4.89
E
+
00
5.00
E
+
02
2.03
E
+
02
1.64
E
+
00
4.78
E
+
00
1.54
E
+
02
1.14
E
+
02
f13
3.40
E
-
01
1.63
E
-
01
7.11
E
-
01
8.70
E
-
02
3.12
E
-
01
1.48
E
-
01
5.01
E
-
01
6.40
E
-
02
f14
3.03
E
+
00
3.50
E
-
01
3.35
E
+
00
1.90
E
-
01
3.03
E
+
00
3.50
E
-
01
3.26
E
+
00
1.73
E
-
01
f15
0.00
E
+
00
0.00
E
+
00
3.24
E
+
00
1.10
E
+
01
0.00
E
+
00
0.00
E
+
00
3.24
E
+
00
1.10
E
+
01
f16
1.10
E
+
02
7.15
E
+
00
1.34
E
+
02
5.87
E
+
00
1.10
E
+
02
7.20
E
+
00
1.16
E
+
02
5.68
E
+
00
f17
1.10
E
+
02
9.83
E
+
00
1.55
E
+
02
1.02
E
+
01
1.09
E
+
02
9.71
E
+
00
1.38
E
+
02
7.95
E
+
00
f18
4.80
E
+
02
2.40
E
+
02
5.00
E
+
02
2.45
E
+
02
4.80
E
+
02
2.40
E
+
02
5.00
E
+
02
2.45
E
+
02
f19
5.80
E
+
02
2.48
E
+
02
4.20
E
+
02
2.14
E
+
02
5.80
E
+
02
2.48
E
+
02
4.20
E
+
02
2.14
E
+
02
f20
5.40
E
+
02
2.50
E
+
02
4.00
E
+
02
2.00
E
+
02
5.40
E
+
02
2.50
E
+
02
4.00
E
+
02
2.00
E
+
02
f21
5.16
E
+
02
7.84
E
+
01
5.00
E
+
02
3.41
E
-
13
5.16
E
+
02
7.84
E
+
01
5.00
E
+
02
3.41
E
-
13
f22
6.80
E
+
02
1.66
E
+
02
6.20
E
+
02
2.19
E
+
02
6.79
E
+
02
1.66
E
+
02
6.16
E
+
02
2.17
E
+
02
f23
5.59
E
+
02
1.46
E
-
12
5.59
E
+
02
1.32
E
-
12
5.59
E
+
02
1.46
E
-
12
5.59
E
+
02
3.41
E
-
13
f24
2.00
E
+
02
0.00
E
+
00
2.00
E
+
02
0.00
E
+
00
2.00
E
+
02
0.00
E
+
00
2.00
E
+
02
0.00
E
+
00
f25
2.00
E
+
02
0.00
E
+
00
2.00
E
+
02
0.00
E
+
00
2.00
E
+
02
0.00
E
+
00
2.00
E
+
02
0.00
E
+
00
Sign test on mean
Neg_Dif
Pos_Dif
Ties
P value
Neg_Dif
Pos_Dif
Ties
P value
16
4
5
0.012
15
5
5
0.041
“FES” denotes the number of function evaluations. “Std.” denotes the standard deviation of 25 mean errors. The two bottom lines record the test statistics for sign test on mean errors. “Neg_Dif” and “Pos_Dif” denote the number of negative and positive differences, respectively. “P value” denotes the probability value supporting the null hypothesis. Here the both P value are less than the significance level at 0.05.The population size was set to 60, and the dimension was set to 10. The strategies of the other parameters are the same to [48].All the above algorithms are coded in Visual C++ and the experiments were executed on a ACER 4750G laptop with a 2.30 GHz Intel(R) Core (TM)i5 2410M CPU and 2 GB RAM.


## 6.1. Experiments on Low Dimensional Functions

To achieve the aims mentioned above, experiments are conducted on two numerical functions which are chosen according to the experimental results of [43–46]. One is the DE deceptive function [45], which can lead the classical DE to trap in the local optimum. The other is the Rastrigin function. In [45, 46], nineteen benchmark functions including the rastrigin function were tested using the classical DE. Those results indicated that the optimization effect of the rastrigin function is one of the worst.


### 6.1.1. Deceptive Function

Consider(23)f(x)={-3sinc(2x+10),if-10≤x<0,-x·sin(xπ),if0≤x≤10,
where the function sinc(t) is given by
(24)sinc(t)={1,ift=0,sinπtπt,ift≠0.The landscape of DE deceptive function is shown in Figure1. The global optimum of the function is x=-5.0 with the function value f(x)=-3. There is a deceptive local minimum x=8.5060 with function value f(x)=-2.9160in this test function.Figure 1
DE’s deceptive function.


### 6.1.2. Rastrigin Function (2 Dimensions)

Consider(25)f(x)=20+∑i=12‍((xi)2-10cos(2πxi)),000000x∈[-5.12,5.12]2.The global optimum of the function isx=(0,0) with the function value f(x)=0. There are many local optima in this test function.Let CDE-um denote the CDE algorithm using uniform mutation operator. Suppose that CDE-um mutates the worst individual ofU(t) at probability 1, and the new individual is directly retained to the next generation. Experiments were conducted to compare five typical versions of the classic DE with CDE-um algorithm. All experiments were implemented for 50 independent replications. The convergence times and convergence ratio on the 50 replications were reported.In order to show the robustness of CDE-um, we reported the number of function evaluations (FES) to achieve the Ter_Err within Max_FES. Table1 gave the FES of 50 independent replications of five typical versions on the DE’s deceptive function, while Table 2 reported the FES on the Rastrigin function. Those typical versions included DE/best/1 versus CDE-um/best/1, DE/rand/1 versus CDE-um/rand/1, DE/cur-to-best/1 versus CDE-um/cur-to-best/1, and DE/best/2 versus CDE-um/best/2, as well as DE/rand/2 versus CDE-um/best/2. Table 3 analyzes the results of Tables 1 and 2. From the statistics of Table 3, we can see that the ratio (ConRa) converging to the optimum of CDE-um is much higher than the corresponding DE.Table 1
FES to achieve the Ter_Err for DE's deceptive function.
Alg.
best/1
rand/1
cur-to-best/1
best/2
rand/2
DE
CDE-um
DE
CDE-um
DE
CDE-um
DE
CDE-um
DE
CDE-um
FES
176
192
272
416
448
824
264
384
392
632
—
4240
—
184032
—
3328
—
424
560
504
—
147504
—
3920
—
2160
272
744
560
504
—
500832
304
464
—
1384
—
1808
336
1296
—
26200
—
312
—
560
—
1552
536
600
—
163976
448
6248
—
1360
—
320
—
808
—
1568
368
592
—
464
296
312
472
888
—
200
368
727168
—
2944
—
464
560
936
—
5448
320
312
592
664
392
912
424
472
—
66712
—
312
—
22736
304
392
—
768
—
98824
320
5040
—
520
272
1448
352
744
—
82080
—
177312
344
240
—
416
504
648
—
50208
288
520
592
4272
—
368
—
800
—
5408
272
320
—
824
272
408
360
704
—
3096
352
400
416
976
288
344
576
680
—
152256
304
352
—
832
288
320
—
528
—
1.41
E
+
06
—
312
—
4200
—
3592
432
624
—
312624
256
312
—
1192
288
256
480
672
—
370328
224
508880
—
1232
—
608
—
672
—
176
256
2144
—
1328
272
2600
368
784
—
205016
—
632248
—
1240
312
352
376
592
184
168
328
360
672
376
328
464
392
720
—
607768
312
688
—
2888
—
416
408
672
—
2200
—
2240
—
632
—
464
352
896
—
184240
—
1312
536
752
312
520
472
1080
160
406128
—
448
552
408
368
360
—
672
—
268560
—
817456
—
9792
—
2456
448
560
—
295208
—
360
—
1128
—
776
352
744
—
38936
336
336
—
672
—
416
—
728
—
160
296
402096
472
512
208
328
496
784
—
126144
—
368
—
520
336
4360
—
576
—
759336
312
184160
752
2456
—
376
—
840
—
292232
304
2064
392
680
—
480
320
5032
—
24032
—
336
632
936
272
2088
352
656
—
240
—
107664
—
2456
272
2696
456
552
—
555152
—
1432
—
1008
320
1096
336
1664
168
265536
264
105600
—
352
232
512
—
752
168
2256
296
1864
—
1680
360
352
384
760
—
55616
280
320
—
20664
—
904
—
832
—
1.11
E
+
06
336
248
—
592
—
376
352
824
176
263744
—
11136
—
800
408
448
616
69016
—
123896
352
400
456
2168
264
960
536
592
—
200
352
1456
288
672
288
384
544
792
—
784008
304
238752
—
1368
320
5320
520
2536
—
164408
—
29432
—
1072
304
1248
488
584
208
252816
—
4216
392
704
—
568
496
536
—
2088
—
3200
432
560
280
440
576
536
—
542560
—
312
616
472
440
368
—
848
192
1768
—
80536
—
640
—
432
—
672
—
743632
304
320
—
592
—
2976
408
680
“FES” denotes the number of function evaluations. “—” indicates that the algorithm cannot find the optimum within Max_FES.Table 2
FES to achieve the Ter_Err for Rastrigin function.
Alg.
best/1
rand/1
cur-to-best/1
best/2
rand/2
DE
CDE-um
DE
CDE-um
DE
CDE-um
DE
CDE-um
DE
CDE-um
FES
—
103376
—
1680
1184
824
1088
1232
2000
2400
—
1.60
E
+
06
1392
1472
1408
3328
976
1392
2112
2432
560
1.19
E
+
06
1664
1424
1264
2160
1264
1392
1584
2512
—
942224
—
1200
1392
1384
1168
1280
1936
2176
—
672
1440
1584
1280
560
1136
1280
1792
2480
—
452064
1696
1600
1184
1360
1120
1312
1856
2304
560
624
1536
1456
1600
464
1088
1184
2000
1792
720
688
1424
1648
1280
2944
—
1472
—
2352
—
576
1296
1552
1312
664
—
1296
1920
2128
672
576
1184
1248
1184
22736
1056
1296
1776
1936
—
198368
1424
1424
2720
520
1072
1280
2176
2368
—
60336
—
1856
1104
240
1200
1280
2000
2480
656
5.27
E
+
06
1424
1584
1136
4272
896
5840
1840
2304
—
267360
1552
28192
1376
824
1056
1056
1728
2288
—
3.16
E
+
06
1568
1344
1376
976
1136
1408
1792
2720
672
1.11
E
+
06
1296
1440
—
832
1136
1552
2416
2144
608
800
1408
1856
1200
4200
800016
1216
1936
2240
672
2.54
E
+
06
1600
1600
1456
1192
1088
1568
2112
2496
704
3.75
E
+
06
1536
3712
1184
1232
1168
1232
2096
2512
560
236592
1328
1648
1344
1328
1072
1408
1904
2240
—
3.91
E
+
06
1536
1808
1952
1240
—
1328
2336
2368
—
241776
1200
1872
1280
376
1216
1312
1744
2880
—
1072
1408
218208
1344
2888
1152
1248
2000
2512
—
4.70
E
+
06
1520
1408
1232
632
1264
1152
1904
2464
—
8.20
E
+
06
1344
689360
1136
752
1200
5568
1856
2352
—
640
1424
1488
1376
408
1184
1424
1808
2448
—
788880
1344
3.49
E
+
06
1376
9792
1216
1424
2416
2512
576
656
1408
1168
1056
1128
1168
1296
1856
2240
640
560
1408
1536
1184
672
960
1344
1856
2432
—
2.74
E
+
06
1376
228048
5136
512
1312
1312
1888
2512
—
672
1312
1520
1456
520
1232
1184
2112
2160
736
17952
—
1584
1536
2456
1200
3504
1920
2560
592
1.87
E
+
06
1264
1536
1408
680
1296
1136
2000
2432
—
15456
1328
24288
1280
936
1296
1264
1856
2272
624
2.39
E
+
06
1232
1680
1264
2456
1136
1152
2144
2448
—
1.72
E
+
06
1264
1504
1040
1008
1264
1504
1776
2352
544
656
1440
1616
1184
352
944
1200
1824
2432
640
5.25
E
+
06
1296
1520
1184
1680
960
1360
2064
2048
720
656
1600
2.27
E
+
06
1520
20664
976
1296
1744
2080
672
4.95
E
+
06
1536
1392
1120
592
1056
1232
1904
2464
—
784
1472
1456
1344
800
1072
1168
1776
2176
528
1.18
E
+
06
1472
9.47
E
+
06
1472
2168
1280
12944
1824
2672
640
576
1344
1648
1376
672
1056
10960
1984
2528
624
9.54
E
+
06
1680
1360
1328
1368
1120
1248
1952
2768
720
87056
1568
1392
1376
1072
1104
1136
1776
2464
640
640
1280
1696
1344
704
1088
1264
2096
2368
576
1.86
E
+
06
1328
1344
1232
560
1232
1312
2000
2240
—
848
—
1504
1344
472
1200
1136
2080
2176
544
688
1600
1440
1344
640
1056
1216
2000
2544
640
9.40
E
+
06
1392
1408
1136
592
1056
1344
2096
2336
“FES” denotes the number of function evaluations. “—” indicates that the algorithm cannot find the optimum within Max_FES.Table 3
Statistical analysis of Tables1  and 2.
Function
Deceptive function
Rastrigin function
Algorithm
RTs
CTs
ConRa
RTs
CTs
ConRa
DE/best/1
50
8
16%
50
27
54%
CDE-um/best/1
50
50
100%
50
50
100%
DE/rand/1
50
28
56%
50
45
90%
CDE-um/rand/1
50
50
100%
50
50
100%
DE/cur-to-best/1
50
17
34%
50
49
98%
CDE-um/cur-to-best/1
50
50
100%
50
50
100%
DE/best/2
50
29
58%
50
47
94%
CDE-um/best/2
50
50
100%
50
50
100%
DE/rand/2
50
37
74%
50
49
98%
CDE-um/rand/2
50
50
100%
50
50
100%
“RTs” denotes runing times. “CTs” denotes convergence times. “ConRa” denotes convergence ratio.Figures2, 3, and 4 showed the convergence times graphs in 50 independent replications within 800 iterations for DE’s deceptive function. We can see that all the convergence curves hold two common characteristics as follows.(i)
When the iteration times are smaller, the convergence times of five typical versions of the classical DE are slightly larger than the corresponding CDE-um. However, with the iteration times are increasing, the convergence times of CDE-um will become far larger than the corresponding DE. From this we can see that smaller increasing in the computational cost can make a greatly improving on the robustness of CDE-um algorithm.(ii)
When the iteration times are larger, all the convergence graphs of five typical versions of the classical DE become a straight line. However, all the graphs of CDE-um show the ladder’s rising status. This indirectly shows that the classical DE cannot escape from a local optimal set or a premature solution set if trapping in, but CDE-um enhances the ability to escape from the local optimal set or premature solution set.Figure 2
Convergence times figure in 50 runs for DE’s deceptive function using */cur-to-best/1 algorithms.Convergence times figure in 50 runs for DE’s deceptive function.
(a)
*/best/1
(b)
*/rand/1Convergence times figure in 50 runs for DE’s deceptive function.
(a)
*/best/2
(b)
*/rand/2The convergence graphs on the rastrigin function had the similar characteristics with DE’s deceptive function, so the graphics are omitted here.The population size is set to8×n. The maximum number of function evaluations (Max_FES) is set to 5,000,000.(i)
Mutation factor,F=0.5 [44, 47];(ii)
Crossover probability,Cr=0.9 [44, 47];(iii)
Termination error value (Ter_Err), Ter_Err=10-12.


## 6.1.1. Deceptive Function

Consider(23)f(x)={-3sinc(2x+10),if-10≤x<0,-x·sin(xπ),if0≤x≤10,
where the function sinc(t) is given by
(24)sinc(t)={1,ift=0,sinπtπt,ift≠0.The landscape of DE deceptive function is shown in Figure1. The global optimum of the function is x=-5.0 with the function value f(x)=-3. There is a deceptive local minimum x=8.5060 with function value f(x)=-2.9160in this test function.Figure 1
DE’s deceptive function.


## 6.1.2. Rastrigin Function (2 Dimensions)

Consider(25)f(x)=20+∑i=12‍((xi)2-10cos(2πxi)),000000x∈[-5.12,5.12]2.The global optimum of the function isx=(0,0) with the function value f(x)=0. There are many local optima in this test function.Let CDE-um denote the CDE algorithm using uniform mutation operator. Suppose that CDE-um mutates the worst individual ofU(t) at probability 1, and the new individual is directly retained to the next generation. Experiments were conducted to compare five typical versions of the classic DE with CDE-um algorithm. All experiments were implemented for 50 independent replications. The convergence times and convergence ratio on the 50 replications were reported.In order to show the robustness of CDE-um, we reported the number of function evaluations (FES) to achieve the Ter_Err within Max_FES. Table1 gave the FES of 50 independent replications of five typical versions on the DE’s deceptive function, while Table 2 reported the FES on the Rastrigin function. Those typical versions included DE/best/1 versus CDE-um/best/1, DE/rand/1 versus CDE-um/rand/1, DE/cur-to-best/1 versus CDE-um/cur-to-best/1, and DE/best/2 versus CDE-um/best/2, as well as DE/rand/2 versus CDE-um/best/2. Table 3 analyzes the results of Tables 1 and 2. From the statistics of Table 3, we can see that the ratio (ConRa) converging to the optimum of CDE-um is much higher than the corresponding DE.Table 1
FES to achieve the Ter_Err for DE's deceptive function.
Alg.
best/1
rand/1
cur-to-best/1
best/2
rand/2
DE
CDE-um
DE
CDE-um
DE
CDE-um
DE
CDE-um
DE
CDE-um
FES
176
192
272
416
448
824
264
384
392
632
—
4240
—
184032
—
3328
—
424
560
504
—
147504
—
3920
—
2160
272
744
560
504
—
500832
304
464
—
1384
—
1808
336
1296
—
26200
—
312
—
560
—
1552
536
600
—
163976
448
6248
—
1360
—
320
—
808
—
1568
368
592
—
464
296
312
472
888
—
200
368
727168
—
2944
—
464
560
936
—
5448
320
312
592
664
392
912
424
472
—
66712
—
312
—
22736
304
392
—
768
—
98824
320
5040
—
520
272
1448
352
744
—
82080
—
177312
344
240
—
416
504
648
—
50208
288
520
592
4272
—
368
—
800
—
5408
272
320
—
824
272
408
360
704
—
3096
352
400
416
976
288
344
576
680
—
152256
304
352
—
832
288
320
—
528
—
1.41
E
+
06
—
312
—
4200
—
3592
432
624
—
312624
256
312
—
1192
288
256
480
672
—
370328
224
508880
—
1232
—
608
—
672
—
176
256
2144
—
1328
272
2600
368
784
—
205016
—
632248
—
1240
312
352
376
592
184
168
328
360
672
376
328
464
392
720
—
607768
312
688
—
2888
—
416
408
672
—
2200
—
2240
—
632
—
464
352
896
—
184240
—
1312
536
752
312
520
472
1080
160
406128
—
448
552
408
368
360
—
672
—
268560
—
817456
—
9792
—
2456
448
560
—
295208
—
360
—
1128
—
776
352
744
—
38936
336
336
—
672
—
416
—
728
—
160
296
402096
472
512
208
328
496
784
—
126144
—
368
—
520
336
4360
—
576
—
759336
312
184160
752
2456
—
376
—
840
—
292232
304
2064
392
680
—
480
320
5032
—
24032
—
336
632
936
272
2088
352
656
—
240
—
107664
—
2456
272
2696
456
552
—
555152
—
1432
—
1008
320
1096
336
1664
168
265536
264
105600
—
352
232
512
—
752
168
2256
296
1864
—
1680
360
352
384
760
—
55616
280
320
—
20664
—
904
—
832
—
1.11
E
+
06
336
248
—
592
—
376
352
824
176
263744
—
11136
—
800
408
448
616
69016
—
123896
352
400
456
2168
264
960
536
592
—
200
352
1456
288
672
288
384
544
792
—
784008
304
238752
—
1368
320
5320
520
2536
—
164408
—
29432
—
1072
304
1248
488
584
208
252816
—
4216
392
704
—
568
496
536
—
2088
—
3200
432
560
280
440
576
536
—
542560
—
312
616
472
440
368
—
848
192
1768
—
80536
—
640
—
432
—
672
—
743632
304
320
—
592
—
2976
408
680
“FES” denotes the number of function evaluations. “—” indicates that the algorithm cannot find the optimum within Max_FES.Table 2
FES to achieve the Ter_Err for Rastrigin function.
Alg.
best/1
rand/1
cur-to-best/1
best/2
rand/2
DE
CDE-um
DE
CDE-um
DE
CDE-um
DE
CDE-um
DE
CDE-um
FES
—
103376
—
1680
1184
824
1088
1232
2000
2400
—
1.60
E
+
06
1392
1472
1408
3328
976
1392
2112
2432
560
1.19
E
+
06
1664
1424
1264
2160
1264
1392
1584
2512
—
942224
—
1200
1392
1384
1168
1280
1936
2176
—
672
1440
1584
1280
560
1136
1280
1792
2480
—
452064
1696
1600
1184
1360
1120
1312
1856
2304
560
624
1536
1456
1600
464
1088
1184
2000
1792
720
688
1424
1648
1280
2944
—
1472
—
2352
—
576
1296
1552
1312
664
—
1296
1920
2128
672
576
1184
1248
1184
22736
1056
1296
1776
1936
—
198368
1424
1424
2720
520
1072
1280
2176
2368
—
60336
—
1856
1104
240
1200
1280
2000
2480
656
5.27
E
+
06
1424
1584
1136
4272
896
5840
1840
2304
—
267360
1552
28192
1376
824
1056
1056
1728
2288
—
3.16
E
+
06
1568
1344
1376
976
1136
1408
1792
2720
672
1.11
E
+
06
1296
1440
—
832
1136
1552
2416
2144
608
800
1408
1856
1200
4200
800016
1216
1936
2240
672
2.54
E
+
06
1600
1600
1456
1192
1088
1568
2112
2496
704
3.75
E
+
06
1536
3712
1184
1232
1168
1232
2096
2512
560
236592
1328
1648
1344
1328
1072
1408
1904
2240
—
3.91
E
+
06
1536
1808
1952
1240
—
1328
2336
2368
—
241776
1200
1872
1280
376
1216
1312
1744
2880
—
1072
1408
218208
1344
2888
1152
1248
2000
2512
—
4.70
E
+
06
1520
1408
1232
632
1264
1152
1904
2464
—
8.20
E
+
06
1344
689360
1136
752
1200
5568
1856
2352
—
640
1424
1488
1376
408
1184
1424
1808
2448
—
788880
1344
3.49
E
+
06
1376
9792
1216
1424
2416
2512
576
656
1408
1168
1056
1128
1168
1296
1856
2240
640
560
1408
1536
1184
672
960
1344
1856
2432
—
2.74
E
+
06
1376
228048
5136
512
1312
1312
1888
2512
—
672
1312
1520
1456
520
1232
1184
2112
2160
736
17952
—
1584
1536
2456
1200
3504
1920
2560
592
1.87
E
+
06
1264
1536
1408
680
1296
1136
2000
2432
—
15456
1328
24288
1280
936
1296
1264
1856
2272
624
2.39
E
+
06
1232
1680
1264
2456
1136
1152
2144
2448
—
1.72
E
+
06
1264
1504
1040
1008
1264
1504
1776
2352
544
656
1440
1616
1184
352
944
1200
1824
2432
640
5.25
E
+
06
1296
1520
1184
1680
960
1360
2064
2048
720
656
1600
2.27
E
+
06
1520
20664
976
1296
1744
2080
672
4.95
E
+
06
1536
1392
1120
592
1056
1232
1904
2464
—
784
1472
1456
1344
800
1072
1168
1776
2176
528
1.18
E
+
06
1472
9.47
E
+
06
1472
2168
1280
12944
1824
2672
640
576
1344
1648
1376
672
1056
10960
1984
2528
624
9.54
E
+
06
1680
1360
1328
1368
1120
1248
1952
2768
720
87056
1568
1392
1376
1072
1104
1136
1776
2464
640
640
1280
1696
1344
704
1088
1264
2096
2368
576
1.86
E
+
06
1328
1344
1232
560
1232
1312
2000
2240
—
848
—
1504
1344
472
1200
1136
2080
2176
544
688
1600
1440
1344
640
1056
1216
2000
2544
640
9.40
E
+
06
1392
1408
1136
592
1056
1344
2096
2336
“FES” denotes the number of function evaluations. “—” indicates that the algorithm cannot find the optimum within Max_FES.Table 3
Statistical analysis of Tables1  and 2.
Function
Deceptive function
Rastrigin function
Algorithm
RTs
CTs
ConRa
RTs
CTs
ConRa
DE/best/1
50
8
16%
50
27
54%
CDE-um/best/1
50
50
100%
50
50
100%
DE/rand/1
50
28
56%
50
45
90%
CDE-um/rand/1
50
50
100%
50
50
100%
DE/cur-to-best/1
50
17
34%
50
49
98%
CDE-um/cur-to-best/1
50
50
100%
50
50
100%
DE/best/2
50
29
58%
50
47
94%
CDE-um/best/2
50
50
100%
50
50
100%
DE/rand/2
50
37
74%
50
49
98%
CDE-um/rand/2
50
50
100%
50
50
100%
“RTs” denotes runing times. “CTs” denotes convergence times. “ConRa” denotes convergence ratio.Figures2, 3, and 4 showed the convergence times graphs in 50 independent replications within 800 iterations for DE’s deceptive function. We can see that all the convergence curves hold two common characteristics as follows.(i)
When the iteration times are smaller, the convergence times of five typical versions of the classical DE are slightly larger than the corresponding CDE-um. However, with the iteration times are increasing, the convergence times of CDE-um will become far larger than the corresponding DE. From this we can see that smaller increasing in the computational cost can make a greatly improving on the robustness of CDE-um algorithm.(ii)
When the iteration times are larger, all the convergence graphs of five typical versions of the classical DE become a straight line. However, all the graphs of CDE-um show the ladder’s rising status. This indirectly shows that the classical DE cannot escape from a local optimal set or a premature solution set if trapping in, but CDE-um enhances the ability to escape from the local optimal set or premature solution set.Figure 2
Convergence times figure in 50 runs for DE’s deceptive function using */cur-to-best/1 algorithms.Convergence times figure in 50 runs for DE’s deceptive function.
(a)
*/best/1
(b)
*/rand/1Convergence times figure in 50 runs for DE’s deceptive function.
(a)
*/best/2
(b)
*/rand/2The convergence graphs on the rastrigin function had the similar characteristics with DE’s deceptive function, so the graphics are omitted here.The population size is set to8×n. The maximum number of function evaluations (Max_FES) is set to 5,000,000.(i)
Mutation factor,F=0.5 [44, 47];(ii)
Crossover probability,Cr=0.9 [44, 47];(iii)
Termination error value (Ter_Err), Ter_Err=10-12.


## 6.2.  Experiments on Functions of CEC2005

Wang et al. [48] presented a composite differential evolution algorithm (CoDE), which employed three trial vector generation strategies, that is, rand/1/bin, rand/2/bin, and current-to-rand/1. The experimental studies on the 25 benchmark functions of CEC2005 have indicated that CoDE’s overall performance was better than the other seven outstanding competitors (please refer to [48] for details). Now we give a convergent CoDE algorithm (CCoDE-umbest) based on the above convergent algorithm framework. The CCoDE-umbest algorithm has the DE/um-best/1 operator, which was presented in Section 5.1, instead of the current-to-rand/1 of CoDE.This paper compared CCoDE-umbest with CoDE on the 25 benchmark functions of CEC2005. Table4 reported the average and standard deviation of the function error values obtained in 25 runs when FES = 1.5E + 5 and FES = 3.0E + 5, respectively. The two bottom lines in Table 4 gave the test statistics for sign test [49] on the mean errors. From Table 4, the probability values (0.012 for FES = 1.5E + 5, 0.041 for FES = 3.0E + 5) supporting the null hypothesis are less than the significance level at 0.05. So we can reject the null hypothesis, that is to say, the overall performance of CCoDE-umbest is better than CoDE on the benchmarks. It implies that the use of the convergent algorithm framework can improve the performance of CoDE.Table 4
The function error values achieved via CCoDE-umbest and CoDE on CEC2005's test functions.
FES
1.5
E
+
5
3.0
E
+
5
Alg.
CCoDE-umbest
CoDE
CCoDE-umbest
CoDE
Mean
Std.
Mean
Std.
Mean
Std.
Mean
Std.
f1
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
f2
1.83
E
-
04
1.21
E
-
04
5.16
E
-
04
2.28
E
-
04
1.14
E
-
11
1.13
E
-
11
7.42
E
-
11
8.58
E
-
11
f3
1.01
E
+
04
9.71
E
+
03
2.78
E
+
05
1.07
E
+
05
5.33
E
+
03
9.45
E
+
03
5.05
E
+
04
1.34
E
+
04
f4
8.19
E
-
03
5.36
E
-
03
1.84
E
-
02
1.07
E
-
02
1.67
E
-
08
1.39
E
-
08
7.72
E
-
08
6.33
E
-
08
f5
2.98
E
-
03
1.37
E
-
03
8.78
E
-
02
3.06
E
-
02
9.56
E
-
10
5.66
E
-
10
1.11
E
-
06
7.15
E
-
07
f6
2.88
E
-
05
2.40
E
-
05
5.62
E
-
03
3.56
E
-
03
3.41
E
-
14
3.22
E
-
14
5.91
E
-
09
4.29
E
-
09
f7
2.12
E
-
01
1.46
E
-
01
2.69
E
-
01
5.34
E
-
02
2.12
E
-
01
1.46
E
-
01
1.69
E
-
01
3.94
E
-
02
f8
2.01
E
+
01
7.89
E
-
02
2.03
E
+
01
5.47
E
-
02
2.01
E
+
01
7.08
E
-
02
2.03
E
+
01
6.77
E
-
02
f9
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
f10
8.81
E
+
00
3.05
E
+
00
2.05
E
+
01
3.25
E
+
00
8.80
E
+
00
3.05
E
+
00
1.40
E
+
01
2.52
E
+
00
f11
1.59
E
+
00
9.51
E
-
01
6.17
E
+
00
6.60
E
-
01
1.16
E
+
00
1.01
E
+
00
5.28
E
+
00
8.16
E
-
01
f12
2.76
E
+
00
4.89
E
+
00
5.00
E
+
02
2.03
E
+
02
1.64
E
+
00
4.78
E
+
00
1.54
E
+
02
1.14
E
+
02
f13
3.40
E
-
01
1.63
E
-
01
7.11
E
-
01
8.70
E
-
02
3.12
E
-
01
1.48
E
-
01
5.01
E
-
01
6.40
E
-
02
f14
3.03
E
+
00
3.50
E
-
01
3.35
E
+
00
1.90
E
-
01
3.03
E
+
00
3.50
E
-
01
3.26
E
+
00
1.73
E
-
01
f15
0.00
E
+
00
0.00
E
+
00
3.24
E
+
00
1.10
E
+
01
0.00
E
+
00
0.00
E
+
00
3.24
E
+
00
1.10
E
+
01
f16
1.10
E
+
02
7.15
E
+
00
1.34
E
+
02
5.87
E
+
00
1.10
E
+
02
7.20
E
+
00
1.16
E
+
02
5.68
E
+
00
f17
1.10
E
+
02
9.83
E
+
00
1.55
E
+
02
1.02
E
+
01
1.09
E
+
02
9.71
E
+
00
1.38
E
+
02
7.95
E
+
00
f18
4.80
E
+
02
2.40
E
+
02
5.00
E
+
02
2.45
E
+
02
4.80
E
+
02
2.40
E
+
02
5.00
E
+
02
2.45
E
+
02
f19
5.80
E
+
02
2.48
E
+
02
4.20
E
+
02
2.14
E
+
02
5.80
E
+
02
2.48
E
+
02
4.20
E
+
02
2.14
E
+
02
f20
5.40
E
+
02
2.50
E
+
02
4.00
E
+
02
2.00
E
+
02
5.40
E
+
02
2.50
E
+
02
4.00
E
+
02
2.00
E
+
02
f21
5.16
E
+
02
7.84
E
+
01
5.00
E
+
02
3.41
E
-
13
5.16
E
+
02
7.84
E
+
01
5.00
E
+
02
3.41
E
-
13
f22
6.80
E
+
02
1.66
E
+
02
6.20
E
+
02
2.19
E
+
02
6.79
E
+
02
1.66
E
+
02
6.16
E
+
02
2.17
E
+
02
f23
5.59
E
+
02
1.46
E
-
12
5.59
E
+
02
1.32
E
-
12
5.59
E
+
02
1.46
E
-
12
5.59
E
+
02
3.41
E
-
13
f24
2.00
E
+
02
0.00
E
+
00
2.00
E
+
02
0.00
E
+
00
2.00
E
+
02
0.00
E
+
00
2.00
E
+
02
0.00
E
+
00
f25
2.00
E
+
02
0.00
E
+
00
2.00
E
+
02
0.00
E
+
00
2.00
E
+
02
0.00
E
+
00
2.00
E
+
02
0.00
E
+
00
Sign test on mean
Neg_Dif
Pos_Dif
Ties
P value
Neg_Dif
Pos_Dif
Ties
P value
16
4
5
0.012
15
5
5
0.041
“FES” denotes the number of function evaluations. “Std.” denotes the standard deviation of 25 mean errors. The two bottom lines record the test statistics for sign test on mean errors. “Neg_Dif” and “Pos_Dif” denote the number of negative and positive differences, respectively. “P value” denotes the probability value supporting the null hypothesis. Here the both P value are less than the significance level at 0.05.The population size was set to 60, and the dimension was set to 10. The strategies of the other parameters are the same to [48].All the above algorithms are coded in Visual C++ and the experiments were executed on a ACER 4750G laptop with a 2.30 GHz Intel(R) Core (TM)i5 2410M CPU and 2 GB RAM.


## 7. Analysis and Discussion

In this paper, two sufficient conditions for the convergence of DE have been presented in forms of a theorem and a corollary. These conditions describe the limiting behaviors of DE. Given a sub-sequence population, the sufficient conditions require that the probability generating an optimum (or optima) by the reproduction operations is greater than a small positive number. Taking into account the selection operator of DE which can retain the elitist individual(s) of current population to the next generation, the sufficient conditions were easily proved by using the infinite product. Judging by essentials, sufficient conditions for the convergence of the classical evolutionary algorithms [38] and the elitist genetic algorithm [50–52], which is proved by using the Markov Chain, generally conclude two requirements. One is the ergodicity of the population states; the other is the retention of the current best solution. In contrast, the sufficient conditions for the convergence of DE presented in this paper do not require the population state to hold with the ergodic property.Theoretical studies of algorithms’ convergence are of significance to understand their search behaviors and to develop more robust algorithms. According to the presented sufficient conditions, a modified algorithm framework, CDE, is proposed. By employing an extra mutation operator, the CDE algorithm framework becomes to converge in probability. It is not difficult to infer that there are many mutation operators meeting the convergent condition, such as uniform mutation, Gaussian mutation operator, and other mutation operators.Thus, now there arises a new problem: which mutation operator is the most suitable one? Inspired by the process from the classical genetic algorithm to the elitist genetic algorithm, our preference should be directed to the operators with the following characteristics. Firstly, the auxiliary operator is simple and straightforward to implement. Secondly, the operator can make DE algorithm convergent, thereby improving the robustness of the algorithm. Finally, the computational cost generated by the auxiliary operator is reasonable. Based on these factors, this paper presents the CDE-um and CCoDE-umbest algorithms and gives numerical experiments to verify the robustness and competitiveness of those convergent DE algorithms.From Table3, we can see that all the convergence ratios of five versions of CDE-um on test functions reach 100%. This shows that the convergent algorithm CDE-um improves the robustness of the classical DE. In addition, from Figures 2–4, comparing with the corresponding DE, the computational cost of CDE-um is not large, and still acceptable and reasonable. As shown in Table 4, the results on the CCoDE-umbest algorithm indicate that the reasonably use of the convergent algorithm framework can improve the performance of CoDE.Moreover, the robustness of CDE-um also can be further analyzed by numerical experiments. Figure5 gives the convergence graphs for DE’s deceptive function in a single run. From the graphs in Figure 5, we can see that CDE-um can escape from the local optimum of the test functions, while the classical DE cannot escape in case of trapping in the local optimum solution set. In fact, the mutation perturbations approach 0 when the classical DE traps in a local optimum solution set, which results in that the population of the classical DE cannot be optimized any more.Convergence graph for DE’s deceptive function at a run.
(a)
2 dimensions
(b)
3 dimensionsOf course, we have to note that convergence in probability is a property when the iteration times approach infinity. The previous theorem and experimental results cannot infer that the CDE can solve all function optimization problems within a finite iteration.


## 8. Conclusion and Future Work

The convergent property studies, as one of the basic researches for algorithms, benefit designing more robust algorithms. Few of researches have been done in dealing with conditions for the convergence of DE. This paper presented and proved two sufficient conditions for the convergence of DE. These sufficient conditions state that DE variants can guarantee converging to a global optimum solution if the probability, generating an optimum (or optima) by the reproduction operations of each generation in a certain sub-sequence population, is greater than a small positive number. According to the sufficient conditions, a convergent algorithm framework CDE was presented. The algorithm framework demonstrates that the employment of some auxiliary operators satisfying certain conditions can make the classical DE converge in probability. It was then proved that uniform mutation and Gaussian mutation operators meet the convergence conditions of the auxiliary operator.Convergent algorithms may not always work competitively, but these should generally possess more powerful robustness. So in order to further verify the conclusions drawn from the theoretic researches, this paper gave numerical experiments comparing the performance of the convergent algorithm, CDE-um algorithm, and the classical DE (including five typical versions). CDE-um algorithm was designed by incorporating uniform mutation into the classical DE. The experimental results on the test functions show that smaller increase in the computational cost can make a greatly improvement on the robustness for all five typical versions of CDE-um. In addition, this paper improved theComposite Differential Evolution (CoDE) inspired of the convergence theory and tested its competitiveness on the benchmark functions of CEC2005.In summary, the sufficient conditions guaranteeing global convergence of DE variants, which were proved in this paper, are easy to check and are general enough to be useful for the family of DE algorithms. And in future works, it appears to be promising for developing more competitive and convergent algorithms by incorporating a certain convergence-assisted operator into some outstanding variants of modified DE algorithms.



---

*Source: 193196-2013-10-21.xml*