NonDominatedSorter#

Layer 2: Compose

Comparators in the ParetoComparator family (NSGA2Comparator/HypervolumeComparator/NSGA3Comparator/RNSGA2Comparator/EpsilonDominanceComparator) delegate sorting the population into fronts to sorter, a swappable argument. Where Dominator handles “the definition of the dominance relation between two points,” sorter is a second, independent swap axis: “how to use that dominance relation to assign individuals to fronts.”

NonDominatedSorter’s role#

NonDominatedSorter is defined not as an abstract base class but as a Protocol (structural subtyping). Any callable satisfying the signature __call__(f, direction=None, *, dominator=None) -> tuple[ranks, fronts] can be passed as sorter without inheriting from any class.

ranks is an array giving each individual’s front number (0 is best); fronts satisfies the contract that fronts[i] is the list of individual indices belonging to front i.

Built-in NonDominatedSorters#

non_dominated_sort/dda_non_dominated_sort are both functions satisfying the (ranks, fronts) contract above (with no class hierarchy of their own).

Function	Algorithm
`non_dominated_sort`	[3]’s non-dominated sorting. A front-peeling approach that strips off one front at a time
`dda_non_dominated_sort`	The Dominance-Degree Approach (Zhou et al., 2017 proposed the dominance degree matrix; Mishra & Senwar, 2020 proposed DDA-ENS’s front assignment)

non_dominated_sort’s complexity is O(MN²), but because the dominance matrix is built vectorized with NumPy, it runs fast in practice. dda_non_dominated_sort is guaranteed to return exactly the same (ranks, fronts) as non_dominated_sort, making it a drop-in alternative provided for scalability when the number of individuals N or objectives M is large (M > 100).

Both handle rows containing NaN the same way. Rows containing NaN are excluded from normal front splitting, and are appended one individual at a time as a sentinel front after the final front.

sorter and dominator are independent swap axes. Both non_dominated_sort/dda_non_dominated_sort merely call dominator.dominance_matrix() internally, and take no part in defining the dominance relation itself. If dominator is omitted, ParetoDominator is used as the default.

Auxiliary functions#

Auxiliary functions used inside the internal implementation of Pareto-family Comparators are also available standalone as public API.

crowding_distance(f_front): Computes crowding distance within a single front. Used by NSGA2Comparator. Boundary solutions (those achieving the minimum or maximum of each objective) are assigned inf.

crowding_distance_all_fronts(f, fronts): Applies crowding_distance to every front returned by non_dominated_sort.

spea2_fitness(f, direction=None, dominator=None): The fitness computation [4] used by SPEA2Comparator. Computed from three components: strength (the number of individuals dominated), raw fitness (the sum of the strengths of the individuals that dominate it), and density (the reciprocal of the \(k\)-nearest-neighbor distance).

Warning

spea2_fitness’s return value follows the convention that lower is better, the opposite of saealib’s overall “higher is better” score convention. Be careful not to pass it directly to another Comparator.

Extending NonDominatedSorter#

Because NonDominatedSorter is a Protocol, writing a single function that satisfies the (ranks, fronts) contract is enough to use as a custom implementation. There’s no need to inherit from a base class.

import numpy as np
from saealib import non_dominated_sort


def logged_non_dominated_sort(f, direction=None, *, dominator=None):
    """The minimal function satisfying the Protocol, simply adding pre-processing to the existing implementation."""
    print(f"sorting {len(f)} individuals")
    return non_dominated_sort(f, direction, dominator=dominator)

Passing it as ParetoComparator(sorter=logged_non_dominated_sort, ...) lets you swap the sorting scheme without changing an existing Comparator implementation.

NonDominatedSorter#