A glossary of tiny lectures, part 8

Week 8: optimizers

By Tim Menzies, published 2026-11-02, updated 2026-11-02

Summary: Fifty years of search, in four short functions: genetic algorithms, differential evolution, simulated annealing and greedy local search — plus the random baseline that exists to embarrass anyone whose clever method cannot beat a lucky dip. They all work. They also spend evaluations like water, which is fine when the model is cheap and ruinous when it is not. Demos in ezr-eg8.lua; machinery verbatim from ezr-apps.lua.

The drag race

New acronyms: GA (genetic algorithm), DE (differential evolution), SA (simulated annealing).

snap and guess: The classic optimizers invent new x values, so their offspring have no goals at all. Rather than call the model for every mutant, this code SNAPS a mutant to the nearest real row and grades it by that neighbour's disty. That is a lie with a purpose: it keeps the comparison fair (every method scores against the same pool) and it keeps the demos fast. Homework asks where the lie leaks.
```
function TBL.guess(i,row)
  return i:disty(i:snap(row)) end
```
mutate: Copy a row, re-pick a few x cells: symbols by frequency (rare values stay rare), numbers by a gaussian step of one standard deviation, clamped to ±3sd. Mutation is where every population method gets its new ideas, and the clamp is what stops those ideas leaving the world the data came from.
```
function pick(col,v,    sd)
  if col.has then return wkey(col.has) end
  v  = v ~= "?" and v or col.mu
  sd = col:div()
  return max(col.mu - 3*sd,
             min(col.mu + 3*sd, v + sd * gauss())) end
```

ga (genetic algorithm): Darwin in twelve lines. Keep a population; to make each kid, pick two parents by a domination tournament, cut-and-splice them, then mutate. Repeat for the.gens generations and return the best of the final population. Everything expensive lives in the fitness call, which is why a GA is a fine idea when the model is cheap and a terrible one when each label costs a week.

function TBL.ga(i,    pop,kids)
  pop = slice(shuffle(i.rows), 1, the.np)
  for _ = 1, the.gens do
    kids = {}
    for _ = 1, the.np do
      push(kids, i:mutate(cross(i, tourn(i, pop),
                                    tourn(i, pop)))) end
    pop = kids end
  return i:snap(keysort(pop, function(r)
                          return i:guess(r) end)[1]) end

de (differential evolution): The population IS the step size. A kid is a + F(b - c) for three random members — so while the population is spread out the jumps are long, and as it converges they shrink automatically, with no cooling schedule to tune. A kid replaces its parent only if it is better. Across this course's races, DE is the classic that keeps winning.

function TBL.de(i,    pop,es,t,kid,d,at)
  pop = slice(shuffle(i.rows), 1, the.np)
  es  = map(pop, function(r) return i:guess(r) end)
  for _ = 1, the.gens do
    for j = 1, #pop do
      t   = some(pop, 3)
      kid = i:extrapolate(t[1], t[2], t[3])
      d   = i:guess(kid)
      if d < es[j] then pop[j], es[j] = kid, d end end end
  at = 1
  for j = 2, #es do if es[j] < es[at] then at = j end end
  return i:snap(pop[at]) end

local search: The (1+1) loop, stripped to nothing: mutate the current solution, accept the mutant if the acceptance rule says so, and remember the best ever seen. ls accepts only improvements — fast, and stuck in the first valley it finds.

local function climb(i,accept,    s,e,b,eb,kid,d)
  s = i.rows[rand(#i.rows)]
  e = i:guess(s)
  b, eb = s, e
  for h = 1, the.budget1 do
    kid = i:mutate(s)
    d   = i:guess(kid)
    if d < eb then b, eb = kid, d end
    if accept(e, d, h) then s, e = kid, d end end
  return i:snap(b) end

sa (simulated annealing): The same loop with one different line: accept a WORSE mutant with probability e^-Δ/T, where the temperature T falls as the budget burns. Early on it wanders (escaping local valleys); late on it only improves. One rule, two behaviours, zero extra machinery — which is why annealing is still the best first thing to try on a strange problem.
```
function TBL.sa(i)
  return climb(i, function(e,d,h)
    return d < e or rand() < exp((e - d) /
      (1 - h/the.budget1 + 1e-32)) end) end
```
race: The drag race: every optimizer, several repeats, plus a best-of-np random baseline (any) that exists to embarrass anyone whose clever method cannot beat a lucky dip. Results go straight into ranks, so the output is a rank table, not a champion. Always race against any; papers that do not are how the field wastes decades.
```
function TBL.race(i,repeats,    d)
  d = {ga={}, de={}, sa={}, ls={}, any={}}
  for _ = 1, repeats or the.repeats do
    push(d.ga,  i:disty(i:ga()))
    push(d.de,  i:disty(i:de()))
    push(d.sa,  i:disty(i:sa()))
    push(d.ls,  i:disty(i:ls()))
    push(d.any, i:disty(
      keysort(some(i.rows, the.np), i:Y())[1])) end
  return d, ranks(d) end
```
Holland: Adaptation in natural and artificial systems. John H. Holland. University of Michigan Press, 1975.

Storn & Price: Differential evolution -- a simple and efficient heuristic for global optimization over continuous spaces. Rainer Storn, Kenneth Price. Journal of Global Optimization 11, 1997, 341-359.

Kirkpatrick, Gelatt & Vecchi: Optimization by simulated annealing. S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi. Science 220(4598), 1983, 671-680.