S-Metric Calculation by Considering Dominated Hypervolume as Klee's Measure Problem
- 1 December 2009
- journal article
- research article
- Published by MIT Press in Evolutionary Computation
- Vol. 17 (4), 477-492
- https://doi.org/10.1162/evco.2009.17.4.17402
Abstract
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.Keywords
This publication has 10 references indexed in Scilit:
- On the Complexity of Computing the Hypervolume IndicatorIEEE Transactions on Evolutionary Computation, 2009
- A Fast Incremental Hypervolume AlgorithmIEEE Transactions on Evolutionary Computation, 2008
- SMS-EMOA: Multiobjective selection based on dominated hypervolumeEuropean Journal of Operational Research, 2007
- Covariance Matrix Adaptation for Multi-objective OptimizationEvolutionary Computation, 2007
- A faster algorithm for calculating hypervolumeIEEE Transactions on Evolutionary Computation, 2006
- Performance assessment of multiobjective optimizers: an analysis and reviewIEEE Transactions on Evolutionary Computation, 2003
- New Upper Bounds in Klee’s Measure ProblemSIAM Journal on Computing, 1991
- Batched dynamic solutions to decomposable searching problemsJournal of Algorithms, 1985
- On the complexity of computing the measure of ∪[a i ,b i ]Communications of the ACM, 1978
- Can the Measure of ∪ n 1 [ a i , b i ] be Computed in Less Than O(n logn) Steps?The American Mathematical Monthly, 1977