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

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.