# Evolutionary Search with Multiple Utopian Reference Points in Decomposition-Based Multiobjective Optimization

Authors: Wu Lin; Qiuzhen Lin; Zexuan Zhu; Jianqiang Li; Jianyong Chen; Zhong Ming
Journal: Complexity
 (2019)

---

## Abstract

Decomposition-based multiobjective evolutionary algorithms (MOEA/Ds) have become increasingly popular in recent years. In these MOEA/Ds, evolutionary search is guided by the used weight vectors in decomposition function to approximate the Pareto front (PF). Generally, the decomposition function will be constructed by the weight vectors and the reference point, which play an important role to balance convergence and diversity during the evolutionary search. However, in most existing MOEA/Ds, only one ideal point is used as the reference point for all the evolutionary search, which is harmful to search the entire PF when tackling the problems with difficult-to-approximate PF boundaries. To address the above problem, this paper proposes an evolutionary search method with multiple utopian reference points in MOEA/Ds. Similar to the existing MOEA/Ds, each solution is associated with one weight vector, which provides an evolutionary search direction, while the novelty of our approach is to use multiple utopian reference points, which can provide evolutionary search directions for different weight vectors. Corner solutions are used to approximate the nadir point and then multiple utopian reference points for evolutionary search can be constructed based on the ideal point and the nadir point, which are uniformly distributed on the coordinate axis or planes. The use of these utopian points can prevent solutions to gather in the same region of PF and helps to strike a good balance of exploration and exploitation in the search space. The performance of our proposed algorithm is validated on tackling 16 recently proposed test problems with difficult-to-approximate PF boundaries and empirically compared to eight state-of-the-art multiobjective evolutionary algorithms. The experimental results demonstrate the superiority of the proposed algorithm on solving most of the test problems adopted.


---

## Body

## 1. Introduction

In some real-world applications [1–3], there are many problems involving the optimization of multiple (often conflicting) objectives, which are termed multiobjective optimization problems (MOPs). In general, a MOP can be defined mathematically as follows:(1)minx∈ΩFx=f1x,…,fmxT,where Ω∈Rn is then-dimensional decision (variable) space (n is the number of decision variables), x=(x1,…,xn)T is a decision vector in Ω, and the objective vectorF(x) consists ofm objective functions f1(x),…,fm(x). Usually, the output of MOPs will be a set of tradeoff solutions for all the objectives, called Pareto-optimal solutions (PS). The mapping of PS on the objective space is called Pareto-optimal front (PF). Traditional mathematical methods are difficult to obtain a subset of PS in a single run, while multiobjective evolutionary algorithms (MOEAs) can use a population composed of many individuals to approximate the PF, which are popular for tackling MOPs [4–6]. Compared with traditional mathematical methods, MOEAs can well solve various kinds of MOPs without their differentiable and derivable characteristics. Due to these advantages, MOEAs have been very popular in recent years [7–10].Most of MOEAs can be classified to three categories based on the selection mechanisms:(1) Pareto-based MOEAs [11–14]; (2) indicator-based MOEAs [15, 16]; and (3) decomposition-based MOEAs [17, 18]. In fact, there are only two main tasks in the optimization process of MOEAs. The first one is to ensure convergence, i.e., MOEAs should have the convergence power to push its population towards the PF, while the second one is to maintain diversity, i.e., MOEAs should search a set of solutions uniformly distributed along the PF. Despite the equal importance of both tasks, most state-of-the-art MOEAs follow the principle of convergence first and diversity second, such as NSGA-II [11], SPEA2 [12], MDMOEA [13], and CA-MOEA [14]. Specifically, in MDMOEA [13], a new dominance relation, i.e., L-dominance, is proposed to better balance convergence and diversity when solving many-objective optimization problems. For MOPs with irregular PFs, CA-MOEA [14] uses the clustering method to detect the distribution of individuals in the objective space and then selects individuals according to cluster centers in the last nondominated front. In these MOEAs [11–14], nondominated solutions are selected in priority into the next generation for ensuring convergence, which will induce the diversity loss in sense.One popular decomposition-based framework for MOEA (MOEA/D) proposed by Zhanget al. [17] has been widely studied in recent years. Moreover, some improved MOEA/D variants [19–22] are designed to better balance convergence and diversity. In MOEA/D-DE [19], the offspring can replace at mostnr individuals in its neighborhood to prevent diversity loss, wherenr is preset as a small positive integer. For example, in MOEA/D-STM [20] with a stable matching (STM) model, each individual is assigned to one subproblem based on their mutual preference information, trying to balance convergence and diversity during the evolutionary search. Moreover, MOEA/D-ATO [21] adaptively assigns the suitable combination of mating neighborhood size and reproduction operator to each subproblem at different searching stage. In IMOEA/DU [22], a crossover operator based on uniform design and selection strategy based on decomposition are used to help MOEAs to improve the search efficiency. Recently, in MOEA/HD [23], subproblems are layered into different hierarchies, aiming to better balance convergence and diversity during evolution. In MOEA/D-CPDE [24], the best individual in each generation will be regarded as a seed, which will evolve two individuals by cloud generator. In DAA [25], an efficient decomposition-based archiving approach is proposed to dealing with multiobjective optimization problems. On the other hand, recent research studies have indicated that the coevolution mechanism can significantly improve the performance of MOEAs [26, 27]. The basic idea in these MOEAs is to divide a complex system into several modules, which are then evolved separately [26, 28]. For example, MOEA/D-M2M [29] decomposes a MOP into a set of simple MOPs and then solves these simple MOPs in a collaborative manner. Similarly, E-CODBA [30] exploits coevolution, decomposition, and energy laws to come up with good solutions within an acceptable execution time, aiming to solve some real-world applications, i.e., combinatorial bilevel problems. Furthermore, some other heuristic searching algorithms, i.e., particle swarm optimization [31] and immune algorithm [32] are also developed to solving optimization problems.However, it is found in [33–45] that most of MOEA/Ds adopt one single reference point for all the evolutionary search directions, which is harmful for searching the entire PF when tackling MOPs that are characterized with difficult-to-approximate PF boundaries [46]. To solve this kind of MOPs, in this paper, an evolutionary search method with multiple utopian reference points is proposed for MOEA/Ds. Each solution will be associated with one weight vector, which provides an evolutionary search direction. However, in our approach, multiple utopian reference points are used to provide evolutionary search directions for different weight vectors. To summarize, our approach consists of the following features.( 1 ) Different from the existing decomposition approaches, multiple utopian reference points are used to replace the ideal reference point in our proposed decomposition function. The use of these utopian reference points can provide multiple search directions, which will guide the solutions towards their respective utopian reference points. Therefore, our proposed approach can prevent the solutions to gather in the same region of PF and help to strike a good balance of exploration and exploitation in the search space.( 2 ) These utopian reference points are uniformly distributed on the coordinate axis or planes, which are used to provide different evolutionary search directions for different weight vectors. Moreover, they are adaptively adjusted according to the evaluation of the ideal point and the nadir point in each generation. By this way, the evolutionary search directions are adaptively adjusted, which guide solutions to approximate the entire PF during the evolutionary process.The rest of this paper is organized as follows. Section2 provides some useful preliminaries of this paper. Section 3 describes the technical details of the proposed evolutionary search method with multiple utopian reference points and the entire algorithm. The experimental results and related discussions are presented in Sections 4 and 5, respectively. Finally, Section 6 concludes this paper and provides some future directions.


## 2. Preliminaries

### 2.1. Tchebycheff Decomposition

In decomposition approaches, the scalar subproblem is formulated as a weighted aggregation of all the objectives by decomposition function. The TCH decomposition [17] is a commonly used decomposition function in MOEA/Ds, which can be constructed by a weight vector and a reference point. It can be mathematically defined by the following formulation:(2)minx∈Ωgtex∣w,z∗=max1≤i≤mfix-zi∗wi,where z∗ is used as the reference point for the weight vector w=(w1,…,wm)T, wi≥0 for all i∈{1,…,m} and ∑i=1mwi=1. Note that wi is set to be a very small number, say 10−6, in case wi=0. Actually, in most existing MOEA/Ds [19–25], the ideal reference point is usually used as the initial point of all weight vectors, which is estimated by using the best value of each objective found so far during evolution. Note that all the solutions should be dominated by the ideal reference point in the objective space. Thus, it is obvious that fi(x) is larger than zi∗ for all i∈{1,…,m} in the objective space. In the recent study [47], the geometric property of the subproblem’s objective function in the TCH decomposition has been studied in detail. It can be summarized as follows.Proposition 1.
Letzide=(z1ide,…,zmide) be an ideal reference point of (1) and w=(w1,…,wm)T be a positive weight vector. If a given objective vector F(x)=(f1(x),…,fm(x)) is in the line(3)L1:f1x-z1idew1=⋯=fmx-zmidewm,as shown in Figure 1(a). Then(4)gteFx∣w,zide=Fx-zide1,where ·1 denotes thel1-norm.Figure 1
Tchebycheff decomposition with the ideal reference point for the cases: (a)F(x) is located in the lineL1. (b)F(x) is not located in the lineL1.
(a) (b)In the case thatF(x) is not located inL1, the following proposition depicts the geometric property of gte(F(x)∣w,zide).Proposition 2.
Letzide=(z1ide,…,zmide) be an ideal reference point of (1) and w=(w1,…,wm)T be a positive weight vector. Given an objective vector F(x)=(f1(x),…,fm(x)), if F(y)=(f1(y),…,fm(y)) is generated to satisfy two constraints: (1) F(x) and F(y) are located in the same contour line, i.e., gte(F(x)∣w,zide)=gte(F(y)∣w,zide); (2) F(y) lies in the lineL1 as shown in Figure 1(b); we have(5)gteFx∣w,zide=Fy-zide1.The above two propositions demonstrate the geometric property of TCH decomposition in a serious mathematical proof. More details of proofs have been systematically discussed and analyzed in [47].


### 2.2. Different Types of Reference Points

There have been numerous studies of decomposition approaches [35–45] to use different types of reference points for providing evolutionary search directions. According to the position of reference point relative to the true PF in the objective space, there have three main kinds of reference points in existing MOEA/Ds. For clarity, we give the mathematical definitions of three kinds of reference points as follows.Definition 3 (the ideal point).
The ideal pointzide=(z1ide,…,zmide)T is assigned by the best value of each objective in the true PF, as defined by(6)ziide=min⁡fix∣x∈Ω,i∈1,…,m.Definition 4 (the nadir point).
The nadir pointznad=(z1nad,…,zmnad)T is assigned by the worst value of each objective in the true PF, as defined by (7)zinad=max⁡fix∣x∈PS,i∈1,…,m.Definition 5 (the utopian point).
The utopian pointzuto=(z1uto,…,zmuto)T is assigned by an infeasible objective vector that dominates the ideal point, as defined by(8)ziuto=ziide-εi,i∈1,…,m,where εi>0 for all i∈{1,…,m}.As shown in Figure2(a), the ideal point is the most commonly used reference point for search directions (as indicated by the weight vectors), which is estimated by using the best value of each objective found so far during evolution. The use of the ideal reference point can speed up convergence, but it will also cause the loss of diversity. The representative MOEA/Ds, such as MOEA/D [17] and its variants MOEA/D-DE [19], MOEA/D-STM [20], MOEA/D-ATO [21], IMOEA/DU [22], MOEA/HD [23], MOEA/D-CPDE [24], and DAA [25], all adopt the ideal point as the reference point for all the search directions. However, it can be observed from Figure 2(b) that the current population is pushed away from the nadir reference point as far as possible. Therefore, the solutions in the boundary parts of the PF can be easier to be exploited if the nadir point rather than the ideal point is used as the reference point. The existing MOEA/Ds [36–39], i.e., MOEA/D-TPN [37], MOEA/D-MR [38], and PAEA [39], adopt the nadir reference point, which show a better performance to maintain diversity. Moreover, in Figure 2(c), the utopian reference point can be used to explore the new areas in the boundary parts of the PF when tackling the MOPs with difficult-to-approximate PF boundaries, which has been validated in some studies [40–43], like MOEA/D-UP [42] and Global WASF-GA [43]. Furthermore, there are some attempts [44, 45] to use multiple reference points, which are used to ensure good diversity by guiding different solutions to approximate the true PF. As shown in Figure 2(d), multiple reference points rather than the ideal reference point are used to provide search directions for different solutions, which are uniformly distributed along the approximated PF.Figure 2
Four different cases of reference points in decomposition functions: (a) the ideal point; (b) the nadir point; (c) the utopian point; (d) multiple reference points.
(a) (b) (c) (d)


### 2.3. The Motivations of Our Method1

In decomposition approaches, each subproblem is built by using a weight vector and a reference point, which provides an evolutionary search direction for its associated solution. As it is impossible to know the exact ideal point beforehand, an approximate ideal point is often used as the reference point for all the search directions in MOEA/Ds [17, 19–25], which is obtained by using the best value of each objective found so far during evolution. For example, in MOEA/D [17], a set of uniform weight vectors decomposes a MOP into a number of subproblems, which are assigned with the same computational resource in evolutionary search. However, as pointed out in MOEA/D-DRA [48] and MOEA/D-IRA [49], these subproblems are not equally important and the computational resources should be allocated according to the difficulties of subproblems. Especially, when tackling the problems with difficult-to-approximate PF boundaries, solutions in the middle part of the PF are easier to be found, while that in the PF boundaries are difficult to be searched. Thus, the solutions with good convergence in the middle part of the PF will replace the ones close to the PF boundaries with a high probability, which will cause overcrowdedness at the middle part of the PF. As observed in Figure 3(a), the newly generated offspring close to the ideal reference point have a better aggregated function value for their corresponding subproblems, which will replace these parent solutions with poor convergence into the next generation. Once solutions are all trapped into the middle part of the PF, the boundary solutions will be almost impossible to be found due to the restriction of search directions in decomposition approaches. Similarly, as shown in Figure 3(b), although the nadir point is used as the reference point for search directions, the loss of diversity in the PF boundaries still exists when tackling the MOPs with difficult-to-approximate PF boundaries, while its middle part of the PF can be easily found.Figure 3
The missing of boundary PF parts in the cases: (a) the ideal reference point: (b) the nadir reference point.
(a) (b)Therefore, for the problems with difficult-to-approximate PF boundaries, this paper proposes an evolutionary search method with multiple utopian reference points (MUP) in MOEA/Ds, which can avoid overcrowdedness at the middle part of the PF and search the entire PF. Similar to the existing MOEA/Ds, each solution is associated with one weight vector, which can provide an evolutionary search direction. However, the main difference of our approach with the existing MOEA/Ds is that multiple utopian reference points are used to provide evolutionary search directions for different weight vectors. As these utopian reference points are uniformly distributed along all the coordinate axis or planes that are constructed by the ideal reference point and the nadir reference point, a much wider breadth-diversity [46], which indicates how widely the solutions are distributed over the PF, can be obtained in the evolutionary process. Our approach can help to explore the boundary areas on the PF due to the use of multiple utopian reference points. At the same time, all the solutions are guided by their respective utopian reference points to approximate the true PF, which prevents them to gather at the same region of the PF and helps to strike a good balance of exploration and exploitation in the search space.


### 2.4. Related Work of MOEA/Ds

As recently revealed in [35], the reference point providing evolutionary search directions plays a crucial role in balancing convergence and diversity of MOEA/D. Actually, different types of reference points, such as the ideal point, the nadir point, and the utopian point, could have different impacts on the search behaviors of MOEA/Ds. Recently, the nadir point is used in [36–39] as the reference point for strengthening diversity, while the utopian point is adopted in [40–42] as the reference point for all the evolutionary search directions in MOEA/Ds. Both of a utopian point and a generalized nadir point are used simultaneously as the reference points in [43], which indicates that MOEA/Ds can achieve a much wider distribution to approximate the PF if the utopian point rather than the ideal point is treated as the reference point. In the above-mentioned MOEA/Ds, there are at most two reference points adopted to provide search directions. However, in R-MOEA/D [44], a new scalarizing function using a series of new reference points derived from a given reference point in the preference model is proposed, which ensures a much wider spread of approximate solutions. However, this approach only works well on MOPs with two objectives, which cannot be extended for MOPs with more objectives. Similarly, a new scalarization method is proposed in [45] to get a more uniform distribution on the PF. To summarize, the appropriate selection of reference points for evolutionary search directions can improve the performance of MOEA/Ds, which will better balance exploration and exploitation during the evolutionary process.


## 2.1. Tchebycheff Decomposition

In decomposition approaches, the scalar subproblem is formulated as a weighted aggregation of all the objectives by decomposition function. The TCH decomposition [17] is a commonly used decomposition function in MOEA/Ds, which can be constructed by a weight vector and a reference point. It can be mathematically defined by the following formulation:(2)minx∈Ωgtex∣w,z∗=max1≤i≤mfix-zi∗wi,where z∗ is used as the reference point for the weight vector w=(w1,…,wm)T, wi≥0 for all i∈{1,…,m} and ∑i=1mwi=1. Note that wi is set to be a very small number, say 10−6, in case wi=0. Actually, in most existing MOEA/Ds [19–25], the ideal reference point is usually used as the initial point of all weight vectors, which is estimated by using the best value of each objective found so far during evolution. Note that all the solutions should be dominated by the ideal reference point in the objective space. Thus, it is obvious that fi(x) is larger than zi∗ for all i∈{1,…,m} in the objective space. In the recent study [47], the geometric property of the subproblem’s objective function in the TCH decomposition has been studied in detail. It can be summarized as follows.Proposition 1.
Letzide=(z1ide,…,zmide) be an ideal reference point of (1) and w=(w1,…,wm)T be a positive weight vector. If a given objective vector F(x)=(f1(x),…,fm(x)) is in the line(3)L1:f1x-z1idew1=⋯=fmx-zmidewm,as shown in Figure 1(a). Then(4)gteFx∣w,zide=Fx-zide1,where ·1 denotes thel1-norm.Figure 1
Tchebycheff decomposition with the ideal reference point for the cases: (a)F(x) is located in the lineL1. (b)F(x) is not located in the lineL1.
(a) (b)In the case thatF(x) is not located inL1, the following proposition depicts the geometric property of gte(F(x)∣w,zide).Proposition 2.
Letzide=(z1ide,…,zmide) be an ideal reference point of (1) and w=(w1,…,wm)T be a positive weight vector. Given an objective vector F(x)=(f1(x),…,fm(x)), if F(y)=(f1(y),…,fm(y)) is generated to satisfy two constraints: (1) F(x) and F(y) are located in the same contour line, i.e., gte(F(x)∣w,zide)=gte(F(y)∣w,zide); (2) F(y) lies in the lineL1 as shown in Figure 1(b); we have(5)gteFx∣w,zide=Fy-zide1.The above two propositions demonstrate the geometric property of TCH decomposition in a serious mathematical proof. More details of proofs have been systematically discussed and analyzed in [47].


## 2.2. Different Types of Reference Points

There have been numerous studies of decomposition approaches [35–45] to use different types of reference points for providing evolutionary search directions. According to the position of reference point relative to the true PF in the objective space, there have three main kinds of reference points in existing MOEA/Ds. For clarity, we give the mathematical definitions of three kinds of reference points as follows.Definition 3 (the ideal point).
The ideal pointzide=(z1ide,…,zmide)T is assigned by the best value of each objective in the true PF, as defined by(6)ziide=min⁡fix∣x∈Ω,i∈1,…,m.Definition 4 (the nadir point).
The nadir pointznad=(z1nad,…,zmnad)T is assigned by the worst value of each objective in the true PF, as defined by (7)zinad=max⁡fix∣x∈PS,i∈1,…,m.Definition 5 (the utopian point).
The utopian pointzuto=(z1uto,…,zmuto)T is assigned by an infeasible objective vector that dominates the ideal point, as defined by(8)ziuto=ziide-εi,i∈1,…,m,where εi>0 for all i∈{1,…,m}.As shown in Figure2(a), the ideal point is the most commonly used reference point for search directions (as indicated by the weight vectors), which is estimated by using the best value of each objective found so far during evolution. The use of the ideal reference point can speed up convergence, but it will also cause the loss of diversity. The representative MOEA/Ds, such as MOEA/D [17] and its variants MOEA/D-DE [19], MOEA/D-STM [20], MOEA/D-ATO [21], IMOEA/DU [22], MOEA/HD [23], MOEA/D-CPDE [24], and DAA [25], all adopt the ideal point as the reference point for all the search directions. However, it can be observed from Figure 2(b) that the current population is pushed away from the nadir reference point as far as possible. Therefore, the solutions in the boundary parts of the PF can be easier to be exploited if the nadir point rather than the ideal point is used as the reference point. The existing MOEA/Ds [36–39], i.e., MOEA/D-TPN [37], MOEA/D-MR [38], and PAEA [39], adopt the nadir reference point, which show a better performance to maintain diversity. Moreover, in Figure 2(c), the utopian reference point can be used to explore the new areas in the boundary parts of the PF when tackling the MOPs with difficult-to-approximate PF boundaries, which has been validated in some studies [40–43], like MOEA/D-UP [42] and Global WASF-GA [43]. Furthermore, there are some attempts [44, 45] to use multiple reference points, which are used to ensure good diversity by guiding different solutions to approximate the true PF. As shown in Figure 2(d), multiple reference points rather than the ideal reference point are used to provide search directions for different solutions, which are uniformly distributed along the approximated PF.Figure 2
Four different cases of reference points in decomposition functions: (a) the ideal point; (b) the nadir point; (c) the utopian point; (d) multiple reference points.
(a) (b) (c) (d)


## 2.3. The Motivations of Our Method1

In decomposition approaches, each subproblem is built by using a weight vector and a reference point, which provides an evolutionary search direction for its associated solution. As it is impossible to know the exact ideal point beforehand, an approximate ideal point is often used as the reference point for all the search directions in MOEA/Ds [17, 19–25], which is obtained by using the best value of each objective found so far during evolution. For example, in MOEA/D [17], a set of uniform weight vectors decomposes a MOP into a number of subproblems, which are assigned with the same computational resource in evolutionary search. However, as pointed out in MOEA/D-DRA [48] and MOEA/D-IRA [49], these subproblems are not equally important and the computational resources should be allocated according to the difficulties of subproblems. Especially, when tackling the problems with difficult-to-approximate PF boundaries, solutions in the middle part of the PF are easier to be found, while that in the PF boundaries are difficult to be searched. Thus, the solutions with good convergence in the middle part of the PF will replace the ones close to the PF boundaries with a high probability, which will cause overcrowdedness at the middle part of the PF. As observed in Figure 3(a), the newly generated offspring close to the ideal reference point have a better aggregated function value for their corresponding subproblems, which will replace these parent solutions with poor convergence into the next generation. Once solutions are all trapped into the middle part of the PF, the boundary solutions will be almost impossible to be found due to the restriction of search directions in decomposition approaches. Similarly, as shown in Figure 3(b), although the nadir point is used as the reference point for search directions, the loss of diversity in the PF boundaries still exists when tackling the MOPs with difficult-to-approximate PF boundaries, while its middle part of the PF can be easily found.Figure 3
The missing of boundary PF parts in the cases: (a) the ideal reference point: (b) the nadir reference point.
(a) (b)Therefore, for the problems with difficult-to-approximate PF boundaries, this paper proposes an evolutionary search method with multiple utopian reference points (MUP) in MOEA/Ds, which can avoid overcrowdedness at the middle part of the PF and search the entire PF. Similar to the existing MOEA/Ds, each solution is associated with one weight vector, which can provide an evolutionary search direction. However, the main difference of our approach with the existing MOEA/Ds is that multiple utopian reference points are used to provide evolutionary search directions for different weight vectors. As these utopian reference points are uniformly distributed along all the coordinate axis or planes that are constructed by the ideal reference point and the nadir reference point, a much wider breadth-diversity [46], which indicates how widely the solutions are distributed over the PF, can be obtained in the evolutionary process. Our approach can help to explore the boundary areas on the PF due to the use of multiple utopian reference points. At the same time, all the solutions are guided by their respective utopian reference points to approximate the true PF, which prevents them to gather at the same region of the PF and helps to strike a good balance of exploration and exploitation in the search space.


## 2.4. Related Work of MOEA/Ds

As recently revealed in [35], the reference point providing evolutionary search directions plays a crucial role in balancing convergence and diversity of MOEA/D. Actually, different types of reference points, such as the ideal point, the nadir point, and the utopian point, could have different impacts on the search behaviors of MOEA/Ds. Recently, the nadir point is used in [36–39] as the reference point for strengthening diversity, while the utopian point is adopted in [40–42] as the reference point for all the evolutionary search directions in MOEA/Ds. Both of a utopian point and a generalized nadir point are used simultaneously as the reference points in [43], which indicates that MOEA/Ds can achieve a much wider distribution to approximate the PF if the utopian point rather than the ideal point is treated as the reference point. In the above-mentioned MOEA/Ds, there are at most two reference points adopted to provide search directions. However, in R-MOEA/D [44], a new scalarizing function using a series of new reference points derived from a given reference point in the preference model is proposed, which ensures a much wider spread of approximate solutions. However, this approach only works well on MOPs with two objectives, which cannot be extended for MOPs with more objectives. Similarly, a new scalarization method is proposed in [45] to get a more uniform distribution on the PF. To summarize, the appropriate selection of reference points for evolutionary search directions can improve the performance of MOEA/Ds, which will better balance exploration and exploitation during the evolutionary process.


## 3. The Proposed Method

In this section, the generation of multiple utopian points (MUP) is first introduced in Section3.1. Then, the decomposition approach of using MUP is described in Section 3.2, while the incorporation of MUP method into MOEA/D is clarified in Section 3.3.


### 3.1. Generation of Multiple Utopian Points

In existing MOEA/Ds [40–43], a utopian point is usually set as Definition 5. It is clear that the utopian point dominates the ideal point according to this definition. As illustrated in Figure 4, a utopian point is only located in the narrow dominated areas between the ideal point and the origin point, as named by the narrow utopian area in Figure 4.Figure 4
Illustration of a utopian point, narrow utopian area, and dominated area.In this paper, one more generalized formula of the utopian point is given, as mathematically defined by(9)¬∃Fx≺zuto,∀x∈PS.It can be observed from (9) that the utopian area can be extended to a much wider objective space using this general definition. Thus, in other words, the area except for the dominated area of PS can be served as the utopian area.In our proposed decomposition method with MUP, the weight vectors and the reference points are still the critical components. Given a set of uniformly distributed weight vectorsW={w1,…,wN} that is generated by using Das and Dennis’s [50] systematic approach and an ideal reference point that is estimated by using the best value of each objective found so far during evolution, a MOP is decomposed into a set of scalar optimization subproblems by using a decomposition function. Unlike the existing MOEA/Ds [19–25] with only an ideal point, a set of utopian reference points is derived from the ideal point in this paper. Each of these utopian reference points {z1,…,zN} (where zi=(z1i,…,zmi)T and i∈{1,…,N}) can be generated by shifting the ideal reference point along the coordinate axis, as described in (10)(10)zji=zjide+αjwji-min⁡wi,(11)whereαj=zjnad-zjide,j∈1,…,m.The ideal point and the nadir point decide the range of these newly generated utopian points as illustrated in (11). In this paper, we use the corner solutions [50] to compute the nadir point. In fact, theseM corner solutions lying on the objective axes have a good ability in representing the boundary of each objective on the PF, which can be obtained by simultaneously minimizing M-1 objectives. As suggested in [51], the Euclidean distance to the ideal point is considered in the paper, as follows:(12)dm=∑i=1,i≠mMfix-ziide2,m∈1,…,MThen, the corner solution cm can be obtained as follows:(13)cm=arg⁡minx∈Ω⁡dmx,m∈1,…,MThus, the nadir point can be computed by(14)zinad=max1≤m≤Mficm,i∈1,…,MIn our proposed method, each utopian point is associated with a weight vector as illustrated in (10). Although the ideal reference point is inaccurate, the case that solutions are overcrowded around the ideal reference point will not occur as multiple utopian reference points are used to provide evolutionary search directions for different weight vectors. As shown in Figure 5, for MOPs with two objectives, these newly generated utopian reference points are uniformly distributed in the coordinate axis, which are bounded between the ideal point and the nadir point. However, for MOPs with more than two objectives, these utopian reference points will be distributed in the coordinate planes. According to (11), these utopian reference points are adaptively adjusted according to the change of the ideal point and the nadir point during the evolutionary process.Figure 5
An illustration of correlation between a utopian point and its corresponding search direction for two objectives.


### 3.2. Decomposition with MUP

In our proposed decomposition approach, a set of uniformly distributed utopian reference points replaces the ideal reference point to guide the search behaviors of individuals. Due to the replacement of reference point, the classical TCH decomposition function in (2) is not suitable for balancing convergence and diversity in our approach. Therefore, to strike a good balance of exploration and exploitation in the search space, a novel decomposition function is proposed by applying some mild modifications on the classical TCH decomposition function, as mathematically defined by(15)minx∈Ω⁡gutox∣w,zuto=max1≤i≤mfix-ziutowi,where the utopian point is used as the starting point for each search direction generated by (10). Unlike the classical TCH decomposition function in (2), the utopian point rather than the ideal point is used to provide evolutionary search direction for each associated individual, and the absolute operator is removed to allow the objective value of the solution to be smaller than the utopian reference point in some dimensions, i.e., fi(x)<ziuto, where ∃i∈{1,…,m}.Without using the absolute operator in (15), it is obvious that there are two situations in our proposed decomposition function. Actually, there is no difference with the classical TCH decomposition function when the solution is dominated by the utopian reference point. However, if the solution is not dominated by the utopian reference point (i.e., their relationship is nondominated), the objective value of the solution that is smaller than the utopian reference point in one dimension will not play any effect on the aggregated function value of (15), whereas the objective values larger than the utopian reference point in other dimensions will decide the aggregated function value. Of course, according to the definition of utopian point, solutions are impossible to dominate the utopian reference point. Similar to the study in [47], the geometric property of the subproblems’ objective functions is investigated when using (15) for decomposition.Proposition 6.
Letzuto=(z1uto,…,zmuto) be a utopian reference point of (1) and w=(w1,…,wm)T be a positive weight vector. If a given objective vector F(x)=(f1(x),…,fm(x)) is in the line:(16)L2=f1x-z1utow1=⋯=fmx-zmutowm,which is shown in Figure 6(a). Then,(17)gutoFxw,zuto=Fx-zuto1.Figure 6
Tchebycheff decomposition with the utopian reference point.
(a) (b)In the above equation, sincefi(x)≥ziuto for all i∈{1,…,m}, the geometric property of the subproblems’ objective functions is the same with that of the classical TCH decomposition function. According to Proposition 1 introduced in Section 2, Proposition 6 can be tenable by replacing the ideal reference point with the utopian reference point.Proposition 7.
Letzuto=(z1uto,…,zmuto) be a utopian reference point of (1) and w=(w1,…,wm)T be a positive weight vector. Given an objective vector F(x)=(f1(x),…,fm(x)), if F(y)=(f1(y),…,fm(y)) is generated to satisfy two constraints: (1) F(x) and F(y) are located in the same contour line, i.e., guto(F(x)∣w,zuto)=guto(F(y)∣w,zuto); (2) F(y) lies in the line L2 as shown in Figure 6(b); we have(18)gutoFx∣w,zuto=Fy-zuto1In this proposition, there are two different cases according to the dominance relation between the solution and the utopian reference point in the objective space. As shown in Figure6(b), fi(x1)≥ziuto for all i∈{1,…,m}. In this case, there is no difference between our method and the classical TCH approach on the geometric property. Thus, Proposition 7 can be tenable according to Proposition 2. However, there is another case that the solution is nondominated by the utopian reference point. As shown in Figure 6(b), fi(x2)<ziuto for at least one dimension ∃i∈{1,…,m}. The proof is given as follows.Proof.
According to the conditions ofF(y), we get(19)gutoFx2∣w,zuto→1gutoFy∣w,zuto→2Fy-zuto1Remark 8.
In geometry,guto(F(x2)∣w,zuto) is equal to thel1-norm of F(y)-zuto as shown in Figure 6(b). F(y) is the intersection point between the lineL2 and the contour line of guto(F(x2)∣w,zuto) in the objective space, as follows:(20)Fy=f1y,…,fmy=zuto+gutoFx2∣w,zuto·wsince(21)gutoFx2∣w,zuto→1gutoFy∣w,zuto→2f1y-z1utow1=⋯=fmy-zmutowmFor example, given F(x2)=(1,0.5), zuto=(0,1), and w=(1/3,2/3), we can calculate(22)gutoFx2∣w,zuto=max⁡1-01/3,0.5-12/3=3,f1y=z1uto+gutoFx2∣w,zuto·w1=0+3×13=1,f2y=z2uto+gutoFx2∣w,zuto·w2=1+3×23=3.


### 3.3. Incorporation of MUP Method into MOEA/D

In this section, we introduce the framework of our evolutionary search method with MUP in MOEA/Ds, i.e., MOEA/D-MUP, whose pseudocode is given in Algorithm1. At the beginning, a population withN solutions P={x1,…,xN} is initialized in line (1), and a set of uniformly distributed weight vectors W={w1,…,wN} is generated by using the Das and Dennis [50] systematic approach in line (2). Then, theseN solutions are randomly allocated to associate each ofN subproblems. Moreover, for each weight vector wi (i∈{1,…,N}), itsT closest weight vectors are assigned as its neighbors B(i) in lines (3)-(5), where 1≤T≤N. Then, the ideal point will be initialized by finding the best value of each objective and the nadir point will be initialized using the corner solutions in lines (6)-(7), which have been introduced in Section 3.1. Afterward, like other MOEA/Ds [19–25], parent solutions are randomly selected from the neighborhood with a high probability δ in line (11). In this case, the more similar child solutions will be produced to have a good exploitation on the local region. Otherwise, parent solutions are randomly selected from the whole population with a low probability 1-δ in line (13). In this case, a very wide range of child solutions could be generated by evolutionary operators due to the dissimilarity among these parent solutions. After that, two parent solutions are randomly selected in line (15), which are used to generate a new offspring by evolutionary operators in lines (16)-(17), i.e., differential evolution (DE) and polynomial-based mutation [19]. Next, the newly generated offspring will be used to update the ideal point in line (18), and then the neighborhood ofi-th subproblem is also updated by the offspring in line (19). As shown in Algorithm 2, each subproblem is associated with a unique utopian reference point in line (2), which will be used to compute the aggregated function values of solutions. Then, as shown in lines (3)-(5) of Algorithm 2, the compared parent solution will be replaced by the newly generated offspring if the offspring has the smaller aggregated function value. After updating all the neighborhoods of subproblems, the nadir point will be reevaluated by recalculating the corner solutions of the updated population in line (21). If the stopping criterion is not satisfied in line (8), the above evolutionary process will be repeated in lines (9)-(21); otherwise, the final population will be outputted in line (23).Algorithm 1:Framework of MOEA/D using MUP Method.
Input: MOP: the multiobjective optimization problem N: the size of population T: the size of neighborhood δ: probability of local mating Output: a set of solutions ( 1 ) Initialize a set of solutions P={x1,…,xN} ( 2 ) Generate a set of uniformly distributed weight vectors W={w1,…,wN} ( 3 ) for i ← 1 : N do ( 4 )  B(i)←{i1,…,iT}, where wi1,…,wiT are Tclosest weight vectors to wi ( 5 ) end ( 6 ) Initialize the ideal point zide ( 7 ) Initialize the nadir point znadby corner points in population P ( 8 ) while stopping criterion is not satisfied do ( 9 )    fori←1:Ndo ( 10 )     ifrand<δthen ( 11 )      E←B(i) ( 12 )     else ( 13 )    E←{1,…,N} ( 14 )     end ( 15 )     Randomly select two indexes r1, r2 from E ( 16 )     Produce a solution y- from xi,xr1,xr2 by crossover operator ( 17 )     Perform mutation operator on y- to produce a new solution y ( 18 )     Update the ideal reference point zide ( 19 )     Update neighboring solutions by Algorithm 2 ( 20 )    end ( 21 )    Reevaluate the nadir point znad by corner solutions in the updated population ( 22 ) end ( 23 ) return PAlgorithm 2:UpdateNeighboringSolutions.
Input: B(i): the neighboring of the i-th subproblem y: a new generated solution zide: the ideal point znad: the nadir point ( 1 ) for each index j∈B(i)do ( 2 )  Compute the utopian point zj associated with j-th subproblem using Eq. (10) ( 3 )  ifguto(y∣wj,zj)≤guto(xj∣wj,zj) ( 4 )   xj=y ( 5 )  end ( 6 ) end


## 3.1. Generation of Multiple Utopian Points

In existing MOEA/Ds [40–43], a utopian point is usually set as Definition 5. It is clear that the utopian point dominates the ideal point according to this definition. As illustrated in Figure 4, a utopian point is only located in the narrow dominated areas between the ideal point and the origin point, as named by the narrow utopian area in Figure 4.Figure 4
Illustration of a utopian point, narrow utopian area, and dominated area.In this paper, one more generalized formula of the utopian point is given, as mathematically defined by(9)¬∃Fx≺zuto,∀x∈PS.It can be observed from (9) that the utopian area can be extended to a much wider objective space using this general definition. Thus, in other words, the area except for the dominated area of PS can be served as the utopian area.In our proposed decomposition method with MUP, the weight vectors and the reference points are still the critical components. Given a set of uniformly distributed weight vectorsW={w1,…,wN} that is generated by using Das and Dennis’s [50] systematic approach and an ideal reference point that is estimated by using the best value of each objective found so far during evolution, a MOP is decomposed into a set of scalar optimization subproblems by using a decomposition function. Unlike the existing MOEA/Ds [19–25] with only an ideal point, a set of utopian reference points is derived from the ideal point in this paper. Each of these utopian reference points {z1,…,zN} (where zi=(z1i,…,zmi)T and i∈{1,…,N}) can be generated by shifting the ideal reference point along the coordinate axis, as described in (10)(10)zji=zjide+αjwji-min⁡wi,(11)whereαj=zjnad-zjide,j∈1,…,m.The ideal point and the nadir point decide the range of these newly generated utopian points as illustrated in (11). In this paper, we use the corner solutions [50] to compute the nadir point. In fact, theseM corner solutions lying on the objective axes have a good ability in representing the boundary of each objective on the PF, which can be obtained by simultaneously minimizing M-1 objectives. As suggested in [51], the Euclidean distance to the ideal point is considered in the paper, as follows:(12)dm=∑i=1,i≠mMfix-ziide2,m∈1,…,MThen, the corner solution cm can be obtained as follows:(13)cm=arg⁡minx∈Ω⁡dmx,m∈1,…,MThus, the nadir point can be computed by(14)zinad=max1≤m≤Mficm,i∈1,…,MIn our proposed method, each utopian point is associated with a weight vector as illustrated in (10). Although the ideal reference point is inaccurate, the case that solutions are overcrowded around the ideal reference point will not occur as multiple utopian reference points are used to provide evolutionary search directions for different weight vectors. As shown in Figure 5, for MOPs with two objectives, these newly generated utopian reference points are uniformly distributed in the coordinate axis, which are bounded between the ideal point and the nadir point. However, for MOPs with more than two objectives, these utopian reference points will be distributed in the coordinate planes. According to (11), these utopian reference points are adaptively adjusted according to the change of the ideal point and the nadir point during the evolutionary process.Figure 5
An illustration of correlation between a utopian point and its corresponding search direction for two objectives.


## 3.2. Decomposition with MUP

In our proposed decomposition approach, a set of uniformly distributed utopian reference points replaces the ideal reference point to guide the search behaviors of individuals. Due to the replacement of reference point, the classical TCH decomposition function in (2) is not suitable for balancing convergence and diversity in our approach. Therefore, to strike a good balance of exploration and exploitation in the search space, a novel decomposition function is proposed by applying some mild modifications on the classical TCH decomposition function, as mathematically defined by(15)minx∈Ω⁡gutox∣w,zuto=max1≤i≤mfix-ziutowi,where the utopian point is used as the starting point for each search direction generated by (10). Unlike the classical TCH decomposition function in (2), the utopian point rather than the ideal point is used to provide evolutionary search direction for each associated individual, and the absolute operator is removed to allow the objective value of the solution to be smaller than the utopian reference point in some dimensions, i.e., fi(x)<ziuto, where ∃i∈{1,…,m}.Without using the absolute operator in (15), it is obvious that there are two situations in our proposed decomposition function. Actually, there is no difference with the classical TCH decomposition function when the solution is dominated by the utopian reference point. However, if the solution is not dominated by the utopian reference point (i.e., their relationship is nondominated), the objective value of the solution that is smaller than the utopian reference point in one dimension will not play any effect on the aggregated function value of (15), whereas the objective values larger than the utopian reference point in other dimensions will decide the aggregated function value. Of course, according to the definition of utopian point, solutions are impossible to dominate the utopian reference point. Similar to the study in [47], the geometric property of the subproblems’ objective functions is investigated when using (15) for decomposition.Proposition 6.
Letzuto=(z1uto,…,zmuto) be a utopian reference point of (1) and w=(w1,…,wm)T be a positive weight vector. If a given objective vector F(x)=(f1(x),…,fm(x)) is in the line:(16)L2=f1x-z1utow1=⋯=fmx-zmutowm,which is shown in Figure 6(a). Then,(17)gutoFxw,zuto=Fx-zuto1.Figure 6
Tchebycheff decomposition with the utopian reference point.
(a) (b)In the above equation, sincefi(x)≥ziuto for all i∈{1,…,m}, the geometric property of the subproblems’ objective functions is the same with that of the classical TCH decomposition function. According to Proposition 1 introduced in Section 2, Proposition 6 can be tenable by replacing the ideal reference point with the utopian reference point.Proposition 7.
Letzuto=(z1uto,…,zmuto) be a utopian reference point of (1) and w=(w1,…,wm)T be a positive weight vector. Given an objective vector F(x)=(f1(x),…,fm(x)), if F(y)=(f1(y),…,fm(y)) is generated to satisfy two constraints: (1) F(x) and F(y) are located in the same contour line, i.e., guto(F(x)∣w,zuto)=guto(F(y)∣w,zuto); (2) F(y) lies in the line L2 as shown in Figure 6(b); we have(18)gutoFx∣w,zuto=Fy-zuto1In this proposition, there are two different cases according to the dominance relation between the solution and the utopian reference point in the objective space. As shown in Figure6(b), fi(x1)≥ziuto for all i∈{1,…,m}. In this case, there is no difference between our method and the classical TCH approach on the geometric property. Thus, Proposition 7 can be tenable according to Proposition 2. However, there is another case that the solution is nondominated by the utopian reference point. As shown in Figure 6(b), fi(x2)<ziuto for at least one dimension ∃i∈{1,…,m}. The proof is given as follows.Proof.
According to the conditions ofF(y), we get(19)gutoFx2∣w,zuto→1gutoFy∣w,zuto→2Fy-zuto1Remark 8.
In geometry,guto(F(x2)∣w,zuto) is equal to thel1-norm of F(y)-zuto as shown in Figure 6(b). F(y) is the intersection point between the lineL2 and the contour line of guto(F(x2)∣w,zuto) in the objective space, as follows:(20)Fy=f1y,…,fmy=zuto+gutoFx2∣w,zuto·wsince(21)gutoFx2∣w,zuto→1gutoFy∣w,zuto→2f1y-z1utow1=⋯=fmy-zmutowmFor example, given F(x2)=(1,0.5), zuto=(0,1), and w=(1/3,2/3), we can calculate(22)gutoFx2∣w,zuto=max⁡1-01/3,0.5-12/3=3,f1y=z1uto+gutoFx2∣w,zuto·w1=0+3×13=1,f2y=z2uto+gutoFx2∣w,zuto·w2=1+3×23=3.


## 3.3. Incorporation of MUP Method into MOEA/D

In this section, we introduce the framework of our evolutionary search method with MUP in MOEA/Ds, i.e., MOEA/D-MUP, whose pseudocode is given in Algorithm1. At the beginning, a population withN solutions P={x1,…,xN} is initialized in line (1), and a set of uniformly distributed weight vectors W={w1,…,wN} is generated by using the Das and Dennis [50] systematic approach in line (2). Then, theseN solutions are randomly allocated to associate each ofN subproblems. Moreover, for each weight vector wi (i∈{1,…,N}), itsT closest weight vectors are assigned as its neighbors B(i) in lines (3)-(5), where 1≤T≤N. Then, the ideal point will be initialized by finding the best value of each objective and the nadir point will be initialized using the corner solutions in lines (6)-(7), which have been introduced in Section 3.1. Afterward, like other MOEA/Ds [19–25], parent solutions are randomly selected from the neighborhood with a high probability δ in line (11). In this case, the more similar child solutions will be produced to have a good exploitation on the local region. Otherwise, parent solutions are randomly selected from the whole population with a low probability 1-δ in line (13). In this case, a very wide range of child solutions could be generated by evolutionary operators due to the dissimilarity among these parent solutions. After that, two parent solutions are randomly selected in line (15), which are used to generate a new offspring by evolutionary operators in lines (16)-(17), i.e., differential evolution (DE) and polynomial-based mutation [19]. Next, the newly generated offspring will be used to update the ideal point in line (18), and then the neighborhood ofi-th subproblem is also updated by the offspring in line (19). As shown in Algorithm 2, each subproblem is associated with a unique utopian reference point in line (2), which will be used to compute the aggregated function values of solutions. Then, as shown in lines (3)-(5) of Algorithm 2, the compared parent solution will be replaced by the newly generated offspring if the offspring has the smaller aggregated function value. After updating all the neighborhoods of subproblems, the nadir point will be reevaluated by recalculating the corner solutions of the updated population in line (21). If the stopping criterion is not satisfied in line (8), the above evolutionary process will be repeated in lines (9)-(21); otherwise, the final population will be outputted in line (23).Algorithm 1:Framework of MOEA/D using MUP Method.
Input: MOP: the multiobjective optimization problem N: the size of population T: the size of neighborhood δ: probability of local mating Output: a set of solutions ( 1 ) Initialize a set of solutions P={x1,…,xN} ( 2 ) Generate a set of uniformly distributed weight vectors W={w1,…,wN} ( 3 ) for i ← 1 : N do ( 4 )  B(i)←{i1,…,iT}, where wi1,…,wiT are Tclosest weight vectors to wi ( 5 ) end ( 6 ) Initialize the ideal point zide ( 7 ) Initialize the nadir point znadby corner points in population P ( 8 ) while stopping criterion is not satisfied do ( 9 )    fori←1:Ndo ( 10 )     ifrand<δthen ( 11 )      E←B(i) ( 12 )     else ( 13 )    E←{1,…,N} ( 14 )     end ( 15 )     Randomly select two indexes r1, r2 from E ( 16 )     Produce a solution y- from xi,xr1,xr2 by crossover operator ( 17 )     Perform mutation operator on y- to produce a new solution y ( 18 )     Update the ideal reference point zide ( 19 )     Update neighboring solutions by Algorithm 2 ( 20 )    end ( 21 )    Reevaluate the nadir point znad by corner solutions in the updated population ( 22 ) end ( 23 ) return PAlgorithm 2:UpdateNeighboringSolutions.
Input: B(i): the neighboring of the i-th subproblem y: a new generated solution zide: the ideal point znad: the nadir point ( 1 ) for each index j∈B(i)do ( 2 )  Compute the utopian point zj associated with j-th subproblem using Eq. (10) ( 3 )  ifguto(y∣wj,zj)≤guto(xj∣wj,zj) ( 4 )   xj=y ( 5 )  end ( 6 ) end


## 4. Experimental Settings

### 4.1. Test Instance

Sixteen test problems [46] (i.e., F1-F16) featured by difficult-to-approximate PF boundaries are considered as the benchmark problems in our experimental studies. F1-F8 are two-objective optimization problems, while F9-F16 are three-objective optimization problems. As suggested in [46], the number of decision variables is set as 31 in two-objective optimization problems (F1-F8). However, in three-objective optimization problems (F9-F16), the number of decision variables is set as 32. The true PFs of F1-F7 are the same, which can be represented by a straight line in the objective space. The true PF of F8 is convex. Similar to F1-F8, the geometry of the true PFs of F9-F15 is a hyperplane except that the PF of F16 is convex. The design details and control parameters for F1-F16 are introduced in [46].


### 4.2. The Compared Algorithms

Three classical MOEAs (NSGA-II [11], SMS-EMOA [15], and MOEAD/D-DRA [48]) and a modified variant of MOEA/D-DRA (MOEA/D-DRA-UT [46]) are chosen for comparison to assess the performance of the proposed algorithm on F1-F16. NSGA-II is a famous dominance-based MOEA, while SMS-EMOA is a well-known indicator-based MOEA using the hypervolume metric for population diversity maintenance. Moreover, MOEA/D-DRA is a typical decomposition-based MOEA, in which all subproblems are dynamically allocated with different computational resources according to their different computational difficulties in evolution. MOEA/D-DRA-UT is first suggested in [46] and the authors modify MOEA/D-DRA to MOEA/D-DRA-UT by changing the reference point from the ideal point (denoted as zide) to the utopian point (denoted as zuto), where zuto≺zide is under the objective space. As reported in [40–43], using the utopian point as the reference point for all search directions, a much wider spread of approximate solutions can be achieved in MOEA/Ds. Furthermore, for better demonstrating the superiority of our proposed algorithm on F1-F16, four representative MOEA/Ds are also used for comparison, i.e., MOEA/D-STM [20], MOEA/D-M2M [29], MOEA/D-AWA [34], and MOEA/D-PaS [33]. These codes of the compared algorithms are implemented in PlatEMO [52], while the code of MOEA/D-MUP is available at https://github.com/wulinszu/MOEAD-MUP.git.


### 4.3. Parameter Settings

As shown in Table1, the parameters of the compared algorithms, i.e., NSGA-II [11], SMS-EMOA [15], MOEA/D-DRA [48], and other MOEA/D variants (MOEA/D-STM [20], MOEA/D-M2M [29], MOEA/D-AWA [34], and MOEA/D-PaS [33]), are set the same as in their corresponding references. For MOEA/D-DRA-UT, ziuto=ziide-ε, where i∈{1,…,M} and ε is set as a small positive number. As suggested in [46], ε=0.1 is used. However, in MOEA/D-MUP, the neighborhood size is T=0.1N, and the probability used to select in the neighborhood is δ=0.9. The common parameters of these algorithms in our experimental studies are summarized as follows:(1)
The population size:N is set to 200 for F1-F8 and 300 for F9-F16.(2)
Reproduction operators: To be fair, we use DE operator and Polynomial-based mutation for offspring generation in all the compared algorithms except that MOEA/D-M2M employs another recombination operator [53] as suggested in [29]. As recommended in [19], we set CR=1.0 and F=0.5 in DE operation, η=20 and pm=1/n in Polynomial-based mutation operator, where η is the number of decision variables.(3)
The stopping condition and the number of runs: The maximal number of function evaluation is set to 300,000 for all test problems. All the algorithms are run 30 times independently on each test problem.Table 1
Parameter settings of all the compared algorithms.
Algorithm Parameter settings NGSA-II N=200 SMS-EMOA N=200 MOEA/D-DRA N=200, T=0.1N, δ= 0.9, nr= 0.01N MOEA/D-DRA-UT N=200, T=20, δ= 0.9, nr= 2, ε= 0.1 MOEA/D-STM N=200, T=20, δ= 0.9 MOEA/D-M2M N=200, K=0.1N MOEA/D-AWA N=200, rate_update_weight=0.05, rate_evol=0.8, wag=100 MOEA/D-PaS N=200, T=0.1N, δ= 0.9, nr= 0.01N MOEA/D-MUP N=200, T=0.1N, δ= 0.9, nr= 0.1N


### 4.4. Performance Metrics

To compare the performance of all algorithms on test instances, the inverted generational distance (IGD) indicator and the hypervolume indicator (IH) are used in our experiments. A set of solutions uniformly sampled along the true PF is needed for computing the former indicator, i.e., IGD. However, for the later, i.e.,IH, a reference point is necessary. In our experiment, all the nondominated solutions are selected from the final population, which are used to compare the performance of all algorithms in terms of IGD values andIH values.( 1 ) IGD [54]: Let P∗ be a set of solutions which are uniformly sampled along the PF in the objective space. The approximate set (denoted asA in (23)) composes of a set of nondominated solutions, which are selected from the final population obtained by the corresponding algorithm. Then, the IGD value can be computed as follows:(23)IGDP,A=∑i=1P∗min⁡dj=1A⁡si,ajP∗,si∈P∗,aj∈A,where d(si,ai)=(s1i-a1i)2+⋯+(smi-ami)2 andm is the number of objectives. As suggested in [46], 500 representative points are uniformly sampled from the PF to form P∗ for F1-F8, and 1,000 points are chosen as P∗ for F9-F16.( 2 ) I H [55]: Let r=r1,…,rmT be a reference point in the objective space. The approximate set (denoted asA in (24)) composes of a set of nondominated solutions, which are obtained by the corresponding algorithm in the objective space. Then, theIH value is computed as follows:(24)IHA,r=vol⋃a∈Aa1,r1×⋯×am,rm,(25)subjecttoa≺r,∀a∈A,where vol(·) is the Lebesgue measure. As suggested in [29], the reference point r=(1.0,…,1.0)T is considered in our experiments. Please note that all the nondominated solutions inA should dominate the reference point in the objective space.


## 4.1. Test Instance

Sixteen test problems [46] (i.e., F1-F16) featured by difficult-to-approximate PF boundaries are considered as the benchmark problems in our experimental studies. F1-F8 are two-objective optimization problems, while F9-F16 are three-objective optimization problems. As suggested in [46], the number of decision variables is set as 31 in two-objective optimization problems (F1-F8). However, in three-objective optimization problems (F9-F16), the number of decision variables is set as 32. The true PFs of F1-F7 are the same, which can be represented by a straight line in the objective space. The true PF of F8 is convex. Similar to F1-F8, the geometry of the true PFs of F9-F15 is a hyperplane except that the PF of F16 is convex. The design details and control parameters for F1-F16 are introduced in [46].


## 4.2. The Compared Algorithms

Three classical MOEAs (NSGA-II [11], SMS-EMOA [15], and MOEAD/D-DRA [48]) and a modified variant of MOEA/D-DRA (MOEA/D-DRA-UT [46]) are chosen for comparison to assess the performance of the proposed algorithm on F1-F16. NSGA-II is a famous dominance-based MOEA, while SMS-EMOA is a well-known indicator-based MOEA using the hypervolume metric for population diversity maintenance. Moreover, MOEA/D-DRA is a typical decomposition-based MOEA, in which all subproblems are dynamically allocated with different computational resources according to their different computational difficulties in evolution. MOEA/D-DRA-UT is first suggested in [46] and the authors modify MOEA/D-DRA to MOEA/D-DRA-UT by changing the reference point from the ideal point (denoted as zide) to the utopian point (denoted as zuto), where zuto≺zide is under the objective space. As reported in [40–43], using the utopian point as the reference point for all search directions, a much wider spread of approximate solutions can be achieved in MOEA/Ds. Furthermore, for better demonstrating the superiority of our proposed algorithm on F1-F16, four representative MOEA/Ds are also used for comparison, i.e., MOEA/D-STM [20], MOEA/D-M2M [29], MOEA/D-AWA [34], and MOEA/D-PaS [33]. These codes of the compared algorithms are implemented in PlatEMO [52], while the code of MOEA/D-MUP is available at https://github.com/wulinszu/MOEAD-MUP.git.


## 4.3. Parameter Settings

As shown in Table1, the parameters of the compared algorithms, i.e., NSGA-II [11], SMS-EMOA [15], MOEA/D-DRA [48], and other MOEA/D variants (MOEA/D-STM [20], MOEA/D-M2M [29], MOEA/D-AWA [34], and MOEA/D-PaS [33]), are set the same as in their corresponding references. For MOEA/D-DRA-UT, ziuto=ziide-ε, where i∈{1,…,M} and ε is set as a small positive number. As suggested in [46], ε=0.1 is used. However, in MOEA/D-MUP, the neighborhood size is T=0.1N, and the probability used to select in the neighborhood is δ=0.9. The common parameters of these algorithms in our experimental studies are summarized as follows:(1)
The population size:N is set to 200 for F1-F8 and 300 for F9-F16.(2)
Reproduction operators: To be fair, we use DE operator and Polynomial-based mutation for offspring generation in all the compared algorithms except that MOEA/D-M2M employs another recombination operator [53] as suggested in [29]. As recommended in [19], we set CR=1.0 and F=0.5 in DE operation, η=20 and pm=1/n in Polynomial-based mutation operator, where η is the number of decision variables.(3)
The stopping condition and the number of runs: The maximal number of function evaluation is set to 300,000 for all test problems. All the algorithms are run 30 times independently on each test problem.Table 1
Parameter settings of all the compared algorithms.
Algorithm Parameter settings NGSA-II N=200 SMS-EMOA N=200 MOEA/D-DRA N=200, T=0.1N, δ= 0.9, nr= 0.01N MOEA/D-DRA-UT N=200, T=20, δ= 0.9, nr= 2, ε= 0.1 MOEA/D-STM N=200, T=20, δ= 0.9 MOEA/D-M2M N=200, K=0.1N MOEA/D-AWA N=200, rate_update_weight=0.05, rate_evol=0.8, wag=100 MOEA/D-PaS N=200, T=0.1N, δ= 0.9, nr= 0.01N MOEA/D-MUP N=200, T=0.1N, δ= 0.9, nr= 0.1N


## 4.4. Performance Metrics

To compare the performance of all algorithms on test instances, the inverted generational distance (IGD) indicator and the hypervolume indicator (IH) are used in our experiments. A set of solutions uniformly sampled along the true PF is needed for computing the former indicator, i.e., IGD. However, for the later, i.e.,IH, a reference point is necessary. In our experiment, all the nondominated solutions are selected from the final population, which are used to compare the performance of all algorithms in terms of IGD values andIH values.( 1 ) IGD [54]: Let P∗ be a set of solutions which are uniformly sampled along the PF in the objective space. The approximate set (denoted asA in (23)) composes of a set of nondominated solutions, which are selected from the final population obtained by the corresponding algorithm. Then, the IGD value can be computed as follows:(23)IGDP,A=∑i=1P∗min⁡dj=1A⁡si,ajP∗,si∈P∗,aj∈A,where d(si,ai)=(s1i-a1i)2+⋯+(smi-ami)2 andm is the number of objectives. As suggested in [46], 500 representative points are uniformly sampled from the PF to form P∗ for F1-F8, and 1,000 points are chosen as P∗ for F9-F16.( 2 ) I H [55]: Let r=r1,…,rmT be a reference point in the objective space. The approximate set (denoted asA in (24)) composes of a set of nondominated solutions, which are obtained by the corresponding algorithm in the objective space. Then, theIH value is computed as follows:(24)IHA,r=vol⋃a∈Aa1,r1×⋯×am,rm,(25)subjecttoa≺r,∀a∈A,where vol(·) is the Lebesgue measure. As suggested in [29], the reference point r=(1.0,…,1.0)T is considered in our experiments. Please note that all the nondominated solutions inA should dominate the reference point in the objective space.


## 5. Experimental Studies

In this section, we present and discuss the comparisons of MOEA/D-MUP with other state-of-the-art algorithms. Three classical algorithms (NSGA-II, SMS-MOEA, and MOEA/D-DRA), and a competitive algorithm with the utopian reference point (MOEA/D-DRA-UT) are chosen for comparison. Experimental results obtained by the above four algorithms in terms of the two common indicators, i.e., IGD andIH, are shown in Tables 2 and 3, respectively. In addition, four representative MOEA/D variants such as MOEA/D-STM, MOEA/D-M2M, MOEA/D-AWA and MOEA/D-PaS are also chosen to further validate the superiority of our proposed algorithm. The values of IGD andIH obtained by the four MOEA/D variants are shown in Tables 4 and 5, respectively. Please note that the final nondominated solutions with the median IGD values obtained by different algorithms in 30 runs are plotted in Figures 8 and 9.Table 2
Mean and standard deviation of IGD values obtained by four classical algorithms and MOEA/D-MUP.
Problem NSGA-II SMS-EMOA MOEA/D-DRA MOEA/D-DRA-UT MOEA/D-MUP F1 2.73E-02 (3.07E-03)- 3.43E-02 (5.81E-03)- 1.88E-02 (1.59E-03)- 3.93E-03 (3.07E-03)- 2.87E-03 (1.44E-04) F2 3.28E-02 (2.75E-03)- 4.47E-02 (3.22E-03)- 2.90E-02 (1.86E-03)- 4.02E-03 (2.75E-03)- 3.02E-03 (1.50E-04) F3 4.84E-02 (7.66E-03)- 6.39E-02 (9.64E-03)- 3.80E-02 (3.39E-03)- 5.09E-03 (7.66E-03)- 3.56E-03 (2.52E-04) F4 5.73E-02 (6.22E-03)- 7.50E-02 (5.05E-03)- 4.48E-02 (2.94E-03)- 5.21E-03 (6.22E-03)- 4.00E-03 (5.85E-04) F5 6.35E-02 (2.13E-02)- 8.43E-02 (2.54E-02)- 6.34E-02 (1.22E-02)- 5.14E-03 (2.13E-02)- 4.58E-03 (4.94E-04) F6 8.19E-02 (1.99E-02)- 1.13E-01 (1.55E-02)- 7.10E-02 (8.72E-03)- 6.19E-03 (1.99E-02)- 5.49E-03 (8.24E-04) F7 1.92E-01 (1.07E-02)- 1.77E-01 (6.64E-03)- 1.74E-01 (4.10E-03)= 1.35E-01 (1.07E-02)+ 1.71E-01 (9.01E-03) F8 5.86E-02 (1.60E-02)- 9.17E-02 (1.65E-02)- 6.32E-02 (2.26E-03)- 6.14E-03 (1.60E-02)+ 8.41E-03 (2.91E-03) F9 1.35E-01 (2.27E-02)- 1.02E-01 (7.36E-03)- 5.42E-02 (3.92E-02)- 4.97E-02 (2.27E-02)- 3.56E-02 (8.63E-04) F10 1.29E-01 (2.31E-02)- 1.02E-01 (3.36E-03)- 5.66E-02 (3.54E-02)- 5.62E-02 (2.31E-02)- 3.64E-02 (1.11E-03) F11 1.60E-01 (3.49E-02)- 1.16E-01 (3.48E-03)- 6.89E-02 (5.42E-02)- 6.17E-02 (3.49E-02)- 4.20E-02 (1.74E-03) F12 1.65E-01 (2.51E-02)- 1.18E-01 (3.88E-03)- 7.40E-02 (4.19E-02)- 6.30E-02 (2.51E-02)- 4.41E-02 (1.90E-03) F13 2.03E-01 (5.73E-02)- 1.36E-01 (1.27E-02)- 9.21E-02 (7.91E-02)- 7.32E-02 (5.73E-02)- 5.60E-02 (2.69E-03) F14 1.88E-01 (2.89E-02)- 1.46E-01 (6.56E-03)- 9.80E-02 (3.27E-02)- 7.59E-02 (2.89E-02)- 5.99E-02 (3.59E-03) F15 2.18E-01 (1.57E-02)- 1.99E-01 (3.88E-03)- 1.40E-01 (1.40E-02)- 1.37E-01 (1.57E-02)= 1.37E-01 (5.16E-03) F16 5.35E-02 (9.17E-03)- 7.61E-02 (6.07E-03)- 6.58E-02 (7.53E-03)- 4.23E-02 (9.17E-03)- 3.72E-02 (3.25E-03) +/-/= 0/16/0 0/16/0 0/15/1 2/13/1 ∖ According to Wilcoxon’s rank sum test with a significant levelα=0.05, +, − and = indicate that the corresponding MOEA is significantly better than, worse than or similar to MOEA/D-MUP.Table 3
Mean and standard deviation ofIH values obtained by four classical algorithms and MOEA/D-MUP.
Problem NSGA-II SMS-EMOA MOEA/D-DRA MOEA/D-DRA-UT MOEA/D-MUP F1 4.70E-01 (1.59E-03)- 4.65E-01 (3.24E-03)- 4.80E-01 (3.07E-03)- 4.93E-01 (1.02E-03)- 4.95E-01 (2.93E-04) F2 4.66E-01 (1.86E-03)- 4.58E-01 (1.63E-03)- 4.71E-01 (2.75E-03)- 4.93E-01 (7.69E-04)- 4.95E-01 (2.81E-04) F3 4.50E-01 (3.39E-03)- 4.39E-01 (4.60E-03)- 4.64E-01 (7.66E-03)- 4.91E-01 (2.66E-03)- 4.93E-01 (4.57E-04) F4 4.45E-01 (2.94E-03)- 4.31E-01 (2.38E-03)- 4.57E-01 (6.22E-03)- 4.91E-01 (2.38E-03)- 4.93E-01 (9.87E-04) F5 4.31E-01 (1.22E-02)- 4.14E-01 (1.21E-02)- 4.42E-01 (2.13E-02)- 4.91E-01 (1.28E-03)- 4.92E-01 (7.98E-04) F6 4.19E-01 (8.72E-03)- 3.98E-01 (6.95E-03)- 4.36E-01 (1.99E-02)- 4.89E-01 (2.22E-03)= 4.90E-01 (1.42E-03) F7 3.27E-01 (4.10E-03)- 3.29E-01 (2.78E-03)- 3.35E-01 (1.07E-02)- 3.64E-01 (1.10E-02)+ 3.56E-01 (4.01E-03) F8 7.93E-01 (2.26E-03)- 7.81E-01 (2.23E-03)- 7.83E-01 (1.60E-02)- 8.25E-01 (2.79E-03)= 8.24E-01 (3.87E-03) F9 5.72E-01 (3.92E-02)- 6.16E-01 (2.45E-02)- 6.76E-01 (2.27E-02)- 7.40E-01 (2.53E-02)= 7.38E-01 (7.61E-03) F10 5.60E-01 (3.54E-02)- 5.97E-01 (1.08E-02)- 6.70E-01 (2.31E-02)- 6.99E-01 (1.08E-02)- 7.26E-01 (6.19E-03) F11 5.21E-01 (5.42E-02)- 5.71E-01 (3.13E-02)- 6.34E-01 (3.49E-02)- 6.92E-01 (2.56E-02)- 7.00E-01 (8.77E-03) F12 5.04E-01 (4.19E-02)- 5.57E-01 (1.89E-02)- 6.22E-01 (2.51E-02)- 6.73E-01 (1.42E-02)- 6.89E-01 (8.42E-03) F13 4.54E-01 (7.91E-02)- 5.37E-01 (6.65E-02)- 5.80E-01 (5.73E-02)- 6.48E-01 (1.63E-02)= 6.50E-01 (7.62E-03) F14 4.58E-01 (3.27E-02)- 5.02E-01 (3.22E-02)- 5.69E-01 (2.89E-02)- 6.36E-01 (1.54E-02)= 6.39E-01 (9.76E-03) F15 4.13E-01 (1.40E-02)- 4.17E-01 (3.52E-03)- 4.75E-01 (1.57E-02)- 4.91E-01 (5.18E-03)= 4.90E-01 (4.29E-03) F16 9.18E-01 (7.53E-03)- 4.65E-01 (3.24E-03)- 9.27E-01 (9.17E-03)- 9.51E-01 (3.97E-03)- 9.59E-01 (1.51E-03) +/-/= 0/16/0 0/16/0 0/16/0 1/9/6 ∖ According to Wilcoxon’s rank sum test with a significant levelα=0.05, +, − and = indicate that the corresponding MOEA is significantly better than, worse than or similar to MOEA/D-MUP.Table 4
Mean and standard deviation of IGD values obtained by four representative MOEA/Ds and MOEA/D-MUP.
Problem MOEA/D-STM MOEA/D-M2M MOEA/D-AWA MOEA/D-PaS MOEA/D-MUP F1 1.47E-02 (4.39E-03)- 8.58E-03 (2.01E-03)- 8.43E-02 (2.18E-03)- 1.74E-02 (2.19E-03)- 2.87E-03 (1.44E-04) F2 2.14E-02 (4.00E-03)- 1.25E-02 (2.80E-03)- 8.95E-02 (2.12E-03)- 2.07E-02 (2.09E-03)- 3.02E-03 (1.50E-04) F3 2.80E-02 (7.22E-03)- 1.07E-02 (2.18E-03)- 1.47E-01 (3.64E-03)- 3.12E-02 (3.03E-03)- 3.56E-03 (2.52E-04) F4 3.81E-02 (6.41E-03)- 1.41E-02 (3.25E-03)- 1.54E-01 (2.54E-03)- 3.59E-02 (2.67E-03)- 4.00E-03 (5.85E-04) F5 2.61E-02 (1.95E-02)- 1.52E-02 (4.28E-03)- 2.29E-01 (3.30E-03)- 7.30E-02 (7.81E-02)- 4.58E-03 (4.94E-04) F6 5.16E-02 (1.96E-02)- 1.75E-02 (4.56E-03)- 2.37E-01 (3.00E-03)- 1.39E-01 (1.37E-01)- 5.49E-03 (8.24E-04) F7 1.73E-01 (1.16E-02)= 6.62E-02 (8.57E03)+ 2.54E-01 (1.90E-02)- 2.02E-01 (6.36E-02)- 1.71E-01 (9.01E-03) F8 4.41E-02 (9.46E-03)- 2.16E-02 (6.39E-03)- 1.90E-01 (2.92E-03)- 5.84E-02 (5.55E-02)- 8.41E-03 (2.91E-03) F9 4.51E-02 (2.60E-03)- 7.07E-02 (2.40E-03)- 4.96E-02 (2.15E-03)- 4.18E-02 (2.42E-03)- 3.56E-02 (8.63E-04) F10 4.75E-02 (1.47E-03)- 7.39E-02 (2.33E-03)- 5.17E-02 (2.22E-03)- 4.52E-02 (3.95E-03)- 3.64E-02 (1.11E-03) F11 6.05E-02 (6.23E-03)- 8.91E-02 (5.95E-03)- 6.91E-02 (3.65E-03)- 5.27E-02 (4.14E-03)- 4.20E-02 (1.74E-03) F12 6.49E-02 (2.65E-03)- 9.83E-02 (1.03E-02)- 7.25E-02 (2.49E-03)- 5.96E-02 (5.30E-03)- 4.41E-02 (1.90E-03) F13 7.92E-02 (1.28E-02)- 9.35E-02 (1.04E-02)- 1.06E-01 (3.93E-03)- 7.12E-02 (7.55E-03)- 5.60E-02 (2.69E-03) F14 8.45E-02 (1.02E-02)- 9.93E-02 (1.65E-02)- 1.13E-01 (5.05E-03)- 8.06E-02 (2.07E-02)- 5.99E-02 (3.59E-03) F15 1.40E-01 (3.81E-03)- 2.14E-01 (5.36E-03)- 1.72E-01 (8.14E-03)- 1.45E-01 (5.10E-03)- 1.37E-01 (5.16E-03) F16 7.10E-02 (5.00E-03)- 5.16E-02 (2.78E-03)- 8.78E-02 (6.21E-03)- 6.85E-02 (4.07E-03)- 3.72E-02 (3.25E-03) +/-/= 0/15/1 1/15/0 0/16/0 0/16/0 ∖ According to Wilcoxon’s rank sum test with a significant levelα=0.05, +, − and = indicate that the corresponding MOEA is significantly better than, worse than or similar to MOEA/D-MUP.Table 5
Mean and standard deviation ofIH values obtained by four representative MOEA/Ds and MOEA/D-MUP.
Problem MOEA/D-STM MOEA/D-M2M MOEA/D-AWA MOEA/D-PaS MOEA/D-MUP F1 4.84E-01 (4.07E-03)- 4.86E-01 (3.43E-03)- 4.35E-01 (1.19E-03)- 4.80E-01 (2.94E-03)- 4.95E-01 (2.93E-04) F2 4.78E-01 (3.77E-03)- 4.80E-01 (4.69E-03)- 4.32E-01 (1.26E-03)- 4.77E-01 (2.22E-03)- 4.95E-01 (2.81E-04) F3 4.71E-01 (6.77E-03)- 4.81E-01 (3.98E-03)- 3.90E-01 (1.77E-03)- 4.67E-01 (3.34E-03)- 4.93E-01 (4.57E-04) F4 4.63E-01 (5.40E-03)- 4.76E-01 (5.16E-03)- 3.86E-01 (1.57E-03)- 4.63E-01 (3.18E-03)- 4.93E-01 (9.87E-04) F5 4.73E-01 (1.80E-02)- 4.73E-01 (8.50E-03)- 3.34E-01 (1.80E-03)- 4.32E-01 (6.19E-02)- 4.92E-01 (7.98E-04) F6 4.51E-01 (1.74E-02)- 4.69E-01 (8.67E-03)- 3.28E-01 (1.68E-03)- 3.78E-01 (1.10E-01)- 4.90E-01 (1.42E-03) F7 3.49E-01 (7.79E-03)- 3.92E-01 (1.19E02)+ 3.04E-01 (1.14E-02)- 3.21E-01 (5.39E-02)- 3.56E-01 (4.01E-03) F8 7.97E-01 (5.39E-03)- 8.10E-01 (5.14E-03)- 7.33E-01 (1.40E-03)- 7.78E-01 (7.00E-02)- 8.24E-01 (3.87E-03) F9 6.83E-01 (1.98E-02)- 6.60E-01 (1.36E-02)- 6.99E-01 (3.22E-03)- 7.09E-01 (1.37E-02)- 7.38E-01 (7.61E-03) F10 6.67E-01 (4.42E-03)- 6.45E-01 (6.63E-03)- 6.91E-01 (2.99E-03)- 6.92E-01 (6.82E-03)- 7.26E-01 (6.19E-03) F11 6.41E-01 (3.00E-02)- 6.39E-01 (2.69E-02)- 6.47E-01 (4.72E-03)- 6.72E-01 (1.22E-02)- 7.00E-01 (8.77E-03) F12 6.23E-01 (6.72E-03)- 6.23E-01 (2.90E-02)- 6.39E-01 (3.32E-03)- 6.61E-01 (1.42E-02)- 6.89E-01 (8.42E-03) F13 6.06E-01 (5.73E-02)- 6.40E-01 (2.84E02)= 5.74E-01 (2.90E-03)- 6.28E-01 (2.39E-02)- 6.50E-01 (7.62E-03) F14 5.88E-01 (4.53E-02)- 6.33E-01 (3.94E02)= 5.65E-01 (3.76E-03)- 6.15E-01 (1.35E-02)- 6.39E-01 (9.76E-03) F15 4.81E-01 (6.37E-03)- 4.03E-01 (8.49E-03)- 4.56E-01 (9.47E-03)- 4.84E-01 (5.15E-03)- 4.90E-01 (4.29E-03) F16 9.16E-01 (3.50E-03)- 9.26E-01 (2.18E-03)- 9.36E-01 (1.35E-03)- 9.31E-01 (2.83E-03)- 9.59E-01 (1.51E-03) +/-/= 0/16/0 1/13/2 0/16/0 0/16/0 ∖ According to Wilcoxon’s rank sum test with a significant levelα=0.05, +, − and = indicate that the corresponding MOEA is significantly better than, worse than or similar to MOEA/D-MUP.


### 5.1. Quantitative Comparisons

According to Wilcoxon’s rank sum test with a significant level of 0.05, the experimental results obtained by the nine MOEAs in terms of IGD metric andIH metric are shown in Tables 2–5, respectively. In general, it can be observed that MOEA/D-MUP performs better than the other eight algorithms on most test problems, i.e., F1-F16. More specifically, it can be seen from Tables 2–5 that our proposed MOEA/D-MUP achieves the best results in terms of the mean IGD values in all compared algorithms on F1-F6 and F9-F16. In addition, compared with the other algorithms except MOEA/D-DRA-UT and MOEA/D-M2M, MOEA/D-MUP obtains the best values for both mean IGD metric andIH metric on F7. For F8, MOEA/D-MUP only performs slightly worse than MOEA/D-DRA-UT in terms of mean IGD metric, while they have no significant difference in terms of meanIH metric. Next, we specifically analyze and discuss the superiority and drawback of MOEA/D-MUP with four classical MOEAs and four representative MOEA/Ds, respectively. The comparison results of MOEA/D-MUP with four classical MOEAs in terms of mean IGD andIH values are presented in Tables 2 and 3, respectively. The best metric values are highlighted in bold face and the metric values which are significantly similar to the metric value of MOEA/D-MUP are marked with italic font.As shown in Tables2 and 3, we can conclude that MOEA/D-MUP is significantly better than NSGA-II and SMS-EMOA in terms of mean IGD andIH values on all test problems adopted, i.e., F1-F16. In fact, the fast nondominated sorting approach always tends to choose these solutions in the middle part of the PF, which is caused by the characteristics of the problems that the solutions located in the middle part of the PF always can dominate other boundary solutions during the evolutionary process. Thus, as shown in Tables 2 and 3, NSGA-II always obtains very poor performance on all test problems, i.e., F1-F16. Similarly, the update strategy of neighborhood used in most MOEA/Ds is executed based on the aggregated function value to replace parent solutions, which also follows the strategy of convergence first and diversity second. Thus, overcrowdedness in the middle part of the PF still occurs in most MOEA/Ds. For example, although a dynamic computational resource allocation strategy is adopted in MOEA/D, MOEA/D-DRA still fails to cover the boundaries of these PFs when solving F1-F16. As shown in Tables 2 and 3, in terms of mean IGD andIH values, MOEA/D-MUP achieves better performance than MOEA/D-DRA on all test problems except that they have no significant difference on F7 regarding the mean IGD value. For MOEA/D-DRA-UT, more boundary areas can be found in the evolutionary search process, while MOEA/D-DRA-UT is still beaten by our proposed MOEA/D-DRA-UT on most test problems. These results validate that solutions in the middle part of the PF are likely maintained in the environmental selection mechanisms of these traditional MOEAs when tackling the problems with difficult-to-approximate PF boundaries. It can be observed from Tables 2 and 3, MOEA/D-MUP significantly outperforms MOEA/D-DRA-UT on most test problems. For example, on F1-F6, MOEA/D-MUP is significantly better than MOEA/D-DRA-UT in terms of mean IGD andIH values. However, on F7, no algorithm can approximate the entire PF due to the extreme difficulty to search the PF boundaries. Quantitatively, MOEA/D-MUP is slightly beaten by MOEA/D-DRA-UT in terms of mean IGD andIH values on F7. In addition, the performance of MOEA/D-DRA is similar to MOEA/D-MUP in terms of IGD on F7. This is mainly because the used dynamic resource allocation strategy can allocate more computational resources to search the undiscovered boundaries of the true PF on F7. Quantitatively, for F8, MOEA/D-MUP is slightly beaten by MOEA/D-DRA-UT in terms of IGD metric, while they have similar results in terms ofIH metric. As discussed above, the use of the utopian reference point instead of the ideal reference point is helpful to exploit the boundaries of the PF. However, in MOEA/D-MUP, multiple utopian reference points are used to provide different evolutionary search directions, which fails to cover the entire PF of F8. This is mainly because the inaccuracy of the nadir point leads to the wrong judgment about the upper bounds of the entire PF of F8. Furthermore, For F9-F16, MOEA/D-MUP achieves a better performance than MOEA/D-DRA-UT in terms of mean IGD metric, except that they are similar on F15. In terms of meanIH metric, MOEA/D-MUP performs much better than MOEA/D-DRA-UT on F10-F12 and F16, and they obtain statistically similar results for the rest three-objective test problems. In general, these results confirm the superiority of MOEA/D-MUP for tackling these problems with difficult-to-approximate PF boundaries.As shown in Tables4 and 5, the experimental results of MOEA/D-MUP with four representative MOEA/Ds (MOEA/D-STM, MOEA/D-M2M, MOEA/D-AWA, and MOEA/D-PaS) also demonstrate the superiority of MOEA/D-MUP on these test problems. It is clear from the two tables that MOEA/D-MUP significantly outperforms MOEA/D-STM, MOEA/D-AWA, and MOEA/D-PaS on F1-F16 and achieves better performance on most test problems than MOEA/D-M2M. As shown in Tables 4 and 5, MOEA/D-MUP is only beaten by MOEA/D-M2M on F7, and they obtain statistically similar results on F13 and F14 in terms ofIH. On other problems, MOEA/D-MUP is significantly better than MOEA/D-M2M. In terms of IGD, MOEA/D-STM is similar to MOEA/D-MUP on F7, while MOEA/D-STM is significantly worse than MOEA/D-MUP on the rest problems. When compared to MOEA/D-AWA and MOEA/D-PaS, MOEA/D-MUP performs much better on all test problems. Furthermore, when compared to MOEA/D-STM, MOEA/D-M2M, MOEA/D-AWA, and MOEA/D-PaS, MOEA/D-M2M attains the best mean IGD andIH values on all two-objective test problems. From these comparison results, it can be concluded that our proposed MOEA/D-MUP obtains the best performance, and the decomposition strategy used in MOEA/D-M2M achieves some success for some problems with difficult-to-approximate PF boundaries, as it can effectively maintain the boundary solutions into the next population. To conclude, our proposed MOEA/D-MUP can attain significantly better convergence and breadth-diversity than other compared MOEAs on most test problems adopted. For the problems with difficult-to-approximate PF boundaries, diversity should be more considered during the evolution.To visually show the convergence speeds of all the compared algorithms during the evolution, the curves of IGD value over the number of evaluations are depicted in Figure7, when solving two biobjective optimization problems (F1 and F6) and three triple-objective optimization problems (F10, F13, and F16). As shown in Figures 7(a) and 7(b), although MOEA/D-DRA-UT shows a faster convergence speed than MOEA/D-MUP in the early stage, MOEA/D-MUP can finally obtain the best IGD values on F1 and F6. For F10, F13, and F16, respectively, in Figures 7(c), 7(d), and 7(e), MOEA/D-MUP also shows a much faster convergence speed during the evolution and achieves the best IGD values.Figure 7
The convergence curves of all the compared algorithms on (a) F1, (b) F6, (c) F10, (d) F13, and (e) F16.
(a) (b) (c) (d) (e)Figure 8
The final populations obtained by MOEA/D-DRA-UT, MOEA/D-M2M, and MOEA/D-MUP on F3, F5, F6, and F8.Figure 9
The final populations obtained by MOEA/D-DRA-UT, MOEA/D-M2M, and MOEA/D-MUP on F9, F12, and F16.


### 5.2. Qualitative Comparisons

Due to page limitations, we select two competitive algorithms, i.e., MOEA/D-DRA-UT and MOEA/D-M2M, to qualitatively demonstrate the superiority of our proposed algorithm on solving most of the test problems adopted. For example, some representative two-objective problems, i.e., F1, F3, F5, F6, and F8 are shown in Figure8 and some three-objective problems are shown Figure 9, respectively. As shown in Figure 8, it is obvious that our proposed algorithm MOEA/D-MUP performs best on these test problems. For F8 with the convex PF, MOEA/D-MUP is only beaten by MOEA/D-DRA-UT, while MOEA/D-MUP is obviously better than MOEA/D-M2M. As shown in Figure 8, MOEA/D-MUP obtains a better approximation of the PF on F8 than MOEA/D-M2M. For example, boundary solutions obtained by MOEA/D-DRA-UT have not completely converged to the true PF, while MOEA/D-MUP performs much better.As shown in Figure9, the final nondominated sets obtained by the three algorithms on F9, F12 and F16 are plotted. It is obvious that MOEA/D-MUP performs significantly better than MOEA/D-DRA-UT and MOEA/D-M2M for these three-objective problems, i.e., F9, F12 and F16. Moreover, it can be seen from Figure 9 that more boundary solutions are obtained by MOEA/D-MUP, while the other two algorithms cannot approximate the PF boundaries sufficiently.


### 5.3. Parameter Sensitivity Analysis

In our algorithm, the maximal number of solutions replaced by a newly generated solution could be set as large asT (the neighborhood size). However, in most MOEA/Ds [19], the maximal number of solutions replaced by a newly generated solution is bounded bynr, which is set to be much smaller thanT. To study the impact ofnr in MOEA/D-MUP, different values (i.e., 2, 10, 20 and 30) are used for performance comparison. Due to page limitations, only the curves of IGD values obtained by fournr values on some test problems, i.e., F6 and F16, are provided in Figures 10(a) and 10(b). As shown in Figure 10, it is found that the performance of MOEA/D-MUP with a largenr value is superior to that with a smallnr value. Thus, in MOEA/D-MUP, the maximal number of solutions replaced by a newly generated solution is set to be as large as the neighborhood size, which can better balance convergence and diversity during the evolutionary process.Figure 10
Parameter sensitivity studies ofnr on (a) F6 and (b) F16.
(a) (b)


## 5.1. Quantitative Comparisons

According to Wilcoxon’s rank sum test with a significant level of 0.05, the experimental results obtained by the nine MOEAs in terms of IGD metric andIH metric are shown in Tables 2–5, respectively. In general, it can be observed that MOEA/D-MUP performs better than the other eight algorithms on most test problems, i.e., F1-F16. More specifically, it can be seen from Tables 2–5 that our proposed MOEA/D-MUP achieves the best results in terms of the mean IGD values in all compared algorithms on F1-F6 and F9-F16. In addition, compared with the other algorithms except MOEA/D-DRA-UT and MOEA/D-M2M, MOEA/D-MUP obtains the best values for both mean IGD metric andIH metric on F7. For F8, MOEA/D-MUP only performs slightly worse than MOEA/D-DRA-UT in terms of mean IGD metric, while they have no significant difference in terms of meanIH metric. Next, we specifically analyze and discuss the superiority and drawback of MOEA/D-MUP with four classical MOEAs and four representative MOEA/Ds, respectively. The comparison results of MOEA/D-MUP with four classical MOEAs in terms of mean IGD andIH values are presented in Tables 2 and 3, respectively. The best metric values are highlighted in bold face and the metric values which are significantly similar to the metric value of MOEA/D-MUP are marked with italic font.As shown in Tables2 and 3, we can conclude that MOEA/D-MUP is significantly better than NSGA-II and SMS-EMOA in terms of mean IGD andIH values on all test problems adopted, i.e., F1-F16. In fact, the fast nondominated sorting approach always tends to choose these solutions in the middle part of the PF, which is caused by the characteristics of the problems that the solutions located in the middle part of the PF always can dominate other boundary solutions during the evolutionary process. Thus, as shown in Tables 2 and 3, NSGA-II always obtains very poor performance on all test problems, i.e., F1-F16. Similarly, the update strategy of neighborhood used in most MOEA/Ds is executed based on the aggregated function value to replace parent solutions, which also follows the strategy of convergence first and diversity second. Thus, overcrowdedness in the middle part of the PF still occurs in most MOEA/Ds. For example, although a dynamic computational resource allocation strategy is adopted in MOEA/D, MOEA/D-DRA still fails to cover the boundaries of these PFs when solving F1-F16. As shown in Tables 2 and 3, in terms of mean IGD andIH values, MOEA/D-MUP achieves better performance than MOEA/D-DRA on all test problems except that they have no significant difference on F7 regarding the mean IGD value. For MOEA/D-DRA-UT, more boundary areas can be found in the evolutionary search process, while MOEA/D-DRA-UT is still beaten by our proposed MOEA/D-DRA-UT on most test problems. These results validate that solutions in the middle part of the PF are likely maintained in the environmental selection mechanisms of these traditional MOEAs when tackling the problems with difficult-to-approximate PF boundaries. It can be observed from Tables 2 and 3, MOEA/D-MUP significantly outperforms MOEA/D-DRA-UT on most test problems. For example, on F1-F6, MOEA/D-MUP is significantly better than MOEA/D-DRA-UT in terms of mean IGD andIH values. However, on F7, no algorithm can approximate the entire PF due to the extreme difficulty to search the PF boundaries. Quantitatively, MOEA/D-MUP is slightly beaten by MOEA/D-DRA-UT in terms of mean IGD andIH values on F7. In addition, the performance of MOEA/D-DRA is similar to MOEA/D-MUP in terms of IGD on F7. This is mainly because the used dynamic resource allocation strategy can allocate more computational resources to search the undiscovered boundaries of the true PF on F7. Quantitatively, for F8, MOEA/D-MUP is slightly beaten by MOEA/D-DRA-UT in terms of IGD metric, while they have similar results in terms ofIH metric. As discussed above, the use of the utopian reference point instead of the ideal reference point is helpful to exploit the boundaries of the PF. However, in MOEA/D-MUP, multiple utopian reference points are used to provide different evolutionary search directions, which fails to cover the entire PF of F8. This is mainly because the inaccuracy of the nadir point leads to the wrong judgment about the upper bounds of the entire PF of F8. Furthermore, For F9-F16, MOEA/D-MUP achieves a better performance than MOEA/D-DRA-UT in terms of mean IGD metric, except that they are similar on F15. In terms of meanIH metric, MOEA/D-MUP performs much better than MOEA/D-DRA-UT on F10-F12 and F16, and they obtain statistically similar results for the rest three-objective test problems. In general, these results confirm the superiority of MOEA/D-MUP for tackling these problems with difficult-to-approximate PF boundaries.As shown in Tables4 and 5, the experimental results of MOEA/D-MUP with four representative MOEA/Ds (MOEA/D-STM, MOEA/D-M2M, MOEA/D-AWA, and MOEA/D-PaS) also demonstrate the superiority of MOEA/D-MUP on these test problems. It is clear from the two tables that MOEA/D-MUP significantly outperforms MOEA/D-STM, MOEA/D-AWA, and MOEA/D-PaS on F1-F16 and achieves better performance on most test problems than MOEA/D-M2M. As shown in Tables 4 and 5, MOEA/D-MUP is only beaten by MOEA/D-M2M on F7, and they obtain statistically similar results on F13 and F14 in terms ofIH. On other problems, MOEA/D-MUP is significantly better than MOEA/D-M2M. In terms of IGD, MOEA/D-STM is similar to MOEA/D-MUP on F7, while MOEA/D-STM is significantly worse than MOEA/D-MUP on the rest problems. When compared to MOEA/D-AWA and MOEA/D-PaS, MOEA/D-MUP performs much better on all test problems. Furthermore, when compared to MOEA/D-STM, MOEA/D-M2M, MOEA/D-AWA, and MOEA/D-PaS, MOEA/D-M2M attains the best mean IGD andIH values on all two-objective test problems. From these comparison results, it can be concluded that our proposed MOEA/D-MUP obtains the best performance, and the decomposition strategy used in MOEA/D-M2M achieves some success for some problems with difficult-to-approximate PF boundaries, as it can effectively maintain the boundary solutions into the next population. To conclude, our proposed MOEA/D-MUP can attain significantly better convergence and breadth-diversity than other compared MOEAs on most test problems adopted. For the problems with difficult-to-approximate PF boundaries, diversity should be more considered during the evolution.To visually show the convergence speeds of all the compared algorithms during the evolution, the curves of IGD value over the number of evaluations are depicted in Figure7, when solving two biobjective optimization problems (F1 and F6) and three triple-objective optimization problems (F10, F13, and F16). As shown in Figures 7(a) and 7(b), although MOEA/D-DRA-UT shows a faster convergence speed than MOEA/D-MUP in the early stage, MOEA/D-MUP can finally obtain the best IGD values on F1 and F6. For F10, F13, and F16, respectively, in Figures 7(c), 7(d), and 7(e), MOEA/D-MUP also shows a much faster convergence speed during the evolution and achieves the best IGD values.Figure 7
The convergence curves of all the compared algorithms on (a) F1, (b) F6, (c) F10, (d) F13, and (e) F16.
(a) (b) (c) (d) (e)Figure 8
The final populations obtained by MOEA/D-DRA-UT, MOEA/D-M2M, and MOEA/D-MUP on F3, F5, F6, and F8.Figure 9
The final populations obtained by MOEA/D-DRA-UT, MOEA/D-M2M, and MOEA/D-MUP on F9, F12, and F16.


## 5.2. Qualitative Comparisons

Due to page limitations, we select two competitive algorithms, i.e., MOEA/D-DRA-UT and MOEA/D-M2M, to qualitatively demonstrate the superiority of our proposed algorithm on solving most of the test problems adopted. For example, some representative two-objective problems, i.e., F1, F3, F5, F6, and F8 are shown in Figure8 and some three-objective problems are shown Figure 9, respectively. As shown in Figure 8, it is obvious that our proposed algorithm MOEA/D-MUP performs best on these test problems. For F8 with the convex PF, MOEA/D-MUP is only beaten by MOEA/D-DRA-UT, while MOEA/D-MUP is obviously better than MOEA/D-M2M. As shown in Figure 8, MOEA/D-MUP obtains a better approximation of the PF on F8 than MOEA/D-M2M. For example, boundary solutions obtained by MOEA/D-DRA-UT have not completely converged to the true PF, while MOEA/D-MUP performs much better.As shown in Figure9, the final nondominated sets obtained by the three algorithms on F9, F12 and F16 are plotted. It is obvious that MOEA/D-MUP performs significantly better than MOEA/D-DRA-UT and MOEA/D-M2M for these three-objective problems, i.e., F9, F12 and F16. Moreover, it can be seen from Figure 9 that more boundary solutions are obtained by MOEA/D-MUP, while the other two algorithms cannot approximate the PF boundaries sufficiently.


## 5.3. Parameter Sensitivity Analysis

In our algorithm, the maximal number of solutions replaced by a newly generated solution could be set as large asT (the neighborhood size). However, in most MOEA/Ds [19], the maximal number of solutions replaced by a newly generated solution is bounded bynr, which is set to be much smaller thanT. To study the impact ofnr in MOEA/D-MUP, different values (i.e., 2, 10, 20 and 30) are used for performance comparison. Due to page limitations, only the curves of IGD values obtained by fournr values on some test problems, i.e., F6 and F16, are provided in Figures 10(a) and 10(b). As shown in Figure 10, it is found that the performance of MOEA/D-MUP with a largenr value is superior to that with a smallnr value. Thus, in MOEA/D-MUP, the maximal number of solutions replaced by a newly generated solution is set to be as large as the neighborhood size, which can better balance convergence and diversity during the evolutionary process.Figure 10
Parameter sensitivity studies ofnr on (a) F6 and (b) F16.
(a) (b)


## 6. Conclusion

In this paper, we have proposed an evolutionary search method with multiple utopian reference points for MOEA/D, called MOEA/D-MUP, which uses multiple utopian reference points to provide evolutionary search directions for different weight vectors. In order to effectively exploit the undiscovered boundaries of PF and enhance the breadth-diversity, the utopian reference point of each search direction is got by transforming the ideal point at a specified distance. Moreover, the nadir point is used to restrict the maximal translational distance. In other words, the positions of multiple utopian reference points in the objective space are bounded by the ideal point and the nadir point. Comparing our proposed algorithm with eight state-of-the-art MOEAs in terms of both IGD andIH metrics, we have witnessed the effectiveness and competitiveness of MOEA/D-MUP on F1-F16 used in this paper. As indicated by the experimental results, most existing MOEA/Ds cannot approximate the entire PFs on these test problems because the boundaries of PF cannot be effectively exploited. For the problems with difficult-to-approximate PF boundaries, there is a little effort that has been made to (1) effectively exploit the boundary areas and (2) balance exploration and exploitation in the search space. Therefore, there is much room for further development.In the future work, we would like to investigate more effective selection mechanisms to better balance convergence and diversity during the evolutionary search process when tackling the problems with difficult-to-approximate PF boundaries. Specifically, we will further study a more accurate generation method for utopian reference points and design recombination operators with stronger search ability. We also will put more efforts to develop mechanisms that can adaptively approximate the complex PFs and to extend our algorithm for solving many-objective optimization problems. Moreover, it is valuable to apply our proposed algorithm to solve some real-world applications [56, 57].



---

*Source: 7436712-2019-04-01.xml*