The Loop, Start to Finish
Lesson 13.1 said a genetic algorithm is four decisions — representation, fitness, selection, variation. This lesson makes each of them concrete. Everything below fits inside one loop that never changes:
1. Create a starting population of random candidates. 2. Evaluate the fitness of every candidate. 3. While budget remains: choose parents by selection, recombine them with crossover, perturb the children with mutation, evaluate the children, and decide which candidates form the next population. 4. Return the best candidate ever seen — which, as the elitism section explains, is not automatically the best candidate in the final population.
Notice where the cost sits. Selection, crossover and mutation are arithmetic on short data structures and are effectively free. Step 2 is where the money goes: if fitness means training a model, then a population of 50 over 100 generations is 5,000 training runs. Every parameter choice below is really a decision about how to spend those evaluations.
Encoding: The Choice That Constrains Everything
The representation is the first decision because the variation operators have to act on it. Choose badly and your crossover produces children that are not valid solutions at all. Four encodings cover almost everything:
Binary strings. The classical form, and the one Holland (1975) analysed and Goldberg (1989) built his worked examples on. Each bit is a switch, or a group of bits is a number decoded to a range. It suits subset selection perfectly: with 40 candidate features, a 40-bit string is a subset.
Real-valued vectors. One floating-point number per parameter, which is the natural choice for continuous quantities such as a regularisation strength or a filter coefficient. There is no decoding step and no resolution limit, but the operators change: bit flips are meaningless and are replaced by Gaussian perturbation.
Permutations. When a solution is an order — the sequence in which a crew visits 20 sites, the order of operations in a schedule — the candidate is a permutation, and validity is a hard constraint: every element must appear exactly once. This is the encoding where naive crossover breaks, as shown below.
Trees. When the thing being evolved is an expression or a program, the candidate is a tree: operators at the internal nodes, variables and constants at the leaves. Crossover swaps subtrees. This is the representation genetic programming and symbolic regression use, and Lesson 13.4 returns to it.
Ask one question of any representation you are considering: does its natural crossover and mutation produce valid candidates? If yes, the whole method stays simple. If no, you now need repair procedures or constraint handling — a real cost, and the subject of part of Lesson 13.3. A second, softer question: are values that mean similar things written similarly? In plain binary, 127 is 01111111 and 128 is 10000000 — consecutive numbers in which every bit differs, so no single mutation can step from one to the other. Flip that same top bit on 127 instead and you get 255. Adjacency in value is not adjacency in the encoding, which is why real-valued encodings, or a Gray code where consecutive integers differ by exactly one bit, are often preferred.
Selection: Choosing Parents
Selection is the only step that consults fitness, so it is where the search direction comes from. Three schemes cover standard practice.
Tournament selection. Pick k candidates at random from the population and let the best of them become a parent. Repeat for each parent slot. The tournament size k is the selection-pressure dial: k = 2 is gentle and lets weak candidates through often, while a large k means only near-best candidates ever reproduce. Brad Miller and David Goldberg (1995) analysed tournament selection in exactly these terms. It is also the practical favourite for two mundane reasons: it needs no global sum and no sorting, only comparisons, and it is unaffected by adding a constant to every fitness value.
Roulette wheel, or fitness-proportionate selection. Give each candidate a slice of a wheel in proportion to its fitness, then spin. In code: form the cumulative sum of fitness values, draw a uniform random number between 0 and the total, and take the candidate whose cumulative interval contains it. It has two real weaknesses. Fitness must be non-negative for the slices to make sense, so a loss or an error has to be transformed first. And as Lesson 13.1 showed with 10-versus-9 becoming 1000-versus-999, the pressure it applies depends on the arbitrary scale and offset of your fitness values.
Rank-based selection. Sort the population and assign each candidate a selection probability from its rank, discarding the raw fitness values entirely. James Baker (1985) proposed this precisely to decouple selection pressure from fitness scale. The usual form is linear in rank with a single pressure parameter:
Crossover: Recombining Two Parents
Crossover is the operator that makes this family different from every single-point search method. It is applied with probability pc; with probability 1 − pc the parents are copied through unchanged. Rates in the range 0.6 to 0.9 are the common starting point, and De Jong’s 1975 thesis is the early empirical study of settings like this — take them as sensible defaults to start from, not as measured optima for your problem.
One-point crossover. Choose a cut position and give the child everything before the cut from parent A and everything after it from parent B. Two-point crossover. Choose two cuts and swap the middle segment. Uniform crossover. Decide each position independently by coin flip, taking that gene from A or from B.
The difference between them is which structure survives. One-point crossover keeps genes that sit near each other on the string together, and only rarely separates them — so with a binary encoding the arbitrary decision of which parameter you wrote at which position starts to matter. This positional effect is what Holland’s 1975 analysis of which patterns survive recombination is about. Uniform crossover has no positional preference at all, which is exactly its strength and its weakness: nothing is privileged, and no long block of co-adapted genes is safe.
For real-valued vectors there is a fourth option with no discrete analogue — blend the parents rather than cutting them:
Permutations need their own operator. Cut two visiting orders at a point and splice them and you will usually get nonsense — a route that visits site 3 twice and never visits site 7. Order crossover fixes this by construction: copy a contiguous segment from parent A into the child, then fill the empty positions with the elements the child still lacks, taking them in the order they appear in parent B.
Parent A is 1 2 3 4 5 6 7 8 and parent B is 3 7 5 1 6 8 2 4. Copy positions 4 to 6 from A, so the child starts as _ _ _ 4 5 6 _ _. The elements still missing are 1, 2, 3, 7 and 8; in parent B those appear in the order 3, 7, 1, 8, 2. Fill the empty positions left to right from position 7 onwards, wrapping to the front: position 7 gets 3, position 8 gets 7, then positions 1, 2, 3 get 1, 8 and 2. The child is 1 8 2 4 5 6 3 7 — a valid permutation that inherited a run of consecutive stops from A and the relative ordering of everything else from B. Validity is not repaired afterwards; it is impossible to violate.
Mutation, and the Rate Trade-Off
Mutation is the operator that can introduce material no parent had. Crossover only ever shuffles what is already present in the population, so without mutation a value lost from every candidate is lost permanently.
Bit flip. Visit each bit and invert it with probability pm. Because the flips are independent, the expected number of changed bits in a child is simply the string length times the rate:
Gaussian perturbation. For a real-valued vector, add zero-mean Gaussian noise to each component: x′ = x + σ ε with ε drawn from a standard normal. Here σ is the step size and it is the analogue of the bit-flip rate; a common practice is to shrink it as the run progresses, so early generations explore widely and later ones refine.
Swap. For a permutation, exchange the elements at two randomly chosen positions. Like order crossover, it cannot produce an invalid candidate.
The trade-off in one paragraph. Too low a rate and diversity is never replenished: the population converges, crossover between similar parents stops producing anything new, and the run stalls — the premature convergence of Lesson 13.1, arriving by a different route. Too high a rate and children stop resembling their parents, so good structure is destroyed as fast as selection finds it and you have paid for a population to run a random search. De Jong’s 1975 thesis is the early empirical work here, and the settings it popularised — a population in the tens, a high crossover rate and a small mutation rate of the order of one bit in a thousand — remain a reasonable place to start. Treat them as defaults to be tuned against your own fitness curve, not as facts.
Elitism: Losing the Best Solution Is a Real Bug
Here is a property of the loop that surprises people the first time they see it. Selection is stochastic, so the best candidate in the population may simply not be chosen. Even if it is chosen, crossover and mutation are destructive by design, so what enters the next generation is a modified copy. Put those together and the best fitness in the population can go down from one generation to the next. Nothing in the loop as described so far prevents it.
There are two standard protections and you want at least one of them. Elitism copies the top e candidates into the next generation unchanged, guaranteeing that the population’s best fitness is monotonically non-decreasing; e = 1 or a small percentage of the population is typical. Separately, and even more cheaply, keep a best-ever record outside the population: whenever you evaluate a candidate that beats the incumbent, store a copy. Report that at the end, not the best of the final generation.
The smoothly rising curve in most published figures is a best-so-far curve, and a best-so-far curve cannot go down by definition — so it proves nothing about whether your loop preserves anything. Plot the best fitness in the current population as well. If that trace dips, you are losing solutions, and any run you stop early may report something worse than what it had already found. And do not overcorrect: elitism with a large e is selection pressure under another name, so it drives the diversity collapse of Lesson 13.1 just as reliably as an oversized tournament.
Generational or Steady-State Replacement
Generational replacement builds N children and replaces the entire population with them in one step. It is simple, it is trivially parallel — all N evaluations are independent, so they can run at once — and it is the scheme that most needs elitism, since it discards every parent.
Steady-state replacement produces one or two children per iteration and inserts them into the existing population, evicting somebody: the worst candidate, the oldest, or the child’s most similar parent. Nothing waits for a generation boundary, so a good gene starts being reused immediately. That makes the effective selection pressure higher for the same nominal settings, which cuts both ways: faster progress, and a faster diversity collapse if you are not watching.
Between the two extremes sits the idea of replacing only a fraction of the population each cycle — the generation gap, which De Jong (1975) studied as an explicit parameter. Anything between one individual and the whole population is available to you, and it is one more dial on the same trade-off.
The Exploration/Exploitation Dial, as Concrete Parameters
Exploration and exploitation is a slogan until you can name the settings that move it. In a genetic algorithm you can:
Toward exploration: a larger population N; a smaller tournament size k, or a rank pressure s nearer 1; a higher mutation rate or Gaussian σ; fewer elites; generational rather than steady-state replacement. Toward exploitation: a larger k or an s nearer 2; more elites; steady-state replacement; a smaller σ, particularly late in a run.
Two diagnostics make the tuning empirical rather than superstitious. First, plot diversity beside fitness — the spread of the population, however you measure it, whether mean pairwise distance on real vectors or the fraction of positions that are not fixed on bit strings. Diversity collapsing in the first few generations means too much pressure; diversity staying high while best fitness barely moves means too little. Second, remember what your budget actually buys: N multiplied by the number of generations is the number of fitness evaluations, and that product, not the number of generations, is your bill. Doubling the population halves the generations you can afford.
- The loop is fixed: initialise, evaluate, then repeat select, crossover, mutate, evaluate and replace — and report the best candidate ever seen.
- Fitness evaluation dominates the cost. Population size times generations is the number of evaluations you are buying.
- Encodings are binary strings, real-valued vectors, permutations and trees. The right test is whether the natural operators produce valid candidates.
- Tournament selection makes pressure an explicit dial through the tournament size (Miller and Goldberg, 1995); rank selection removes fitness scale from the picture (Baker, 1985); roulette selection is sensitive to both scale and offset.
- One-point and two-point crossover preserve neighbouring genes and so make position on the string meaningful; uniform crossover has no positional bias; permutations require an order-preserving operator such as order crossover.
- Expected bit flips per child is L times the mutation rate, which is why a rate of one over the string length is a common starting point.
- Without elitism the best fitness in a population can decrease from one generation to the next. Keep elites, keep a best-ever copy, and plot the population best rather than only the best-so-far curve.
- Generational replacement is simple and parallel; steady-state propagates good candidates immediately and raises effective pressure. The generation gap sits between them.
- Exploration and exploitation are not a mood but six concrete settings: N, k or s, the crossover rate, the mutation rate or σ, the elite count, and the replacement scheme.