Mutation (genetic algorithm)

Part of a series on the
Evolutionary algorithm
Artificial development Artificial life Cellular evolutionary algorithm Cultural algorithm Differential evolution Effective fitness Evolutionary computation Evolution strategy Gaussian adaptation Grammar induction Evolutionary multimodal optimization Particle swarm optimization Memetic algorithm Natural evolution strategy Neuroevolution Promoter based genetic algorithm Spiral optimization algorithm Self-modifying code Polymorphic code
Genetic algorithm
Chromosome Clonal selection algorithm Crossover Fly algorithm Genetic memory Genetic fuzzy systems Mutation Schema Selection
Genetic programming
Cartesian genetic programming Linear genetic programming Grammatical evolution Multi expression programming Genetic Improvement Eurisko Parity benchmark
v t e

Mutation is a genetic operator used to maintain genetic diversity of the chromosomes of a population of an evolutionary algorithm (EA), including genetic algorithms in particular. It is analogous to biological mutation.

The classic example of a mutation operator of a binary coded genetic algorithm (GA) involves a probability that an arbitrary bit in a genetic sequence will be flipped from its original state. A common method of implementing the mutation operator involves generating a random variable for each bit in a sequence. This random variable tells whether or not a particular bit will be flipped. This mutation procedure, based on the biological point mutation, is called single point mutation. Other types of mutation operators are commonly used for representations other than binary, such as floating-point encodings or representations for combinatorial problems.

The purpose of mutation in EAs is to introduce diversity into the sampled population. Mutation operators are used in an attempt to avoid local minima by preventing the population of chromosomes from becoming too similar to each other, thus slowing or even stopping convergence to the global optimum. This reasoning also leads most EAs to avoid only taking the fittest of the population in generating the next generation, but rather selecting a random (or semi-random) set with a weighting toward those that are fitter.^[1]

The following requirements apply to all mutation operators used in an EA:^[2][3]

1. every point in the search space must be reachable by one or more mutations.
2. there must be no preference for parts or directions in the search space (no drift).
3. small mutations should be more probable than large ones.

For different genome types, different mutation types are suitable. Some mutations are Gaussian, Uniform, Zigzag, Scramble, Insertion, Inversion, Swap, and so on.^[4][5][6] An overview and more operators than those presented below can be found in the introductory book by Eiben and Smith^[7] or in.^[3][8]