Compute the hypervolume metric with respect to a given reference point assuming minimization of all objectives. For 2D and 3D, the algorithm used (Fonseca et al. 2006; Beume et al. 2009) has \(O(n \log n)\) complexity, where \(n\) is the number of input points. For 4D or higher, it uses a recursive algorithm that has the 3D algorithm as a base case algorithm (Fonseca et al. 2006) , which has \(O(n^{m-2} \log n)\) time and linear space complexity in the worst-case, where \(m\) is the dimension of the points, 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 \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 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 (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.
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
.
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
.