Evolutionary Algorithms — Natural Selection as Computation

1. The Evolutionary Loop

Every evolutionary algorithm follows the same high-level loop, mirroring biological evolution:

1. Initialise a population of candidate solutions (individuals), usually at random
2. Evaluate each individual: compute its fitness (how well it solves the problem)
3. Select parents from the population, favouring higher fitness
4. Reproduce: apply crossover (recombination) and mutation to produce offspring
5. Replace some or all of the old population with offspring
6. Repeat from step 2 until a termination criterion (target fitness, evaluation budget, or convergence)

The beauty is its generality: as long as you can encode solutions and measure fitness, the algorithm requires no knowledge of gradients, problem structure, or convexity. This makes it applicable wherever gradient descent fails — discontinuous, multimodal, noisy, or black-box objective functions.

2. Chromosome Encoding

A chromosome (or genotype) is the internal representation of a candidate solution. The choice of encoding profoundly affects which genetic operators make sense and how efficiently the search space is explored.

Binary Encoding

The original GA encoding represents each solution as a bit string. Each bit or group of bits encodes one parameter. Binary encoding enables classical crossover and bitwise mutation. It is natural for combinatorial problems — knapsack, scheduling, feature selection — where solutions are inherently discrete.

Real-Valued Encoding

For continuous optimisation, encoding parameters as floating-point numbers avoids the precision loss of binary representation. Crossover blends parent values; mutation adds Gaussian noise: x' = x + N(0, σ²). Real-valued encoding is standard in evolution strategies and is more appropriate for neural network weight optimisation.

Permutation Encoding

Problems like the Travelling Salesman Problem require solutions that are orderings of items. Standard crossover operators break permutation validity, necessitating specialised operators like Order Crossover (OX) or Partially Mapped Crossover (PMX).

3. Fitness Functions and Landscapes

The fitness function f(x) assigns a scalar score to each individual, guiding the search toward better solutions. Designing a good fitness function is often the hardest part of applying evolutionary algorithms — a poorly designed fitness landscape can cause premature convergence or mislead the search entirely.

Visualising the fitness function as a fitness landscape (a surface over the space of all possible solutions) reveals the challenge:

• Unimodal landscapes — one global optimum; gradient methods work fine and EAs provide no particular advantage
• Multimodal landscapes — many local optima separated by valleys; gradient descent gets trapped, EAs can maintain population diversity and escape
• Deceptive landscapes — the fitness gradient points toward a sub-optimal peak; EAs with crossover can overcome this via the building-block hypothesis
• Neutral networks — flat fitness plateaus connected by ridges; mutation can random-walk across neutral space to reach new adaptive peaks

Fitness shaping techniques address pathological landscapes: novelty search rewards behavioural diversity rather than objective fitness; quality-diversity algorithms (MAP-Elites) maintain a map of high-performing solutions across a behavioural descriptor space; multi-objective EAs (NSGA-II, MOEA/D) optimise several competing objectives simultaneously, producing a Pareto front of trade-off solutions.

4. Selection: Tournament and Roulette

Selection determines which individuals become parents of the next generation. It must balance exploitation (favouring high-fitness individuals) with exploration (maintaining diversity to avoid premature convergence).

Roulette Wheel (Fitness-Proportionate) Selection

Each individual i is assigned a selection probability proportional to its fitness:

A random number in [0, 1] selects an individual, as if spinning a weighted roulette wheel. Problem: if one individual has vastly superior fitness, it dominates selection and genetic diversity collapses quickly — premature convergence. Fitness scaling (rank-based or sigma-truncation) mitigates this.

Tournament Selection

Sample k individuals at random and select the fittest among them as a parent. The tournament size k controls selection pressure: k = 2 (binary tournament) is mild; larger k increases pressure. Tournament selection is robust, works with negative fitness values, and is trivially parallelisable — it is the most commonly used method in modern EAs.

Elitism

Always copy the best m individuals unchanged into the next generation, guaranteeing that the best solution found so far is never lost to genetic drift. Elitism dramatically improves convergence speed on most problems at negligible computational cost.

5. Crossover Operators

Crossover (recombination) combines genetic material from two parents to produce offspring. The hypothesis is that if two fit individuals each contain partial solutions to the problem, their offspring may combine those good partial solutions — the building-block hypothesis.

Single-Point Crossover

Choose a random cut point k. Child 1 takes genes 1..k from parent A and genes k+1..n from parent B; child 2 takes the complement:

Uniform Crossover

Each gene position is independently inherited from parent A or B with probability 0.5. This produces maximum mixing — beneficial when good genes are scattered throughout the chromosome rather than clustered. It disrupts building blocks more than single-point crossover, so the optimal choice depends on the problem's epistatic structure.

Blend Crossover (BLX-α) for Real Values

For real-valued encoding, the offspring gene is sampled uniformly from the interval [min(a,b) − α·d, max(a,b) + α·d], where d = |a − b| and α is a parameter (typically 0.5). This allows offspring to explore slightly outside the range of their parents, maintaining diversity without pure random mutation.

6. Mutation and the Schema Theorem

Mutation introduces random changes to an individual's chromosome, preventing the population from converging to a local optimum and ensuring the search can, in principle, reach any point in the solution space.

For binary encoding, each bit flips independently with probability p_m (the mutation rate). Typical values: p_m = 1/L where L is chromosome length — on average, one bit flips per individual per generation. Too high a mutation rate destroys good solutions faster than selection can preserve them; too low a rate gives insufficient exploration.

The Schema Theorem

Holland's Schema Theorem provides a theoretical foundation for why GAs work. A schema H is a template over {0, 1, *} where * matches either bit, e.g. H = 1*10*. The theorem states that short, low-order, above-average schemata receive exponentially increasing samples across generations:

where m(H,t) is the count of schema H in generation t, f(H) is the schema's average fitness, f̄ is population average fitness, δ(H) is the defining length (distance between first and last fixed positions), and o(H) is the order (number of fixed positions). Schemata with high fitness, short defining length, and low order are preserved and amplified — these are the "building blocks" the GA implicitly discovers and combines.

7. NEAT: Neuroevolution of Augmenting Topologies

Standard GAs with fixed-length chromosomes can evolve neural network weights but not architecture. NEAT, developed by Kenneth Stanley and Risto Miikkulainen in 2002, evolves both the weights and topology of neural networks simultaneously — starting from minimal networks and growing complexity only as needed.

Historical Markings (Innovation Numbers)

Every new gene (node or connection) receives a global innovation number when it first appears via mutation. When crossover combines two networks of different structure, genes with matching innovation numbers are aligned; excess and disjoint genes are inherited from the fitter parent. This solves the "competing conventions problem" — two networks that implement the same function but encode it differently can still exchange genetic material meaningfully.

Speciation

NEAT measures genetic compatibility between individuals using a distance function that accounts for disjoint genes and weight differences. Individuals are grouped into species. Fitness is shared within species: each individual's fitness is divided by the species size, so species compete for population slots proportional to their best members. This protects new structural innovations from extinction before they have time to optimise — the computational equivalent of geographic isolation in biology.

Complexification

NEAT starts with minimal networks (input nodes connected directly to output nodes, no hidden nodes) and adds structure only when mutations create new nodes by splitting existing connections, or add new connections between existing nodes. Networks grow exactly as complex as necessary.

8. Evolution Strategies and CMA-ES

Evolution Strategies (ES) are evolutionary algorithms designed specifically for continuous optimisation. Rather than binary chromosomes, individuals are real-valued vectors, and the key insight is: rather than fixing the mutation distribution, learn it adaptively from the population.

The Covariance Matrix Adaptation Evolution Strategy (CMA-ES) is the state-of-the-art derivative-free optimiser for continuous, non-convex problems. At each generation it maintains a multivariate Gaussian distribution N(m, σ²C) over the search space and samples new individuals from it:

After evaluating all λ offspring, the μ best are selected and used to update three quantities:

• m (mean): weighted average of selected offspring — moves the distribution toward good solutions
• σ (global step size): adapted via cumulative step-size adaptation (CSA) to target the optimal success rate of approximately 1/5 improvements per generation
• C (covariance matrix): updated using rank-μ and rank-1 updates to align the mutation ellipsoid with the fitness landscape's principal curvature directions

CMA-ES is invariant to monotone transformations of fitness, rotation and rescaling of the search space. It achieves superlinear convergence on quasi-quadratic functions and handles ill-conditioned landscapes gracefully. It is the algorithm of choice for hyperparameter optimisation, mechanical design, and any problem with 10–1000 continuous parameters and no analytic gradient.

9. Real-World Applications

Circuit Design

John Koza used genetic programming to evolve analogue electronic circuits from scratch. His system re-discovered the topology of patented human-designed circuits and in some cases produced novel designs that outperformed them — without any prior knowledge of circuit theory. NASA's Space Technology 5 mission flew a spacecraft antenna designed by an evolutionary algorithm, one that human engineers would likely never have conceived.

Drug Discovery

Molecular structures can be encoded as SMILES strings or molecular graphs and evolved toward target binding affinity, synthesisability, and toxicity constraints simultaneously. Multi-objective EAs navigate the vast chemical space (~10⁶⁰ possible drug-like molecules) and have contributed to candidates for antibiotic resistance and protein-protein interaction inhibitors.

Spacecraft Trajectories

Planning fuel-optimal interplanetary trajectories is a non-convex, mixed-integer problem. ESA uses differential evolution and particle swarm optimisation to design gravity-assist sequences — chains of planetary flybys that use gravitational slingshots to reach distant targets with minimal propellant. Both the BepiColombo mission to Mercury and the JUICE mission to Jupiter used EA-designed trajectory solutions.

Game AI and Robotics

NEAT and its successors have evolved controllers for bipedal walking robots, swimming fish simulations, and competitive game agents. OpenAI used evolution strategies at scale — running thousands of parallel evaluations — to train agents for MuJoCo locomotion tasks, demonstrating that ES can compete with reinforcement learning when massively parallelised, since fitness evaluations are trivially independent.