Table of Contents

SMS-EMOA (2007)

S-Metric Selection Evolutionary Multi-objective Optimization Algorithm — Nicola Beume, Boris Naujoks, and Michael Emmerich, SMS-EMOA: Multiobjective selection based on dominated hypervolume, European Journal of Operational Research 181(3):1653–1669, 2007. DOI: 10.1016/j.ejor.2006.08.008.

SMS-EMOA keeps NSGA-II's elitist evolutionary skeleton — and its SBX + polynomial-mutation operators — but replaces the survival criterion. Where NSGA-II breaks ties within a front by crowding distance, SMS-EMOA removes the solution that contributes the least dominated hypervolume (the S-metric). Selecting on the very indicator the field grades approximations by steers the population straight toward a high-hypervolume — hence well-converged and well-distributed — Pareto front. OptunaSharp ships it as SmsEmoaSampler.

The idea

The S-metric (hypervolume) of a set B, bounded by a reference point y_ref that every solution dominates, is the Lebesgue measure Λ of the region B dominates:

S(B, y_ref) = Λ( ⋃_{y∈B} { y' | y ≺ y' ≺ y_ref } )

Maximising it over a bounded-size set is equivalent to finding the Pareto set (Fleischer), and for a fixed number of points the maximiser is empirically well-spread — so hypervolume alone rewards both convergence and diversity. SMS-EMOA is built on two pillars: (1) non-dominated sorting as the primary rank, and (2) hypervolume as the tie-breaker that discards the least-contributing solution in the worst front.

Steady-state (μ+1) main loop. One offspring per generation, one deletion — so Reduce only ever compares the μ+1 leave-one-out hypervolumes of a single front, not a combinatorial (μ+λ) selection:

P₀ ← init()                       # μ random individuals
repeat
    q ← generate(Pₜ)              # ONE offspring by SBX + polynomial mutation
    Pₜ₊₁ ← Reduce(Pₜ ∪ {q})       # drop one, back to μ
until termination

Reduce — the hypervolume survival. Non-dominated-sort the μ+1 individuals into fronts R₁,…,R_v, then delete from the worst front R_v the solution whose exclusive hypervolume contribution is least:

Reduce(Q):
    {R₁,…,R_v} ← fast-nondominated-sort(Q)
    r ← argmin_{s∈R_v} ΔS(s, R_v)      where   ΔS(s, R_v) = S(R_v) − S(R_v \ {s})
    return Q \ {r}

Because a dominated point adds no volume its dominator did not already cover, Reduce never trades a dominator for a dominated point, and the covered hypervolume can only grow — the invariant S(Pₜ) ≤ S(Pₜ₊₁).

Reference point and cost. The contribution ΔS depends on y_ref; the paper recomputes it each generation as the componentwise worst objective values + 1.0 (and in 2-D omits it, always keeping the two extremes). ΔS has closed forms — O(N) in 2-D, an O(μ³) grid method in 3-D — but exact hypervolume is exponential in the number of objectives, which is why SMS-EMOA targets two and three objectives. A cheaper dominating-points selection variant (Algorithm 3 in the paper) is also proposed; OptunaSharp implements the basic ΔS rule.

On the ZDT and DTLZ suites the paper reports SMS-EMOA ranking best on the S-metric on every function except ZDT6, ahead of NSGA-II, C-NSGA-II, SPEA2, and ε-MOEA.

In OptunaSharp

SmsEmoaSampler reconstructs the μ-survivor population from completed trials and evolves it steady-state as above, across Optuna's full parameter space (categorical and single-value distributions fall back to the independent sampler):

using OptunaSharp;
using OptunaSharp.Samplers;

var study = Optuna.CreateStudy(
    directions: new[] { StudyDirection.Minimize, StudyDirection.Minimize },
    sampler: new SmsEmoaSampler(populationSize: 40, seed: 0));

study.Optimize((Func<Trial, IReadOnlyList<double>>)(t =>
{
    double x = t.SuggestFloat("x", 0, 1);
    double y = t.SuggestFloat("y", 0, 1);
    return new[] { x, (1 - Math.Sqrt(x)) + y };
}), nTrials: 400);

The first populationSize (μ) completed trials are the random initial population; every later trial proposes one offspring, generated by the shared NSGA-II child generation (binary tournament + SBX + polynomial mutation — nothing is re-implemented). populationSize, crossover (default SBXCrossover, the paper's classic operator), mutation (default PolynomialMutation), crossoverProb, mutationProb, swappingProb, hvReferenceEps, and seed are configurable.

Beyond-core. SMS-EMOA is absent from Optuna core (which stops at NSGA-II / NSGA-III / MO-TPE), so — like LM-CMA and JANUS — it is a beyond-core, paper-faithful port validated by convergence and achieved hypervolume, not bit-matched to Optuna. On ZDT1 it matches or beats NSGAIISampler using the same SBX + polynomial mutation, confirming the paper's claim that the hypervolume tie-breaker helps. The survival details follow pymoo's SMSEMOA (sms.py), which differs from the 2007 paper in three documented, behavior-preserving ways: the reference point is 1 + hvReferenceEps (default eps = 10) in the population's normalized ideal/nadir box rather than the paper's dynamic worst + 1.0; only the basic ΔS variant is implemented (not the dominating-points one); and the general leave-one-out hypervolume routine is used in place of the paper's specialized 2-D/3-D kernels.

In-memory state. The μ-survivor set is reconstructed incrementally and held in memory for the study's duration, so a SMS-EMOA study does not resume its population across process boundaries (the same concession as JanusSampler).

Relationship to NSGA-II

  • From NSGA-II (2002): inherits the elitist skeleton — combine the population with the new offspring, fast non-dominated sort, fill fronts, and reproduce by binary tournament + SBX + polynomial mutation. Only the secondary score changes: crowding distance → least hypervolume contribution (ΔS).
  • Versus the AGE-MOEA family: those are the other "swap NSGA-II's secondary score" descendants — they replace crowding distance with a geometry-adaptive survival score, where SMS-EMOA replaces it with the S-metric. SMS-EMOA is steady-state (μ+1); the AGE-MOEA family and NSGA-II are generational (μ+λ).

See also

NSGA-II (2002) · NSGA-III (2014) · AGE-MOEA-2 (2022) · Samplers · Multi-objective Optimization · the API reference.

Edit this page