moocore.

pareto_rank#

moocore.pareto_rank(points, /, *, maximise=False)[source]#

Rank points according to Pareto-optimality (nondominated sorting).

The function pareto_rank() is meant to be used like numpy.argsort(), but it assigns indexes according to Pareto dominance, where rank 0 indicates those solutions not dominated by any other solution in the input set. Duplicated points are assigned the same rank. The resulting ranking can be used to partition points into different lists or arrays, each of them being mutually nondominated [1] (see examples below).

See also

Benchmarks of nondominated Sorting (Pareto ranking).

Parameters:

  • points (ArrayLike) – Array of numerical values, where each row gives the coordinates of a point in objective space. If the array is created by the read_datasets() function, remove the last column.

  • maximise (bool | Sequence[bool], default: False) – Whether the objectives must be maximised instead of minimised. Either a single boolean value that applies to all objectives or a list of boolean values, with one value per objective. Also accepts a 1D numpy array with value 0/1 for each objective.

Returns:

ndarray – An integer vector of the same length as the number of rows of points with values within [0, len(points) - 1], where each value gives the Pareto rank of each point (lower is better).

Notes

Given a finite set of points \(X \subset \mathbb{R}^m\) and \(x,y \in X\), let \(x \prec y\) denote that \(x\) dominates \(y\) according to Pareto optimality. Nondominated sorting partitions the set \(X\) into an ordered sequence of fronts, \(F_0, F_1, \dots, F_k\), where \(0 \leq k \leq |X|\), satisfying the following conditions:

  1. All points are allocated to a front: \(\bigcup_{i=0}^{k} F_i = X\)

  2. Each point is allocated to only one front: \(F_i \cap F_j = \emptyset,\; \forall i,j \in\{0,1,\dots,k\},\,i\neq j\)

  3. Fronts are mutually nondominated: \(\nexists x,y \in F_i, \,x \prec y,\; \forall i=0,1,\dots,k\)

  4. The first front contains points not dominated by any other point: \(\forall y \in F_0,\,\nexists x \in X,\, x\prec y\)

  5. Every point in front \(i\) is dominated by at least one point in front \(i-1\): \(\forall y \in F_i,\, \exists x \in F_{i-1},\, x\prec y,\; \forall i=1,2,\dots,k\)

The rank returned by pareto_rank() is the index \(i \in \{0,1,\dots,k\}\) of the front \(F_i\) allocated to each point. If all points are mutually nondominated, there is only one front \((k=0)\). If each front contains one point, then \(k=n=|X|\).

With \(m=2\), the code uses the best-known \(O(n \log n)\) algorithm by Jensen[2]. When \(m \geq 3\), it uses the naive algorithm that identifies one front at a time, which requires \(O(n^2\log n)\) for \(m=3\), and \(O(n^2 \log^{m-2} n)\) for \(m \geq 4\).

References

Examples

>>> x = moocore.get_dataset("input1.dat")[:, :2]
>>> ranks = moocore.pareto_rank(x)
>>> ranks
array([ 4,  8,  0, 11,  0,  3,  7,  1,  3,  0,  8,  4,  5,  4, 11,  4,  4,
        5,  7,  3,  8, 12,  8,  9,  5, 10,  6,  2,  7,  3, 10,  7,  2,  5,
        2,  7,  1,  2,  9,  0, 11,  6,  7, 10, 13,  3,  6,  3,  0,  9,  9,
        0,  2, 13,  1,  6,  7,  6,  6, 10,  4, 13,  6,  8, 12, 13,  4,  8,
        5,  1, 12, 10,  3,  8,  9,  6,  7,  6,  6,  9,  5,  2,  3,  4,  7,
        3,  8,  3,  2, 10,  1,  2, 12,  1,  2,  9,  4,  2,  5,  2],
      dtype=int32)

We can now split the original set into a list of nondominated sets ordered by Pareto rank:

>>> fronts = [x.compress((g == ranks), axis=0) for g in np.unique(ranks)]
>>> len(fronts)
14

The first element is the set of points not dominated by anything else:

>>> np.array_equal(fronts[0], moocore.filter_dominated(x))
True
On this page