Cone-based hypervolume indicators: Construction, properties, and efficient computation

Michael Emmerich, André Deutz, Johannes Kruisselbrink, Pradyumn Kumar Shukla

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


In this paper we discuss cone-based hypervolume indicators (CHI) that generalize the classical hypervolume indicator (HI) in Pareto optimization. A family of polyhedral cones with scalable opening angle γ is studied. These γ-cones can be efficiently constructed and have a number of favorable properties. It is shown that for γ-cones dominance can be checked efficiently and the CHI computation can be reduced to the computation of the HI in linear time with respect to the number of points μ in an approximation set. Besides, individual contributions to these can be computed using a similar transformation to the case of Pareto dominance cones. Furthermore, we present first results on theoretical properties of optimal μ-distributions of this indicator. It is shown that in two dimensions and for linear Pareto fronts the optimal μ-distribution has uniform gap. For general Pareto curves and γ approaching zero, it is proven that the optimal μ-distribution becomes equidistant in the Manhattan distance. An important implication of this theoretical result is that by replacing the classical hypervolume indicator by CHI with γ-cones in hypervolume-based algorithms, such as the SMS-EMOA, the distribution can be shifted from a distribution that is focussed more on the knee point region to a distribution that is uniformly distributed. This is illustrated by numerical examples in 2-D. Moreover, in 3-D a similar dependency on γ is observed.

Original languageEnglish
Title of host publicationEvolutionary Multi-Criterion Optimization - 7th International Conference, EMO 2013, Proceedings
Number of pages17
Publication statusPublished - 2013
Event7th International Conference on Evolutionary Multi-Criterion Optimization, EMO 2013 - Sheffield, United Kingdom
Duration: 19 Mar 201322 Mar 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7811 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference7th International Conference on Evolutionary Multi-Criterion Optimization, EMO 2013
Country/TerritoryUnited Kingdom


  • Complexity
  • Cone-based Hypervolume Indicator
  • Cone-orders
  • Hypervolume Indicator
  • Optimal μ-distribution


Dive into the research topics of 'Cone-based hypervolume indicators: Construction, properties, and efficient computation'. Together they form a unique fingerprint.

Cite this