Local search

Genetic Algorithm

Evolve a crowd of guesses until the fittest survives.

Interactive demo coming soon — read the theory below

The idea

A Genetic Algorithm (GA) borrows ideas from biological evolution to search for good solutions. Instead of improving one guess, it keeps a whole "population" of candidate solutions and lets them evolve over many rounds (generations). Each round it keeps the better ones, mixes pairs together (crossover), and randomly tweaks some (mutation), scoring everyone with a "fitness function." Over time the population drifts toward strong solutions. It is great for huge, bumpy search spaces, but it is random and never guarantees the best possible answer.

How it works

Represent each candidate solution as a 'chromosome', a simple encoded form like a string of bits or numbers (this encoding is called the genotype).
Create an initial population: generate many random chromosomes to start with.
Evaluate fitness: run the fitness function on every individual to score how good its solution is.
Selection: pick parents for the next generation, giving fitter individuals a higher chance of being chosen (e.g. tournament or roulette-wheel selection).
Crossover: pair up parents and combine their chromosomes to produce children that inherit pieces from both.
Mutation: with a small probability, randomly tweak a gene in a child to inject fresh variety and avoid getting stuck.
Form the new generation from the children (often keeping a few top performers unchanged, called elitism), then repeat from the evaluate step.
Stop when you hit a generation limit, a good-enough fitness, or the population stops improving; return the best individual ever seen.

OPEN, CLOSED & the data structures

A population: a collection (array) of individuals. Each individual is a chromosome (encoded candidate solution, e.g. a bit string or list of numbers) paired with its fitness score. Global state also tracks the current generation number and the best-so-far individual found across all generations. Tunable parameters live alongside: population size, crossover rate, mutation rate, and selection method.

Pseudocode

function GeneticAlgorithm(fitness):
    population = create_random_population(POP_SIZE)
    best = fittest_of(population, fitness)
    for generation in 1..MAX_GENERATIONS:
        scored = evaluate(population, fitness)
        best = better_of(best, fittest_of(scored))
        if good_enough(best): break
        next_gen = keep_elites(scored)        # optional elitism
        while size(next_gen) < POP_SIZE:
            parent1 = select(scored)          # fitter = more likely
            parent2 = select(scored)
            child = crossover(parent1, parent2)
            child = mutate(child, MUTATION_RATE)
            add child to next_gen
        population = next_gen
    return best

At a glance

Complete?Not guaranteed complete. It is stochastic (driven by randomness) and explores only a sample of the space, so it may never visit a valid solution even if one exists. In practice it reliably finds good solutions in large spaces, but "found something" is never guaranteed within a fixed run.

Optimal?Not optimal. A GA does not guarantee the global optimum (the single best possible solution). Randomness plus finite generations mean it can converge on a strong-but-imperfect answer. You improve your odds with bigger populations, more generations, and good mutation, but there is no optimality promise.

TimeRoughly O(generations x population size x cost-of-one-fitness-evaluation). The fitness function is usually the dominant cost. No tight bound on generations to reach a good answer, it is set by you (the budget), not derived.

SpaceO(population size x chromosome length), since it holds a whole population in memory at once (typically two generations during breeding). Modest and does not grow with the number of generations.

👍 When to use it

The search space is huge and rugged (many peaks and valleys) where systematic search is too slow.
You can score a solution's quality with a fitness function but cannot easily compute the best answer directly.
The problem has no usable gradient or clean mathematical structure to exploit (e.g. scheduling, route design, tuning many parameters).
A 'good enough' solution found in reasonable time is more valuable than a guaranteed-perfect one.
Solutions can be naturally encoded as strings, lists, or vectors that are easy to combine and mutate.

⚠️ Watch out for

Premature convergence: the population can collapse onto one mediocre solution too early; keep enough diversity (mutation, larger population).
Parameter sensitivity: results depend heavily on population size, mutation rate, and crossover rate, expect to tune them.
Fitness function is everything: a poorly designed fitness function guides evolution toward the wrong goal.
It is not optimal or repeatable: different runs give different answers because of randomness (set a seed if you need reproducibility).
Costly evaluations: if scoring one candidate is expensive, running many individuals over many generations can be slow.
Encoding matters: a bad chromosome representation makes crossover and mutation produce mostly broken or invalid solutions.