Authors: Beume, Nicola
Rudolph, Günter
Title: Faster S-metric calculation by considering dominated hypervolume as Klee s measure problem
Language (ISO): en
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 faster determination of the S-metric value is of essential 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 run time O(n log n + n^(d/2) log n), for n points of d>= 3 dimensions. This complex algorithmis adapted to the special case of calculating the S-metric. Conceptual simplifications of the implementation are concerned that save on a factor of O(log n) and establish an upper bound of O(n log n + n^(d/2)) for the S-metric calculation, improving the previously known bound of O(n^(d-1)).
Subject Headings: evolutionary algorithms
Klee s measure problem
multi-objective optimization
performance assessment
Issue Date: 2006-07
Appears in Collections:Sonderforschungsbereich (SFB) 531

Files in This Item:
File Description SizeFormat 
21606.pdfDNB176.83 kBAdobe PDFView/Open

This item is protected by original copyright

Items in Eldorado are protected by copyright, with all rights reserved, unless otherwise indicated.