NEAT: Evolving Neural Topologies

Why Does This Exist?

Every neural net starts with a guess about size. Too few hidden units and the net cannot represent the task. Too many and you pay in slow evaluation, dead weights, and tuning pain. Backprop cannot fix this because it tunes weights inside fixed wiring. Topology stays what a human drew on day one.

Stanley and Miikkulainen introduced NEAT in 2002 to evolve wiring and weights together. Every run starts from the smallest net that connects inputs to outputs, then adds structure only when the bigger shape earns its place. Search over structures 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 moves that make it work: minimal start complexification, historical markings that align crossover, speciation that shelters newcomers, and fitness sharing that stops one species from taking over. For the gradient alternative that keeps topology fixed, read policy gradient next. Fitness below means the task score you define, such as game score or distance walked.

Think of It Like This

How It Actually Works

A NEAT genome is a parts list. Node genes name inputs, outputs, and hidden nodes as they appear. Connection genes wire them. Each connection stores an input node, an output node, a weight, an enabled flag, and an innovation number. The innovation number is a global counter that stamps every structural mutation ever invented, in order. The same shape invented twice in different genomes carries the same number.

Crossover aligns by history

Line up both parents by innovation number. Matching genes share a number and come from either parent at random. Disjoint genes miss inside the other parent range. Excess genes sit past the other parent maximum. Disjoint and excess genes come from the fitter parent. Two nets with different shapes still cross cleanly because shared history decides what corresponds.

Compatibility distance with numbers

Speciation needs a distance. For two genomes, count excess genes $E$, disjoint genes $D$, and mean weight gap over matching genes $\bar{W}$. Let $N$ be the larger gene count. With coefficients $c_1$, $c_2$, and $c_3$:

Here $\delta$ is the compatibility distance, $E$ counts excess genes, $D$ counts disjoint genes, $\bar{W}$ is the mean absolute weight gap on matching genes, and $N$ scales for genome length. Use the paper values $c_1 = 1.0$, $c_2 = 1.0$, $c_3 = 0.4$ with threshold $\delta_t = 1.0$. Take $N = 12$.

Pair A versus B has $E = 1$, $D = 2$, $\bar{W} = 0.5$:

Since $0.45 < 1.0$, B joins A species.

Pair A versus C has $E = 4$, $D = 5$, $\bar{W} = 1.4$:

Since $1.31 > 1.0$, C founds a new species.

Sheltering newcomers and sharing fitness

A fresh hidden node starts with random weights, so its first score often trails the tuned small net. Without shelter, selection kills each novelty in one generation. Speciation fixes this by grouping close genomes so newcomers race their own kind while they tune.

Fitness sharing then splits raw score by species size. A genome scoring 40 in a species of 5 gets $40 / 5 = 8.0$. Large species pay tax, small promising ones keep room, and cloning alone cannot win.

Growth itself is two mutations. Add link wires two existing nodes. Add node splits one wire: the old gene switches off but stays stored, and two new genes route through a fresh hidden node. Because runs start minimal and each addition must survive speciated contests, nets stay as small as the task allows.

Code

This snippet recomputes both distances and the sharing adjustment from the worked example.

1def compatibility_distance(excess: int, disjoint: int, w_bar: float, n: int) -> float:2    return excess / n + disjoint / n + 0.4 * w_bar3
4
5def adjusted_fitness(raw: float, size: int) -> float:6    return raw / size7
8
9print(f"{compatibility_distance(1, 2, 0.5, 12):.4f}")  # -> 0.450010print(f"{compatibility_distance(4, 5, 1.4, 12):.4f}")  # -> 1.310011print(f"{adjusted_fitness(40.0, 5):.1f}")  # -> 8.0

Watch Out For

The Quick Version

• NEAT evolves wiring and weights together, starting each run from a minimal net with inputs wired straight to outputs.
• Innovation numbers stamp each structural change in order, so crossover lines up genes by shared history.
• Compatibility distance $\delta = E/N + D/N + 0.4\bar{W}$ gates species: 0.45 keeps B with A, 1.31 splits C off.
• Speciation shelters fresh shapes from open contest while they tune random weights.
• Fitness sharing divides raw score by species size, so 40 over 5 members scores 8.0.
• Add link and add node grow the net, with old genes switched off but kept, so small nets stay small until complexity pays.

What to Read Next

• Exploration vs. Exploitation
• Deep Reinforcement Learning
• Policy Gradient Methods
• Evolutionary Methods and Neuroevolution