Module nsga2 

NSGA-II — the elitist non-dominated sorting genetic algorithm, and atune’s multi-objective sampler.

Multi-objective is the one part of this design that was prepared from M1 and never filled: a trial’s values is a Vec<f64>, Scheduler::on_report takes a values slice so pruning is multi-objective-aware from day one, and StudyView::best deliberately answers None for a multi-objective study because a Pareto front has no total order. Nsga2 and the pareto module are what fill it.

The algorithm, precisely

NSGA-II (Deb, Pratap, Agarwal & Meyarivan 2002) is a generational genetic algorithm whose whole contribution is how it ranks a population:

1. Non-dominated sorting (fast_non_dominated_sort) partitions the population into fronts — front 0 is the Pareto set, front 1 what is left once it is removed, and so on. Rank is the primary fitness.
2. Crowding distance (crowding_distance) measures how isolated a solution is inside its own front, and is the secondary fitness. It is what keeps the population spread along the front instead of clustering on one convenient corner of it.
3. Binary tournament (binary_tournament) on (rank, crowding) picks two parents.
4. Variation in the transform layer’s unit hypercube produces one child: SBX crossover (η_c = DEFAULT_CROSSOVER_ETA) and polynomial mutation (η_m = DEFAULT_MUTATION_ETA, per-parameter rate 1/d) for numeric genes; uniform crossover and re-choice for categorical ones, because a categorical is not an interval (see variation).
5. Elitist survival: once a whole generation of children has been evaluated, parents and children are pooled, non-dominated-sorted, and the next generation is filled front by front — the splitting front truncated by decreasing crowding distance. Elitism is why a solution found in generation 3 cannot be lost in generation 4.

One atune trial is one child. The first population_size trials are a uniform random initial population; from then on every trial is bred.

Constraints: feasibility first

An objective may record constraint values with TrialCtx::record_constraints (≤ 0 satisfied, > 0 violated). Ranking then uses constrained_dominates: a feasible solution beats an infeasible one whatever their objectives say, and two infeasible ones are ranked by total violation — so an infeasible population is driven toward feasibility first and toward the front afterwards. A study that records no constraints is ranked by plain Pareto dominance and pays nothing for the feature.

The values reach this sampler through FrozenTrial::constraints, which the study loop fills at trial end from the trial’s typed constraint blob — the same channel M4.0 opened for the per-seed replicate fan (typed state, never an attribute junk drawer). See crate::pareto::constraint for the full recording mechanism.

State: NSGA-II is stateful

A population is state: it cannot be recomputed from the study history, because which of two mutually non-dominated solutions survived a truncation depends on crowding distances computed against a population that no longer exists. So Nsga2 carries its elite, its part-filled offspring buffer and its in-flight jobs through the M4.0 state seam (state/restore_state), and a study torn down and reopened continues with the exact population it left.

restore_state validates the blob against the live sampler — the population size, the configuration dimension, the objective count, every vector length, and that every gene is a finite coordinate in [0, 1] — and reports a typed Error::Sampler rather than adopting a population shaped for a different search (the trap DEHB and CMA-ES each paid for). Nothing non-finite ever reaches the blob: a child whose objectives or constraints are not all finite is not admitted to the population, because serde_json writes a non-finite f64 as null and it would come back meaning something else entirely.

Determinism

Every draw — the initial population, both tournament picks, the SBX spread factors, the mutation coins and magnitudes — comes from a [ChaCha8Rng] seeded from the study seed through the per-trial sampler_seed, never from ambient entropy. Under a single worker with a fixed seed NSGA-II is fully reproducible, and a reopen restores the population exactly (an acceptance test pins it).

It does not get the trial-number-indexed promise of the determinism contract: NSGA-II is population-based and therefore history-dependent — which children have been evaluated when a generation closes decides what survives, and under parallelism that is thread scheduling. A parallel NSGA-II study is replayable, not pre-determined, exactly like Tpe and Dehb. As with DEHB, a resume is exact when the previous handle stopped on a trial boundary (the loop persists seam state at trial end, not at ask); a handle torn down between an ask and its tell simply re-issues that job.

Modules

variation

The pure NSGA-II variation operators, in the transform-layer unit hypercube.

Structs

Nsga2

The elitist non-dominated sorting genetic algorithm (NSGA-II) as a Sampler.

Constants

DEFAULT_CROSSOVER_ETA

The default SBX distribution index η_c (see variation::sbx_child).

DEFAULT_MUTATION_ETA

The default polynomial-mutation distribution index η_m (see variation::polynomial_delta).

DEFAULT_POPULATION_SIZE

The default population size — the number of trials in one generation.

DEFAULT_SWAPPING_PROB

The default probability that a categorical gene is taken from the second parent in uniform crossover.

MAX_POPULATION_SIZE

The largest legal population.

MIN_POPULATION_SIZE

The smallest legal population: a tournament needs somebody to compare.