# An Improved Multiobjective Algorithm: DNSGA2-PSA

Authors: Dan Qu; Xianfeng Ding; Hongmei Wang
Journal: Journal of Robotics
 (2018)

---

## Abstract

In general, the proximities to a certain diversity along the front and the Pareto front have the equal importance for solving multiobjective optimization problems (MOPs). However, most of the existing evolutionary algorithms give priority to the proximity over the diversity. To improve the diversity and decrease execution time of the nondominated sorting genetic algorithm II (NSGA-II), an improved algorithm is presented in this paper, which adopts a new vector ranking scheme to decrease the whole runtime and utilize Part and Select Algorithm (PSA) to maintain the diversity. In this algorithm, a more efficient implementation of nondominated sorting, namely, dominance degree approach for nondominated sorting (DDA-NS), is presented. Moreover, an improved diversity preservation mechanism is proposed to select a well-diversified set out of an arbitrary given set. By embedding PSA and DDA-NS into NSGA-II, denoted as DNSGA2-PSA, the whole runtime of the algorithm is decreased significantly and the exploitation of diversity is enhanced. The computational experiments show that the combination of both (DDA-NS, PSA) to NSGA-II is better than the isolated use cases, and DNSGA2-PSA still performs well in the high-dimensional cases.


---

## Body

## 1. Introduction

In the past 30 years, evolutionary multiobjective optimization (EMO) has been popular in research and application [1–10], and a lot of multiobjective evolutionary algorithms (MOEAs) have been presented [11–25]. The nondominated sorting genetic algorithm (NSGA) being one of the first MOEA was introduced in [12]. Then, an improved version of NSGA, called NSGA-II [13], has been proposed. To improve the performance of NSGA-II, S. Salomon et al. [26, 27] introduced a diversity preservation mechanism that is based on partitioning algorithm for function selection. It is shown that this procedure significantly enhances the exploitation of diversity when embedded into NSGA-II [27]. Moreover, P. Mohapatra and S. Roy [28] proposed a new method which was called AP-NSGA-II. It employed the machine processed of NSGA-II but worked with a set of average-point-based techniques to maintain the diversity among solutions. The performance of the proposed AP-NSGA-II can maintain the diversity to some degree. Then, X. Y. Pan and J. Zhu [29] proposed an improved algorithm LDMNSGA-II. The algorithm adopted the technology of Latin hypercube sampling to ensure that the distribution of initial population could be uniform. And it used differential evolution operator to replace crossover operator of NSGA-II to enhance the local search ability and search accuracy. The results demonstrate that the proposed algorithm can achieve a good overall property on multiobjective optimization. Considering the execution time of NSGA-II, many scholars have made some research on the algorithm [30–34]. It is worth noting that Y. R. Zhou et al. [35] introduced the dominance degree matrix for a vector set. And a fast method was designed for constructing the new data structure. By using the dominance degree matrix, it developed an efficient implementation of nondominated sorting called dominance degree approach for nondominated sorting (DDA-NS). Empirical results demonstrated that DDA-NS transcends other typical approach for nondominated sorting and DDA-NS works well for solving multiobjective problems. For these reasons, we borrow the idea of dominance degree matrix and PSA method to improve the performance of NSGA-II. So that it can combine the advantages of reducing runtime and improving diversity.This paper is organized as follows. Section1 provides an introduction; Section 2 introduces the DDA-NS method and PSA. Section 3 describes a straightforward approach for integrating DDA-NS and PSA into NSGA-II. The performance comparison is shown at Section 4. Finally, the paper ends with some conclusions in Section 5.


## 2. Basic Ideas and Concepts

Mathematically, a multiobjective problem (MOP) is described as(1)
y
=
min
⁡
f
1
x
,
f
2
x
,
…
,
f
m
x
THere x
=
(
x
1
,
.
.
.
,
x
n
)
T
∈
Ω is the decision vector of dimension n, y
i
=
f
i
(
x
) is the i
t
h objective function, and Ω
∈
R
n is the decision space (DS). The image set, Y
=
y
∣
x
∈
Ω, is called the objective space (OS). Let x
∗
∈
Ω be a decision vector. A decision vector x
∗
∈
Ω is called a Pareto optimal solution if its objective vector is not dominated by any other vector in the objective space Y. All the Pareto optimal solutions constitute the Pareto optimal set. The Pareto optimal front is the set of images of the Pareto optimal set.


### 2.1. DDA-NSS

We first introduce some basic notions of DDA-NS which was introduced in [35].


#### 2.1.1. Dominance Degree

Letd
(
X
,
Y
)
=
i
∣
i
∈
1
,
…
,
m
,
X
i
≤
Y
i, which is called dominance degree of X to Y and represents the dominance between X and Y, where |
A
| is the cardinality of A.It is obvious to find the following:(
1
)  0
≤
d
(
X
,
Y
)
≤
m(
2
)  If X
≺
Y, then d
(
X
,
Y
)
=
m, which means that d
(
X
,
Y
) will reach its maximum value at m when X
≺
Y(
3
) If d
X
,
Y
=
m, then X
≺
Yor X
=
Y


#### 2.1.2. Dominance Degree Matrix

LetP
=
Y
1
,
Y
2
,
.
.
.
,
Y
N be a N objective vectors set, Y
i
=
(
y
1
i
,
y
2
i
,
.
.
.
,
y
m
i
)
T
∈
R
m, and (
i
=
1,2
,
.
.
.
,
N
) is a m dimensional vector. Define the dominance degree matrix D
=
(
d
i
j
)
N
×
N on the set P for the dominance relation by (2)
d
i
j
=
d
Y
i
,
Y
j
,
i
,
j
∈
1,2
,
…
,
N
.A faster method for calculating the dominance degree matrix follows the following two main steps:(
1
) Sort the objective vectors on every objective by using Quicksort [36].(
2
) Construct the dominance degree matrix by using the sorted results acquired in step (
1
).Firstly, we construct the comparison matrix of a row vectorr
=
(
r
1
,
r
2
,
.
.
.
,
r
N
)
∈
R
N and define the comparison matrix C
r
=
(
c
i
j
)
N
×
N of r by(3)
c
i
j
=
1
,
r
i
≤
r
j
,
0
,
otherwise
.One can see Algorithm 1 in literature [35] to calculate the matrix C
r.Secondly, sum the comparison matrices of each objective vector and then we can obtain the dominance degree matrix of a set of vectors. One can see Algorithm 2 in literature [35] for the details of this procedure.Finally, a novel nondominated sorting method is provided in the following paragraph, in which the dominance degree matrix is utilized to assign the solutions to nondominated fronts in the populationP.As we know, nondominated sorting approach assigns all solutions in initial populationP to nondominated fronts F
i. The first front F
1 consists of the set of nondominated solutions in the initialized population P. The second front F
2 is the set of nondominated solutions in the remaining set P
-
F
1 (i.e., removes all solutions assigned to F
1 from the population P) and repeats the procedure for the subsequent fronts.Assume thatA
N
×
N denotes the dominance degree matrix of the population P of size N. In order to eliminate the influence of the same individuals, the corresponding elements of A are set to 0. Let m
a
x
(
A
) be a row vector which consists of the corresponding maximum elements from each column of A. It can be verified that, for any Y
i
≠
Y
j
∈
P, Y
i dominates Y
j if and only if d
Y
i
,
Y
j equals m. Then, the solutions corresponding to elements of m
a
x
(
A
) whose subscripts are less than m are nondominated solutions of P. These nondominated solutions were classified to the first front F
1. Then, delete the column and row vectors corresponding to F
1 from A and denote the remaining matrix by A
1. Then, continue the same procedure for matrix A
1 and obtain the second front F
2. Repeat such a process until all solutions are classified to F
i. Thus, a new nondominated sorting method is attained, which is provided in Algorithm 3 of literature [35].The time complexity of the DDA-NS approach isO
(
m
N
2
). By using the DDA-NS approach, the complexity to compare the objective function values of nondominated sorting process in the NSGA-II can be reduced from O
(
m
N
2
) to O
(
m
N
log
⁡
N
) at iteration of the NSGA-II algorithm.


### 2.2. Part and Select Algorithm (PSA)

The Part and Select Algorithm (PSA) was put forward by S. Salomon et al. [27]. In this part we will make a brief introduction of the Part and Select Algorithm (PSA) which aims to select the well-spread points from a set of A (contains n candidate solutions). The procedure contains two main steps.Step 1.
DivideA into m subsets, so that the similar members can be grouped in the same subset.Step 2.
Each diverse subset is constructed through selecting one member from each generated subset.
To divide a set intok subsets, PSA carry on k
-
1 divisions of one set into two subsets. In each dividing process, the set with the greatest dissimilarity among whole elements is divided. The same procedure is continued until the desired stopping criterion is met. The desired stopping criterion can be either a predefined number of subsets or a maximal dissimilarity among each of the subsets. The dissimilarity of the set A is the measure ϕ
A.LetA
=
f
i
=
[
f
i
1
,
.
.
.
,
f
i
m
]
⊂
R
m (n objective vector f
i
=
F
(
x
i
) for points x
i
∈
Q) and denote(4)
a
j
≔
min
i
=
1
,
…
,
n
⁡
f
i
j
b
j
≔
max
i
=
1
,
…
,
n
⁡
f
i
j
Δ
j
≔
b
j
-
a
j
,
j
=
1
,
…
m
(5)
ϕ
A
≔
max
i
=
1
,
…
,
m
⁡
Δ
jObviously, a largerϕ
A indicates a greater dissimilarity among the members of A. The pseudocode of PSA originates from Algorithm 1 in literature [27].After the setA has been divided into the k subsets A
1
,
.
.
.
,
A
k, choose the member closest to the center of the hyperrectangle circumscribing A
i in the sense of Euclidean metric. If there exist more than one member closest to the center, chose one of them randomly. Let A
=
(
f
1
,
.
.
.
,
f
n
)
⊂
R
m be the original set of n members, from which a subset of k members is to be selected. The complexity of this selecting approach is O
(
m
n
k
).Proposition 1 (see [27]).
Given a setA
=
(
f
1
,
.
.
.
,
f
n
)
⊂
R
m, the overall complexity of choosing k
≤
n elements out of A using PSA and the center point selection is O
(
m
n
k
).


## 2.1. DDA-NSS

We first introduce some basic notions of DDA-NS which was introduced in [35].


### 2.1.1. Dominance Degree

Letd
(
X
,
Y
)
=
i
∣
i
∈
1
,
…
,
m
,
X
i
≤
Y
i, which is called dominance degree of X to Y and represents the dominance between X and Y, where |
A
| is the cardinality of A.It is obvious to find the following:(
1
)  0
≤
d
(
X
,
Y
)
≤
m(
2
)  If X
≺
Y, then d
(
X
,
Y
)
=
m, which means that d
(
X
,
Y
) will reach its maximum value at m when X
≺
Y(
3
) If d
X
,
Y
=
m, then X
≺
Yor X
=
Y


### 2.1.2. Dominance Degree Matrix

LetP
=
Y
1
,
Y
2
,
.
.
.
,
Y
N be a N objective vectors set, Y
i
=
(
y
1
i
,
y
2
i
,
.
.
.
,
y
m
i
)
T
∈
R
m, and (
i
=
1,2
,
.
.
.
,
N
) is a m dimensional vector. Define the dominance degree matrix D
=
(
d
i
j
)
N
×
N on the set P for the dominance relation by (2)
d
i
j
=
d
Y
i
,
Y
j
,
i
,
j
∈
1,2
,
…
,
N
.A faster method for calculating the dominance degree matrix follows the following two main steps:(
1
) Sort the objective vectors on every objective by using Quicksort [36].(
2
) Construct the dominance degree matrix by using the sorted results acquired in step (
1
).Firstly, we construct the comparison matrix of a row vectorr
=
(
r
1
,
r
2
,
.
.
.
,
r
N
)
∈
R
N and define the comparison matrix C
r
=
(
c
i
j
)
N
×
N of r by(3)
c
i
j
=
1
,
r
i
≤
r
j
,
0
,
otherwise
.One can see Algorithm 1 in literature [35] to calculate the matrix C
r.Secondly, sum the comparison matrices of each objective vector and then we can obtain the dominance degree matrix of a set of vectors. One can see Algorithm 2 in literature [35] for the details of this procedure.Finally, a novel nondominated sorting method is provided in the following paragraph, in which the dominance degree matrix is utilized to assign the solutions to nondominated fronts in the populationP.As we know, nondominated sorting approach assigns all solutions in initial populationP to nondominated fronts F
i. The first front F
1 consists of the set of nondominated solutions in the initialized population P. The second front F
2 is the set of nondominated solutions in the remaining set P
-
F
1 (i.e., removes all solutions assigned to F
1 from the population P) and repeats the procedure for the subsequent fronts.Assume thatA
N
×
N denotes the dominance degree matrix of the population P of size N. In order to eliminate the influence of the same individuals, the corresponding elements of A are set to 0. Let m
a
x
(
A
) be a row vector which consists of the corresponding maximum elements from each column of A. It can be verified that, for any Y
i
≠
Y
j
∈
P, Y
i dominates Y
j if and only if d
Y
i
,
Y
j equals m. Then, the solutions corresponding to elements of m
a
x
(
A
) whose subscripts are less than m are nondominated solutions of P. These nondominated solutions were classified to the first front F
1. Then, delete the column and row vectors corresponding to F
1 from A and denote the remaining matrix by A
1. Then, continue the same procedure for matrix A
1 and obtain the second front F
2. Repeat such a process until all solutions are classified to F
i. Thus, a new nondominated sorting method is attained, which is provided in Algorithm 3 of literature [35].The time complexity of the DDA-NS approach isO
(
m
N
2
). By using the DDA-NS approach, the complexity to compare the objective function values of nondominated sorting process in the NSGA-II can be reduced from O
(
m
N
2
) to O
(
m
N
log
⁡
N
) at iteration of the NSGA-II algorithm.


## 2.1.1. Dominance Degree

Letd
(
X
,
Y
)
=
i
∣
i
∈
1
,
…
,
m
,
X
i
≤
Y
i, which is called dominance degree of X to Y and represents the dominance between X and Y, where |
A
| is the cardinality of A.It is obvious to find the following:(
1
)  0
≤
d
(
X
,
Y
)
≤
m(
2
)  If X
≺
Y, then d
(
X
,
Y
)
=
m, which means that d
(
X
,
Y
) will reach its maximum value at m when X
≺
Y(
3
) If d
X
,
Y
=
m, then X
≺
Yor X
=
Y


## 2.1.2. Dominance Degree Matrix

LetP
=
Y
1
,
Y
2
,
.
.
.
,
Y
N be a N objective vectors set, Y
i
=
(
y
1
i
,
y
2
i
,
.
.
.
,
y
m
i
)
T
∈
R
m, and (
i
=
1,2
,
.
.
.
,
N
) is a m dimensional vector. Define the dominance degree matrix D
=
(
d
i
j
)
N
×
N on the set P for the dominance relation by (2)
d
i
j
=
d
Y
i
,
Y
j
,
i
,
j
∈
1,2
,
…
,
N
.A faster method for calculating the dominance degree matrix follows the following two main steps:(
1
) Sort the objective vectors on every objective by using Quicksort [36].(
2
) Construct the dominance degree matrix by using the sorted results acquired in step (
1
).Firstly, we construct the comparison matrix of a row vectorr
=
(
r
1
,
r
2
,
.
.
.
,
r
N
)
∈
R
N and define the comparison matrix C
r
=
(
c
i
j
)
N
×
N of r by(3)
c
i
j
=
1
,
r
i
≤
r
j
,
0
,
otherwise
.One can see Algorithm 1 in literature [35] to calculate the matrix C
r.Secondly, sum the comparison matrices of each objective vector and then we can obtain the dominance degree matrix of a set of vectors. One can see Algorithm 2 in literature [35] for the details of this procedure.Finally, a novel nondominated sorting method is provided in the following paragraph, in which the dominance degree matrix is utilized to assign the solutions to nondominated fronts in the populationP.As we know, nondominated sorting approach assigns all solutions in initial populationP to nondominated fronts F
i. The first front F
1 consists of the set of nondominated solutions in the initialized population P. The second front F
2 is the set of nondominated solutions in the remaining set P
-
F
1 (i.e., removes all solutions assigned to F
1 from the population P) and repeats the procedure for the subsequent fronts.Assume thatA
N
×
N denotes the dominance degree matrix of the population P of size N. In order to eliminate the influence of the same individuals, the corresponding elements of A are set to 0. Let m
a
x
(
A
) be a row vector which consists of the corresponding maximum elements from each column of A. It can be verified that, for any Y
i
≠
Y
j
∈
P, Y
i dominates Y
j if and only if d
Y
i
,
Y
j equals m. Then, the solutions corresponding to elements of m
a
x
(
A
) whose subscripts are less than m are nondominated solutions of P. These nondominated solutions were classified to the first front F
1. Then, delete the column and row vectors corresponding to F
1 from A and denote the remaining matrix by A
1. Then, continue the same procedure for matrix A
1 and obtain the second front F
2. Repeat such a process until all solutions are classified to F
i. Thus, a new nondominated sorting method is attained, which is provided in Algorithm 3 of literature [35].The time complexity of the DDA-NS approach isO
(
m
N
2
). By using the DDA-NS approach, the complexity to compare the objective function values of nondominated sorting process in the NSGA-II can be reduced from O
(
m
N
2
) to O
(
m
N
log
⁡
N
) at iteration of the NSGA-II algorithm.


## 2.2. Part and Select Algorithm (PSA)

The Part and Select Algorithm (PSA) was put forward by S. Salomon et al. [27]. In this part we will make a brief introduction of the Part and Select Algorithm (PSA) which aims to select the well-spread points from a set of A (contains n candidate solutions). The procedure contains two main steps.Step 1.
DivideA into m subsets, so that the similar members can be grouped in the same subset.Step 2.
Each diverse subset is constructed through selecting one member from each generated subset.
To divide a set intok subsets, PSA carry on k
-
1 divisions of one set into two subsets. In each dividing process, the set with the greatest dissimilarity among whole elements is divided. The same procedure is continued until the desired stopping criterion is met. The desired stopping criterion can be either a predefined number of subsets or a maximal dissimilarity among each of the subsets. The dissimilarity of the set A is the measure ϕ
A.LetA
=
f
i
=
[
f
i
1
,
.
.
.
,
f
i
m
]
⊂
R
m (n objective vector f
i
=
F
(
x
i
) for points x
i
∈
Q) and denote(4)
a
j
≔
min
i
=
1
,
…
,
n
⁡
f
i
j
b
j
≔
max
i
=
1
,
…
,
n
⁡
f
i
j
Δ
j
≔
b
j
-
a
j
,
j
=
1
,
…
m
(5)
ϕ
A
≔
max
i
=
1
,
…
,
m
⁡
Δ
jObviously, a largerϕ
A indicates a greater dissimilarity among the members of A. The pseudocode of PSA originates from Algorithm 1 in literature [27].After the setA has been divided into the k subsets A
1
,
.
.
.
,
A
k, choose the member closest to the center of the hyperrectangle circumscribing A
i in the sense of Euclidean metric. If there exist more than one member closest to the center, chose one of them randomly. Let A
=
(
f
1
,
.
.
.
,
f
n
)
⊂
R
m be the original set of n members, from which a subset of k members is to be selected. The complexity of this selecting approach is O
(
m
n
k
).Proposition 1 (see [27]).
Given a setA
=
(
f
1
,
.
.
.
,
f
n
)
⊂
R
m, the overall complexity of choosing k
≤
n elements out of A using PSA and the center point selection is O
(
m
n
k
).


## 3. Improved NSGA-II

NSGA-II is widely applied for solving multiobjective problems (MOPs) [27–30]. However, its nondominated sorting approach usually has high computational overhead and the finalPareto approximate set is lack of diversity. For these considerations, this paper proposed a variant of NSGA-II algorithm. We denote this improved algorithm by DNSGA2-PSA which takes NSGA-II as the framework and retains the NSGA-II elitist-preserving approach, the crowding distance mechanism, and the binary tournament selection. After the population initialized, rank the population by DDA-NS and then calculate the individual’s crowded distance in each layer by PSA, so as to reduce the running time of the nondominated sorting and keep the initial solutions well-distributed. When the parent and offspring populations merged, PSA is used to prune population size instead of crowding comparison operator. Specific changes are as follows.


### 3.1. Modifying the Nondominated Sorting of NSGA-II

DDA-NS is integrated into the classical NSGA-II to replace fast nondominated sorting method. We assume that the current populationP
t of the size N be sorted by DDA-NS. Firstly, we use Algorithm 2 in literature [35] to calculate the dominance degree matrix of the current population P
t, donated as D
N
×
N and then set it as input to Algorithm 3 in literature [35]. Further, the nondominated front F
=
F
1
,
F
2
,
.
.
. is putted out.


### 3.2. Integration of PSA into NSGA-II

Because of the minimal requirements of PSA, the algorithm can be integrated into any MOEA and used as a selection mechanism and/or as a crowding assignment mechanism. So, the purpose is to utilize the high competency of PSA to select a diversified subset from an arbitrary set for enhancing diversity along the Pareto front. The difference between DNSGA2-PSA and the classical NSGA-II is that, instead of selectingm members from the last front F
l according to the crowded-comparison operator, selection is according to PSA. That is, assume that the combined current population R
t
=
P
t
∪
Q
t of the size2N is sorted to the nondominated fronts F
1
,
.
.
.
,
F
l
,
.
.
. and F
1
+
.
.
.
+
F
l
-
1
=
s
<
N and F
1
+
.
.
.
+
F
l
>
N. Then the next parent population P
t is constructed from the members of the sets F
1
,
.
.
.
,
F
l
-
1
,
.
.
. and from N
-
s members of the set F
l. The only difference from the classical NSGA-II is that, instead of selecting N
-
s members from the last front F
l according to the crowded-comparison operator ≺
n, selection is according to the PSA, as follows. The last front F
l is partitioned to m subsets according to Algorithm 1 in literature [27], and the central element of each subset is chosen to P
t
+
1. Besides, the crowding assignment of NSGA-II, used for the binary tournament, is modified as well. Each set F
i
,
i
=
1
,
.
.
.
l, is partitioned according to Algorithm 1 of literature [27] into F
i
/
2 subsets, and every member of F
i is assigned a crowding measure equal to the number of members in its subset.


### 3.3. DNSGA2-PSA Algorithm

The DNSGA2-PSA is formed by integrating existing NSGA-II with DDA-NS and PSA. The procedure of the DNSGA2-PSA is depicted in Algorithm1.Algorithm 1:Main steps of DNSGA2-PSA.
(
1
) Initial population P
t
(
2
) Assign the solutions Y
i
∈
P
t to fronts F
1
,
.
.
.
,
F
l
,
.
.
. by DDA-NS //Algorithm
3
originates from ([35], Algorithm
1
: DDA-NS)
(
3
) Calculate the crowded distance in each layer by PSA // Algorithm
1  originates from
([27], Algorithm
1:Partitioning a set A into m subsets)
(
4
) Parent population P
t
′
←binary tournament selectin of P
t
(
5
) Offspring population Q
t
←genetic operators (simulated binary crossover and polynomial mutation) of P
t
′
(
6
) Recombination population R
t
=
P
t
′
∪
Q
t
(
7
) The next generation population P
t
+
1
←select the recombination population R
t by PSA //Algorithm
1
originates from
([27], Algorithm
1
:Partitioning a set A into m subsets)


## 3.1. Modifying the Nondominated Sorting of NSGA-II

DDA-NS is integrated into the classical NSGA-II to replace fast nondominated sorting method. We assume that the current populationP
t of the size N be sorted by DDA-NS. Firstly, we use Algorithm 2 in literature [35] to calculate the dominance degree matrix of the current population P
t, donated as D
N
×
N and then set it as input to Algorithm 3 in literature [35]. Further, the nondominated front F
=
F
1
,
F
2
,
.
.
. is putted out.


## 3.2. Integration of PSA into NSGA-II

Because of the minimal requirements of PSA, the algorithm can be integrated into any MOEA and used as a selection mechanism and/or as a crowding assignment mechanism. So, the purpose is to utilize the high competency of PSA to select a diversified subset from an arbitrary set for enhancing diversity along the Pareto front. The difference between DNSGA2-PSA and the classical NSGA-II is that, instead of selectingm members from the last front F
l according to the crowded-comparison operator, selection is according to PSA. That is, assume that the combined current population R
t
=
P
t
∪
Q
t of the size2N is sorted to the nondominated fronts F
1
,
.
.
.
,
F
l
,
.
.
. and F
1
+
.
.
.
+
F
l
-
1
=
s
<
N and F
1
+
.
.
.
+
F
l
>
N. Then the next parent population P
t is constructed from the members of the sets F
1
,
.
.
.
,
F
l
-
1
,
.
.
. and from N
-
s members of the set F
l. The only difference from the classical NSGA-II is that, instead of selecting N
-
s members from the last front F
l according to the crowded-comparison operator ≺
n, selection is according to the PSA, as follows. The last front F
l is partitioned to m subsets according to Algorithm 1 in literature [27], and the central element of each subset is chosen to P
t
+
1. Besides, the crowding assignment of NSGA-II, used for the binary tournament, is modified as well. Each set F
i
,
i
=
1
,
.
.
.
l, is partitioned according to Algorithm 1 of literature [27] into F
i
/
2 subsets, and every member of F
i is assigned a crowding measure equal to the number of members in its subset.


## 3.3. DNSGA2-PSA Algorithm

The DNSGA2-PSA is formed by integrating existing NSGA-II with DDA-NS and PSA. The procedure of the DNSGA2-PSA is depicted in Algorithm1.Algorithm 1:Main steps of DNSGA2-PSA.
(
1
) Initial population P
t
(
2
) Assign the solutions Y
i
∈
P
t to fronts F
1
,
.
.
.
,
F
l
,
.
.
. by DDA-NS //Algorithm
3
originates from ([35], Algorithm
1
: DDA-NS)
(
3
) Calculate the crowded distance in each layer by PSA // Algorithm
1  originates from
([27], Algorithm
1:Partitioning a set A into m subsets)
(
4
) Parent population P
t
′
←binary tournament selectin of P
t
(
5
) Offspring population Q
t
←genetic operators (simulated binary crossover and polynomial mutation) of P
t
′
(
6
) Recombination population R
t
=
P
t
′
∪
Q
t
(
7
) The next generation population P
t
+
1
←select the recombination population R
t by PSA //Algorithm
1
originates from
([27], Algorithm
1
:Partitioning a set A into m subsets)


## 4. Computational Experiments and Performance Comparison

To demonstrate the scalability of the DDA-NS method and PSA, the experiments were conducted to compare the proposed DNSGA2-PSA with the NSGA2-PSA, along withN
S
G
A
-
I
I
D
D
A
-
N
S in this part. Both algorithms are tested on the following benchmark functions and evaluated by the following performance criteria. All experiments were implemented on a system with the following specifications.


### 4.1. Benchmark Function

Example 2 (DTLZ1, [37]).
(6)
min
⁡
f
1
X
=
1
2
x
1
x
2
…
x
M
-
1
1
+
g
X
M
min
⁡
f
2
X
=
1
2
x
1
x
2
…
1
-
x
M
-
1
1
+
g
X
M
⋮
min
⁡
f
M
X
=
1
2
1
-
x
1
1
+
g
X
M
g
X
M
=
100
X
M
+
∑
x
i
∈
X
M
x
i
-
0.5
2
-
cos
⁡
20
π
x
i
-
0.5where M
=
3, n
=
7, 0
≤
x
i
≤
1
(
i
=
1,2
,
.
.
.
,
n
), and the realPareto front is linear hyperplane ∑
m
=
1
M
f
m
=
0.5.Example 3 (DTLZ2, [37]).
(7)
min
⁡
f
1
X
=
1
+
g
X
M
cos
⁡
0.5
x
1
π
…
cos
⁡
0.5
x
M
-
2
π
cos
⁡
0.5
x
M
-
1
π
min
⁡
f
2
X
=
1
+
g
X
M
cos
⁡
0.5
x
1
π
…
cos
⁡
0.5
x
M
-
2
π
sin
⁡
0.5
x
M
-
1
π
⋮
min
⁡
f
M
X
=
1
2
1
+
g
X
M
sin
⁡
0.5
x
1
π
g
X
M
=
∑
x
i
∈
X
M
x
i
-
0.5
2where M
=
3, n
=
12
,
0
≤
x
i
≤
1
(
i
=
1,2
,
.
.
.
,
n
), and the realPareto front is nonconvex and formed with ∑
i
=
1
M
(
f
i
∗
)
2
=
1.Example 4 (DTLZ3, [37]).
(8)
min
⁡
f
1
X
=
1
+
g
X
M
cos
⁡
0.5
x
1
π
…
cos
⁡
0.5
x
M
-
2
π
cos
⁡
0.5
x
M
-
1
π
min
⁡
f
2
X
=
1
+
g
X
M
cos
⁡
0.5
x
1
π
…
cos
⁡
0.5
x
M
-
2
π
sin
⁡
0.5
x
M
-
1
π
⋮
min
⁡
f
M
X
=
1
2
1
+
g
X
M
sin
⁡
0.5
x
1
π
g
X
M
=
100
X
M
+
∑
x
i
∈
X
M
x
i
-
0.5
2
-
cos
⁡
20
π
x
i
-
0.5where M
=
3, n
=
12
,
0
≤
x
i
≤
1
,
i
=
1,2
,
.
.
.
,
n, and the realPareto front(at g
∗
=
0) is nonconvex.Example 5 (DTLZ4, [37]).
(9)
min
⁡
f
1
X
=
1
+
g
X
M
cos
⁡
0.5
x
1
100
π
…
cos
⁡
0.5
x
M
-
2
100
π
cos
⁡
0.5
x
M
-
1
100
π
min
⁡
f
2
X
=
1
+
g
X
M
cos
⁡
0.5
x
1
100
π
…
cos
⁡
0.5
x
M
-
2
100
π
sin
⁡
0.5
x
M
-
1
100
π
⋮
min
⁡
f
M
X
=
1
2
1
+
g
X
M
sin
⁡
0.5
x
1
100
π
g
X
M
=
∑
x
i
∈
X
M
x
i
-
0.5
2where M
=
3, n
=
12
,
0
≤
x
i
≤
1
(
i
=
1,2
,
.
.
.
,
n
), and the realPareto front is nonconvex and formed with ∑
f
i
2
=
1
,
i
=
1
,
.
.
.
,
M.
The Pareto optimal front of DTLZ1 is the hyperplane of all points that satisfy the equation∑
f
i
=
0.5
,
i
=
1
,
.
.
.
M, where M is the number of objectives. The PF of DTLZ2-4 is the hypersphere of all points that satisfy the equation ∑
f
i
2
=
1
,
i
=
1
,
.
.
.
M. DTLZ3 uses the same function for convergence as in DTLZ1, and therefore it can check the ability of a MOEA to find solutions close to the real PF. A very small section in the decision space is mapped to a very large section in the objective space of DTLZ4. This property makes it a good benchmark to test the ability of a MOEA to find a diverse set of solutions. Since the proposed DNSGA2-PSA aims to enhance the diversity of the approximated set, the results for the DTLZ4 are of major importance.


### 4.2. Performance Criteria

In the evaluation of multiobjective optimization algorithms, the convergence of the optimal solution set to the real Pareto optimal solution set and the uniform distribution of the optimal solution sets on the real Pareto solution set is considered. In this paper, four performance criteria are used to evaluate the convergence and the diversity of distribution of these algorithms.


#### 4.2.1. GD

Generation distance (GD) [38] is a way to estimate how far the elements produced by our algorithm are from those in the truePareto front of the problem. The measure is(10)
G
D
=
∑
i
=
1
n
d
i
2
nHere, n is the number of nondominated vectors found by the algorithm and d
i is theEuclidean metric between each of these vectors and the nearest member of the truePareto front.


#### 4.2.2. IGD

Inverted generational distance (IGD) [39] measure can indicate the overall quality of a solution set Q (i.e., its convergence to thePareto frontand diversity along thePareto front). IGD is defined by(11)
I
G
D
Z
,
Q
=
1
Z
∑
i
=
1
Z
min
j
=
1
Q
⁡
d
z
i
,
q
jHere d
(
z
i
,
q
j
) is a distance between z
i and q
j in the objective space. This paper uses theEuclidean distance as d
(
z
i
,
q
j
).The IGD in (11) is the average distance from each reference point z
i to its nearest solution in the solution set Q.


#### 4.2.3. HV

Hypervolume (HV) [40] is also known as the S measure or theLebesgue measure [41, 42]. The hypervolume of a set measures the size of the dominated portion of the objective space byPareto approximation set. HV is defined by(12)
S
A
≔
μ
⋃
a
∈
A
y
∈
Y
:
a
r
e
f
≺
y
≺
aHere A is the nondominated solution set, x is the decision vector, X is the decision space, y is the target vector, Y is the target space, and μ is theLebesgue measure, while a
r
e
f is the reference point.


#### 4.2.4. Spacing

Spacing [43] is evenness metric. Assume that A denotes the approximate Pareto optimal solution set obtained by our algorithm, and then Spacing is defined by(13)
S
=
1
A
-
1
∑
i
=
1
A
d
-
-
d
i
2
(14)
d
i
=
min
j
⁡
∑
m
=
1
k
f
m
a
i
-
f
m
a
j
a
i
,
a
j
∈
A
;
i
,
j
=
1,2
,
…
AHere d
- is the mean of d
i, and k is the number of objective functions. If the value of Spacing equals zero, it indicates that the obtained nondominated solution is evenness in the target space.


### 4.3. Discussion of the Results

In this section, the DNSGA2-PSA is compared with theN
S
G
A
-
I
I
D
D
A
-
N
S, along with NSGA2-PSA. For a fair comparison, both algorithms start with the same initial population at every test and use the same genetic settings. In this paper, we employ a binary tournament selection operator, a polynomial mutation operator, and a real-parameter simulated binary crossover operator to construct the genetic operators. The mutation probability of p
m
=
1
/
n and crossover probability of p
c
=
0.9 are used. For real-coded NSGA, the distribution indexes for crossover and mutation operators are set to be η
c
=
20 and η
m
=
20, respectively. In the three algorithms, the maximum number of generations is set as 250; the population size is set as 100. The results of a typical approximated set can be seen for three objectives in Figure 1; the statistical results for two to five objectives are shown in Figures 2 and 3.Figure 1
The final approximated set obtained byN
S
G
A
-
I
I
D
D
A
-
N
S and DNSGA2-PSA on Examples 2–5.
(a)
Example2 _DTLZ1
(b)
Example3 _DTLZ2
(c)
Example4 _DTLZ3
(d)
Example5 _DTLZ4Figure 2
Box plots of results from 30 independent runs of NSGA2-PSA, DNSGA2-PSA, andN
S
G
A
-
I
I
D
D
A
-
N
S (from left to right) on the DTLZ1-4 test cases for two and three objectives, respectively.
(a)
GD results for two objectives
(b)
GD results for three objectives
(c)
IGD results for two objectives
(d)
IGD results for three objectives
(e)
HV results for two objectives
(f)
HV results for three objectives
(g)
Spacing results for two objectives
(h)
Spacing results for three objectivesFigure 3
Box plots of results from 30 independent runs of NSGA2-PSA, DNSGA2-PSA, andN
S
G
A
-
I
I
D
D
A
-
N
S (from left to right) on the DTLZ1-4 test cases for four and five objectives, respectively.
(a)
GD results for four objectives
(b)
GD results for five objectives
(c)
IGD results for four objectives
(d)
IGD results for five objectives
(e)
HV results for four objectives
(f)
HV results for five objectives
(g)
Spacing results for four objectives
(h)
Spacing results for five objectivesWe discuss the effectiveness of DNSGA2-PSA in terms of the following aspects.


#### 4.3.1. Computational Cost

Intuitively, as we can see from Table1, the execution time of DNSGA2-PSA is less than NSGA2-PSA but more than N
S
G
A
-
I
I
D
D
A
-
N
S for DTLZ1-4, which shows the superiority of the DDA-NS approach. Accordingly, the DDA-NS approach is demonstrated to outperform the original NSGA-II whose framework embedding the fast nondominated sorting approaches in terms of running time.Table 1
Compare the mean execution time and standard deviation results for four test functions.
Runtime(s)
DNSGAII-PSA
N
S
G
A
-
I
I
D
D
A
-
N
S
NSGA2-PSA
DTLZ1
82.8436±2.5913
41.7521± 3.3535
395.4527±3.5630
DTLZ2
88.9393±1.2915
42.0592±2.6453
396.8257±2.6019
DTLZ3
89.9203±3.4223
47.8723±3.2109
408.3502±3.5452
DTLZ4
87.6524±3.3539
45.2425±4.6275
398.2296±2.2497


#### 4.3.2. Convergence and Diversity

As we know, GD means the convergence of the algorithm; IGD provides information about both convergence and diversity of the approximated set. Smaller values of the GD and IGD are preferred. With respect to the DTLZ1-4, Tables2 and 3 reflect that the GD and IGD values of DNSGA2-PSA are always better than that of N
S
G
A
-
I
I
D
D
A
-
N
S. In both aspects of convergence and diversity of solutions, DNSGA2-PSA performs better than N
S
G
A
-
I
I
D
D
A
-
N
S in these test problems. With regard to comprehensive performance, DNSGA2-PSA is better than N
S
G
A
-
I
I
D
D
A
-
N
S.Table 2
Comparison of GD mean and standard deviation between our approach (denoted by DNSGA2-PSA), NSGA2-PSA, andN
S
G
A
-
I
I
D
D
A
-
N
S, for four test functions.
GD
DNSGA2-PSA
NSGA2-PSA
N
S
G
A
-
I
I
D
D
A
-
N
S
DTLZ1
4.7125e-04±2.3316e-05
4.6890e-04±4.1349e-05
5.6233e-04±4.4749e-05
DTLZ2
4.2343e-04±6.2219e-05
4.2263e-04±2.2339e-05
4.8921e-04±8.2429e-05
DTLZ3
3.7908e-04±7.2873e-05
3.8104e-04±5.8342e-05
4.7813e-04±4.4758e-05
DTLZ4
3.6495e-04±1.2377e-05
3.7920e-04±5.2339e-05
4.9249e-04±7.2519e-05Table 3
Comparison of IGD mean and standard deviation between our approach (denoted by DNSGA2-PSA), NSGA2-PSA, andN
S
G
A
-
I
I
D
D
A
-
N
S, for four test functions.
IGD
DNSGA2-PSA
NSGA2-PSA
N
S
G
A
-
I
I
D
D
A
-
N
S
DTLZ1
3.2745e-03±4.2545e-04
3.1232e-03±7.3396e-05
3.7982e-03±5.2536e-04
DTLZ2
3.4822e-03±5.7713e-05
3.5746 e-03±4.3576e-04
4.2834 e-03±7.5576e-04
DTLZ3
4.6440e-03±2.3459e-04
4.6629e-03±3.3236e-04
4.9624 e-03±4.8346e-04
DTLZ4
5.3955 e-03±2.3391e-04
5.2483 e-03±8.3676e-05
6.3581 e-03±3.3711e-04Table4 is the results of HV measure. A higher value of HV is associated with a good spread and convergence. Based on the results shown in Table 4, we can conclude that our algorithm (DNSGA2-PSA) obtains the best results, with the largest HV (on average). Also, we can say that the DNSGA2-PSA is relatively better than the N
S
G
A
-
I
I
D
D
A
-
N
S algorithms.Table 4
Comparison of HV mean and standard deviation between our approach (denoted by DNSGA2-PSA), NSGA2-PSA, andN
S
G
A
-
I
I
D
D
A
-
N
S, for four test functions.
HV
DNSGA2-PSA
NSGA2-PSA
N
S
G
A
-
I
I
D
D
A
-
N
S
DTLZ1
7.3037e-01±1.3556e-03
7.3113e-01±2.3921e-03
6.8817e-01±2.5359e-03
DTLZ2
6.8715e-01±2.1701e-03
6.6455e-01±5.1771e-02
5.5013e-01±7.1321e-03
DTLZ3
7.0915e-01±1.6023e-02
7.2915e-01±2.1301e-02
6.2915e-01±4.8001e-02
DTLZ4
6.35425e-01±4.0491e-02
6.7545e-01±8.1201e-04
5.3066e-01±5.1508e-02As we know, Spacing provides information about diversity of the approximated set and smaller value of the Spacing is preferred. As can be seen from Table5, the index of diversity is better than NSGA-IIDDA-NS but roughly equivalent as NSGA2-PSA. So, we can conclude that DNSGA2-PSA algorithm has a great advantage in promoting diversity.Table 5
Comparison of Spacing mean and standard deviation between our approach (denoted by DNSGA2-PSA), NSGA2-PSA, andN
S
G
A
-
I
I
D
D
A
-
N
S, for four test functions.
Spacing
DNSGA2-PSA
NSGA2-PSA
N
S
G
A
-
I
I
D
D
A
-
N
S
DTLZ1
1.1037e-01±1.4766e-03
1.1173e-01±1.9301e-03
2.1817e-01±2.8859e-03
DTLZ2
1.2681e-01±2.0713e-03
1.2455e-01±2.1915e-03
2.1013e-01±7.3851e-03
DTLZ3
1.0915e-01±1.7208e-03
1.2915e-01±2.1435e-03
2.0915e-00±4.6301e-02
DTLZ4
1.1654e-01±1.0491e-02
1.2545e-01±7.1371e-03
2.0066e-01±5.6728e-02For two to five objectives of DTLZ series, the boxplot of GD, IGD, HV, and Spacing are depicted in Figures2 and 3, respectively. We can conclude that the IGD, HV, and Spacing values of DNSGA2-PSA are better than N
S
G
A
-
I
I
D
D
A
-
N
S. However, as the number of objective functions increases, this advantage comes at the cost of a loss of proximity, as manifested in larger GD value of DNSGA2-PSA. Then the unresolved tradeoff between diversity and proximity emerges. The higher HV and smaller Spacing of DNSGA2-PSA indicate that the gain in diversity is more significant than the loss of proximity.


#### 4.3.3. Overall Evaluation

Through the group of experiments, it has been shown that the proposed modified DNSGA2-PSA is clearly superior compared with theN
S
G
A
-
I
I
D
D
A
-
N
S and NSGA2-PSA, especially generating relatively diverse nondominated set and reducing the running time sharply. This illustrates the effectiveness of the mechanisms adopted in our DDA-NS and PSA approach to maintain diversity and reduce runtime.


## 4.1. Benchmark Function

Example 2 (DTLZ1, [37]).
(6)
min
⁡
f
1
X
=
1
2
x
1
x
2
…
x
M
-
1
1
+
g
X
M
min
⁡
f
2
X
=
1
2
x
1
x
2
…
1
-
x
M
-
1
1
+
g
X
M
⋮
min
⁡
f
M
X
=
1
2
1
-
x
1
1
+
g
X
M
g
X
M
=
100
X
M
+
∑
x
i
∈
X
M
x
i
-
0.5
2
-
cos
⁡
20
π
x
i
-
0.5where M
=
3, n
=
7, 0
≤
x
i
≤
1
(
i
=
1,2
,
.
.
.
,
n
), and the realPareto front is linear hyperplane ∑
m
=
1
M
f
m
=
0.5.Example 3 (DTLZ2, [37]).
(7)
min
⁡
f
1
X
=
1
+
g
X
M
cos
⁡
0.5
x
1
π
…
cos
⁡
0.5
x
M
-
2
π
cos
⁡
0.5
x
M
-
1
π
min
⁡
f
2
X
=
1
+
g
X
M
cos
⁡
0.5
x
1
π
…
cos
⁡
0.5
x
M
-
2
π
sin
⁡
0.5
x
M
-
1
π
⋮
min
⁡
f
M
X
=
1
2
1
+
g
X
M
sin
⁡
0.5
x
1
π
g
X
M
=
∑
x
i
∈
X
M
x
i
-
0.5
2where M
=
3, n
=
12
,
0
≤
x
i
≤
1
(
i
=
1,2
,
.
.
.
,
n
), and the realPareto front is nonconvex and formed with ∑
i
=
1
M
(
f
i
∗
)
2
=
1.Example 4 (DTLZ3, [37]).
(8)
min
⁡
f
1
X
=
1
+
g
X
M
cos
⁡
0.5
x
1
π
…
cos
⁡
0.5
x
M
-
2
π
cos
⁡
0.5
x
M
-
1
π
min
⁡
f
2
X
=
1
+
g
X
M
cos
⁡
0.5
x
1
π
…
cos
⁡
0.5
x
M
-
2
π
sin
⁡
0.5
x
M
-
1
π
⋮
min
⁡
f
M
X
=
1
2
1
+
g
X
M
sin
⁡
0.5
x
1
π
g
X
M
=
100
X
M
+
∑
x
i
∈
X
M
x
i
-
0.5
2
-
cos
⁡
20
π
x
i
-
0.5where M
=
3, n
=
12
,
0
≤
x
i
≤
1
,
i
=
1,2
,
.
.
.
,
n, and the realPareto front(at g
∗
=
0) is nonconvex.Example 5 (DTLZ4, [37]).
(9)
min
⁡
f
1
X
=
1
+
g
X
M
cos
⁡
0.5
x
1
100
π
…
cos
⁡
0.5
x
M
-
2
100
π
cos
⁡
0.5
x
M
-
1
100
π
min
⁡
f
2
X
=
1
+
g
X
M
cos
⁡
0.5
x
1
100
π
…
cos
⁡
0.5
x
M
-
2
100
π
sin
⁡
0.5
x
M
-
1
100
π
⋮
min
⁡
f
M
X
=
1
2
1
+
g
X
M
sin
⁡
0.5
x
1
100
π
g
X
M
=
∑
x
i
∈
X
M
x
i
-
0.5
2where M
=
3, n
=
12
,
0
≤
x
i
≤
1
(
i
=
1,2
,
.
.
.
,
n
), and the realPareto front is nonconvex and formed with ∑
f
i
2
=
1
,
i
=
1
,
.
.
.
,
M.
The Pareto optimal front of DTLZ1 is the hyperplane of all points that satisfy the equation∑
f
i
=
0.5
,
i
=
1
,
.
.
.
M, where M is the number of objectives. The PF of DTLZ2-4 is the hypersphere of all points that satisfy the equation ∑
f
i
2
=
1
,
i
=
1
,
.
.
.
M. DTLZ3 uses the same function for convergence as in DTLZ1, and therefore it can check the ability of a MOEA to find solutions close to the real PF. A very small section in the decision space is mapped to a very large section in the objective space of DTLZ4. This property makes it a good benchmark to test the ability of a MOEA to find a diverse set of solutions. Since the proposed DNSGA2-PSA aims to enhance the diversity of the approximated set, the results for the DTLZ4 are of major importance.


## 4.2. Performance Criteria

In the evaluation of multiobjective optimization algorithms, the convergence of the optimal solution set to the real Pareto optimal solution set and the uniform distribution of the optimal solution sets on the real Pareto solution set is considered. In this paper, four performance criteria are used to evaluate the convergence and the diversity of distribution of these algorithms.


### 4.2.1. GD

Generation distance (GD) [38] is a way to estimate how far the elements produced by our algorithm are from those in the truePareto front of the problem. The measure is(10)
G
D
=
∑
i
=
1
n
d
i
2
nHere, n is the number of nondominated vectors found by the algorithm and d
i is theEuclidean metric between each of these vectors and the nearest member of the truePareto front.


### 4.2.2. IGD

Inverted generational distance (IGD) [39] measure can indicate the overall quality of a solution set Q (i.e., its convergence to thePareto frontand diversity along thePareto front). IGD is defined by(11)
I
G
D
Z
,
Q
=
1
Z
∑
i
=
1
Z
min
j
=
1
Q
⁡
d
z
i
,
q
jHere d
(
z
i
,
q
j
) is a distance between z
i and q
j in the objective space. This paper uses theEuclidean distance as d
(
z
i
,
q
j
).The IGD in (11) is the average distance from each reference point z
i to its nearest solution in the solution set Q.


### 4.2.3. HV

Hypervolume (HV) [40] is also known as the S measure or theLebesgue measure [41, 42]. The hypervolume of a set measures the size of the dominated portion of the objective space byPareto approximation set. HV is defined by(12)
S
A
≔
μ
⋃
a
∈
A
y
∈
Y
:
a
r
e
f
≺
y
≺
aHere A is the nondominated solution set, x is the decision vector, X is the decision space, y is the target vector, Y is the target space, and μ is theLebesgue measure, while a
r
e
f is the reference point.


### 4.2.4. Spacing

Spacing [43] is evenness metric. Assume that A denotes the approximate Pareto optimal solution set obtained by our algorithm, and then Spacing is defined by(13)
S
=
1
A
-
1
∑
i
=
1
A
d
-
-
d
i
2
(14)
d
i
=
min
j
⁡
∑
m
=
1
k
f
m
a
i
-
f
m
a
j
a
i
,
a
j
∈
A
;
i
,
j
=
1,2
,
…
AHere d
- is the mean of d
i, and k is the number of objective functions. If the value of Spacing equals zero, it indicates that the obtained nondominated solution is evenness in the target space.


## 4.2.1. GD

Generation distance (GD) [38] is a way to estimate how far the elements produced by our algorithm are from those in the truePareto front of the problem. The measure is(10)
G
D
=
∑
i
=
1
n
d
i
2
nHere, n is the number of nondominated vectors found by the algorithm and d
i is theEuclidean metric between each of these vectors and the nearest member of the truePareto front.


## 4.2.2. IGD

Inverted generational distance (IGD) [39] measure can indicate the overall quality of a solution set Q (i.e., its convergence to thePareto frontand diversity along thePareto front). IGD is defined by(11)
I
G
D
Z
,
Q
=
1
Z
∑
i
=
1
Z
min
j
=
1
Q
⁡
d
z
i
,
q
jHere d
(
z
i
,
q
j
) is a distance between z
i and q
j in the objective space. This paper uses theEuclidean distance as d
(
z
i
,
q
j
).The IGD in (11) is the average distance from each reference point z
i to its nearest solution in the solution set Q.


## 4.2.3. HV

Hypervolume (HV) [40] is also known as the S measure or theLebesgue measure [41, 42]. The hypervolume of a set measures the size of the dominated portion of the objective space byPareto approximation set. HV is defined by(12)
S
A
≔
μ
⋃
a
∈
A
y
∈
Y
:
a
r
e
f
≺
y
≺
aHere A is the nondominated solution set, x is the decision vector, X is the decision space, y is the target vector, Y is the target space, and μ is theLebesgue measure, while a
r
e
f is the reference point.


## 4.2.4. Spacing

Spacing [43] is evenness metric. Assume that A denotes the approximate Pareto optimal solution set obtained by our algorithm, and then Spacing is defined by(13)
S
=
1
A
-
1
∑
i
=
1
A
d
-
-
d
i
2
(14)
d
i
=
min
j
⁡
∑
m
=
1
k
f
m
a
i
-
f
m
a
j
a
i
,
a
j
∈
A
;
i
,
j
=
1,2
,
…
AHere d
- is the mean of d
i, and k is the number of objective functions. If the value of Spacing equals zero, it indicates that the obtained nondominated solution is evenness in the target space.


## 4.3. Discussion of the Results

In this section, the DNSGA2-PSA is compared with theN
S
G
A
-
I
I
D
D
A
-
N
S, along with NSGA2-PSA. For a fair comparison, both algorithms start with the same initial population at every test and use the same genetic settings. In this paper, we employ a binary tournament selection operator, a polynomial mutation operator, and a real-parameter simulated binary crossover operator to construct the genetic operators. The mutation probability of p
m
=
1
/
n and crossover probability of p
c
=
0.9 are used. For real-coded NSGA, the distribution indexes for crossover and mutation operators are set to be η
c
=
20 and η
m
=
20, respectively. In the three algorithms, the maximum number of generations is set as 250; the population size is set as 100. The results of a typical approximated set can be seen for three objectives in Figure 1; the statistical results for two to five objectives are shown in Figures 2 and 3.Figure 1
The final approximated set obtained byN
S
G
A
-
I
I
D
D
A
-
N
S and DNSGA2-PSA on Examples 2–5.
(a)
Example2 _DTLZ1
(b)
Example3 _DTLZ2
(c)
Example4 _DTLZ3
(d)
Example5 _DTLZ4Figure 2
Box plots of results from 30 independent runs of NSGA2-PSA, DNSGA2-PSA, andN
S
G
A
-
I
I
D
D
A
-
N
S (from left to right) on the DTLZ1-4 test cases for two and three objectives, respectively.
(a)
GD results for two objectives
(b)
GD results for three objectives
(c)
IGD results for two objectives
(d)
IGD results for three objectives
(e)
HV results for two objectives
(f)
HV results for three objectives
(g)
Spacing results for two objectives
(h)
Spacing results for three objectivesFigure 3
Box plots of results from 30 independent runs of NSGA2-PSA, DNSGA2-PSA, andN
S
G
A
-
I
I
D
D
A
-
N
S (from left to right) on the DTLZ1-4 test cases for four and five objectives, respectively.
(a)
GD results for four objectives
(b)
GD results for five objectives
(c)
IGD results for four objectives
(d)
IGD results for five objectives
(e)
HV results for four objectives
(f)
HV results for five objectives
(g)
Spacing results for four objectives
(h)
Spacing results for five objectivesWe discuss the effectiveness of DNSGA2-PSA in terms of the following aspects.


### 4.3.1. Computational Cost

Intuitively, as we can see from Table1, the execution time of DNSGA2-PSA is less than NSGA2-PSA but more than N
S
G
A
-
I
I
D
D
A
-
N
S for DTLZ1-4, which shows the superiority of the DDA-NS approach. Accordingly, the DDA-NS approach is demonstrated to outperform the original NSGA-II whose framework embedding the fast nondominated sorting approaches in terms of running time.Table 1
Compare the mean execution time and standard deviation results for four test functions.
Runtime(s)
DNSGAII-PSA
N
S
G
A
-
I
I
D
D
A
-
N
S
NSGA2-PSA
DTLZ1
82.8436±2.5913
41.7521± 3.3535
395.4527±3.5630
DTLZ2
88.9393±1.2915
42.0592±2.6453
396.8257±2.6019
DTLZ3
89.9203±3.4223
47.8723±3.2109
408.3502±3.5452
DTLZ4
87.6524±3.3539
45.2425±4.6275
398.2296±2.2497


### 4.3.2. Convergence and Diversity

As we know, GD means the convergence of the algorithm; IGD provides information about both convergence and diversity of the approximated set. Smaller values of the GD and IGD are preferred. With respect to the DTLZ1-4, Tables2 and 3 reflect that the GD and IGD values of DNSGA2-PSA are always better than that of N
S
G
A
-
I
I
D
D
A
-
N
S. In both aspects of convergence and diversity of solutions, DNSGA2-PSA performs better than N
S
G
A
-
I
I
D
D
A
-
N
S in these test problems. With regard to comprehensive performance, DNSGA2-PSA is better than N
S
G
A
-
I
I
D
D
A
-
N
S.Table 2
Comparison of GD mean and standard deviation between our approach (denoted by DNSGA2-PSA), NSGA2-PSA, andN
S
G
A
-
I
I
D
D
A
-
N
S, for four test functions.
GD
DNSGA2-PSA
NSGA2-PSA
N
S
G
A
-
I
I
D
D
A
-
N
S
DTLZ1
4.7125e-04±2.3316e-05
4.6890e-04±4.1349e-05
5.6233e-04±4.4749e-05
DTLZ2
4.2343e-04±6.2219e-05
4.2263e-04±2.2339e-05
4.8921e-04±8.2429e-05
DTLZ3
3.7908e-04±7.2873e-05
3.8104e-04±5.8342e-05
4.7813e-04±4.4758e-05
DTLZ4
3.6495e-04±1.2377e-05
3.7920e-04±5.2339e-05
4.9249e-04±7.2519e-05Table 3
Comparison of IGD mean and standard deviation between our approach (denoted by DNSGA2-PSA), NSGA2-PSA, andN
S
G
A
-
I
I
D
D
A
-
N
S, for four test functions.
IGD
DNSGA2-PSA
NSGA2-PSA
N
S
G
A
-
I
I
D
D
A
-
N
S
DTLZ1
3.2745e-03±4.2545e-04
3.1232e-03±7.3396e-05
3.7982e-03±5.2536e-04
DTLZ2
3.4822e-03±5.7713e-05
3.5746 e-03±4.3576e-04
4.2834 e-03±7.5576e-04
DTLZ3
4.6440e-03±2.3459e-04
4.6629e-03±3.3236e-04
4.9624 e-03±4.8346e-04
DTLZ4
5.3955 e-03±2.3391e-04
5.2483 e-03±8.3676e-05
6.3581 e-03±3.3711e-04Table4 is the results of HV measure. A higher value of HV is associated with a good spread and convergence. Based on the results shown in Table 4, we can conclude that our algorithm (DNSGA2-PSA) obtains the best results, with the largest HV (on average). Also, we can say that the DNSGA2-PSA is relatively better than the N
S
G
A
-
I
I
D
D
A
-
N
S algorithms.Table 4
Comparison of HV mean and standard deviation between our approach (denoted by DNSGA2-PSA), NSGA2-PSA, andN
S
G
A
-
I
I
D
D
A
-
N
S, for four test functions.
HV
DNSGA2-PSA
NSGA2-PSA
N
S
G
A
-
I
I
D
D
A
-
N
S
DTLZ1
7.3037e-01±1.3556e-03
7.3113e-01±2.3921e-03
6.8817e-01±2.5359e-03
DTLZ2
6.8715e-01±2.1701e-03
6.6455e-01±5.1771e-02
5.5013e-01±7.1321e-03
DTLZ3
7.0915e-01±1.6023e-02
7.2915e-01±2.1301e-02
6.2915e-01±4.8001e-02
DTLZ4
6.35425e-01±4.0491e-02
6.7545e-01±8.1201e-04
5.3066e-01±5.1508e-02As we know, Spacing provides information about diversity of the approximated set and smaller value of the Spacing is preferred. As can be seen from Table5, the index of diversity is better than NSGA-IIDDA-NS but roughly equivalent as NSGA2-PSA. So, we can conclude that DNSGA2-PSA algorithm has a great advantage in promoting diversity.Table 5
Comparison of Spacing mean and standard deviation between our approach (denoted by DNSGA2-PSA), NSGA2-PSA, andN
S
G
A
-
I
I
D
D
A
-
N
S, for four test functions.
Spacing
DNSGA2-PSA
NSGA2-PSA
N
S
G
A
-
I
I
D
D
A
-
N
S
DTLZ1
1.1037e-01±1.4766e-03
1.1173e-01±1.9301e-03
2.1817e-01±2.8859e-03
DTLZ2
1.2681e-01±2.0713e-03
1.2455e-01±2.1915e-03
2.1013e-01±7.3851e-03
DTLZ3
1.0915e-01±1.7208e-03
1.2915e-01±2.1435e-03
2.0915e-00±4.6301e-02
DTLZ4
1.1654e-01±1.0491e-02
1.2545e-01±7.1371e-03
2.0066e-01±5.6728e-02For two to five objectives of DTLZ series, the boxplot of GD, IGD, HV, and Spacing are depicted in Figures2 and 3, respectively. We can conclude that the IGD, HV, and Spacing values of DNSGA2-PSA are better than N
S
G
A
-
I
I
D
D
A
-
N
S. However, as the number of objective functions increases, this advantage comes at the cost of a loss of proximity, as manifested in larger GD value of DNSGA2-PSA. Then the unresolved tradeoff between diversity and proximity emerges. The higher HV and smaller Spacing of DNSGA2-PSA indicate that the gain in diversity is more significant than the loss of proximity.


### 4.3.3. Overall Evaluation

Through the group of experiments, it has been shown that the proposed modified DNSGA2-PSA is clearly superior compared with theN
S
G
A
-
I
I
D
D
A
-
N
S and NSGA2-PSA, especially generating relatively diverse nondominated set and reducing the running time sharply. This illustrates the effectiveness of the mechanisms adopted in our DDA-NS and PSA approach to maintain diversity and reduce runtime.


## 4.3.1. Computational Cost

Intuitively, as we can see from Table1, the execution time of DNSGA2-PSA is less than NSGA2-PSA but more than N
S
G
A
-
I
I
D
D
A
-
N
S for DTLZ1-4, which shows the superiority of the DDA-NS approach. Accordingly, the DDA-NS approach is demonstrated to outperform the original NSGA-II whose framework embedding the fast nondominated sorting approaches in terms of running time.Table 1
Compare the mean execution time and standard deviation results for four test functions.
Runtime(s)
DNSGAII-PSA
N
S
G
A
-
I
I
D
D
A
-
N
S
NSGA2-PSA
DTLZ1
82.8436±2.5913
41.7521± 3.3535
395.4527±3.5630
DTLZ2
88.9393±1.2915
42.0592±2.6453
396.8257±2.6019
DTLZ3
89.9203±3.4223
47.8723±3.2109
408.3502±3.5452
DTLZ4
87.6524±3.3539
45.2425±4.6275
398.2296±2.2497


## 4.3.2. Convergence and Diversity

As we know, GD means the convergence of the algorithm; IGD provides information about both convergence and diversity of the approximated set. Smaller values of the GD and IGD are preferred. With respect to the DTLZ1-4, Tables2 and 3 reflect that the GD and IGD values of DNSGA2-PSA are always better than that of N
S
G
A
-
I
I
D
D
A
-
N
S. In both aspects of convergence and diversity of solutions, DNSGA2-PSA performs better than N
S
G
A
-
I
I
D
D
A
-
N
S in these test problems. With regard to comprehensive performance, DNSGA2-PSA is better than N
S
G
A
-
I
I
D
D
A
-
N
S.Table 2
Comparison of GD mean and standard deviation between our approach (denoted by DNSGA2-PSA), NSGA2-PSA, andN
S
G
A
-
I
I
D
D
A
-
N
S, for four test functions.
GD
DNSGA2-PSA
NSGA2-PSA
N
S
G
A
-
I
I
D
D
A
-
N
S
DTLZ1
4.7125e-04±2.3316e-05
4.6890e-04±4.1349e-05
5.6233e-04±4.4749e-05
DTLZ2
4.2343e-04±6.2219e-05
4.2263e-04±2.2339e-05
4.8921e-04±8.2429e-05
DTLZ3
3.7908e-04±7.2873e-05
3.8104e-04±5.8342e-05
4.7813e-04±4.4758e-05
DTLZ4
3.6495e-04±1.2377e-05
3.7920e-04±5.2339e-05
4.9249e-04±7.2519e-05Table 3
Comparison of IGD mean and standard deviation between our approach (denoted by DNSGA2-PSA), NSGA2-PSA, andN
S
G
A
-
I
I
D
D
A
-
N
S, for four test functions.
IGD
DNSGA2-PSA
NSGA2-PSA
N
S
G
A
-
I
I
D
D
A
-
N
S
DTLZ1
3.2745e-03±4.2545e-04
3.1232e-03±7.3396e-05
3.7982e-03±5.2536e-04
DTLZ2
3.4822e-03±5.7713e-05
3.5746 e-03±4.3576e-04
4.2834 e-03±7.5576e-04
DTLZ3
4.6440e-03±2.3459e-04
4.6629e-03±3.3236e-04
4.9624 e-03±4.8346e-04
DTLZ4
5.3955 e-03±2.3391e-04
5.2483 e-03±8.3676e-05
6.3581 e-03±3.3711e-04Table4 is the results of HV measure. A higher value of HV is associated with a good spread and convergence. Based on the results shown in Table 4, we can conclude that our algorithm (DNSGA2-PSA) obtains the best results, with the largest HV (on average). Also, we can say that the DNSGA2-PSA is relatively better than the N
S
G
A
-
I
I
D
D
A
-
N
S algorithms.Table 4
Comparison of HV mean and standard deviation between our approach (denoted by DNSGA2-PSA), NSGA2-PSA, andN
S
G
A
-
I
I
D
D
A
-
N
S, for four test functions.
HV
DNSGA2-PSA
NSGA2-PSA
N
S
G
A
-
I
I
D
D
A
-
N
S
DTLZ1
7.3037e-01±1.3556e-03
7.3113e-01±2.3921e-03
6.8817e-01±2.5359e-03
DTLZ2
6.8715e-01±2.1701e-03
6.6455e-01±5.1771e-02
5.5013e-01±7.1321e-03
DTLZ3
7.0915e-01±1.6023e-02
7.2915e-01±2.1301e-02
6.2915e-01±4.8001e-02
DTLZ4
6.35425e-01±4.0491e-02
6.7545e-01±8.1201e-04
5.3066e-01±5.1508e-02As we know, Spacing provides information about diversity of the approximated set and smaller value of the Spacing is preferred. As can be seen from Table5, the index of diversity is better than NSGA-IIDDA-NS but roughly equivalent as NSGA2-PSA. So, we can conclude that DNSGA2-PSA algorithm has a great advantage in promoting diversity.Table 5
Comparison of Spacing mean and standard deviation between our approach (denoted by DNSGA2-PSA), NSGA2-PSA, andN
S
G
A
-
I
I
D
D
A
-
N
S, for four test functions.
Spacing
DNSGA2-PSA
NSGA2-PSA
N
S
G
A
-
I
I
D
D
A
-
N
S
DTLZ1
1.1037e-01±1.4766e-03
1.1173e-01±1.9301e-03
2.1817e-01±2.8859e-03
DTLZ2
1.2681e-01±2.0713e-03
1.2455e-01±2.1915e-03
2.1013e-01±7.3851e-03
DTLZ3
1.0915e-01±1.7208e-03
1.2915e-01±2.1435e-03
2.0915e-00±4.6301e-02
DTLZ4
1.1654e-01±1.0491e-02
1.2545e-01±7.1371e-03
2.0066e-01±5.6728e-02For two to five objectives of DTLZ series, the boxplot of GD, IGD, HV, and Spacing are depicted in Figures2 and 3, respectively. We can conclude that the IGD, HV, and Spacing values of DNSGA2-PSA are better than N
S
G
A
-
I
I
D
D
A
-
N
S. However, as the number of objective functions increases, this advantage comes at the cost of a loss of proximity, as manifested in larger GD value of DNSGA2-PSA. Then the unresolved tradeoff between diversity and proximity emerges. The higher HV and smaller Spacing of DNSGA2-PSA indicate that the gain in diversity is more significant than the loss of proximity.


## 4.3.3. Overall Evaluation

Through the group of experiments, it has been shown that the proposed modified DNSGA2-PSA is clearly superior compared with theN
S
G
A
-
I
I
D
D
A
-
N
S and NSGA2-PSA, especially generating relatively diverse nondominated set and reducing the running time sharply. This illustrates the effectiveness of the mechanisms adopted in our DDA-NS and PSA approach to maintain diversity and reduce runtime.


## 5. Conclusion

To reduce the execution time and enhance the exploitation of diversity of NSGA-II, this paper has discussed the combination of a new vector ranking scheme and diversity preserving selection with NSGA-II algorithm. The new vector ranking scheme produces a new data structure, namely, the dominance degree matrix. Using the dominance degree matrix, a novel and efficient execution of nondominated sorting to serve for ranking vector set (DDA-NS) is developed. Moreover, diversity preserving mechanism PSA (Part and Select Algorithm) is proposed. To demonstrate the potential benefit of the novel algorithm, DDA-NS and PSA are integrated into the well-known NSGA-II. According to experimental results, we can conclude the following.(
1
) The fast dominance degree matrix construction method can improve the computational complexity of vector ranking procedure efficiently.(
2
) The selection based on the partitioning algorithm can gain a front involving higher diversity (based on Spacing).



---

*Source: 9697104-2018-09-02.xml*