I4 · Problem Solving and Reasoning: Classical AI

Genetic Algorithms

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.

10 min Intermediate · Sublevel Intermediate Jump to the activity

What you need: The earlier topics of this module.

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

ChoiceOptionsEffect
EncodingBit strings, real numbers, permutations (for routes)Must make crossover and mutation produce valid candidates
Selection pressureTournament size, ranking, roulette wheelToo strong loses variety; too weak learns slowly
Mutation rateTypically 1 ÷ length per geneToo high becomes random search; too low gets stuck
ConstraintsPenalties, repair, or zero fitness for invalid answersKeeps 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

  1. Encode a candidate solution as a chromosome.
  2. Write a fitness function, handling invalid candidates.
  3. Create a random population and evaluate it.
  4. Loop: select parents, apply crossover and mutation, keep the elite.
  5. Stop after enough generations and report the best candidate found.

The maths

Knapsack fitness
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

genetic_knapsack.py
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.

  1. 1Mutate a few genes in each child
  2. 2Copy the elite into the next generation
  3. 3Select parents by tournament
  4. 4Create children by crossover
  5. 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

Question 1

1. What does the fitness function do in a GA?

Question 2

2. Parents 110|01 and 001|10 cross over after the third gene. One child is…

Question 3

3. Why is mutation needed?

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