Novel algorithm to calculate hypervolume indicator of Pareto
  approximation set
arXiv:0704.1196v1  [cs.CG]  10 Apr 2007
Novel algorithm to calculate hypervolume
indicator of Pareto approximation set
Qing Yang1 and Shengchao Ding2,3
1 School of Computer Science and Technology, South-Central University for
Nationalities, Wuhan, China
2 Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China
3 Graduate University of the Chinese Academy of Sciences, Beijing, China
dingshengchao@ict.ac.cn
Abstract. Hypervolume indicator is a commonly accepted quality mea-
sure for comparing Pareto approximation set generated by multi-objective
optimizers. The best known algorithm to calculate it for n points in d-
dimensional space has a run time of O(nd/2) with special data structures.
This paper presents a recursive, vertex-splitting algorithm for calculating
the hypervolume indicator of a set of n non-comparable points in d > 2
dimensions. It splits out multiple child hyper-cuboids which can not be
dominated by a splitting reference point. In special, the splitting refer-
ence point is carefully chosen to minimize the number of points in the
child hyper-cuboids. The complexity analysis shows that the proposed
algorithm achieves O(( d
)n) time and O(dn2) space complexity in the
worst case.
1 Introduction
Optimization for multiple conflicting objectives results in more than one optimal
solutions (known as Pareto-optimal solutions). Although one of these solutions
is to be chosen at the end, the recent trend in evolutionary and classical multi-
objective optimization studies have focused on approximating the set of Pareto-
optimal solutions. However, to assess the quality of Pareto approximation set,
special measures are needed [1].
Hypervolume indicator is a commonly accepted quality measure for compar-
ing approximation set generated by multi-objective optimizers. The indicator
measures the hypervolume of the dominated portion of the objective space by
Pareto approximation set and has received more and more attention in recent
years [2, 3, 1, 4].
There have been some studies that discuss the issue of fast hypervolume cal-
culation [5–8]. These algorithms partition the covered space into many cuboid-
shaped regions, within which the approach considering the dominated hyper-
volume as a special case of Klee’s measure problem is regarded as the cur-
rent best one. This approach [8] adopts orthogonal partition tree which requires
O(nd/2) storage and streaming variant [9]. Conceptual simplification of the im-
plementation are concerned and thus the algorithm achieves an upper bound of
http://arxiv.org/abs/0704.1196v1
O(n log n+ nd/2) for the hypervolume calculation. Ignoring the running time of
sorting the points according to the d-th dimension, O(n log n), the running time
of this approach is exponential of the dimension of space d.
This paper develops novel heuristics for the calculation of hypervolume in-
dicator. Special technologies are applied and the novel approach yields upper
bound of O((d
)n) runtime and consumes O(dn2) storage. The paper is orga-
nized as follows. In the next section, the hypervolume indicator is defined, and
some background on its calculation is provided. Then, an algorithm is proposed
which uses the so-called vertex-splitting technology to reduce the hypervolume.
The complexities of the proposed algorithm are analyzed in Section 4. The last
section concludes this paper with an open problem.
2 Background
Without loss of generality, for multi-objective optimization problems, if the d
objective functions f = (f1, . . . , fd) are considered with fi to be minimized,
not one optimal solution but a set of good compromise solutions are obtained
since that the objectives are commonly conflicting. The compromise solutions are
commonly called Pareto approximation solutions and the set of them is called the
Pareto approximation set. For a Pareto approximation set M = {y1, y2, . . . , yn}
produced in a run of a multi-objective optimizer, where yi = (yi1, . . . , yid) ∈
M ⊂ Rd, all the solutions are non-comparable following the well-known concept
of Pareto dominance. Specially, we say that yi dominates yk at the j-th dimension
if yij < ykj .
The unary hypervolume indicator of a set M consists of the measure of the
region which is simultaneously dominated by M and bounded above by a ref-
erence point r = (r1, . . . , rd) ∈ R
d such that rj ≥ maxi=1,...,n {yij}. In the
context of hypervolume indicator, we call the solutions in M as the domina-
tive points. As illustrated in Fig. 1(a), the shading region consists of an or-
thogonal polytope, and may be seen as the union of three axis-aligned hyper-
rectangles with one common vertex, i.e., the reference point r. Another example
in three dimensional space is shown in Fig. 1(b), where five dominative points,
y1 = (1, 2, 3), y2 = (4, 3, 2), y3 = (5, 1, 4), y4 = (3, 5, 1), y5 = (2, 2, 2.5), and the
reference point r = (6, 6, 6) are considered. The volume is the union of the vol-
umes of all the cuboids each of which is bounded by a vertex, where the common
regions are counted only once. If a point yk is dominated by another point yi,
the cuboid bounded by yk is completely covered by the cuboid bounded by yi.
And thus only the non-dominated points contribute to the hypervolume.
3 The proposed algorithm
In other works, e.g. the work of Beume and Rudolph [8], the hyper-cuboid in
d-dimensional space are partitioned into child hyper-cuboids along the d-th di-
mension and then all these child hypervolumes are gathered together by the
inclusion-exclusion principle [10].
(a) A hypervolume indicator in the two-
objective case
(b) A hypervolume indicator in the
three-objective case. To lay out the
cuboids well, the axes are rotated where
the reference point is shaded
In this paper, we step in another way. The hyper-cuboid is partitioned into
child hyper-cuboids at some splitting reference points and then all the child hy-
pervolumes are gathered directly. More detailed, given a point yi ∈ M , each of
other points inM must dominated yi at some dimensions for the non-comparable
relation. If the parts over yi are handled, the problem of calculating the hyper-
volume bounded by M and the reference point is figured out. The additional
part partitioned out at the j-th dimension is also a d-dimensional hyper-cuboid
whose vertices are ones beyond yi at such dimension. Their projections on the
hyperplane orthogonal to dimension j are all dominated by yi, and thus are
free from consideration. It should be noted that the reference point of child
hyper-cuboid is altered to r′ = (r1, . . . , yij , . . . , rd), namely the j-th coordinate
is replaced by yij . The other child hyper-cuboids are handled in the similar way.
In these processes, the given point is called the splitting reference point.
Obviously, the hyper-cuboids with more dominative points require more run
time to calculate the hypervolumes. To reduce the whole run time for calculating
all these child hyper-cuboids, the splitting reference point should be carefully
selected. The strategy adopted in this paper is described as follows.
(1) Let k = n − 1 and choose a point with the least dimensions on which the
point dominated by other k points.
(2) If some points tie, update k as k − 1 and then within these points, choose
a point with the least dimensions on which the point dominated by other k
points.
(3) Repeat the similar process until only single point is left or k = 1. And if
k = 1 and several points are left, the first found point is selected.
By the above principle, as an example, not y2 or other points but y5 is chosen
as the first splitting reference point for the case shown in Fig. 1(b). Two child
cuboids each bounded by one points and another child cuboid bounded by two
points are generated by splitting along y5. This is the optimal strategy in such
case.
The algorithm to calculate the hypervolume is shown in Algorithm 1. Some
major parameters are as follows.
– int[n][d] order The orders of all the dominative points at each dimension
are represented by a two-dimensional array of integer.
– int split The index of the point at which the hyper-cuboid is cut to
generate multiple child hyper-cuboids is called split.
– int[n] splitCount The numbers of k present in the split-th row of the
array order are saved in splitCount, where k = 0, . . . , n− 1.
– int[n] coveredCount The numbers of k present in the current checked
row of the array order are save in coveredCount, where k = 0, . . . , n− 1.
Moreover, some conventions are explained as follows.
– The subscript of yij begins with 1 while the index of array begins with 0.
Thus yij is same as y[i− 1][j − 1].
– Assume a and b are two arrays and n is an element. a[] ⇐ n means setting
each element of a as n, while a[] ⇐ b[] means copying all the elements of b
to a pairwise.
– Assume S is a set and x is an element. S ⇐ S + {x} means appending a
copy of x to S.
The inputs of the algorithm are a set of non-dominated (dominative) points
and a reference point, thus the hyper-cuboids are represented implicitly.
In fact, when the hyper-cuboid is cut into two child hyper-cuboids, there may
be some points dominated by the splitting reference point in the bigger cuboid,
and thus such points could be removed from the points set H . In the proposed
algorithm, it does not matter whether those points are removed or not.
4 Complexity Analysis
Before discussing the time-space complexity of the proposed algorithm, some
properties are presented firstly.
Lemma 1. Let δij be the number of points dominating yi at the j-th dimension.
(1) For d ≥ 2 and each i ∈ {1, . . . , n},
j=1 δij ≥ n− 1.
(2) For d ≥ 2 and each j ∈ {1, . . . , d},
i=1 δij ≤
(n− 1).
(3) For d = 2 and each i ∈ {1, . . . , n},
j=1 δij = n− 1.
j=1 δij ≤
(n− 1).
(5) For d ≥ 2 and each i ∈ {1, . . . , n},
j=1 δij ≤
(n− 1).
Algorithm 1 Calculate Hypervolume, CalcV olume(H)
Input: The hyper-cuboid H defined by the dominative points {y1, y2, . . . , yn} where
yi = (yi1, . . . , yid), and the reference point r = (r1, . . . , rd), namely H =
{y1, . . . , yn, r}. The initial number n of dominative points can be obtained from
the length of H and the dimension d is known too.
Output: The hypervolume of H , volume.
1: /* initialization */
2: if n = 1 then
3: return
|rj − y1j |;
4: end if
5: volume ⇐ 0;
6: splitCount[] ⇐ n;
7: /* count the numbers of points dominating every point at each dimension */
8: for j = 1 to d do
9: sort y1j , . . . , ynj ;
10: for all i such that 1 ≤ i ≤ n do
11: order[i− 1][j − 1] ⇐ number of points dominating yij strictly;
12: end for
13: end for
14: /* estimate split based on the statistical results of order */
15: for i = 1 to n do
16: coveredCount[] ⇐ 0;
17: for j = 1 to d do
18: coveredCount[order[i− 1, j − 1]]++;
19: end for
20: for k = n− 1 downto 0 do
21: if coveredCount[k] < splitCount[k] then
22: split ⇐ i;
23: splitCount[] ⇐ coveredCount[];
24: break;
25: end if
26: end for
27: end for
28: /* cut H at each dimension through the point indexed by split */
29: for j = 1 to d do
30: if order[split− 1][j − 1] > 0 then
31: H2 ⇐ {};
32: for all yi in H\{ysplit, r} do
33: if yij is dominated strictly by ysplit,j then
34: H2 ⇐ H2 + {yi};
35: yij ⇐ ysplit,j ;
36: end if
37: /* Here yi can be removed from H if yi is dominated strictly by ysplit */
38: end for
39: r2 ⇐ r;
40: r2[j − 1] ⇐ ysplit,j ;
41: H2 ⇐ H2 + {r2};
42: volume ⇐ volume+ CalcV olume(H2);
43: end if
44: end for
45: volume ⇐ volume+
|rj − ysplit,j |;
46: return volume;
Proof. It is clear that (2) ⇒ (4) ⇒ (5). The follows show (1), (2) and (3).
(1) (By Contradiction.) Assume to the contrary there is some i ∈ {1, . . . , n},∑d
j=1 δij < n − 1. If this is the case, there are at least one yk where k 6= i
such that each yij dominates ykj for all j ∈ {1, . . . , d}. It follows that yi
dominates yk, which contradicts our assumption that all the elements in
{y1, . . . , yn} are non-comparable.
(2) Given j, sort all yij where i = 1, . . . , n and label each yij a sequence
number I(i) which ranges from 0 to n − 1. Thus
i=1 I(i) =
(n − 1).
There are two cases to consider. Firstly, if all yij are different each other,
then δij = I(i). It follows that
i=1 δij =
(n − 1). Secondly, if there
are same elements within {y1j, . . . , ynj}, without loss of generality, suppose
yij = ykj and I(k) = I(i) + 1. Then δij = δkj = I(i) < I(k), it follows that∑n
i=1 δij <
(n− 1). This completes the proof.
(3) (By contradiction.) For any yi,
j=1 δij < n − 1 is excluded by (1) of
this lemma. Thus
j=1 δij > n − 1 for some yi is considered. If this is
the case, we obtain
j=1 δij > n(n − 1), contradicting (2) of this
lemma, which implies
j=1 δij =
i=1 δij ≤ n(n − 1), namely∑n
j=1 δij ≤ n(n− 1).
Lemma 2. Let ωi(k) be the amount of k in all δij where j = 1, . . . , d, namely
ωi(k) = |{j : δij = k, j = 1, . . . , d}|. Then
(1) 0 ≤ ωi(k) ≤ d for any i and k;
i=1 ωi(k) ≤ d for any k;
k=0 kωi(k) ≤
(n− 1) for any i.
Proof. By the definition of ωi(k), it is clear that all statements follows Lemma 1.
Lemma 3. Let f(n, d) be the runtime of Algorithm 1 to compute a hypervolume
with n dominative points in a d-dimensional space. Then
(1) f(n, d) + f(m, d) > f(n− 1, d) + f(m+ 1, d) where n−m > 1;
(2) f(n, d) > f(m, d) + f(n−m, d) where n > m;
(3) f(n, d) is minimal when
j=1 δij = n− 1 and |δij − δik| ≤ 1 for any j and
(4) f(n, d) is maximal when
j=1 δij =
(n − 1) for any i and ωi(k) =
any i and each k = 0, . . . , n− 1.
Proof. (1) and (2) are clear.
(3) By the process of Algorithm 1, given some i,
f(n, d) = dn logn+
f(δij , d) (1)
By (1) of Lemma 1,
j=1 δij ≥ n − 1. It is clear that for a given i, it is
necessary that
j=1 δij = n− 1 to minimize f(n, d). In addition, all the δij
must share alike, i.e. |δij − δik| ≤ 1 for any j and k. If this is not the truth,
suppose δij − δik > 1. Thus by (1) of this lemma,
f(δij , d) + f(δik, d) > f(δij − 1, d) + f(δik + 1, d) (2)
Let δij′ = δij − 1 and δik′ = δik + 1. δij′ and δik′ can be modified in the
similar way until |δij − δik| ≤ 1. This completes the proof.
(4) By (5) of Lemma 1,
j=1 δij ≤
(n− 1). It is clear that for a given i, it is
necessary that
j=1 δij =
(n− 1) to maximize f(n, d).
Hence Eqn. (1) is written as follows,
f(n, d) = dn logn+
ω(k)f(k, d) (3)
Suppose yi is the splitting reference point chosen by Algorithm 1, ωi(n−1) ≤
, or else contradicting
i=1 ωi(n− 1) ≤ d. To maximize f(n, d) in Eqn. (3),
let ωi(n − 1) =
. Similarly, we get ωi(n − 2) =
, . . ., ωi(1) =
, and so
on. It is exactly
k=0 kωi(k) =
(n− 1). This completes the proof.
4.1 Bounds of runtime at special cases
First of all, it is clear that f(1, d) = d. By (3) of Lemma 3, the algorithm performs
best when each δij shares alike for the chosen i. If d ≥ n− 1, δij ≤ 1 for any j.
f(n, d) = dn logn+ (n− 1)f(1, d) (4)
which implies f(n, d) = Ω(dn log n). If d < n−1, δij > 1 for any j. In the rough,
we get
f(n, d) = dn logn+ d · f(
, d) < dn logn+ d · f(
, d) (5)
It can be obtained from Eqn. (5) that f(n, d) = Θ(dn log n logd n) even when
f(n−1
, d) is relaxed to f(n
, d).
Fredman and Weide [11] have shown that Klee’s measure problem has a lower
bound of Ω(n logn) for arbitrary d ≥ 1. Just as Beume and Rudolph [8] have
mentioned, although it is unknown what the lower bound for calculating the
hypervolume is, it is definitely not harder than solving KMP because it is a
special case of KMP. Therefore, there is a gap between the lower bound of the
proposed algorithm and the actual lower bound of calculating the hypervolume.
In the average cases, suppose that for the given splitting reference point yi,∑d
j=1 δij =
(n− 1). Meanwhile, each δij shares alike, i.e. δij =
. Thus,
f(n, d) = dn logn+ d · f(
, d) < dn logn+ d · f(
, d) (6)
which implies the runtime of the proposed algorithm is Θ(dnlog d) at the given
cases.
4.2 Upper bound of runtime
By (2) of Lemma 3, f(n− 1) > f(n− 1− k) + f(k) for any k = 1, . . . , n−2
. And
by (4) of Lemma 3, at the worst cases, we have
f(n, d) = dn logn+ d
(f(n− 1) + f(n− 2) + . . .+ f(2) + f(1))
< dn logn+ d
(1 + n−2
)f(n− 1)
< dn logn+ d
f(n− 1)
which implies that the proposed algorithm for computing the hypervolume bounded
by n points and a reference point in d-dimensional space has a runtime ofO((d
at the worst cases.
4.3 Space complexity
Let g(n, d) be the used storage by Algorithm 1. In the proposed algorithm, every
child hypervolume is calculated one by one. Since the storage can be reused
after the former computation has been completed, g(n, d) is only related to the
maximum usage of all the computations of child hypervolumes. Hence,
g(n, d) = dn+ max
i∈{1,...,n},j∈{1,...,d}
{g(δij , d) : 0 ≤ δij ≤ n− 1} (8)
Thus the upper bound of space is as follows.
g(n, d) = dn+ g(n− 1, d) (9)
where g(1) = d. It is easy to obtain an O(dn2) space upper bound for the
proposed algorithm.
Combining the above analyses together, we obtain the time-space complexity
of the proposed algorithm.
Theorem 1. The hypervolume of a hyper-cuboid bounded by n non-comparable
points and a reference point in d-dimensional space can be computed in time
)n) using O(dn2) storage.
5 Conclusions
A fast algorithm to calculate the hypervolume indicator of Pareto approxima-
tion set is proposed. In the novel algorithm, the hyper-cuboid bounded by non-
comparable points and the reference point is partitioned into many child hyper-
cuboids along the carefully chosen splitting reference point at each dimension.
The proposed approach is very different to the technique used in other works
where the whole d-dimensional volume is calculated by computing the (d − 1)-
dimensional volume along the dimension d. Such difference results in very differ-
ent time bounds, namely O((d
)n) for our work and O(n
2 ) for the best previous
result. Neither kind of technique can exceed the other completely and each has
his strong point. Additionally, the amount of storage used by our algorithm is
only O(dn2) even no special technique is developed to reduce the space complex-
As the context has mentioned, it is very important to choose appropriate
splitting reference point for our algorithm.Well selected point can reduce number
of points in separated parts and thus cut down the whole runtime. We do not
know whether the strategy adopted in this paper is optimal or near optimal.
Further investigations should be worked on.
References
1. Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C.M., da Fonseca, V.G.: Perfor-
mance Assessment of Multiobjective Optimizers: An Analysis and Review. IEEE
Transactions on Evolutionary Computation 7(2) (2003) 117–132
2. Zitzler, E., Thiele, L.: Multiobjective Optimization Using Evolutionary Algorithms
—A Comparative Study. In Eiben, A.E., ed.: Parallel Problem Solving from Nature
V, Amsterdam, Springer-Verlag (1998) 292–301
3. Zitzler, E., Thiele, L.: Multiobjective Evolutionary Algorithms: A Comparative
Case Study and the Strength Pareto Approach. IEEE Transactions on Evolution-
ary Computation 3(4) (1999) 257–271
4. Zitzler, E., Brockhoff, D., Thiele, L.: The hypervolume indicator revisited: On the
design of pareto-compliant indicators via weighted integration. In: Proceedings
of the 4th International Conference on Evolutionary Multi-Criterion Optimization
(EMO 2007). Volume 4403., Springer-Verlag (2007) 862–876
5. While, L., Bradstreet, L., Barone, L., Hingston, P.: Heuristics for optimising the
calculation of hypervolume for multi-objective optimisation problems. In: The 2005
IEEE Congress on Evolutionary Computation. Volume 3. (2005) 2225–2232
6. While, L., Hingston, P., Barone, L., Huband, S.: A faster algorithm for calculating
hypervolume. IEEE Transactions on Evolutionary Computation 10(1) (2006) 29–
7. Fonseca, C.M., Paquete, L., nez, M.L.I.: An improved dimension-sweep algorithm
for the hypervolume indicator. In: IEEE Congress on Evolutionary Computation
(CEC 2006). (2006) 1157–1163
8. Beume, N., Rudolph, G.: Faster s-metric calculation by considering dominated
hypervolume as klee’s measure problem. In Kovalerchuk, B., ed.: Proceedings of
the Second IASTED Conference on Computational Intelligence, Anaheim, ACTA
Press (2006) 231–236
9. Edelsbrunner, H., Overmars, M.H.: Batched dynamic solutions to decomposable
searching problems. Journal of Algorithms 6(4) (1985) 515–542
10. Overmars, M.H., Yap, C.K.: New upper bounds in klee’s measure problem. SIAM
Journal on Computing 20(6) (1991) 1034–1045
11. Fredman, M.L., Weide, B.: The complexity of computing the measure of
[ai, bi].
Communications of ACM 21 (1978) 540–544
