A region division based diversity maintaining approach for many-objective optimization

Abstract

Evolutionary algorithms have been used to solve a variety of many-objective optimization problems, where these problems contain more than three conflicting objectives. Most existing evolutionary algorithms have shown to perform well on many-objective optimization problems with regular Pareto optimal fronts, their performance, however, will often considerably deteriorate on those whose Pareto optimal fronts are irregular, e.g., discontinuous, degenerated and convex. To address this issue, in this paper, we propose a region division based many-objective optimization evolutionary algorithm, termed RdEA, where a region division approach is suggested to maintain diversity of population for many-objective optimization (especially for problems with irregular Pareto fronts). In the proposed region division based diversity maintaining approach, the geometric information of Pareto optimal fronts is taken into account by using the non-dominated solutions found at each generation, which helps to solve the problems with irregular Pareto optimal fronts better. The proposed RdEA is compared with five state-of-the-art many-objective evolutionary algorithms on 16 test problems from two test suites DTLZ and WFG and a real-world optimization problem. Experimental results on these problems demonstrate that the competitiveness of the proposed algorithm in solving many-objective optimization problems, especially for those with irregular Pareto optimal fronts.

Keywords

Many-objective optimization region division diversity maintaining irregular Pareto front

1. Introduction

Most real-world optimization problems are characterized by the existence of multiple, often conflicting, objectives [1, 2], such as electrical engineering [3], engineering modelling [4, 5, 6, 7], industrial scheduling problems [8, 9] and robotics and control [10, 11, 12]. These optimization problems are called multi-objective optimization problems (MOPs), which involve more than two objectives [13]. Many-objective optimization problems (MaOPs) refer to MOPs involving more than three objectives [14], which are very common in real-world applications, see e.g. [15, 16, 17]. For MOPs, there does not typically exist a single solution that minimizes all objectives simultaneously. Hence, attention is paid to Pareto optimal solutions, that is, solutions that cannot be improved in any objective without degrading at least one of the other objectives [13, 18, 19, 20, 21]. Suppose $x_{A},x_{B}$ are two solutions of an MOP, solution $x_{A}$ is called to Pareto dominate solution $x_{B}$ (denoted as $x_{A}$ $\prec$ $x_{B}$ ), if and only if $f_{i}(x_{A})$ $\leqslant$ $f_{i}(x_{B})$ , $\forall i\in\{1,2,\ldots,M\}$ , and there exists at least one objective $f_{j}$ with $j\in\{1,2,\ldots,M\}$ satisfies $f_{j}(x_{A})<f_{j}(x_{B})$ . If there does not exist any solution $x_{C}$ $\in$ $X$ which Pareto dominates solution $x_{A}$ , solution $x_{A}$ is called a Pareto optimal solution. The collection of all Pareto optimal solutions is called the Pareto optimal set, and the Pareto optimal front (PF) is the projection of Pareto optimal set in objective space.

Existing approaches mainly focused on convergence enhancement for solving MaOPs and have achieved great success on MaOPs with regular PFs [22], but have paid few attentions to maintain the diversity of populations, which would lead to the fact that the found solutions are not uniformly distributed if no additional diversity maintenance strategies are included for MaOPs with irregular PFs.

For this reason, some powerful diversity maintaining strategies have been proposed in MOEAs for obtaining uniformly distributed solutions of MaOPs, see, e.g., MOEA/D [25], NSGA-III [26] and $\theta$ -DEA [27]. One of the representatives of this category is the MOEA/D [25], where an MaOP is decomposed into several scalar optimization subproblems by a set of predefined uniformly distributed weight vectors and optimizes these subproblems simultaneously. For each subproblem, the solution’s survival for next population should be as close to its weight vector as possible for maintaining diversity, hence the Pareto optimal solutions obtained by MOEA/D hold a similar distribution as the uniform weight vectors. The MOEA/D can achieve a set of uniformly distributed Pareto optimal solutions on MaOPs with regular Pareto fronts, but encounters huge challenges in achieving well distributed solutions on those with irregular Pareto fronts. To this end, some adaptive strategies have been proposed to adjust the weight vectors used in MOEAs, e.g., RVEA [28] and MOEA/D-AWA [29]. These strategies have shown to partly improve the distribution of obtained Pareto optimal solutions on most MaOPs with irregular Pareto optimal fronts, but it still needs to be further improved, especially for MaOPs with degenerated or discontinuous fronts as indicated by benchmark problems DTLZ5, 6, 7 and WFG3 [16].

Despite of these reference-based diversity strategies, there are also some strategies adopting region division based approaches for diversity maintaining, e.g., MOEA/D-M2M [30], MOPSO-M2M [31], and GrEA [32]. In MOEA/D-M2M and MOPSO-M2M, the objective space is divided into a number of subregions and then all the subregions are searched using sub-swarms simultaneously. The experimental results on DTLZ1 and DTLZ2 with three objectives indicate that the MOPSO-M2M performs better than another PSO algorithms [33] in achieving a uniformly distributed solution set [31]. As for GrEA, the objective space is divided into a variety of identical hypercubes, and it can achieve a uniformly distributed result on most MaOPs with a lot of parameters adjusting procedure [32].

It is worth noting that the difficulty of diversity maintaining in MaOPs is caused by the curse of dimensionality [14]. In MaOP, as the number of dimensions increases, distance measures become increasingly meaningless for a limited size of population distributed in an extremely large objective space [34]. Traditional distance-based diversity maintaining strategies would fail to estimate the contribution of each solution to the diversity of the population, which results in the difficulty in diversity maintaining for these strategies. However, in the region division based diversity maintaining strategy, the objective space is divided into different subregions to classify solutions into different groups, and the contribution of each solution to the diversity of the population can be estimated, which enables this strategy to maintain diversity in high-dimensional objective space.

In this paper, we propose a region division based diversity maintaining approach for many-objective optimization to obtain uniformly distributed solutions for MaOPs with both regular and irregular Pareto optimal fronts. Meanwhile, the efficient non-dominated sorting (ENS) [35] applied in this paper is compared with approximate non-dominated sorting (A-ENS) [36], as well as another recent published algorithm which is designed for large-scale multi-objective optimization (LMEA [37]), the detailed discussions and comparison are given in the section of experimental results. To summarize, the main contributions of this paper are as follows:

1) 1)
A region division strategy is proposed to maintain diversity of populations for solving MaOPs. The key difference between existing region division strategies and that developed in this paper is that the proposed region division is performed based on the geometric information of the Pareto optimal front determined by the non-dominated solutions found at each generation. Due to the geometric information of the front, the proposed region division strategy can maintain a good diversity of populations on MaOPs with both regular and irregular fronts, thereby leading to uniformly distributed solutions.
2)
An evolutionary algorithm, termed RdEA, is developed to solve MaOPs based on the region division strategy. In RdEA, the diversity of populations is maintained by the region division in the sense that the number of subregions covered by solutions is prior to the convergence of solutions in the environmental selection.
3)
Extensive experimental results are conducted to verify the performance of RdEA for solving MaOPs by comparing it with five state-of-the-art MOEAs for many-objective optimization on two widely used test suites DTLZ and WFG. Empirical results demonstrate that RdEA holds a competitive performance for solving MaOPs, especially for those with irregular PFs.

The rest of this paper is organized as follows. In Section 2, the details of the proposed region division strategy and the RdEA for solving MaOPs are described. The performance of our RdEA by comparing with five state-of-the-art methods on many-objective optimization is presented in Section 3. Conclusions and future work are given in Section 5.
2. The proposed RdEA algorithm

In this section, the proposed RdEA algorithm for solving MaOPs is presented. First, the general framework of RdEA is given and then the details of geometric information based region division are elaborated. Next, the region division based environmental selection is described. At last, the computational complexity of proposed RdEA is analyzed.

2.1 General framework of RdEA

The RdEA algorithm holds a similar framework as NSGA-II. The main difference between RdEA and NSGA-II is their environmental selection. In NSGA-II, the crowing distance is used to select solutions for next population, whereas the geometric information based region division is adopted in RdEA for maintaining diversity to solve MaOPs.

Algorithm 1 presents the general framework of RdEA in pseudo code, which consists of the following main components. First, an initial population of size $N$ is randomly generated. Second, $N$ offspring individuals are generated from the parent population by using binary tournament strategy based on dominance relationship and the crowding distance. Thirdly, non-dominated sorting is performed on the combination of the parent and offspring population. Fourthly, the proposed region division approach is adopted to divide the individuals in the combined population into different subregions. Finally, $N$ individuals are selected as the parent population of the next generation by the environmental selection. This procedure repeats until a termination condition is met.

Algorithm 1
General Framework of RdEA
0:
$P$ (population), $N$ (size of population), $l$ (times of division), $\delta$ (threshold).
1:
$P\leftarrow\textit{Initialization}(N)$
2:
$P_{0}\leftarrow P$ , $\Delta P\leftarrow 1$
3:
while termination criterion not fulfilled do
4:
$P^{\prime}\leftarrow\textit{Mating\_Selection}(P_{0},N)$
5:
$P\leftarrow P^{\prime}\cup\textit{Variation}(P^{\prime},N)$
6:
$F\leftarrow\textit{Nondominated\_sort}(P)$ /find the solutions in the first $i$ fronts $F_{j}$ , $1\leqslant j\leqslant i$ , where $i$ is the minimum value such that $|F|$ $=$ $|F_{1}$ $\cup$ $F_{2}\cdots\cup F_{i}|\geqslant N$ /
7:
$[B,\textit{Central}]\leftarrow\textit{Region\_Division}(P,F_{1},l,M)$
8:
$[P_{0},\Delta P]\leftarrow\textit{Envir\_Selection}(B,F,\delta)$
9:
end
10:
Return: $P_{0}$
2.2 Geometric information based region division

The geometric information based region division is the key component of the proposed RdEA to maintain diversity for solving MaOPs, especially for MaOPs with irregular PFs. The division procedure consists of two main steps: 1) calculating the geometric information of Pareto fronts, and 2) performing region division in objective space. The pseudo code of the region division procedure is given in Algorithm 2. In the following, we present the details of the two steps of the region division approach, respectively.

Algorithm 2
$\textit{Region\_Division}(P,F_{1},l)$
0:
$P$ (population), $l$ (time of divisions), $F_{1}$ (first front), $\delta$ (threshold).
1:
$[V,r]\leftarrow\textit{Boundary}(P,\delta)$
2:
$q\leftarrow\textit{Curvature}(F_{1},r)$
3:
$[B,\textit{Central}]\leftarrow\textit{Division}(q,V,l)$
2.2.1 Geometric information calculation

The geometric information considered here is the curvature [38] and boundary of the Pareto fronts, which are two important elements for characterizing the geometric shape of a front [16]. We first consider how to approximately calculate the curvature by using the solutions found during the search stages, where the curvature information is applied to handle with the solution density imbalance between the central region and boundary region of the PF (especially for MaOPs with convex PFs). For instance, MOEA/D fails to find boundary solutions for WFG1 and WFG2 as the PFs of these two problems are convex [22]. For this end, let us assume that each Pareto front can be described by the following formula if the objective values have been normalized.

$\sum^{M}_{i=1}x_{i}^{q}=1,$

where $x=(x_{1},x_{2},\ldots,x_{M})$ is a point of the front, $M$ is the number of objectives and $q$ is a parameter for characterizing the curvature of the front. Note that, this formulation holds for all kinds of Pareto fronts, since each front is obtained by non-dominated solutions which are distributed on a hypersurface, and this formulation is capable of characterizing a hypersurface approximatively. For instance, the Pareto optimal solution of DTLZ1 corresponds to $X_{M}=0$ and the objective vectors are on the linear hyperplane: $\sum^{M}_{m=1}{f_{m}^{1}}=0.5$ [39], that is, the curvature of the Pareto optimal front of DTLZ1 is 1, and the curvature of the Pareto optimal front of DTLZ2 can be worked out as 2. In [40], it has been shown that the Pareto fronts of most MaOPs can be described by Eq. (1), with $q>1$ , $q=1$ and $0<q<1$ indicating that the front is convex, flat and concave, respectively. In the following, we use the non-dominated solutions found at each generation to determine the value of $q$ . Algorithm 3 presents the details of calculating curvature of Pareto fronts.

Algorithm 3
$\textit{Curvature}(F_{1})$
0:
$F_{1}$ (non-dominated solutions).
0:
$q$ (curvature).
1:
$\textit{ideal}\leftarrow$ ideal point of set $F_{1}$
2:
$\textit{nadir}\leftarrow$ nadir point of set $F_{1}$
3:
for $i=1:|F_{1}|$ do
4:
$s_{i}^{\prime}\leftarrow(s_{i}-\textit{ideal})/(\textit{nadir-ideal})$ /Normalize the $i$ th solution in $F_{1}$ /
5:
end for
6:
$P\leftarrow\{s_{1}^{\prime},s_{2}^{\prime},\ldots,s_{|F_{1}|}^{\prime}\}$
7:
$s\leftarrow$ find the extreme solutions in $P$
8:
$V\leftarrow\sum_{i=1}^{M}{s_{i}}/M$ /Average the objective values in the same objective, $M$ is the number of objectives /
9:
$s_{c}\leftarrow arg\max_{j\in\{1,2,\ldots,m\}}{{\displaystyle\frac{s_{j}\cdot V% }{\|s_{i}\|\cdot\|V\|}}}$ /* $\|\|$ denotes the Euclidean distance from $$ to the original point/
10:
$q\leftarrow{\displaystyle\frac{\lg{(1/M)}}{\lg{(\|s_{c}\|/\sqrt{M}})}}$

Figure 1.
An example to illustrate the method to calculate the curvature of a Pareto front.

Figure 1 presents an example to illustrate how the curvature of a front is calculated by five non-dominated solutions $A$ , $B$ , $C$ , $D$ and $E$ , where origin $O$ is the ideal point and $V$ is the nadir point. First, all non-dominated solutions in $F_{1}$ are normalized by using the nadir point and the ideal point as shown in step 4 in Algorithm 3, such that origin $O$ becomes the new ideal point and the extreme points are located at different coordinate axes. Second, the non-dominated solution $C$ with the smallest acute angle with vector $\overrightarrow{OV}$ is found, where $V$ is the nadir point of the normalized solutions. For any solution $s_{i}$ , the angle between $s_{i}$ and $\overrightarrow{OV}$ is given as

$<s_{i},\overrightarrow{OV}>=\arccos\frac{\overrightarrow{Os_{i}}\cdot% \overrightarrow{OV}}{\|\overrightarrow{Os_{i}}\|_{2}\|\overrightarrow{OV}\|_{2% }},$

where $\overrightarrow{Os_{i}}$ represents a vector from $O$ to $s_{i}$ . At last, the curvature $q$ of the Pareto front can be approximately calculated by using solution $C$ as follows

$q=\frac{\lg(1/M)}{\lg(\textit{dis}/\sqrt{M})},$

where $d i s$ is the Euclidean distance from origin to solution $C$ and $M$ is the number of objectives. The Eq. (3) can be directly obtained from the following two equations.

$\sum_{i=1}^{M}f_{i}^{q}=1,∼{}\|(f_{1},f_{2},\ldots,f_{M})\|_{2}=dis,$

since for $C=(f_{1},f_{2},\ldots,f_{M})$ we can roughly have $f_{1}=f_{2}=\ldots=f_{M}$ due to the fact that $C$ is very close to the centrality of the front given by Eq. (1).

For any solution $Y=(y_{1},y_{2},\ldots,y_{M})$ of an MOP, it can easily be normalized to $Y^{\prime}$ by the following formulas

$\displaystyle\|Y\|_{q}=\left(\sum\nolimits_{i=1}^{M}y_{i}^{q}\right)^{1/q},$ $\displaystyle Y^{\prime}=\left(\frac{y_{1}}{\|Y\|_{q}},\frac{y_{2}}{\|Y\|_{q}}% ,\ldots,\frac{y_{M}}{\|Y\|_{q}}\right).$

Next, we will show how to calculate the boundary of the Pareto front. Due to the fact that the aim of region division is to divide the population into several groups, we here determine the boundary of the populations to perform more effective division of population. Since the boundary is determined by several endpoints, we only need to determine these endpoints. It is necessary to stress that the endpoints we refer to are those obtained by current population, hence they may be not the ones located at each axis as given by Eq. (1). Algorithm 4 presents the details of the method for calculating the endpoints of the boundary.

For simplicity, Fig. 2 presents an example to illustrate how the endpoints of the boundary of a population are calculated, where the population consists of five solutions $A, B, C, D, E$ and the curvature $q=1$ has been determined by the non-dominated solutions in the population. First, all solutions in the population are normalized by Eq. (5), hence the normalized solutions $A^{\prime},B^{\prime},C^{\prime},D^{\prime},E^{\prime}$ are all located on the plane $x_{1}+x_{2}+x_{3}=1$ . Second, linear correlation analysis between objectives is performed to delete the highly linear correlated objectives as described by steps 2 to 11 in Algorithm 4, which aims to handle with MaOPs with degenerated PFs such as DTLZ5 and DTLZ6. For a given population with $M$ objectives, one objective $i\in\{1,2,\ldots,M\}$ is regarded as linear correlation with another objective $j$ , $i\neq j$ , if the angle between $O_{i}=(f^{1}_{i},f^{2}_{i},\ldots,f^{|P|}_{i})$ and $O_{j}=(f^{1}_{j},f^{2}_{j},\ldots,f^{|P|}_{j})$ is smaller than a predefined threshold $\delta$ , where $f^{k}_{i}$ , $1\leqslant k\leqslant|P|$ , $1\leqslant i\leqslant M$ denotes the $i$ th objective value of the $k$ th solution in population $P$ . All objectives which are linear correlated to the $i$ th objective will be deleted in determining the boundary of population. The linear correlation analysis between objectives is suggested to address the situation where the Pareto front is degenerated. In the following experiments, the threshold $\delta$ is always set to $\pi/6$ according to the approximation significant level of 20%. Note that, the intersection angle of two vectors ranges from 0 to $\pi$ , and the threshold is set to $\pi/6$ regardless of the dimensionality of the vectors. Third, the solutions $A^{\prime}$ , $B^{\prime}$ and $C^{\prime}$ along the boundary are found, where the solutions have the minimal value at least on one objective in $P$ . At last, the endpoints $X^{\prime},Y^{\prime},Z^{\prime}$ can be obtained by $A^{\prime}$ , $B^{\prime}$ and $C^{\prime}$ on the plane $x_{1}+x_{2}+x_{3}=1$ .
Algorithm 4
$\textit{Boundary}(P,\delta)$
0:
$P$ (population), $\delta$ (threshold).
0:
$\{V_{1},V_{2},\ldots,V_{r}\}$ (endpoints)
1:
$P^{\prime}\leftarrow$ project these solutions in $P$ to a hyperplane by Eq. (5)
2:
$\textit{obj}\leftarrow{\phi}$
3:
for $i\leftarrow 1:M$ do
4:
for $j\leftarrow i+1:M$ do
5:
$\cos<$ $O_{i},O_{j}$ $>\leftarrow{\displaystyle\frac{O_{i}\cdot O_{j}}{\|O_{i}\|\cdot\|O_{j}\|}}$ / $O_{i}=(f^{1}_{i},f^{2}_{i},\ldots,f^{|P^{\prime}|}_{i})$ /
6:
if $\cos<$ $O_{i},O_{j}$ $>$ $>\cos\delta$ then
7:
$\textit{obj}\leftarrow\textit{obj}\cup\{i\}$
8:
end
9:
end for
10:
end for
11:
$P\leftarrow$ delete objective values in dimension $o b j$ of population $P^{\prime}$
12:
$r\leftarrow$ length of the objective vector in $P$
13:
for $j=1:r$ do
14:
$v_{j}\leftarrow$ the minimal objective value of the $j$ th objective in $P$
15:
$V_{j}\leftarrow\{v_{1},\ldots,v_{j-1},v_{j}^{\prime},v_{j+1},\ldots,v_{r}\}$ / $v_{j}^{\prime}=1-\sum_{i\neq j}{v_{i}}$ */
16:
end for

Figure 2.
An example to illustrate the method to calculate the boundary of a population.

To analyze the influence of the parameter $q$ on the performance of the proposed algorithm, the performance of the proposed algorithm with different settings of $q$ is tested on DTLZ1 with 3, 5 and 10 objectives, respectively. In this experiment, the parameter $q$ is set to 0.5, 1, 1.5 and 2 in comparison with the adaptively adjusted version, and the IGD values achieved by RdEA with different settings of $q$ are displayed in Table 1. It can be observed that the setting of curvature affects the performance of the proposed algorithm, and the performance of the proposed algorithm degenerates when a fixed curvature value is set. Meanwhile, the proposed algorithm can benefit from the adaptive curvature calculation, as the adaptive curvature calculation is capable of estimating the curvature of the Pareto front in the generations.

Table 1
IGD Values achieved by RdEA with different settings of parameter $q$ on DTLZ1 with 3, 5 and 10 objectives, respectively

Obj. $q$

0.5 1 1.5 2 Adaptive

3 2.52e-1 (1.69e-5) 2.47e-2 (1.73e-5) 2.48e-2 (1.27e-5) 2.48e-2 (2.53e-5) 2.42e-2 (1.17e-5)

5 5.83e-2 (5.55e-5) 5.53e-3 (4.36e-5) 5.49e-2 (1.28e-5) 5.48e-2 (5.76e-5) 5.47e-2 (3.25e-5)

10 9.86e-2 (3.27e-4) 9.63e-2 (2.54e-4) 9.59e-2 (5.23e-4) 9.56e-2 (2.22e-4) 9.54e-2 (1.87e-4)

2.2.2 Region division

Obj.	$q$
0.5	1	1.5	2	Adaptive
3	2.52e-1 (1.69e-5)	2.47e-2 (1.73e-5)	2.48e-2 (1.27e-5)	2.48e-2 (2.53e-5)	2.42e-2 (1.17e-5)
5	5.83e-2 (5.55e-5)	5.53e-3 (4.36e-5)	5.49e-2 (1.28e-5)	5.48e-2 (5.76e-5)	5.47e-2 (3.25e-5)
10	9.86e-2 (3.27e-4)	9.63e-2 (2.54e-4)	9.59e-2 (5.23e-4)	9.56e-2 (2.22e-4)	9.54e-2 (1.87e-4)

After the curvature and boundary of the Pareto front are obtained, the proposed RdEA starts to divide the region covered by solutions in population into many subregions. Algorithm 5 presents the main steps of region division in RdEA.

Figure 3 presents an example to illustrate how the region division is performed by Algorithm 5 for an MOP with three objectives, where we assume that the curvature $q=1$ and three endpoints $A$ , $B$ and $C$ of the region have been determined by the non-dominated solutions in the population. In the following, we will show how to divide the region covered by $A$ , $B$ and $C$ . For convenience of description, we denote $R_{S}$ as a subregion, where $S$ is the endpoints along the boundary of the subregion.

First, the middle points between each two endpoints are calculated and normalized by Eq. (5) such that the normalized middle points $A^{\prime},B^{\prime},C^{\prime}$ locate on the Pareto front with curvature $q=1$ . Second, four subregions are obtained by using the endpoints $A, B, C$ and middle points $A^{\prime},B^{\prime},C^{\prime}$ , namely, $R_{AB^{\prime}C^{\prime}}$ , $R_{A^{\prime}BC^{\prime}}$ , $R_{A^{\prime}B^{\prime}C}$ and $R_{A^{\prime}B^{\prime}C^{\prime}}$ . The former three subregions are obtained by two adjacent middle points and one endpoint, and the last subregion is obtained by the three middle points. The above procedure can be repeated on each subregion to divide them into smaller subregions until the time of divisions is satisfied.

Figure 3.

An example of the proposed region division method, where four subregions are obtained.

Algorithm 5

$\textit{Division}(q,V,l)$

$q$ (curvature), $l$ (time of division), $V$ (boundary of the population).

$B$ (endpoints of each subregion), Central (the central vector of each subregion).

for $i\leftarrow 1:M$ do

for $j\leftarrow 1:M\setminus i$ do

$B(i,j)\leftarrow(V(i)+V(j))/2$

end for

$B(i)(M+1)\leftarrow V_{i}$

end for

for $j\leftarrow 1:M-1$ do

$B(M+1)(j)\leftarrow(V_{j}+V_{j+1})/2$

end for

10:

if $M$ is even then

11:

$i\leftarrow 2$

12:

else

13:

$i\leftarrow 1$

14:

end

15:

$B(M+1)(M+1)\leftarrow(V_{M+1}+S_{i})$

16:

for $i\leftarrow 1:m+1$ do

17:

$\textit{Central}(i)\leftarrow\sum_{j=1}^{M+1}B(i,j)$

18:

end for

19:

repeat steps 1 to 18 to divide the each smaller subregions

To visualize the region division in high-dimensional space, 10000 randomly generated 5-dimensional solutions are divided into $(5+1)^{3}$ subregions, and the solutions in one selected subregion are highlighted as shown in Fig. 4. It can be observed that these solutions in the same subregion have similar objective values in each dimension, hence the subregion division is reasonable for maintain diversity in high-dimensional objective space.

Figure 4.

An example of region division in high-dimensional space, where 10000 solutions are divided into 216 subregions and the solutions in one selected subregion are highlighted.

2.3 Region division based environmental selection

The region covered by solutions in population is divided into subregions by Algorithm 5, the RdEA will select solutions for next population according to the subregions in which the solutions locate in environmental selection. The environmental selection in RdEA is performed as follows.

Let us assume that the number of nonempty subregions is $K$ . For each of the $K$ nonempty subregions, one solution is selected for next population. The selected solution belongs to one of the two types: 1) the solution with the shortest Euclidean distance to the origin, and 2) the solution closest to the center of the subregion. The former solution will have a better convergence than the other solutions in the subregion, whereas the last solution holds a better diversity. For deciding which type of solutions is selected in the nonempty subregions at each generation, a convergence level $\Delta P$ is defined here.

$\Delta P=\textit{abs}\left(\frac{\overline{\|\textit{NP}_{t}\|}-\overline{\|% \textit{NP}_{t-1}\|}}{\overline{\|\textit{NP}_{t-1}\|}}\right),$

where $\textit{NP}_{t}$ is the set of non-dominated solutions in population at $t$ th generation, $\overline{\|\cdot\|}$ is the average value of Euclidean distances from the solutions to the origin in objective space, and $\textit{abs}(\cdot)$ is the absolute function. The convergence level $\Delta P$ is used to characterize the extent of convergence changing at different generations. A large value of $\Delta P$ indicates that the population can be further improved in terms of convergence, hence the solution with the shortest Euclidean distance to the origin is selected in each nonempty subregion for next population at that generation.

Algorithm 6
$\textit{Envir\_Selection}(B,F,\delta)$
0:
$B$ (endpoints of each subregion), $F$ (the Pareto fronts of the combined population), $\delta$ (threshold of $\Delta P$ )
0:
$P_{0}$ (population), $\Delta P$ (convergence level)
1:
$[\textit{kind},\theta]\leftarrow$ classify each solution to a subregion with label kind
2:
$\theta\leftarrow$ calculate the acute angle between the solution and the central vector of its belongs subregion by Eq. (2)
3:
$\text{{KIND}}\leftarrow$ merge the labels of nonempty subregions in kind
4:
$\{I_{1},I_{2},\ldots,I_{|\text{{KIND}}|}\}\leftarrow\textit{Partition}(\textit% {kind})$ /Put the solutions with the same label in the same set /
5:
for $i=1:|\text{{KIND}}|$ do
6:
if $\Delta P_{t-1}>\delta$ then
7:
$s_{i}\leftarrow$ select the solution with the shortest Euclidean distance to the original point
8:
else
9:
$s_{i}\leftarrow$ select the solution with the smallest $\theta$ value
10:
end
11:
$Q\leftarrow Q\cup{s_{i}}$
12:
end for
13:
$\textit{Next}\leftarrow Q$
14:
update $\Delta P$ by Eq. (6)

It is necessary to stress that there are some region division based algorithms for MaOPs (e.g., GrEA [32]), however the proposed geometric information based region division has some potential superiority. To illustrate this fact, Fig. 5 presents an example, where the population has seven solutions $p_{i}$ , $1\leqslant i\leqslant 7$ and four solutions from them will be selected for next population. As shown in the figure, solutions $p_{1}$ , $p_{2}$ , $p_{3}$ , $p_{5}$ , $p_{6}$ and $p_{7}$ are non-dominated with each other, whereas solution $p_{4}$ is dominated by solution $p_{5}$ . If the existing region division strategies are used (for example, the grid division in GrEA [32]), the solutions $\{p_{1},p_{5},p_{6},p_{7}\}$ are selected for next generation population. However, the solutions $p_{1}$ , $p_{4}$ , $p_{6}$ and $p_{7}$ will be selected if the proposed region division is adopted. It is not difficult to find that, compared to the set of solutions $\{p_{1},$ $p_{5},$ $p_{6},$ $p_{7}\}$ , the set of solutions $\{p_{1},$ $p_{4},$ $p_{6},$ $p_{7}\}$ has a better diversity. The population $\{p_{1},$ $p_{4},$ $p_{6},$ $p_{7}\}$ will be more helpful to achieve a better performance for the final population, despite that the solution $p_{4}$ is worse than $p_{5}$ in terms of convergence.

Figure 5.
An example to illustrate the region division based environmental selection in RdEA, where four solutions will be selected from a population having 7 solutions for next population.

2.4 Theoretical computational complexity analysis

In this section, we provide an upper bound of the computational complexity of RdEA. Suppose that the RdEA with population size of $N$ is used to solve an MaOP with $M$ objectives. The RdEA mainly performs the following four operations: non-dominated sorting, geometric information calculation, region division and environmental selection. The complexity of non-dominated sorting is $O(\textit{MN}^{2})$ in the worst case by using the efficient non-dominated sorting (ENS) [35]. The computational efficiency of non-dominated sorting can be improved if the tree-based efficient non-dominated sorting (T-ENS) [37] or the approximate non-dominated sorting (A-ENS) [36] is adopted. The geometric information needs to calculate both curvature and boundary of the Pareto optimal front, each of which at most needs a complexity of $O(\textit{MN})$ . As for the region division, a complexity of $O(N(M+1)^{l})$ is needed, where $l$ is the time of divisions. The environmental selection takes a complexity of $O(N|\text{KIND}|)$ , where $|\text{KIND}|$ is the number of subregions with at least one solution. Due to the fact that the population size is $N$ , the environmental selection at most holds a complexity of $O(N^{2})$ . This means that the complexity of RdEA is $O(M^{l+2}N+\textit{MN}^{2})$ in one generation. Therefore, the proposed RdEA holds a computational complexity of $O(G(M^{l+2}N+\textit{MN}^{2}))$ in the worst case, where $G$ is the number of generations and $l$ is the time of divisions (a very small value is used for solving MaOPs).

3. Experimental results and discussions

In this section, the performance of RdEA is verified by empirically comparing it with five popular MOEAs for many-objective optimization, namely, MOEA/D [25], NSGA-III [26], $\theta$ -DEA [27], KnEA [41], and RVEA [28]. The experiments are conducted on 16 test problems taken from two widely used test suites, DTLZ [39] and WFG [42]. For each test problem, 3, 5 and 10 objectives will be considered, respectively. The quality of the found solution sets is evaluated by two widely adopted performance metrics, Inverted Generational Distance (IGD) [43] and Hypervolume (HV) [44]. Each algorithm is performed for 20 runs on each test instance independently, and the Wilcoxon rank sum test is adopted to compare the results achieved by RdEA and other compared algorithms at a significant level of 0.05. Symbol ‘ $+$ ’ indicates that the RdEA significantly outperforms the compared algorithms according to the Wilcoxon rank sum test, while ‘ $-$ ’ represents that the compared algorithms significantly outperform the RdEA, and ‘ $\approx$ ’ means that there is no statistically significant difference between the results achieved by RdEA and the compared algorithm. All the experiments are conducted on a PC with a 2.50 GHz Intel Core(TM) i7-6500U CPU (4 CPU Cores) on the Windows 10 64-bit operation system, and the source codes are written on the same Matlab platform named PlatEMO [45] (Matlab version: R2015b 64-bit).

3.1 Experimental settings

3.1.1 Test problems

In the experimental study, the tested 16 test problems consist of 7 DTLZ test problems (DTLZ1 to DTLZ7) and 9 WFG test problems (WFG1 to WFG9), whose settings are listed in Table 2. According to whether their Pareto optimal fronts are regular or not, these test problems are divided into two groups.

(1)
Problems with regular Pareto fronts. The regular Pareto fronts refer to the ones which are continuous or non-convex in this paper. Most real-world MaOPs would belong to this category and hence they are often used in evaluating the performance of MOEAs. Among the 16 test problems considered in the experiments, the test problems with regular fronts are DTLZ1 to DTLZ4, and WFG4 to WFG9.
(2)
Problems with irregular Pareto fronts. The irregular Pareto fronts refer to those which are discontinuous, degenerated or convex in this paper. These test problems represent a group of challenging problems for existing MOEAs, and much work still needs to be performed for effectively solving them. Six test problems, DTLZ5 to DTLZ7 and WFG1 to WFG3, considered in the experiments belong to this category.

Table 2
Settings of the number of objectives, the number of decision variables and the property of PF for each test problem

Problem Number of Number of

objectives decision Remark

( $M$ ) variables ( $D$ )

DTLZ1 3, 5, 10 M-1 $+$ 5 Regular

DTLZ2, 3, 4 3, 5, 10 M-1 $+$ 10 Regular

WFG4–9 3, 5, 10 M-1 $+$ 10 Regular

WFG1, 2 3, 5, 10 M-1 $+$ 10 Convex

DTLZ5, 6 3, 5, 10 M-1 $+$ 10 Degenerated

WFG3 3, 5, 10 M-1 $+$ 10 Degenerated

DTLZ7 3, 5, 10 M-1 $+$ 20 Discontinuous

3.1.2 Parameter settings

Problem	Number of	Number of
	objectives	decision	Remark
	( $M$ )	variables ( $D$ )
DTLZ1	3, 5, 10	M-1 $+$ 5	Regular
DTLZ2, 3, 4	3, 5, 10	M-1 $+$ 10	Regular
WFG4–9	3, 5, 10	M-1 $+$ 10	Regular
WFG1, 2	3, 5, 10	M-1 $+$ 10	Convex
DTLZ5, 6	3, 5, 10	M-1 $+$ 10	Degenerated
WFG3	3, 5, 10	M-1 $+$ 10	Degenerated
DTLZ7	3, 5, 10	M-1 $+$ 20	Discontinuous

For a fair comparison, we adopt the recommended parameter values which have achieved the best performance for all compared algorithms. The parameters of the compared algorithms are set as follows.

Table 3
Setting of population size in NSGA-III, MOEA/D, $\theta$ -DEA and RVEA, where $p_{1}$ and $p_{2}$ are parameters controlling the numbers of weight vectors along the boundary of the Pareto front and inside it, respectively

Obj.	Parameter ( $p_{1},p_{2}$ )	Population size ( $N$ )
3	(9, 3)	65
5	(6, 1)	215
10	(4, 4)	1430

Table 4

The number of reference points for different test instances in IGD

Problem.	Objective Number
	3	5	10
DTLZ1–4	4950	4845	4004
DTLZ5, 6	5000	5000	5000
DTLZ7	5041	6561	19683
WFG2	5041	6561	19683
WFG3	5000	5000	5000
WFG1, WFG4–9	4950	4845	4004

(1) (1)

Crossover and mutation operators. In all considered algorithms, the simulated binary cross- over [46] and polynomial mutation [47] have been adopted to create offspring. The distribution index of crossover is set to $n_{c}=$ 20 and the distribution index of mutation is set to $n_{m}=$ 20, as recommended in [18]. The crossover probability $p_{c}=$ 1.0 and the mutation probability $p_{m}=1/D$ are used, where $D$ denotes the number of decision variables.

(2)

Population size. The population size of the proposed RdEA is determined by the number of divided subregions $(M+1)^{l}$ , where $M$ is the number of objectives and $l$ is the time of divisions. For all test problems, $l$ is always set to 3 in the experiments. For a fair comparison, the population size of the compared algorithms is also set to the same value. Due to the fact that the population sizes of NSGA-III, MOEA/D, $\theta$ -DEA and RVEA cannot be arbitrarily set since they are determined by the number of uniformly distributed weight vectors, we set the population sizes of these algorithms to the integers closest to the population size adopted in RdEA. For NSGA-III, MOEA/D, $\theta$ -DEA and RVEA, the two-layer strategy recommended in NSGA-III is adopted to generate the uniformly distributed weight vectors to avoid that the generated vectors are all located along the boundary of Pareto fronts for MaOPs. Table 3 presents the settings of population size adopted in the compared algorithms, where $p_{1}$ and $p_{2}$ are parameters controlling the numbers of weight vectors along the boundary of the Pareto front and inside it, respectively. The population size of KnEA is set to 65, 215 and 1430 for MaOPs with 3, 5 and 10 objectives respectively, while the population size of RdEA is set to 64, 216 and 1331 (the population size for RdEA is set the same as the number of subregions to achieve the best result).

Table 5

The IGD values of six MaOEAs on 30 test instances with regular Pareto optimal fronts and the best result in each row is highlighted

Problem	Obj.	MOEA/D	NSGA-III	$\theta$ -DEA	KnEA	RVEA	RdEA
DTLZ1	3	2.60e-2 (7.20e-5) $-$	2.60e-2 (1.28e-4) $-$	2.59e-2 (7.46e-5) $-$	7.50e-2 (4.09e-2) $-$	2.60e-2 (1.48e-4) $-$	2.42e-2 (1.17e-5)
	5	5.22e-2 (3.44e-5) $+$	5.21e-2 (1.76e-5) $+$	5.21e-2 (2.62e-5) $+$	2.02e-1 (6.29e-2) $-$	5.21e-2 (1.45e-5) $+$	5.47e-2 (3.25e-5)
	10	9.12e-2 (2.43e-4) $-$	9.27e-2 (1.02e-2) $-$	8.42e-2 (5.47e-3) $\approx$	2.80e-1 (2.61e-2) $-$	8.68e-2 (8.45e-5) $\approx$	8.54e-2 (1.87e-4)
DTLZ2	3	6.81e-2 (1.98e-6) $-$	6.79e-2 (1.27e-4) $-$	6.79e-2 (1.20e-4) $-$	9.22e-2 (5.70e-3) $-$	6.85e-2 (1.46e-3) $-$	6.42e-2 (3.09e-4)
	5	1.61e-1 (3.43e-6) $+$	1.61e-1 (4.20e-5) $+$	1.61e-1 (8.77e-6) $-$	1.77e-1 (4.89e-3) $-$	1.61e-1 (1.39e-5) $+$	1.71e-1 (7.62e-4)
	10	3.26e-1 (2.06e-4) $+$	3.25e-1 (1.75e-3) $+$	3.23e-1 (8.32e-5) $+$	3.63e-1 (6.76e-2) $-$	3.24e-1 (8.27e-5) $+$	3.34e-1 (1.49e-3)
DTLZ3	3	6.89e-2 (4.57e-4) $\approx$	6.85e-2 (6.84e-4) $\approx$	6.86e-2 (7.87e-4) $\approx$	1.43e-1 (3.45e-2) $-$	7.04e-2 (2.13e-3) $\approx$	7.75e-2 (8.94e-3)
	5	1.62e-1 (5.38e-4) $+$	1.61e-1 (4.78e-4) $+$	1.61e-1 (1.24e-4) $+$	3.71e-1 (1.52e-1) $+$	1.61e-1 (3.70e-4) $+$	4.78e-1 (8.57e-2)
	10	3.27e-1 (5.71e-4) $+$	3.42e-1 (7.12e-2) $+$	3.52e-1 (1.14e-1) $\approx$	1.22e+0 (5.76e-2) $-$	3.24e-1 (3.09e-4) $+$	4.50e-1 (1.59e-2)
DTLZ4	3	2.03e-1 (3.01e-1) $-$	3.46e-1 (3.17e-1) $-$	3.07e-1 (2.51e-1) $-$	2.62e-1 (3.60e-1) $-$	6.81e-2 (4.80e-5) $\approx$	6.46e-2 (2.36e-4)
	5	2.10e-1 (1.03e-1) $-$	1.61e-1 (9.42e-5) $+$	1.61e-1 (3.52e-5) $+$	1.77e-1 (4.05e-3) $\approx$	1.61e-1 (4.18e-5) $+$	1.75e-1 (1.86e-3)
	10	4.32e-1 (5.51e-2) $-$	3.24e-1 (2.40e-4) $+$	3.22e-1 (1.37e-4) $+$	5.43e-1 (1.43e-2) $-$	3.23e-1 (8.98e-5) $+$	3.33e-1 (1.49e-3)
WFG4	3	3.02e-1 (1.74e-3) $-$	2.72e-1 (7.25e-4) $+$	2.72e-1 (5.51e-4) $+$	3.47e-1 (1.26e-2) $-$	2.78e-1 (1.81e-3) $-$	2.51e-1 (1.31e-3)
	5	1.43e+0 (3.07e-2) $-$	9.54e-1 (6.63e-4) $+$	9.54e-1 (6.56e-4) $+$	1.01e+0 (9.16e-3) $-$	9.54e-1 (1.53e-3) $\approx$	9.95e-1 (2.54e-3)
	10	8.08e+0 (1.64e-2) $-$	3.09e+0 (1.35e-2) $\approx$	3.10e+0 (9.70e-3) $\approx$	2.33e+0 (1.35e-2) $+$	2.96e+0 (1.05e-2) $+$	3.08e+0 (1.38e-2)
WFG5	3	2.96e-1 (5.69e-4) $-$	2.78e-1 (5.86e-4) $-$	2.78e-1 (7.36e-4) $-$	3.35e-1 (1.32e-2) $-$	2.83e-1 (1.19e-3) $-$	2.66e-1 (4.40e-4)
	5	1.37e+0 (6.00e-2) $-$	9.45e-1 (8.05e-4) $+$	9.45e-1 (6.68e-4) $+$	9.93e-1 (1.01e-2) $\approx$	9.46e-1 (1.59e-3) $+$	9.89e-1 (1.03e-3)
	10	7.82e+0 (7.86e-2) $-$	3.06e+0 (1.11e-2) $+$	3.04e+0 (8.34e-3) $+$	2.31e+0 (1.71e-2) $+$	2.98e+0 (1.79e-2) $+$	3.13e+0 (6.47e-3)
WFG6	3	3.26e-1 (3.90e-3) $-$	2.92e-1 (9.34e-3) $-$	2.90e-1 (8.17e-3) $-$	3.89e-1 (2.77e-2) $-$	2.92e-1 (6.e-3) $-$	2.86e-1 (6.52e-3)
	5	1.52e+0 (4.09e-2) $-$	9.51e-1 (1.87e-3) $+$	9.48e-1 (6.91e-4) $+$	1.03e+0 (1.04e-2) $-$	9.51e-1 (9.59e-4) $+$	9.97e-1 (2.55e-3)
	10	8.13e+0 (5.81e-2) $-$	3.14e+0 (8.14e-3) $\approx$	3.14e+0 (4.65e-3) $\approx$	2.43e+0 (1.45e-2) $+$	2.97e+0 (1.85e-2) $+$	3.13e+0 (7.84e-3)
WFG7	3	3.36e-1 (1.06e-2) $-$	2.73e-1 (3.20e-4) $-$	2.73e-1 (3.55e-4) $-$	3.38e-1 (1.28e-2) $-$	2.78e-1 (1.95e-3) $-$	2.54e-1 (2.09e-3)
	5	1.55e+0 (2.00e-2) $-$	9.56e-1 (6.23e-4) $+$	9.56e-1 (4.06e-4) $+$	1.01e+0 (1.18e-2) $-$	9.58e-1 (9.58e-4) $+$	9.97e-1 (2.73e-3)
	10	8.13e+0 (1.94e-2) $-$	3.09e+0 (9.00e-3) $\approx$	3.08e+0 (5.24e-3) $\approx$	2.27e+0 (8.96e-3) $+$	2.93e+0 (1.51e-2) $+$	3.11e+0 (5.25e-3)
WFG8	3	3.46e-1 (2.05e-3) $-$	3.18e-1 (1.62e-3) $\approx$	3.18e-1 (3.06e-3) $+$	4.48e-1 (2.83e-2) $-$	3.37e-1 (4.84e-3) $-$	3.29e-1 (2.01e-3)
	5	1.43e+0 (2.05e-1) $-$	9.89e-1 (5.67e-3) $\approx$	9.76e-1 (5.28e-3) $+$	1.08e+0 (7.01e-3) $\approx$	9.82e-1 (7.21e-4) $+$	1.07e+0 (2.72e-3)
	10	7.64e+0 (6.53e-2) $-$	3.07e+0 (6.44e-2) $+$	3.11e+0 (2.52e-2) $\approx$	2.52e+0 (3.82e-2) $+$	2.92e+0 (1.30e-2) $+$	3.14e+0 (4.02e-3)
WFG9	3	3.09e-1 (1.02e-2) $-$	2.75e-1 (4.05e-3) $-$	3.02e-1 (5.34e-2) $-$	3.17e-1 (3.85e-2) $-$	3.02e-1 (4.35e-2) $-$	2.57e-1 (1.42e-3)
	5	1.42e+0 (1.28e-2) $-$	9.20e-1 (3.36e-3) $\approx$	9.19e-1 (3.17e-3) $+$	9.50e-1 (1.14e-2) $\approx$	9.35e-1 (1.53e-3) $+$	9.90e-1 (3.13e-3)
	10	7.45e+0 (8.50e-2) $-$	3.04e+0 (1.23e-2) $+$	3.01e+0 (2.59e-2) $+$	2.35e+0 (1.55e-2) $+$	2.91e+0 (1.76e-2) $+$	3.19e+0 (1.02e-2)

(3)

Number of runs and stopping condition. For each algorithm, 20 independent runs are performed on each test instance. The maximum number of evaluations is adopted as the termination criterion for all considered algorithms. For DTLZ1, the maximum number of evaluations is set to 700 N, 1000 N for DTLZ3 and 500 N for the remaining test problems, where $N$ is the population size of an algorithm.

Table 6

The IGD values of six MaOEAs on 18 test instances with irregular Pareto optimal fronts and the best result in each row is highlighted

Problem	Obj.	MOEA/D	NSGA-III	$\theta$ -DEA	KnEA	RVEA	RdEA
DTLZ5	3	2.00e-2 (6.81e-3) $-$	8.88e-1 (6.54e-2) $-$	1.49e+0 (1.57e-1) $-$	7.88e-1 (6.04e-2) $-$	7.41e-2 (4.60e-3) $-$	1.10e-2 (6.75e-3)
	5	4.22e-1 (3.15e-2) $-$	6.96e-1 (8.45e-2) $-$	1.03e+0 (1.14e-1) $-$	3.64e-1 (5.78e-2) $-$	2.08e-1 (2.05e-2) $-$	8.40e-2 (7.06e-3)
	10	2.30e-1 (2.65e-3) $-$	5.25e-1 (2.16e-2) $-$	9.09e-1 (7.44e-2) $-$	2.47e-1 (4.72e-2) $\approx$	3.96e-1 (2.97e-2) $-$	2.20e-1 (4.37e-2)
DTLZ6	3	2.20e-2 (9.12e-3) $-$	9.83e-1 (5.83e-2) $-$	1.49e+0 (1.61e-1) $-$	5.83e-1 (6.31e-2) $-$	1.21e-1 (1.65e-2) $-$	1.70e-2 (5.20e-3)
	5	8.72e-2 (3.15e-3) $\approx$	6.42e-1 (5.08e-2) $-$	8.53e-1 (1.05e-1) $-$	4.80e-1 (8.78e-2) $-$	1.89e-1 (4.16e-2) $-$	7.50e-2 (7.33e-3)
	10	1.96e-1 (9.62e-2) $\approx$	5.56e-1 (1.16e-1) $-$	8.20e-1 (5.30e-2) $-$	2.47e-1 (8.46e-2) $-$	2.64e-1 (4.59e-2) $-$	1.90e-1 (1.04e-2)
DTLZ7	3	3.87e-1 (2.29e-1) $-$	6.74e-1 (5.15e-2) $-$	8.87e-1 (1.16e-1) $-$	5.04e-1 (5.67e-2) $-$	1.31e-1 (5.45e-3) $-$	1.05e-1 (4.20e-2)
	5	6.10e-1 (3.90e-2) $-$	5.77e-1 (4.20e-2) $-$	8.31e-1 (8.95e-2) $-$	3.74e-1 (6.26e-2) $-$	4.07e-1 (7.37e-3) $-$	2.64e-1 (5.15e-2)
	10	1.26e+0 (1.26e-1) $\approx$	4.08e-1 (2.43e-2) $+$	7.00e-1 (8.60e-2) $+$	1.23e-1 (4.18e-2) $+$	1.44e+0 (6.95e-2) $-$	1.24e+0 (5.02e-2)
WFG1	3	6.62e-1 (8.52e-2) $-$	3.23e-1 (2.32e-2) $-$	3.49e-1 (4.27e-2) $-$	3.38e-1 (7.55e-2) $-$	4.08e-1 (8.50e-2) $-$	1.85e-1 (3.19e-2)
	5	1.67e+1 (2.87e-1) $-$	7.22e-1 (5.73e-2) $-$	7.48e-1 (8.28e-2) $-$	7.11e-1 (1.01e-1) $-$	5.17e-1 (3.62e-2) $-$	4.29e-1 (1.12e-2)
	10	2.82e+0 (1.22e-1) $-$	1.05e+0 (1.17e-1) $\approx$	1.46e+0 (1.40e-1) $-$	1.25e+0 (4.25e-2) $-$	1.13e+0 (1.05e-1) $\approx$	1.04e+0 (1.99e-1)
WFG2	3	7.43e-1 (1.03e-2) $-$	2.41e-1 (1.28e-2) $-$	1.94e-1 (3.28e-2) $\approx$	2.08e-1 (2.18e-2) $-$	2.48e-1 (2.69e-2) $-$	1.83e-1 (3.97e-2)
	5	2.03e+0 (3.23e-1) $-$	6.59e-1 (1.18e-2) $-$	7.46e-1 (9.87e-3) $-$	4.98e-1 (5.81e-2) $+$	6.33e-1 (9.05e-2) $-$	5.83e-1 (2.20e-2)
	10	8.62e+0 (2.80e+0) $-$	9.20e-1 (1.32e-1) $+$	1.77e+0 (2.06e-1) $-$	1.25e+0 (5.38e-2) $+$	3.53e+0 (2.03e+0) $-$	1.46e+0 (3.83e-1)
WFG3	3	2.50e-1 (2.38e-3) $\approx$	2.02e-1 (2.01e-3) $+$	2.01e-1 (2.40e-3) $+$	2.82e-1 (1.33e-2) $-$	3.05e-1 (2.68e-2) $-$	2.63e-1 (1.28e-2)
	5	1.16e+0 (3.29e-2) $-$	7.07e-1 (8.29e-3) $-$	7.10e-1 (5.41e-3) $-$	8.70e-1 (7.84e-2) $-$	4.58e-1 (1.55e-2) $-$	3.20e-1 (4.34e-2)
	10	1.45e+0 (1.06e-1) $-$	2.32e+0 (2.86e-2) $-$	2.32e+0 (5.35e-2) $-$	2.04e+0 (4.81e-2) $-$	1.95e+0 (9.87e-2) $-$	6.64e-1 (2.02e-2)

Table 7

The HV values of six MaOEAs on 18 test instances with irregular Pareto optimal fronts and the best result in each row is highlighted

Problem	Obj.	MOEA/D	NSGA-III	$\theta$ -DEA	KnEA	RVEA	RdEA
DTLZ5	3	1.30e-1 (0.00e+0) $\approx$	1.26e-1 (5.48e-3) $-$	1.18e-1 (4.47e-3) $-$	1.08e-1 (1.30e-2) $-$	9.40e-2 (5.48e-3) $-$	1.34e-1 (1.00e-3)
	5	1.00e-2 (0.00e+0) $\approx$	1.00e-2 (0.00e+0) $\approx$	1.00e-2 (0.00e+0) $\approx$	6.00e-3 (5.48e-3) $\approx$	1.00e-2 (0.00e+0) $\approx$	7.50e-3 (3.20e-4)
	10	0.00e+0 (0.00e+0) $-$	0.00e+0 (0.00e+0) $-$	0.00e+0 (0.00e+0) $-$	0.00e+0 (0.00e+0) $-$	0.00e+0 (0.00e+0) $-$	4.23e-8 (3.54e-9)
DTLZ6	3	1.30e-1 (0.00e+0) $\approx$	1.22e-1 (4.47e-3) $-$	1.18e-1 (4.47e-3) $-$	1.30e-1 (0.00e+0) $\approx$	7.80e-2 (1.48e-2) $-$	1.33e-1 (2.42e-3)
	5	1.00e-2 (0.00e+0) $+$	1.00e-2 (0.00e+0) $+$	1.00e-2 (0.00e+0) $+$	4.00e-3 (5.48e-3) $-$	1.00e-2 (0.00e+0) $+$	8.65e-3 (4.57e-4)
	10	0.00e+0 (0.00e+0) $-$	0.00e+0 (0.00e+0) $-$	0.00e+0 (0.00e+0) $-$	0.00e+0 (0.00e+0) $-$	0.00e+0 (0.00e+0) $-$	5.54e-8 (7.57e-9)
DTLZ7	3	1.32e+0 (6.71e-2) $-$	1.56e+0 (5.48e-3) $+$	1.49e+0 (6.30e-2) $\approx$	1.57e+0 (9.18e-2) $+$	1.47e+0 (3.83e-2) $\approx$	1.44e+0 (2.34e-1)
	5	1.43e+0 (6.71e-2) $-$	2.28e+0 (1.52e-2) $+$	1.93e+0 (5.76e-2) $+$	2.30e+0 (1.67e-2) $+$	1.92e+0 (2.88e-2) $+$	1.68e+0 (3.45e-1)
	10	5.60e-1 (3.22e-1) $-$	2.73e+0 (2.59e-2) $+$	2.66e+0 (1.77e-1) $+$	1.71e+0 (3.51e-1) $+$	9.72e-1 (5.87e-1) $-$	1.04e+0 (1.23e-1)
WFG1	3	5.42e+1 (4.15e+0) $-$	5.63e+1 (2.91e+0) $\approx$	5.71e+1 (9.39e-1) $-$	5.78e+1 (1.05e+0) $\approx$	5.39e+1 (2.52e+0) $-$	5.87e+1 (2.05e+0)
	5	6.12e+3 (2.29e+0) $\approx$	5.59e+3 (2.42e+2) $-$	5.66e+3 (1.49e+2) $-$	6.08e+3 (1.44e+2) $-$	5.64e+3 (1.45e+2) $-$	6.14e+3 (5.35e+2)
	10	6.51e+9 (6.31e+8) $-$	8.93e+9 (4.07e+8) $\approx$	9.60e+9 (9.06e+6) $\approx$	9.63e+9 (2.11e+6) $\approx$	5.26e+9 (1.51e+8) $-$	9.69e+9 (8.45e+8)
WFG2	3	5.39e+1 (7.09e-1) $\approx$	5.89e+1 (6.06e-2) $\approx$	5.93e+1 (2.07e-2) $\approx$	5.88e+1 (2.38e-1) $\approx$	5.87e+1 (1.43e-1) $\approx$	5.72e+1 (3.47e+0)
	5	5.99e+3 (1.89e+2) $=$	6.15e+3 (6.29e+0) $+$	6.15e+3 (6.00e+0) $+$	6.14e+3 (6.36e+0) $+$	6.13e+3 (1.09e+1) $+$	6.08e+3 (4.53e+1)
	10	9.62e+9 (7.59e+6) $\approx$	9.63e+9 (1.57e+7) $\approx$	9.58e+9 (1.59e+7) $-$	9.60e+9 (4.54e+6) $\approx$	9.54e+9 (1.47e+7) $-$	9.64e+9 (2.35e+7)
WFG3	3	5.67e+0 (2.30e-2) $+$	6.03e+0 (1.23e-1) $+$	5.87e+0 (5.64e-2) $+$	5.94e+0 (8.02e-2) $+$	5.21e+0 (2.05e-1) $-$	5.61e+0 (3.43e-1)
	5	1.11e+0 (1.64e-2) $-$	1.85e+0 (1.83e-1) $+$	2.39e+0 (1.25e-1) $+$	6.32e-1 (2.33e-1) $-$	1.92e+0 (8.96e-2) $+$	1.23e+0 (3.50e-1)
	10	0.00e+0 (0.00e+0) $-$	0.00e+0 (0.00e+0) $-$	0.00e+0 (0.00e+0) $-$	0.00e+0 (0.00e+0) $-$	0.00e+0 (0.00e+0) $-$	6.04e-6 (2.44e-7)

(4)

Settings of other parameters. Following the practice in [48], the Tchebycheff function in MOEA/D is selected as the scalarizing function, and the neighborhood size $T$ was specified as 10% of the population size as recommended in [25]. In $\theta$ -DEA, the penalty-based boundary intersection (PBI) approach is adopted as the aggressive function with the penalty factor being set to 5 as recommended in [27], and the number of weight vectors in neighborhood is set to $\lfloor N/10\rfloor$ , where $N$ is the population size. Two parameters $\alpha$ and $f_{r}$ used in RVEA are set to $\alpha=$ 2 and $f_{r}=$ 0.1 as recommended in [28]. The parameter $T$ for controlling the ratio of knee points [41] is set to $T=$ 0.5 for most MaOPs, except for being set to $T=$ 0.6 on tri-objectives DTLZ1, 3 and $T=$ 0.1 on ten-objective DTLZ1, 3 as recommended in [28]. For RdEA, the threshold $\delta$ for boundary calculation is set to $\pi/6$ . The number of division l is set to 4 for DTLZ5, 6 and WFG3, and 3 for the rest test problems. Note that, we have adjusted the parameter settings in each compared algorithm, and each algorithm with the recommended parameter settings performs the best on each instance, hence the specific parameter settings are set as the recommendation.

Table 8

IGD results achieved by RdEA, A-ENS, and LMEA DTLZ2 and 10-objective DTLZ7 with 9 and 100 decision variables

Pro.	Dec.	RdEA	A-ENS	LMEA
DTLZ2	14	3.34e-1 (1.49e-3)	5.96e-1 (6.34e-2)	4.10e-1 (4.34e-3)
	100	5.05e-1 (2.25e-2)	5.10e-1 (6.34e-2)	4.94e-1 (3.34e-1)
DTLZ7	24	1.29e+0 (1.87e-2)	1.36e-1 (2.54e-2)	1.31e+0 (1.34e-2)
	100	1.37e+0 (3.25e-2)	1.26e+0 (6.34e-2)	1.02e+0 (1.24e-2)

3.1.3 Performance metrics

Two widely performance metrics are used to assess the performance of the compared algorithms on benchmark test problems. The first one is the Inverted Generational Distance (IGD) [43], which can assess both the convergence and distribution of the solution set obtained by MOEAs. Suppose that $P^{*}$ is a set of evenly distributed reference points in the Pareto optimal front and $\Omega$ is the set of non-dominated solutions found by MOEAs. The IGD can be mathematically defined as follows.

$\text{IGD}(P^{*},\Omega)=\frac{\sum_{x\in P^{*}}dis(x,\Omega)}{|P^{*}|},$

where $dis(x,\Omega)$ is the minimum Euclidean distance between $x$ and points in $\Omega$ , and $|P^{*}|$ denotes the number of elements in $P^{*}$ . The set of reference points required for calculating IGD values are uniformly selected from the Pareto optimal front of each test problem, and a set size closest to 5000 is used in this paper, where the exact number is displayed in Table 4.

Figure 6.

The non-dominated front obtained by each algorithm on DTLZ1 with ten objectives in the run associated with the best IGD value.

The second performance metric adopted in this paper is the hypervolume (HV) [44]. Generally, hypervolume is favored because it captures in a single scalar both the closeness of the solutions to the optimal set and, to some extent, the spread of the solutions across objective space. Given a solution set $\Omega$ , the HV value of $\Omega$ is defined as the area covered by $\Omega$ with respect to a set of predefined reference points $P^{*}$ in the objective space:

$\text{HV}(P^{*},\Omega)=\lambda(H(\Omega,P^{*})),$

where

$\displaystyle H(\Omega,P^{*})=\{z\in Z|\exists x\in\Omega,\exists r\in P^{*}:$ $\displaystyle f(x)\leqslant z\leqslant r\},$

and $\lambda$ is the Lebesgue measure with

$\lambda(H(P^{*},\Omega))=\int_{\mathbb{P^{*}}^{n}}l_{H(P^{*},\Omega)}(z)dz,$

where $l_{H(P^{*},\Omega)}$ is the characteristic function of $H(P^{*},$ $\Omega)$ .

Note that, a smaller value of IGD will indicate a better performance of the algorithm; in contrast, a greater value of HV will indicate a better performance of the algorithm.

3.2 Experimental results and comparison

In the following, we verify the performance of the proposed RdEA on test problems with regular fronts and those with irregular fronts.

3.2.1 Performance on MaOPs with regular fronts

Table 5 presents the IGD values of the compared algorithms on ten MaOP test problems with regular Pareto fronts, where the best result achieved by the algorithms on each test instance is highlighted. From Table 5, we can find that the proposed RdEA holds a competitive performance on the test problems with regular Pareto fronts in terms of both convergence and distribution of obtained solution set. Among the 30 test instances belonging to this category, RdEA obtains 8 best IGD values, while NSGA-III, KnEA, $\theta$ -DEA and KnEA achieve 7, 6 and 6 best values, respectively.

The final non-dominated solutions achieved by each algorithm on DTLZ1 with 10 objectives are displayed in Fig. 6. It can be observed that the proposed RdEA has achieved a set of totally converged and uniformly distributed solutions. Therefore, it can be concluded that the performance of proposed RdEA is competitive with the other five state-of-the-art MaOEAs on MaOPs with regular Pareto fronts, especially for the performance in the distribution of obtained solution set.

3.2.2 Performance on MaOPs with irregular Pareto fronts

Tables 6 and 7 show the IGD and HV values achieved by the compared algorithms on the six benchmark problems with irregular Pareto fronts, where the best result achieved by the algorithms on each test instance is highlighted. It can be found from the tables that the proposed RdEA outperforms the five compared MaOEAs on MaOPs with irregular fronts in terms of IGD values. Among these test instances with irregular fronts, RdEA achieves 14 best IGD values out of 18 test instances. It seems that KnEA also holds a competitive average performance on problems with irregular Pareto fronts, whose number of the best IGD values is ranked the second among the six considered algorithms. In Table 7, RdEA achieves 9 best results on 18 test instances, which is the best among the six algorithms under consideration. Therefore, we can conclude that the proposed RdEA outperforms the five compared algorithms on MaOPs with irregular Pareto fronts, in terms of both convergence and distribution.

To take a closer look at the distribution difference between the final non-dominated solutions achieved by different algorithms, Figs 7–9 depict the non-dominated solutions with the lowest IGD values obtained by each algorithm among 20 runs in the objective space on four test problems with irregular Pareto fronts, namely, DTLZ5, DTLZ7 and WFG1. These three test problems are used for describing three classes of irregular Pareto fronts, namely, degenerated, discontinuous and convex.

Figure 7.

The non-dominated front obtained by each algorithm on DTLZ5 with three objectives in the run associated with the best IGD value.

Figure 8.

The non-dominated front obtained by each algorithm on DTLZ7 with three objectives in the run associated with the best IGD value.

Figure 9.

The non-dominated front obtained by each algorithm on WFG1 with three objectives in the run associated with the best IGD value.

As seen from Fig. 7, the Pareto optimal front of 3-objective DTLZ5 is a degenerated line. It can be found that NSGA-III and KnEA have a promising performance in obtaining uniformly distributed solutions on DTLZ5. Compared to these two algorithms, the proposed RdEA can achieve a better distribution on DTLZ5. As for DTLZ7 with three objectives, its Pareto front consists of four discontinuous sub-fronts. From Fig. 8, we can find that it is hard for all six algorithms to achieve a set of uniformly distributed solutions in each of the four sub-fronts of 3-objective DTLZ7. It seems that KnEA and RdEA can obtain a slightly better distribution than the other four algorithms on DTLZ7 with three objectives. Similar results can be observed from Fig. 9 for WFG1 with three objectives, whose Pareto optimal front is a convex curve in the first quadrant of the objective space. The RVEA and the proposed RdEA seems to perform better than the other four algorithms in terms of distribution, despite that this issue is hard for all algorithms on 3-objective WFG1.

Figure 10.

Design variables of the vehicle model.

Figure 11.

The non-dominated front obtained by each algorithm on crash-worthiness design of vehicles for complete trade-off front.

From Figs 7–9, we can therefore conclude that the proposed RdEA holds a competitive performance on MaOPs with irregular Pareto fronts in terms of distribution. Therefore, the proposed RdEA is well suited to solve MaOPs in obtaining a set of uniformly distributed solutions, especially for those with irregular Pareto fronts.

In the proposed RdEA, the non-dominated sorting method is adopted to rank the solutions in terms of Pareto dominance relationship. It is import for RdEA as the better converged solutions (non-dominated solutions) can be distinguished for accelerating the convergence rate of the algorithm. In [36], an approximate efficient non-dominated sorting (A-ENS) approach is proposed for many-objective optimization, where the approximate dominance relationship between two solutions is determined by a maximum of three objective comparisons on top of a sorted population according to one of the objectives. Besides, a decision variable clustering-based evolutionary algorithm, named LMEA, is proposed for large-scale many-objective optimization [37] (with more than 100 decision variables), where the decision variable clustering method is adopted to divide the decision variables into convergence-related variables and diversity-related variables. The performance of RdEA, A-ENS, and LMEA on 10-objective DTLZ2 and DTLZ7 with up to 100 decision variables are investigated. Note that, A-ENS is used in NSGA-III to achieve the best performance, and the population size for these algorithms is set to 215 with the maximum number of iterations being set to 500 on all these test instances. The IGD results achieved by RdEA, A-ENS, and LMEA are displayed in Table 8. From the comparison results, we can find that the proposed algorithm is more suited to deal with many-objective with irregular fronts in case the length of decision variables is not large.

4. Problem from practice

One important engineering problem, namely crash-worthiness design of vehicles (CSDV) for complete trade-off front [49] in the area of vehicles design, is used as application example to test the performance of the proposed RdEA on solving real-world engineering problem.

The CSDV problem aims at structural optimization of the frontal structure of vehicles for crash-worthiness, where the thickness of five reinforced members around the frontal structure are chosen as the decision variables. Figure 10 presents the design variables (denoted by $t_{1},t_{2},\ldots,t_{5}$ ) of the vehicle model (this figure is cited from [49]). The optimization problem consists of finding the values of the thickness $[t_{1},$ $t_{2},$ $\ldots,t_{5}]$ such that the three objectives in the following are minimized simultaneously:

(1) (1)
The mass of vehicle.
(2)
Deceleration during the full frontal crash (which is proportional to biomechanical injuries caused to the occupants).
(3)
Toe board intrusion in the offset-frontal crash (which accounts for the structural integrity of the vehicle).

Further details regarding the CSDV model can be found in [26, 49].

The proposed RdEA has been tested to solve the CSDV problem and its performance has been compared with MOEA/D, NSGA-III, $\theta$ -DEA, KnEA and RVEA. The population size is set to 65 and the iteration number is set to 100, other specific parameter setting is the same mentioned above, and the number of division in RdEA is set to 4.

The final non-dominated solutions obtained by the six compared algorithms are displayed in Fig. 11. The HV values achieved by these algorithms over 20 runs are obtained: MOEA/D (1.78e $+$ 2), NSGA-III (2.29e $+$ 2), $\theta$ -DEA (2.14e $+$ 2), KnEA (2.18e $+$ 2), RVEA (2.03e $+$ 2), and RdEA (2.42e $+$ 2). Compared with results obtained by the other five compared algorithms, the proposed RdEA has achieved the best result on this problem (a larger HV value indicates a better performance).

Note that, the difficult for solving CSDV lies in the nonlinearity of this problem, where its Pareto optimal front is a discontinuous 3-dimensional surface with a hole in the central region. Existing MaOEAs fail to obtain a set of representative solutions which are spread on the entire approximation Pareto front, e.g., MOEA/D has obtained a set of solutions distributed on part of the approximation Pareto front, and RVEA fail to find the solutions around the hole of the approximation Pareto front. This problem demonstrates the overall performance of RdEA in finding a representative set of points on the entire Pareto optimal front, where the practical problem is hard for existing methods due to the differences in scaling of objectives and complex Pareto optimal front (such as potential holes in the Pareto optimal front, etc.).
5. Conclusion

In this paper, a region division based diversity maintaining approach has been proposed for many-objective optimization. For solving MaOPs with irregular Pareto fronts better, the proposed approach uses geometric information of the front obtained by non-dominated solutions at each generation in region division. An evolutionary algorithm, termed RdEA, has also been suggested to solve MaOPs based on the proposed region division approach. Experimental results have indicated that the proposed RdEA holds a competitive performance in solving both MaOPs with regular Pareto fronts and those with irregular fronts. Compared to the five popular MOEAs, MOEA/D, NSGA-III, $\theta$ -DEA, RVEA and KnEA, the proposed RdEA demonstrates a better average performance in obtaining a set of uniformly distributed solutions on MaOPs with irregular Pareto fronts.

The work developed in this paper shows that the idea of using geometric information of Pareto fronts is a very promising approach to solve MaOPs with irregular fronts. Instead of introducing preference information to set some preferred optimization direction, the geometric information of the population is calculated from generation to generation, which can adaptively enhance the diversity maintaining ability of the proposed approach. In addition, experimental results on a real-world application, named car-worthiness design of vehicles, have verified the efficiency of the proposed RdEA on obtaining a set of uniformly distributed and well converged solutions, which offers a representative set of solutions for the decision makers. Future work on developing more effective region division approaches by taking use of the geometric information of Pareto fronts is highly desirable. It also deserves to be further investigated how to capture the exact geometric information of Pareto fronts, which could greatly improve the performance of the proposed algorithm for solving MaOPs with irregular fronts. Besides, the use of machine learning techniques [50, 51] can be adopted for calculating the curvature and boundary instead of the approximation calculation used in this paper, and parallel techniques can be used for improving the efficiency of the algorithm [52].

Footnotes

Here, the meaning of “uniformly” is as follows. If a point sequence $\{Pi\}:P_{i}=(p_{i,1},p_{i,2},\ldots,p_{i,n})$ , $i=0,1,\ldots,N-1$ , is given in $n$ -dimensional unit hyper-cube $C^{n}$ , the point sequence $\{P_{i}\}$ is uniformly distributed when the following equality holds: $\lim_{N\rightarrow\infty}\frac{S_{N}(D)}{N}=V_{D},∼{}\forall D\subseteq C^{n},% \vspace*{-2pt}$ where $D\subseteq C^{n}$ is an arbitrary hypercube with positive volume $V_{D}>0$ , and $S_{N}(D)$ is the number of points from the sequence belonging to this arbitrary hypercube. The geometrical interpretation of this equation is that when the number of points $N$ is large enough, the number of points $S_{N}(D)$ , belonging to an arbitrary hypercube $D$ , is proportional to its volume $V_{D}$ [23, ].

Acknowledgments

This work was supported by National Natural Science Foundation of China (61272152, 61320106005, 61502004, 61502001, and 61672033) and the Innovation Scientists and Technicians Troop Construction Projects of Henan Province (154200510012).

References

Coletta

LFS

Hruschka

Acharya

, et al. Using metaheuristics to optimize the combination of classifier and cluster ensembles. Integrated Computer-Aided Engineering. 2015; 22(3): 229–242.

Joly

Verstraete

Paniagua

. Integrated multifidelity, multidisciplinary evolutionary design optimization of counterrotating compressors. Integrated Computer-Aided Engineering. 2014; 21(3): 249–261.

Rivas-Dávalos

Irving

. An approach based on the strength Pareto evolutionary algorithm 2 for power distribution system planning. In: Evolutionary Multi-Criterion Optimization. Springer; 2005. p. 707–720.

Campomanes-Álvarez

Cordń

Damas

. Evolutionary multi-objective optimization for mesh simplification of 3D open models. Integrated Computer-Aided Engineering. 2013; 20(4): 375–390.

Rashidi

Ranjitkar

. Bus dwell time modeling using gene expression programming. Computer-Aided Civil and Infrastructure Engineering. 2015; 30(6): 478–489.

Sarma

Adeli

. Data parallel fuzzy genetic algorithm for cost optimization of large space steel structures. International Journal of Space Structures. 2003; 18(3): 195–205.

Vincenzi

Savoia

. Coupling response surface and differential evolution for parameter identification problems. Computer-Aided Civil and Infrastructure Engineering. 2015; 30(5): 376–393.

Jia

Wang

Fan

. Multiobjective bilevel optimization for production-distribution planning problems using hybrid genetic algorithm. Integrated Computer-Aided Engineering. 2014; 21(1): 77–90.

Yang

Emmerich

Bäck

Kok

. Multi-objective inventory routing with uncertain demand using population-based metaheuristics. Integrated Computer-Aided Engineering. 2016; 23(3): 205–220.

10.

Bolourchi

Masri

Aldraihem

. Studies into computational intelligence and evolutionary approaches for model-free identification of hysteretic systems. Computer-Aided Civil and Infrastructure Engineering. 2015; 30(5): 330–346.

11.

Pires

EJS

de Moura

Oliveira

Machado

JAT

. Multi-objective genetic manipulator trajectory planner. In: Applications of Evolutionary Computing. Springer; 2004. p. 219–229.

12.

Sarma

Adeli

. Life-cycle cost optimization of steel structures. International Journal for Numerical Methods in Engineering. 2002; 55(12): 1451–1462.

13.

Coello

CAC

. Evolutionary multi-objective optimization: A historical view of the field. Computational Intelligence Magazine, IEEE. 2006; 1(1): 28–36.

14.

Khare

Yao

Deb

. Performance scaling of multiobjective evolutionary algorithms. In: Proceedings of the Second International Conference on Evolutionary Multi-Criterion Optimization. Springer; 2003. p. 376–390.

15.

Farina

Amato

. A fuzzy definition of “optimality” for many-criteria optimization problems. IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans. 2004; 34(3): 315–326.

16.

Kociecki

Adeli

. Shape optimization of free-form steel space-frame roof structures with complex geometries using evolutionary computing. Engineering Applications of Artificial Intelligence. 2015; 38: 168–182.

17.

Sarma

Adeli

. Fuzzy genetic algorithm for optimization of steel structures. Journal of Structural Engineering. 2000; 126(5): 596–604.

18.

Deb

. Multi-objective optimization using evolutionary algorithms. vol. 16. John Wiley & Sons; 2001.

19.

Zhou

Zhao

Suganthan

Zhang

. Multiobjective evolutionary algorithms: A survey of the state of the art. Swarm and Evolutionary Computation. 2011; 1(1): 32–49.

20.

Rostami

Neri

. Covariance matrix adaptation Pareto archived evolution strategy with hypervolume-sorted adaptive grid algorithm. Integrated Computer-Aided Engineering. 2016; 23(4): 313–329.

21.

Lee

Arditi

. An advanced stochastic time-cost tradeoff analysis based on a CPM-guided genetic algorithm. Computer-Aided Civil and Infrastructure Engineering. 2015; 30(10): 824–842.

22.

Ishibuchi

Setoguchi

Masuda

Nojima

. Performance of Decomposition-Based Many-Objective Algorithms Strongly Depends on Pareto Front Shapes. IEEE Transactions on Evolutionary Computation. 2016.

23.

Georgieva

Jordanov

. A hybrid meta-heuristic for global optimisation using low-discrepancy sequences of points. Computers & Operations Research. 2010; 37(3): 456–469.

24.

Niederreiter

. Random number generation and quasi-Monte Carlo methods. SIAM; 1992.

25.

Zhang

. MOEA/D: A multi-objective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation. 2007; 11(6): 712–731.

26.

Deb

Jain

. An evolutionary many-objective optimization algorithm using reference-point based non-dominated sorting approach, part I: solving problems with box constraints. IEEE Transactions on Evolutionary Computation. 2014; 18(4): 577–601.

27.

Yuan

Wang

Yao

. A new dominance relation based evolutionary algorithm for many-objective optimization. IEEE Transactions on Evolutionary Computation. 2016; 20(1): 16–37.

28.

Cheng

Jin

Olhofer

Sendhoff

. A reference vector guided evolutionary algorithm for many-objective optimization. IEEE Transactions on Evolutionary Computation. 2016; 20(5): 773–791.

29.

Liu

. MOEA/D with adaptive weight adjustment. Evolutionary Computation. 2014; 22(2): 231–264.

30.

Liu

Zhang

. Decomposition of a multiobjective optimization problem into a number of simple multiobjective subproblems. IEEE Transactions on Evolutionary Computation. 2014; 18(3): 450–455.

31.

Chen

Liu

. A region decomposition-based multi-objective particle swarm optimization algorithm. International Journal of Pattern Recognition and Artificial Intelligence. 2014; 28(8): 1459009.

32.

Yang

Liu

Zheng

. A grid-based evolutionary algorithm for many-objective optimization. IEEE Transactions on Evolutionary Computation. 2013; 17(5): 721–736.

33.

Shabbir

Omenzetter

. Particle swarm optimization with sequential niche technique for dynamic finite element model updating. Computer-Aided Civil and Infrastructure Engineering. 2015; 30(5): 359–375.

34.

Parsons

Haque

Liu

. Subspace clustering for high dimensional data: A review. ACM SIGKDD Explorations Newsletter. 2004; 6(1): 90–105.

35.

Zhang

Tian

Cheng

Jin

. An efficient approach to non-dominated sorting for evolutionary multi-objective optimization. IEEE Transactions on Evolutionary Computation. 2015; 19(2): 201–213.

36.

Zhang

Tian

Jin

. Approximate non-dominated sorting for evolutionary many-objective optimization. Information Sciences. 2016, in press.

37.

Zhang

Tian

Jin

Cheng

. A decision variable clustering-based evolutionary algorithm for large-scale many-objective optimization. IEEE Transactions on Evolutionary Computation. 2016, in press.

38.

Kociecki

Adeli

. Two-phase genetic algorithm for topology optimization of free-form steel space-frame roof structures with complex curvatures. Engineering Applications of Artificial Intelligence. 2014; 32: 218–227.

39.

Deb

Thiele

Laumanns

Zitzler

. Scalable test problems for evolutionary multiobjective optimization. Springer; 2005.

40.

Pan

Tian

Zhang

. An improved reference point sampling method on Pareto optimal front. In: 2016 IEEE Congress on Evolutionary Computation (CEC). IEEE; 2016. p. 5230–5237.

41.

Zhang

Tian

Jin

. A knee point driven evolutionary algorithm for many-objective optimization. IEEE Transactions on Evolutionary Computation. 2015; 19(6): 761–776.

42.

Huband

Hingston

Barone

While

. A review of multiobjective test problems and a scalable test problem toolkit. IEEE Transactions on Evolutionary Computation. 2006; 10(5): 477–506.

43.

Zhou

Jin

Zhang

. Combining model-based and genetics-based offspring generation for multi-objective optimization using a convergence criterion. In: 2006 IEEE Congress on Evolutionary Computation. IEEE; 2006. p. 892–899.

44.

While

Hingston

Barone

Huband

. A faster algorithm for calculating hypervolume. IEEE Transactions on Evolutionary Computation. 2006; 10(1): 29–38.

45.

Tian

Cheng

Zhang

Jin

. PlatEMO: A MATLAB platform for evolutionary multi-objective optimization. arXiv preprint arXiv: 170100879. 2017.

46.

Deb

. Multi-Objective Optimization Using Evolutionary Algorithms. New York: Wiley; 2001.

47.

Deb

Goyal

. A combined genetic adaptive search (GeneAS) for engineering design. Computer Science and Informatics. 1996; 26: 30–45.

48.

Ishibuchi

Hitotsuyanagi

Tsukamoto

Nojima

. Many-objective test problems to visually examine the behavior of multiobjective evolution in a decision space. In: International Conference on Parallel Problem Solving from Nature. Springer; 2010. p. 91–100.

49.

Liao

Yang

Zhang

. Multiobjective optimization for crash safety design of vehicles using stepwise regression model. Structural and Multidisciplinary Optimization. 2008; 35(6): 561–569.

50.

Adeli

Hung

. Machine learning: neural networks, genetic algorithms, and fuzzy systems. John Wiley & Sons, Inc.; 1994.

51.

Adeli

Kumar

. Distributed computer-aided engineering. vol. 2. CRC Press; 1998.

52.

Adeli

Sarma

. Cost optimization of structures: fuzzy logic, genetic algorithms, and parallel computing. John Wiley & Sons; 2006.

A region division based diversity maintaining approach for many-objective optimization

Abstract

Keywords

1. Introduction

2.1 General framework of RdEA

3. Experimental results and discussions

3.1 Experimental settings

3.1.1 Test problems

Table 3 Setting of population size in NSGA-III, MOEA/D, θ -DEA and RVEA, where p 1 and p 2 are parameters controlling the numbers of weight vectors along the boundary of the Pareto front and inside it, respectively

3.2.1 Performance on MaOPs with regular fronts

3.2.2 Performance on MaOPs with irregular Pareto fronts

Footnotes

Acknowledgments

References

Table 3
Setting of population size in NSGA-III, MOEA/D, $\theta$ -DEA and RVEA, where $p_{1}$ and $p_{2}$ are parameters controlling the numbers of weight vectors along the boundary of the Pareto front and inside it, respectively