Quarterly (spring, summer, fall, winter)
176 pp. per issue
7 x 10
2014 Impact factor:

Evolutionary Computation

Winter 2009, Vol. 17, No. 4, Pages 477-492
(doi: 10.1162/evco.2009.17.4.17402)
© 2009 by the Massachusetts Institute of Technology
S-Metric Calculation by Considering Dominated Hypervolume as Klee's Measure Problem
Article PDF (636.55 KB)

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 fast determination of the S-metric value is of essential importance. This work describes how to consider the S-metric as a special case of a more general geometric 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 realize the algorithm without complex data structures and establish an upper bound of O(nd/2 log n) for the S-metric calculation for d ≥ 3. The performance of the new algorithm is studied in comparison to another state of the art algorithm on a set of academic test functions.