Autor(en): | Beume, Nicola Fonseca, Carlos M. López-Ibáñez, Manuel Paquete, Luís Vahrenhold, Jan |
Titel: | On the complexity of computing the hypervolume indicator |
Sprache (ISO): | en |
Zusammenfassung: | The goal of multi-objective optimization is to find a set of best compromise solutions for typically conflicting objectives. Due to the complex nature of most real-life problems, only an approximation to such an optimal set can be obtained within reasonable (computing) time. To compare such approximations, and thereby the performance of multi-objective optimizers providing them, unary quality measures are usually applied. Among these, the hypervolume indicator (or S-metric) is of particular relevance due to its good properties. Moreover, this indicator has been successfully integrated into stochastic optimizers, such as evolutionary algorithms, where it serves as a guidance criterion for searching the parameter space. Recent results show that computing the hypervolume indicator can be seen as solving a specialized version of Klee s Measure Problem. In general, Klee s Measure Problem can be solved in O(n^d/2 log n) for an input instance of size n in d dimensions; as of this writing, it is unknown whether a lower bound higher than Omega(n log n) can be proven. In this article, we derive a lower bound of Omega(n log n) for the complexity of computing the hypervolume indicator in any number of dimensions d > 1 by reducing the problem to the so-called UNIFORMGAP problem. For the three dimensional case, we also present a matching upper bound of O(n log n) that is obtained by extending an algorithm for finding the maxima of a point set. |
Schlagwörter: | complexity analysis computational geometry Multi-objective optimization performance assessment |
URI: | http://hdl.handle.net/2003/26142 http://dx.doi.org/10.17877/DE290R-8718 |
Erscheinungsdatum: | 2007-12 |
Enthalten in den Sammlungen: | Sonderforschungsbereich (SFB) 531 |
Dateien zu dieser Ressource:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
23507.pdf | DNB | 159.45 kB | Adobe PDF | Öffnen/Anzeigen |
Diese Ressource ist urheberrechtlich geschützt. |
Diese Ressource ist urheberrechtlich geschützt. rightsstatements.org