moocore.pareto_rank

moocore.pareto_rank(data, /, *, maximise=False)

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. Duplicated points are kept on the same front. The resulting ranking can be used to partition points into different lists or arrays, each of them being mutually nondominated [1].

With 2 dimensions, the code uses the \(O(n \log n)\) algorithm by Jensen[2].

Parameters:

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

• maximise (bool | list[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 data, where each value gives the Pareto rank of each point (lower is better).

References

[1]

Kalyanmoy Deb, A. Pratap, S. Agarwal, and T. Meyarivan. A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2):182–197, 2002. doi:10.1109/4235.996017.

[2]

M. T. Jensen. Reducing the run-time complexity of multiobjective EAs: the NSGA-II and other algorithms. IEEE Transactions on Evolutionary Computation, 7(5):503–515, 2003.

Examples

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

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

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

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

>>> np.array_equal(paretos[0], moocore.filter_dominated(x))
True