NeuroEvolution of Augmenting Topologies (NEAT)

Why Does This Exist?

Every neural network starts with a guess nobody likes admitting: how big should it be? Pick too few hidden units and the net cannot represent the task. Pick too many and you pay in slow training, overfitting, and a pile of dead weights. Gradient training never answers this question, because backprop tunes weights inside a fixed wiring diagram. Topology stays whatever a human drew on day one.

Stanley and Miikkulainen's NEAT (2002) attacks the sizing problem head on: evolve the wiring and the weights together, starting from the smallest possible network and complexifying only when a bigger structure earns its keep. It is evolution as architecture search. And it sits on ideas you already know: searching structures instead of tweaking one policy is exploration at the topology level, while the weight tuning it replaces is the gradient machinery of deep reinforcement learning.

This page covers the four tricks that make it work: minimal-start complexification, historical markings that align crossover, speciation that shelters newcomers, and fitness sharing that stops one species from eating the population. For the gradient-based alternative, read policy gradient next.

Think of It Like This

How It Actually Works

A NEAT genome is a parts list, not a blueprint. Node genes name the parts (inputs, outputs, hidden nodes as they appear). Connection genes wire them: each one stores an input node, an output node, a weight, an enabled flag, and an innovation number. The innovation number is the whole game: a global counter stamps every structural mutation ever invented, in order, so the same structure invented twice in different genomes carries the same number.

Crossover then has no guesswork. Line up both parents' connection genes by innovation number. Matching genes (same number) are inherited from either parent at random. Disjoint genes (a number missing inside the other parent's range) and excess genes (numbers past the other parent's maximum) come from the fitter parent. Two networks with completely different shapes still cross over cleanly, because history, not position, decides what corresponds to what.

Why new topologies need shelter

A fresh hidden node starts with random weights, so its first fitness score is usually worse than the tuned small net it came from. Without protection, selection kills every innovation in one generation and evolution stalls at the minimal net. NEAT's fix is speciation: genomes whose compatibility distance falls under a threshold compete in the same species and share its offspring quota, so newcomers race their own kind while they tune up.

The compatibility distance, with numbers

For two genomes, count excess genes $E$, disjoint genes $D$, and the mean absolute weight difference over matching genes $\bar{W}$. Let $N$ be the gene count of the larger genome. With coefficients $c_1$, $c_2$, $c_3$:

$\delta = \frac{c_1 E}{N} + \frac{c_2 D}{N} + c_3 \bar{W}$

Use the paper's standard coefficients $c_1 = 1.0$, $c_2 = 1.0$, $c_3 = 0.4$ with a speciation threshold $\delta_t = 1.0$. Take three genomes whose largest holds $N = 12$ genes:

1. Genome A versus genome B: $E = 1$, $D = 2$, $\bar{W} = 0.5$. Then $\delta = 1/12 + 2/12 + 0.4 \times 0.5 = 0.0833 + 0.1667 + 0.20 = 0.45$. Since $0.45 < 1.0$, B joins A's species.
2. Genome A versus genome C: $E = 4$, $D = 5$, $\bar{W} = 1.4$. Then $\delta = 4/12 + 5/12 + 0.4 \times 1.4 = 0.3333 + 0.4167 + 0.56 = 1.31$. Since $1.31 > 1.0$, C founds a new species.

Fitness sharing then divides each raw fitness by its species size. A genome scoring 40 in a species of 5 gets adjusted fitness $40 / 5 = 8.0$. Big species get taxed, small promising ones get room, and nobody wins by cloning alone.

Complexification itself is two mutations. Add-link splices a new connection between two existing nodes. Add-node splits an old connection: the old gene switches off (kept in the genome, flagged disabled) and two new genes route through a fresh hidden node. Because growth starts minimal and every addition must survive speciated competition, networks end up as small as the task allows.

Code

The snippet below recomputes the worked example: both compatibility distances and the fitness-sharing adjustment.

1def compatibility_distance(2    excess: int, disjoint: int, w_bar: float, n: int,3    c1: float = 1.0, c2: float = 1.0, c3: float = 0.4,4) -> float:5    """NEAT compatibility distance between two genomes."""6    return c1 * excess / n + c2 * disjoint / n + c3 * w_bar7
8
9def adjusted_fitness(raw_fitness: float, species_size: int) -> float:10    """Explicit fitness sharing: split raw fitness across the species."""11    return raw_fitness / species_size12
13
14d_same = compatibility_distance(1, 2, 0.5, 12)15d_split = compatibility_distance(4, 5, 1.4, 12)16adj = adjusted_fitness(40.0, 5)17
18print(f"same-species delta: {d_same:.4f}")19print(f"new-species delta: {d_split:.4f}")20print(f"adjusted fitness: {adj:.1f}")21print(f"same species: {d_same < 1.0}, new species: {d_split > 1.0}")

1# -> expected output:2same-species delta: 0.45003new-species delta: 1.31004adjusted fitness: 8.05same species: True, new species: True

Watch Out For

The Quick Version

• NEAT evolves network wiring and weights together, starting every run from a minimal net with inputs wired straight to outputs.
• Innovation numbers stamp each structural mutation in order, so crossover aligns genes by shared history instead of guessing which parts correspond.
• The compatibility distance $\delta = E/N + D/N + 0.4\bar{W}$ decides species membership: 0.45 keeps genome B with A, while 1.31 splits genome C off.
• Speciation shelters fresh topologies from open competition, and fitness sharing divides raw scores by species size (40 over 5 members scores 8.0).
• Growth comes from add-link and add-node mutations that switch old genes off rather than deleting them, so small nets stay small until complexity pays.
• Bloat and lazy speciation thresholds are the two traps: penalize excess connections and keep species count turning over.

What to Read Next

• Exploration vs. Exploitation
• Deep Reinforcement Learning
• Policy Gradient Methods