Genetic Algorithm Lab (2D): Route and Schema Theorem

The genetic algorithm

A population of P candidate solutions evolves by repeating three steps. Selection: pick parents; here by tournament (draw k individuals at random, keep the best) or, on the Rastrigin problem, by fitness-proportionate “roulette” selection, where individual i is chosen with probability Fi / Σ F. Crossover: combine two parents. Mutation: make small random changes. The best elites may be copied unchanged, which guarantees that the best length never gets worse.

The route problem

A candidate is a permutation of the cities and its cost is the closed tour length Σ |cπ(i) − cπ(i+1)|. Order crossover (OX) copies a random slice of parent 1 and fills the remaining positions in the order the cities appear in parent 2, so every child is a valid tour. Mutations are a swap of two cities, reversal of a segment (a 2-opt move) or moving one city. Tournament selection of size k picks the fittest of P individuals with probability 1 − (1 − 1/P)k, so a larger k means stronger selection pressure and faster, but less diverse, convergence. With mutation switched off and a large k the population loses diversity and stalls on a poor tour (premature convergence).

Building blocks and the schema theorem

Holland’s schema theorem says that for a binary string schema H (a pattern with some bits fixed) under fitness-proportionate selection, one-point crossover with probability p_c and bit-flip mutation with rate p_b: E[m(H, t+1)] ≥ m(H, t) · f(H)/f̄ · [1 − pc δ(H)/(L − 1) − o(H) pb], where m is the number of members, f(H) their mean fitness, f̄ the population mean, δ the defining length, o the order and L the string length. Short, above-average schemata therefore receive exponentially more copies. The 2D page tests this on the Rastrigin landscape, where a schema is a square region of the map. The route page shows a looser analogue: the share of the best tour’s edges that appear across the population, which rises as good edges (building blocks) spread.

Benchmarks

The Rastrigin function f(x, y) = 20 + Σ (xi² − 10 cos 2πxi) has its global minimum 0 at the origin and about 100 local minima on [−5.12, 5.12]². For routes, cities on a circle have a known optimum (the regular polygon, 2NR sin(π/N)); for other layouts the dashed line is a nearest-neighbour plus 2-opt heuristic, which is a good reference but not a proof of optimality.

Honest simplifications

Small problems (up to 60 cities, 2 variables); the evolving creature in the 3D view is a toy truck following the current best tour; schema statistics describe one run, while the theorem is a statement about the expectation (which is why check 1 averages thousands of one-generation trials); the theorem is a lower bound and says nothing about whether the GA finds the global optimum; no restarts, niching or adaptive rates.

Checks run in the page

Route mode: (1) circle optimum formula and a fresh GA run reaching it; (2) order crossover always yields valid permutations; (3) tournament win probability against the closed form; (4) tour length invariance and elitism monotonicity. Rastrigin mode: (1) Holland’s bound against a Monte-Carlo average of one-generation transitions; (2) the function’s minimum and sign; (3) roulette frequencies equal F_i/ΣF; (4) the bit-flip mutation rate.