Suppose every candidate solution in a 0–1 knapsack population excludes potatoes. Crossover can recombine existing candidates, but it cannot introduce a potato-including candidate if none of the parents has that gene set. Mutation solves this exploration problem by randomly changing parts of a candidate’s chromosome. section 18.1.8
A genetic algorithm applies mutation after crossover creates a new individual. The two are separate operators: crossover recombines parents’ features, while mutation makes a local change that may reach a solution the current population cannot produce by recombination alone. Fitness evaluation and natural selection then determine which candidates are more likely to contribute to later generations. section 18.1.5 section 18.1.8
Choose an operator that fits the chromosome representation:
- For a binary knapsack chromosome, visit each gene. With a specified mutation chance, replace its value with 1 minus its current value. Each decision is independent, so even a gene shared by every current candidate can change. section 18.1.8
- For a traveling-salesperson tour represented as an ordering of vertices, swap either adjacent vertices or two randomly chosen vertices. These are separate mutation operators adapted from local-search transitions. section 18.2.2
Listing 18.9 0-1 knapsack: Bit-wise mutation
function knapsackMutation(chromosome, mutationChance) #1
for i in {0,..,|chromosome|} do #2
if random() < mutationChance then
chromosome[i] ← 1 – chromosome[i] #3
return chromosome
The bit-wise knapsack listing shows the complete operator: scan the chromosome, draw a random value for each position, and flip that bit when the draw falls below mutationChance. section 18.1.8
Mutation rate is a trade-off. Too little mutation leaves exploration dependent on the initial population; too much can disrupt convergence and undo the benefits of crossover and selection. The illustrated knapsack mutation rate is deliberately exaggerated; a suggested real-scenario range there is roughly 0.1%–1%, depending on chromosome size. Traveling-salesperson experiments also compare operator probabilities rather than assuming one setting works universally. section 18.1.8 section 18.2.4
The bit-wise operator scans n genes, taking O(n) time and constant extra space when it modifies the chromosome directly. A single vertex swap takes constant time under constant-time indexing and swapping. Direct modification is acceptable for these genetic-algorithm mutations, but callers should document that the input changes. Mutation complements crossover rather than guaranteeing an optimal answer; for highly interdependent variables, compare genetic algorithms with simulated annealing on representative instances. section 18.1.8 section 18.2.2 section 18.5
