Selection
Fitness sharing, culling, and four places where an obvious-looking division is wrong
Species exist so that a genome competes mainly against genomes like itself. This is the part that cashes that in: deciding how many offspring each species gets, which members are allowed to produce them, and which species do not get to continue at all.
It is five short functions and I got three of them subtly wrong first.
pop = Speciate(pop)
pop = AdjustCompatThreshold(pop)
pop = RankSpecies(pop)
pop = FitnessSharing(pop)
pop = KillStaleSpecies(pop)
pop = CullSpecies(pop)
pop = Evolve(pop)
Fitness sharing
// FitnessSharing computes each genome's adjusted fitness: its raw fitness
// divided by the size of its species.
//
// Sharing is what stops a single successful topology from swamping the
// population. Offspring go to a species in proportion to the sum of its
// members' adjusted fitness, which is its mean raw fitness: a species twice
// the size earns no more for it, and has to be fitter per member to grow.
A genome in a species of forty is worth a fortieth of its raw fitness. So a species does not earn more offspring simply for being big - it has to be better per member.
Then the trap:
// The sum is what the paper allocates by. Dividing it by the size again, to get
// a mean of the adjusted values, penalises size twice over: a species then
// loses offspring for having grown, shrinks, wins them back, and the
// population oscillates between species instead of settling where the
// fitness says it should.
Sum of raw/size over size members is already the mean. Taking the mean of that divides by size a second time, and the result is a control loop with the sign of a see-saw: the species that did well last generation grows, is penalised for having grown, shrinks, is rewarded for being small, grows again. Fitness has stopped deciding anything.
// The raw fitness is left untouched so that reporting and best-genome
// tracking stay honest.
Two fitness arrays, not one. GenomeFitness is what the evaluator said; GenomeAdjustedFitness is what selection uses. Overwriting the raw one would make every progress line report a number that drops whenever a species grows.
Ranking
// Species are ranked by the fitness of their best current member, which is
// what the rank is used for: deciding which species are doing well enough now
// to be protected from being culled as stale, and which breed first when the
// population is topped up. Ranking by the best a species has ever produced
// would keep a species whose members have since scattered to other species,
// or been overtaken, at the top for the rest of the run on the strength of
// one ancestor.
Best current member. BestFitness - the best a species ever managed - exists for staleness, and using it for ranking too is an easy mistake that gives a long-dead species tenure.
// Both sorts are stable, so equally fit genomes keep their index order and
// equally fit species their existing order. Which of two tied genomes is the
// elite decides what the next generation is built from, so it must follow from
// the population and not from which sort algorithm happened to be in use.
Ties are common - two elites carried over untouched score identically - and with an unstable sort, which of them becomes the elite depends on the sort implementation. A run would then stop being reproducible for reasons nothing in the algorithm can see.
Culling
// CullSpecies removes the least fit members of each species so that only the
// top SurvivalThreshold fraction may reproduce. At least two members are kept
// where possible so that crossover still has two parents to work with.
func CullSpecies(pop Population) Population {
for i, species := range pop.Species {
keep := int(math.Ceil(pop.Cfg.SurvivalThreshold * float64(len(species.Genomes))))
if keep < 2 {
keep = 2
}
if keep > len(species.Genomes) {
keep = len(species.Genomes)
}
pop.Species[i].Genomes = species.Genomes[:keep]
}
return pop
}
SurvivalThreshold: .2,
The bottom 80% of every species does not breed. The floor of two is what keeps crossover possible; a species cut to one member can only clone.
Killing stale species
// KillStaleSpecies removes species that have not improved for
// SpeciesStalenessThreshold generations, always keeping the SpeciesElitism
// fittest species alive. If every species is stale the elitism floor is what
// stops the population from going extinct.
SpeciesElitism: 2,
SpeciesStalenessThreshold: 20,
Twenty generations without a personal best and a species is done - unless it is one of the two fittest, which are never culled for staleness. Late in a run everything is stale, because everything has plateaued, and without that floor the whole population would be removed in one generation.
Handing out the offspring
This is the fiddliest function in the library.
// getDesiredOffspringCount allocates the whole population across the species in
// proportion to their adjusted fitness.
//
// The allocation is exact: largest-remainder rounding distributes the leftover
// slots, so the population size never drifts.
Proportional allocation gives fractional shares - 43.7 offspring - and the fractions have to go somewhere. Truncating loses several genomes a generation and the population quietly shrinks; rounding each independently can overshoot. Largest-remainder rounding hands out the floors first and then the leftover slots to whoever was cheated most:
species exact floor remainder +1? final
A 43.7 43 .7 yes 44
B 38.2 38 .2 38
C 41.5 41 .5 yes 42
D 26.6 26 .6 yes 27
--- ---
148 4 to give 151 -> exactly 150 after
the population guard
Then the shift, which is the third subtle division:
// Fitnesses are shifted so that the worst genome in the population sits at
// zero, because a fitness function that returns negative values would
// otherwise produce negative or nonsensical shares. Shifting by the worst
// genome rather than the worst species means a species only gets nothing when
// every member of it is as bad as the population's worst; shifting by the
// worst species would hand the second best of two species the minimum
// allowance no matter how close it was.
With two species scoring 100.0 and 99.9, shifting by the worst species makes their shares 0.1 and 0.0 - the second gets nothing, despite being within a tenth of a per cent. Shifting by the worst genome keeps the ratio close to 1:1, which is what the fitnesses actually say.
There is an epsilon floor on top of that, so that a species which is merely the worst is not instantly wiped out, and a MinSpeciesSize afterwards, with the extra slots clawed back from the largest allocations so the total still comes out right.
Choosing parents
// selectParents picks two parents from the species' surviving members by
// roulette over their fitness.
//
// Fitness is measured from the worst genome in the whole population, the same
// floor the offspring allocation uses, so that every survivor has a share
// unless it is as bad as the population's worst. Measuring from the worst
// survivor instead, as this once did, gives that survivor no share at all -
// and a species cut down to two members, the most common size late in a run,
// then only ever mates its best with itself. Its crossover is a clone, and the
// second parent the cull kept for it is never used.
That is my favourite bug in the whole library, because everything about it looks correct. Roulette over fitness - worst survivor is textbook. But the worst survivor’s share is exactly zero, so it is never picked - and with two survivors, the fitter one is drawn twice, crossover produces a clone of it, and the careful floor of two in CullSpecies has been doing nothing at all for most of the run.
Nothing errors. The run is just worse than it should be, in a way that gets more pronounced the more species there are.
// Picking uniformly among survivors, as some implementations do, was tried
// and is measurably slower to find a solution: the cull alone applies too
// little pressure within a species.
Worth knowing, because uniform selection is a perfectly defensible design - the cull has already thrown away the bottom 80%, so why apply pressure twice? Measured, it loses.
The pattern
Four of the five things in this post are a division or a subtraction with an obvious-looking wrong version:
- divide the shared fitness by the size again, and the population oscillates;
- rank by best-ever instead of best-now, and dead species keep tenure;
- shift by the worst survivor instead of the worst genome, and a two-member species stops crossing over;
- take the mean instead of the sum, and size is penalised twice.
None of them crashes. None of them is visible in a progress line. They make the algorithm quietly worse, which is the failure mode this entire family of algorithms specialises in.
Next: actually making the next generation.