Genetic algorithm
Population -> fitness -> weighted selection -> crossover+mutation -> repeat, evolving a population of candidate solutions toward a target.
What it is
A genetic algorithm evaluates the fitness of each member of a population, builds a mating pool from that evaluation, and gives some individuals — not all — the chance to become parents; their genes cross, and the new population replaces the old before the loop repeats. It’s commonly shortened to GA. Nature of Code sets out to “walk through the steps of the classic GA in a more general way” before writing any implementation.
How it works
These excerpts cover four of the loop’s stages; initialization, mating-pool weighting, and mutation aren’t among them, so they’re left out rather than guessed.
- Fitness & mating pool. “Evaluate the fitness of each element of the population and build a mating pool.” Pool-weighting toward fitter individuals isn’t given here — see Roulette wheel selection.
- Select two parents for each new child: “There must be a mechanism by which some creatures have the opportunity to be parents and pass on their genetic information, while others don’t.”
- Crossover. “This implementation uses the random midpoint method of crossover, in which the first section of genes is taken from parent A and the second from parent B.”
- Replace & repeat. The book’s own step 4: “Replace the old population with the new population and return to step 2.”
Separately: “There must be a variety of traits present in the population of creatures or a means to introduce variation for evolution to take place.” No mechanism or rate for introducing variation appears here; mutation is the obvious candidate, but the word isn’t in these excerpts.
Parameters & tuning
- Crossover. The excerpts name this the random midpoint method of crossover: parent A supplies the first section of genes, parent B the second. Where the split point falls isn’t described here.
- What isn’t specified. No population size, mutation rate, or crossover rate appears in these excerpts. Don’t import a number from elsewhere and treat it as this source’s.
Where it’s been used
These excerpts don’t name a work that used this loop. The neighbours below diverge from it at different points — see Variants & neighbours.
Variants & neighbours
Interactive selection replaces a GA’s fitness function with fitness assigned by human observers (viewing time, clicks, ratings), keeping the same selection/reproduction loop.
Roulette wheel selection gives each member a slice of a wheel sized by normalized fitness, then samples it so fitter individuals are more likely, not certain — a candidate for the mating-pool-weighting gap above.
Continuous (steady-state) evolutionary ecosystem replaces the generational structure entirely — fitness becomes a creature’s lifespan, birth and death happen per frame, and dying removes it from ever reproducing rather than waiting for a batch replacement.
Go deeper
- natureofcode.com/genetic-algorithms — the source behind every quotation on this page.
Related, in brief
Roulette wheel selection
Give each population member a slice of a wheel sized by its normalized fitness, then sample so fitter elements are more likely, but not certain, to be chosen as parents.
Connected to
Variant of: Interactive selection
Built from: Roulette wheel selection
Variants: Continuous (steady-state) evolutionary ecosystem · Interactive selection
Steps: Roulette wheel selection
Try it yourself
The book gives two separate preconditions for evolution to do anything at all: variety of traits in the population, and unequal odds of reproducing. Suppose your population has plenty of trait variety, but every individual is equally likely to become a parent. What happens over many generations, and which precondition is missing?
Nothing improves, generation after generation. The population still has 'a variety of traits' — the book's other stated precondition — but the missing piece is 'a mechanism by which some creatures have the opportunity to be parents and pass on their genetic information, while others don't.' Without that mechanism, nothing biases who passes genes on, so variety alone doesn't produce improvement; selection does.