Authors: Beume, Nicola
Fonseca, Carlos M.
López-Ibáñez, Manuel
Paquete, Luís
Vahrenhold, Jan
Title: On the complexity of computing the hypervolume indicator
Language (ISO): en
Abstract: 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.
Subject Headings: complexity analysis
computational geometry
Multi-objective optimization
performance assessment
Issue Date: 2007-12
Appears in Collections:Sonderforschungsbereich (SFB) 531

Files in This Item:
File Description SizeFormat 
23507.pdfDNB159.45 kBAdobe PDFView/Open

This item is protected by original copyright

All resources in the repository are protected by copyright.