N. Beume and G. Rudolph (Germany)
Multi-objective optimization, evolutionary algorithms, per formance assessment, efficient algorithms, S-metric, 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
