Genetic

Stable

Evolutionary optimization for Go simulations and games

Used by ViF and Stapes

GoConcurrencyAIGenetic Algorithms
GitHub

Genetic algorithms in Go on the standard library: a generational engine for scores known at once, and a steady-state engine for scores that come in long after a candidate is handed out, as in a game that is running.

  • A streaming engine for fitness that arrives late and out of order
  • A generational engine for candidates scored on demand
  • One set of operators for both, over any encoding
  • Several populations by id, metrics over a lifetime, and atomic save and load
  • A runnable example: two populations of landers that learn around each other

The streaming engine

A game knows how good a candidate was only when its run ends: an enemy’s controller is scored when the enemy dies, a lander’s when it lands, and runs end out of order. The streaming engine hands out proposals when the host asks and takes scores back whenever they come, with no batch to wait for.

Archive

Scored, sorted, fixed sizea candidate enters only above the tail, so elitism needs no setting

Breed

  1. Select tournament or roulette, from the archive alone
  2. Combine uniform or n-point crossover
  3. Perturb bounded Gaussian, clamped or reflected at the bounds; categorical for labels

Proposals

A ring of offspringunevaluated, first in first out; its depth sets how stale a proposal can be

Host

  1. Propose a genotype and its EvalID
  2. Evaluate anywhere, for as long as it takes, in any order: a flight, a match, a render
  3. CompleteEvaluation its score goes back to the archive; or abandon it
  4. Every MinOutcomesPerGen outcomes is a generation, and the ring refills
The generational Engine runs the same operators in a loop of its own: elites carried over, then selection, crossover and mutation, scored by a pool of workers.
Elitism
The archive admits a candidate only above its worst, so a good one is never displaced by a worse. SetEqual keeps one copy of a genotype at its latest score, which stops the archive filling with clones of its best and lets it follow an objective that changes.
In flight
An evaluation waits in one of eight slots of a table; a new one evicts the oldest only when all eight hold newer, and a late score for an evicted one is ignored. A host may drop evaluations it can no longer score.
Noise
An elitist archive keeps lucky outcomes. When another population is part of the objective, score a genotype by the mean of several runs; the lander example flies each four times.
Concurrency
One mutex and no goroutines or channels of its own. Stats is lock-free, safe to poll every frame.
Continuation
The same seed and calls give the same proposals. Checkpoint and Restore resume at the exact next proposal; Snapshot and Inject carry the archive alone, to re-score it when the world changes.

The generational engine

For a score known on demand: elites carried over, the rest bred by selection, crossover and mutation, scored by a pool of workers. The result does not depend on the number of workers, and a steady generation allocates nothing. Seeds open the first generation, a schedule such as the one-fifth rule tunes the mutation as it runs, and Memoize scores a genome once. Stapes uses it to fit a voice to a recording by ear and to compress a song’s bars into as few patterns as they allow.

Any encoding

A solution is any type the operators handle. Real vectors are the common case; bit patterns take a ten-line flip mutation, and an assignment of items to representatives, as bars to a dictionary’s patterns, is a list of integers under a categorical mutation.

Many populations

registry runs up to 256 populations by id, each its own streaming engine. SampleScout keeps every category of a decoded first gene under evaluation however far the archive has converged, and a stopped population still answers with its bounds’ midpoints, so a game can always spawn something. Metrics can accumulate over a lifetime and be scored when it ends, and archives save atomically. In the lander example, two populations of controllers fly toward one pad from opposite corners and learn around each other.