Running a run
Evaluation, the loop, and making a stochastic algorithm reproducible enough to debug
Every piece is built. This is the loop around them, the parallelism, and the thing that mattered more than any of it: making a stochastic algorithm repeat exactly.
Scoring a genome
// Evaluator scores a single genome by running its network.
//
// It is called concurrently for many genomes at once, so it must not write to
// shared state without synchronisation. Returning an error aborts the whole
// generation and the error is returned to the caller.
//
// The network is already compiled and may be activated as many times as the
// task needs; a genome that has to be driven through several steps of a game
// simply calls Activate in a loop.
type Evaluator func(ctx context.Context, net *network.Network) (float64, error)
One function. It gets a compiled network and returns a number, and everything else about your problem lives inside it.
Handing over a *network.Network rather than a Genome is deliberate: it means the library compiles, the evaluator cannot forget to, and it cannot accidentally compile per activation.
Running the population
workers := Workers(pop.Cfg.Parallelism, len(pop.Genomes))
wg.Add(workers)
for w := 0; w < workers; w++ {
go func() {
defer wg.Done()
for {
i := int(next.Add(1)) - 1
if i >= len(pop.Genomes) {
return
}
if err := ctx.Err(); err != nil {
fail(err)
return
}
net, err := pop.Genomes[i].CompileFor(pop.Cfg)
if err != nil {
fail(fmt.Errorf("%w: genome %d: %w", ErrCompile, i, err))
return
}
fitness, err := eval(ctx, net)
if err != nil {
fail(fmt.Errorf("%w: genome %d: %w", ErrEvaluate, i, err))
return
}
pop.GenomeFitness[i] = fitness
}
}()
}
wg.Wait()
Work is pulled off an atomic counter rather than split up front. By the end of a run, genome sizes vary a great deal - one species with a big topology, several small ones - and a static split leaves cores idle while one worker grinds through the large ones.
The first failure wins and cancels the rest:
fail := func(err error) {
failOnce.Do(func() {
failure = err
// Stop the other workers as soon as one of them fails.
cancel()
})
}
Measured on 16 logical cores, 150 genomes, 200 activations each:
workers=1 8.06 ms/generation
workers=2 4.50 ms 1.8x
workers=4 2.56 ms 3.1x
workers=8 2.00 ms 4.0x
workers=16 1.58 ms 5.1x
workers=unlimited 1.45 ms 5.6x
Not linear past eight, because the serial half of a generation - speciation, allocation, structural mutation - is not going anywhere.
Parallelism has three modes, and the third exists for a specific case:
0 one worker per CPU. Right for CPU-bound evaluators.
n exactly n.
Unlimited one goroutine per genome. For evaluators that block -
on a simulator, a subprocess, a network call.
An evaluator that spends its time waiting should not be limited to the number of cores, and one that spends its time computing should not have 150 goroutines fighting over 16.
The loop
func RunGeneration(ctx context.Context, pop Population, eval Evaluator) (Population, error) {
if err := Evaluate(ctx, pop, eval); err != nil {
return pop, err
}
return Advance(pop), nil
}
Split in two, because not every problem is one independent evaluator per genome:
// Advance produces the next generation from the fitnesses already in
// pop.GenomeFitness.
//
// RunGeneration is Evaluate followed by Advance. Call them separately when
// scoring cannot be expressed as one independent Evaluator per genome - a
// competitive tournament where genomes are played off against each other, for
// instance. Write each genome's score into pop.GenomeFitness by index, then
// hand the population here.
And Run is the loop with the stopping conditions, which insists you give it at least one:
if opts.MaxGenerations == 0 && opts.Solved == nil && opts.OnGeneration == nil && ctx.Done() == nil {
return pop, fmt.Errorf("%w: set MaxGenerations, Solved, OnGeneration or a cancellable context", ErrNoStopCondition)
}
// The population is always returned, including when the run ends early, so the
// best genome found so far is never lost to an error or a cancelled context.
Which is the least I can do for someone who has just had a four-hour run die on generation nine thousand.
When the evaluator returns nonsense
// sanitiseFitness replaces any non-finite fitness with a finite one: NaN and
// -Inf become the lowest finite fitness in the population, +Inf the highest.
//
// A non-finite fitness would otherwise propagate: shifting fitnesses to be
// non-negative turns a single infinity into an infinite range, which makes
// the offspring allocation produce garbage for every genome, not just the
// broken one.
One NaN from one genome poisons the entire allocation, so every species gets a nonsense share and the generation is wasted. Clamping it costs one pass and contains the damage to the genome that caused it.
The +Inf case is a judgement call worth stating:
// +Inf is kept at the top rather than sent to the bottom because
// an evaluator that returns it means "cannot be beaten", and turning that
// into the worst score in the population would silently invert the one
// result it was most sure of.
Reproducibility
Evolution is stochastic, which is not the same as unrepeatable. If a run cannot be repeated then a promising result cannot be studied and a rare crash cannot be bisected.
cfg.Seed = 12345
Leave it at zero and one is drawn and recorded on pop.Seed, so a run worth keeping can be replayed by feeding that value back.
The part that makes it hold up under parallelism:
// generationSeed derives a generation's random stream from the run's seed.
//
// Deriving it rather than letting one stream run on across generations means a
// generation's randomness depends only on the seed and the generation number.
// That is what lets a run be picked up from a snapshot and continue exactly as
// it would have: an uninterrupted run and a resumed one reach the same place.
func generationSeed(seed uint64, generation int) uint64 {
// splitmix64 finaliser, which scrambles even closely-related inputs.
x := seed + uint64(generation)*pcgStreamOffset
x ^= x >> 30
x *= 0xBF58476D1CE4E5B9
x ^= x >> 27
x *= 0x94D049BB133111EB
x ^= x >> 31
return x
}
run seed
|
+-- generation 0 stream -- slot seeds --> offspring
+-- generation 1 stream -- slot seeds --> offspring
+-- generation 2 stream -- slot seeds --> offspring
each derived, none carried on from the last
One stream running across all generations would work fine for an uninterrupted run and break the moment you resumed from a checkpoint, because the resumed run would have to reproduce the exact position of a generator that was never saved. Deriving per generation means generation twelve’s randomness is a function of the seed and the number twelve, and it does not matter how you got there.
Saving
Genomes are plain exported types, so a trained network needs no custom marshalling:
data, err := json.Marshal(pop.BestEverGenome)
// ... later, in another process ...
var genome neat.Genome
err = json.Unmarshal(data, &genome)
net, err := genome.Compile()
And a whole run in progress:
data, err := json.Marshal(pop.Snapshot())
// ... after a crash ...
var snapshot neat.Snapshot
err = json.Unmarshal(data, &snapshot)
pop, err := neat.Restore(snapshot)
// There is deliberately no random state here. A generation's randomness is
// derived from Seed and Generation, so a restored run continues exactly as the
// uninterrupted one would have.
What does have to be in there is the innovation registry. Restoring the genomes without it lets a later mutation issue a marking already in use, which is precisely what markings exist to prevent - and it fails silently.
That is the lot
Eleven posts and about two thousand lines. If I had to name the three things that mattered most:
- Historical markings. Everything else follows from them, and they are half a page of code.
- Speciation with a threshold that moves. A fixed threshold works beautifully for a hundred generations and then quietly stops working.
- Reproducibility. Not a feature - a tool. Every bug in this series was found by running the same seed twice and asking why the answers differed.
The things that went wrong were almost never the algorithm. They were a division applied twice, a floor measured from the wrong place, a multiplicative step that could not cross zero: small, invisible, and each one costing a few per cent of a result nobody had a baseline for.
If you want to see it pointed at something rather than built, I used it to play snake, where it beat every player I wrote by hand.