Dominated hypervolume (contribution)

Given a point set x and a reference point r function hv calcultes the hypervolume indicator value [1]. In contrast, function hv_contr returns a vector of length nrow(x) where the $i$th position contains the hypervolume contribution of the $i$th point in x.

hv(x, r = NULL, offset = 1, ...)

hv_contr(x, r = NULL, offset = 1)

Arguments

x	[`matrix`] Matrix of points (column-wise).
r	[`numeric` \| `NULL`] Reference point. Set to the maximum in each dimension by default if not provided.
offset	[`numeric(1)`] Offset to be added to each component of the reference point only in the case where no reference is provided and one is calculated automatically. Default is 1.
...	[any] Not used at the moment.

Value

Dominated hypervolume in the case of hv or a vector of the dominated hypervolume contributions for each point of x in the case of hv_contr.

Details

The hypervolume (HV) indicator [1, 2] is arguebly one of the most often used performance indicators likely due to its straight-forward definition. Given a set of points $X = \{x_1, \ldots, x_{|X|}\}$ and an anti-optimal reference point $r \in R^m$ the HV-indicator, also called the S-metric, is defined as $$ HV(X, r) = \lambda_m\left(\bigcup_{x \in X} [x \preceq x' \preceq r]\right). $$ Here, $\lambda_m$ is the $m$-dimensional Lebesgue measure. Informally, the hypervolume indicator is the space/volume enclosed by the point set and the anti-optimal (i.e., it is dominated by every point $x \in X$) reference point. It is known to be strictly monotonic. I.e., if the point set $X$ strictly dominates another point set $Y$, then $HV(X,r) > HV(Y, r)$ holds.

Function hv computes the dominated hypervolume of a set of points given a reference set whereby hv_contr computes the hypervolume contribution of each point which is a key ingredient of the S-Metric Selection EMOA (SMS-EMOA) [3, 4].

If no reference point is given, the nadir point of the set x is determined and a positive offset with default 1 is added. This is to ensure that the reference point is dominated by all of the points in the reference set (anti-optimality property).

Note

Keep in mind that this function assumes all objectives to be minimized. In case at least one objective is to be maximized, the data needs to be transformed accordingly in advance.

References

[1] E. Zitzler and L. Thiele. Multiobjective Optimization Using Evolutionary Algorithms - A Comparative Case Study. In Conference on Parallel Problem Solving from Nature (PPSN V), volume 1498 of LNCS, pages 292–301, 1998.

[2] Knowles, J. D., Thiele, L. and Zitzler, E. A tutorial on the performance assessment of stochastive multiobjective optimizers. TIK-Report No. 214, Computer Engineering and Networks Laboratory, ETH Zurich, February 2006 (Revised version. First version, January 2005). doi: 10.3929/ethz-b-000023822.

[3] M. Emmerich, N. Beume, and B. Naujoks. An EMO Algorithm Using the Hypervolume Measure as Selection Criterion. In Conference on Evolutionary Multi-Criterion Optimization (EMO 2005), volume 3410 of LNCS, pages 62–76. Springer Berlin, 2005.