I9. SMS-EMOA: selection by hypervolume contribution¶
Lesson B4 showed that the hypervolume rewards convergence, spread and uniformity at once, and lesson I6 asked why an algorithm should not select for it directly. SMS-EMOA, the S-metric selection evolutionary multi-objective algorithm of Emmerich, Beume and Naujoks [1, 2], does exactly that, in the simplest possible way: create one offspring, and remove the solution whose loss costs the least hypervolume.
SMS-EMOA keeps NSGA-II's non-dominated sorting for convergence and replaces the crowding distance with the exclusive hypervolume contribution for diversity. Because it removes a single solution per step, its contributions always describe the current set; NSGA-II, which cuts a whole front with distances computed once (lesson I3), has no such guarantee.
In this lesson you will learn:
- the steady-state (μ + 1) loop and what it changes;
- how the N + 1 solutions are sorted, and which front loses a member;
- how the exclusive hypervolume contribution is computed, and how the reference point changes it;
- what VAMOS does when the last front has one point, with more than two objectives and with constraints;
- what the selection costs, and when to use SMS-EMOA.
From an indicator to a selection rule¶
The hypervolume, or S metric, was introduced to compare the results of multi-objective algorithms [3]. A set of a given size that maximizes it contains only Pareto-optimal points [4], so an algorithm whose population never loses hypervolume moves towards the front. Emmerich, Beume and Naujoks turned that observation into a selection operator [2], and Beume, Naujoks and Emmerich evaluated the resulting algorithm on two- and three-objective benchmarks and on aeronautical design problems [1].
The steady-state loop¶
SMS-EMOA is a (μ + 1) algorithm, in the terminology of evolution strategies: μ = N parents create one offspring, and the worst of the N + 1 solutions leaves.
Each evaluation changes the population, so a good child can become a parent at once, as in steady-state NSGA-II (lesson I5). The child competes on equal terms: if it is the worst of the N + 1, it is the one removed, and the population does not change.
Parent selection is not part of the method. VAMOS draws both parents uniformly
at random by default, selection("random"), and selection("tournament")
uses NSGA-II's tournament on rank and crowding distance instead.
Sorting the N + 1 solutions¶
The N + 1 solutions are sorted into fronts exactly as in NSGA-II (lesson I2). Only the last front F_v can lose a member; every earlier front is safe. Early in a run, F_v often holds dominated solutions or the child alone. Later, all N + 1 solutions are often mutually non-dominated, v = 1, and the hypervolume alone decides.
VAMOS does not sort from scratch at every step. It keeps the fronts of the population and inserts the child: the child joins the first front whose members do not dominate it, and the members it dominates move down one front, possibly pushing others further. The result is the same set of fronts as a full sort.
Beume et al. [1] also describe a cheaper rule for a population with more than one front: remove the member of the last front that the most solutions dominate. VAMOS does not use it; it always measures hypervolume contributions.
The exclusive hypervolume contribution¶
With S(A) the hypervolume of a set A with respect to a reference point r (lesson B4), the exclusive contribution of s to the last front is the hypervolume lost if s leaves:
With two objectives it is a rectangle. Sort F_v by f₁, so that s₁, …, s_n have increasing f₁ and decreasing f₂; each point's rectangle reaches to the next point along f₁ and to the previous point along f₂, and the two extremes reach the reference point:
A point squeezed between close neighbours has a thin rectangle and leaves first, so the removals thin out crowded regions. Drag the points of the figure and watch which one SMS-EMOA would discard:
The reference point¶
The two extremes' contributions extend to r, so r decides how much they are
worth. Too close, and the extremes contribute almost nothing and are removed
first; far away, and they are always kept. VAMOS offers three rules through
SMSEMOAConfig.builder().reference_point(...):
Ideal and nadir are the best and worst value of each objective over all N + 1 solutions, not only the last front (lesson B2). The default places r one objective range beyond the worst values, so rescaling an objective rescales r with it and the selection does not depend on the units. jMetal's rule lies close to the worst values. A fixed vector suits an objective space whose bounds are known; points outside its box contribute 0 and are removed before any point inside it with a positive contribution. The SMS-EMOA lesson compares the rules and records when VAMOS introduced them. Auger et al. [5] showed how r shapes the distribution that maximizes the hypervolume, and Ishibuchi et al. [6] how to choose it.
Special cases in VAMOS¶
- The last front has one solution. It is removed at once, and no hypervolume is computed. If that solution is the child, the population does not change.
- Ties. The first of the equal smallest contributions is removed, in the order of the population with the child last. Duplicated points contribute 0.
- More than two objectives. The contributions are exact: MooCore's
hv_contributionswhen MooCore is installed, otherwise an exact sweep for two objectives and, for three or more, one exact hypervolume of the front for each point left out. VAMOS uses no approximation. - Constraints. With the default
constraint_mode="feasibility", while any of the N + 1 solutions is infeasible, the one with the largest total violation is removed (the last one on ties), and no hypervolume is computed. Aconstraint_handling(...)technique ranks the N + 1 solutions instead, and the least contributor of its last front leaves; see choose a constraint-handling technique. - Duplicates. With
eliminate_duplicates(True), a child that repeats a decision vector or an objective vector of the population is discarded.
Step through one selection¶
Six parents, P1 to P6, and one child C. Press the step buttons: sort into fronts, identify the last front, compute its contributions, remove the worst. Things to try:
- In the default scenario, the child is dominated by P3 and P4. It is alone in the last front, so VAMOS removes it without computing any hypervolume.
- Switch to the second scenario, or drag C below the front, and step again. All seven points form one front; P4, squeezed between P3 and C, has the smallest contribution and leaves.
- Lower the reference offset to 0. The extremes P1 and P6 now contribute nothing, and P1, the first of them, is removed: the population starts losing its spread.
In VAMOS¶
The contributions of the second scenario, with MooCore and VAMOS' default reference point:
import moocore
import numpy as np
parents = np.array([[0.08, 0.90], [0.20, 0.62], [0.35, 0.45], [0.40, 0.40], [0.62, 0.22], [0.90, 0.06]])
child = np.array([[0.50, 0.30]])
candidates = np.vstack([parents, child]) # the N + 1 solutions, here a single front
nadir, ideal = candidates.max(axis=0), candidates.min(axis=0)
reference = nadir + 1.0 * (nadir - ideal) # VAMOS' default reference point, offset 1.0
contributions = moocore.hv_contributions(candidates, ref=reference)
labels = ["P1", "P2", "P3", "P4", "P5", "P6", "C"]
print("reference point:", reference.round(3))
for label, (f1, f2), value in zip(labels, candidates, contributions):
print(f"{label} ({f1:.2f}, {f2:.2f}): contribution {value:.4f}")
print("SMS-EMOA removes", labels[int(np.argmin(contributions))])
Output:
reference point: [1.72 1.74]
P1 (0.08, 0.90): contribution 0.1008
P2 (0.20, 0.62): contribution 0.0420
P3 (0.35, 0.45): contribution 0.0085
P4 (0.40, 0.40): contribution 0.0050
P5 (0.62, 0.22): contribution 0.0224
P6 (0.90, 0.06): contribution 0.1312
C (0.50, 0.30): contribution 0.0120
SMS-EMOA removes P4
The large margin of the default reference point gives the extremes the two largest contributions. In the algorithm, one step generates a single child, evaluates it, counts the evaluation and runs the survival:
# Excerpt from src/vamos/engine/algorithm/smsemoa/smsemoa.py
def _reference_step(
self, st: SMSEMOAState, problem: ProblemProtocol, eval_strategy: EvaluationBackend
) -> tuple[NDArray[Any], NDArray[np.float64], NDArray[np.float64] | None]:
"""Generate, evaluate and insert one child (the reference for ``CompiledSteadyStep``).
Returns the evaluated child as ``(X, F, G)`` rows.
"""
X_child = self._generate_offspring(st)
F_child, G_child = self._evaluate_offspring(problem, X_child, eval_strategy, st.constraint_mode)
# A constraint-handling technique follows the evaluations before the child's.
progress = run_progress(st.n_eval, st.max_evals)
st.n_eval += X_child.shape[0]
survival_selection(st, X_child, F_child, G_child, self.kernel, progress)
return X_child, F_child, G_child
_generate_offspring draws the two parents (with replacement under random
selection), applies the crossover, and mutates and keeps only its first child.
Without constraints, the survival works on a buffer F_work that holds the N
parents and the child in its last row:
# Excerpt from src/vamos/engine/algorithm/smsemoa/helpers.py
F_work = _ensure_objective_buffer(st, pop_n, st.F.shape[1])
F_work[:pop_n] = st.F
F_work[pop_n] = F_child[0]
if st.ref_adaptive:
st.ref_point = update_reference_point(st.ref_point, F_work, st.ref_offset, st.ref_rule)
fronts = [list(front) for front in st.fronts]
ranks = np.empty(pop_n + 1, dtype=int)
ranks[:pop_n] = st.ranks
ranks[pop_n] = -1
incremental_insert_fronts(fronts, ranks, F_work, pop_n)
worst_front = np.asarray(fronts[-1], dtype=int)
if worst_front.size == 1:
remove_idx = int(worst_front[0])
else:
remove_idx = int(worst_front[least_contributor(kernel, F_work[worst_front], st.ref_point)])
if remove_idx == pop_n:
return
_write_child_survivor(st, X_child, F_child, G_child, pop_n, remove_idx)
- The adaptive reference point is updated from all N + 1 rows before anything is removed.
incremental_insert_frontsinserts rowpop_n, the child, into the cached fronts.- A last front of one member is removed directly; otherwise
least_contributorpicks the member to remove. remove_idx == pop_nmeans the child itself lost: the population is left unchanged. Otherwise the child takes the place of the removed member, and the cached fronts, ranks and crowding distances are updated for the next parent selection.
least_contributor measures the contributions inside the reference box only:
# Excerpt from src/vamos/engine/algorithm/smsemoa/helpers.py
def least_contributor(kernel: KernelBackend, points: FloatArray, ref_point: FloatArray) -> int:
"""Row of ``points`` with the smallest hypervolume contribution (the first on ties).
Points outside the reference box (a fixed user reference) contribute 0; the
others are measured among themselves with the kernel's contribution hook.
"""
inside = np.all(points <= ref_point, axis=1)
if bool(inside.all()):
contributions = kernel.hypervolume_contributions(points, ref_point)
else:
contributions = np.zeros(points.shape[0], dtype=float)
if bool(inside.any()):
contributions[inside] = kernel.hypervolume_contributions(points[inside], ref_point)
return int(np.argmin(contributions))
With the adaptive rules, every point lies inside the box; only a fixed vector
can leave some outside. np.argmin returns the first smallest value, the tie
rule above. The default reference point is computed by:
# Excerpt from src/vamos/engine/algorithm/components/hv_reference.py
def relative_reference_point(F: ArrayLike, offset: float) -> NDArray[np.float64]:
"""``nadir + offset * (nadir - ideal)`` of the rows of ``F``, objective by objective.
The point is the reference ``1 + offset`` of the objectives normalized to
``[0, 1]`` by the ideal and the nadir of ``F``, expressed in the original units.
Rescaling an objective rescales the reference with it, so the order of the
hypervolume contributions, and any selection that follows it, does not depend
on the objective units. An objective with no spread uses a range of 1: all
points then share that factor of their contributions.
"""
values = np.asarray(F, dtype=float)
top = np.max(values, axis=0)
span = top - np.min(values, axis=0)
span = np.where(span > 0.0, span, 1.0)
return np.asarray(top + offset * span, dtype=np.float64)
A complete run on ZDT1 with the default reference point written out:
from vamos import optimize
from vamos.algorithms import SMSEMOAConfig
from vamos.problems import ZDT1
problem = ZDT1(n_var=30)
config = (
SMSEMOAConfig.builder()
.pop_size(50)
.crossover("sbx", prob=0.9, eta=20.0)
.mutation("pm", prob="1/n", eta=20.0)
.selection("random")
.reference_point(offset=1.0, adaptive=True)
.build()
)
result = optimize(problem, algorithm="smsemoa", algorithm_config=config, max_evaluations=5_000, engine="numpy", seed=1)
F = result.F
print("evaluations:", result.data["evaluations"], "| generations of 50 children:", result.data["generation"])
print("returned:", F.shape, "| f1 from", round(float(F[:, 0].min()), 3), "to", round(float(F[:, 0].max()), 3))
print("reference point of the last step:", result.data["reference_point"].round(3))
Output:
evaluations: 5000 | generations of 50 children: 99
returned: (50, 2) | f1 from 0.0 to 0.991
reference point of the last step: [1.982 2.118]
After the 50 initial evaluations, 4,950 children were created, one per step; VAMOS counts a generation every 50 children. The returned set spans nearly the whole range of f₁, because the extremes carry large contributions. The SMS-EMOA lesson records a run with a fixed reference point, and the configuration reference lists every builder method.
Cost¶
Each evaluation is followed by one contributions computation on the last front. With two objectives, a sort of that front suffices, O(n log n) for n points. The cost of the exact hypervolume, and of exact contributions, grows exponentially with the number of objectives [7, 8]; Guerreiro, Fonseca and Paquete [9] survey the exact and approximate algorithms. A run of E evaluations computes E sets of contributions, where NSGA-II computes E / N sets of crowding distances.
With engine="numba" and a supported configuration (real encoding with SBX
and polynomial mutation, among others), VAMOS compiles the whole step, including
the two-objective contributions, and reproduces the NumPy path. For many objectives,
HypE [10] estimates the contributions by Monte Carlo sampling, and
reference-direction algorithms avoid them altogether (lesson
A1).
SMS-EMOA compared¶
- With NSGA-II. Same sorting; the hypervolume contribution replaces the crowding distance, and one child per step replaces N. The contributions account for the shape of the front and are recomputed after every removal.
- With SPEA2 (lesson I7). Both remove one solution at a time; SPEA2 measures distances to neighbours, SMS-EMOA measures the volume a point adds, so its distribution depends on the shape of the front and on the reference point [5].
- With IBEA (lesson I10). IBEA also selects by an indicator but needs only pairwise indicator values, which stay cheap with many objectives.
- When to use it. Two or three objectives, when the hypervolume is the measure that matters, and especially when evaluations are expensive enough that the per-step selection cost does not matter.
Key points¶
- SMS-EMOA is steady-state: each step creates one child and removes one of the N + 1 solutions.
- Only the last front loses a member: the one with the smallest exclusive hypervolume contribution ΔS(s, F_v) = S(F_v) − S(F_v \ {s}).
- The reference point sets the contributions of the extremes; VAMOS' default is nadir + 1.0 · (nadir − ideal) of the N + 1 solutions, recomputed at every step.
- VAMOS removes a single-member last front directly, computes exact contributions for any number of objectives, and handles constraints by violation first.
- The cost of exact contributions limits SMS-EMOA to few objectives.
Next: I10. IBEA: indicator-based fitness.
References¶
[1] Beume, N., Naujoks, B., and Emmerich, M. (2007). SMS-EMOA: Multiobjective selection based on dominated hypervolume. European Journal of Operational Research, 181(3), 1653–1669.
[2] Emmerich, M., Beume, N., and Naujoks, B. (2005). An EMO algorithm using the hypervolume measure as selection criterion. Evolutionary Multi-Criterion Optimization – EMO 2005, Lecture Notes in Computer Science 3410, 62–76.
[3] Zitzler, E., and Thiele, L. (1998). Multiobjective optimization using evolutionary algorithms – A comparative case study. Parallel Problem Solving from Nature – PPSN V, Lecture Notes in Computer Science 1498, 292–301.
[4] Fleischer, M. (2003). The measure of Pareto optima: Applications to multi-objective metaheuristics. Evolutionary Multi-Criterion Optimization – EMO 2003, Lecture Notes in Computer Science 2632, 519–533.
[5] Auger, A., Bader, J., Brockhoff, D., and Zitzler, E. (2009). Theory of the hypervolume indicator: Optimal μ-distributions and the choice of the reference point. Proceedings of the Tenth ACM SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA '09), 87–102.
[6] Ishibuchi, H., Imada, R., Setoguchi, Y., and Nojima, Y. (2018). How to specify a reference point in hypervolume calculation for fair performance comparison. Evolutionary Computation, 26(3), 411–440.
[7] Beume, N., Fonseca, C. M., López-Ibáñez, M., Paquete, L., and Vahrenhold, J. (2009). On the complexity of computing the hypervolume indicator. IEEE Transactions on Evolutionary Computation, 13(5), 1075–1082.
[8] Bringmann, K., and Friedrich, T. (2010). Approximating the volume of unions and intersections of high-dimensional geometric objects. Computational Geometry, 43(6–7), 601–610.
[9] Guerreiro, A. P., Fonseca, C. M., and Paquete, L. (2021). The hypervolume indicator: Computational problems and algorithms. ACM Computing Surveys, 54(6), Article 119.
[10] Bader, J., and Zitzler, E. (2011). HypE: An algorithm for fast hypervolume-based many-objective optimization. Evolutionary Computation, 19(1), 45–76.