SPEA2 (Strength Pareto Evolutionary Algorithm 2)#
SPEA2 is a multi-objective evolutionary algorithm that improves the fitness assignment and archive management of the original SPEA (Strength Pareto Evolutionary Algorithm). It ranks individuals by combining a dominance-based fitness with \(k\)-th-nearest-neighbor density, and maintains a fixed-size external archive using a truncation procedure that avoids losing boundary solutions.
Overview#
SPEA showed strong performance as an early multi-objective evolutionary algorithm, but had two weaknesses.
One was that individuals dominated by the same archive individuals ended up with identical fitness, making it impossible to distinguish between them. The other was that the clustering technique used when the archive exceeded its capacity could lose boundary solutions on the outer edge of the non-dominated solution set.
SPEA2 resolves each of these two weaknesses with an independent mechanism. Each individual \(i\) is assigned a strength \(S(i)\), the number of individuals it dominates, and the sum of the strengths of the individuals that dominate \(i\) becomes its raw fitness \(R(i)\). \(R(i)=0\) means \(i\) is non-dominated, and a larger value indicates it is dominated by more (and stronger) individuals. To distinguish between individuals sharing the same \(R(i)\), the reciprocal of the distance \(\sigma_i^k\) to the \(k\)-th nearest individual in objective space is added as a density term, \(D(i)=1/(\sigma_i^k+2)\). The final fitness \(F(i)=R(i)+D(i)\) is better when smaller, and non-dominated individuals always have \(F(i)<1\).
SPEA2 maintains a fixed-size external archive separate from the population. In each generation, non-dominated individuals (\(F(i)<1\)) are copied from the combined set of the population and archive into a new archive. If the copied archive fits exactly within the specified size, it is used as-is; if it falls short, inferior solutions are added in order of increasing \(F(i)\) to fill it. If it exceeds the specified size, a truncation operator is applied, removing individuals one at a time — always the one with the smallest nearest-neighbor distance — recomputing distances as it goes. Because this procedure breaks ties between individuals with equal distance using the distance to their second- and third-nearest neighbors in turn, boundary solutions are unlikely to be removed by mistake.
The source is [4]. The concrete procedure is shown in the pseudocode below.
Pseudocode#
Algorithm 6 (SPEA2)
Inputs population size \(N\), archive size \(\bar N\), maximum generations \(T\) Output the non-dominated solution set \(A\)
Initialization: generate an initial population \(P_0\), prepare an empty archive \(\bar P_0 = \emptyset\), and set \(t=0\)
Fitness assignment: compute the fitness \(F(i) = R(i) + D(i)\) of every individual in \(P_t\) and \(\bar P_t\)
Environmental selection: copy the non-dominated individuals of \(P_t \cup \bar P_t\) into \(\bar P_{t+1}\). If \(|\bar P_{t+1}| > \bar N\), reduce it with the truncation operator; if \(|\bar P_{t+1}| < \bar N\), fill it with inferior solutions in order of increasing \(F(i)\)
Termination check: if \(t \geq T\) or another termination condition is met, output the non-dominated individuals in \(\bar P_{t+1}\) as \(A\) and stop
Mating selection: perform binary tournament selection (with replacement) on \(\bar P_{t+1}\) to fill the mating pool
Variation: apply crossover and mutation to the mating pool to generate \(P_{t+1}\), set \(t=t+1\), and return to step 2
Flowchart#
flowchart TD
INIT["LHSInitializer<br/>Sample n_init_archive individuals (≈ literature P0) →<br/>rank_population() ranks them<br/>(fitness assignment + environmental selection) →<br/>take top n_init_population as<br/>initial ctx.population (≈ literature P̄1)<br/>(L1, L2, L3)"] --> GEN
subgraph GEN["One generation (DirectStrategy.step)"]
direction TB
ASK["GA.ask()<br/>Binary tournament selection →<br/>SBX crossover →<br/>Polynomial mutation to generate<br/>N offspring<br/>(L5, L6)"] --> EVAL["True evaluation<br/>(no surrogate involved;<br/>no independent pseudocode step)"]
EVAL --> COMB["GA.tell()<br/>Combine population (P̄t) and offspring<br/>into a single pool"]
COMB --> RANK["SPEA2Comparator.rank_population()<br/>prepare_population(): S(i)→R(i)→D(i)→F(i)<br/>sort_population(): F(i)<1 spea2_truncation_order,<br/>F(i)≥1 ascending F(i),<br/>infeasible: ascending cv<br/>(L2, L3)"]
RANK --> TRUNC["TruncationSelection<br/>Take top N̄ individuals as P̄t+1"]
end
GEN --> TERM{"Termination condition<br/>reached?"}
TERM -- "Not yet (L4)" --> GEN
TERM -- "Reached" --> RESULT(["Non-dominated solution set A"])
Configuration in saealib#
Role |
saealib implementation |
Corresponding step |
|---|---|---|
Initialization |
|
L1, L2, L3 |
Search algorithm |
|
L3, L5, L6 |
Parent selection |
|
L5 |
Crossover |
|
L6 |
Mutation |
|
L6 |
Fitness computation & environmental selection |
|
L2, L3 |
Evaluation strategy |
|
No independent step (occurs after L6, before the next L2) |
from saealib import GA, LHSInitializer, SPEA2Comparator, Optimizer
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.strategies import DirectStrategy
from saealib.termination import Termination, max_fe
N = 30 # offspring per generation, and the initial candidate pool size
N_BAR = 20 # SPEA2 external archive size
problem = zdt1(n_var=10)
problem.comparator = SPEA2Comparator()
algorithm = GA(
CrossoverSBX(prob=0.9, eta=20.0),
MutationPolynomial(eta=20.0),
TournamentSelection(tournament_size=2),
TruncationSelection(),
)
opt = (
Optimizer(problem)
.set_initializer(LHSInitializer(n_init_archive=N, n_init_population=N_BAR))
.set_algorithm(algorithm)
.set_strategy(DirectStrategy(n_offspring=N))
.set_termination(Termination(max_fe(2000)))
)
ctx = opt.run()
pareto_f = ctx.pareto_archive.get_array("f")
The problem.comparator = SPEA2Comparator() line cannot be omitted.
In NSGA-II, NSGA2Comparator is the default for n_obj > 1, so the same line could be omitted, but this is not the case for SPEA2.
ctx.pareto_archive is saealib’s own cumulative non-dominated archive, tracked across the entire run independently of any specific algorithm; it is not the same state container as SPEA2’s external archive, which corresponds to ctx.population.
Read ctx.population directly if the paper’s output \(A\) (the non-dominated solutions in the final external archive \(\bar P_{t+1}\)) is specifically what’s needed.
Differences from the source#
With the default ParetoDominator on an unconstrained problem, saealib reproduces SPEA2’s core selection semantics — the strength/raw-fitness/density fitness assignment and the truncation-based environmental selection — as described in the paper.
Two aspects of the execution structure differ from the source.
Initialization: the paper generates an initial population \(P_0\) (size \(N\)) and starts with an empty archive \(\bar P_0 = \emptyset\); the first fitness assignment and environmental selection (L2, L3) only happen once the main loop begins at \(t=0\).
saealib’s LHSInitializer folds this initial fitness assignment and environmental selection into construction itself: it samples n_init_archive individuals (playing the role of the paper’s \(P_0\)), true-evaluates them, and calls rank_population() to rank them before handing the top n_init_population to the initial ctx.population.
The resulting ctx.population at \(t=0\) therefore already corresponds to the paper’s post-selection archive \(\bar P_1\), not to the empty \(\bar P_0\).
Constraint handling: for constrained problems, SPEA2Comparator additionally applies Deb (2000)’s feasibility-first rule [10] — feasible individuals always outrank infeasible ones, and infeasible individuals are ordered by ascending constraint violation.
The SPEA2 algorithm as published does not address constraint handling; this is a saealib-side extension.
Parameters and variants#
Complexity#
Fitness computation (\(S(i)\)/\(R(i)\)/\(D(i)\)) is \(O(M^2)\) (\(M=N+\bar N\)), or \(O(M^2\log M)\) including the distance sort needed for density estimation. The truncation operator is \(O(M^3)\) in the worst case and \(O(M^2\log M)\) on average [4].
Sizing \(N\) and \(\bar N\) independently: ctx.population plays the role of SPEA2’s archive \(\bar P\) — GA.tell() merges it with the offspring, and TruncationSelection (using the SPEA2Comparator configured via problem.comparator) performs environmental selection on the result — so LHSInitializer(n_init_population=...) sets \(\bar N\), and DirectStrategy(n_offspring=...) sets the number of offspring generated (and true-evaluated) per generation, \(N\).
LHSInitializer’s other size parameter, n_init_archive, sets the number of initially evaluated entries in saealib’s own cumulative Archive (ctx.archive) — a different, longer-lived container than SPEA2’s external archive, which keeps growing with every subsequent generation’s evaluations.
At \(t=0\) specifically it also sizes the candidate pool subjected to the first fitness assignment and environmental selection (see Differences from the source above), so a literature-faithful initialization sets n_init_archive=N.
Built-in initializers require n_init_population <= n_init_archive, so an initial state with \(\bar N > N\) cannot be constructed directly.
Swapping the dominator (dominance predicate): SPEA2Comparator(dominator=...) lets you inject a Dominator other than the default ParetoDominator.
Since the computation of \(S(i)\)/\(R(i)\) depends on this dominance predicate, swapping it changes SPEA2’s fitness itself.