比較器

Layer 2: Compose

基底

saealib.Comparator

Base class for comparator.

実装

saealib.SingleObjectiveComparator	Comparator for single-objective optimization.
saealib.WeightedSumComparator	Comparator for multi-objective optimization via weighted scalarization.
saealib.ParetoComparator	Comparator for multi-objective optimization via non-dominated sorting only.
saealib.NSGA2Comparator	Comparator for multi-objective optimization via NSGA-II style ranking.
saealib.NSGA3Comparator	Comparator for many-objective optimization via NSGA-III style ranking.
saealib.RNSGA2Comparator	Comparator for multi-objective optimization via R-NSGA-II style ranking.
saealib.SPEA2Comparator	Comparator implementing SPEA2 fitness-based ranking (Zitzler et al., 2001).
saealib.HypervolumeComparator	Comparator using front rank and exclusive HV contribution (SMS-EMOA style).
saealib.EpsilonDominanceComparator	Comparator using ε-box dominance instead of standard Pareto dominance.

支配関係

saealib.Dominator	Abstract base for dominance predicates.
saealib.ParetoDominator	Pareto dominance predicate.
saealib.EpsilonDominator	ε-dominance predicate (Laumanns et al., 2002).

非劣ソート

saealib.NonDominatedSorter

Protocol for non-dominated sorting callables.

saealib.non_dominated_sort(f, direction=None, *, dominator=None)

Non-dominated sorting via a vectorized dominance matrix.

Implements the fast-nondominated-sort front-peeling scheme of Deb et al. (2002): each individual's domination count is decremented as its dominators are peeled off, front by front. This implementation replaces the original Python double loop with a NumPy dominance matrix accumulated one objective at a time.

Time is O(MN^2), but the pairwise dominance relations are computed with a NumPy dominance matrix accumulated one objective at a time (peak memory O(N^2), no (N, N, M) tensor), replacing the original Python double loop.

NaN rows are treated as infinitely bad and placed in the last front.

パラメータ:

• f (np.ndarray) -- Objective matrix. shape: (n, n_obj)

• direction (np.ndarray or None) -- Per-objective optimization direction: +1 = maximize, -1 = minimize. None defaults to minimization for all objectives.

• dominator (Dominator or None) -- Dominance predicate to use. None defaults to ParetoDominator (standard Pareto dominance).

戻り値:

• ranks (np.ndarray shape (n,)) -- Pareto front index for each individual (0 = first/best front).

• fronts (list[list[int]]) -- fronts[i] contains the local indices of individuals in front i.

戻り値の型:

tuple[ndarray, list[list[int]]]

参照

[3]: Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182-197.

saealib.dda_non_dominated_sort(f, direction=None, *, dominator=None)

Non-dominated sorting via the Dominance-Degree Approach (DDA-ENS).

Zhou et al. (2017) introduced the dominance degree matrix; Mishra & Senwar (2020) proposed the DDA-ENS front-assignment scheme used here.

Produces identical (ranks, fronts) to non_dominated_sort() and satisfies the NonDominatedSorter Protocol. It is intended as a scalable drop-in for large N and/or large M (M > 100).

The dominance relation is computed once as an NxN boolean matrix (peak memory O(N^2), independent of M; no (N, N, M) tensor is ever allocated). Front assignment then follows the DDA-ENS scheme: solutions are ordered by ascending dominance-in-degree (number of solutions that dominate them), so that a solution's dominators are always processed before the solution itself. Each solution is assigned to the first existing front whose members do not dominate it, creating a new front when necessary.

NaN handling is identical to non_dominated_sort(): rows that contain any NaN value are excluded from the dominance computation and appended afterwards as individual sentinel fronts at rank len(real_fronts).

パラメータ:

• f (np.ndarray) -- Objective matrix. shape: (n, n_obj)

• direction (np.ndarray or None) -- Per-objective optimization direction: +1 = maximize, -1 = minimize. None defaults to minimization for all objectives.

• dominator (Dominator or None) -- Dominance predicate to use. None defaults to ParetoDominator (standard Pareto dominance).

戻り値:

• ranks (np.ndarray) -- Pareto front index for each individual (0 = first/best front). shape: (n,), dtype int.

• fronts (list[list[int]]) -- fronts[i] contains the global indices of individuals in front i.

戻り値の型:

tuple[ndarray, list[list[int]]]

saealib.crowding_distance(f_front)

Compute crowding distance for a single Pareto front (NSGA-II).

Boundary solutions (minimum and maximum per objective) are assigned infinite crowding distance; other solutions are assigned the sum, over each objective, of the normalized distance between their two neighbors once sorted by that objective.

パラメータ:

f_front (np.ndarray) -- Objective values of individuals in the front. shape: (n, n_obj)

戻り値:

Crowding distances. shape: (n,)

戻り値の型:

np.ndarray

参照

[3]: Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182-197.

saealib.crowding_distance_all_fronts(f, fronts)

Compute crowding distance for all fronts.

パラメータ:

• f (np.ndarray) -- Objective matrix. shape: (n, n_obj)

• fronts (list[list[int]]) -- Output of non_dominated_sort: fronts[i] = local indices in front i.

戻り値:

Crowding distances for all individuals. shape: (n,)

戻り値の型:

np.ndarray

saealib.spea2_fitness(f, direction=None, dominator=None)

Compute SPEA2 fitness values for a set of objective vectors.

Implements the fitness assignment procedure from Zitzler et al. (2001). Lower fitness is better (this deviates from the library's general higher-is-better score convention — do NOT pass the result directly to comparators that assume higher = better).

Fitness components:

• Strength S(i): number of solutions that i dominates.

• Raw fitness R(i): sum of the strengths of all solutions that dominate i. R(i) = 0 iff i is non-dominated.

• Density D(i) = 1 / (sigma_i^k + 2), where sigma_i^k is the Euclidean distance (in objective space) from i to its k-th nearest neighbour. The +2 keeps D in (0, 0.5].

• Fitness F(i) = R(i) + D(i).

注釈

Deviation from the paper: Zitzler et al. (2001) define k = floor(√(N + N̄)) using the combined size of the population and an external archive. This utility operates on a single set of N points, so it uses k = floor(√N) instead, clamped to [0, N-1].

パラメータ:

• f (np.ndarray) -- Objective matrix. shape: (N, n_obj).

• direction (np.ndarray or None) -- Per-objective optimization direction: +1 = maximize, -1 = minimize. None defaults to minimization for all objectives. Passed directly to the dominator (same convention as ParetoComparator).

• dominator (Dominator or None) -- Dominance predicate used to build the dominance matrix. None defaults to ParetoDominator (standard Pareto dominance).

戻り値:

SPEA2 fitness values F, shape (N,). Lower = better.

戻り値の型:

np.ndarray

参照

[4]: Zitzler, E., Laumanns, M., & Thiele, L. (2001). SPEA2: Improving the Strength Pareto Evolutionary Algorithm. TIK-Report 103, ETH Zurich, Switzerland.