Genetic Algorithms

Part 5 built a formidable machine. Given a smooth \(F\), Newton and its relatives locate a minimum with a handful of iterations and quantifiable convergence rates. But every one of those methods rests on assumptions that a great many real problems simply refuse to satisfy: that \(\nabla F\) exists and is computable; that a single point can carry the entire search; and — most consequentially — that the local minimum found is the one wanted.

Consider what breaks those assumptions in practice. The objective may be the output of a finite-element simulation or a physical experiment, with no formula to differentiate. The variables may be discrete — which of five motors, how many turns of wire — so that a gradient is not merely unavailable but meaningless. The landscape may be riddled with local minima, in which case a descent method faithfully reports the bottom of whichever valley it happened to start in. And, as Chapter 19 was careful to note, only convexity ever promoted a local answer to a global one.

The design is a deliberate analogy with natural evolution, introduced by John Holland in the 1970s and developed into an engineering tool through the 1980s and 90s. Individuals encode solutions; the fitter ones reproduce more often; their offspring recombine parental material; occasional random mutation introduces variation. Selection supplies the pressure toward quality, while crossover and mutation supply the variety for selection to act on. Nothing in the loop knows anything about calculus.

A GA does not manipulate solutions directly; it manipulates chromosomes — encoded representations of them. Borrowing the biological vocabulary: the chromosome is a string, each position is a gene, and the value at a position is an allele. The encoded string is the genotype; the solution it decodes to is the phenotype. The operators of Section 24-5 act blindly on genotypes, which is exactly why the encoding is the most consequential design decision in the whole algorithm.

Classical GAs use binary encoding. A continuous variable \(x \in [x_{\min}, x_{\max}]\) is represented by an \(L\)-bit string, and the mapping from the integer value \(d\) of that string back to the real number is a simple linear interpolation:

The bit length therefore buys resolution: each extra bit halves the spacing between representable points. Binary strings have one notorious flaw, the Hamming cliff. Adjacent integers can differ in every bit — \(15 = 01111\) and \(16 = 10000\) are neighbours in value but maximally distant in string space — so a mutation cannot easily step between them. Gray coding, in which consecutive integers always differ by exactly one bit, removes the cliff and is generally preferred when binary encoding is used at all.

For continuous engineering problems modern practice usually skips binary entirely and uses real-valued encoding, where the chromosome simply is the vector \(\mathbf{x}\). Precision becomes unlimited, decoding disappears, and the string length equals the number of variables — but the operators must be redesigned, since averaging two real numbers is meaningful whereas swapping bits is not.

Permutation encoding illustrates why the representation cannot be chosen casually. For a travelling-salesman tour, the chromosome is an ordering of cities, and every city must appear exactly once. Apply an ordinary crossover to two valid tours and the offspring will typically visit some cities twice and others never — an infeasible string. The encoding thus dictates the operators, which is why specialised order-preserving crossovers exist for this case.

The fitness function is the GA's only contact with the problem, and it must be a quantity to be maximised, with higher meaning better. Since Part 5 posed everything as minimisation, a conversion is needed. Any monotone decreasing transformation serves; the two standard choices are subtraction from a large constant, or a reciprocal:

Raw fitness values often behave badly under the proportionate selection of Section 24-4. Early on, one lucky individual may dominate the population's total fitness and take over within a few generations; later, when everyone is nearly equally good, the differences become invisible and selection degenerates into a random walk. Fitness scaling — linear, sigma-truncation, or power-law — rescales the values to keep selection pressure roughly constant. Rank-based selection sidesteps the whole issue by discarding magnitudes and using only the ordering.

Constraints require thought, because the operators of Section 24-5 have no notion of feasibility and cheerfully produce illegal offspring. Four approaches are standard, and the most common should look familiar from Chapter 21:

The alternatives each have their place. Rejection — discard infeasible offspring and re-breed — is simple but wasteful when feasibility is rare. Repair maps an illegal string to a nearby legal one and works well when a natural repair exists. Best of all, when it is possible, is a closed encoding in which every string is automatically feasible; permutation encoding does this for the TSP tour constraint by construction. An encoding that cannot express an illegal solution needs no constraint handling at all.

Selection chooses which individuals become parents. It is the only operator that looks at fitness, and therefore the only source of pressure toward good solutions — but it creates nothing new, merely redistributing copies of material already present. The tuning quantity is selection pressure: too little and the search drifts aimlessly; too much and the population collapses onto one individual long before the space has been explored.

Roulette-wheel selection (fitness-proportionate) is the classical scheme. Each individual receives a slice of a wheel in proportion to its fitness, and each spin selects one parent:

The expected-count form is worth pausing on: an individual is expected to receive as many copies as its fitness exceeds the population average. Exactly average means one copy; twice average means two. This ratio drives the entire schema analysis of Section 24-6.

Roulette selection has the weaknesses already noted — it is hostage to the scale of the fitness values, and it fails outright for negative fitness. Tournament selection avoids both and is the modern default: pick \(k\) individuals at random, and the fittest wins. It never touches magnitudes, only comparisons, so scaling becomes irrelevant; and \(k\) is a clean dial for selection pressure — \(k = 2\) is gentle, larger \(k\) increasingly ruthless.

Elitism is not a selection scheme so much as an insurance policy laid over one, and it fixes a real defect. Without it, the best individual found so far can be destroyed by crossover or mutation and simply lost — the GA's best-so-far can get worse. Copying the top \(e\) individuals unchanged into the next generation guarantees the best never deteriorates. A small \(e\) (one or two) is almost always worth having; a large one is just excessive selection pressure by another name.

Selection decides who reproduces; crossover and mutation decide what the children look like. The two operators play sharply different roles, and confusing them is the most common conceptual error in the subject.

Crossover is the recombination operator and the heart of the GA. Applied to two parents with probability \(p_c\) (typically \(0.6\)–\(0.9\)), it exchanges material to create offspring. Single-point crossover cuts both parents at a common random locus and swaps the tails:

Variants trade off how disruptively they mix. Two-point crossover swaps a middle segment and treats the string as a ring, removing the positional bias that penalises genes at the ends. Uniform crossover decides each gene independently by coin flip — maximally mixing, but so disruptive to contiguous groups of genes that it undercuts the building-block argument of Section 24-6. For real-valued chromosomes, arithmetic crossover blends parents, \(\mathbf{c} = \lambda\mathbf{a} + (1-\lambda)\mathbf{b}\), while SBX (simulated binary crossover) and BLX-\(\alpha\) imitate the spread of binary crossover in a continuous space.

Mutation flips each gene independently with a small probability \(p_m\), typically around \(1/L\) so that roughly one bit per chromosome changes. Its role is not to drive the search — crossover does that — but to guarantee reachability. Crossover can only shuffle alleles already present in the population; if every individual carries a \(0\) at some position, no amount of recombination will ever produce a \(1\) there, and that region of the space becomes permanently unreachable. Mutation is the insurance against such lost alleles.

A fair question hangs over everything above: why should this produce anything but noise? There is no gradient, no model, no descent. The classical answer is Holland's schema theorem, and while it is not the last word, it is the argument that turned a biological analogy into a subject.

A schema \(H\) is a similarity template — a string over \(\{0, 1, *\}\), where \(*\) matches either bit. The schema \(1\!*\!*\!0\!*\) describes every 5-bit string starting with \(1\) and carrying \(0\) in position 4, a set of \(2^3 = 8\) strings. Two measurements characterise it: the order \(o(H)\), the number of fixed positions, and the defining length \(\delta(H)\), the distance between the outermost fixed positions. For \(1\!*\!*\!0\!*\): \(o(H) = 2\) and \(\delta(H) = 4 - 1 = 3\).

The two measurements matter because they govern how each operator threatens the schema. Crossover destroys \(H\) only if the cut falls between its fixed positions — probability \(\delta(H)/(L-1)\), so short schemata survive. Mutation destroys \(H\) if it flips any fixed position — probability about \(o(H)\cdot p_m\), so low-order schemata survive. And selection multiplies copies by the ratio of the schema's average fitness to the population's. Combining the three gives the theorem:

These favoured short, low-order, above-average schemata are the building blocks, and the building-block hypothesis is the claim that a GA works by discovering them and recombining them, via crossover, into progressively better solutions. Worked Example 6 makes the mechanism concrete: two schemata of identical order and identical fitness advantage can have opposite fates purely because one is short and the other long.

A second observation compounds the first. Every string of length \(L\) is simultaneously an instance of \(2^L\) different schemata, so a population of \(N\) strings is quietly gathering evidence about far more schemata than it has members — Holland's estimate is on the order of \(N^3\) usefully processed per generation. This is implicit parallelism: the GA evaluates \(N\) individuals but implicitly tests a vastly larger number of hypotheses about which patterns are good.

A GA has more tuning knobs than any method in Part 5, and they interact. The values below are starting points, not prescriptions — the honest position is that good settings are problem-dependent and usually found by experiment.

The characteristic failure is premature convergence: the population collapses onto copies of one above-average individual, diversity vanishes, and — since crossover between identical parents produces identical children — the GA grinds to a halt at a mediocre answer with only mutation still doing anything. The cause is almost always excessive selection pressure early on, when one lucky individual dominates a young population. The countermeasures are diversity-preserving: rank or tournament selection instead of raw roulette, larger populations, fitness sharing (individuals in crowded regions have their fitness discounted), crowding replacement, or restarts.

Every one of these knobs is really the same knob — the exploration–exploitation balance. Exploration surveys new regions; exploitation refines what is already good. High selection pressure, high elitism and low mutation all exploit; large populations, low pressure and high mutation all explore. Too much exploitation converges prematurely to a local optimum; too much exploration never converges at all. Every parameter above is a vote on this one trade, which is why they must be tuned together rather than individually.

Termination is equally heuristic — there is no \(\lVert\nabla F\rVert \le \varepsilon\) to test, since no gradient exists. In practice one stops after a generation budget, after the best fitness has stagnated for a fixed number of generations, when population diversity falls below a threshold, or when a target value is reached. And because a GA is stochastic, a single run proves nothing: report results over multiple independent runs with different seeds, quoting best, mean and standard deviation. A GA that "found the optimum" once in twenty runs is a very different tool from one that finds it every time.

Where a random number is needed, state the convention you use. Difficulty rises down the list.