# A DE-Based Scatter Search for Global Optimization Problems

Authors: Kun Li; Huixin Tian
Journal: Discrete Dynamics in Nature and Society
 (2015)

---

## Abstract

This paper proposes a hybrid scatter search (SS) algorithm for continuous global optimization problems by incorporating the evolution mechanism of differential evolution (DE) into the reference set updated procedure of SS to act as the new solution generation method.  This hybrid algorithm is called a DE-based SS (SSDE) algorithm.  Since different kinds of mutation operators of DE have been proposed in the literature and they have shown different search abilities for different kinds of problems, four traditional mutation operators are adopted in the hybrid SSDE algorithm. To adaptively select the mutation operator that is most appropriate to the current problem, an adaptive mechanism for the candidate mutation operators is developed.  In addition, to enhance the exploration ability of SSDE, a reinitialization method is adopted to create a new population and subsequently construct a new reference set whenever the search process of SSDE is trapped in local optimum.  Computational experiments on benchmark problems show that the proposed SSDE is competitive or superior to some state-of-the-art algorithms in the literature.


---

## Body

## 1. Introduction

In recent years, many research efforts have been devoted to the hybridization of different algorithms because the adoption of the best features of individual algorithm can often result in a new powerful and efficient hybrid algorithm. When designing such hybrid algorithms, one should examine and evaluate the features and search mechanisms of different algorithms, as well as their potential combinations.Scatter search (SS) was firstly proposed by Glover [1] for integer programming. It is a population-based evolutionary algorithm that combines a set of solutions to construct a new solution. The scatter search template (Glover [2]) provides the foundation for most implementations of SS by now. After population initialization, SS selects a subset of solutions from the population as the reference set and then operates on the reference set to generate new trial solutions by combining solutions in the reference set. With comparison to the other evolutionary algorithms such as genetic algorithm, the memory feature of the reference set can accurately grasp the current optimization state and reduce the frequency of using stochastic search, which in turn greatly improves the ability of global search. In addition, the diversity maintenance mechanism of SS guarantees the search diversity during evolution. Due to its flexibility and effectiveness, SS has been widely used in tackling combination optimization problems such as the graph-based permutation problems (Rego and Aleao [3]), flow shop scheduling problem (Yamada and Nakano [4], Nowicki and Smutnicki [5]), vehicle routing problem (Taillard [6]), quadratic assignment problem (Chung et al. [7]), and vehicle routing (Greistorfer [8], Russell and Chiang [9]). Although SS has achieved good performance in solving combination optimization problems, few literatures focus on the application of SS in continuous optimization problems. Herrera et al. [10] investigated the performance of continuous SS with two combination methods, namely, theBLX-α and the average combination. Ugray et al. [11] proposed a multistart framework for global optimization by embedding SS with a nonlinear programming solver.Although differential evolution (DE) is a new member of the swarm-based evolutionary algorithms, it has become one of the most powerful stochastic search algorithms in the literature (Das and Suganthan [12]). Due to its simplicity and ease of implementation, DE has performed well in many single-objective optimization problems (Zhang and Sanderson [13], Qin et al. [14]) and engineering optimization problems (Babu and Angira [15], Zhang and Rangaiah [16]). The main advantage of DE is that it enables the solution to learn from better solutions (e.g., the DE/best/1 mutation operator) and at the same time maintain the search diversity (e.g., the DE/rand/1 mutation operator).Due to the power of SS and DE, some researchers start to investigate their hybridization to construct a new powerful algorithm. Davendra and Onwubolu [17] and Davendra et al. [18] proposed a hybrid DE with SS for discrete optimization problems such as quadratic assignment problem (QAP), traveling salesman problem (TSP), and permutation flow shop scheduling problem (PFSP). However, this hybrid algorithm is in fact a two-phase method, in which the first phase is to obtain a good solution by DE and the second phase is to improve this solution by SS. Shi et al. [19] developed a real hybrid SS with DE by embedding DE into SS to generate the new reference set. This hybrid algorithm is used to solve the discrete project scheduling problem.In this paper, we propose a new hybrid algorithm based on SS and DE, named hybrid SS with DE (SSDE). The main framework follows that of SS but uses DE to combine solutions in the reference set and then generate new solutions. Different from that of Shi et al. [19], our hybrid algorithm is designed for continuous algorithm. In addition, our hybrid SSDE algorithm adopts multiple mutation operators proposed for classical DE and makes use of an adaptive mechanism to select the most appropriate mutation operators during evolution. This strategy makes the hybrid SSDE very robust for different kinds of optimization problems.The remainder of this paper is organized as follows. Section2 gives the background descriptions on SS and DE, and in Section 3 the procedure and components of the hybrid SSDE are described in details. The computational experiments are carried out in Section 4 and our SSDE is compared to the other state-of-the-art evolutionary algorithms in the literature on benchmark test problems. Finally, this paper is concluded in Section 5.


## 2. Background

### 2.1. Canonical Scatter Search

The framework of the SS generally includes five components (shown in Algorithm1). The SS first generates a population of solutions using a diversification generation method that considers both solution quality and diversity. Then the reference update method is used to build and maintain the reference set by selecting some solutions with good quality and the other solutions with good diversity from the population (note that the size of the reference set is a preset fixed value). Based on the reference set, the subset generation method is used to produce a great number of subsets of solutions as a basis for creating combined solutions (e.g., all the two solutions and the three solutions selected from the reference set are generally taken as the subsets). For each subset, the solution combination method is used to transform the solutions in the subset into one combined solution. At last, the improvement method is applied to further improve each combined solution. If there is no new solution added to the reference set, the algorithm terminates; otherwise, the algorithm goes to the subset generation procedure and starts a new iteration.Algorithm 1:Canonical scatter search.
(1)Begin
(2) Use theDiversification generation method to create a population.
(3) Use theImprovement method to enhance the population, and set S
b to be the best solution found so far.
(4) Use theReference update method to build the initial reference set R.
(5)while (the termination criterion is not reached) do
(6)  Generate subsets fromR using the Subset generation method.
(7)Combine each subset into a new solution using the Solution combination method.
(8)Use the Improvement method to enhance each combined solution, and update S
b.
(9)Update the reference set based on the union of the current reference set and the new combined
solutions using theReference update method.
(10)end while
(11)Report the best solution S
b.
(12)End


### 2.2. Canonical Differential Evolution

DE algorithm is a simple, fast, and robust evolutionary algorithm. It starts with a populationP of N
P solutions, and at each generation G the population updates through three main consecutive steps: mutation, crossover, and selection. In the following, the ith solution in the population of generation G is denoted as X
i
,
G, i
=
1,2
,
…
,
N
P.The mutation step first randomly selects three solutions{
X
r
1
,
G
,
X
r
2
,
G
,
X
r
3
,
G
} from the population P of generation G for the target individual X
i
,
G and then generates the perturbed vector V
i
,
G based on the three selected solutions as follows:(1)
V
i
,
G
=
X
r
1
,
G
+
F
×
X
r
2
,
G
-
X
r
3
,
G
,where i
=
1,2
,
…
,
N
P, r
1, r
2, r
3 are three different numbers randomly selected from {
1,2
,
…
,
N
P
} and F
∈
[
0,1
] is the control parameter.The crossover step generates the trial solutionU
i
,
G
=
(
u
1
,
i
,
G
,
u
2
,
i
,
G
,
…
,
u
n
,
i
,
G
) based on the perturbed vector V
i
,
G
=
(
v
1
,
i
,
G
,
v
2
,
i
,
G
,
…
,
v
n
,
i
,
G
) and the target solution X
i
,
G
=
(
x
1
,
i
,
G
,
x
2
,
i
,
G
,
…
,
x
n
,
i
,
G
) as follows:(2)
u
j
,
i
,
G
=
v
j
,
i
,
G
,
if
rand
j
≤
C
r
or
j
=
j
rand
x
j
,
i
,
G
,
otherwise
,where j
=
1
,
…
,
n, rand
j
∈
[
0,1
] and j
rand is a randomly chosen index from {
1
,
…
,
n
} to ensure that the trial solution U
i
,
G does not duplicate the target solution X
i
,
G. C
r
∈
[
0,1
] is the crossover probability set by the user.Once the trial solution is generated, the selection step compares it with its target solution. If the trial solutionU
i
,
G has an equal or lower objective function value than that of its target solution X
i
,
G, it replaces the target vector in the next generation; otherwise, the target solution retains its place in the population for at least one generation. That is, the solution in the next generation is selected according to the following rule:(3)
X
i
,
G
+
1
=
U
i
,
G
,
if
f
(
U
i
,
G
)
≤
f
(
X
i
,
G
)
X
i
,
G
,
otherwise
.


## 2.1. Canonical Scatter Search

The framework of the SS generally includes five components (shown in Algorithm1). The SS first generates a population of solutions using a diversification generation method that considers both solution quality and diversity. Then the reference update method is used to build and maintain the reference set by selecting some solutions with good quality and the other solutions with good diversity from the population (note that the size of the reference set is a preset fixed value). Based on the reference set, the subset generation method is used to produce a great number of subsets of solutions as a basis for creating combined solutions (e.g., all the two solutions and the three solutions selected from the reference set are generally taken as the subsets). For each subset, the solution combination method is used to transform the solutions in the subset into one combined solution. At last, the improvement method is applied to further improve each combined solution. If there is no new solution added to the reference set, the algorithm terminates; otherwise, the algorithm goes to the subset generation procedure and starts a new iteration.Algorithm 1:Canonical scatter search.
(1)Begin
(2) Use theDiversification generation method to create a population.
(3) Use theImprovement method to enhance the population, and set S
b to be the best solution found so far.
(4) Use theReference update method to build the initial reference set R.
(5)while (the termination criterion is not reached) do
(6)  Generate subsets fromR using the Subset generation method.
(7)Combine each subset into a new solution using the Solution combination method.
(8)Use the Improvement method to enhance each combined solution, and update S
b.
(9)Update the reference set based on the union of the current reference set and the new combined
solutions using theReference update method.
(10)end while
(11)Report the best solution S
b.
(12)End


## 2.2. Canonical Differential Evolution

DE algorithm is a simple, fast, and robust evolutionary algorithm. It starts with a populationP of N
P solutions, and at each generation G the population updates through three main consecutive steps: mutation, crossover, and selection. In the following, the ith solution in the population of generation G is denoted as X
i
,
G, i
=
1,2
,
…
,
N
P.The mutation step first randomly selects three solutions{
X
r
1
,
G
,
X
r
2
,
G
,
X
r
3
,
G
} from the population P of generation G for the target individual X
i
,
G and then generates the perturbed vector V
i
,
G based on the three selected solutions as follows:(1)
V
i
,
G
=
X
r
1
,
G
+
F
×
X
r
2
,
G
-
X
r
3
,
G
,where i
=
1,2
,
…
,
N
P, r
1, r
2, r
3 are three different numbers randomly selected from {
1,2
,
…
,
N
P
} and F
∈
[
0,1
] is the control parameter.The crossover step generates the trial solutionU
i
,
G
=
(
u
1
,
i
,
G
,
u
2
,
i
,
G
,
…
,
u
n
,
i
,
G
) based on the perturbed vector V
i
,
G
=
(
v
1
,
i
,
G
,
v
2
,
i
,
G
,
…
,
v
n
,
i
,
G
) and the target solution X
i
,
G
=
(
x
1
,
i
,
G
,
x
2
,
i
,
G
,
…
,
x
n
,
i
,
G
) as follows:(2)
u
j
,
i
,
G
=
v
j
,
i
,
G
,
if
rand
j
≤
C
r
or
j
=
j
rand
x
j
,
i
,
G
,
otherwise
,where j
=
1
,
…
,
n, rand
j
∈
[
0,1
] and j
rand is a randomly chosen index from {
1
,
…
,
n
} to ensure that the trial solution U
i
,
G does not duplicate the target solution X
i
,
G. C
r
∈
[
0,1
] is the crossover probability set by the user.Once the trial solution is generated, the selection step compares it with its target solution. If the trial solutionU
i
,
G has an equal or lower objective function value than that of its target solution X
i
,
G, it replaces the target vector in the next generation; otherwise, the target solution retains its place in the population for at least one generation. That is, the solution in the next generation is selected according to the following rule:(3)
X
i
,
G
+
1
=
U
i
,
G
,
if
f
(
U
i
,
G
)
≤
f
(
X
i
,
G
)
X
i
,
G
,
otherwise
.


## 3. Proposed SSDE Algorithm

In this section, we first present the overall framework of our hybrid SSDE algorithm in Algorithm2 and then describe each component of it in details in the following sections. In Algorithm 2, |
P
| denotes the size of population.Algorithm 2:Hybrid scatter search with differential evolution (SSDE).
(1)Begin
(2)  Set the selection probability of each crossover operatorO
k to be the same, that is, p
k
=
1
/
K,
whereK is the sum of all mutation operators.
(3)  Set the iteration counterG
=
0 and the t
=
0.
(4)  Use theDiversification method to generate a population P, evaluate each solution in P and then set the best solution
found so farS
b to be the best one in P.
(5)while (the termination criterion is not reached) do
(6)    Use theReference update method to update reference set R.
(7)    SetG
=
G
+
1, and i
=
0.  Set the solution set P
′ to be empty.
(8)if (t
<
t
max
⁡) do
(9)while (i
<
|
P
|)
do // generate a new solution for each X
i
,
G in P
(10)Set the successful count s
k
G and failure count f
k
G of the crossover operator O
k to be zero.
(11) (1) Mutation
(12)       Randomly select a mutation operator (namelyO
k) using the Adaptive selection method.
(13)       Randomly select solutions fromR according to the requirement of mutation operator O
k.
(14)       Perform mutation operatorO
k on the selected solutions to generate a new trial solution V
i
,
G.
(15)     (2) Crossover
(16)        Apply crossover operation based on (5) to obtain new solution U
i
,
G.
(17)     (3) Selection
(18)       Use (7) to select the new solutionX
i
,
G
+
1. If f
(
X
i
,
G
+
1
)
<
f
(
X
i
,
G
), set s
k
G = s
k
G
+
1; otherwise, set f
k
G = f
k
G
+
1.
(19)     Adds
k
G and f
k
G of each crossover operator O
k to the end of a list L whose length is l. If G
>
l,
then remove the first node of this list so that only a maximum of l nodes are stored in list L.
(20)     Update the selection probabilityp
k of each operator O
k according to the method described in Section 3.4.
(21)      Seti
=
i
+
1.
(22)end while
(23)if (the best solution in P is better than S
b) do
(24)      UpdateS
b and set t
=
0.
(25)else do
(26)      Sett
=
t
+
1.
(27)end if
(28)else do
(29)    Sort the solutions in theP in the ascending order of the objective value, and then randomly reinitialize
the latter half of solutions in P.
(30)    Sett
=
0.
(31)end if
(32)end while
(33)Report the best solution S
b.
(34)End


### 3.1. Initial Population Generation Method

To obtain an initial population with good diversity, we developed a diversification method following the main ideas of [20]. The details of this method are as follows, in which D is the sum of dimensions and L
B
j and U
B
j are the lower bound and upper bound of dimension j. Based on this method, the diversification of initial population can be guaranteed.Step 1. Divide the range of each dimension [
L
B
j
,
U
P
j
]
(
j
=
1
,
…
,
D
) into R equal subranges.Step 2. From dimension j
=
1 to j
=
D, do the following steps.Step 2.1. Set i
=
1 and the selection probability of each subrange r to be p
r
=
1
/
R.Step 2.2. Randomly select a subrange, namely, r, and then within this range generate a random value for x
i
j.Step 2.3. For the selected subrange r, set p
r
=
p
r
-
1
/
n, and for the other unselected subranges set p
k
=
p
k
+
1
/
(
n
×
(
R
-
1
)
).Step 2.4. Set i
=
i
+
1. If i
>
n, j
=
j
+
1 and then go to Step 2.1; otherwise, go to Step 2.2.


### 3.2. Reference Update Method

In canonical SS algorithm, the reference setR generally consists of two parts of solutions: one part is a set of solutions with good quality in objective function value and the other part is a set of solutions with good diversity. This is a good choice for discrete solutions; however, for continuous optimization problems such a setting will often deteriorate the search efficiency. If two solutions are far from each other in the solution space, then the offspring generated from them is often inferior to them. In our preliminary experiment, the results show that the adoption of this setting often results in a very slow convergence speed, which in turn makes the algorithm unable to reach a good solution within a given number of function evaluations. Therefore, in our hybrid SSDE, the reference set R consists of only the best b solutions in the population. At the end of each generation, the reference set R is updated with the best b solutions in the new population.


### 3.3. Mutation Operators Used in Hybrid SSDE

As mentioned above, several mutation operators proposed for DE are adopted in our hybrid SSDE algorithm. The definitions of these mutation operators are as follows. In these equations,X
best denotes the best solution found so far by the algorithm:(1)
DE/rand/1:V
i
,
G
=
X
r
1
,
G
+
F
×
(
X
r
2
,
G
-
X
r
3
,
G
);
(2)
DE/best/1:V
i
,
G
=
X
best
,
G
+
F
×
(
X
r
1
,
G
-
X
r
2
,
G
);
(3)
DE/rand-to-best/1:V
i
,
G
=
X
i
,
G
+
F
×
(
X
best
,
G
-
X
i
,
G
)
+
F
×
(
X
r
1
,
G
-
X
r
2
,
G
);
(4)
DE/best/2:V
i
,
G
=
X
best
,
G
+
F
×
(
X
r
1
,
G
-
X
r
2
,
G
)
+
F
×
(
X
r
3
,
G
-
X
r
4
,
G
).


### 3.4. Adaptive Selection Method for Mutation Operators

To select the mutation operator, we present an adaptive mechanism by introducing the concept of solution survival used in the JADE [13] and SaDE [14]. The success and failure memories in SaDE are also used in the hybrid SSDE. In our SSDE, the application of a selected mutation operator for solution X
i
,
G is viewed as successful only if the new solution resulted from this operator (X
i
,
G
+
1 in Algorithm 2) outperforms X
i
,
G. A list L with a fixed length l (also called the learning period) is established to store the successful counter s
k
G and unsuccessful counter f
k
G of each crossover operator O
k. During the first l generations, the selection probability of each mutation operator is equal to 1
/
K (K is the sum of mutation operators). This warm-up period is used to train the algorithm to analyze the performance and suitability of each mutation operator for the current optimization problem. At the end of each generation, the number of s
k
G and f
k
G for each crossover operator is counted and then added to the end of the list L. Then from the generation G
=
l
+
1, the head node of list L will be removed so that the new record of s
k
G and f
k
G can be added to the end of L.The selection probability of each mutation operatork at generation G (denoted as p
k
G) is calculated as follows according to SaDE [14]:(4)
p
k
G
=
S
k
G
∑
k
=
1
K
S
k
G
,
where
S
k
G
=
∑
g
=
G
-
l
G
-
1
s
k
g
∑
g
=
G
-
l
G
-
1
(
s
k
g
+
f
k
g
)
+
0.01
,
k
=
1
,
…
,
K
;
G
>
l
.


### 3.5. Reinitialization of Population

During the evolution process, the hybrid SSDE algorithm may be trapped in local optimal regions, which in turn will deteriorate the performance of the hybrid SSDE. To further improve the ability of getting out of local optimal regions, a reinitialization method is adopted. During the evolution, we will record the number of consecutive generations that the best solution found so far has not been updated. Whenever this number exceeds a limit, then we will reinitialize the populationP as follows. First, sort the solutions in the population P in the ascending order of their objective function values. Second, delete the latter half of the population in which the solutions have worse objective function values. Third, randomly select two solutions from the left half of P and then perform the S
B
X operator [20] to generate two offspring solutions. We will repeat the third step for |
P
|
/
2 times to generate |
P
| new solutions, and then we select the best |
P
|
/
2 solutions and add them to P.The procedure of theS
B
X operator can be described as follows according to Deb and Agrawal [20]. For two solutions X
=
(
x
1
,
…
,
x
D
) and Y
=
(
y
1
,
…
,
y
D
), theSBX operator can result in two new solutions Z
1
=
(
z
1
,
1
,
…
,
z
1
,
D
) and Z
2
=
(
z
2
,
1
,
…
,
z
2
,
D
) as follows. First, generate a random uniform number u
∈
[
0,1
] and then generate a new random number β based on u and a distribution index η according to (5)
β
=
2
u
1
/
(
1
+
η
)
,
if
u
≤
0.5
1
2
(
1
-
u
)
1
/
(
1
+
η
)
,
otherwise
.At last each dimension of the two new solutions is generated using the following equations: z
1
,
i
=
0.5
[
(
1
+
β
)
x
i
+
(
1
-
β
)
y
i
] and z
2
,
i
=
0.5
[
(
1
-
β
)
x
i
+
(
1
+
β
)
y
i
], (
i
=
1,2
,
…
,
D
).


## 3.1. Initial Population Generation Method

To obtain an initial population with good diversity, we developed a diversification method following the main ideas of [20]. The details of this method are as follows, in which D is the sum of dimensions and L
B
j and U
B
j are the lower bound and upper bound of dimension j. Based on this method, the diversification of initial population can be guaranteed.Step 1. Divide the range of each dimension [
L
B
j
,
U
P
j
]
(
j
=
1
,
…
,
D
) into R equal subranges.Step 2. From dimension j
=
1 to j
=
D, do the following steps.Step 2.1. Set i
=
1 and the selection probability of each subrange r to be p
r
=
1
/
R.Step 2.2. Randomly select a subrange, namely, r, and then within this range generate a random value for x
i
j.Step 2.3. For the selected subrange r, set p
r
=
p
r
-
1
/
n, and for the other unselected subranges set p
k
=
p
k
+
1
/
(
n
×
(
R
-
1
)
).Step 2.4. Set i
=
i
+
1. If i
>
n, j
=
j
+
1 and then go to Step 2.1; otherwise, go to Step 2.2.


## 3.2. Reference Update Method

In canonical SS algorithm, the reference setR generally consists of two parts of solutions: one part is a set of solutions with good quality in objective function value and the other part is a set of solutions with good diversity. This is a good choice for discrete solutions; however, for continuous optimization problems such a setting will often deteriorate the search efficiency. If two solutions are far from each other in the solution space, then the offspring generated from them is often inferior to them. In our preliminary experiment, the results show that the adoption of this setting often results in a very slow convergence speed, which in turn makes the algorithm unable to reach a good solution within a given number of function evaluations. Therefore, in our hybrid SSDE, the reference set R consists of only the best b solutions in the population. At the end of each generation, the reference set R is updated with the best b solutions in the new population.


## 3.3. Mutation Operators Used in Hybrid SSDE

As mentioned above, several mutation operators proposed for DE are adopted in our hybrid SSDE algorithm. The definitions of these mutation operators are as follows. In these equations,X
best denotes the best solution found so far by the algorithm:(1)
DE/rand/1:V
i
,
G
=
X
r
1
,
G
+
F
×
(
X
r
2
,
G
-
X
r
3
,
G
);
(2)
DE/best/1:V
i
,
G
=
X
best
,
G
+
F
×
(
X
r
1
,
G
-
X
r
2
,
G
);
(3)
DE/rand-to-best/1:V
i
,
G
=
X
i
,
G
+
F
×
(
X
best
,
G
-
X
i
,
G
)
+
F
×
(
X
r
1
,
G
-
X
r
2
,
G
);
(4)
DE/best/2:V
i
,
G
=
X
best
,
G
+
F
×
(
X
r
1
,
G
-
X
r
2
,
G
)
+
F
×
(
X
r
3
,
G
-
X
r
4
,
G
).


## 3.4. Adaptive Selection Method for Mutation Operators

To select the mutation operator, we present an adaptive mechanism by introducing the concept of solution survival used in the JADE [13] and SaDE [14]. The success and failure memories in SaDE are also used in the hybrid SSDE. In our SSDE, the application of a selected mutation operator for solution X
i
,
G is viewed as successful only if the new solution resulted from this operator (X
i
,
G
+
1 in Algorithm 2) outperforms X
i
,
G. A list L with a fixed length l (also called the learning period) is established to store the successful counter s
k
G and unsuccessful counter f
k
G of each crossover operator O
k. During the first l generations, the selection probability of each mutation operator is equal to 1
/
K (K is the sum of mutation operators). This warm-up period is used to train the algorithm to analyze the performance and suitability of each mutation operator for the current optimization problem. At the end of each generation, the number of s
k
G and f
k
G for each crossover operator is counted and then added to the end of the list L. Then from the generation G
=
l
+
1, the head node of list L will be removed so that the new record of s
k
G and f
k
G can be added to the end of L.The selection probability of each mutation operatork at generation G (denoted as p
k
G) is calculated as follows according to SaDE [14]:(4)
p
k
G
=
S
k
G
∑
k
=
1
K
S
k
G
,
where
S
k
G
=
∑
g
=
G
-
l
G
-
1
s
k
g
∑
g
=
G
-
l
G
-
1
(
s
k
g
+
f
k
g
)
+
0.01
,
k
=
1
,
…
,
K
;
G
>
l
.


## 3.5. Reinitialization of Population

During the evolution process, the hybrid SSDE algorithm may be trapped in local optimal regions, which in turn will deteriorate the performance of the hybrid SSDE. To further improve the ability of getting out of local optimal regions, a reinitialization method is adopted. During the evolution, we will record the number of consecutive generations that the best solution found so far has not been updated. Whenever this number exceeds a limit, then we will reinitialize the populationP as follows. First, sort the solutions in the population P in the ascending order of their objective function values. Second, delete the latter half of the population in which the solutions have worse objective function values. Third, randomly select two solutions from the left half of P and then perform the S
B
X operator [20] to generate two offspring solutions. We will repeat the third step for |
P
|
/
2 times to generate |
P
| new solutions, and then we select the best |
P
|
/
2 solutions and add them to P.The procedure of theS
B
X operator can be described as follows according to Deb and Agrawal [20]. For two solutions X
=
(
x
1
,
…
,
x
D
) and Y
=
(
y
1
,
…
,
y
D
), theSBX operator can result in two new solutions Z
1
=
(
z
1
,
1
,
…
,
z
1
,
D
) and Z
2
=
(
z
2
,
1
,
…
,
z
2
,
D
) as follows. First, generate a random uniform number u
∈
[
0,1
] and then generate a new random number β based on u and a distribution index η according to (5)
β
=
2
u
1
/
(
1
+
η
)
,
if
u
≤
0.5
1
2
(
1
-
u
)
1
/
(
1
+
η
)
,
otherwise
.At last each dimension of the two new solutions is generated using the following equations: z
1
,
i
=
0.5
[
(
1
+
β
)
x
i
+
(
1
-
β
)
y
i
] and z
2
,
i
=
0.5
[
(
1
-
β
)
x
i
+
(
1
+
β
)
y
i
], (
i
=
1,2
,
…
,
D
).


## 4. Computational Experiments and Results

In this section, we start with the introduction of the experimental environment in Section4.1 and then the test problems in Section 4.2. Finally, Section 4.5 is devoted to carrying out the comparative studies between our SSDE and the other state-of-the-art evolutionary algorithms.


### 4.1. Experimental Settings

The proposed SSDE algorithm is implemented in C++, and all the experiments are carried out on a personal computer with the Intel Core 2 Duo 2.8 GHz CPU and 4 GB memory.The parameters are set as follows based on our preliminary experiments. The population size is set to be 100, the size of reference setR is set to be 35, the control parameter F is generated by N
(
0.8,0.3
), the crossover probability Cr is generated by N
(
0.3,0.3
), and the number of consecutive generations t
max
⁡ is set to be 50.


### 4.2. Test Problems

To test the performance of the proposed SSDE algorithm, 10 benchmark problems are selected from the literature. The definition of these problems is given in Table1, in which the last column is the optimal objective function value for each test problem. In our experiments, we use D
=
30.Table 1
Definition of benchmark problems.
Test function
Solution space
Optimal value
f
1
x
=
∑
i
=
1
D
x
i
2
-
100,100
D
0
f
2
x
=
∑
i
=
1
D
x
i
+
∏
i
=
1
D
x
i
-
10,10
D
0
f
3
x
=
∑
i
=
1
D
∑
j
=
1
i
x
j
2
-
100,100
D
0
f
4
(
x
)
=
max
⁡
x
i
-
100,100
D
0
f
5
x
=
π
D
10
sin
⁡
2
⁡
π
y
1
+
∑
i
=
1
D
-
1
y
i
-
1
2
1
+
10
sin
⁡
2
⁡
π
y
i
+
1
+
y
D
-
1
2
+
∑
i
=
1
D
u
x
i
,
10,100,4
-
50,50
D
0
u
x
i
,
a
,
k
,
m
=


k
x
i
-
a
m
0
k
x
i
-
a
m
x
i
>
a
-
a
≤
x
i
≤
a
x
i
<
-
a
y
i
=
1
+
x
i
+
1
/
4
f
6
x
=
∑
i
=
1
D
x
i
+
0.5
2
-
100,100
D
0
f
7
x
=
∑
i
=
1
D
i
x
i
4
+
rand
0,1
-
1.28,1.28
D
0
f
8
x
=
∑
i
=
1
D
-
x
i
sin
⁡
⁡
x
i
+
D
×
418.98288727243369
-
500,500
D
0
f
9
(
x
)
=
∑
i
=
1
D
x
i
2
-
10
cos
⁡
2
π
x
i
+
10
-
5.12,5.12
D
0
f
10
(
x
)
=
-
20
exp
⁡
-
0.2
1
D
∑
i
=
1
D
x
i
2
-
exp
⁡
1
D
∑
i
=
1
D
cos
⁡
2
π
x
i
+
20
+
e
-
32,32
D
0In the experiment, a total of 50 independent runs are performed for each test problem to collect the statistical performance of each algorithm. The independentt
-test is used to show the statistical difference between different algorithms and the result for each problem is given in the last column of Tables 2, 3, and 4. In the last column denoted as Sig, the signal “+” denotes that the performance difference between our SSDE and the best one among the other algorithms in the table is significant with a confidence level of 95%, while the signal “−” denotes that their performance difference is not significant.Table 2
Comparison results between SSDE algorithms with and without adaptive selection method.
Test functions
Gen
Mean (Std Dev)
Sig
SSDErand1
SSDEbest1
SSDE
r
-best
SSDEbest2
SSDE
f
1
1500
3.2
e
-
18  (2.7
e
-
18)
6.0
e
-
31  (9.7
e
-
27)
8.1
e
-
31  (1.2
e
-
32)
4.2
e
-
27 (3.6
e
-
24)
5.96
e
-
36  (1.33
e
-
36)
+
f
2
2000
1.2
e
-
15  (4.2
e
-
16)
2.4
e
-
40  (2.0
e
-
40)
2.1
e
-
29  (1.5
e
-
28)
1.1
e
-
17  (1.6
e
-
17)
3.77
e
-
27  (1.33
e
-
36)
+
f
3
5000
6.5148(12.8856)
6.5
e
-
8  (12.16)
6.3
e
-
8  (1.2
e
-
17)
1.7
e
-
11  (1.2
e
-
13)
9.83
e
-
12  (2.18
e
-
11)
+
f
4
5000
5.2
e
-
3 (3.8
e
-
2)
4.2
e
-
2 (8.1
e
-
2)
2.7
e
-
3 (1.4
e
-
3)
4.1
e
-
10 (1.2
e
-
11)
6.44
e
-
13
(
2.67
e
-
12
)
+
f
5
1500
5.3
e
-
19 (5.1
e
-
19)
2.0
e
-
3 (1.2
e
-
3)
1.8
e
-
32 (1.9
e
-
43)
3.2
e
-
23 (2.4
e
-
21)
1.57
e
-
32 (2.75
e
-
47)
+
f
6
1500
2.6
e
-
18 (1.8
e
-
19)
1.3
e
-
32 (3.0
e
-
33)
0(0)
2.7
e
-
24 (3.3
e
-
23)
3.08
e
-
35 (3.08
e
-
34)
+
f
7
3000
2.7
e
-
46 (3.1
e
-
53)
0 (0)
0 (0)
0 (0)
0 (0)
−
f
8
9000
0 (0)
6.0237(17.4291)
0 (0)
1.1(6.2506)
0 (0)
−
f
9
5000
0 (0)
3.2942(2.1396)
4.4
e
-
2 (2.5
e
-
1)
0 (0)
0 (0)
−
f
10
2000
1.3
e
-
13 (1.1
e
-
17)
1.2
e
-
14 (4.1
e
-
12)
1.3
e
-
13 (2.3
e
-
15)
7.8
e
-
1 (1.7688)
4.51
e
-
15 (3.55
e
-
15)
+Table 3
Comparison results between SS-SBX and SSDE.
Test functions
Gen
Mean (Std Dev)
Sig
SS-SBX
SSDE
f
1
1500
0 (0)
5.96
e
-
36 (1.33
e
-
36)
−
f
2
2000
0 (0)
3.77
e
-
27 (1.33
e
-
36)
−
f
3
5000
9.74
e
+
00 (1.5
e
+
01)
9.83
e
-
12 (2.18
e
-
11)
+
f
4
5000
0 (0)
6.44
e
-
13 (2.67
e
-
12)
+
f
5
1500
3.31
e
-
01 (3.09
e
-
03)
1.57
e
-
32 (2.75
e
-
47)
+
f
6
1500
1.21
e
-
01 (1.18
e
-
01)
3.08
e
-
35 (3.08
e
-
34)
+
f
7
3000
0 (0)
0 (0)
−
f
8
9000
2.33
e
-
01 (1.70
e
-
00)
0 (0)
+
f
9
5000
0 (0)
0 (0)
−
f
10
2000
4.44
e
-
16 (0)
7.51
e
-
15 (3.55
e
-
15)
+Table 4
Comparison results between SSDE and the other state-of-the-art algorithms.
Test functions
Gen
Mean (Std Dev)
Sig
SaDE
JADE
SSDE
f
1
1500
4.5
e
-
20 (6.9
e
-
20)
1.3
e
-
54 (9.2
e
-
54)
5.96
e
-
36 (1.33
e
-
36)
+
f
2
2000
1.9
e
-
14 (1.05
e
-
14)
3.9
e
-
22 (2.7
e
-
21)
3.77
e
-
27
(
1.33
e
-
36
)
+
f
3
5000
9.0
e
-
37 (5.43
e
-
36)
6.0
e
-
87 (1.9
e
-
86)
9.83
e
-
12 (2.18
e
-
11)
+
f
4
5000
7.4
e
-
11 (1.82
e
-
10)
4.3
e
-
66 (1.2
e
-
65)
6.44
e
-
13 (2.67
e
-
12)
+
f
5
1500
1.2
e
-
19 (2.0
e
-
19)
1.6
e
-
32 (5.5
e
-
48)
1.57
e
-
32 (2.75
e
-
47)
−
f
6
1500
0 (0)
0 (0)
3.08
e
-
35 (3.08
e
-
34)
+
f
7
3000
4.8
e
-
03 (1.2
e
-
03)
6.8
e
-
04 (2.5
e
-
04)
0 (0)
+
f
8
9000
4.7
e
+
00 (3.3
e
+
01)
7.1
e
+
00 (2.8
e
+
01)
0 (0)
+
f
9
5000
0 (0)
0 (0)
0 (0)
−
f
10
2000
4.3
e
-
14 (2.6
e
-
14)
4.4
e
-
15 (0)
4.51
e
-
15 (3.55
e
-
15)
−


### 4.3. Efficiency Analysis of Adaptive Selection Method

In this section, we first carried out an experiment to show the efficiency of the adaptive selection method. We compared our proposed SSDE algorithm with four SSDE algorithms each of which adopts only one mutation operator. These four algorithms are, respectively, denoted asSSDE
rand
1, SSDE
best
1, SSDE
r
-best, and SSDE
best
2 according to the four mutation operators.The comparison results for the proposed SSDE algorithm and the other SSDE with only one mutation operator are presented in Table2, in which a better result is shown in the bold type. The second columnGen denotes the generations used in the algorithm as the stopping criterion, andMean (Std Dev) represents the average value and the standard deviation obtained by each algorithm for each test problem.From Table2, it can be seen that the SSDE algorithm with the adaptive selection method can obtain the best results and show the best robustness for almost all the test problems. It is significantly better than the other four algorithms for 9 out of the 10 test problems. The reason behind this phenomenon is that this strategy can adaptively select the most appropriate mutation operators for the current problem. In addition, the adoption of multiple kinds of mutation operators also help to improve the exploration ability of SSDE because such a strategy can help to enhance the algorithm’s ability of getting out of local optimal regions.


### 4.4. Efficiency Analysis of Hybrid Architecture of SSDE

To test the impact of adopting DE as the generation method for new solutions, in this section we implemented another kind of SS in which the new solutions were generated by the simulated binary crossover (SBX). That is, lines from 10 to 20 in Algorithm 2 are replaced by the following steps: first, randomly select two solutions from the reference R; second, apply theSBX operator to the two solutions to generate two new solutions; third, select the best one as the new solution X
i
,
G
+
1. This algorithm is denoted asSS-SBX.The comparison results for the two kinds of SS algorithms are presented in Table3, in which a better result is shown in the bold type. From this table, it can be seen that althoughSS-SBX obtains the best results for f
1, f
2, f
4, f
7, f
9, and f
10, for the other problems its performance is much worse. The SSDE algorithm obtains the best results for 6 out of the 10 problems, and its performance for the other four problems is also very good. Therefore, it can be concluded that the SSDE algorithm is superior theSS-SBX, especially with respect to the robustness.


### 4.5. Comparisons with Other State-of-the-Art Algorithms

In the above sections, we have shown that the adaptive selection mechanism based on multiple mutation operators and the adoption of DE into SS can help to improve both the search performance and robustness of SS. In this section, we further compare our SSDE with the other state-of-the-art evolutionary algorithms in the literature. These algorithms include the SaDE proposed in [14] and the JADE with archive proposed in [13]. Both the evolutionary algorithms have adaptive strategies in parameter control or mutation strategy selection during the evolution process. The comparison results are given in Table 4.From Table4, it can be found that our SSDE obtains better results for 7 out of the 10 problems with comparison to the SaDE algorithm in [14] (the performance differences are significant for all of the 7 problems) and for 4 out of the 10 problems with comparison to the JADE algorithm in [13]. For problems f
7 and f
8, our SSDE algorithm can reach the optimal solutions, while the other two algorithms SaDE and JADE show a much worse performance. In addition, it also appears that our SSDE algorithm is more robust for different kinds of problems. On average, it can be concluded that our SSDE is competitive to the JADE algorithm but superior to the SaDE algorithm for the 10 benchmark test problems.To give a graphical illustration of this analysis, we reimplemented the SaDE algorithm and compared the evolution processes between our SSDE and the SaDE for the first six problems. The comparison results are shown in Figure1, in which the ordinate is log10
(
f
(
X
)
) in which f
(
X
) is the objective function value of the best solution found in each iteration. Please note that whenever the algorithm reaches the optimal solution, the evolution process line will terminate in the figures because the optimal objective function value of each problem is zero. From this figure, it can be seen that the convergence speed of our SSDE is much faster than that of the SaDE for all the six test problems.Figure 1
Evolution process of SSDE and SaDE for functionsf
1
–
f
6.


## 4.1. Experimental Settings

The proposed SSDE algorithm is implemented in C++, and all the experiments are carried out on a personal computer with the Intel Core 2 Duo 2.8 GHz CPU and 4 GB memory.The parameters are set as follows based on our preliminary experiments. The population size is set to be 100, the size of reference setR is set to be 35, the control parameter F is generated by N
(
0.8,0.3
), the crossover probability Cr is generated by N
(
0.3,0.3
), and the number of consecutive generations t
max
⁡ is set to be 50.


## 4.2. Test Problems

To test the performance of the proposed SSDE algorithm, 10 benchmark problems are selected from the literature. The definition of these problems is given in Table1, in which the last column is the optimal objective function value for each test problem. In our experiments, we use D
=
30.Table 1
Definition of benchmark problems.
Test function
Solution space
Optimal value
f
1
x
=
∑
i
=
1
D
x
i
2
-
100,100
D
0
f
2
x
=
∑
i
=
1
D
x
i
+
∏
i
=
1
D
x
i
-
10,10
D
0
f
3
x
=
∑
i
=
1
D
∑
j
=
1
i
x
j
2
-
100,100
D
0
f
4
(
x
)
=
max
⁡
x
i
-
100,100
D
0
f
5
x
=
π
D
10
sin
⁡
2
⁡
π
y
1
+
∑
i
=
1
D
-
1
y
i
-
1
2
1
+
10
sin
⁡
2
⁡
π
y
i
+
1
+
y
D
-
1
2
+
∑
i
=
1
D
u
x
i
,
10,100,4
-
50,50
D
0
u
x
i
,
a
,
k
,
m
=


k
x
i
-
a
m
0
k
x
i
-
a
m
x
i
>
a
-
a
≤
x
i
≤
a
x
i
<
-
a
y
i
=
1
+
x
i
+
1
/
4
f
6
x
=
∑
i
=
1
D
x
i
+
0.5
2
-
100,100
D
0
f
7
x
=
∑
i
=
1
D
i
x
i
4
+
rand
0,1
-
1.28,1.28
D
0
f
8
x
=
∑
i
=
1
D
-
x
i
sin
⁡
⁡
x
i
+
D
×
418.98288727243369
-
500,500
D
0
f
9
(
x
)
=
∑
i
=
1
D
x
i
2
-
10
cos
⁡
2
π
x
i
+
10
-
5.12,5.12
D
0
f
10
(
x
)
=
-
20
exp
⁡
-
0.2
1
D
∑
i
=
1
D
x
i
2
-
exp
⁡
1
D
∑
i
=
1
D
cos
⁡
2
π
x
i
+
20
+
e
-
32,32
D
0In the experiment, a total of 50 independent runs are performed for each test problem to collect the statistical performance of each algorithm. The independentt
-test is used to show the statistical difference between different algorithms and the result for each problem is given in the last column of Tables 2, 3, and 4. In the last column denoted as Sig, the signal “+” denotes that the performance difference between our SSDE and the best one among the other algorithms in the table is significant with a confidence level of 95%, while the signal “−” denotes that their performance difference is not significant.Table 2
Comparison results between SSDE algorithms with and without adaptive selection method.
Test functions
Gen
Mean (Std Dev)
Sig
SSDErand1
SSDEbest1
SSDE
r
-best
SSDEbest2
SSDE
f
1
1500
3.2
e
-
18  (2.7
e
-
18)
6.0
e
-
31  (9.7
e
-
27)
8.1
e
-
31  (1.2
e
-
32)
4.2
e
-
27 (3.6
e
-
24)
5.96
e
-
36  (1.33
e
-
36)
+
f
2
2000
1.2
e
-
15  (4.2
e
-
16)
2.4
e
-
40  (2.0
e
-
40)
2.1
e
-
29  (1.5
e
-
28)
1.1
e
-
17  (1.6
e
-
17)
3.77
e
-
27  (1.33
e
-
36)
+
f
3
5000
6.5148(12.8856)
6.5
e
-
8  (12.16)
6.3
e
-
8  (1.2
e
-
17)
1.7
e
-
11  (1.2
e
-
13)
9.83
e
-
12  (2.18
e
-
11)
+
f
4
5000
5.2
e
-
3 (3.8
e
-
2)
4.2
e
-
2 (8.1
e
-
2)
2.7
e
-
3 (1.4
e
-
3)
4.1
e
-
10 (1.2
e
-
11)
6.44
e
-
13
(
2.67
e
-
12
)
+
f
5
1500
5.3
e
-
19 (5.1
e
-
19)
2.0
e
-
3 (1.2
e
-
3)
1.8
e
-
32 (1.9
e
-
43)
3.2
e
-
23 (2.4
e
-
21)
1.57
e
-
32 (2.75
e
-
47)
+
f
6
1500
2.6
e
-
18 (1.8
e
-
19)
1.3
e
-
32 (3.0
e
-
33)
0(0)
2.7
e
-
24 (3.3
e
-
23)
3.08
e
-
35 (3.08
e
-
34)
+
f
7
3000
2.7
e
-
46 (3.1
e
-
53)
0 (0)
0 (0)
0 (0)
0 (0)
−
f
8
9000
0 (0)
6.0237(17.4291)
0 (0)
1.1(6.2506)
0 (0)
−
f
9
5000
0 (0)
3.2942(2.1396)
4.4
e
-
2 (2.5
e
-
1)
0 (0)
0 (0)
−
f
10
2000
1.3
e
-
13 (1.1
e
-
17)
1.2
e
-
14 (4.1
e
-
12)
1.3
e
-
13 (2.3
e
-
15)
7.8
e
-
1 (1.7688)
4.51
e
-
15 (3.55
e
-
15)
+Table 3
Comparison results between SS-SBX and SSDE.
Test functions
Gen
Mean (Std Dev)
Sig
SS-SBX
SSDE
f
1
1500
0 (0)
5.96
e
-
36 (1.33
e
-
36)
−
f
2
2000
0 (0)
3.77
e
-
27 (1.33
e
-
36)
−
f
3
5000
9.74
e
+
00 (1.5
e
+
01)
9.83
e
-
12 (2.18
e
-
11)
+
f
4
5000
0 (0)
6.44
e
-
13 (2.67
e
-
12)
+
f
5
1500
3.31
e
-
01 (3.09
e
-
03)
1.57
e
-
32 (2.75
e
-
47)
+
f
6
1500
1.21
e
-
01 (1.18
e
-
01)
3.08
e
-
35 (3.08
e
-
34)
+
f
7
3000
0 (0)
0 (0)
−
f
8
9000
2.33
e
-
01 (1.70
e
-
00)
0 (0)
+
f
9
5000
0 (0)
0 (0)
−
f
10
2000
4.44
e
-
16 (0)
7.51
e
-
15 (3.55
e
-
15)
+Table 4
Comparison results between SSDE and the other state-of-the-art algorithms.
Test functions
Gen
Mean (Std Dev)
Sig
SaDE
JADE
SSDE
f
1
1500
4.5
e
-
20 (6.9
e
-
20)
1.3
e
-
54 (9.2
e
-
54)
5.96
e
-
36 (1.33
e
-
36)
+
f
2
2000
1.9
e
-
14 (1.05
e
-
14)
3.9
e
-
22 (2.7
e
-
21)
3.77
e
-
27
(
1.33
e
-
36
)
+
f
3
5000
9.0
e
-
37 (5.43
e
-
36)
6.0
e
-
87 (1.9
e
-
86)
9.83
e
-
12 (2.18
e
-
11)
+
f
4
5000
7.4
e
-
11 (1.82
e
-
10)
4.3
e
-
66 (1.2
e
-
65)
6.44
e
-
13 (2.67
e
-
12)
+
f
5
1500
1.2
e
-
19 (2.0
e
-
19)
1.6
e
-
32 (5.5
e
-
48)
1.57
e
-
32 (2.75
e
-
47)
−
f
6
1500
0 (0)
0 (0)
3.08
e
-
35 (3.08
e
-
34)
+
f
7
3000
4.8
e
-
03 (1.2
e
-
03)
6.8
e
-
04 (2.5
e
-
04)
0 (0)
+
f
8
9000
4.7
e
+
00 (3.3
e
+
01)
7.1
e
+
00 (2.8
e
+
01)
0 (0)
+
f
9
5000
0 (0)
0 (0)
0 (0)
−
f
10
2000
4.3
e
-
14 (2.6
e
-
14)
4.4
e
-
15 (0)
4.51
e
-
15 (3.55
e
-
15)
−


## 4.3. Efficiency Analysis of Adaptive Selection Method

In this section, we first carried out an experiment to show the efficiency of the adaptive selection method. We compared our proposed SSDE algorithm with four SSDE algorithms each of which adopts only one mutation operator. These four algorithms are, respectively, denoted asSSDE
rand
1, SSDE
best
1, SSDE
r
-best, and SSDE
best
2 according to the four mutation operators.The comparison results for the proposed SSDE algorithm and the other SSDE with only one mutation operator are presented in Table2, in which a better result is shown in the bold type. The second columnGen denotes the generations used in the algorithm as the stopping criterion, andMean (Std Dev) represents the average value and the standard deviation obtained by each algorithm for each test problem.From Table2, it can be seen that the SSDE algorithm with the adaptive selection method can obtain the best results and show the best robustness for almost all the test problems. It is significantly better than the other four algorithms for 9 out of the 10 test problems. The reason behind this phenomenon is that this strategy can adaptively select the most appropriate mutation operators for the current problem. In addition, the adoption of multiple kinds of mutation operators also help to improve the exploration ability of SSDE because such a strategy can help to enhance the algorithm’s ability of getting out of local optimal regions.


## 4.4. Efficiency Analysis of Hybrid Architecture of SSDE

To test the impact of adopting DE as the generation method for new solutions, in this section we implemented another kind of SS in which the new solutions were generated by the simulated binary crossover (SBX). That is, lines from 10 to 20 in Algorithm 2 are replaced by the following steps: first, randomly select two solutions from the reference R; second, apply theSBX operator to the two solutions to generate two new solutions; third, select the best one as the new solution X
i
,
G
+
1. This algorithm is denoted asSS-SBX.The comparison results for the two kinds of SS algorithms are presented in Table3, in which a better result is shown in the bold type. From this table, it can be seen that althoughSS-SBX obtains the best results for f
1, f
2, f
4, f
7, f
9, and f
10, for the other problems its performance is much worse. The SSDE algorithm obtains the best results for 6 out of the 10 problems, and its performance for the other four problems is also very good. Therefore, it can be concluded that the SSDE algorithm is superior theSS-SBX, especially with respect to the robustness.


## 4.5. Comparisons with Other State-of-the-Art Algorithms

In the above sections, we have shown that the adaptive selection mechanism based on multiple mutation operators and the adoption of DE into SS can help to improve both the search performance and robustness of SS. In this section, we further compare our SSDE with the other state-of-the-art evolutionary algorithms in the literature. These algorithms include the SaDE proposed in [14] and the JADE with archive proposed in [13]. Both the evolutionary algorithms have adaptive strategies in parameter control or mutation strategy selection during the evolution process. The comparison results are given in Table 4.From Table4, it can be found that our SSDE obtains better results for 7 out of the 10 problems with comparison to the SaDE algorithm in [14] (the performance differences are significant for all of the 7 problems) and for 4 out of the 10 problems with comparison to the JADE algorithm in [13]. For problems f
7 and f
8, our SSDE algorithm can reach the optimal solutions, while the other two algorithms SaDE and JADE show a much worse performance. In addition, it also appears that our SSDE algorithm is more robust for different kinds of problems. On average, it can be concluded that our SSDE is competitive to the JADE algorithm but superior to the SaDE algorithm for the 10 benchmark test problems.To give a graphical illustration of this analysis, we reimplemented the SaDE algorithm and compared the evolution processes between our SSDE and the SaDE for the first six problems. The comparison results are shown in Figure1, in which the ordinate is log10
(
f
(
X
)
) in which f
(
X
) is the objective function value of the best solution found in each iteration. Please note that whenever the algorithm reaches the optimal solution, the evolution process line will terminate in the figures because the optimal objective function value of each problem is zero. From this figure, it can be seen that the convergence speed of our SSDE is much faster than that of the SaDE for all the six test problems.Figure 1
Evolution process of SSDE and SaDE for functionsf
1
–
f
6.


## 5. Conclusions

In this paper, we developed a hybrid scatter search algorithm by incorporating the differential evolution algorithm to act as the new solution generation method. To make the proposed hybrid algorithm more robust for different kinds of optimization problems, an adaptive selection mechanism is developed for multiple mutation strategies. A population reinitialization method is also used to help the algorithm to get out from local optimums. The computational results based on benchmark test problems show that the proposed hybrid SSDE algorithm is very efficient and robust and that its performance is competitive or even superior to two state-of-the-art evolutionary algorithms in the literature.



---

*Source: 303125-2015-03-18.xml*