Reproduction

Building the next generation in parallel without making the run depend on which goroutine won

Every species knows how many offspring it is owed. This is the part that produces them - which is where the expensive work is, and where the temptation to parallelise it runs straight into the requirement that a seeded run be reproducible.

Elitism

// Carry the species' best over untouched, so a solution once found is
// never lost to a bad mutation.
for j := 0; j < elitism; j++ {
	speciesGenomes = append(speciesGenomes, len(newGenomes))
	newGenomes = append(newGenomes, pop.Genomes[species.Genomes[j]])
}

Elitism: 2,

The top two of each species go through unchanged. Without that, the best genome the run has ever produced can be mutated into something worse and simply lost - and since mutation is far more often harmful than helpful, it will be.

There is a cap on it that is not obvious:

if elitism >= numOffspring && numOffspring > 1 {
	// Never let elitism consume a species' entire allowance. A species
	// made up only of unmutated copies of itself cannot search, and
	// with many small species that stalls the whole population.
	elitism = numOffspring - 1
}

A species allocated two offspring with an elitism of two produces two exact copies of what it already had. It cannot improve, cannot get worse, and cannot ever leave that state - and its members will still be there next generation, still scoring the same, still getting two slots. With a dozen small species that is most of the population frozen.

Keeping the population the right size

Proportional allocation plus a minimum species size plus rounding means the total can miss. Both directions are handled explicitly.

// Species were appended in order, so the last species always owns the
// tail of newGenomes: dropping the last genome is dropping that species'
// last member, and a species left with no members goes with it.
for len(newGenomes) > pop.Cfg.PopulationSize {

And when there are too few, the fittest species breeds extra. The interesting case is the one that should never happen:

if len(newSpecies) == 0 {
	// Total extinction: reseed from the best genome ever seen, falling
	// back to any surviving genome if there is no best yet.
	seed := pop.BestEverGenome
	if seed.NumLayers() == 0 {
		if len(pop.Genomes) == 0 {
			break
		}
		seed = pop.Genomes[0]
	}
	newGenomes = append(newGenomes, pop.Breeder.MutateGenome(seed))
	continue
}

Every species stale, every species culled, nothing left. It is meant to be impossible - SpeciesElitism protects the two fittest - but “meant to be impossible” and “cannot happen after a config change” are different claims, and the cost of being wrong is a run that panics on an empty slice a thousand generations in.

The parallelism problem

Breeding is the expensive half of a generation: crossover, four parameter mutations, a genome copy each. It is also pure computation on read-only data, so it ought to parallelise perfectly.

It does not, quite:

// Breeding runs in parallel; the structural mutations that follow it run one
// genome at a time. That split is what lets the expensive part use every core
// without making the run irreproducible: a structural mutation draws a
// historical marking from the shared innovation registry, and if two workers
// raced for those the gene numbering - and with it speciation, and with it the
// whole run - would depend on which goroutine won.

A mutex on the registry makes it safe. It does not make it deterministic: whichever goroutine gets there first takes the lower number, and next time the run is replayed it might be the other one. From there the two runs have different gene IDs, so different compatibility distances, so different species, so different everything.

So reproduction is two passes:

pass 1  (parallel)      crossover + parameter mutations, per slot
pass 2  (serial)        structural mutations, in slot order

// Apply structural mutations one at a time, in slot order, so historical
// markings are handed out in the same order on every run.
source := rand.NewPCG(0, 0)
breeder := pop.Breeder.withRand(rand.New(source))
for i := range slots {
	source.Seed(slots[i].mutateSeed, slots[i].mutateSeed^pcgStreamOffset)
	genomes[slots[i].index] = breeder.mutateStructure(slots[i].genome)
}

The serial pass is cheap - structural mutations fire on a few per cent of offspring and do almost nothing when they do not - so nearly all the work is still parallel.

Seeds, not sources

The other half of determinism is that a worker must not draw from a shared random source either, for the same reason: what it gets would depend on how the work was divided.

// offspringSlot is a place in the next generation waiting for a child.
//
// Each slot carries its own pair of random seeds rather than a random source,
// so that breeding a slot allocates nothing: a worker reseeds the source it
// already owns. Two seeds because breeding and structural mutation happen in
// separate passes, and each needs a stream that depends only on the run's seed.
type offspringSlot struct {
	index      int
	species    Species
	breedSeed  uint64
	mutateSeed uint64
	genome     Genome
}

// Draw every slot's seeds up front, in order, from the population's own
// source. They therefore depend on the run's seed and nothing else - not on
// how the work is later divided between goroutines.
for i := range slots {
	slots[i].breedSeed = pop.Breeder.rng.Uint64()
	slots[i].mutateSeed = pop.Breeder.rng.Uint64()
}

Every slot’s randomness is decided before any worker starts. A worker then reseeds the PCG source it already owns:

source := rand.NewPCG(0, 0)
breeder := pop.Breeder.withRand(rand.New(source))
for {
	i := int(next.Add(1)) - 1
	if i >= len(slots) {
		return
	}
	source.Seed(slots[i].breedSeed, slots[i].breedSeed^pcgStreamOffset)
	slots[i].genome = breeder.breed(pop, slots[i].species, floor)
}

Reseeding rather than constructing is why this allocates nothing per slot, and PCG is cheap enough to reseed that it is not worth avoiding.

Work is pulled off an atomic counter rather than split up front, because genome sizes vary wildly by the end of a run and a static split leaves cores idle.

seeds drawn in order, once     ->  workers take slots as they free up
                                   in whatever order they like
slot 0  breed=a0 mutate=b0         worker 1: 0, 3, 4
slot 1  breed=a1 mutate=b1         worker 2: 1, 2, 5
slot 2  breed=a2 mutate=b2
...                                same result either way

There is a test asserting the same seed gives the same population at 1, 2, 4, 8, 16 and unlimited workers, which is the only way I would believe any of the above.

Where a copy is and is not needed

if len(species.Genomes) > 1 && b.cfg.Chance(rng, b.cfg.MateCrossoverRate) {
	// 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)])
}

Crossover allocates its result, so the child is already exclusively owned. A clone is a struct copy sharing the parent’s slices, so mutating it in place would corrupt a genome that is still in the current generation and may still be an elite.

That is the kind of distinction that is invisible until a run starts producing genomes with impossible structures, which is how I found it.

Next: the loop around all of this.