Definition
Nature never designed a cheetah on paper. Over many generations, faster animals survived and passed on their traits, with small random changes along the way. Genetic algorithms borrow this idea to solve problems where the number of possible answers is far too large to check one by one.
A genetic algorithm (GA) is a search method inspired by natural evolution. It keeps a population of candidate solutions, each encoded as a chromosome such as a string of bits. A fitness function scores each candidate. In every generation, fitter candidates are more likely to be selected as parents; crossover combines parts of two parents to make children; and mutation randomly changes a few genes to keep variety. Over many generations the population tends to improve. GAs are useful for optimisation problems such as scheduling, routing and design, where good answers are needed but exact methods are too slow.
In simple words
Imagine breeding mango trees for the sweetest fruit. You plant many trees, taste the fruit, cross the sweetest trees, plant their seeds, and occasionally get a surprising new variety. After many seasons, your orchard is much sweeter. A genetic algorithm does this with answers instead of trees.
Overview
- Genetic algorithms search by evolving a population of candidate solutions.
- A fitness function scores candidates; fitter ones are more likely to become parents.
- Crossover combines parents; mutation adds small random changes.
- John Holland developed the approach in the 1960s and 1970s.
- They need no gradients, only a way to score candidates.
- They are one family of evolutionary algorithms, alongside evolution strategies and genetic programming.
Why it matters
Many real problems, such as timetabling exams, routing delivery vans, packing containers or designing antenna shapes, have astronomically many possible solutions and no simple formula. GAs give good solutions in reasonable time and need only a way to score a candidate, not a gradient or a full model of the problem. NASA used an evolved antenna on its Space Technology 5 mission in 2006.
Key terms
- Population
- The set of candidate solutions in one generation.
- Chromosome
- The encoding of one candidate, such as the bit string 0101.
- Fitness function
- A score saying how good a candidate is.
- Selection
- Choosing parents, favouring fitter candidates, for example by tournament.
- Crossover
- Combining parts of two parents to create children.
- Mutation
- A small random change to a child, such as flipping one bit.
Types
Each part of a genetic algorithm comes in several types. Choosing them well matters as much as the population size.
1. Encoding types
How a candidate is written as a chromosome: binary strings, real-valued vectors, permutations or trees.
- How it works: The encoding must make crossover and mutation produce valid candidates; permutations need special operators so no city repeats.
- Example: Knapsack: a bit per item; a delivery route: a permutation of stops; antenna design: real-valued lengths.
- When to use it: Choose the encoding first, because it decides which operators make sense.
2. Selection methods
Ways to choose parents: roulette-wheel (fitness-proportional), rank, and tournament selection.
- How it works: Roulette gives each candidate a slice proportional to its fitness; tournament selection picks the best of k random candidates; rank selection uses order, not raw fitness.
- Example: Tournament selection with k = 3 in the knapsack example.
- When to use it: Use tournament selection as a robust default; adjust k to control selection pressure.
3. Crossover types
One-point, two-point, uniform and order-based crossover.
- How it works: One-point swaps tails after a cut; uniform chooses each gene from either parent at random; order crossover keeps permutations valid.
- Example: Parents 110|01 and 001|10 give children 11010 and 00101 by one-point crossover.
- When to use it: Use one-point or uniform for binary strings and order-based crossover for routes and schedules.
4. Mutation types
Bit flips, swaps, inversions and small random changes to numbers.
- How it works: Each gene changes with a small probability, often 1 ÷ chromosome length; Gaussian mutation adds small noise to real values.
- Example: Swapping two stops in a delivery route, or flipping one bit in a knapsack solution.
- When to use it: Use mutation to keep variety in the population and avoid premature convergence.
5. Replacement strategies (elitism and steady state)
Rules for forming the next generation.
- How it works: Generational replacement swaps the whole population; elitism copies the best few unchanged; steady-state GAs replace only a few individuals at a time.
- Example: Keeping the two best knapsack packings in every generation so the best value never drops.
- When to use it: Use elitism almost always; it is cheap and guarantees the best solution is never lost.
Explained in detail
One generation of a genetic algorithm
Start with, say, 50 random chromosomes. Compute each one's fitness. Select parents: in tournament selection, pick 3 candidates at random and keep the fittest, repeating to get each parent. Apply crossover with a high probability, often 0.7 to 0.9: in one-point crossover, cut both parents at the same random position and swap the tails. Apply mutation with a low probability per gene, often 1 ÷ (chromosome length), flipping bits or nudging numbers. Many GAs also use elitism, copying the best one or two candidates unchanged into the next generation so the best solution found is never lost. Repeat for a fixed number of generations or until fitness stops improving.
Design choices
| Choice | Options | Effect |
|---|---|---|
| Encoding | Bit strings, real numbers, permutations (for routes) | Must make crossover and mutation produce valid candidates |
| Selection pressure | Tournament size, ranking, roulette wheel | Too strong loses variety; too weak learns slowly |
| Mutation rate | Typically 1 ÷ length per gene | Too high becomes random search; too low gets stuck |
| Constraints | Penalties, repair, or zero fitness for invalid answers | Keeps the search near feasible solutions |
Strengths, limits and relatives
GAs explore many regions of the search space at once, which helps them escape local optima that trap hill climbing. They need no derivatives, so they work when the score comes from a simulation or a messy rule. On the other hand, they offer no guarantee of finding the best answer, need many fitness evaluations, and have several settings to tune. When a problem has a smooth, differentiable objective, gradient methods are usually much faster. Related methods include simulated annealing, particle swarm optimisation, ant colony optimisation and evolution strategies; neuroevolution even evolves the weights or structure of neural networks. In the code below, with 16 items and a weight limit of 50, the best packing in a random first generation is worth 290; by generation 20 the GA reaches 355, which a brute-force check of all 65,536 combinations confirms is the true optimum.
Real-world scenarios: logistics companies evolve delivery routes for dozens of vans under time windows; engineers evolve the shapes of antennas, turbine blades and car parts tested in simulation; and timetabling offices evolve class, exam and shift schedules that satisfy hundreds of rules. In each case the fitness function encodes what good means, and that is where most of the design effort goes.
How it works
- Encode a candidate solution as a chromosome.
- Write a fitness function, handling invalid candidates.
- Create a random population and evaluate it.
- Loop: select parents, apply crossover and mutation, keep the elite.
- Stop after enough generations and report the best candidate found.
The maths
- 1 if item i is packed, else 0
- Weight capacity
A bag holds 10 kg. Items: A (5 kg, ₹10), B (4 kg, ₹40), C (6 kg, ₹30) and D (3 kg, ₹50). Chromosome 0101 packs B and D: weight 7 kg, fitness ₹90. Chromosome 0011 packs C and D: 9 kg, ₹80. One-point crossover after the second gene gives children 01|11 = 0111 (B, C, D: 13 kg, too heavy, fitness 0) and 00|01 = 0001 (D only: ₹50). Mutating the first bit of 0101 gives 1101 (A, B, D: 12 kg, fitness 0). Checking all 16 combinations confirms that 0101, worth ₹90, is the best; a GA finds it without checking every option, which matters when there are 50 items and over a thousand million million combinations.
In code
from itertools import product
import numpy as np
rng = np.random.default_rng(1)
weights = rng.integers(1, 15, 16) # 16 items
values = rng.integers(5, 60, 16)
CAP = 50
def fitness(pop):
w = pop @ weights
return np.where(w <= CAP, pop @ values, 0)
# Brute force: all 2**16 = 65,536 combinations, possible only because 16 is small
best_exact = max(int(np.dot(c, values)) for c in product([0, 1], repeat=16) if np.dot(c, weights) <= CAP)
pop = rng.integers(0, 2, (40, 16))
for gen in range(60):
fit = fitness(pop)
if gen in (0, 5, 20, 59):
print(f"generation {gen:>2}: best value {fit.max()}, average value {fit.mean():.0f}")
elite = pop[np.argsort(fit)[-2:]] # keep the two best
children = []
while len(children) < len(pop) - 2:
a, b = (pop[max(rng.choice(len(pop), 3), key=lambda i: fit[i])] for _ in range(2)) # tournaments
cut = rng.integers(1, 16)
child = np.concatenate([a[:cut], b[cut:]]) # one-point crossover
flip = rng.random(16) < 1 / 16 # mutation
children.append(np.where(flip, 1 - child, child))
pop = np.vstack([elite, children])
print("Best value found by the GA:", fitness(pop).max(), "| true best by brute force:", best_exact)Output
generation 0: best value 290, average value 50 generation 5: best value 349, average value 183 generation 20: best value 355, average value 208 generation 59: best value 355, average value 219 Best value found by the GA: 355 | true best by brute force: 355
Try it yourself
One generation
Put the steps of a GA generation in order.
- 1Mutate a few genes in each child
- 2Copy the elite into the next generation
- 3Select parents by tournament
- 4Create children by crossover
- 5Evaluate the fitness of every candidate
Match the GA idea to nature
Which natural process inspired each step?
- Selection
- Crossover
- Mutation
- Population
Building an exam timetable
A university must schedule 120 exams into 15 slots without clashes for any student.
Common mistakes
- Using a mutation rate so high that the search becomes random.
- Forgetting elitism, so the best solution can be lost.
- Using a GA where a simple exact or gradient method would be faster.
Check yourself
Summary
- Genetic algorithms evolve a population of candidate solutions using a fitness score.
- Selection, crossover and mutation create each new generation; elitism keeps the best.
- They need no gradients and suit scheduling and design, but give no guarantee of the best answer.
Finished reading?
Sources: Melanie Mitchell, An Introduction to Genetic Algorithms (MIT Press) · Russell and Norvig, Artificial Intelligence: A Modern Approach, chapter on local search