Evolution
Genetic algorithms for four encodings, NSGA-II, evolution strategies, CMA-ES, differential evolution, particle swarms and ant colonies — each a category a process inherits by supplying its fitness.
Each algorithm here is a category: a model with no parameter list that declares the draws a generation
consumes, the state it carries and the step that moves it. A process names it as its parent and supplies what
only the problem knows — usually fitness(P) — and the compiler flattens the two into one process before
checking anything (see Categories). A category reads constructor parameters
it does not declare; a child that lacks one is told so at its own line:
'Knapsack' is Genetic and has no 'genes'; add it to the parameter list.
Every draw is fresh and sized for one generation, so a long run holds one generation of numbers and is still a
deterministic function of its seed. Everything maximises. Every category exposes best, bestFitness and
meanFitness, and runs by Path(n), which keeps the first weight it declares.
One rule for non-finite scores, in every family: a NaN fitness, objective or cost is the worst value there is.
Each ranking reads its scores through clipFitness (Genetics) before any max, min or
comparison — \(\pm\infty\) becomes \(\pm 10^{300}\) and NaN becomes \(-10^{300}\) — so a NaN is never kept over a
finite score, never shares first place with the real best, and best is always a real individual, never a sum
of two. For finite scores nothing changes. bestFitness reads NaN only when no score is a number at all (a
refused population, say); meanFitness stays a plain mean and reads NaN when any score is NaN.
open Prelude.Evolution
Genetic algorithms
| Category | Reads | Child supplies | Defaults |
|---|---|---|---|
Genetic |
size, genes, seed |
fitness(P), and through a leaf spawn(u), cross(a, b, k), mutate(C, k) |
select ≔ tournament, elites ≔ 1 |
BitGenetic : Genetic |
— | fitness(P) |
spawnBits; uniformCross at ½; bitFlip at \(1/g\) |
RealGenetic : Genetic |
lower, upper |
fitness(P) |
spawnReals; sbx at \(\eta = 15\); gaussianStep at \(1/g\), \(\sigma = 0.1\,(h - \ell)\) |
IntegerGenetic : Genetic |
lower, upper |
fitness(P) |
spawnIntegers; uniformCross at ½; resetStep at \(1/g\) |
PermutationGenetic : Genetic |
— | fitness(P) |
spawnOrders; orderCross; swapStep at ½ |
A generation: \(f = \operatorname{fitness}(P)\); children \(C = \operatorname{mutate}(\operatorname{cross}(\operatorname{select}(P, f, u^{\text{pick}}),\ \operatorname{select}(P, f, u^{\text{pair}})))\);
then \(P \leftarrow \operatorname{elite}(P, f, C, \operatorname{fitness}(C), \text{elites})\). Draws: pick, pair, cuts \([n, 2]\); mix, flip, dice \([n, g]\) uniform; noise \([n, g]\) normal.
RealGenetic clips a child back into the box twice: cross (sbx) is itself wrapped in boxed(…, lower,
upper), and mutate (gaussianStep) clips again — a spread \(\beta\) far from one can throw an SBX child past
either parent and so past the box, and a gaussian step can carry it back out.
process Knapsack(values, weights, capacity, size, genes, seed) : BitGenetic {
def packed(P) ≔ einsum("pi,i->p", P, values)
def load(P) ≔ einsum("pi,i->p", P, weights)
def fitness(P) ≔ packed(P) − einsum("i->", values) · max(load(P) − capacity, 0)
}
Many objectives — Pareto (NSGA-II)
Reads size, genes, lower, upper, seed; the child supplies objectives(P) \(\in \mathbb{R}^{n \times m}\), all maximised.
Parents win a crowded tournament; children are sbx plus a gaussianStep; parents and children compete for the
next population. Reads front (1 on the first front) and scores.
Fronts without a loop. Point \(a\) dominates \(b\) when \(O_a \ge O_b\) in every objective and \(>\) in one. The front of \(b\) is the length of the longest chain of dominations ending at \(b\), which is what peeling fronts off one at a time measures. With \(W^{(0)}_{ab} = 1\) where \(a\) dominates \(b\) and \(-10^9\) elsewhere, seven max-plus squarings \(W^{(k+1)} = \max\big(W^{(k)},\ \max_c W^{(k)}_{ac} + W^{(k)}_{cb}\big)\) cover every chain up to 128 steps, and \(\operatorname{front}(b) = \max(0, \max_a W^{(7)}_{ab})\). Populations of up to 128 are exact: those 128 fronts always hold at least 128 points and survival takes \(n\) of the union’s \(2n\), so for \(n \le 128\) every survivor is ranked exactly; front 0 — nothing dominates it — is exact at any population size.
Crowding sums, over objectives, the gap between a point’s nearest neighbours above and below within its front,
over the objective’s range; an edge of a front counts \(10^9\). Survivors are ordered by front, then by
\(1/(1 + \text{crowding})\), then by position. The union of parents and children is stacked, \([2, n, \cdot]\).
Objectives go through clipFitness before domination and crowding alike, so a NaN objective is that objective’s
worst value: the point is still ranked, on the front its other objectives earn, and every survivor is a real member
of the union.
Evolution strategies — Strategy and Covariance
Strategy — reads parents, children, genes, lower, upper, seed; a \((\mu, \lambda)\) strategy with one step \(\sigma\) per
individual, \(\sigma' = \sigma\,e^{\tau z}\) with \(\tau = 1/\sqrt g\), child \(=\) parent \(+ \sigma' \mathcal N(0, I)\); the best \(\mu\) children
survive. Reads sigma. Fewer children than parents reads NaN from the start: parent \(r \ge \lambda\) has no child
to be, and read as a row of zeros it would sit exactly at a bowl’s optimum, so the selection divides by
children ≥ parents and the starting population and steps are multiplied by its ratio to itself — \(1\), or
\(0/0\) — as a too-small Differential population is.
Covariance (CMA-ES) — reads genes, children, seed, start \(\in \mathbb{R}^g\) and step. Weights location \(m\), sigma
\(\sigma\), shape \(C\), pathSigma \(p_\sigma\), pathShape \(p_c\) and eigenbasis \(B\). It follows Hansen’s 2016 tutorial
(arXiv:1604.00772) in its classic form, positive weights only: recombination, massOf \(=\mu_{\text{eff}}\),
sigmaRate \(c_\sigma\), sigmaDamping \(d_\sigma\), shapeRate \(c_c\), rankOneRate \(c_1\), rankMuRate \(c_\mu\):
\(y_k = B\,\operatorname{diag}(\ell)\,z_k,\ \ \ell = \sqrt{\operatorname{diag}(B^\top C B)}, \qquad m' = m + \sigma \textstyle\sum_k w_k y_k,\) \(p_\sigma' = (1-c_\sigma)p_\sigma + \sqrt{c_\sigma(2-c_\sigma)\mu_{\text{eff}}}\;B\operatorname{diag}(\ell)^{-1}B^\top \bar y, \qquad \sigma' = \sigma \exp\!\Big(\tfrac{c_\sigma}{d_\sigma}\big(\tfrac{\lVert p_\sigma'\rVert}{\mathbb E\lVert\mathcal N(0,I)\rVert} - 1\big)\Big),\) \(p_c' = (1-c_c)p_c + h_\sigma\sqrt{c_c(2-c_c)\mu_{\text{eff}}}\,\bar y, \qquad C' = (1 - c_1 - c_\mu)C + c_1\big(p_c'p_c'^\top + (1-h_\sigma)c_c(2-c_c)C\big) + c_\mu \textstyle\sum_k w_k y_k y_k^\top,\)
and \(B' = \operatorname{eigenvectors}(C)\). The eigenbasis lags the matrix by one generation — the one loop in the
algorithm stays confined to one update — and sampling draws its lengths \(\ell\) from the current \(C\) along the
stale \(B\): not Hansen’s lazy update (which samples a stale \(B\) and a stale \(D\) together, an older \(C\)
throughout), but the current \(C\) with the off-diagonal part of \(B^\top C B\) dropped — measured at about 0–5%
more generations than the eager update. There is a relative eigenvalue floor: each squared length is held at
no less than \(10^{-14}\) of the largest, because a matrix Cholesky factors cleanly can still come back from the
eigensolver with a diagonal entry a hair below zero, and an unguarded root of that would wreck the step. Reads
mean, sigma, spreadMatrix.
Differential evolution — Differential
Reads size ≥ 4, genes, lower, upper, seed; DE/rand/1/bin with scale \(F = 0.8\) and crossRate \(0.9\). For each row
\(i\), three distinct donors \(r_1, r_2, r_3 \ne i\) come from one row of uniforms: its ranking with \(i\)’s own place removed.
The trial takes \(x_{r_1} + F(x_{r_2} - x_{r_3})\) where a uniform is below the crossover rate, and always at one drawn
position; it is clipped, and replaces \(x_i\) when its fitness is no lower — both through clipFitness, so a NaN
parent is replaced by any finite trial and a NaN trial replaces nothing better. A population smaller than four rows has
no three other rows to draw from, and reads NaN from its very first generation — the donor weights divide by
rows(u) > 3, which is \(0/0\) below four and \(1/1\) at or above, so nothing is ever silently read as the row
itself or as a row of zeros.
Particle swarm — Swarm
Reads size, genes, lower, upper, seed. Weights position \(x\), velocity \(v\), memory \(m\) and topScore \(s\):
with inertia \(w = 0.72\), cognitive \(c_1 = 1.49\), social \(c_2 = 1.49\) and \(g\) the leader, the best remembered position.
A NaN evaluation reads as the worst score there is, never an improvement: fitness is passed through
clipFitness before a particle’s memory or the leader ever compares against it, so a broken objective cannot
appear to lead the swarm, and a remembered best survives it.
Ant colony — Colony (Ant System)
Reads size, cities, distances, seed — size ants, not ants: a process named Ants cannot also declare a
parameter ants, since C# refuses a property named like its own class (CS0542), so every family in this file
reads size instead. Every ant starts at city 0 and, for \(\text{cities} - 1\) turns, moves to an unvisited
city with probability \(\propto \tau_{ij}^{\alpha}\,\eta_{ij}^{\beta}\), \(\eta = 1/d\) — antWalk, one of the two loops in this module (CMA-ES’s eigenbasis is the other),
run once a step as host code, which answers the edges each ant used, \(E \in \{0,1\}^{a \times c \times c}\). Then
\(\tau' = (1 - \rho)\tau + \sum_k (E_k + E_k^\top)/L_k\) — the deposit is symmetric, since an undirected tour lays
pheromone on both directions of every edge it used — with alpha 1, beta 2, evaporation \(\rho = \tfrac12\) and
\(L_k\) = cost(E), the tour length by default, read through clipFitness negated — a NaN cost is \(10^{300}\), the
longest tour, which deposits nothing and is never the route. Every read is NaN before the first step: bestTour, bestLength
and walked all answer NaN until an ant has walked once, the same honesty a too-small Differential population
reads from its start. Reads bestTour (edge matrix), bestLength, pheromone.
Examples
Knapsack above, with values [60, 100, 120, 80, 30, 90, 70, 40, 50, 110], weights [10, 20, 30, 15, 5, 25, 20, 10,
15, 30], capacity 80, a population of 40 and 40 generations — a claim about one named seed, not every seed:
seed 20260915 first reaches 390 at generation 24 of the 40, answering BestFitness() = 390 and Best() =
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0], the brute-forced optimum
(EvolutionCase.Knapsack_from_seed_20260915_reaches_its_brute_forced_optimum). Most seeds, not all, reach it
within 40 generations.