Compute the hypervolume metric with respect to a given reference point assuming minimization of all objectives.
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}^d\) with respect to a reference point \(\vec{r} \in \mathbb{R}^d\) is the volume of the region dominated by the set and bounded by the reference point (Zitzler and Thiele 1998) . 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 (Knowles and Corne 2002; Zitzler et al. 2003) , that is, \(\nexists A,B \subset \mathbb{R}^m\), 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 the hypervolume of the latter. Conversely, 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.
For 2D and 3D, the algorithms used (Fonseca et al. 2006; Beume et al. 2009) have \(O(n \log n)\) complexity, where \(n\) is the number of input points. The 3D case uses the \(\text{HV3D}^{+}\) algorithm (Guerreiro and Fonseca 2018) , which has the sample complexity as the HV3D algorithm (Fonseca et al. 2006; Beume et al. 2009) , but it is faster in practice.
For 4D, the algorithm used is \(\text{HV4D}^{+}\) (Guerreiro and Fonseca 2018) , 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, it uses a recursive algorithm (Fonseca et al. 2006) with \(\text{HV4D}^{+}\) as the base case, resulting in a \(O(n^{d-2})\) time complexity and \(O(n)\) space complexity in the worst-case, where \(d\) is the dimension of the points. Experimental results show that the pruning techniques used may reduce the time complexity even further. The original proposal (Fonseca et al. 2006) had the HV3D algorithm as the base case, giving a time complexity of \(O(n^{d-2} \log n)\). Andreia P. Guerreiro enhanced the numerical stability of the algorithm by avoiding floating-point comparisons of partial hypervolumes.
References
Nicola Beume, Carlos
M. Fonseca, Manuel López-Ibáñez, Luís Paquete, Jan Vahrenhold (2009).
“On the complexity of computing the hypervolume indicator.”
IEEE Transactions on Evolutionary Computation, 13(5), 1075–1082.
doi:10.1109/TEVC.2009.2015575
.
Carlos
M. Fonseca, Luís Paquete, Manuel López-Ibáñez (2006).
“An improved dimension-sweep algorithm for the hypervolume indicator.”
In Proceedings of the 2006 Congress on Evolutionary Computation (CEC 2006), 1157–1163.
doi:10.1109/CEC.2006.1688440
.
Andreia
P. Guerreiro, Carlos
M. Fonseca (2018).
“Computing and Updating Hypervolume Contributions in Up to Four Dimensions.”
IEEE Transactions on Evolutionary Computation, 22(3), 449–463.
doi:10.1109/tevc.2017.2729550
.
Joshua
D. Knowles, David Corne (2002).
“On Metrics for Comparing Non-Dominated Sets.”
In Proceedings of the 2002 Congress on Evolutionary Computation (CEC'02), 711–716.
Eckart Zitzler, Lothar Thiele (1998).
“Multiobjective Optimization Using Evolutionary Algorithms - A Comparative Case Study.”
In Agoston
E. Eiben, Thomas Bäck, Marc Schoenauer, Hans-Paul Schwefel (eds.), Parallel Problem Solving from Nature – PPSN V, volume 1498 of Lecture Notes in Computer Science, 292–301.
Springer, Heidelberg, Germany.
doi:10.1007/BFb0056872
.
Eckart Zitzler, Lothar Thiele, Marco Laumanns, Carlos
M. Fonseca, Viviane Grunert da Fonseca (2003).
“Performance Assessment of Multiobjective Optimizers: an Analysis and Review.”
IEEE Transactions on Evolutionary Computation, 7(2), 117–132.
doi:10.1109/TEVC.2003.810758
.