Genetic Algorithms

in reviewThis lesson is complete and being validated before release - details may still change.

Genetic algorithm

Loading interactive demo…

The grid is one generation: a row per genome, a column per item, a 1 where the genome takes the item. Each generation is scored, the fittest row is copied over untouched, tournaments of two pick the parents, a one-point cut splices each pair, and rare flips mutate the children. The strip beneath lists the items by weight and value, and the plot tracks the best fitness per generation against the exact optimum from the knapsack table. Tap a row to follow that individual.Take the tour, or press and explore. Legend:

The panel beside the stage is the real GeneticAlgorithm class from the published library executing in your browser, with the current line highlighted.

An item taken, tinted deeper the fitter its row.
An item left, and the item and row headers.
The elite row, and an item the shown genome takes.
A row over the capacity.
The rows a tournament drew.
The tournament winners, and the followed row.
The cut across the parents, and every flipped bit.

best is the fittest row's fitness over the table's optimum; weight is what that row carries over the capacity; mean is the generation's average fitness; flips counts the bits mutation flipped while breeding it; and generation is which one is on display. The plot's second line is the mean fitness of the finished run.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

A population instead of a walker. Simulated annealing moved one point and asked whether to accept each step. A genetic algorithm keeps $P$ candidates at once and breeds the next $P$ from them. Here a candidate is a genome of $n$ bits, one per knapsack item, and its fitness is

f(x) = \sum_i v_i x_i \;-\; \lambda \cdot \max\!\left(0,\; \sum_i w_i x_i - C\right)

the value packed, less a penalty of $\lambda$ per unit of weight over the capacity $C$ . The stage sets $\lambda$ to twice the best value per unit of weight among the items, rounded up, so dropping the excess always pays: an overweight genome scores below some genome that fits, and can score below zero. Nothing is repaired. Selection has to breed the overweight rows out, and the grid shows exactly what the operators produced.

Four operators, one generation. Scoring every genome costs $P$ evaluations of $n$ bits. Then:

Elitism. The fittest genome is copied untouched into the next generation. The best fitness is therefore non-decreasing in the generation count: whatever crossover and mutation do to the other rows, the plot's top line can hold or climb, never fall.
Tournament selection. Each parent is the fitter of two genomes drawn at random. A tournament only compares, so a negative fitness costs nothing. Roulette-wheel selection, which gives each genome a share of the wheel in proportion to its fitness, needs every fitness to be a positive share, and would have to shift or clip the penalised scores first.
One-point crossover. With probability $p_c$ the pair is cut at a point in $[1, n-1]$ and the tails are swapped: each child keeps one parent's head and the other's tail. At $p_c = 0$ nothing recombines.
Mutation. Every bit of every child flips with probability $p_m$ . It is the only operator that reaches a bit no parent carries. At $p_m = 0$ the population converges on copies of one genome; near $\tfrac{1}{2}$ every child is a coin toss and selection cannot keep what it found.

One generation is $O(Pn)$ for the scoring and the operators, so a run of $G$ generations costs $O(GPn)$ evaluations of the fitness, with $O(Pn)$ bits of memory for the two generations in play.

Measured against the exact answer. The knapsack lesson's table finds the optimum in $O(nC)$ , and this instance is small enough for that, so the best readout shows the search's fitness over the table's optimum. The default run reaches 40 of 40 at generation 14; the largest instance stops at 47 of 50. That is the honest shape of a meta-heuristic: no bound, no certificate, a good answer often and the best answer sometimes. Wolpert and Macready's No Free Lunch theorems (1997) say why no cleverness fixes this in general: averaged over all possible objective functions, every search algorithm performs the same, so a method is good only relative to a family of problems whose structure its operators happen to exploit. Crossover pays on knapsack because a good head and a good tail of a genome are good together; on a problem where bits interact across the whole string, the cut tears what it should keep.

How GeneticAlgorithm is written, and why (the code panel's comments and tracer checkboxes reveal the full published file):

Penalty over repair. score is the value less the penalty for the excess weight, and the constructor's defaultPenalty is ceil(2 * max value/weight). A repair step that drops items until the bag closes would hide what the operators produced; the penalty leaves every genome as bred and lets selection judge it.
A tournament of two. select draws GA_TOURNAMENT_SIZE indices with rng.index(P) and keeps the fitter, the lower index on a tie. Ties are decided by index, not by a second draw, so the trace is the same in Node and in the browser.
One cut in [1, n - 1]. crossover is static and throws on a cut of 0 or n, which would copy the parents and call it a cross. The run draws 1 + rng.index(n - 1) only when the pair is crossed, so an uncrossed pair consumes one random draw, not two.
The elite is a copy. next starts as [elite.slice()], and mutation runs over the children only; the elite's bits are never visited, so the best fitness cannot fall between evaluations.
An odd count of children. The pairs produce two children each, and P - 1 slots remain after the elite. When that is odd, the last pair's second child is dropped before it is mutated, so pairs = ceil((P - 1) / 2) and the flip draws match the children kept.
Genomes as strings in the trace. The payloads carry "10110010" rather than arrays, so the narration prints a genome as one word and the stage splits it back into bits; evaluate carries the arrays of fitness and weight for the whole generation at once.
history is G + 1 long. The first population is scored before any breeding, so the plot has a point at generation 0, and verdict reports the fittest genome of the last generation, not the best ever seen; with the elite those are the same.

Simulating evolution on a computer began in the 1950s with Nils Barricelli's experiments at the Institute for Advanced Study and Alex Fraser's simulations of artificial selection. It became an optimisation tool in the 1960s and 1970s: Ingo Rechenberg and Hans-Paul Schwefel evolved engineering designs in Berlin, and John Holland framed the genetic algorithm at Michigan, with the schema theorem to argue why selection, crossover, and mutation find good building blocks. His students carried it on: De Jong measured it on test functions, and Goldberg's 1989 book made it the textbook.

1954Nils Aall Barricelli - Runs computer simulations of evolution on the Institute for Advanced Study's machine; the publication is little noticed at the time.source
1957Alex Fraser - Begins a series of papers simulating the artificial selection of organisms with multiple loci controlling a measurable trait, the first genetic algorithms in all but name.source
1975John Holland - Publishes Adaptation in Natural and Artificial Systems, the book that popularised genetic algorithms, with the schema theorem predicting the quality of the next generation.source
1975Kenneth De Jong - Completes a PhD under Holland at the University of Michigan with a dissertation on genetic algorithms, An Analysis of the Behavior of a Class of Genetic Adaptive Systems.source
1989David E. Goldberg - Publishes Genetic Algorithms in Search, Optimization, and Machine Learning, translated into many languages and the field's most cited textbook.source

Used today

Scheduling and timetabling - A timetable or a job order is a genome; crossover recombines partial schedules and the penalty handles clashes, where an exact search is out of reach.
Antenna and circuit design - Shapes and component values evolve against a simulator's score, finding designs no hand would draw.
Hyperparameter and architecture search - Learning rates, layer counts, and connection patterns are bred against a validation score when the objective has no gradient.

Did you know

Evolution strategies, the European cousin of the genetic algorithm, were created in the early 1960s by Ingo Rechenberg and Hans-Paul Schwefel; the genetic algorithm page credits their work with making artificial evolution a widely recognised optimisation method.source
NASA's Space Technology 5 mission, launched in March 2006, flew an antenna whose complicated, asymmetric shape was found by an evolutionary design program rather than drawn by an engineer.source
John Koza, another of Holland's PhD students, patented a genetic algorithm for evolving programs in 1988, and his series of books from 1992 established genetic programming as its own field.source
The first commercial genetic algorithm product was a mainframe toolkit General Electric sold for industrial processes in the late 1980s; Evolver, the first for desktop computers, followed in 1989.source

bag

items8

pop8

gens20

cross0.9

flip0.10

best: 40 of 40
weight: 14 of 14
mean: 26.3
flips: 10
generation: 20 of 20

genetic-algorithm.ts

import { KnapsackProblem } from "../dynamic-programming/knapsack-problem";import { Mulberry32 } from "../random";import type { Tracer } from "../trace";/** The fewest genomes a population holds; two pairs, so selection has something to choose from. */export const GA_MIN_POPULATION = 4;/** The most genomes a population holds, so a generation's grid fits the stage. */export const GA_MAX_POPULATION = 10;/** The most generations one run breeds. */export const GA_MAX_GENERATIONS = 30;/** The tournament draws this many contestants per parent. */export const GA_TOURNAMENT_SIZE = 2;export interface GeneticOptions {  /** The knapsack instance the genomes choose from. */  problem: KnapsackProblem;  /** Seeds the first population and every later draw. */  seed: number;  /** Genomes per generation: even, in [GA_MIN_POPULATION, GA_MAX_POPULATION]. Default 8. */  population?: number;  /** Generations bred after the first: in [1, GA_MAX_GENERATIONS]. Default 20. */  generations?: number;  /** The chance a pair of parents is crossed rather than copied, in [0, 1]. Default 0.9. */  crossoverRate?: number;  /** The chance each bit of a child flips, in [0, 1]. Default 0.1. */  mutationRate?: number;  /** Fitness lost per unit of weight over the capacity; default ceil(2 * the best value per weight among the items). */  penalty?: number;}export interface GeneticResult {  /** The fittest genome of the last generation, one bit per item. */  readonly best: readonly number[];  /** Its fitness: value less the penalty for any weight over the capacity. */  readonly fitness: number;  /** Its total weight. */  readonly weight: number;  /** Its total value. */  readonly value: number;  /** The best fitness of every generation, the first population included: `generations + 1` entries. */  readonly history: readonly number[];  /** How many generations were bred. */  readonly generations: number;}/** A flipped bit: the genome's index in the new generation and the bit's position. */export type GeneticFlip = readonly [genome: number, bit: number];/** * A genetic algorithm over bit-string genomes, one bit per knapsack item: * a population of random choices is scored, and each generation breeds * the next from it. Two parents are picked by tournaments of two (a * random pair, the fitter wins), crossed at one random point with the * crossover rate (otherwise copied), and each bit of each child flips * with the mutation rate. The fittest genome is carried over unchanged * (the elite), so the best fitness never falls. A genome over the * capacity is not repaired: a linear penalty per unit of excess weight * makes it score below any choice that fits, so selection breeds it out * while the grid shows exactly what the operators produced. Fitness can * be negative, which is why selection is a tournament rather than a * roulette wheel. * * Time: O(G P n) for G generations, P genomes, n items. Space: O(P n). */export class GeneticAlgorithm {  readonly problem: KnapsackProblem;  readonly seed: number;  readonly population: number;  readonly generations: number;  readonly crossoverRate: number;  readonly mutationRate: number;  readonly penalty: number;  constructor(options: GeneticOptions, private readonly tracer?: Tracer) {    const { problem, seed, population = 8, generations = 20, crossoverRate = 0.9, mutationRate = 0.1 } = options;    if (!Number.isInteger(population) || population % 2 !== 0 || population < GA_MIN_POPULATION || population > GA_MAX_POPULATION) {      throw new RangeError(`population must be an even whole number in [${GA_MIN_POPULATION}, ${GA_MAX_POPULATION}]`);    }    if (!Number.isInteger(generations) || generations < 1 || generations > GA_MAX_GENERATIONS) throw new RangeError(`generations must be a whole number in [1, ${GA_MAX_GENERATIONS}]`);    if (!(crossoverRate >= 0 && crossoverRate <= 1)) throw new RangeError(`crossoverRate ${crossoverRate} must lie in [0, 1]`);    if (!(mutationRate >= 0 && mutationRate <= 1)) throw new RangeError(`mutationRate ${mutationRate} must lie in [0, 1]`);    const penalty = options.penalty ?? GeneticAlgorithm.defaultPenalty(problem);    if (!(penalty > 0) || !Number.isFinite(penalty)) throw new RangeError(`penalty ${penalty} must be positive`);    this.problem = problem;    this.seed = seed;    this.population = population;    this.generations = generations;    this.crossoverRate = crossoverRate;    this.mutationRate = mutationRate;    this.penalty = penalty;  }  /** The default penalty: twice the best value per unit of weight among the items, rounded up, so dropping the excess always pays. */  static defaultPenalty(problem: KnapsackProblem): number {    return Math.ceil(2 * Math.max(...problem.items.map((item) => item.value / item.weight)));  }  /** One-point crossover: the first `cut` bits of each parent with the rest of the other; `cut` in [1, n - 1]. */  static crossover(a: readonly number[], b: readonly number[], cut: number): [number[], number[]] {  static crossover(firstParent: readonly number[], secondParent: readonly number[], cut: number): [number[], number[]] {    if (a.length !== b.length) throw new RangeError("parents must have the same length");    if (firstParent.length !== secondParent.length) throw new RangeError("parents must have the same length");    if (!Number.isInteger(cut) || cut < 1 || cut > a.length - 1) throw new RangeError(`cut ${cut} must be a whole number in [1, ${a.length - 1}]`);    if (!Number.isInteger(cut) || cut < 1 || cut > firstParent.length - 1) throw new RangeError(`cut ${cut} must be a whole number in [1, ${a.length - 1}]`);    return [      [...a.slice(0, cut), ...b.slice(cut)],      [...firstParent.slice(0, cut), ...secondParent.slice(cut)],      [...b.slice(0, cut), ...a.slice(cut)],      [...secondParent.slice(0, cut), ...firstParent.slice(cut)],    ];  }  /** The fitness of a choice: its value, less the penalty for every unit of weight over the capacity. */  score(bits: readonly number[]): number {    const { weight, value } = this.problem.evaluate(bits);    return value - this.penalty * Math.max(0, weight - this.problem.capacity);  }  /** Breeds the generations from a seeded first population and reports the fittest genome of the last. */  run(): GeneticResult {    const rng = new Mulberry32(this.seed);    const random = new Mulberry32(this.seed);    const n = this.problem.size;    const itemCount = this.problem.size;    const P = this.population;    const populationSize = this.population;    let genomes: number[][] = Array.from({ length: P }, () => Array.from({ length: n }, () => rng.index(2)));    let genomes: number[][] = Array.from({ length: populationSize }, () => Array.from({ length: itemCount }, () => random.index(2)));    // ▸ the first population: one random bit per item for each genome, 1 to take the item and 0 to leave it    this.tracer?.emit("init", {      capacity: this.problem.capacity,      genomes: genomes.map(GeneticAlgorithm.text),      items: this.problem.items.map((item) => ({ name: item.name, value: item.value, weight: item.weight })),    });    const history: number[] = [];    let { best, fitness } = this.evaluate(genomes, 0);    history.push(fitness[best]!);    for (let generation = 0; generation < this.generations; generation++) {      const elite = genomes[best]!;      // ▸ the fittest genome is copied into the next generation untouched, so the best fitness can never fall      this.tracer?.emit("elite", { fitness: fitness[best]!, generation, genome: GeneticAlgorithm.text(elite), index: best });      const next: number[][] = [elite.slice()];      const flips: GeneticFlip[] = [];      for (let pair = 0; next.length < P; pair++) {      for (let pair = 0; next.length < populationSize; pair++) {        const parents = [this.select(genomes, fitness, rng), this.select(genomes, fitness, rng)] as const;        const parents = [this.select(genomes, fitness, random), this.select(genomes, fitness, random)] as const;        // ▸ a tournament of two for each parent: two genomes drawn at random, the fitter one wins        this.tracer?.emit("select", { generation, pair, parents: [parents[0].winner, parents[1].winner], picks: [...parents[0].picks, ...parents[1].picks] });        const a = genomes[parents[0].winner]!;        const firstParent = genomes[parents[0].winner]!;        const b = genomes[parents[1].winner]!;        const secondParent = genomes[parents[1].winner]!;        const crossed = rng.next() < this.crossoverRate;        const crossed = random.next() < this.crossoverRate;        const cut = crossed ? 1 + rng.index(n - 1) : 0;        const cut = crossed ? 1 + random.index(itemCount - 1) : 0;        const children = crossed ? GeneticAlgorithm.crossover(a, b, cut) : [a.slice(), b.slice()];        const children = crossed ? GeneticAlgorithm.crossover(firstParent, secondParent, cut) : [firstParent.slice(), secondParent.slice()];        // ▸ with the crossover rate, cut both parents at one random point and swap their tails; otherwise copy them        this.tracer?.emit("crossover", {          children: children.map(GeneticAlgorithm.text),          crossed,          cut,          generation,          pair,          parents: [GeneticAlgorithm.text(a), GeneticAlgorithm.text(b)],          parents: [GeneticAlgorithm.text(firstParent), GeneticAlgorithm.text(secondParent)],        });        // The last pair of an odd count of children yields one too many: the second is dropped before it is mutated.        for (const child of children) {          if (next.length === P) break;          if (next.length === populationSize) break;          const index = next.length;          for (let bit = 0; bit < n; bit++) {          for (let bit = 0; bit < itemCount; bit++) {            if (rng.next() < this.mutationRate) {            if (random.next() < this.mutationRate) {              child[bit] = 1 - child[bit]!;              flips.push([index, bit]);            }          }          next.push(child);        }      }      // ▸ every bit of every child flips with the mutation rate; the next generation is complete      this.tracer?.emit("mutate", { flips: flips.map((flip) => [...flip]), generation, genomes: next.map(GeneticAlgorithm.text) });      genomes = next;      ({ best, fitness } = this.evaluate(genomes, generation + 1));      history.push(fitness[best]!);    }    const winner = genomes[best]!;    const plan = this.problem.evaluate(winner);    // ▸ the fittest genome of the last generation, with its fitness and weight    this.tracer?.emit("verdict", { fitness: fitness[best]!, generation: this.generations, genome: GeneticAlgorithm.text(winner), weight: plan.weight });    return { best: winner.slice(), fitness: fitness[best]!, weight: plan.weight, value: plan.value, history, generations: this.generations };  }  /** Scores every genome of a generation; `best` is the fittest, the lowest index on a tie. */  private evaluate(genomes: readonly (readonly number[])[], generation: number): { best: number; fitness: number[] } {    const fitness = genomes.map((genome) => this.score(genome));    const weights = genomes.map((genome) => this.problem.weight(genome));    let best = 0;    fitness.forEach((value, index) => {      if (value > fitness[best]!) best = index;    });    // ▸ score every genome: its value, less the penalty for every unit of weight over the capacity; the fittest is the best    this.tracer?.emit("evaluate", { best, fitness: fitness.slice(), generation, weights });    return { best, fitness };  }  /** A tournament of two: two random genomes, the fitter wins, a tie goes to the lower index. */  private select(genomes: readonly (readonly number[])[], fitness: readonly number[], rng: Mulberry32): { winner: number; picks: number[] } {  private select(genomes: readonly (readonly number[])[], fitness: readonly number[], random: Mulberry32): { winner: number; picks: number[] } {    const picks = Array.from({ length: GA_TOURNAMENT_SIZE }, () => rng.index(genomes.length));    const picks = Array.from({ length: GA_TOURNAMENT_SIZE }, () => random.index(genomes.length));    let winner = picks[0]!;    for (const pick of picks) {      if (fitness[pick]! > fitness[winner]! || (fitness[pick] === fitness[winner] && pick < winner)) winner = pick;    }    return { winner, picks };  }  private static text(bits: readonly number[]): string {    return bits.join("");  }}

generation =: 20
genome =: 01011011
fitness =: 40
weight =: 14
optimum =: 40

The run ends with 01011011 at fitness 40 and weight 14: exactly the table's optimum. The dynamic programming table is the exact answer the search is measured against.

import { KnapsackProblem } from "../dynamic-programming/knapsack-problem";import { Mulberry32 } from "../random";import type { Tracer } from "../trace";/** The fewest genomes a population holds; two pairs, so selection has something to choose from. */export const GA_MIN_POPULATION = 4;/** The most genomes a population holds, so a generation's grid fits the stage. */export const GA_MAX_POPULATION = 10;/** The most generations one run breeds. */export const GA_MAX_GENERATIONS = 30;/** The tournament draws this many contestants per parent. */export const GA_TOURNAMENT_SIZE = 2;export interface GeneticOptions { /** The knapsack instance the genomes choose from. */ problem: KnapsackProblem; /** Seeds the first population and every later draw. */ seed: number; /** Genomes per generation: even, in [GA_MIN_POPULATION, GA_MAX_POPULATION]. Default 8. */ population?: number; /** Generations bred after the first: in [1, GA_MAX_GENERATIONS]. Default 20. */ generations?: number; /** The chance a pair of parents is crossed rather than copied, in [0, 1]. Default 0.9. */ crossoverRate?: number; /** The chance each bit of a child flips, in [0, 1]. Default 0.1. */ mutationRate?: number; /** Fitness lost per unit of weight over the capacity; default ceil(2 * the best value per weight among the items). */ penalty?: number;}export interface GeneticResult { /** The fittest genome of the last generation, one bit per item. */ readonly best: readonly number[]; /** Its fitness: value less the penalty for any weight over the capacity. */ readonly fitness: number; /** Its total weight. */ readonly weight: number; /** Its total value. */ readonly value: number; /** The best fitness of every generation, the first population included: `generations + 1` entries. */ readonly history: readonly number[]; /** How many generations were bred. */ readonly generations: number;}/** A flipped bit: the genome's index in the new generation and the bit's position. */export type GeneticFlip = readonly [genome: number, bit: number];/** * A genetic algorithm over bit-string genomes, one bit per knapsack item: * a population of random choices is scored, and each generation breeds * the next from it. Two parents are picked by tournaments of two (a * random pair, the fitter wins), crossed at one random point with the * crossover rate (otherwise copied), and each bit of each child flips * with the mutation rate. The fittest genome is carried over unchanged * (the elite), so the best fitness never falls. A genome over the * capacity is not repaired: a linear penalty per unit of excess weight * makes it score below any choice that fits, so selection breeds it out * while the grid shows exactly what the operators produced. Fitness can * be negative, which is why selection is a tournament rather than a * roulette wheel. * * Time: O(G P n) for G generations, P genomes, n items. Space: O(P n). */export class GeneticAlgorithm { readonly problem: KnapsackProblem; readonly seed: number; readonly population: number; readonly generations: number; readonly crossoverRate: number; readonly mutationRate: number; readonly penalty: number; constructor(options: GeneticOptions, private readonly tracer?: Tracer) { const { problem, seed, population = 8, generations = 20, crossoverRate = 0.9, mutationRate = 0.1 } = options; if (!Number.isInteger(population) || population % 2 !== 0 || population < GA_MIN_POPULATION || population > GA_MAX_POPULATION) { throw new RangeError(`population must be an even whole number in [${GA_MIN_POPULATION}, ${GA_MAX_POPULATION}]`); } if (!Number.isInteger(generations) || generations < 1 || generations > GA_MAX_GENERATIONS) throw new RangeError(`generations must be a whole number in [1, ${GA_MAX_GENERATIONS}]`); if (!(crossoverRate >= 0 && crossoverRate <= 1)) throw new RangeError(`crossoverRate ${crossoverRate} must lie in [0, 1]`); if (!(mutationRate >= 0 && mutationRate <= 1)) throw new RangeError(`mutationRate ${mutationRate} must lie in [0, 1]`); const penalty = options.penalty ?? GeneticAlgorithm.defaultPenalty(problem); if (!(penalty > 0) || !Number.isFinite(penalty)) throw new RangeError(`penalty ${penalty} must be positive`); this.problem = problem; this.seed = seed; this.population = population; this.generations = generations; this.crossoverRate = crossoverRate; this.mutationRate = mutationRate; this.penalty = penalty; } /** The default penalty: twice the best value per unit of weight among the items, rounded up, so dropping the excess always pays. */ static defaultPenalty(problem: KnapsackProblem): number { return Math.ceil(2 * Math.max(...problem.items.map((item) => item.value / item.weight))); } /** One-point crossover: the first `cut` bits of each parent with the rest of the other; `cut` in [1, n - 1]. */ static crossover(a: readonly number[], b: readonly number[], cut: number): [number[], number[]] { static crossover(firstParent: readonly number[], secondParent: readonly number[], cut: number): [number[], number[]] { if (a.length !== b.length) throw new RangeError("parents must have the same length"); if (firstParent.length !== secondParent.length) throw new RangeError("parents must have the same length"); if (!Number.isInteger(cut) || cut < 1 || cut > a.length - 1) throw new RangeError(`cut ${cut} must be a whole number in [1, ${a.length - 1}]`); if (!Number.isInteger(cut) || cut < 1 || cut > firstParent.length - 1) throw new RangeError(`cut ${cut} must be a whole number in [1, ${a.length - 1}]`); return [ [...a.slice(0, cut), ...b.slice(cut)], [...firstParent.slice(0, cut), ...secondParent.slice(cut)], [...b.slice(0, cut), ...a.slice(cut)], [...secondParent.slice(0, cut), ...firstParent.slice(cut)], ]; } /** The fitness of a choice: its value, less the penalty for every unit of weight over the capacity. */ score(bits: readonly number[]): number { const { weight, value } = this.problem.evaluate(bits); return value - this.penalty * Math.max(0, weight - this.problem.capacity); } /** Breeds the generations from a seeded first population and reports the fittest genome of the last. */ run(): GeneticResult { const rng = new Mulberry32(this.seed); const random = new Mulberry32(this.seed); const n = this.problem.size; const itemCount = this.problem.size; const P = this.population; const populationSize = this.population; let genomes: number[][] = Array.from({ length: P }, () => Array.from({ length: n }, () => rng.index(2))); let genomes: number[][] = Array.from({ length: populationSize }, () => Array.from({ length: itemCount }, () => random.index(2))); // ▸ the first population: one random bit per item for each genome, 1 to take the item and 0 to leave it this.tracer?.emit("init", { capacity: this.problem.capacity, genomes: genomes.map(GeneticAlgorithm.text), items: this.problem.items.map((item) => ({ name: item.name, value: item.value, weight: item.weight })), }); const history: number[] = []; let { best, fitness } = this.evaluate(genomes, 0); history.push(fitness[best]!); for (let generation = 0; generation < this.generations; generation++) { const elite = genomes[best]!; // ▸ the fittest genome is copied into the next generation untouched, so the best fitness can never fall this.tracer?.emit("elite", { fitness: fitness[best]!, generation, genome: GeneticAlgorithm.text(elite), index: best }); const next: number[][] = [elite.slice()]; const flips: GeneticFlip[] = []; for (let pair = 0; next.length < P; pair++) { for (let pair = 0; next.length < populationSize; pair++) { const parents = [this.select(genomes, fitness, rng), this.select(genomes, fitness, rng)] as const; const parents = [this.select(genomes, fitness, random), this.select(genomes, fitness, random)] as const; // ▸ a tournament of two for each parent: two genomes drawn at random, the fitter one wins this.tracer?.emit("select", { generation, pair, parents: [parents[0].winner, parents[1].winner], picks: [...parents[0].picks, ...parents[1].picks] }); const a = genomes[parents[0].winner]!; const firstParent = genomes[parents[0].winner]!; const b = genomes[parents[1].winner]!; const secondParent = genomes[parents[1].winner]!; const crossed = rng.next() < this.crossoverRate; const crossed = random.next() < this.crossoverRate; const cut = crossed ? 1 + rng.index(n - 1) : 0; const cut = crossed ? 1 + random.index(itemCount - 1) : 0; const children = crossed ? GeneticAlgorithm.crossover(a, b, cut) : [a.slice(), b.slice()]; const children = crossed ? GeneticAlgorithm.crossover(firstParent, secondParent, cut) : [firstParent.slice(), secondParent.slice()]; // ▸ with the crossover rate, cut both parents at one random point and swap their tails; otherwise copy them this.tracer?.emit("crossover", { children: children.map(GeneticAlgorithm.text), crossed, cut, generation, pair, parents: [GeneticAlgorithm.text(a), GeneticAlgorithm.text(b)], parents: [GeneticAlgorithm.text(firstParent), GeneticAlgorithm.text(secondParent)], }); // The last pair of an odd count of children yields one too many: the second is dropped before it is mutated. for (const child of children) { if (next.length === P) break; if (next.length === populationSize) break; const index = next.length; for (let bit = 0; bit < n; bit++) { for (let bit = 0; bit < itemCount; bit++) { if (rng.next() < this.mutationRate) { if (random.next() < this.mutationRate) { child[bit] = 1 - child[bit]!; flips.push([index, bit]); } } next.push(child); } } // ▸ every bit of every child flips with the mutation rate; the next generation is complete this.tracer?.emit("mutate", { flips: flips.map((flip) => [...flip]), generation, genomes: next.map(GeneticAlgorithm.text) }); genomes = next; ({ best, fitness } = this.evaluate(genomes, generation + 1)); history.push(fitness[best]!); } const winner = genomes[best]!; const plan = this.problem.evaluate(winner); // ▸ the fittest genome of the last generation, with its fitness and weight this.tracer?.emit("verdict", { fitness: fitness[best]!, generation: this.generations, genome: GeneticAlgorithm.text(winner), weight: plan.weight }); return { best: winner.slice(), fitness: fitness[best]!, weight: plan.weight, value: plan.value, history, generations: this.generations }; } /** Scores every genome of a generation; `best` is the fittest, the lowest index on a tie. */ private evaluate(genomes: readonly (readonly number[])[], generation: number): { best: number; fitness: number[] } { const fitness = genomes.map((genome) => this.score(genome)); const weights = genomes.map((genome) => this.problem.weight(genome)); let best = 0; fitness.forEach((value, index) => { if (value > fitness[best]!) best = index; }); // ▸ score every genome: its value, less the penalty for every unit of weight over the capacity; the fittest is the best this.tracer?.emit("evaluate", { best, fitness: fitness.slice(), generation, weights }); return { best, fitness }; } /** A tournament of two: two random genomes, the fitter wins, a tie goes to the lower index. */ private select(genomes: readonly (readonly number[])[], fitness: readonly number[], rng: Mulberry32): { winner: number; picks: number[] } { private select(genomes: readonly (readonly number[])[], fitness: readonly number[], random: Mulberry32): { winner: number; picks: number[] } { const picks = Array.from({ length: GA_TOURNAMENT_SIZE }, () => rng.index(genomes.length)); const picks = Array.from({ length: GA_TOURNAMENT_SIZE }, () => random.index(genomes.length)); let winner = picks[0]!; for (const pick of picks) { if (fitness[pick]! > fitness[winner]! || (fitness[pick] === fitness[winner] && pick < winner)) winner = pick; } return { winner, picks }; } private static text(bits: readonly number[]): string { return bits.join(""); }}