Approximating the Hypervolume Indicator using Fast Quasi-Random Low-Discrepancy Sequences: Supplementary Materials

The hypervolume indicator measures the volume of the objective space weakly dominated by a set of solutions in multi-objective optimization problems. It is one the most popular unary quality metrics for comparing multi-objective optimizers. The computation of the hypervolume requires exponential time on the number of objectives, hence, it quickly becomes impractical for large number of points in more than 5 dimensions. To overcome this limitation, several methods for approximating the hypervolume have been proposed in the literature. A recent proposal uses polar coordinates to transform the hypervolume into an integral over the hypersphere that is approximated via (quasi-)Monte Carlo sampling. In this paper, we replace two key components of this proposal with: (1) $R_\phi$, a fast multi-dimensional generalization of the Kronecker sequence that generates sampling points in the hypercube, and (2) a simple and efficient mapping from the hypercube to the positive orthant of the hypersphere. We compare these components with other possible alternatives, including the well-known Sobol and Halton low-discrepancy sequences. Our experimental results show that combination of these two components, which we call $R_\phi$-FWE+, typically achieves lower approximation error at equal or lower computation cost.