Faster S-Metric Calculation by Considering Dominated Hypervolume as Klee's Measure Problem

N. Beume and G. Rudolph (Germany)


Multiobjective optimization, evolutionary algorithms, per formance assessment, efficient algorithms, Smetric, hy pervolume, Klee’s measure problem.


The dominated hypervolume (or S-metric) is a commonly accepted quality measure for comparing approximations of Pareto fronts generated by multi-objective optimizers. Since optimizers exist, namely evolutionary algorithms, that use the S-metric internally several times per iteration, a faster determination of the S-metric value is of essen tial importance. This paper describes how to consider the S-metric as a special case of a more general geometrical problem called Klee’s measure problem (KMP). For KMP, an algorithm exists with runtime O(n log n + nd/2 log n), for n points of d ≥ 3 dimensions. This complex algorithm is adapted to the special case of calculating the S-metric. Conceptual simplifications of the implementation are con cerned that save on a factor of O(logn) and establish an upper bound of O(n log n+nd/2 ) for the S-metric calcula tion, improving the previously known bound of O(nd−1 ).

Important Links:

Go Back