Module nsga3 

NSGA-III — the reference-point-based many-objective genetic algorithm.

Nsga2 keeps its population spread along the Pareto front with crowding distance, which works well for two or three objectives and degrades beyond: in many dimensions almost every solution is mutually non-dominated, and crowding distance stops telling a well-spread population from a clustered one. NSGA-III (Deb & Jain 2014, “An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I”, IEEE TEC 18(4)) replaces crowding with reference directions: a structured set of points on the unit simplex, and survival that keeps the population close to as many of their rays as possible. The implementation follows the paper in the form Optuna’s NSGAIIISampler (optuna/samplers/_nsgaiii/) implements it.

The algorithm, precisely

Breeding is NSGA-II’s, reused verbatim from nsga2::variation: two parents by binary tournament, SBX crossover and polynomial mutation for numeric genes, uniform crossover and re-choice for categorical ones. The tournament compares rank only — every crowding value is 0, so a tie goes to the second draw — which is the dominance-only tournament Optuna’s NSGA-III inherits from its NSGA-II child generation; diversity is survival’s job here, not selection’s.

Survival, once a whole generation of children has been evaluated:

1. Pool parents and children and non-dominated-sort them (fast_non_dominated_sort, constraint-aware). Accept whole fronts while they fit in population_size.
2. If a front does not fit, normalize the accepted members plus that front: translate by the ideal point, find each axis’s extreme point by an achievement scalarizing function, and rescale by the intercepts of the hyperplane through them.
3. Associate each member with the closest reference line (perpendicular distance to the ray through a reference point).
4. Niche-preserving selection fills the remaining places from the splitting front: repeatedly take the least-crowded reference point that still has a candidate, and admit its closest candidate if no accepted member sits on it yet, a random one otherwise.

The reference points default to the Das–Dennis lattice with DEFAULT_DIVIDING_PARAMETER divisions per axis (Optuna’s dividing_parameter=3), built for the study’s objective count — C(M+p−1, p) points, reduced if it would exceed MAX_REFERENCE_POINTS (never below one division: the M axis directions). A caller may supply its own with with_reference_points.

Constraints, state and determinism

Exactly as for Nsga2: constraint values recorded with TrialCtx::record_constraints rank a feasible solution above every infeasible one (constrained_dominates); the population, part-filled offspring buffer and in-flight jobs ride the sampler-state seam and are validated on restore; a child whose objectives or constraints are not all finite, or whose evaluated point is not the bred point, is not admitted.

Every draw comes from a ChaCha8Rng: breeding is seeded from the per-trial sampler_seed, and survival’s niche draws from a seed the sampler captures (derived from the first trial it breeds) and persists, keyed per generation. A single worker with a fixed seed is fully reproducible and a reopen continues exactly; a parallel study is replayable, not pre-determined, like NSGA-II.

Structs

Nsga3

The reference-point-based many-objective genetic algorithm (NSGA-III) as a Sampler.

Constants

DEFAULT_DIVIDING_PARAMETER

The default number of divisions per objective axis of the Das–Dennis reference lattice — Optuna’s dividing_parameter=3.

MAX_REFERENCE_POINTS

The most reference points survival will work with.