Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

Theory of the Hypervolume Indicator: Optimal μ-Distributions and the Choice of the Reference Point

Anne Auger 1 Johannes Bader 2 Dimo Brockhoff 1 Eckart Zitzler 2 
1 TAO - Machine Learning and Optimisation
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : The hypervolume indicator is a set measure used in evolutionary multiobjective optimization to evaluate the performance of search algorithms and to guide the search. Multiobjective evolutionary algorithms using the hypervolume indicator transform multiobjective problems into single objective ones by searching for a finite set of solutions maximizing the corresponding hypervolume indicator. In this paper, we theoretically investigate how those optimal $\mu$-distributions---finite sets of $\mu$ solutions maximizing the hypervolume indicator---are spread over the Pareto front of biobjective problems. This problem is of high importance for practical applications as these sets characterize the preferences that the hypervolume indicator encodes, i.e., which types of Pareto set approximations are favored. In particular, we tackle the question whether the hypervolume indicator is biased towards certain regions. For linear fronts we prove that the distribution is uniform with constant distance between two consecutive points. For general fronts where it is presumably impossible to characterize exactly the distribution, we derive a limit result when the number of points grows to infinity proving that the empirical density of points converges to a density proportional to the square root of the negative of the derivative of the front. Our analyses show that it is not the shape of the Pareto front but only its slope that determines how the points that maximize the hypervolume indicator are distributed. Experimental results illustrate that the limit density is a good approximation of the empirical density for small $\mu$. Furthermore, we analyze the issue of where to place the reference point of the indicator such that the extremes of the front can be found if the hypervolume indicator is optimized. We derive an explicit lower bound (possibly infinite) ensuring the presence of the extremes in the optimal distribution. This result contradicts the common belief that the reference point has to be chosen close to the nadir point: for certain types of fronts, we show that no finite reference point allows to have the extremes in the optimal $\mu$-distribution.
Document type :
Conference papers
Complete list of metadata

Cited literature [27 references]  Display  Hide  Download
Contributor : Dimo Brockhoff Connect in order to contact the contributor
Submitted on : Sunday, November 8, 2009 - 6:46:41 PM
Last modification on : Sunday, June 26, 2022 - 11:50:49 AM
Long-term archiving on: : Thursday, June 17, 2010 - 6:10:26 PM


Files produced by the author(s)




Anne Auger, Johannes Bader, Dimo Brockhoff, Eckart Zitzler. Theory of the Hypervolume Indicator: Optimal μ-Distributions and the Choice of the Reference Point. Foundations of Genetic Algorithms (FOGA 2009), Jan 2009, Orlando, Florida, United States. ⟨10.1145/1527125.1527138⟩. ⟨inria-00430540⟩



Record views


Files downloads