Hypervolume

The hypervolume of a set $F$ with respect to a reference point $r$ is the volume of the region dominated by $F$ and bounded by $r$ [4], [5] (Def. 8), [7]:

\[\mathrm{HV}(F; r) = \lambda_m\Bigl(\bigcup_{y \in F} [y_1, r_1] \times \dots \times [y_m, r_m]\Bigr).\]

Higher is better. hypervolume computes it exactly:

$m = 2$: sort by the first objective and add one rectangle per point;
$m = 3$: the dimension sweep of Paquete et al. described in [6] (Section III-A), sweeping the third objective and keeping the non-dominated projections on the first two;
$m \ge 4$: the slicing recursion of [6] (Algorithm 1) along the last objective, down to the three-dimensional case.

The value depends strongly on $r$, so the reference point is always an argument [9].

Normalized hypervolume

normalized_hypervolume follows the convention of [8] (Section 7.2): map each objective by $\tilde y_j = (y_j - \mathrm{ideal}_j)/(\mathrm{nadir}_j - \mathrm{ideal}_j)$ with ideal and nadir of the reference front, take $r = (1.1, \dots, 1.1)$, and divide by $1.1^m$ so that the value lies in $[0, 1]$:

\[\mathrm{HV}_{\mathrm{norm}}(F) = \frac{\mathrm{HV}(\tilde F; (1.1, \dots, 1.1))}{1.1^m}.\]

Normalizing and placing the reference point slightly beyond the nadir is common practice, but no numerical rule is standard: [9] shows that $1.1$ is not always appropriate and proposes a rule that depends on the number of points and objectives. The offset $1.1$ and the division by $1.1^m$ are therefore a convention, adjustable through offset.

julia> using MultiObjectiveMetrics

julia> hypervolume([[1.0, 2.0], [2.0, 1.0]], [3.0, 3.0])
3.0

julia> R = [[0.0, 1.0], [1.0, 0.0]];

julia> normalized_hypervolume(R, R) ≈ 0.21 / 1.21
true

MultiObjectiveMetrics.hypervolume — Function

hypervolume(F, reference)

Exact hypervolume of the point set F with respect to reference [4], [5]: the Lebesgue measure of the region dominated by F and bounded by reference,

HV(F; r) = λ_m(∪_{y ∈ F} [y, r]).

Higher is better. The reference point is always explicit: there is no default, because the value depends strongly on it [9]. Points that are not strictly better than reference in every objective contribute nothing; dominated and repeated points do not change the value. An empty set, or a set with no contributing point, has hypervolume zero.

Algorithms: sorting for m = 2; the dimension sweep of Paquete et al. described in [6] (Section III-A) for m = 3, in O(n²) worst-case time with a sorted vector instead of a balanced tree; and the slicing recursion of [6] (Algorithm 1), down to the three-dimensional case, for m ≥ 4.

See normalized_hypervolume for the normalized variant.

Examples

julia> hypervolume([[1.0, 2.0], [2.0, 1.0]], [3.0, 3.0])
3.0

julia> hypervolume([[1.0, 1.0, 1.0]], [2.0, 3.0, 4.0])
6.0

source

MultiObjectiveMetrics.normalize_points — Function

normalize_points(F, ideal, nadir) -> Vector{Vector}

Map every point f of F to (f - ideal) ./ max.(nadir - ideal, eps), so that ideal goes to the origin and nadir to the vector of ones. The eps of the floating-point type guards objectives with ideal[j] == nadir[j].

Examples

julia> normalize_points([[1.0, 4.0], [3.0, 2.0]], [1.0, 2.0], [3.0, 4.0])
2-element Vector{Vector{Float64}}:
 [0.0, 1.0]
 [1.0, 0.0]

source

MultiObjectiveMetrics.normalized_hypervolume — Function

normalized_hypervolume(F, R; offset = 1.1, tol = Tolerance())
normalized_hypervolume(F, ideal, nadir; offset = 1.1, tol = Tolerance())

Hypervolume of F after normalize_points, with reference point offset * ones(m), divided by offset^m:

HV_norm(F) = HV(normalize(F); (offset, …, offset)) / offset^m.

With a reference front R, ideal = ideal_point(R) and nadir = nadir_point(R). The value lies in [0, 1]; higher is better, and for performance profiles use 1 / HV_norm.

This is the convention of [8] (Section 7.2), not a definition from the hypervolume literature: normalizing by ideal and nadir and taking a reference point slightly worse than the nadir is common practice, but offset = 1.1 and the division by offset^m are the authors' choices; see [9] for the effect of the reference point. Use hypervolume for any other reference point.

Returns NaN when F is empty or when ideal ≈ nadir in every objective (under tol).

Examples

julia> R = [[0.0, 1.0], [1.0, 0.0]];

julia> normalized_hypervolume(R, R) ≈ 0.21 / 1.21
true

source