Inproceedings3317
Cone-based Hypervolume Indicators: Construction, Properties, and Efficient Computation
Cone-based Hypervolume Indicators: Construction, Properties, and Efficient Computation
Published: 2013
Buchtitel: in EMO 2013
Nummer: in press„in press“ ist keine Zahl.
Reihe: LNCS
Verlag: Springer
Referierte Veröffentlichung
BibTeX
Kurzfassung
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.
Evolutionäre Algorithmen, Multikriterielle Optimierung, Globale Optimierung