Genetic Algorithms
Introduction
A genetic algorithm (GA) is a population-based optimization method inspired by biological evolution. Instead of following a gradient downhill, it keeps a whole population of candidate solutions and lets natural selection do the searching: the fitter candidates are more likely to reproduce, their traits are recombined and randomly perturbed, and over many generations the population drifts toward better and better solutions.
GAs belong to the family of evolutionary algorithms. The headline appeal is that they treat the objective as a black box: you only need to be able to score a candidate solution. You never need derivatives, a smooth function, or even a continuous search space. That makes them a go-to tool for messy, non-differentiable, and combinatorial problems where gradient descent simply cannot be applied.
The core analogy: a candidate solution is an organism; its encoded parameters are its chromosome / genotype; how good it is at the task is its fitness. Breed the fit ones, mutate occasionally, repeat. Evolution is a remarkably general optimizer.
The building blocks
Before the loop makes sense, three pieces of vocabulary must be nailed down.
Genotype / chromosome (the encoding)
A chromosome is how you encode one candidate solution as something the GA can manipulate — typically a fixed-length string of genes. Common encodings: a bit-string (e.g. 1011001 for a knapsack: which items to pack), a vector of real numbers (parameters of a model), or a permutation (a tour for the traveling-salesman problem). The encoding is a genuine design decision — it determines what crossover and mutation actually do.
Fitness function (the objective)
The fitness function f(chromosome) → ℝ maps a candidate to a single number measuring how good it is, where higher is better. It is the only thing the GA knows about your problem. It can be any computable score — an analytic formula, the result of a simulation, the accuracy of a model, or the outcome of a game. It need not be differentiable or even continuous.
Population (the search frontier)
Rather than tracking a single point like gradient descent, a GA maintains a population of many chromosomes at once. This parallel exploration is what lets a GA cover a rugged landscape with many peaks and avoid betting everything on one starting point.
The GA loop
Every genetic algorithm is the same loop. One pass through it produces one new generation.
1. Selection — who gets to reproduce
Selection biases reproduction toward fitter individuals. Two classic schemes:
- Fitness-proportionate (roulette wheel): an individual is chosen with probability pᵢ = fᵢ / Σⱼ fⱼ — its slice of a roulette wheel is proportional to its fitness. (This needs non-negative fitness values.)
- Tournament selection: pick k random individuals and keep the fittest of them. Larger k means stronger selection pressure. It is simple, robust, and does not care about the absolute scale of fitness — which is why the demo below uses it.
2. Crossover — recombining two parents
Crossover (recombination) mixes the genes of two selected parents to build a child, exploiting good sub-solutions discovered separately. For a bit-string, single-point crossover cuts both parents at a random position and swaps the tails (e.g. 11|0010 + 00|1101 → 11|1101). For real-valued genes, a common choice is a blend: child = α·p₁ + (1−α)·p₂ with random α ∈ [0, 1] (used in the demo). Crossover is the main exploitation operator: it combines what already works.
3. Mutation — random perturbation for exploration
Mutation randomly tweaks a child with small probability: flip a bit, or add a little gaussian noise to a real gene. Its job is exploration — injecting new genetic material so the population does not collapse onto one point and lose diversity. Without mutation, a GA can only shuffle the genes it started with and will stall in a local optimum. The mutation rate is the key knob controlling how much fresh variation enters each generation.
4. Elitism — do not lose your best
Because crossover and mutation are random, the next generation can accidentally be worse than the current one. Elitism copies the top few individuals into the next generation unchanged, guaranteeing the best-so-far fitness never decreases. It is a cheap, near-universal addition. Toggle it off in the demo (with high mutation) to watch the best score wobble downward.
Interactive demo: evolution in action
Below, each blue dot is one individual whose single gene is a value x ∈ [0, 10]. We are maximizing the purple fitness curve f(x), which has a deceptive local peak near x ≈ 2 and the true global peak near x ≈ 7.4. Selection, crossover, and mutation all run as real JavaScript each generation. Press Evolve 1 generation to step, or Auto-run to watch the cloud of dots crawl uphill while the lower chart plots best and average fitness climbing.
Controls
0 = no exploration (can get stuck on the local peak). High = noisy, never settles.
k = 1 is random drift. Higher k means only the very fittest reproduce (greedy).
Things to try
- Set mutation σ to 0 and auto-run: the swarm often gets trapped on the orange local peak.
- Raise mutation high (~1.0): best fitness stays jittery and never locks on.
- Turn off elitism with high mutation: the best can actually get worse.
Watch the tension between exploration and exploitation: strong selection pressure plus low mutation converges fast but can be fooled into the local peak; high mutation keeps exploring but never settles. Good GAs balance the two.
Exploration vs. exploitation
Every optimizer faces this trade-off. Exploitation means refining the good solutions you have already found; exploration means searching new regions in case something better is out there. In a GA the operators map cleanly onto the two:
| Lever | Pushes toward | If overdone |
|---|---|---|
| High mutation rate | Exploration (diversity) | Random search; good solutions are lost to noise |
| Low / zero mutation | Exploitation | Premature convergence to a local optimum |
| High selection pressure (large k) | Exploitation (greedy) | Diversity collapses early; stuck on a peak |
| Large population | Exploration (more peaks covered) | More fitness evaluations per generation (slower) |
Premature convergence is the classic GA failure mode: selection pressure squeezes all diversity out of the population before it has found the global optimum, and with too little mutation there is no way back out. The mutation rate is the primary defense.
GA vs. gradient descent
GAs and gradient descent solve the same kind of problem — find parameters that optimize an objective — but make opposite assumptions about what you can compute.
| Genetic algorithm | Gradient descent | |
|---|---|---|
| Needs gradients? | No — only a fitness score (black box) | Yes — needs ∇f (differentiable objective) |
| What it tracks | A whole population of candidates | A single point moved by −η∇f |
| Search space | Continuous, discrete, or combinatorial | Continuous / differentiable only |
| Local optima | Population + mutation help escape them | Can get stuck (mitigated by momentum, restarts) |
| Cost / efficiency | Many fitness evals; no gradient info ⇒ slow | Gradient gives direction ⇒ fast when applicable |
| Result | Stochastic; no convergence guarantee | Converges to a (local) optimum on convex/smooth f |
When to reach for a GA — and when not to
Good fit
- • Black-box objectives — you can only score solutions, not differentiate them
- • Non-differentiable or discontinuous fitness (simulations, game outcomes)
- • Combinatorial problems — scheduling, routing, layout, feature selection
- • Rugged, multi-modal landscapes with many local optima
- • Mixed discrete/continuous parameters that other methods handle awkwardly
- • Multi-objective search (a population can approximate a Pareto front)
Poor fit / costs
- • The objective is differentiable — gradient descent will be far faster
- • Each fitness evaluation is expensive (GAs need many of them)
- • You need a provable optimum or convergence guarantee
- • Tuning many hyperparameters (population, rates, operators) can be fiddly
- • High-dimensional smooth problems where neural-net-style training shines
In practice GAs appear in hyperparameter and architecture search, antenna and circuit design, game-playing and procedural content, scheduling and timetabling, and as a baseline for any optimization where you can score a candidate but cannot take a derivative.
Key Takeaways
- A genetic algorithm is population-based, derivative-free optimization modeled on natural selection.
- A chromosome encodes one candidate solution; a fitness function scores it (higher is better).
- The loop is: initialize → evaluate → selection → crossover → mutation → next generation → repeat.
- Selection (roulette / tournament) biases reproduction toward fit individuals; crossover recombines two parents; mutation injects random variation.
- Crossover exploits known-good genes; mutation explores. Their balance is the central tuning problem, and the mutation rate is the main knob.
- Elitism carries the best individuals forward so the best fitness never regresses.
- Too little mutation or too much selection pressure causes premature convergence to a local optimum; too much mutation degenerates into random search.
- Use GAs for black-box, non-differentiable, combinatorial, or rugged problems — but expect them to need many fitness evaluations and offer no convergence guarantee. If you have gradients, prefer gradient descent.