Evolutionary Computation

ArtificialArtificial Life and Emergent Systems covers complex behaviour emerging from simple, fixed local rules. Evolutionary computation borrows a different, equally simple natural process — not fixed rules, but a population, mutation, and selection — and turns it into a general-purpose search and optimisation technique, formalised by John Holland as the genetic algorithm¹.

The Genetic Algorithm Cycle

AA genetic algorithm maintains a population of candidate solutions, each encoded as a string (classically a bit string, though other encodings work too) called a chromosome, and repeats a four-step cycle:

1. Evaluate: score every individual with a fitness function
2. Select:   individuals with higher fitness are more likely (not certain) to reproduce
3. Crossover: pair up selected individuals; combine parts of each parent's chromosome to make offspring
4. Mutate:   randomly flip a small fraction of bits in the offspring
Repeat for many generations.

Selection being probabilistic rather than strictly "only the best survive" matters — a slightly weaker individual still gets some chance to reproduce, which keeps the search from collapsing too early onto whatever looks best in the first few generations and missing a better solution reachable only through an initially weaker-looking path. Crossover is the operator that makes a genetic algorithm more than random search: two individually decent solutions can combine into a better one if each happens to be strong in a part of the chromosome where the other is weak. Mutation is what keeps the population from settling into a genetic dead end — a bit flip that neither parent had introduces genuinely new information the crossover of existing chromosomes alone could never produce, giving the search a way to reach solutions outside the current population's whole gene pool.

Worked Example: A Toy Optimisation

MaximiseMaximise f(x) = x², where x is encoded as a 5-bit binary chromosome (so x ranges from 0 to 31). Start with a small random population: 01101 (x=13, fitness=169), 11000 (x=24, fitness=576), 00100 (x=4, fitness=16), 10011 (x=19, fitness=361). Selection favours the higher-fitness individuals — 11000 and 10011 are the most likely parents. A single-point crossover after bit 2 on those two parents: 11|000 and 10|011 combine into 11011 (x=27, fitness=729) and 10000 (x=16, fitness=256) — the first offspring is already better than either parent, purely from recombining their bits differently, with no mutation involved yet. A small mutation might then flip one bit of 11011 to 11111 (x=31, fitness=961) — the maximum possible value for a 5-bit chromosome, reached by chance rather than by any directed search, and now carried forward as the population's new best individual for the next generation to build on.

When It's the Right Tool

GeneticGenetic algorithms don't need a gradient, a differentiable objective function, or even a smoothly-behaved search space at all — they only need a way to evaluate a candidate's fitness and a way to encode candidates as chromosomes, which makes them a natural fit for problems where gradient-based methods don't apply: discrete or combinatorial problems (scheduling, circuit layout), problems with a noisy, non-smooth, or entirely unknown fitness landscape, or problems where the objective itself is expensive to evaluate exactly and a good-enough answer found by exploring broadly is more useful than an exact answer found slowly. The trade-off is that a genetic algorithm gives no guarantee of finding the true optimum, and can converge slowly, or prematurely, onto a merely-good-enough solution if the population loses diversity too early — exactly the failure mode mutation exists to guard against, and exactly why tuning the mutation rate (too low: the population stagnates; too high: it never converges on anything) is one of the genuine practical skills in applying the method well — Goldberg's textbook, still the standard practical treatment of genetic algorithms, covers this and the other design trade-offs (population size, selection pressure, encoding choice) in depth².

There's a sharper failure mode worth knowing before writing a fitness function: evolution optimises exactly what the fitness function measures, not what the designer meant by it, and a population will reliably find and exploit any gap between the two. This is the same failure When Agents Fail names reward hacking in a reinforcement-learning agent — a genetic algorithm given a fitness function with a loophole will evolve a population that scores highly through that loophole, not through the behaviour the loophole was meant to be a proxy for.

References