Genetics
The operators of an evolutionary algorithm — spawn, select, cross, mutate, survive and read — for bits, reals, integers and permutations, written as masks and one-hot contractions.
This module holds the operators every evolutionary algorithm is assembled from. A population is a matrix
\(P \in \mathbb{R}^{n \times g}\) — one individual per row, one gene per column — and its fitness a vector
\(f \in \mathbb{R}^n\). Every operator answers a new matrix from those and a tensor of draws sized for one
generation, so the same definitions serve a process that declares its own draws and the categories of
Evolution.
Conventions. Everything maximises: to minimise a cost \(c\), use \(f = -c\) — Ellipsoid, Rosenbrock,
Rastrigin and Zdt in the sample project all write fitness(P) ≔ 0 − cost(P). Draws are arguments: \(u\) is
uniform in \([0, 1)\) and \(z\) standard normal, with the shape each entry states. Integers and permutations
are doubles holding whole numbers, compared with \(=\). An index is a mask — “row \(r\)” is a one-hot row — and
a tie always goes to the lower row index, so every operator is a deterministic function of its draws. For a
draw \(u \in [0,1)^{m \times k}\), \(u_{p0}\) and \(u_{p1}\) are its first two columns (lead, trail), and
\(\lfloor u\,n \rfloor^{-} = \min(\lfloor u\,n \rfloor, n - 1)\) (wholeOf) turns a uniform into a whole number below \(n\).
A NaN fitness is the worst fitness there is, and that one rule holds in every operator here and every family in
Evolution: every ranking entry — tournament, roulette, rankWheel, elite, fittest,
bestScore — reads fitness through clipFitness before any max, min or comparison, which clips
\(\pm\infty\) to \(\pm 10^{300}\) and turns a NaN into \(-10^{300}\). A NaN let through would compare false both ways:
it would share place 0 with the real best, and a mask built on that place would sum two rows into a point no
individual occupies. The replacement is a match, which lowers to a select (Where) on both executors, so the
NaN is never multiplied by zero — that would leave it NaN. A scrubbed NaN ties with \(-\infty\), and the tie goes
to the lower row. placeDown and placeUp themselves stay raw.
open Prelude.Genetics
Spawn
spawnBits · spawnReals · spawnIntegers
spawnBits(u) · u uniforms matrix n×g → bits matrix n×g
spawnReals(u, lo, hi) · lo, hi bounds scalar or vector g → reals matrix n×g
spawnIntegers(u, lo, hi) · lo, hi whole-number bounds → whole numbers matrix n×g
def spawnBits(u) ≔ u < 0.5
def spawnReals(u, lo, hi) ≔ lo + u · (hi − lo)
def spawnIntegers(u, lo, hi) ≔ min(floor(lo + u · (hi − lo + 1)), hi)
spawnOrders
spawnOrders(u) · u uniforms matrix n×g → permutations of \(0 \dots g-1\) matrix n×g
Each row is the within-row rank of its uniforms, ties to the earlier position, so it is exactly a permutation.
def spawnOrders(u) ≔ rowPlace(u)
Read
placeDown · placeUp
placeDown(f) · f fitness vector n → place, 0 for the fittest vector n · placeUp(f) → place, 0 for the least fit
A place is a permutation rather than a midrank: selection and survival need a place each row holds alone. Both
are raw: a NaN is neither above nor below anything and would take place 0 beside the real best, so every caller
reads fitness through clipFitness first.
fittest · bestScore · meanScore · diversity · generationOf
fittest(P, f) → the fittest row vector g, always one of \(P\)’s rows · bestScore(f) → \(\max_i f_i\) through clipFitness, and NaN only when every score is NaN · meanScore(f) → \(\frac1n \sum_i f_i\), raw ·
diversity(P) → \(\frac1g \sum_j s_j^2\), the mean per-gene sample variance · generationOf(u, k) · u tensor G×n×g → slab \(k\) matrix n×g
def fittest(P, f) ≔ einsum("p,pi->i", placeDown(clipFitness(f)) = 0, P)
def diversity(P) ≔ einsum("j->", variances(P)) / columns(P)
def generationOf(u, k) ≔ einsum("gpi,g->pi", u, positions(einsum("gpi->g", u)) = k)
Building blocks
lead(u),trail(u)— columns 0 and 1 of a draw.wholeOf(u, n)— \(\min(\lfloor u\,n\rfloor, n-1)\).across(r, w),along(r, w)— \([p, q] \mapsto r_p\) and \([p, q] \mapsto w_q\).hotAt(r, w)— the one-hot \([q = r_p]\);rowsPicked(H, P)— \(HP\).geneSlots(u)— \(0, 1, \dots, g - 1\).rowPlace(u)— the within-row rank above;tiedAhead(f)— \(\#\{j < i : f_j = f_i\}\).clipHuge(x)— \(\max(-10^{300}, \min(10^{300}, x))\).clipFitness(f)—clipHuge(f)for every number, \(-10^{300}\) for a NaN; run before any ranking reads fitness.
Select
tournament
tournament(P, f, u) · P population matrix n×g · f fitness vector n · u uniforms matrix m×2 → parents matrix m×g
Let \(a_p = \lfloor u_{p0}\,n \rfloor^-\) and \(b_p = \lfloor u_{p1}\,n \rfloor^-\) be the two entrants of pick \(p\). Then row \(p\) of the result is \(P_{a_p}\) when \(f_{a_p} > f_{b_p}\) or (\(f_{a_p} = f_{b_p}\) and \(a_p \le b_p\)), and \(P_{b_p}\) otherwise.
def tournament(P, f, u) ≔ rowsPicked(tournamentPicks(clipFitness(f), u), P)
roulette · rankWheel
roulette(P, f, u) · u uniforms vector m → parents matrix m×g · rankWheel(P, f, u) → parents matrix m×g
A wheel over weights \(w \ge 0\) picks row \(q\) for draw \(u_p\) when \(\sum_{j<q} w_j < \max(u_p \sum_j w_j,\,10^{-300}) \le \sum_{j \le q} w_j\) —
exactly one row per draw. roulette spins over \(w = f - \min f + 10^{-12}\) and rankWheel over \(w_i = \#\{j : f_j < f_i\} + 1\),
both read through clipFitness first.
def roulette(P, f, u) ≔ wheel(P, clipFitness(f) − minimum(clipFitness(f)) + 1e-12, u)
def rankWheel(P, f, u) ≔ wheel(P, below(clipFitness(f)) + 1, u)
Building blocks
fitterOf,scoreAt,entrantA,entrantB,firstWins,tournamentPicks— the tournament’s entrants, their scores and the one-hot of the winner.before(w)— \(\sum_{j<q} w_j\);spun(w, u)— the floored threshold;wheelPicks(w, u)— the one-hot of each spin;wheel(P, w, u).
Survive
elite
elite(P, f, C, g, keep) · P, f parents and fitness · C, g children and fitness (same \(n\)) · keep how many → next population matrix n×g
The parent in place \(r\) of \(\operatorname{placeDown}(f)\) replaces the child in place \(r\) of \(\operatorname{placeUp}(g)\), for every \(r <\) keep.
def elite(P, f, C, g, keep) ≔ C − einsum("q,qi->qi", placeUp(clipFitness(g)) < keep, C) + einsum("qp,pi->qi", eliteSwap(clipFitness(f), clipFitness(g), keep), P)
Cross
onePoint · twoPoint · uniformCross
onePoint(a, b, u) · a, b parents matrix n×g · u matrix n×2 → children · cut \(c = 1 + \lfloor u_{p0}(g-1) \rfloor\); genes \(i < c\) from \(a\).
twoPoint(a, b, u) · cuts \(c_1 \le c_2\) from \(\lfloor u_{p0}(g+1)\rfloor, \lfloor u_{p1}(g+1)\rfloor\); genes \(c_1 \le i < c_2\) from \(b\).
uniformCross(a, b, u, p) · u matrix n×g · gene from \(a\) where \(u < p\).
blendCross · arithmetic · sbx
blendCross(a, b, u, widen) → \(\min(a,b) - \alpha\,|a-b| + u\,(1 + 2\alpha)\,|a-b|\) (BLX-α, \(\alpha\) = widen).
arithmetic(a, b, w) → \(w\,a + (1-w)\,b\).
sbx(a, b, u, eta) → \(\tfrac12\big((1+\beta)\,a + (1-\beta)\,b\big)\) with \(\beta = (2u)^{1/(\eta+1)}\) for \(u \le \tfrac12\) and \(\big(2(1-u)\big)^{-1/(\eta+1)}\) above — one child of simulated binary crossover. sbx and blendCross can both throw a child past either parent
and so past a box; Evolution’s RealGenetic clips every child back in, after crossover and again after mutation.
def sbx(a, b, u, eta) ≔ 0.5 · ((1 + sbxSpread(u, eta)) · a + (1 − sbxSpread(u, eta)) · b)
orderCross
orderCross(a, b, u) · a, b permutations matrix n×g · u matrix n×2 → permutations matrix n×g
With the cuts of twoPoint, the child keeps \(a\) on \([c_1, c_2)\); the genes of \(b\) not in that segment, in the
order they appear in \(b\), fill the other positions from left to right. The free gene of rank \(r\) among \(b\)’s
free genes goes to the free position of rank \(r\), so the child is always a permutation. This is linear order
crossover — a left-to-right fill — not Davis’s OX1, which fills from a rotation of \(b\) starting after the
segment; the two agree on which genes survive and differ only in where the rest land.
def orderCross(a, b, u) ≔ spanMask(a, u) · a + orderFill(b, a, spanMask(a, u))
Building blocks
headMask(c, a)— \([i < c_p]\);onePointMask,spanStart,spanEnd,spanMask— the cuts.sbxSpread(u, eta)— \(\beta\) above.cityHot(a)— \([a_{pi} = c]\);keptCities,freeInB,countBefore,orderMatch,orderFill— order crossover’s ranks.
Mutate
bitFlip(P, u, rate) → \(P + [u < \text{rate}]\,(1 - 2P)\).
gaussianStep(P, z, u, rate, sigma, lo, hi) → \(\operatorname{boxed}(P + [u < \text{rate}]\,\sigma z,\ \ell,\ h)\) with \(\operatorname{boxed}(x, \ell, h) = \max(\ell, \min(h, x))\).
resetStep(P, u, v, rate, lo, hi) → a fresh spawnIntegers(v, lo, hi) where \(u < \text{rate}\).
creepStep(P, u, v, rate, stride, lo, hi) → \(\operatorname{boxed}(P \pm \text{stride})\) where \(u < \text{rate}\), up when \(v < \tfrac12\).
swapStep(P, u, v, rate) → positions \(\lfloor u_{p0} g\rfloor^-\) and \(\lfloor u_{p1} g\rfloor^-\) exchanged where \(v_{p0} < \text{rate}\).
inversionStep(P, u, v, rate) → the inclusive span between those positions reversed where \(v_{p0} < \text{rate}\).
orderLength(P, d) → \(\sum_i d_{P_{pi},\,P_{p,(i+1) \bmod g}}\), the length of the closed tour each row describes.
Examples
A binary tournament over four individuals with fitness 10, 40, 20 and 30:
fn chosen(P, f, u) ↦ tournament(P, f, u)
With \(P\) = [[0,0],[1,1],[2,2],[3,3]] and \(u\) = [[0.1, 0.3], [0.6, 0.9], [0.3, 0.3], [0.55, 0.45]] the entrants are
(0, 1), (2, 3), (1, 1) and (2, 1), and the answer is [[1,1],[3,3],[1,1],[1,1]] — GeneticsCase.A_tournament_picks_the_fitter_of_two_entrants.