Home |  ENGLISH |  Kontakt |  Impressum |  Anmelden |  KIT


Aus Aifbportal

Wechseln zu: Navigation, Suche

(This page contains COinS metadata)

Cone-based Hypervolume Indicators: Construction, Properties, and Efficient Computation

Michael Emmerich, Andre deutz, Johannes Kruisselbrink, Pradyumn Kumar Shukla

Published: 2013

Buchtitel: in EMO 2013
Nummer: in press
Reihe: LNCS
Verlag: Springer
Referierte Veröffentlichung

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 $\gamma$ is studied. These $\gamma$-cones can be efficiently constructed and have a number of favorable properties. It is shown that for $\gamma$-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 $\mu$ 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 $\mu$-distributions of this indicator. It is shown that in two dimensions and for linear Pareto fronts the optimal $\mu$-distribution has uniform gap. For general Pareto curves and $\gamma$ approaching zero, it is proven that the optimal $\mu$-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 $\gamma$-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 $\gamma$ is observed.


Effiziente Algorithmen

Multikriterielle Optimierung, Globale Optimierung, Evolutionäre Algorithmen