Journal
EVOLUTIONARY COMPUTATION
Volume 17, Issue 4, Pages 477-492Publisher
MIT PRESS
DOI: 10.1162/evco.2009.17.4.17402
Keywords
Multi-objective optimization; evolutionary algorithms; performance assessment; hypervolume indicator; S-metric; computational geometry
Funding
- Deutsche Forschungsgemeinschaft (DFG) [SFB 531]
Ask authors/readers for more resources
The dominated hypervolume (or S-metric) is a commonly accepted duality 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 + n(d/2) logn), for it 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(n(d/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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available