NEAT: Neuroevolution of Augmenting Topologies

1. The topology problem in neuroevolution

Evolutionary algorithms optimise neural network weights by treating them as real-valued chromosomes. This works well for fixed-topology networks but runs into the competing conventions problem when topology is also evolved: two networks computing the same function might use completely different structural layouts, so crossover between them produces non-functional offspring that inherit conflicting structures from each parent.

Previous approaches handled this either by evolving only weights (losing the ability to grow networks) or by using indirect encodings and developmental rules that are difficult to analyse. NEAT's key contribution was to provide a principled solution to all three challenges of evolving variable-topology networks:

1. Competing conventions: solved by historical markings (innovation numbers) that track structural homology across genomes.
2. Premature search convergence: solved by speciation — protecting innovations in separate niches until they have time to optimise.
3. Complexity management: solved by starting from minimal networks and growing complexity only when it is beneficial.

2. Genome representation

A NEAT genome consists of two lists of genes:

• Node genes: each specifies a node's unique ID and type (input, hidden, output, bias). There is no positional information — topology emerges from the connections, not layering.
• Connection genes: each specifies an in-node, out-node, weight, enable/disable bit, and an innovation number (a global historical ID for this particular structural addition).

This is a direct encoding: each gene in the genome corresponds directly to one element (node or connection) in the network phenotype. The enable/disable bit allows temporarily silencing a connection without removing it from the genome — preserving evolutionary history and allowing re-enabling in future generations.

3. Historical markings and innovation numbers

The central insight of NEAT is to track the historical origin of each structural gene. Whenever a new connection or node is added to any genome in the population during a generation, it is assigned a globally unique innovation number — a monotonically increasing integer counter.

If the same structural mutation (same in-node and out-node pair for a connection addition, or splitting the same connection for a node addition) occurs in two different individuals during the same generation, it receives the same innovation number. This creates a historical alignment between genomes: genes with matching innovation numbers are homologous — they appeared at the same evolutionary moment and represent the same structural feature.

This alignment-by-history solves the competing conventions problem without requiring any explicit topology matching or graph isomorphism computation — a constant-time operation per gene regardless of network size.

4. Crossover across topologies

NEAT crossover works gene-by-gene using the innovation number alignment:

1. Matching genes (same innovation number in both parents): the offspring randomly inherits the weight from either parent (50/50 coin flip). If either copy is disabled in a parent, the offspring gene has a 75% chance of also being disabled.
2. Disjoint genes (appear in one parent within the range of the other): inherited from the more fit parent. If both parents have equal fitness, inherited randomly.
3. Excess genes (beyond the shorter genome's endpoint): inherited only from the more fit parent.

The offspring's node set is determined by which connection genes are inherited: any node referenced by an inherited connection is automatically included. This ensures the offspring phenotype is a valid network despite the variable structure of its parents.

5. Structural mutations

NEAT uses three types of mutation to explore the topology space:

Weight mutation (continuous)

Connection weights are mutated by adding Gaussian noise: w' = w + N(0, σ²), or occasionally replaced by a completely new random weight. This is the most frequent mutation type, and the primary mode of optimisation within a fixed topology.

Add-connection mutation (structural)

A new connection gene is added between two previously unconnected nodes (respecting the topological ordering to avoid forward-only cycles, unless recurrent connections are enabled). The new connection has a random initial weight and is assigned the next available innovation number. If the same connection was added elsewhere in the same generation, they share the innovation number.

Add-node mutation (structural)

An existing enabled connection is split by disabling it and inserting a new hidden node H between its endpoints. Two new connections are added: IN → H with weight 1.0 (preserving existing network behaviour) and H → OUT with the original weight. This ensures the new structure computes initially the same function as before, protecting the fitness of the individual while allowing the new node's weights to be subsequently refined.

The initial weights (IN→H = 1.0, H→OUT = original weight) are chosen so that the new node does not immediately disrupt the network's current behaviour — a form of minimally disruptive structural innovation.

6. Speciation and the compatibility distance

New structural innovations initially perform poorly because their new weights need time to be optimised. Without protection, a newly mutated genome with an untested topology would be immediately out-competed by established genomes. NEAT protects innovations through speciation: individuals compete primarily within their own species rather than globally.

Two genomes are in the same species if their compatibility distance δ is below a threshold δ_t:

Each genome is assigned to the first species whose representative genome (randomly selected at the start of each generation) has δ < δ_t against it. If no existing species qualifies, a new species is created. Species representatives are replaced each generation, preventing species from becoming "static."

Fitness sharing and reproduction allocation

Within each species, each genome's raw fitness is divided by the species size — a form of fitness sharing that penalises large species and protects small ones:

The number of offspring allocated to each species in the next generation is proportional to its total adjusted fitness, summed over all members. Species that improve their mean adjusted fitness receive more offspring; those that stagnate for a set number of generations are penalised or removed.

7. Minimality and complexification

NEAT starts with the minimal possible network: direct connections from each input to each output and nothing else — no hidden nodes, no extra connections. Hidden nodes and additional connections are added only through mutation, starting from this minimal base.

This minimality principle has two advantages:

• Efficient search: the algorithm first exploits the simplest possible solutions (which are often good enough for simple problems) before exploring more complex topologies.
• Parsimony: solutions that can be found with fewer neurons and connections are preferred, leading to compact, interpretable networks. NEAT does not add complexity without a fitness justification.

This is called complexification: the population as a whole tends to grow in structural complexity over generations, but only in the directions that improve fitness. Different species may explore very different topological strategies simultaneously.

8. JavaScript NEAT XOR demonstration

The simulation below runs a simplified NEAT on the XOR problem — the classic benchmark because it is not linearly separable and requires at least one hidden node. The population evolves over generations, and the best genome's network is rendered on the right. Nodes are arranged by layer (inputs at left, output at right, hidden nodes in between), and connection weights are shown as line thickness. Watch how hidden nodes are gradually added to solve XOR.

Full NEAT with hundreds of individuals is computationally heavy for the browser; this demo uses a lightweight implementation with simplified speciation and structural mutation to illustrate the concepts. The left panel shows fitness over generations; the right panel shows the best genome's network graph with connection weights as line opacity.

// Simplified NEAT genome structure
class Genome {
  constructor() {
    this.nodes = new Map();   // id → { type: 'in'|'hid'|'out'|'bias' }
    this.conns = new Map();   // innov → { in, out, weight, enabled }
    this.fitness = 0;
    this.species  = -1;
  }

  activate(inputs) {
    // Topological sort then forward pass
    const values = new Map();
    for (const [id, n] of this.nodes) {
      if (n.type === 'in')   values.set(id, inputs[n.idx]);
      if (n.type === 'bias') values.set(id, 1.0);
      if (n.type === 'hid' || n.type === 'out') values.set(id, 0);
    }
    for (const [, g] of this.conns) {
      if (!g.enabled) continue;
      const v = (values.get(g.out) ?? 0) + values.get(g.in) * g.weight;
      values.set(g.out, v);
    }
    return sigmoid(values.get(outputNodeId));
  }
}

function compatibility(g1, g2) {
  let E = 0, D = 0, W = 0, M = 0;
  for (const [innov, c1] of g1.conns) {
    if (g2.conns.has(innov)) { W += Math.abs(c1.weight - g2.conns.get(innov).weight); M++; }
    else D++;
  }
  for (const [innov] of g2.conns) if (!g1.conns.has(innov)) E++;
  const N = Math.max(g1.conns.size, g2.conns.size, 1);
  return C1 * E / N + C2 * D / N + C3 * (M > 0 ? W / M : 0);
}