juniorGenetic Algorithms

What are crossover and mutation, and how do they balance exploration and exploitation?

Updated Feb 20, 2026

Short answer

Crossover combines two parent solutions into offspring, exploiting structure that already works by recombining it. Mutation randomly perturbs an individual, exploring regions the current population cannot reach by recombination alone. Crossover drives convergence and mutation prevents it from being premature — a GA with only crossover stalls in a local optimum, and one with only mutation is random search.

Deep explanation

Crossover operators, in increasing disruptiveness:

TypeScript
Single-point:   parents  AAAA|BBBB   ->  child  AAAABBBB
Two-point:      AA|AAAA|AA + BB|BBBB|BB  ->  AABBBBAA
Uniform:        each gene taken from either parent with probability 0.5

Single-point preserves long contiguous blocks, which suits representations where adjacent genes interact. Uniform mixes aggressively and is better when genes are independent.

Order-preserving crossovers exist for permutation problems. For the travelling salesman, a single-point crossover of two tours produces a sequence with repeated and missing cities — an invalid tour. Order crossover (OX) and partially-mapped crossover (PMX) exist precisely to recombine permutations while keeping them valid. This is the concrete form of the general rule: the crossover operator must match the representation.

Mutation operators depend on the encoding: bit-flip for binary, Gaussian perturbation for real values, swap or inversion for permutations.

Why both are needed.

Crossover alone can only recombine genetic material already present. Once the population converges — every individual carrying the same value at a position — no crossover can ever change it. The search stops in a local optimum with no route out.

Mutation alone reduces the algorithm to a parallel random walk. It can reach anywhere but exploits nothing, discarding the whole point of maintaining a population.

Typical rates reflect the asymmetry: crossover probability 0.6–0.9, mutation probability 0.1–5% per gene. Mutation is deliberately rare because it is destructive — it is a diversity injection, not a search mechanism.

Adaptive schemes adjust as the run proceeds: raise mutation when population diversity collapses, lower it when the population is still spread out. Some implementations track the variance of fitness and tune automatically, which removes much of the manual parameter fiddling GAs are criticised for.

Real-world example

Order crossover for a travelling salesman tour, where naive crossover fails:

Python
# Naive single-point on permutations produces invalid tours:
#   parent1 = [A,B,C,D,E]   parent2 = [C,E,A,B,D]
#   cut at 2 -> [A,B,A,B,D]      A and B twice, C and E missing


def order_crossover(p1, p2):
    size = len(p1)
    a, b = sorted(random.sample(range(size), 2))
    child = [None] * size
    child[a:b] = p1[a:b]                     # keep a slice of parent 1 in place
    remaining = [c for c in p2 if c not in child]   # rest in parent 2's ORDER
    idx = 0
    for i in range(size):
        if child[i] is None:
            child[i] = remaining[idx]; idx += 1
    return child

The child inherits a contiguous run of cities from one parent and the relative ordering of the rest from the other, and is always a valid tour. Mutation here is typically a 2-opt reversal — reversing a segment — which is a small, meaningful change to a route rather than an arbitrary scramble.

Common mistakes

  • - Using a crossover operator that does not respect the representation, producing invalid individuals that then need constant repair.
  • - Setting the mutation rate high enough to destroy the building blocks crossover is trying to assemble.
  • - Relying on crossover alone, so once the population converges at a gene position nothing can ever change it.
  • - Applying single-point crossover to permutation problems, which yields duplicate and missing elements.
  • - Treating mutation as the primary search mechanism rather than a diversity-preserving one.
  • - Never measuring population diversity, which is the signal that tells you whether the exploration/exploitation balance is actually wrong.

Follow-up questions

  • Why does crossover alone cause the search to stall?
  • How do you crossover permutations without producing invalid children?
  • How would you detect that mutation is set too high or too low?
  • What is adaptive mutation?

More Genetic Algorithms interview questions

View all →