# Hypervolume-Optimal $\mu$-Distributions on Line/Plane-based Pareto Fronts in
Three Dimensions

Ke Shang, , Hisao Ishibuchi, , Weiyu Chen, Yang Nan, and Weiduo Liao This work
was supported by National Natural Science Foundation of China (Grant No.
61876075), Guangdong Provincial Key Laboratory (Grant No. 2020B121201001), the
Program for Guangdong Introducing Innovative and Enterpreneurial Teams (Grant
No. 2017ZT07X386), Shenzhen Science and Technology Program (Grant No.
KQTD2016112514355531), the Program for University Key Laboratory of Guangdong
Province (Grant No. 2017KSYS008). (Corresponding Author: Hisao Ishibuchi.)K.
Shang, H. Ishibuchi, W. Chen, Y. Nan and W. Liao are with Guangdong Provincial
Key Laboratory of Brain-inspired Intelligent Computation, Department of
Computer Science and Engineering, Southern University of Science and
Technology, Shenzhen 518055, China (e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>nany@mail.sustech.edu.cn).

###### Abstract

Hypervolume is widely used in the evolutionary multi-objective optimization
(EMO) field to evaluate the quality of a solution set. For a solution set with
$\mu$ solutions on a Pareto front, a larger hypervolume means a better
solution set. Investigating the distribution of the solution set with the
largest hypervolume is an important topic in EMO, which is the so-called
hypervolume optimal $\mu$-distribution. Theoretical results have shown that
the $\mu$ solutions are uniformly distributed on a linear Pareto front in two
dimensions. However, the $\mu$ solutions are not always uniformly distributed
on a single-line Pareto front in three dimensions. They are only uniform when
the single-line Pareto front has one constant objective. In this paper, we
further investigate the hypervolume optimal $\mu$-distribution in three
dimensions. We consider the line- and plane-based Pareto fronts. For the line-
based Pareto fronts, we extend the single-line Pareto front to two-line and
three-line Pareto fronts, where each line has one constant objective. For the
plane-based Pareto fronts, the linear triangular and inverted triangular
Pareto fronts are considered. First, we show that the $\mu$ solutions are not
always uniformly distributed on the line-based Pareto fronts. The uniformity
depends on how the lines are combined. Then, we show that a uniform solution
set on the plane-based Pareto front is not always optimal for hypervolume
maximization. It is locally optimal with respect to a $(\mu+1)$ selection
scheme. Our results can help researchers in the community to better understand
and utilize the hypervolume indicator.

###### Index Terms:

Hypervolume indicator, Evolutionary multi-objective optimization, Optimal
$\mu$-distribution.

##  I Introduction

The hypervolume indicator is a popular performance indicator in the field of
evolutionary multi-objective optimization (EMO). Informally, the hypervolume
of a solution set is the volume of the objective space dominated by the
solution set and dominating a reference point. A well recognized fact in the
EMO community is that the hypervolume indicator is able to evaluate the
convergence and the diversity of a solution set simultaneously. The
hypervolume indicator is strictly Pareto compliant [1], which guarantees that
a solution set maximizing the hypervolume indicator are all Pareto optimal
[2]. Thus, the hypervolume indicator is adopted in some EMO algorithms (EMOAs)
to guide the population converge to the Pareto front. We call these algorithms
hypervolume-based EMOAs. Some representative algorithms are SMS-EMOA [3, 4],
FV-MOEA [5], HypE [6], and R2HCA-EMOA [7]. For a comprehensive survey of the
hypervolume indicator, please refer to [8].

For a hypervolume-based EMOA, a well-converged and widely-distributed solution
set on the Pareto front is expected. The convergence of the solution set can
be achieved due to the Pareto compliance property of the hypervolume
indicator. For the diversity of the solution set, a widely-distributed
solution set on the Pareto front is expected by maximizing the hypervolume
indicator. Many researchers analyze how the solution set is distributed on the
Pareto front when the hypervolume is maximized. This research issue is usually
called the hypervolume optimal $\mu$-distribution.

Theoretical studies have proved that for a linear Pareto front in two
dimensions, the $\mu$ solutions are uniformly distributed on the Pareto front
in order to maximize the hypervolume indciator [9, 10]. To the best of our
knowledge, this conclusion is the only one to precisely describe the
hypervolume optimal-$\mu$ distribution on the Pareto front in two dimensions.
Auger et al. [9] and Friedrich et al. [11] theoretically investigated the
hypervolume optimal $\mu$-distribution of solutions on the two-objective
nonlinear Pareto fronts. However, it is still very difficult to precisely
describe the location of the $\mu$ solutions on the Pareto fronts. In three
dimensional cases, Shukla et al. [12] theoretically investigated the
hypervolume optimal $\mu$-distribution on a single-line Pareto front (i.e., a
degenerated Pareto front). It shows that the uniformity property of the
optimal distribution for a linear Pareto front in two dimensions cannot be
generalized to three dimensions. The solutions are only uniform on a single-
line Pareto front when one objective of the Pareto front is constant (i.e.,
this Pareto front can be degenerated to a linear Pareto front in two
dimensions). Auger et al. [13] theoretically studied the hypervolume optimal
$\mu$-distribution in three dimensions. However, the exact hypervolume optimal
$\mu$-distribution is not obtained in [13]. Singh [14] theoretically studied
the hypervolume behavior when $\mu$ is infinity (i.e., the whole Pareto front)
whereas the hypervolume optimal $\mu$-distribution is not described. Due to
the difficulty of the theoretical study, many studies only investigate the
hypervolume optimal $\mu$-distribution empirically [15, 16, 17, 18, 19], i.e.,
the hypervolume optimal $\mu$-distribution is approximated on the Pareto front
in these studies.

In this paper, we further study the hypervolume optimal $\mu$-distribution in
three dimensions, both theoretically and empirically. We consider the line-
and plane-based Pareto fronts. The line-based Pareto fronts have two and three
lines, where each line has one constant objective. The plane-based Pareto
fronts are with triangular and inverted triangular shapes.

(a) HV=4.9000 (b) HV=4.8909

(c) HV=7.6196 (d) HV=7.6150

(e) HV=5.3500 (f) HV=5.3396

(g) HV=7.7136 (h) HV=7.7100

Figure 1: Uniform and non-uniform solution sets on four types of line-based
Pareto fronts. The reference point is specified as $\mathbf{r}=(-1,-1,-1)$.
The hypervolume of each solution set is shown under each figure.

For the line-based Pareto fronts, we show that the solutions are not always
uniformly distributed. The uniformity depends on how the lines are combined.
For example, Fig. 1 shows four types of the line-based Pareto fronts with
uniform and non-uniform solution sets. The hypervolume value of each solution
set is also shown in Fig. 1 for the reference point
$\mathbf{r}=(-1,-1,-1)$111In this paper, maximization of each objective is
assumed in multi-objective optimization problems. Thus, the reference point is
in the negative orthant.. In some cases (i.e., (a) and (e)), the uniform
solution set has a larger hypervolume than the non-uniform solution set (i.e.,
(a)$>$(b) and (e)$>$(f)). However, in the other cases (i.e., (c) and (g)), the
non-uniform solution set has a larger hypervolume than the uniform solution
set (i.e., (c)$>$(d) and (g)$>$(h)). In this paper, we theoretically
investigate this issue and explain why the uniform solution set is not always
optimal in Fig. 1.

For the plane-based Pareto fronts, we show that the uniform solution set is
not always optimal for hypervolume maximization. It is locally optimal with
respect to a $(\mu+1)$ selection scheme. For example, Fig. 2 shows two types
of the plane-based Pareto fronts with uniform and non-uniform solution sets.
The hypervolume value of each solution set is shown in Fig. 2 for the
reference point $\mathbf{r}=(-1/8,-1/8,-1/8)$. For each Pareto front, the
uniform solution set has a smaller hypervolume than the non-uniform solution
set (e.g., (a)$<$(b) and (c)$<$(d)). In this paper, we investigate this issue
and prove the local optimality of the uniform solution set on the plane-based
Pareto fronts.

(a) HV=0.3223

(b) HV=0.3236

(c) HV=1.1895

(d) HV=1.1908

Figure 2: Uniform and non-uniform solution sets on two types of plane-based
Pareto fronts. The reference point is specified as
$\mathbf{r}=(-1/8,-1/8,-1/8)$. The hypervolume of each solution set is shown
under each figure.

The main contributions of this paper are summarized as follows:

  1. 1.

We extend the single-line Pareto fronts to line-based Pareto fronts with more
than one lines in three dimensions, and reveal that a uniform solution set
cannot always be obtained by maximizing the hypervolume indicator. The
solution set is uniform only if the hypervolume can be decomposed into
independent parts.

  2. 2.

In addition to the line-based Pareto fronts, we also investigate the plane-
based Pareto fronts in three dimensions. The main result is that a uniform
solution set (i.e., a solution set generated by the DAS method [20]) is not
always optimal for hypervolume maximization. It is locally optimal with
respect to a $(\mu+1)$ selection scheme.

The rest of the paper is structured as follows. In Section II, the
preliminaries of the paper is presented. In Section III, the line-based Pareto
fronts are investigated. In Section IV, the plane-based Pareto fronts are
investigated. Finally, the conclusions are drawn in Section V.

This paper is an extended version of our conference paper [21]. In our
conference paper, we only investigated the line-based Pareto fronts. In this
paper, in addition to the line-based Pareto fronts, we also investigate the
plane-based Pareto fronts. More discussions on the line- and plane-based
Pareto fronts are provided in this paper.

##  II Preliminaries

###  II-A Basic Definitions

First, the definitions of the hypervolume indicator, the hypervolume
contribution, and the hypervolume optimal $\mu$-distributions are presented.

The hypervolume of a solution set is defined as follows. For a solution set
$A\subset\mathbb{R}^{m}$ and a reference point $\mathbf{r}\in\mathbb{R}^{m}$,
the hypervolume of the solution set $A$ is defined as

$\text{HV}(A,\mathbf{r})=\mathcal{L}\left(\bigcup_{\mathbf{a}\in
A}\left\\{\mathbf{b}|\mathbf{a}\succeq\mathbf{b}\succeq\mathbf{r}\right\\}\right),$
(1)

where $\mathcal{L}(\cdot)$ is the Lebesgue measure of a set, and
$\mathbf{a}\succeq\mathbf{b}$ means that $\mathbf{a}$ Pareto dominates
$\mathbf{b}$ (i.e., $a_{i}\geq b_{i}$ for all $i=1,...,m$ and $a_{j}>b_{j}$
for at least one $j=1,...,m$ in the maximization case).

The hypervolume contribution is an important concept based on the hypervolume
indicator. It describes the amount of the hypevolume value contributed by a
solution to the solution set. Formally, for a solution $\mathbf{s}\in A$, the
hypervolume contribution of $\mathbf{s}$ to $A$ is defined as

$\text{HVC}(\mathbf{s},A,\mathbf{r})=\text{HV}(A,\mathbf{r})-\text{HV}(A\setminus\\{\mathbf{s}\\},\mathbf{r}).$
(2)

Based on the hypervolume indicator, the hypervolume optimal $\mu$-distribution
is defined as follows [22]. For a Pareto front
$\mathcal{F}\subset\mathbb{R}^{m}$ and a reference point
$\mathbf{r}\in\mathbb{R}^{m}$, the hypervolume optimal $\mu$-distribution is
$\mu\in\mathbb{N}$ points on the Pareto front which maximize the hypervolume
of the $\mu$ points. The set $A$ containing the optimal $\mu$ points is

$A=\arg\max_{|A^{\prime}|=\mu,A^{\prime}\subset\mathcal{F}}\text{HV}(A^{\prime},\mathbf{r}).$
(3)

###  II-B Hypervolume Optimal $\mu$-Distribution in Two Dimensions

For a linear Pareto front in two dimensions, Emmerich et al. [10] and Auger et
al. [9] theoretically show that the $\mu$ solutions which maximize the
hypervolume value are uniformly distributed on the Pareto front. When the
reference point is sufficiently far away from the Pareto front, the optimal
$\mu$-distribution includes the two extreme points of the Pareto front. For
example, consider the linear Pareto front $f_{1}+f_{2}=1$ and $f_{1},f_{2}\geq
0$, if the reference point $\mathbf{r}=(r,r)$ satisfies $r\leq-1/(\mu-1)$
[23]222In the case of minimization, this condition is rewritten as $r\geq
1+1/(\mu-1)$., the two extreme points $(0,1)$ and $(1,0)$ of the Pareto front
are included in the hypervolume optimal $\mu$-distribution.

Fig. 3 gives an illustration of the hypervolume optimal $\mu$-distribution in
two dimensions. In Fig. 3, four solutions (i.e., $\mu=4$) are uniformly
distributed on the Pareto front. If we set the reference point to
$r=-1/(\mu-1)$ (i.e., $r=-1/3$), each solution has the same hypervolume
contribution (i.e., the colored square).

Figure 3: An illustration of the hypervolume optimal $\mu$-distribution on a
linear Pareto front in two dimensions.

###  II-C Hypervolume Optimal $\mu$-Distribution in Three Dimensions

In this paper, all the Pareto fronts are studied in the normalized objective
space (i.e., $[0,1]^{3}$). The reference point is specified as
$\mathbf{r}=(r,r,r)$ (i.e., each element of $\mathbf{r}$ is the same).

Shukla et al. [12] theoretically studied the hypervolume optimal
$\mu$-distribution on a single-line Pareto front in three dimensions and
showed that the solutions are not always uniformly distributed for hypervolume
maximization. A single-line Pareto front in three dimensions is a degenerated
Pareto front. For such a single-line Pareto front, it has the following two
types:

  1. 1.

Type I: Two objectives are conflicting with each other, and the other
objective is constant. Fig. 4 (a) shows an example of Type I Pareto front.

  2. 2.

Type II: Two objectives are consistent (i.e., not conflicting) with each
other, and the other objective is conflicting with the two objectives. Fig. 4
(b) shows an example of Type II Pareto front.

(a) Type I Pareto front (b) Type II Pareto front

Figure 4: Single-line Pareto fronts in three dimensions.

For the Type I Pareto front $f_{1}+f_{3}=1,f_{1},f_{3}\geq 0,f_{2}=0$ in Fig.
4 (a), when the reference point is specified as $r=-1/(\mu-1)$, each solution
of the uniform solution set has the same hypervolume contribution. We can see
that the hypervolume of the three solutions on Type I Pareto front can be
calculated as the two-dimensional hypervolume of the three solutions in
$f_{1}\text{-}f_{3}$ space multiplying $|r|$. Thus, maximizing the hypervolume
in three dimensions is equivalent to maximizing the hypervolume in two
dimensions (i.e., $f_{1}\text{-}f_{3}$ space). Therefore, the solutions are
uniformly distributed on the Type I Pareto front.

For the Type II Pareto front $f_{1}+f_{3}=1,f_{1},f_{3}\geq 0,f_{1}=f_{2}$ in
Fig. 4 (b), when the reference point is specified as $r=-1/(\mu-1)$, each
solution of the uniform solution set has a different hypervolume contribution.
For example, the hypervolume contribution of each solution
$\mathbf{a}=(0,0,1)$, $\mathbf{b}=(0.5,0.5,0.5)$, and $\mathbf{c}=(1,1,0)$ in
Fig. 4 (b) is $0.5^{3}$, $3\times 0.5^{3}$, and $5\times 0.5^{3}$,
respectively. $\mathbf{c}$ has a larger hypervolume contribution than
$\mathbf{b}$, and $\mathbf{b}$ has a larger hypervolume contribution than
$\mathbf{a}$. If we move $\mathbf{b}$ towards $\mathbf{c}$ to a new location
$\mathbf{b}^{\prime}=(0.6,0.6,0.4)$ as illustrated in Fig. 5, then the
hypervolume contribution of $\mathbf{b}^{\prime}$ is $(0.5^{2}\times
3+0.1^{2}+0.1\times 0.5\times 4)\times 0.4=0.384>0.375=3\times 0.5^{3}$. This
means that the whole hypervolume in Fig. 4 (b) can be improved by moving
$\mathbf{b}$ to $\mathbf{b}^{\prime}$. Therefore, the uniform solution set is
not optimal for hypervolume maximziation on the Type II Pareto front.

(a) Before moving $\mathbf{b}$ (b) After moving $\mathbf{b}$

Figure 5: An illustration of moving solution $\mathbf{b}$ in Fig. 4 (b). Only
$f_{1}$-$f_{2}$ subspace is shown. The hypervolume contributions of
$\mathbf{b}$ and $\mathbf{b}^{\prime}$ are the blue areas in (a) and (b) times
their $f_{3}$ values, respectively.

###  II-D DAS Method and Reference Point Specification for Hypervolume
Calculation

The DAS method [20] is a widely used method for generating uniformly
distributed points on a simplex. DAS is adopted in many popular EMOAs (e.g.,
MOEA/D [24], NSGA-III [25]) for generating weight vectors or reference points.

DAS generates all points $\mathbf{w}=(w_{1},w_{2},...,w_{m})$ satisfying the
following relations:

$\displaystyle\sum_{i=1}^{m}w_{i}=1\text{ and }w_{i}\geq 0\text{ for
}i=1,2,...,m,$ (4) $\displaystyle
w_{i}\in\left\\{0,\frac{1}{H},\frac{2}{H},...,1\right\\}\text{ for
}i=1,2,...,m,$

where $m$ is the number of objectives and $H$ is a positive integer.

The total number of generated points is $\binom{H+m-1}{m-1}$. Fig. 6 (a)
illustrates the points generated by DAS in three dimensions with $H=3$ (i.e.,
$\mu=10$). In the EMO community, a DAS solution set is implicitly assumed to
be a perfectly uniform solution set on the unit simplex (i.e., a triangular
plane Pareto front). Thus, a uniform solution set on a triangular plane Pareto
front means a DAS solution set in this paper.

(a) DAS solution set

(b) The hypervolume of the DAS solution set

Figure 6: A DAS solution set in three dimensions and its hypervolume.

Ishibuchi et al. [18] suggested a reference point specification method for
hypervolume calculation. The general idea of the specification method is to
set the reference point so that all solutions of the DAS solution set on the
triangular linear Pareto front have the same hypervolume contribution.

Let us consider the linear Pareto front $f_{1}+f_{2}+...+f_{m}=1$ and
$f_{1},f_{2},...,f_{m}\geq 0$. Given a DAS solution set on the Pareto front,
the reference point $\mathbf{r}=(r,...,r)$ is specified as follows [18]333In
the case of minimization, Eq. (5) is rewritten as $r=1+1/H$.:

$r=-\frac{1}{H},$ (5)

where $H$ is the parameter in (3).

Using this reference point specification, all the solutions have the equal
hypervolume contribution as illustrated in Fig. 6 (b). Eq. (5) is a
generalization of the reference point specification $r=-1/(\mu-1)$ in two
dimensions (see Fig. 3) since $H=\mu-1$ when $m=2$.

##  III Line-based Pareto fronts

In this section, we extend the Type I Pareto front, and investigate the
hypervolume optimal $\mu$-distribution on a Pareto front which consists of
several joint Type I Pareto fronts.

We consider the following four types of Pareto fronts:

  1. 1.

Type III: The two lines are the boundary of a triangular front. Fig. 7 (a)
shows a Type III Pareto front, where the triangular front is
$f_{1}+f_{2}+f_{3}=1,f_{1},f_{2},f_{3}\geq 0$.

  2. 2.

Type IV: The two lines are the boundary of an inverted triangular front. Fig.
7 (b) shows a Type IV Pareto front where the inverted triangular front is
$f_{1}+f_{2}+f_{3}=2,0\leq f_{1},f_{2},f_{3}\leq 1$.

  3. 3.

Type V: The three lines are the boundary of a triangular front. Fig. 7 (c)
shows a Type V Pareto front where the triangular front is
$f_{1}+f_{2}+f_{3}=1,f_{1},f_{2},f_{3}\geq 0$.

  4. 4.

Type VI: The three lines are the boundary of an inverted triangular front.
Fig. 7 (d) shows a Type VI Pareto front where the inverted triangular front is
$f_{1}+f_{2}+f_{3}=2,0\leq f_{1},f_{2},f_{3}\leq 1$.

(a) Type III Pareto front (b) Type IV Pareto front (c) Type V Pareto front (d)
Type VI Pareto front

Figure 7: Line-based Pareto fronts in three dimensions.

Next, the hypervolume optimal $\mu$-distribution on each of these four types
of Pareto fronts is investigated.

###  III-A Type III Pareto Front

Let us consider the Type III Pareto front with two lines where the first line
is $f_{1}+f_{3}=1,f_{1},f_{3}\geq 0$ and $f_{2}=0$, and the second line is
$f_{1}+f_{2}=1,f_{1},f_{2}\geq 0$ and $f_{3}=0$ as in Fig. 7 (a). Before
investigating the hypervolume optimal $\mu$-distribution on this type of
Pareto front, we show the following lemma which will be used in our analysis.

######  Lemma 1 (Reproduced from Theorem 3 in [23]).

Given $\mu\in\mathbb{N}_{\geq 2}$, and a linear Pareto front $f(x)=1-x$ where
$x\in[0,1]$, the unique optimal $\mu$-distribution
$(x_{1}^{\mu},...,x_{\mu}^{\mu})$ for the hypervolume indicator with reference
point $\mathbf{r}=(r_{1},r_{2})\in\mathbb{R}^{2}_{<0}$ can be described by

$x_{i}^{\mu}=f^{-1}(F_{l})+\frac{i}{\mu+1}(F_{r}-f^{-1}(F_{l}))$ (6)

for all $1\leq i\leq\mu$ where

$\displaystyle
F_{l}=\min\left\\{1-r_{1},\frac{\mu+1}{\mu}-\frac{1}{\mu}f(1-r_{2}),\frac{\mu}{\mu-1}\right\\},$
(7) $\displaystyle
F_{r}=\min\left\\{1-r_{2},\frac{\mu+1}{\mu}-\frac{1}{\mu}f^{-1}(1-r_{1}),\frac{\mu}{\mu-1}\right\\}.$

Lemma 1 provides the following two main conclusions:

  1. 1.

The optimal $\mu$ solutions are equispaced on the Pareto front, since
$x_{i}^{\mu}-x_{i-1}^{\mu}$ is constant for all $i$.

  2. 2.

The inclusion of the extreme points $(0,1)$ and $(1,0)$ in the optimal
$\mu$-distribution depends on the location of the reference point. If the
reference point is $\mathbf{r}=(r,r)$, then $r\leq-1/(\mu-1)$ guarantees the
inclusion of the two extreme points. If the reference point is
$\mathbf{r}=(r,0)$, then $r\leq-1/\mu$ guarantees the inclusion of one extreme
point $(1,0)$.

Based on Lemma 1, we present the following theorem describing the hypervolume
optimal $\mu$-distribution on the Type III Pareto front.

######  Theorem 1.

For $\mu>3$ solutions on the Type III Pareto front,

  1. 1.

if $\mu$ is odd, the optimal $\mu$-distribution is that the same number of
solutions lie uniformly on each of the two lines where the three extreme
points (i.e., (1,0,0), (0,1,0), (0,0,1)) are included, under the condition of
$r\leq-2/(\mu-1)$,

  2. 2.

if $\mu$ is even, the optimal $\mu$-distribution is that a different number of
solutions lie uniformly on each of the two lines where the difference in the
number of solutions on each line is one, and the three extreme points (i.e.,
(1,0,0), (0,1,0), (0,0,1)) are included, under the condition of
$r\leq-1/\lfloor\frac{\mu-1}{2}\rfloor$.

###### Proof.

First, we assume that $\mu_{1}$ solutions lie on the first line (from
$(1,0,0)$ to $(0,0,1)$) and $\mu_{2}$ solutions lie on the second line (from
$(1,0,0)$ to $(0,1,0)$) where $\mu_{1}+\mu_{2}=\mu$. Denote the solutions on
the first line from $(1,0,0)$ to $(0,0,1)$ as
$\mathbf{a}_{1},...,\mathbf{a}_{\mu_{1}}$, and the solutions on the second
line from $(1,0,0)$ to $(0,1,0)$ as $\mathbf{b}_{1},...,\mathbf{b}_{\mu_{2}}$.
Without loss of generality, we assume that $f_{1}(\mathbf{a}_{1})\geq
f_{1}(\mathbf{b}_{1})$. Then the whole hypervolume can be decomposed into two
parts as illustrated in Fig. 8. That is, the whole hypervolume is sliced
according to the plane $f_{2}=0$.

One part (denoted as $HV_{1}$) is the hypervolume determined by the solutions
on the first line with the reference point $\mathbf{r}_{1}=(r,r,r)$. The other
part (denoted as $HV_{2}$) is the hypervolume determined by the solutions on
the second line with the reference point $\mathbf{r}_{2}=(r,0,r)$.

Figure 8: An illustration of the decomposition of the hypervolume into two
parts.

Then, the hypervolume can be calculated as $HV=HV_{1}+HV_{2}$. Thus,
maximizing $HV$ is equivalent to maximizing $HV_{1}+HV_{2}$. We can observe
that $HV_{1}$ is the two-dimensional hypervolume in the $f_{1}\text{-}f_{3}$
space (denoted as $HV_{1}^{f_{1}\text{-}f_{3}}$) multiplying $|r|$, and
$HV_{2}$ is the two-dimensional hypervolume in the $f_{1}\text{-}f_{2}$ space
(denoted as $HV_{2}^{f_{1}\text{-}f_{2}}$) multiplying $|r|$. Therefore,
maximizing $HV_{1}+HV_{2}$ is equivalent to maximizing
$HV_{1}^{f_{1}\text{-}f_{3}}+HV_{2}^{f_{1}\text{-}f_{2}}$.

Based on Lemma 1, we can get that the $\mu_{1}$ solutions are equispaced on
the first line and the $\mu_{2}$ solutions are equispaced on the second line,
in order to maximize $HV_{1}^{f_{1}\text{-}f_{3}}$ and
$HV_{2}^{f_{1}\text{-}f_{2}}$ respectively. Note that the reference points for
$HV_{1}^{f_{1}\text{-}f_{3}}$ and $HV_{2}^{f_{1}\text{-}f_{2}}$ are
$\mathbf{r}_{1}^{f_{1}\text{-}f_{3}}=(r,r)$ and
$\mathbf{r}_{2}^{f_{1}\text{-}f_{2}}=(r,0)$, respectively. Based on Lemma 1,
if $r\leq-1/(\mu_{1}-1)$, the two extreme points $(1,0,0)$ and $(0,0,1)$ of
the first line are included in the $\mu_{1}$ solutions. If $r\leq-1/\mu_{2}$,
one extreme point $(0,1,0)$ of the second line is included in the $\mu_{2}$
solutions. Thus, if $r\leq\min\\{-1/(\mu_{1}-1),-1/\mu_{2}\\}$, the three
extreme points are all included.

Next, based on the condition $r\leq\min\\{-1/(\mu_{1}-1),-1/\mu_{2}\\}$, we
determine the values of $\mu_{1}$ and $\mu_{2}$. First,
$HV_{1}^{f_{1}\text{-}f_{3}}$ and $HV_{2}^{f_{1}\text{-}f_{2}}$ are calculated
as illustrated in Fig. 9. $HV_{1}^{f_{1}\text{-}f_{3}}$ is the sum of the
areas of the triangle $A$ and the three rectangles $B$, $C$ and $D$, minus the
areas of the grey triangles in Fig. 9 (a). $HV_{2}^{f_{1}\text{-}f_{2}}$ is
the sum of the areas of the triangle $A$ and the rectangle $B$, minus the
areas of the grey triangles in Fig. 9 (b). More specifically, they are
calculated as follows:

$\displaystyle HV_{1}^{f_{1}\text{-}f_{3}}$
$\displaystyle=\frac{1}{2}-r-r+r^{2}-\frac{1}{2(\mu_{1}-1)^{2}}\times(\mu_{1}-1),$
(8) $\displaystyle=\frac{1}{2}+r(r-2)-\frac{1}{2(\mu_{1}-1)},$ $\displaystyle
HV_{2}^{f_{1}\text{-}f_{2}}$
$\displaystyle=\frac{1}{2}-r-\frac{1}{2\mu_{2}^{2}}\times\mu_{2},$
$\displaystyle=\frac{1}{2}-r-\frac{1}{2\mu_{2}}.$

(a) $HV_{1}^{f_{1}\text{-}f_{3}}$ (b) $HV_{2}^{f_{1}\text{-}f_{2}}$

Figure 9: An illustration of calculating $HV_{1}^{f_{1}\text{-}f_{3}}$ and
$HV_{2}^{f_{1}\text{-}f_{2}}$.

For hypervolume maximization, we can formulate the following optimization
problem:

maximize: $\displaystyle
HV_{1}^{f_{1}\text{-}f_{3}}+HV_{2}^{f_{1}\text{-}f_{2}}$ (9)
$\displaystyle=1-\frac{1}{2(\mu_{1}-1)}-\frac{1}{2\mu_{2}}+r(r-3),$ subject
to: $\displaystyle\mu_{1}+\mu_{2}=\mu\text{ and
}\mu_{1},\mu_{2}\in\mathbb{Z}_{+}.$

The above convex optimization problem can be easily solved by relaxing
$\mu_{1}$ and $\mu_{2}$ to real values. The solution of the optimization
problem is

$\mu_{1}=\frac{\mu+1}{2},\mu_{2}=\frac{\mu-1}{2}.$ (10)

If $\mu$ is odd, Eq. (10) is the optimal solution of (9). In this case,
$\mu_{1}-\mu_{2}=1$, which means that the same number of solutions lie on each
of the two lines (since the joint extreme point $(1,0,0)$ is not counted in
$\mu_{2}$).

If $\mu$ is even, then the optimal solution of (9) is
$\mu_{1}=\lceil\frac{\mu+1}{2}\rceil$,
$\mu_{2}=\lfloor\frac{\mu-1}{2}\rfloor$, or
$\mu_{1}=\lfloor\frac{\mu+1}{2}\rfloor$,
$\mu_{2}=\lceil\frac{\mu-1}{2}\rceil$. In this case, $\mu_{1}-\mu_{2}=2$ or
$\mu_{1}-\mu_{2}=0$, which means that one more or less solution lie on the
first line than on the second line (since the joint extreme point $(1,0,0)$ is
not counted in $\mu_{2}$).

We have shown the condition for the reference point
$r\leq\min\\{-1/(\mu_{1}-1),-1/\mu_{2}\\}$ in order to guarantee the inclusion
of the three extreme points. Based on the above results, if $\mu$ is odd,
$r\leq\min\\{-1/(\mu_{1}-1),-1/\mu_{2}\\}=-1/\mu_{2}=-2/(\mu-1)$. If $\mu$ is
even,
$r\leq\min\\{-1/(\mu_{1}-1),-1/\mu_{2}\\}=-1/\lfloor\frac{\mu-1}{2}\rfloor$. ∎

###  III-B Type IV Pareto Front

Let us consider the Type IV Pareto front with two lines where the first line
is $f_{1}+f_{2}=1,f_{1},f_{2}\geq 0$ and $f_{3}=1$, and the second line is
$f_{1}+f_{3}=1,f_{1},f_{3}\geq 0$ and $f_{2}=1$ as in Fig. 7 (b). Different
from the analysis on the Type III Pareto front, we focus on investigating a
uniform solution set on the Type IV Pareto front as illustrated in Fig. 7 (b),
and analyze whether a uniform solution set is optimal for hypervolume
maximization. Here a uniform solution set means the same number of solutions
are uniformly distributed on each of the two lines.

We have the following theorem for this type of Pareto front.

######  Theorem 2.

For $\mu>3$ solutions on the Type IV Pareto front, a uniform solution set is
not optimal for hypervolume maximization.

###### Proof.

First, we assume that there are $\mu^{\prime}$ solutions uniformly distributed
on each of the two lines, then $\mu^{\prime}=(\mu+1)/2$. Let
$\mathbf{a}_{1},\mathbf{a}_{2},...,\mathbf{a}_{\mu^{\prime}}$ denote the
solutions on the line from $(0,1,1)$ to $(1,1,0)$ where
$\mathbf{a}_{1}=(0,1,1)$ and $\mathbf{a}_{\mu^{\prime}}=(1,1,0)$ are the two
extreme solutions of this line. Fig. 7 (b) illustrates the hypervolume
contributions of the uniformly distributed solutions on the Type IV Pareto
front. We can see that different solutions have different hypervolume
contributions, and each hypervolume contribution is a cuboid. For the
hypervolume contribution of solution $\mathbf{a}_{i}$, the height of the
cuboid is $\frac{1}{\mu^{\prime}-1}$ and the basal area of the cuboid is
$(i-1)(\frac{1}{\mu^{\prime}-1})^{2}$. Thus, the hypervolume contribution of
$\mathbf{a}_{i}$ is

$\displaystyle
HVC(\mathbf{a}_{i})=(i-1)\left(\frac{1}{\mu^{\prime}-1}\right)^{3},\text{
}i=2,...,\mu^{\prime}-1.$ (11)

(a) Before moving a solution (b) After moving a solution

Figure 10: An illustration of moving a solution.

If we move $\mathbf{a}_{i}$ towards $\mathbf{a}_{i+1}$ for any
$i\in\\{2,...,\mu^{\prime}-1\\}$ (i.e., only one solution is moved and all the
others are fixed as illustrated in Fig. 10), a new solution
$\mathbf{a}^{\prime}_{i}=\mathbf{a}_{i}+\alpha(\mathbf{a}_{i+1}-\mathbf{a}_{i})$
where $\alpha\in[0,1]$ is obtained. We can see that the hypervolume
contribution of $\mathbf{a}^{\prime}_{i}$ is composed by two cuboids $A$ and
$B$. The height of the two cuboids is $(1-\alpha)(\frac{1}{\mu^{\prime}-1})$.
The basal area of $A$ is $\alpha(\frac{1}{\mu^{\prime}-1})^{2}$, and the basal
area of $B$ is
$(1+\alpha)(\frac{1}{\mu^{\prime}-1})\times(i-1)(\frac{1}{\mu^{\prime}-1})=(1+\alpha)(i-1)(\frac{1}{\mu^{\prime}-1})^{2}$.
Thus, the hypervolume contribution of $\mathbf{a}^{\prime}_{i}$ is

$\displaystyle HVC(\mathbf{a}^{\prime}_{i})$
$\displaystyle=\left(\alpha\left(\frac{1}{\mu^{\prime}-1}\right)^{2}+(1+\alpha)(i-1)\left(\frac{1}{\mu^{\prime}-1}\right)^{2}\right)$
(12) $\displaystyle\times(1-\alpha)\left(\frac{1}{\mu^{\prime}-1}\right)$
$\displaystyle=[(i-1)(1-\alpha)(1+\alpha)+\alpha(1-\alpha)]\left(\frac{1}{\mu^{\prime}-1}\right)^{3}.$

The hypervolume contribution difference between $\mathbf{a}^{\prime}_{i}$ and
$\mathbf{a}_{i}$ is

$HVC(\mathbf{a}^{\prime}_{i})-HVC(\mathbf{a}_{i})=(-i\alpha^{2}+\alpha)\left(\frac{1}{\mu^{\prime}-1}\right)^{3}.$
(13)

It is easy to obtain that if $0<\alpha<1/i$,
$HVC(\mathbf{a}^{\prime}_{i})-HVC(\mathbf{a}_{i})>0$. This indicates that
$\mathbf{a}^{\prime}_{i}$ has a larger hypervolume contribution than
$\mathbf{a}_{i}$. Thus, we can improve the overall hypervolume by moving
$\mathbf{a}_{i}$ to $\mathbf{a}^{\prime}_{i}$. Therefore, the original uniform
solution set is not optimal for hypervolume maximization. ∎

###  III-C Type V Pareto Front

Let us consider the Type V Pareto front with a triangular shape specified by
$f_{1}+f_{2}+f_{3}=1,f_{1},f_{2},f_{3}\geq 0$ as shown in Fig. 7 (c).

We present the following theorem describing the hypervolume optimal
$\mu$-distribution on the Type V Pareto front.

######  Theorem 3.

For $\mu>3$ solutions on the Type III Pareto front,

  1. 1.

if $(\mu\mod 3)=0$, the optimal $\mu$-distribution is that the same number of
solutions lie uniformly on each of the three lines where the three extreme
points (i.e., (1,0,0), (0,1,0), (0,0,1)) are included, under the condition of
$r\leq-3/\mu$,

  2. 2.

if $(\mu\mod 3)\neq 0$, the optimal $\mu$-distribution is that a different
number of solutions lie uniformly on each of the three lines where two lines
have the same number of solutions and the other line has one more/less
solution, and the three extreme points (i.e., (1,0,0), (0,1,0), (0,0,1)) are
included, under the condition of $r\leq-1/\lfloor\frac{\mu}{3}\rfloor$.

######  Remark 1.

The proof of Theorem 3 is similar to that of Theorem 1. We provide the
detailed proof of Theorem 3 in Section I of the supplementary material.

###  III-D Type VI Pareto Front

Let us consider the Type VI Pareto front with an inverted triangular shape
specified by $f_{1}+f_{2}+f_{3}=2,0\leq f_{1},f_{2},f_{3}\leq 1$ as shown in
Fig. 7 (d). Similar to the analysis on the Type IV Pareto front, we
investigate whether a uniform solution set is optimal for hypervolume
maximization. Here a uniform solution set means the same number of solutions
are uniformly distributed on each of the three lines.

We have the following theorem for this type of Pareto front.

######  Theorem 4.

For $\mu>6$ solutions on the Type VI Pareto front, a uniform solution set is
not optimal for hypervolume maximization.

######  Remark 2.

The proof of Theorem 4 is similar to that of Theorem 2. That is, the
hypervolume of a uniform solution set can be improved by moving one solution.
We provide the detailed proof of Theorem 4 in Section II of the supplementary
material.

######  Remark 3.

Here we need to emphasize that Theorem 4 only holds for $\mu>6$. For the case
of $\mu\leq 6$ (i.e., at most three solutions lie on each line), we cannot
move one solution to get a better overall hypervolume. For example, if there
are three uniformly distributed solutions on each line (i.e., one midpoint and
two extreme points), the overall hypervolume will be decreased (instead of
increased) by moving any of the three midpoints. As will be shown in Section
IV, when $\mu=3$ and $6$ the uniform solution set on the Type VI Pareto front
is optimal for hypervolume maximization.

###  III-E Discussions

####  III-E1 Explanations of the results in Fig. 1

In this section, we have investigated the hypervolume optimal
$\mu$-distribution on four types of line-based Pareto fronts. Through
theoretical analysis, we showed that the uniform solution set is optimal for
hypervolume maximization on the Type III and Type V Pareto fronts, whereas it
is not optimal for hypervolume maximization on the Type IV and Type VI Pareto
fronts. Now we can explain the results in Fig. 1. Since the Pareto front in
Fig. 1 (a) is Type III, the uniform solution set has a larger hypervolume than
any other solution sets. However, since the Pareto front in Fig. 1 (d) is Type
IV, the uniform solution set is not optimal for hypervolume maximization.
Similarly, since the Pareto front in Fig. 1 (e) is Type V, the uniform
solution set has a larger hypervolume than any other solution sets. However,
since the Pareto front in Fig. 1 (h) is Type VI, the uniform solution set is
not optimal for hypervolume maximization.

We need to note that maximization of each objective is assumed in this paper.
If the minimization case is considered, then the conclusions for the Type
III/V and the Type IV/VI Pareto fronts will be exchanged. That is, in the
minimization case, the uniform solution set is optimal for hypervolume
maximization on the Type IV and Type VI Pareto fronts whereas it is not
optimal on the Type III and Type V Pareto fronts.

####  III-E2 Hypervolume optimal $\mu$-distributions on Types IV and VI Pareto
fronts

We have proved that a uniform solution set on the Type IV or Type VI Pareto
front is not optimal for hypervolume maximization. The optimal
$\mu$-distributions on these two types of Pareto fronts are not theoretically
derived in this paper. However, we can empirically investigate their optimal
$\mu$-distributions. Fig. 1 (c) and (g) show the obtained solution sets by
SMS-EMOA on the Types IV and VI Pareto fronts, respectively. For the Type IV
Pareto front, we can see that solutions are sparsely distributed around the
joint extreme point of the two lines. From the joint extreme point to the
other two extreme points, solutions become denser and denser. For the Type VI
Pareto front, we can see that solutions are sparsely distributed around the
three extreme points. More solutions are distributed in the middle of the
three lines.

####  III-E3 Motivation of investigating line-based Pareto fronts

The four line-based Pareto fronts considered in this section are not so
realistic. They can be hardly found in real-world applications. However, as
shown in [17], when the reference point is sufficiently far away, the
solutions for hypervolume maximization are distributed on the boundary of some
realistic Pareto fronts (e.g., the Pareto fronts of DTLZ1-1 [26] and WFG3
[27]). In this case, it is meaningful to investigate the hypervolume optimal
$\mu$-distribution on the line-based Pareto fronts since the line-based Pareto
fronts can be viewed as the boundary of some realistic Pareto fronts. This is
the main motivation to investigate the line-based Pareto fronts.

####  III-E4 Lesson learned from line-based Pareto fronts

From Fig. 7 we can see that the Type III and IV Pareto fronts are very
similar, and the Type V and VI Pareto fronts are very similar. The only
difference is the way to combine different lines. This difference leads to
totally different results. We can see that for the Type III and V Pareto
fronts, the hypervolume can be decomposed into independent parts. However, for
the Type IV and VI Pareto fronts, the hypervolume cannot be decomposed into
independent parts. That is, the solution set is uniform for hypervolume
maximization only if the hypervolume can be decomposed into independent parts.
This is the main lesson we can learn from the line-based Pareto fronts.

####  III-E5 Construction of Type III-VI Pareto fronts

We can also construct test problems with Type III-VI Pareto fronts. For
example, let us consider a multi-line distance minimization problem [28] with
constraints as shown in the left figure of Fig. 11, where the objectives are
to minimize the distance to each of the three lines: $AB$, $AC$ and $BC$. In
the left figure of Fig. 11, the inside of the triangle $ABC$ and the line $BC$
are infeasible. Then the Pareto set of this problem is line $AB$ and line
$AC$. The Pareto front (i.e., the projection of these two lines into the
objective space) is Type III. If we consider to minimize the minus distance to
each line (which is equivalent to maximize the distance to each line) as shown
in the right figure of Fig. 11, given the infeasible region defined, the
Pareto set is the union of the two red lines. In this case, the Pareto front
is Type IV (the objective is the minus distance to each line).

Figure 11: An illustration of the multi-line distance minimization problem
with constraints. (a) The inside of the triangle $ABC$ and the line $BC$ are
infeasible. The union of the line $AB$ and the line $AC$ is the Pareto set.
(b) The objective is the minus distance to each line. The union of the two
line segments is the Pareto set.

Similarly, we can use the multi-line distance minimization problem to
construct a Type V or Type VI Pareto front. The details are provided in
Section IV of the supplementary material.

##  IV Plane-based Pareto fronts

In the last section, we only considered the line-based Pareto fronts in three
dimensions and showed that the hypervolume optimal $\mu$-distribution is not
always uniform on these Pareto fronts. In this section, we investigate plane-
based Pareto fronts, which are more commonly seen in multi-objective
optimization test problems (e.g., three-objective DTLZ1 [29] and DTLZ1-1
[26]).

The following two types of plane-based Pareto fronts were considered by
Ishibuchi et al. [17]:

  1. 1.

Type VII: The linear triangular Pareto front specified by
$f_{1}+f_{2}+f_{3}=1,f_{1},f_{2},f_{3}\geq 0$ (see Fig. 12 (a)).

  2. 2.

Type VIII: The linear inverted triangular Pareto front specified by
$f_{1}+f_{2}+f_{3}=2,0\leq f_{1},f_{2},f_{3}\leq 1$ (see Fig. 12 (b)).

Next, the hypervolume optimal $\mu$-distribution on each of these two types of
Pareto fronts is investigated.

(a) Type VII Pareto front (b) Type VIII Pareto front

Figure 12: Plane-based Pareto fronts in three dimensions.

(a) $H=1$

(b) $H=2$

(c) $H=3$

(d) $H=4$

(e) $H=5$

(f) $H=6$

(g) $H=7$

(h) $H=8$

(i) $H=9$

(j) $H=10$

Figure 13: The DAS solution sets.

(a) $H=1$

(b) $H=2$

(c) $H=3$

(d) $H=4$

(e) $H=5$

(f) $H=6$

(g) $H=7$

(h) $H=8$

(i) $H=9$

(j) $H=10$

Figure 14: The best solution sets obtained by SMS-EMOA.

###  IV-A Type VII Pareto Front

For the DAS solution set on the Type VII Pareto front, if the reference point
is specified as $r=-1/H$, all the solutions have the same hypervolume
contribution as shown in Fig. 12 (a). As already shown in the previous
sections, a uniformly distributed solution set is optimal for hypervolume
maximization when each solution has the same hypervolume contribution (e.g.,
Types I, III and V Pareto fronts). Thus, intuitively we may think that the DAS
solution set is also optimal for hypervolume maximization.

In order to examine whether this intuition is correct or not, we perform SMS-
EMOA on the Type VII Pareto front to search for the optimal
$\mu$-distribution. Here we use SMS-EMOA to do the search since it is proved
by Beume et al. [30] that SMS-EMOA is able to find the optimal
$\mu$-distribution on a two-objective linear Pareto front. Whereas there is no
theoretical guarantee on the three-objective linear Pareto front, SMS-EMOA is
powerful for searching for the optimal $\mu$-distribution in the three-
objective case. We set $H=1,2,...,10$ and the reference point $r=-1/H$, and
use SMS-EMOA to search for the optimal $\mu$-distribution on the Type VII
Pareto front. In order to make sure that the obtained solution set is optimal
(or very close to optimal), we use a large number of generations 10,000 and a
large number of independent runs 100 for each $H$. The best solution set among
100 runs is used as the best optimal $\mu$-distribution for each case.

Table I shows the hypervolume of the best solution sets obtained by SMS-EMOA,
and the DAS solution sets. From Table I, we can observe that for each $H$, the
hypervolume of the DAS solution set is smaller than or equal to the
hypervolume of the best solution set obtained by SMS-EMOA. Specifically, the
DAS solution set has the same hypervolume value as the best solution set
obtained by SMS-EMOA when $H=1,2$. Moreover, all the 100 solution sets
obtained by SMS-EMOA for each $H=1,2$ have the same hypervolume value. This
means that the DAS solution set is optimal for hypervolume maximization when
$H=1,2$, which is consistent with our intuition. However, it is not optimal
for hypervolume maximization when $H=3,...,10$, which is contrary to our
intuition. Thus, the intuition mentioned above is not always correct.

TABLE I: Hypervolume of the solution sets generated by DAS and obtained by SMS-EMOA. The reference point is specified as $r=-1/H$. The better hypervolume value is highlighted in bold for each $H$. $H$ ($\mu$) | DAS | SMS-EMOA
---|---|---
1 (3) | 4.0000 | 4.0000
2 (6) | 1.2500 | 1.2500
3 (10) | 0.7407 | 0.7422
4 (15) | 0.5469 | 0.5483
5 (21) | 0.4480 | 0.4497
6 (28) | 0.3889 | 0.3905
7 (36) | 0.3499 | 0.3515
8 (45) | 0.3223 | 0.3236
9 (55) | 0.3018 | 0.3031
10 (66) | 0.2860 | 0.2872

Figs. 13-14 show the DAS solution sets and the best solution sets obtained by
SMS-EMOA, respectively. We can see that when $H=1,2$, the DAS solution sets
are the same as the best solution sets obtained by SMS-EMOA. However, when
$H=3,...,10$, they are totally different. The solution sets obtained by SMS-
EMOA are not as uniform as the DAS solution sets for $H=3,...,10$.

In the above experiments, we use the reference point suggested in [18] for
hypervolume comparison (i.e., $r=-1/H$). In the case of the Type VII Pareto
front, the optimal $\mu$-distribution strongly depends on the reference point
specification [18]444This conclusion holds for the inverted triangular Pareto
front in [18] since the minimization case is considered in [18]. However, this
conclusion holds for the triangular Pareto front in this paper since we
consider the maximization case.. When the reference point is far away from the
Pareto front (e.g., $r=-100$), all solutions in the optimal $\mu$-distribution
are on the sides of the Pareto front. When the nadir point is used as the
reference point (i.e., $r=0$), no solutions in the optimal $\mu$-distribution
are on the sides of the Pareto front.

Now we want to know whether we can improve the DAS solution set for
$H=3,...,10$ using SMS-EMOA. Through experiments, we found that the DAS
solution set cannot be further improved by SMS-EMOA. This interesting
observation motivates us to examine the property of the DAS solution set. The
following theorem shows that the DAS solution set is locally optimal for
hypervolume maximization with respect to the $(\mu+1)$ selection scheme, i.e.,
the DAS solution set cannot be further improved by replacing one solution.

######  Theorem 5.

Given the reference point $r=-1/H$, the DAS solution set is locally optimal
for hypervolume maximization with respect to a $(\mu+1)$ selection scheme.

###### Proof.

We will prove this theorem by adding one arbitrary solution on the Pareto
front and showing that this solution has the least hypervolume contribution,
which implies that this solution is removed and the original set cannot be
improved.

Firstly, the Pareto front is divided into different triangular regions as
illustrated in Fig. 15. We can see that there are two types of regions: the
triangular regions and the inverted triangular regions. Next, the two types of
regions are considered separately.

Figure 15: The Pareto front is divided into triangular and inverted triangular
regions.

If a solution $\mathbf{p}$ is added in an inverted triangular region as
illustrated in Fig. 16 (a), the hypervolume contributions of three solutions
$\mathbf{a},\mathbf{b},\mathbf{c}$ (i.e., the three vertices of the triangle)
are influenced by $\mathbf{p}$.

(a) Adding a solution in the inverted triangular region (b) Adding a solution
in the triangular region

Figure 16: Adding a solution on the Pareto front.

Suppose $\mathbf{p}=(x,y,z)$, $\mathbf{a}=(1,0,1)$, $\mathbf{b}=(0,1,1)$ and
$\mathbf{c}=(1,1,0)$, then the hypervolume contribution of each of these
solutions can be calculated as follows:

$\displaystyle HVC(\mathbf{p})=xyz,$ (14) $\displaystyle
HVC(\mathbf{a})=1-xz,\text{ }HVC(\mathbf{b})=1-yz,\text{
}HVC(\mathbf{c})=1-xy.$

Given the conditions $x+y+z=2$ and $0\leq x,y,z\leq 1$, we prove that
$HVC(\mathbf{p})<HVC(\mathbf{c})$ as follows:

$\displaystyle HVC(\mathbf{p})$ $\displaystyle=xyz=xy(2-x-y)=xy(1-x)+xy(1-y)$
(15) $\displaystyle<y(1-x)+x(1-y)=(x+y-xy)-xy.$

Let $f(x,y)=x+y-xy$, we have $f(0,0)=0$ and $f(1,1,)=1$. Since $\nabla
f(x,y)=(1-y,1-x)>0$, we have $f(x,y)<f(1,1)=1$. Then, based on Eq. (15), we
have $HVC(\mathbf{p})<1-xy=HVC(\mathbf{c})$. Similarly, we can also prove that
$HVC(\mathbf{p})<HVC(\mathbf{a})$ and $HVC(\mathbf{p})<HVC(\mathbf{b})$. Thus,
$\mathbf{p}$ is the least hypervolume contributor and $\mathbf{p}$ is removed.

If a solution $\mathbf{p}$ is added in a triangular region as illustrated in
Fig. 16 (b), the hypervolume contributions of six solutions
$\mathbf{a},\mathbf{b},\mathbf{c},\mathbf{d},\mathbf{e},\mathbf{f}$ are
influenced by $\mathbf{p}$.

Suppose $\mathbf{p}=(x,y,z)$, $\mathbf{a}=(0,0,1)$, $\mathbf{b}=(1,0,0)$,
$\mathbf{c}=(0,1,0)$, $\mathbf{d}=(1,-1,1)$, $\mathbf{e}=(-1,1,1)$ and
$\mathbf{f}=(1,1,-1)$, then the hypervolume contribution of each of these
solutions can be calculated as follows:

$\displaystyle HVC(\mathbf{p})=xyz+xy+xz+yz,$ (16) $\displaystyle
HVC(\mathbf{a})=1-z,\text{ }HVC(\mathbf{b})=1-x,\text{ }HVC(\mathbf{c})=1-y,$
$\displaystyle HVC(\mathbf{d})=1-xz,\text{ }HVC(\mathbf{e})=1-yz,\text{
}HVC(\mathbf{f})=1-xy.$

Given the conditions $x+y+z=1$ and $0\leq x,y,z\leq 1$, we prove that
$HVC(\mathbf{p})<HVC(\mathbf{a})$ as follows:

$\displaystyle HVC(\mathbf{p})$ $\displaystyle=xyz+xy+xz+yz$ (17)
$\displaystyle=xy(1-x-y)+xy$ $\displaystyle+x(1-x-y)+y(1-x-y)$
$\displaystyle=x+y-x^{2}(1+y)-y^{2}(1+x)$
$\displaystyle<x+y=1-z=HVC(\mathbf{a}).$

Similarly, we can prove that $HVC(\mathbf{p})<HVC(\mathbf{b})$ and
$HVC(\mathbf{p})<HVC(\mathbf{c})$. It is easy to observe that
$HVC(\mathbf{a})<HVC(\mathbf{d})$ and $HVC(\mathbf{a})<HVC(\mathbf{e})$.
Similarly, $HVC(\mathbf{b})<HVC(\mathbf{d})$ and
$HVC(\mathbf{b})<HVC(\mathbf{f})$, $HVC(\mathbf{c})<HVC(\mathbf{e})$ and
$HVC(\mathbf{c})<HVC(\mathbf{f})$. Based on these relations, we can conclude
that $\mathbf{p}$ is the least hypervolume contributor and $\mathbf{p}$ is
removed. ∎

######  Remark 4.

In Theorem 5, the reference point is specified as $r=-1/H$. This is the
suggested reference point specification for the hypervolume indicator as
discussed in Section II-D. If the reference point is specified as $r<-1/H$,
Theorem 5 may not hold anymore since the solutions on the boundary of the
Pareto front have larger hypervolume contributions than the inner solutions.
In this case, replacing an inner solution by a boundary solution can improve
the hypervolume of the whole solution set. When $r>-1/H$, Theorem 5 does not
hold since the reference point is too close to the Pareto front.

###  IV-B Type VIII Pareto Front

If we invert the DAS solution set, we can obtain a uniformly distributed
solution set on the inverted triangular Pareto front as shown in Fig. 12 (b).
We call this uniform solution set as the inverted DAS solution set. If the
reference point is specified as $r=-1/H$, all the solutions have the same
hypervolume contribution as shown in Fig. 12 (b). Similarly, we use SMS-EMOA
to search for the optimal $\mu$-distribution on the Type VIII Pareto front.
All the experimental settings are the same as in the previous subsection.
Table II shows the hypervolume of the inverted DAS solution sets and the best
solution sets obtained by SMS-EMOA. From Table II, we can observe that for
each $H$, the hypervolume of the inverted DAS solution set is smaller than or
equal to the hypervolume of the best solution set obtained by SMS-EMOA, which
means that the inverted DAS solution set is not always optimal for hypervolume
maximization. In Section V of the supplementary material, we visually show the
inverted DAS solution sets and the best solution sets obtained by SMS-EMOA.
Similar observations can be obtained to the case of the Type VII Pareto front.

TABLE II: Hypervolume of the inverted DAS solution sets and the best solution sets obtained by SMS-EMOA. The reference point is specified as $r=-1/H$. The better hypervolume value is highlighted in bold for each $H$. $H$ ($\mu$) | Inverted DAS | SMS-EMOA
---|---|---
1 (3) | 7.0000 | 7.0000
2 (6) | 2.8750 | 2.8750
3 (10) | 2.0000 | 2.0019
4 (15) | 1.6406 | 1.6421
5 (21) | 1.4480 | 1.4496
6 (28) | 1.3287 | 1.3303
7 (36) | 1.2478 | 1.2493
8 (45) | 1.1895 | 1.1908
9 (55) | 1.1454 | 1.1466
10 (66) | 1.1110 | 1.1122

We use the suggested reference point specification in [18] for hypervolume
comparison (i.e., $r=-1/H$). In the case of the Type VIII Pareto front, the
optimal $\mu$-distribution does not change when $r\leq-1/H$ [18]. That is, the
same distribution is always optimal for any specification of the reference
point $\mathbf{r}=(r,r,r)$ satisfying $r\leq-1/H$. This is totally different
from the case of the Type VII Pareto front.

In a similar manner to the case of the triangular Pareto front, we have the
following theorem which shows that the inverted DAS solution set is locally
optimal for hypervolume maximization with respect to the $(\mu+1)$ selection
scheme.

######  Theorem 6.

Given the reference point $r=-1/H$, the inverted DAS solution set is locally
optimal for hypervolume maximization with respect to the $(\mu+1)$ selection
scheme.

###### Proof.

Follow the proof way of Theorem 5, we can easily get this conclusion. ∎

######  Remark 5.

In Theorem 6, the reference point is also specified as $r=-1/H$. Different
from Theorem 5, Theorem 6 still holds for $r<-1/H$. This is because the change
of the reference point only influence the hypervolume contribution of the
three extreme points of the Type VIII Pareto front. This is totally different
from the Type VII Pareto front. When $r>-1/H$, Theorem 6 does not hold since
the reference point is too close to the Pareto front.

###  IV-C Discussions

####  IV-C1 The optimality of the solution sets obtained by SMS-EMOA

In this section, we have shown that the DAS solution sets and the inverted DAS
solution sets are not always the optimal $\mu$-distributions whereas their
distributions look perfectly uniform. The exact hypervolume optimal
$\mu$-distributions on the Types VII and VIII Pareto fronts are not derived in
this paper, and we used SMS-EMOA to search for the optimal
$\mu$-distributions. It is clear that the solution sets obtained by SMS-EMOA
cannot be guaranteed to be optimal. Proving the optimality of the obtained
solution sets is a challenging task in the future.

####  IV-C2 The hypervolume contribution of each solution

Each solution of the DAS solution set (or the inverted DAS solution set) has
the same hypervolume contribution when the reference point is specified as
$r=-1/H$. The counter-intuitive fact is that the whole solution set is not
optimal for hypervolume maximization when $H=3,...,10$. Thus, it is
interesting to investigate the hypervoume contribution of each solution for
the optimal solution set on the plane-based Pareto fronts. We take the Type
VII Pareto front and $H=3$ as an example. Fig. 17 shows the hypervolume
contribution of each solution for the DAS solution set and the best solution
set obtained by SMS-EMOA. We can observe that each solution has the same
hypervolume contribution in the DAS solution set whereas each solution has a
different hypervolume contribution in the best solution set obtained by SMS-
EMOA. We can also observe that the hypervolume contribution of an outer
solution (a solution far from the center of the Pareto front) is larger than
that of an inner solution (a solution close to the center of the Pareto
front). These observations may lead to new research directions in the future.

(a) DAS (HV=0.7407)

(b) SMS-EMOA (HV = 0.7422) (c) DAS (HV=0.7407) (d) SMS-EMOA (HV = 0.7422)

Figure 17: An illustration of the hypervolume contribution of each solution in
(a) the DAS solution set, (b) the best solution set obtained by SMS-EMOA. The
size of the circle represents the relative hypervolume contribution value of
each solution. (c) and (d) show the shape of the hypervolume of (a) and (b),
respectively. The reference point is specified as
$\mathbf{r}=(-1/3,-1/3,-1/3)$.

####  IV-C3 The uniqueness of the hypervolume optimal $\mu$-distribution

It is clear that a DAS solution set is unique on the Pareto front. That is, it
is impossible to have two different DAS solution sets with the same number of
solutions. However, it is not always the case for a solution set maximizing
the hypervolume indicator. As shown in Fig. 14, it is clear that the solution
sets with $H=1,2,3$ are unique. However, for the solution set with $H=4$, we
can rotate the solution set $\pm 120^{\circ}$ to get a different solution set.
Thus, the hypervolume optimal $\mu$-distribution does not necessarily to be
unique.

####  IV-C4 The solutions distribution for hypervolume maximization

Although the theoretical hypervolume optimal $\mu$-distributions on the plane-
based Pareto fronts are not derived in this paper, we can use the empirical
results in Fig. 14 to get a sense of how the solutions are distributed on the
Pareto fronts. From Fig. 14 (a)-(d) we can observe that the solutions are
symmetrically distributed. In our previous work [31], we empirically
investigated the hypervolume optimal $\mu$-distributions on the plane-based
Pareto fronts for $\mu=2,...,10$. We have similar observations, i.e., in most
cases the solutions are symmetrically distributed. Thus, this may be the law
of the hypervolume optimal $\mu$-distribution on the plane-based Pareto
fronts. However, proving this is a challenging task. We leave it as an open
question for future research.

####  IV-C5 Inspirations to EMO algorithm design

In the EMO literature, most decomposition-based EMOAs use the DAS method to
generate weight vectors or reference points. The discussions in this section
suggest the necessity of reconsidering the generation methods for weight
vectors or reference points, in order to obtain better hypervolume results for
these decomposition-based EMOAs. For the hypervolume-based EMOAs (e.g., SMS-
EMOA), the results in this section reveal that a $(\mu+1)$ selection scheme
may fall into local optimum. Thus, a mechanism to jump out of local optimum is
needed in this type of algorithms.

##  V Conclusions

In this paper, we investigated the hypervolume optimal $\mu$-distributions on
line- and plane-based Pareto fronts in three dimensions. First, we
investigated the optimal $\mu$-distributions on the line-based Pareto fronts
with two and three lines. We showed that the solution set is not always
uniform on these Pareto fronts for hypervolume maximization. The solutions are
only uniform on the Type III and Type V Pareto fronts, whereas the solutions
are non-uniform on the Type IV and Type VI Pareto fronts. Then, we
investigated the optimal $\mu$-distributions for the plane-based Pareto
fronts. We showed that the DAS solution set on the Type VII Pareto front and
the inverted DAS solution set on the Type VIII Pareto front are not always
optimal for hypervolume maximization, which is contrary to our intuition.
Table III summarizes all the conclusions mentioned in this paper. These
conclusions can provide more knowledge for the EMO researchers to better
understand the hypervolume indicator. A uniform solution set cannot always be
obtained by maximizing the hypervolume indicator, which reminds us to utilize
the hypervolume indicator in three dimensions more carefully.

TABLE III: A summary of the conclusions for the hypervolume optimal $\mu$-distribution on different Pareto fronts. Maximization of each objective is considered. Pareto front | Optimal $\mu$-distribution | Reference point
---|---|---
Type I | Uniform | $r\leq-1/(\mu-1)$
Type II | Nonuniform | $-$
Type III | Uniform | $r\leq-2/(\mu-1)$
Type IV | Nonuniform | $-$
Type V | Uniform | $r\leq-3/\mu$
Type VI | Nonuniform | $-$
Type VII | Uniform ($H=1,2$) | $r=-1/H$
| Nonuniform ($H>2$) |
Type VIII | Uniform ($H=1,2$) | $r=-1/H$
| Nonuniform ($H>2$) |

For our future work, we have the following research directions. 1) The exact
hypervolume optimal $\mu$-distributions on the Type IV, Type VI, Type VII and
Type VIII Pareto fronts were not derived in this paper. One future direction
is to precisely obtain the hypervolume optimal $\mu$-distributions for these
Pareto fronts. The hypervolume Newton method [32] may be a promising method
for this task. 2) We only considered three dimensions in this paper. It is
interesting to extend our research to higher dimensions and see what happens
there. 3) The non-uniformity caused by maximizing the hypervolume indicator
can be seen as a undesired property of the hypervolume indicator. How to solve
this issue is one research direction. Another research direction is to utilize
this property of hypervolume maximization for decision making (e.g., for the
search of knee regions of nonlinear Pareto fronts).

## References

  * [1] E. Zitzler, D. Brockhoff, and L. Thiele, “The hypervolume indicator revisited: On the design of pareto-compliant indicators via weighted integration,” in _2007 International Conference on Evolutionary Multi-Criterion Optimization_. Springer, 2007, pp. 862–876.
  * [2] M. Fleischer, “The measure of pareto optima applications to multi-objective metaheuristics,” in _2003 International Conference on Evolutionary Multi-Criterion Optimization_. Springer, 2003, pp. 519–533.
  * [3] N. Beume, B. Naujoks, and M. Emmerich, “SMS-EMOA: Multiobjective selection based on dominated hypervolume,” _European Journal of Operational Research_ , vol. 181, no. 3, pp. 1653–1669, 2007.
  * [4] M. Emmerich, N. Beume, and B. Naujoks, “An EMO algorithm using the hypervolume measure as selection criterion,” in _2005 International Conference on Evolutionary Multi-Criterion Optimization_ , 2005, pp. 62–76.
  * [5] S. Jiang, J. Zhang, Y.-S. Ong, A. N. Zhang, and P. S. Tan, “A simple and fast hypervolume indicator-based multiobjective evolutionary algorithm,” _IEEE Transactions on Cybernetics_ , vol. 45, no. 10, pp. 2202–2213, 2015\.
  * [6] J. Bader and E. Zitzler, “HypE: An algorithm for fast hypervolume-based many-objective optimization,” _Evolutionary Computation_ , vol. 19, no. 1, pp. 45–76, 2011.
  * [7] K. Shang and H. Ishibuchi, “A new hypervolume-based evolutionary algorithm for many-objective optimization,” _IEEE Transactions on Evolutionary Computation (Early access)_ , 2020.
  * [8] K. Shang, H. Ishibuchi, L. He, and L. M. Pang, “A survey on the hypervolume indicator in evolutionary multi-objective optimization,” _IEEE Transactions on Evolutionary Computation_ , 2020.
  * [9] A. Auger, J. Bader, D. Brockhoff, and E. Zitzler, “Theory of the hypervolume indicator: optimal $\mu$-distributions and the choice of the reference point,” in _Proceedings of the 10th ACM SIGEVO Workshop on Foundations of Genetic Algorithms_. ACM, 2009, pp. 87–102.
  * [10] M. Emmerich, A. Deutz, and N. Beume, “Gradient-based/evolutionary relay hybrid for computing pareto front approximations maximizing the s-metric,” in _2007 International Workshop on Hybrid Metaheuristics_. Springer, 2007, pp. 140–156.
  * [11] T. Friedrich, F. Neumann, and C. Thyssen, “Multiplicative approximations, optimal hypervolume distributions, and the choice of the reference point,” _Evolutionary computation_ , vol. 23, no. 1, pp. 131–159, 2015.
  * [12] P. K. Shukla, N. Doll, and H. Schmeck, “A theoretical analysis of volume based Pareto front approximations,” in _Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation_ , 2014, pp. 1415–1422.
  * [13] A. Auger, J. Bader, and D. Brockhoff, “Theoretically investigating optimal $\mu$-distributions for the hypervolume indicator: First results for three objectives,” in _2010 International Conference on Parallel Problem Solving from Nature_. Springer, 2010, pp. 586–596.
  * [14] H. K. Singh, “Understanding hypervolume behavior theoretically for benchmarking in evolutionary multi/many-objective optimization,” _IEEE Transactions on Evolutionary Computation_ , 2019.
  * [15] T. Glasmachers, “Optimized approximation sets for low-dimensional benchmark pareto fronts,” in _2014 International Conference on Parallel Problem Solving from Nature_. Springer, 2014, pp. 569–578.
  * [16] H. Ishibuchi, R. Imada, N. Masuyama, and Y. Nojima, “Comparison of hypervolume, IGD and IGD+ from the viewpoint of optimal distributions of solutions,” in _2019 International Conference on Evolutionary Multi-Criterion Optimization_. Springer, 2019, pp. 332–345.
  * [17] H. Ishibuchi, R. Imada, Y. Setoguchi, and Y. Nojima, “Hypervolume subset selection for triangular and inverted triangular pareto fronts of three-objective problems,” in _Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms_. ACM, 2017, pp. 95–110.
  * [18] ——, “Reference point specification in hypervolume calculation for fair comparison and efficient search,” in _Proceedings of the 2017 Genetic and Evolutionary Computation Conference_. ACM, 2017, pp. 585–592.
  * [19] R. Tanabe and H. Ishibuchi, “An analysis of quality indicators using approximated optimal distributions in a three-dimensional objective space,” _IEEE Transactions on Evolutionary Computation (Early access)_ , 2020.
  * [20] I. Das and J. E. Dennis, “Normal-boundary intersection: A new method for generating the pareto surface in nonlinear multicriteria optimization problems,” _SIAM Journal on Optimization_ , vol. 8, no. 3, pp. 631–657, 1998\.
  * [21] K. Shang, H. Ishibuchi, W. Chen, and L. Adam, “Hypervolume optimal $\mu$-distributions on line-based pareto fronts in three dimensions,” in _Parallel Problem Solving from Nature – PPSN XVI_ , T. Bäck, M. Preuss, A. Deutz, H. Wang, C. Doerr, M. Emmerich, and H. Trautmann, Eds. Cham: Springer International Publishing, 2020, pp. 257–270.
  * [22] A. Auger, J. Bader, D. Brockhoff, and E. Zitzler, “Hypervolume-based multiobjective optimization: Theoretical foundations and practical implications,” _Theoretical Computer Science_ , vol. 425, pp. 75–103, 2012\.
  * [23] D. Brockhoff, “Optimal $\mu$-distributions for the hypervolume indicator for problems with linear bi-objective fronts: Exact and exhaustive results,” in _2010 Asia-Pacific Conference on Simulated Evolution and Learning_. Springer, 2010, pp. 24–34.
  * [24] Q. Zhang and H. Li, “MOEA/D: A multiobjective evolutionary algorithm based on decomposition,” _IEEE Transactions on Evolutionary Computation_ , vol. 11, no. 6, pp. 712–731, 2007.
  * [25] K. Deb and H. Jain, “An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part i: solving problems with box constraints,” _IEEE Transactions on Evolutionary Computation_ , vol. 18, no. 4, pp. 577–601, 2013.
  * [26] H. Ishibuchi, Y. Setoguchi, H. Masuda, and Y. Nojima, “Performance of decomposition-based many-objective algorithms strongly depends on pareto front shapes,” _IEEE Transactions on Evolutionary Computation_ , vol. 21, no. 2, pp. 169–190, 2017.
  * [27] H. Ishibuchi, H. Masuda, and Y. Nojima, “Pareto fronts of many-objective degenerate test problems,” _IEEE Transactions on Evolutionary Computation_ , vol. 20, no. 5, pp. 807–813, 2015.
  * [28] M. Li, C. Grosan, S. Yang, X. Liu, and X. Yao, “Multiline distance minimization: A visualized many-objective test problem suite,” _IEEE Transactions on Evolutionary Computation_ , vol. 22, no. 1, pp. 61–78, 2017.
  * [29] K. Deb, L. Thiele, M. Laumanns, and E. Zitzler, “Scalable test problems for evolutionary multiobjective optimization,” in _Evolutionary Multiobjective Optimization_. Springer, 2005, pp. 105–145.
  * [30] N. Beume, B. Naujoks, M. Preuss, G. Rudolph, and T. Wagner, “Effects of 1-greedy $\mathcal{S}$-metric-selection on innumerably large pareto fronts,” in _2009 International Conference on Evolutionary Multi-Criterion Optimization_. Springer, 2009, pp. 21–35.
  * [31] H. Ishibuchi, L. M. Pang, and K. Shang, “Numerical analysis on optimal distributions of solutions for hypervolume maximization,” in _2020 IEEE International Conference on Systems, Man, and Cybernetics (SMC)_. IEEE, 2020, pp. 1103–1110.
  * [32] V. A. S. Hernández, O. Schütze, H. Wang, A. Deutz, and M. Emmerich, “The set-based hypervolume Newton method for bi-objective optimization,” _IEEE Transactions on Cybernetics_ , vol. 50, no. 5, pp. 2186–2196, 2018\.