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

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.
Type de document :
Communication dans un congrès
Foundations of Genetic Algorithms (FOGA 2009), Jan 2009, Orlando, Florida, United States. 2009, 〈10.1145/1527125.1527138〉
Domaine :

Littérature citée [27 références]

https://hal.inria.fr/inria-00430540
Contributeur : Dimo Brockhoff <>
Soumis le : dimanche 8 novembre 2009 - 18:46:41
Dernière modification le : jeudi 5 avril 2018 - 12:30:12
Document(s) archivé(s) le : jeudi 17 juin 2010 - 18:10:26

Fichier

fogaAuthorVersion.pdf
Fichiers produits par l'(les) auteur(s)

Citation

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. 2009, 〈10.1145/1527125.1527138〉. 〈inria-00430540〉

Métriques

Consultations de la notice

2846

Téléchargements de fichiers