Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 36 ยท Crossover and Mutation

Mutation Operators: Bit-Flip, Gaussian and Polynomial

Learn mutation for every encoding: bit-flip, uniform, Gaussian, polynomial and boundary mutation for numbers, plus swap, insert and inversion for permutations, with mutation-rate guidance.

If selection and crossover are the engine of a genetic algorithm, mutation is the spark that keeps it from stalling. Crossover can only rearrange genes the population already holds. Once a gene value disappears from every individual, only mutation can bring it back. Mutation is also the main source of small, local changes, which is how a population fine-tunes a good solution.

This lesson collects the mutation operators for every encoding you have seen, shows how to set the mutation rate, and explains how to use mutation to explore early and refine late.

What mutation must do

A good mutation operator:

  1. Keeps the chromosome valid. A mutated permutation is still a permutation; a gene stays within bounds.
  2. Can reach every point in the search space eventually (ergodicity).
  3. Prefers small changes over large ones, so that most children resemble their parents (strong causality), while still allowing rare large jumps.

Mutation for bit strings

Bit-flip mutation flips each bit independently with probability p_m. The standard rate is 1 / L, one flip per chromosome on average. It is symmetric and simple.

Variants include flipping exactly k random bits, which controls the amount of change precisely, and heavy-tailed mutation, which draws the number of flips from a power-law distribution so that rare large mutations happen. The heavy-tailed variant is a cheap way to escape local optima.

Python Bit-flip mutation and its rate

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

At 1/L about one gene changes per child, but roughly a third of children are unchanged copies of the parent ((1 - 1/L)^L is about 37 %). At 0.5 each child is essentially random, which is no longer evolution.

Mutation for real numbers

Real genes need numeric changes.

  • Uniform mutation: replace the gene with a random value inside its bounds. Large jumps; useful rarely.
  • Gaussian mutation: add N(0, sigma) noise and clip to bounds. The workhorse. sigma is often 5 to 10 % of the gene's range.
  • Polynomial mutation: popular in NSGA-II. It perturbs a gene with a polynomial distribution controlled by an index eta_m (like SBX): small perturbations are likely, large are possible, and the result respects bounds without clipping.
  • Boundary mutation: set the gene to its lower or upper bound. Helps when optima lie on the boundary.
  • Non-uniform mutation: the step size shrinks as generations pass, from exploring early to fine-tuning late.
Python Gaussian versus polynomial mutation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Gaussian mutation near a bound often overshoots and gets clipped to exactly the bound (a visible fraction of children sit on it), while polynomial mutation scales its steps by the distance to the bound and never overshoots. If you see many genes stuck at a boundary, change the operator or reflect instead of clipping.

Mutation for permutations

You met these in permutation encoding: swap, insert, inversion and scramble. A GA for the TSP typically uses inversion, because it changes only two edges. Another option is displacement (cut a segment and insert it elsewhere). All preserve validity.

Mutation for other encodings

  • Categorical genes: replace with another category, sometimes biased by similarity.
  • Tree (GP): replace a subtree with a new random one (see Genetic Programming).
  • Variable-length lists: add, delete or modify an element.

Setting the mutation rate

Encoding Starting rate (per gene) Alternative
Bit string of length L 1 / L 0.5 to 2 times that
Real vector of d genes 1 / d mutate every gene with a small sigma
Permutation Per individual: 0.05 to 0.3 Several small mutations

Two rules of thumb:

  1. More mutation for small populations, since there is less variation to recombine.
  2. Less mutation near the end, when the solution is good and large jumps usually make it worse.
Python Mutation versus recombination: which does the work?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Crossover alone stalls, because lost bit values cannot return. Mutation alone works on this easy problem. Both together are usually best on harder problems. The right balance depends on the problem, which is why the next lesson shows how the GA can adjust its own parameters.

Mutation by encoding

Bits Flip with rate 1/L
Reals Gaussian or polynomial
Orderings Swap, insert, invert
Trees Replace a subtree

Keep chromosomes valid and changes mostly small.

1 / 2

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why is mutation needed even though crossover exists?

    Crossover only recombines existing material, so only mutation can reintroduce lost values or create new ones.
  2. 2. What is the standard bit-flip mutation rate for a chromosome of length L?

    At 1/L about one bit changes per child, a gentle exploration that works well in practice.
  3. 3. What is the advantage of polynomial mutation near a variable's bound?

    Polynomial mutation scales the perturbation by the room left towards the bound, avoiding the pile-up created by clipping Gaussian overshoot.
  4. 4. Which mutation is generally best for tour (TSP) permutations?

    Inversion reverses a segment and alters only two edges, keeping the tour valid and changing quality only a little.

Summary

  • Mutation reintroduces lost gene values and provides small local changes.
  • Bit strings: flip with probability 1/L; heavy-tailed variants add rare big jumps.
  • Real genes: Gaussian (scale sigma to the range), polynomial (bound-aware), boundary and non-uniform mutation.
  • Permutations: swap, insert, inversion, scramble keep the chromosome valid.
  • Use more mutation for small populations and less late in the run.

Next: Parameter Control and Adaptation