Historical markings
The idea the whole algorithm rests on: the same innovation gets the same ID, whoever finds it
If you take one idea away from NEAT, take this one. It is a page of code and it is what makes everything else possible.
The problem
You want to cross two networks over. To do that you need to know which gene in one corresponds to which gene in the other - and once mutation has been adding and removing structure for a few hundred generations, that is not obvious at all.
Two genomes both have a connection from their fourth node to their seventh. Are those the same connection, inherited from a common ancestor? Or did two lineages independently stumble on the same edge? If you guess wrong, crossover takes two networks that solve the problem in different ways and produces a child that does neither.
This is the competing conventions problem, and it is why evolving network topologies mostly did not work before NEAT.
The answer
Give every structural innovation an ID the first time anyone discovers it, and hand out the same ID to everyone who discovers it afterwards.
generation 12, genome A grows 4 -> 7 no one has had this edge: ID 91
generation 12, genome B grows 4 -> 7 seen before: ID 91
generation 40, genome Q grows 4 -> 7 still ID 91
A: ... 88 91 94 ...
B: ... 91 92 ...
^^
the same gene, provably
Now crossover is a walk down two sorted lists, speciation can tell “shares ancestry” apart from “happens to look similar”, and neither has to compare network structure at all.
// Innovations assigns NEAT historical markings.
//
// The point of a historical marking is that the *same* structural innovation
// gets the *same* ID no matter which genome discovers it. That is what lets
// crossover line two genomes up gene-for-gene, and what lets the compatibility
// distance tell "shares ancestry" apart from "happens to look similar". A
// plain incrementing counter cannot do this: two genomes that independently
// grow the same connection would be handed different IDs and would then look
// maximally dissimilar forever.
type Innovations struct {
mu sync.Mutex
ids IDProvider
connections map[connectionKey]int
splits map[int]Split
}
type connectionKey struct {
from, to int
}
Two kinds of marking
A connection is identified by what it joins:
// ConnectionID returns the innovation number for a connection between two
// nodes, allocating one the first time this connection is ever seen.
func (i *Innovations) ConnectionID(from, to int) int {
i.mu.Lock()
defer i.mu.Unlock()
key := connectionKey{from: from, to: to}
if id, ok := i.connections[key]; ok {
return id
}
id := i.ids.Next()
i.connections[key] = id
return id
}
A node is not:
// NodeID returns a brand new node ID with no structural meaning attached.
func (i *Innovations) NodeID() int {
return i.ids.Next()
}
That asymmetry threw me at first, and it is right. “A connection from 4 to 7” names something two genomes can arrive at independently. “A hidden node” does not - there is nothing about a bare node to match on. What is matchable is where it came from, which is the next section.
Splitting a connection
Adding a node in NEAT means splitting an existing connection in two and putting a node in the middle. That is one innovation producing three genes: the node, and the two halves.
before after
4 ------ 91 ------ 7 4 --- 92 --- (new node 93) --- 94 --- 7
91 disabled
All three have to be stable, so the split is recorded against the connection that was split:
// Split records the genes created when a connection is split by an add-node
// mutation, so that the same split always yields the same three IDs.
type Split struct {
NodeID int
InConnection int
OutConnection int
}
// SplitConnection returns the genes for splitting the given connection with a
// new node, allocating them the first time this connection is ever split.
func (i *Innovations) SplitConnection(connectionID, from, to int) Split {
i.mu.Lock()
defer i.mu.Unlock()
if split, ok := i.splits[connectionID]; ok {
return split
}
split := Split{
NodeID: i.ids.Next(),
InConnection: i.ids.Next(),
OutConnection: i.ids.Next(),
}
i.splits[connectionID] = split
// Register the two halves so that a later "add connection" mutation
// producing the same edge reuses the same innovation number.
i.connections[connectionKey{from: from, to: split.NodeID}] = split.InConnection
i.connections[connectionKey{from: split.NodeID, to: to}] = split.OutConnection
return split
}
Those last two lines are the detail I would have missed. The two halves of a split are ordinary connections, and a later add-connection mutation can produce the same edge by a completely different route. If the split did not register them, that edge would get a second, different marking, and two genomes holding what is structurally the same connection would look unrelated forever.
There is a matching lookup that allocates nothing, used by the add-node mutation:
// LookupSplit returns the genes previously allocated for splitting the given
// connection, without allocating any.
func (i *Innovations) LookupSplit(connectionID int) (Split, bool)
It is there because markings are stable, which has a consequence: splitting a given connection always yields the same node ID. If a lineage re-enables a connection that was split earlier and splits it again, it would add a second copy of a node it already has. The add-node mutation asks first, and skips that connection.
Where the registry lives
Not on the Config.
// Breeder produces genomes: it bundles the three things every mutation needs
// together, the settings, the run's random source, and the innovation registry.
//
// These belong in one place because two of them are mutable run state, not
// configuration. Hanging the innovation registry off Config makes a Config
// look reusable when it is not: building a second population from the same
// Config would silently continue the first one's gene-ID sequence, so replaying
// a seeded run in the same process would not reproduce it.
type Breeder struct {
cfg Config
rng *Rand
innovations *Innovations
scratch *crossoverScratch
}
Config is a plain description of what to do, and it is safe to copy. The mutable state - the random source and the innovation registry - lives on the breeder, which the population owns. Two populations built from one Config are two independent runs, which is exactly what anyone would assume.
It has to be saved with the run
// InnovationsSnapshot records which historical markings have been handed out.
//
// This has to travel with the population. Restoring the genomes but not the
// registry would let a later mutation issue a marking that is already in use,
// and two different structures sharing a marking is precisely what historical
// markings exist to prevent.
type InnovationsSnapshot struct {
CurrentID int
Connections []ConnectionInnovation
Splits []SplitInnovation
}
A checkpoint that restores the genomes and not the registry looks like it works. The run carries on, the fitness keeps climbing, and somewhere a few hundred generations later two structurally unrelated genes are sharing a marking and crossover is quietly producing nonsense. It is the sort of bug that does not crash anything and does not look like a bug - it just makes the algorithm slightly worse than it should be, forever.
Next: the mutations that do not change the structure, and so need none of this.