Mutation randomly changes a candidate solution to introduce variation. In a genetic algorithm, it follows parent selection and crossover; the new candidates are then evaluated and considered for the next generation. Unlike crossover, mutation does not need a second parent. section 7.3 section 7.3.4
A binary ticket-price candidate
Suppose a ticket price is encoded as a binary chromosome. A simple mutation tests each bit against a mutation probability and flips selected bits from 0 to 1 or from 1 to 0. In one generation, mutation changes the candidate 01001101 (price 77) into 01100111 (price 103). Fitness evaluation determines whether the changed candidate survives; mutation alone does not guarantee an improvement. section 7.4 section 7.3.5
def mutation(population, mutation_prob) :
chromosome_length = len(population[0])
for i in range(len(population)): #1
for j in range(chromosome_length-1): #2
if mutation_prob > random.random(): #3
if population[i][j]==1: #4
population[i][j]=0 #4
else: #4
population[i][j]=1 #4
return population #5
The Python function shows the nested population-and-gene loops and the random bit flip. Its loop stops before the final bit, despite the accompanying description of a probability at each gene; include that position if every bit should be eligible. section 7.4
The operator must fit the solution representation. For a route encoded as a permutation, changing a gene to an arbitrary city could invalidate the route. Rearranging existing cities instead introduces variation while preserving a valid permutation. section 8.3.2
Common permutation mutations offer different ways to perturb a route:
- Insert moves one selected element after another, largely retaining order and adjacency. section 8.3.2
- Swap exchanges two selected elements, retaining much adjacency while changing their positions. section 8.3.2
- Inversion reverses the segment between two selected positions, disrupting order while largely retaining adjacency. section 8.3.2
- Scramble randomly rearranges elements between selected positions. section 8.3.2
def inversion_mutation(individual, mutation_rate):
n = len(individual)
mutated_individual = individual.copy()
if random.random() < mutation_rate:
i, j = sorted(random.sample(range(n), 2))
mutated_individual[i:j+1] = reversed(mutated_individual[i:j+1])
return mutated_individual
This Python inversion operator first copies the route, then—if a random draw passes the mutation-rate test—reverses a segment between two randomly chosen positions. section 8.3.2
Choose both the mutation method and its probability for the representation and search behavior you want. In the binary example, the probability is tested per gene; in the inversion example, it is tested once per individual. Mutation can favor exploration or exploitation depending on its rate and step size. For constrained problems, check and repair offspring after reproduction. A ready-made alternative for ticket pricing uses pymoo’s PolynomialMutation with RoundingRepair. section 7.4 section 8.3.2 section 8.9 section 7.3
