Mutating the structure
Adding and removing nodes and connections, and why a new node has to start out doing almost nothing
This is the half of mutation that NEAT is named after: the part that grows the topology. Four mutations, all of them rare.
func (b *Breeder) mutateStructure(genome Genome) Genome {
genome = b.mutateAddNode(genome)
genome = b.mutateDeleteNode(genome)
genome = b.mutateAddConnection(genome)
genome = b.mutateDeleteConnection(genome)
return genome
}
// Structural mutations are rare on purpose. NEAT's whole premise is
// that topology grows slowly from a minimal start, so that a new
// structure has generations to prove itself before the next one lands.
// Deletion is rarer than addition, otherwise structure erodes as fast
// as it appears.
AddNodeMutationRate: .03,
DeleteNodeMutationRate: .01,
AddConnectionMutationRate: .08,
DeleteConnectionMutationRate: .02,
Three per cent. A given offspring almost never gets a new node, and that is the point - a structural change makes a genome temporarily worse almost by definition, and it needs generations of weight-tuning before it can show whether it was worth anything.
Adding a node
A node is added by splitting an existing connection in two and sitting in the middle of it.
before after
4 -------- 91 (w=0.8) -------- 7 4 -- 92 (w=1) -- 93 -- 94 (w=0.8) -- 7
91 still there, disabled
// mutateAddNode splits an existing connection in two with a new hidden node
// between the halves, disabling the original connection.
//
// The split is deliberately close to neutral: the incoming half gets a weight
// of 1 and the outgoing half inherits the old weight, so the new node starts
// out reproducing roughly what the connection it replaced did. A split that
// randomises both weights is a large, usually fatal, perturbation - and NEAT
// depends on new structure surviving long enough to be optimised.
That is the single most important line in the mutation code. With random weights on both halves, a new node is a wrecking ball: the genome that gets one is immediately worse than its siblings, it loses its slot in the next generation, and structural growth never happens at all. With 1 and the inherited weight, the new node passes its input through nearly unchanged - “nearly”, because it has an activation function and a bias of its own - so the genome that grew it is roughly as fit as it was, and has time to find out what the node is for.
The old connection is disabled rather than deleted, so the gene stays available to be re-enabled later.
Which connections can be split
// validConnectionForAddNode picks a connection that can be split, or -1 if
// there is none. Splitting is only defined for a connection that runs forwards
// in layer order: a backward one has no layer strictly between its ends, and a
// node put anywhere else would turn the loop into something a feed-forward
// pass could not evaluate.
Four things disqualify a connection, and each one is a bug I would otherwise have shipped.
Already disabled. Splitting it adds a node that contributes nothing at all, and then costs the genome a gene in the compatibility distance forever.
Attached to a bias node. Bias connections are left alone.
Runs backwards or within a layer. In a recurrent genome those exist, and there is no layer strictly between the two ends to put a node in.
Already split, and this genome has the node. Markings are stable, so splitting a given connection always yields the same node ID. If a lineage re-enabled a connection that had been split earlier and split it again, the genome would end up holding two copies of the same gene:
if split, ok := b.innovations.LookupSplit(connection.ID); ok {
if _, exists := places[split.NodeID]; exists {
continue
}
}
The candidates are shuffled and the first valid one taken, rather than filtered into a list and one picked, so the common case walks a handful of connections rather than all of them.
Adding a connection
// pickPotentialConnection chooses uniformly among the connections that could be
// added: any node in an earlier layer to any node in a later one, and when
// recurrent is set, any of the rest as well.
//
// Restricting this to adjacent layers only would forbid skip connections
// entirely, cutting out a large and useful part of the topology space -
// including the minimal XOR solution, where an input feeds the output directly
// as well as through a hidden node.
The XOR example is not hypothetical. The smallest network that solves XOR has an input wired both through a hidden node and straight to the output. Forbid skip connections and the algorithm cannot express its own textbook answer.
The implementation detail is nicer than I expected:
// The candidates are counted and then walked a second time, rather than
// collected into a slice. There are up to O(nodes^2) of them and exactly one is
// wanted, so building the list allocates a large slice per mutation to throw
// nearly all of it away.
count := 0
forEachPotentialConnection(genome, existing, recurrent, func(potentialConnection) bool {
count++
return true
})
if count == 0 {
return potentialConnection{}, false
}
wanted := rng.IntN(count)
var chosen potentialConnection
forEachPotentialConnection(genome, existing, recurrent, func(candidate potentialConnection) bool {
if wanted == 0 {
chosen = candidate
return false
}
wanted--
return true
})
Two passes and no allocation, instead of one pass and a slice of a few thousand candidates that is discarded immediately.
For a recurrent genome the candidate set is every pair at all - backwards, within a layer, and a node to itself:
feed-forward candidates recurrent candidates
in ----> hidden ----> out everything on the left, plus
in ------------------> out hidden -> hidden (self, the smallest
(any earlier layer to any memory there is)
later one) out -> hidden (backwards)
hidden -> hidden' (within a layer)
Inputs and bias nodes are never targets either way. Writing into a sensor would be overwritten by the input on the next activation regardless.
Removing a node
func (b *Breeder) mutateDeleteNode(genome Genome) Genome {
// ... pick a hidden node at random ...
// Drop every connection to or from the node. Leaving one behind would
// create a dangling gene that references a node the network no longer has.
keptConnections := make([]network.Connection, 0, len(genome.Connections))
for _, connection := range genome.Connections {
if connection.To == removeNodeID || connection.From == removeNodeID {
continue
}
keptConnections = append(keptConnections, connection)
}
genome.Connections = keptConnections
return genome
}
Only hidden nodes are eligible - deleting an input or an output changes what the network is, and the caller’s inputs would stop lining up with their sensors.
The connections have to go with it. network.Compile would actually tolerate the dangling ones, since it drops connections referencing a node it cannot find, but they would still be genes: they would be inherited, they would count in the compatibility distance, and they would be dead weight for the rest of the run.
Empty layers are dropped afterwards, so a genome that loses its only hidden node goes back to being a two-layer genome rather than keeping a hole in the middle.
Removing a connection
The plainest of the four, with one exclusion:
func getConnectionIndexForDeletion(rng *Rand, genome Genome) int {
biasNodes := make(map[int]struct{})
for _, node := range getBiasNodes(genome.Layers) {
biasNodes[node.ID] = struct{}{}
}
deletableConnections := make([]int, 0, len(genome.Connections))
for i, connection := range genome.Connections {
if _, ok := biasNodes[connection.From]; ok {
continue
}
if _, ok := biasNodes[connection.To]; ok {
continue
}
deletableConnections = append(deletableConnections, i)
}
if len(deletableConnections) == 0 {
return -1
}
return util.RandSliceElement(rng, deletableConnections)
}
Bias connections are protected. Where bias nodes are in use at all, they are the network’s only source of a constant, and letting deletion pick them off means a genome can quietly lose the ability to shift its own activations - which the weight mutations cannot get back, because there is no gene left to mutate.
Unlike add-node, this one does build the candidate list. There are at most a few hundred connections, not thousands of pairs, and the exclusion makes counting-then-walking more code than it saves.
All four together
rate mutation what it does to the gene count
.08 add connection +1 connection
.03 add node +1 node, +2 connections, 1 disabled
.02 delete connection -1 connection
.01 delete node -1 node, -(its connections)
Adding outruns deleting by about four to one, which is what keeps genomes growing. Whether that is the right ratio is a question worth measuring on your own problem - on snake I found the library’s defaults let connections pile up over thousands of generations long after the score had stopped improving, and bringing the two rates closer together fixed it.
Next: taking two genomes and making one.