SMS-EMOA (S Metric Selection EMOA)#

Layer 2: Compose

SMS-EMOA is a steady-state multi-objective evolutionary algorithm that incorporates dominated hypervolume (the \(\mathcal{S}\) metric) directly into the selection criterion. After splitting the population into fronts via non-dominated sorting, it culls one individual at a time — the one with the smallest hypervolume contribution within the lowest front — monotonically increasing the population’s overall dominated hypervolume with each generation.

Overview#

The hypervolume indicator is widely used as a measure of the quality of a Pareto-front approximation. Fixing a reference point \(\mathbf{y}_{\mathrm{ref}}\) lets you define the Lebesgue measure \(\mathcal{S}(B, \mathbf{y}_{\mathrm{ref}})\) of the region dominated by a solution set \(B\), and it is known that maximizing \(\mathcal{S}\) for a finite Pareto-front approximation is equivalent to finding the true Pareto set.

SMS-EMOA doesn’t stop at using this hypervolume indicator for evaluation — it adopts it as the selection operator itself. Using the same non-dominated sorting as NSGA-II, it splits the population into fronts \(\mathcal{R}_1, \ldots, \mathcal{R}_v\), and within the lowest front \(\mathcal{R}_v\), culls the single individual whose removal causes the smallest decrease in the \(\mathcal{S}\) metric. This decrease is called the exclusive hypervolume contribution, \(\Delta_{\mathcal{S}}(s, \mathcal{R}_v) := \mathcal{S}(\mathcal{R}_v) - \mathcal{S}(\mathcal{R}_v \setminus \{s\})\).

Because hypervolume computation is expensive, SMS-EMOA uses steady-state generational replacement. Each generation generates only a single new individual via crossover and mutation, and culls a single existing individual to keep the population size \(\mu\) constant. This avoids having to compare \(\binom{\mu+\lambda}{\mu}\) combinations as in \((\mu+\lambda)\) generational replacement, keeping \(\mathcal{S}\)-metric evaluations within the lowest front to at most \(\mu+1\).

The source is [5]. The concrete procedure is shown in the pseudocode below.

Pseudocode#

Algorithm 8 (SMS-EMOA)

Inputs objective functions, population size \(\mu\), initial population \(P_0\) Output the population \(P_{t+1}\) of the final generation

  1. Set \(t=0\); generate an initial population \(P_0\) of \(\mu\) individuals

  2. Generate a single new individual \(q_{t+1}\) from \(P_t\) via crossover and mutation

  3. Non-dominated-sort \(Q = P_t \cup \{q_{t+1}\}\) (size \(\mu+1\)) to obtain the front sequence \(\mathcal{R}_1, \ldots, \mathcal{R}_v\)

  4. Identify the lowest front \(\mathcal{R}_v\) (if \(|\mathcal{R}_v|=1\), that single individual is the one to be culled)

  5. If \(|\mathcal{R}_v| > 1\), compute the exclusive hypervolume contribution \(\Delta_{\mathcal{S}}(s, \mathcal{R}_v) = \mathcal{S}(\mathcal{R}_v) - \mathcal{S}(\mathcal{R}_v \setminus \{s\})\) for each individual \(s\) in \(\mathcal{R}_v\), and choose the individual \(r\) with the smallest value

  6. Set \(P_{t+1} = Q \setminus \{r\}\) (which always satisfies \(\mathcal{S}(P_t) \leq \mathcal{S}(P_{t+1})\))

  7. Set \(t=t+1\) and return to step 2, repeating until the termination condition is reached

Flowchart#

        flowchart TD
    INIT["Initializer<br/>Generate initial population P0 of μ individuals<br/>(L1)"] --> GEN
    subgraph GEN["One generation (SteadyStateStrategy.step)"]
        direction TB
        ASK["GA.ask(n_offspring=1)<br/>Randomly select parent →<br/>SBX crossover →<br/>Polynomial mutation to generate one new individual q_t+1<br/>(L2)"] --> EVAL["True evaluation<br/>(no surrogate involved)"]
        EVAL --> COMB["GA.tell()<br/>Combine Q = Pt ∪ {q_t+1}<br/>(L3)"]
        COMB --> SORT["HypervolumeComparator.sort_population()<br/>Non-dominated sorting →<br/>HV contribution within front<br/>(L3-5)"]
        SORT --> TRUNC["TruncationSelection<br/>Cull the last individual<br/>(smallest contribution in the lowest front)<br/>(L4-6)"]
    end
    GEN --> TERM{"Termination condition<br/>reached?"}
    TERM -- "Not yet (L7)" --> GEN
    TERM -- "Reached" --> RESULT(["Population of the final generation"])

Configuration in saealib#

Role

saealib implementation

Corresponding step

Search algorithm

GA (ask(n_offspring=1) generates only one new individual; tell() performs combining \(Q=P_t\cup\{q_{t+1}\}\) and survivor selection)

L2-3, L6

Parent selection

TournamentSelection(tournament_size=1) (uniform random selection with no comparison; the paper does not specify a parent-selection scheme)

L2

Crossover

CrossoverSBX(prob=0.9, eta=20.0)

L2

Mutation

MutationPolynomial(eta=20.0)

L2

Non-dominated sorting + in-front HV contribution

HypervolumeComparator (sort_population internally calls non-dominated sorting and hypervolume_contributions)

L3-5

Survivor selection

TruncationSelection() (culls the last individual in comparator.sort_population’s order — i.e. the one with the smallest contribution in the lowest front)

L4-6

Evaluation strategy

SteadyStateStrategy with SerialEvaluator (sequential evaluation, equivalent to max_workers=1, max_pending=1)

L2, L6-7 (in-generation evaluation)

SteadyStateStrategy requests one candidate per step. The faithful configuration below uses sequential evaluation; asynchronous evaluation is described as a separate extension.

from saealib import (
    GA,
    HypervolumeComparator,
    Optimizer,
    SerialEvaluator,
    SteadyStateStrategy,
)
from saealib.benchmarks import zdt1
from saealib.operators.crossover import CrossoverSBX
from saealib.operators.mutation import MutationPolynomial
from saealib.operators.selection import TournamentSelection, TruncationSelection
from saealib.termination import Termination, max_fe


problem = zdt1(n_var=10)
problem.comparator = HypervolumeComparator()

algorithm = GA(
    CrossoverSBX(prob=0.9, eta=20.0),
    MutationPolynomial(eta=20.0),
    TournamentSelection(tournament_size=1),
    TruncationSelection(),
)
evaluator = SerialEvaluator()

opt = (
    Optimizer(problem)
    .set_algorithm(algorithm)
    .set_strategy(SteadyStateStrategy())
    .set_evaluator(evaluator)
    .set_termination(Termination(max_fe(2000)))
)
ctx = opt.run()
pareto_f = ctx.pareto_archive.get_array("f")

The problem.comparator = HypervolumeComparator() line cannot be omitted. In NSGA-II, NSGA2Comparator is the default for n_obj > 1, so the same line could be omitted, but as with SPEA2 and NSGA-III, SMS-EMOA also requires an explicit assignment.

Asynchronous extension: When evaluation times vary, combine SteadyStateStrategy with AsyncEvaluator and AsyncEvaluationScheduler (for example, max_workers=2, max_pending=2). This extension has a different evaluation order from the sequential configuration above.

from saealib import AsyncEvaluator, AsyncEvaluationScheduler

async_evaluator = AsyncEvaluator(SerialEvaluator(), max_workers=2)
async_schedule = AsyncEvaluationScheduler(async_evaluator, max_pending=2)
async_opt = (
    Optimizer(problem)
    .set_algorithm(algorithm)
    .set_strategy(SteadyStateStrategy())
    .set_evaluator(async_evaluator)
    .set_async_evaluation_scheduler(async_schedule)
)

Differences from the source#

The original SMS-EMOA uses a steady-state procedure that evaluates one individual at a time. This design limits hypervolume calculations for the lowest front to at most \(\mu+1\). The configuration above generates one individual at a time with SteadyStateStrategy. If DirectStrategy generates several individuals per generation instead, HypervolumeComparator ranks hypervolume contributions across every front, so the configuration no longer follows the original procedure that targets only the lowest front. The original procedure does not specify parent selection, so the example uses TournamentSelection(tournament_size=1), which performs no comparison. HypervolumeComparator also does not implement the SMS-EMOA dp variant described in the paper; it provides only the base hypervolume contribution.

Parameters and variants#

Complexity#

Hypervolume computation itself is polynomial in the number of points but exponential in the number of objectives. saealib’s hypervolume (recursive slicing) is \(O(n^{m-1} n \log n)\) (\(n\) the number of points, \(m\) the number of objectives).

The exclusive contribution requires \(k\) leave-one-out HV computations for a front of size \(k\), so computing one front costs \(O(k^{m} \log k)\). Because the paper’s reduction procedure applies this only to the lowest front (size at most \(\mu+1\)), it stays within \(O(\mu^{m} \log \mu)\) per generation [5].

HypervolumeComparator generalizes this by computing contributions across all fronts, but since the sum of front sizes never exceeds \(\mu+1\), the asymptotic upper bound remains \(O(\mu^{m} \log \mu)\).

Alternative reduce procedure (“SMS-EMOA dp”): The paper also proposes a faster variant using the domination count \(d(s, P(t))\) instead of hypervolume contribution.

Handling the reference point: HypervolumeComparator(reference_point=...) accepts a fixed value. With None, it computes a reference point for each front in each generation according to the paper’s definition of adding 1.0 to the worst value of each objective. For two objectives, it follows the paper’s treatment of retaining the two boundary solutions without computing a reference point.

Swapping the dominator (dominance predicate): HypervolumeComparator(reference_point=..., dominator=...) lets you inject a Dominator other than the default ParetoDominator. Since this changes the result of non-dominated sorting, the population subjected to front splitting and contribution computation also depends on this dominance predicate.