Spread metrics

Γ and Δ measure how well a front of $N$ points spreads between extreme values that are the same for all solvers [2] (Section 5.3.3). The extremes come from the reference front R, the non-dominated points of all solvers: for each objective $j$, $f_{0,j} = \min_{y \in R} y_j$ (ideal) and $f_{N+1,j} = \max_{y \in R} y_j$ (nadir). Let $f_{1,j} \le \dots \le f_{N,j}$ be the sorted values of objective $j$ in the front and $\delta_{i,j} = f_{i+1,j} - f_{i,j}$, $i = 0, \dots, N$.

Γ-spread

The largest gap, eq. (5.1) of [2]:

\[\Gamma = \max_{j \in \{1,\dots,m\}} \ \max_{i \in \{0,\dots,N\}} \delta_{i,j}.\]

For two objectives this is the largest distance, in the infinity norm, between consecutive points, counting the extremes.

Δ-spread

The extension to $m$ objectives, eq. (5.2) of [2], of the Δ of [3]:

\[\Delta = \max_{j \in \{1,\dots,m\}} \frac{\delta_{0,j} + \delta_{N,j} + \sum_{i=1}^{N-1} |\delta_{i,j} - \bar\delta_j|} {\delta_{0,j} + \delta_{N,j} + (N-1)\,\bar\delta_j}, \qquad \bar\delta_j = \frac{1}{N-1}\sum_{i=1}^{N-1} \delta_{i,j}.\]

The original Δ of [3] is defined for two objectives with Euclidean distances between consecutive points and extremes of the true front; [2] uses per-objective differences and extremes from the merged fronts, which extends it to any $m$.

Both are lower-is-better. Δ is zero for equally spaced points that reach both extremes. See Conventions for single points, degenerate objectives and points outside the extremes.

julia> using MultiObjectiveMetrics

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

julia> A = [[0.0, 1.0], [0.25, 0.75], [1.0, 0.0]];

julia> gamma_spread(A, R), delta_spread(A, R)
(0.75, 0.5)

MultiObjectiveMetrics.gamma_spread — Function

gamma_spread(A, R; tol = Tolerance())
gamma_spread(A, ideal, nadir; tol = Tolerance())

Γ-spread of the front A [2] (eq. 5.1): the largest gap between consecutive values of any objective, with the extreme values ideal[j] and nadir[j] added at both ends,

Γ = max_j max_{i = 0,…,N} (f_{i+1,j} - f_{i,j}),

where f_{1,j} ≤ … ≤ f_{N,j} are the sorted values of objective j in A, f_{0,j} = ideal[j] and f_{N+1,j} = nadir[j]. With a reference front R, ideal = ideal_point(R) and nadir = nadir_point(R). Lower is better.

Conventions (see Conventions):

values of A outside [ideal[j], nadir[j]] are clipped to that interval;
an objective with ideal[j] ≈ nadir[j] (under tol) is skipped;
NaN if A is empty or every objective is skipped; Inf if A has one point.

A is used as given: pass the non-dominated front of the solver. Repeated points are not removed.

Examples

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

julia> gamma_spread(R, R)
0.5

julia> gamma_spread([[0.0, 1.0], [1.0, 0.0]], R)
1.0

source

MultiObjectiveMetrics.delta_spread — Function

delta_spread(A, R; tol = Tolerance())
delta_spread(A, ideal, nadir; tol = Tolerance())

Δ-spread of the front A [2] (eq. 5.2), the extension to m objectives of the Δ of [3]:

Δ = max_j (δ_{0,j} + δ_{N,j} + Σ_{i=1}^{N-1} |δ_{i,j} - δ̄_j|) / (δ_{0,j} + δ_{N,j} + (N - 1) δ̄_j),

with δ_{i,j} = f_{i+1,j} - f_{i,j} as in gamma_spread and δ̄_j the mean of δ_{i,j}, i = 1, …, N-1. Lower is better; Δ = 0 for equally spaced points that reach both extremes.

Conventions (see Conventions): the same as gamma_spread. An objective in which all points of A coincide gives Δ_j = 1.

Examples

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

julia> delta_spread(R, R)
0.0

julia> delta_spread([[0.0, 1.0], [0.25, 0.75], [1.0, 0.0]], R)
0.5

source