Crossover
Two parents, one child, and the reason the child takes exactly the fitter parent's shape
Historical markings exist so that this post is short. Once both parents' genes carry stable IDs, combining them is bookkeeping.
Three kinds of gene
parent A (fitter) 1 2 3 5 6 7 8
parent B 1 2 3 4 5
^^^^^^^^^ ^ ^^^ ^^^^^
matching | match excess
|
disjoint
matching both parents have it: take the parameter from either
disjoint one parent has it, inside the other's range
excess one parent has it, beyond the other's range
The paper treats disjoint and excess genes the same way when building a child - they are inherited from the fitter parent only - and separates them when measuring how different two genomes are. This implementation follows that, and treats them together here.
The child is the fitter parent, rewired
// Crossover produces a child from two parents, best being the fitter of the two.
//
// Following the NEAT paper: genes present in both parents (matching genes,
// identified by their shared historical marking) take their value from either
// parent, while disjoint and excess genes are inherited from the fitter parent
// only. The child therefore has exactly the fitter parent's structure, which
// also keeps its input and output nodes in their original order - permuting
// them would silently rewire which input feeds which sensor.
func (b *Breeder) Crossover(best, worst Genome) Genome {
The structure comes wholly from the fitter parent. The child’s layers are built by walking the fitter parent’s layers, in order, keeping every node; only the values on those nodes can come from the other parent.
The consequence in that comment is not obvious and it bites hard. If the child’s nodes were assembled from a set union, or sorted by ID, or gathered in whatever order a map iterated, the input nodes could come out in a different order than they went in. network.Compile assigns input positions in the order the nodes are given, so input[0] would silently start feeding a different sensor. Nothing errors. The network just answers a different question than the evaluator thinks it is asking.
Matching genes
for j, bestNode := range layer {
node := bestNode
// Matching gene: take the parameters from either parent.
if worstNode, ok := worstNodes[bestNode.ID]; ok && !cfg.Chance(rng, cfg.MateBestRate) {
node.Bias = worstNode.Bias
node.ActivationFn = worstNode.ActivationFn
}
childLayers[i][j] = node
}
MateBestRate: .5,
A coin toss per gene. The fitter parent decides the shape; for the genes they share, either parent’s numbers will do.
Connections work identically, with one addition:
if matching && (!bestConnection.Enabled || !worstConnection.Enabled) {
// A gene disabled in either parent is usually, but not always,
// disabled in the child. The occasional re-enable is what lets a
// lineage recover a connection an add-node mutation switched off.
connection.Enabled = !cfg.Chance(rng, cfg.MateDisabledRate)
}
MateDisabledRate: .75,
Three times in four the child inherits the disabled state. The fourth time it comes back on.
That quarter matters more than it looks. Every add-node mutation disables a connection, and over a long run a lineage accumulates a growing pile of switched-off genes representing structure it once had. Without a way back, those are dead weight forever: they cost a gene in the compatibility distance and can never contribute again. The occasional re-enable is what makes them a reserve rather than a graveyard.
Not every offspring is a crossover
if len(species.Genomes) > 1 && b.cfg.Chance(rng, b.cfg.MateCrossoverRate) {
fitter, other := selectParents(pop, rng, species, floor)
if pop.GenomeFitness[fitter] < pop.GenomeFitness[other] {
fitter, other = other, fitter
}
// Crossover builds a brand new genome, so it is already ours to mutate.
child = b.Crossover(pop.Genomes[fitter], pop.Genomes[other])
} else {
// A straight clone still shares its slices with the parent, so it has
// to be copied before being mutated.
child = CopyGenome(pop.Genomes[util.RandSliceElement(rng, species.Genomes)])
}
MateCrossoverRate: .75,
A quarter of offspring are a mutated clone of one parent rather than a cross of two. That is not a fallback for when crossover fails - it is a deliberate second channel. Crossover recombines things that already exist; a mutated clone is how a lineage explores away from what its species has.
The fitter, other = other, fitter line is doing real work. Crossover documents its first argument as the fitter parent and behaves quite differently for the two, and roulette selection has no idea which of the two genomes it drew is which.
Not allocating two maps per child
// The lookup tables are scratch space kept on the breeder and cleared
// between children, rather than built afresh: a generation crosses over
// most of the population, and two maps per child was a fifth of the time
// reproduction took.
if b.scratch == nil {
b.scratch = &crossoverScratch{
nodes: make(map[int]network.Node, worst.NumNodes()),
connections: make(map[int]network.Connection, len(worst.Connections)),
}
}
worstNodes, worstConnections := b.scratch.nodes, b.scratch.connections
clear(worstNodes)
clear(worstConnections)
To find matching genes you need the less fit parent indexed by marking. Building that per child is two map allocations, a hundred and fifty times a generation, for a few thousand generations.
Keeping them on the breeder and clearing them instead was worth a fifth of reproduction. The subtlety is that the breeder is copied for each parallel worker:
// scratch is reused by Crossover. It is owned by this Breeder alone: the
// copies made by withRand and withConfig get their own, which is what
// keeps the parallel breeding workers from sharing it.
withRand returns a new Breeder with a nil scratch, so each worker lazily builds its own on first use. Shared scratch space and parallel breeding is exactly the sort of combination that produces a bug you can only reproduce on a machine with more cores than yours.
What it does not do
There is no attempt to line up genes by structure - to notice that two genomes have an equivalent subnetwork wired up differently. That is a genuinely hard problem, and historical markings exist precisely so that nobody has to solve it. Two genes match if and only if they descend from the same innovation, and if two lineages built the same thing independently then the marking registry gave them the same ID anyway.
Next: deciding which genomes are allowed to breed with which.