Genetic Algorithm (GA)
Evolve a population of candidate solutions — mate the good ones, mutate occasionally, kill the worst.
Intuition
The big idea
You don't need to know how to solve the problem. You just need to be able to rate any solution. Start with random "tries", combine the best of each generation, slap in some random mutation to keep diversity, and selection pressure does the rest. After enough generations, surprisingly good solutions emerge.
This works for problems where:
- You can encode a candidate solution as a "chromosome" (string/array).
- You can write a fitness function: chromosome → number (higher = better).
- The search space is too big to enumerate, but solutions aren't isolated — combining two good ones often produces a third good one.
Vocabulary you must know
| Term | Meaning |
|---|---|
| Chromosome / Individual | One candidate solution (e.g., a tour, a coloring) |
| Gene | One position in the chromosome (e.g., the color of variable V3) |
| Population | The current set of chromosomes |
| Fitness | Quality of one chromosome — higher is better |
| Selection | Picking parents — biased toward fitter individuals |
| Crossover | Combining two parents into offspring |
| Mutation | Random tiny change in a chromosome |
| Generation | One iteration of select-mate-mutate-cull |
Algorithm steps
1. Generate an initial random population. 2. Evaluate fitness of each individual. 3. Select pairs for reproduction. 4. Apply crossover to produce offspring. 5. Apply mutation (with small probability) to offspring. 6. Cull weakest individuals (keep best). 7. If stop criterion not met → go to step 3. Solution = individual with highest fitness at the end.
Crossover methods
1-point crossover
Pick one random cut point. Take left part of parent 1 and right part of parent 2 → child 1. Mirror for child 2.
Example with binary genes for a 6-variable CSP (cut after position 4):
Parent 1: R S S R | S R Parent 2: R S S S | R R Child 1: R S S R | R R Child 2: R S S S | S R
2-point crossover
Pick two cut points. Swap the middle segment.
Parent 1: R S S | R S R
Parent 2: R S S | S R R
cut between (3,4) and (5,6)
Child 1: R S S | S R R ← parent 1 + middle from parent 2
Child 2: R S S | R S R
Mutation
For each child, with small probability p_m, randomly change one gene.
Child: R S S S R R Random gene index = 3 Flip color at position 3 → R After: R S R S R R
Why mutation matters: without it, the population's gene pool can collapse (everyone identical), and crossover stops producing anything new. Mutation re-introduces diversity.
TSP-safe crossover (permutation problems)
For TSP, each chromosome is a permutation of cities. Plain 1-point crossover usually produces invalid tours (some cities repeated, others missing).
Order crossover fixes this:
Parent 1: 1 2 3 | 4 5 6 7 | 8 9
Parent 2: 4 5 2 | 1 8 7 6 | 9 3
# Take middle segment from parent 1 (positions 4..7)
Child 1 starts: _ _ _ | 4 5 6 7 | _ _
# Fill remaining positions with cities from parent 2 in order, skipping already-used:
parent 2 order: 4 5 2 1 8 7 6 9 3
^ ^ ^ ^ ^ ^ (skipped: 4,5 already in child; 6,7 already in child)
remaining order: 2, 1, 8, 9, 3
Child 1: 2 1 8 | 4 5 6 7 | 9 3 ✓ valid permutation
Interactive demo — Graph coloring
9-variable graph, color with two colors so no edge has same color on both ends. Watch a small population evolve.
Exam tips
Frequently asked
- "Perform 1-point/2-point crossover on these two parents" — draw the cut, produce both children, check no constraints are violated (for TSP, use a TSP-safe variant).
- "Apply mutation" — pick a random index, flip the gene.
- "Calculate fitness" — count satisfied constraints (CSP) or compute total distance (TSP).
- "Why use GA over greedy?" — GA explores multiple basins simultaneously; doesn't get stuck in one local optimum.
- "Why does plain crossover fail for TSP?" — produces tours with duplicate/missing cities.