Compute the hypervolume metric with respect to a given reference point assuming minimization of all objectives. For 2D and 3D, the algorithm used FonPaqLop06:hypervolume,BeuFonLopPaqVah09:tec has \(O(n \log n)\) complexity. For 4D or higher, it uses a recursive algorithm that has the 3D algorithm as a base case algorithm FonPaqLop06:hypervolume, which has \(O(n^{d-2} \log n)\) time and linear space complexity in the worst-case, but experimental results show that the pruning techniques used may reduce the time complexity even further. Andreia P. Guerreiro improved the integration of the 3D case with the recursive algorithm, which leads to significant reduction of computation time. She has also enhanced the numerical stability of the algorithm by avoiding floating-point comparisons of partial hypervolumes.
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\) with respect to a reference point \(\vec{r}\) is the volume of the region dominated by the set and bounded by the reference point ZitThi1998ppsn. Points in \(A\) that do not strictly dominated \(\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 integral 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 KnoCor2002cec,ZitThiLauFon2003:tec, that is, \(\not\exists A,B \subset \mathbb{R}^d\), such that \(A\) is better than \(B\) in terms of Pareto-optimality and \(\text{hyp}(A) \leq \text{hyp}(B)\). In other words, if a set is better than another in terms of Pareto-optimality, the hypervolume of the former must be strictly larger than one of the latter. Conversely, if the hypervolume of one set is larger than one of another, then we know for sure than the latter set cannot be better than the former in terms of Pareto-optimality.