Genetic Algorithms and Evolutionary Computation

Evolution has produced eyes, wings and brains without a designer. Evolutionary computation borrows its principles — variation and selection — to search for solutions to hard optimisation problems. Genetic algorithms (GAs) are especially useful when the objective is not differentiable, the search space is discrete or strange, and we can evaluate candidate solutions but not reason about them analytically.

The core loop#

A genetic algorithm maintains a population of candidate solutions called individuals, each encoded as a chromosome (often a bit string or a vector). Each generation:

1. Evaluate each individual with a fitness function.
2. Select parents, favouring fitter individuals.
3. Crossover (recombination): combine two parents to produce offspring.
4. Mutate: randomly perturb offspring with small probability.
5. Replace the old population (often keeping the best few — elitism).

Selection schemes#

• Fitness-proportionate (roulette wheel): probability of selection $\propto$ fitness. Sensitive to the scale of fitness values.
• Tournament selection: pick $k$ individuals at random, choose the best. Simple, robust and tunable via $k$.
• Rank selection: select based on rank rather than raw fitness.

Selection pressure controls the balance between exploitation (converge fast on good solutions) and exploration (maintain diversity). Too much pressure causes premature convergence.

Crossover and mutation#

For bit strings, one-point crossover picks a cut point and swaps tails:

Parent A: 11010 | 011        Child 1: 11010 | 100
Parent B: 00111 | 100   →    Child 2: 00111 | 011

Uniform crossover chooses each gene from either parent independently. For permutations (like travelling salesperson tours) we need special operators such as order crossover (OX) that preserve validity. Mutation flips bits (probability typically $\approx 1/L$ for length $L$) or adds Gaussian noise to real-valued genes.

A complete GA in Python#

We maximise the number of ones in a 40-bit string (the "OneMax" problem) — trivial, but it shows every component.

import random

L, POP, GENS, PMUT = 40, 60, 80, 1 / 40

def fitness(ind):
    return sum(ind)

def tournament(pop, k=3):
    return max(random.sample(pop, k), key=fitness)

def crossover(a, b):
    cut = random.randint(1, L - 1)
    return a[:cut] + b[cut:], b[:cut] + a[cut:]

def mutate(ind):
    return [1 - g if random.random() < PMUT else g for g in ind]

pop = [[random.randint(0, 1) for _ in range(L)] for _ in range(POP)]
for gen in range(GENS):
    elite = max(pop, key=fitness)
    children = [elite]                         # elitism
    while len(children) < POP:
        c1, c2 = crossover(tournament(pop), tournament(pop))
        children += [mutate(c1), mutate(c2)]
    pop = children[:POP]
    if gen % 10 == 0:
        print(gen, fitness(max(pop, key=fitness)))
print("best:", fitness(max(pop, key=fitness)))

Why does it work? The schema theorem#

John Holland, who invented GAs in the 1970s, analysed them using schemata — templates like 1**0* where * is a wildcard. His schema theorem states that short, low-order schemata with above-average fitness receive exponentially increasing numbers of trials in successive generations:

where $m(H,t)$ counts instances of schema $H$, $f(H)$ is its average fitness, $\delta(H)$ its defining length and $o(H)$ its order. The associated building-block hypothesis suggests GAs work by combining good short building blocks. It gives useful intuition, though it is not a full convergence proof.

Relatives in the evolutionary family#

• Evolution Strategies (ES): real-valued vectors with self-adapting mutation strengths. CMA-ES adapts a full covariance matrix and is a state-of-the-art black-box optimiser for continuous problems.
• Genetic Programming: evolves programs or expression trees — useful for symbolic regression.
• Differential Evolution: creates mutants from differences between population members.
• Neuroevolution: evolves neural network weights and/or architectures (NEAT). Large-scale ES has been shown to be competitive with reinforcement learning on some control tasks because it parallelises extremely well.

When to use evolutionary methods#

Use them when gradients are unavailable, the landscape is rugged or discontinuous, evaluation can be parallelised, or you need a set of diverse solutions (multi-objective optimisation with NSGA-II produces a Pareto front). Avoid them when a gradient or a specialised solver exists — those are usually far more sample-efficient.