hypervolume: Hypervolume metric

In moocore: Core Mathematical Functions for Multi-Objective Optimization

Hypervolume metric

Description

Compute the hypervolume metric with respect to a given reference point assuming minimization of all objectives.

Usage

hypervolume(x, reference, maximise = FALSE)

Arguments

x	matrix()|data.frame() Matrix or data frame of numerical values, where each row gives the coordinates of a point.
reference	numeric() Reference point as a vector of numerical values.
maximise	logical() Whether the objectives must be maximised instead of minimised. Either a single logical value that applies to all objectives or a vector of logical values, with one value per objective.

Details

The hypervolume of a set of multidimensional points A \subset \mathbb{R}^m, where m is the dimension of the points, with respect to a reference point \vec{r} \in \mathbb{R}^m is the volume of the region dominated by the set and bounded by the reference point \citepZitThi1998ppsn. Points in A that do not strictly dominate \vec{r} do not contribute to the hypervolume value, thus, ideally, the reference point must be strictly dominated by all points in the true Pareto front.

More precisely, the hypervolume is the Lebesgue measure of the union of axis-aligned hyperrectangles (orthotopes), where each hyperrectangle is defined by one point from \vec{a} \in A and the reference point. The union of axis-aligned hyperrectangles is also called an orthogonal polytope.

The hypervolume is compatible with Pareto-optimality \citepKnoCor2002cec,ZitThiLauFon2003:tec, that is, \nexists A,B \subset \mathbb{R}^m, such that A is better than B according to Pareto-optimality and \text{hyp}(A) \leq \text{hyp}(B). In other words, if the hypervolume of a set is larger than the hypervolume of another, then we know for sure than the latter set cannot be better than the former in terms of Pareto-optimality. The hypervolume is also the only unary metric known that is complete according to Pareto-optimality \citepZitThiLauFon2003:tec, that is, if A is better than B according to Pareto-optimality, then \text{hyp}(A) > \text{hyp}(B).

Like most measures of unions of high-dimensional geometric objects, computing the hypervolume is #P-hard \citepBriFri2010approx, which means that the best possible algorithm takes an exponential time on the number of objectives or points, in the worst-case.

For 2D and 3D, the algorithms used \citepFonPaqLop06:hypervolume,BeuFonLopPaqVah09:tec have O(n \log n) complexity, where n is the number of input points. The 3D case uses the \text{HV3D}^{+} algorithm \citepGueFon2017hv4d, which has the sample complexity as the HV3D algorithm \citepFonPaqLop06:hypervolume,BeuFonLopPaqVah09:tec, but it is faster in practice.

For 4D, the algorithm used is \text{HV4D}^{+} \citepGueFon2017hv4d, which has O(n^2) complexity. Compared to the original implementation, this implementation correctly handles weakly dominated points and has been further optimized for speed.

For 5D or higher and up to 12 points, the implementation uses the inclusion-exclusion algorithm \citepWuAza2001metrics, which has O(m 2^{n}) time and O(n\cdot m) space complexity, but it is very fast for such small sets. For larger number of points, it uses a recursive algorithm \citepFonPaqLop06:hypervolume that computes 4D contributions \citepGueFon2017hv4d as the base case, resulting in a O(n^{m-2}) time complexity and O(n) space complexity in the worst-case. Experimental results show that the pruning techniques used may reduce the time complexity even further. The original proposal \citepFonPaqLop06:hypervolume had the HV3D algorithm as the base case, giving a time complexity of O(n^{m-2} \log n). Andreia P. Guerreiro enhanced the numerical stability of the algorithm by avoiding floating-point comparisons of partial hypervolumes.

The hypervolume of 1D inputs is defined as max(0, ref - min(x)).

Value

numeric(1) A single numerical value.

Author(s)

Manuel López-Ibáñez

References

\insertAllCited

Examples

dat = matrix(c(5, 5, 4, 6, 2, 7, 7, 4), ncol=2, byrow=TRUE)
hypervolume(dat, ref=c(10, 10))
hypervolume(dat, ref=0, maximise=TRUE)

data(SPEA2minstoptimeRichmond)
# The second objective must be maximized
# We calculate the hypervolume of the union of all sets.
hypervolume(SPEA2minstoptimeRichmond[, 1:2], reference = c(250, 0),
            maximise = c(FALSE, TRUE))

moocore documentation built on July 12, 2026, 5:06 p.m.