Mutation (genetic algorithm)
Encyclopedia
In genetic algorithm
s of computing
, mutation is a genetic operator
used to maintain genetic diversity
from one generation of a population of algorithm chromosomes
to the next. It is analogous to biological mutation
.Mutation alters one or more gene values in a chromosome from its initial state.In mutation,the solution may change entirely from the previous solution.Hence GA can come to better solution by using mutation.Mutation occurs during evolution according to a user-definable mutation probability.This probability should be set low. If it is set to high, the search will turn into a primitive random search.
The classic example of a mutation operator involves a probability that an arbitrary bit
in a genetic sequence will be changed 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 modified. This mutation procedure, based on the biological point mutation
, is called single point mutation. Other types are inversion and floating point mutation. When the gene encoding is restrictive as in permutation problems, mutations are swaps, inversions and scrambles.
The purpose of mutation in GAs is preserving and introducing diversity. Mutation should allow the algorithm to avoid local minima by preventing the population of chromosomes from becoming too similar to each other, thus slowing or even stopping evolution. This reasoning also explains the fact that most GA systems avoid only taking the fittest
of the population in generating the next but rather a random (or semi-random) selection with a weighting toward those that are fitter.
For different genome types, different mutation types are suitable:
|1 || 0 || 1 || 0 || 0 || 1 || 0
|-
| || || || || ↓ || ||
|-
|1 || 0 || 1 || 0 || 1 || 1 || 0
|}
This mutation operator takes the chosen genome and invert the bits.
(i.e. if the genome bit is 1,it is changed to 0 and vice versa)
This mutation operator replaces the genome with either lower or upper bound randomly.
This can be used for integer and float genes.
The probability that amount of mutation will go to 0 with the next generation is increased by using non-uniform mutation operator.It keeps the population from stagnating in the early stages of the evolution.It tunes solution in later stages of evolution.This mutation operator can only be used for integer and float genes.
This operator replaces the value of the chosen gene with a uniform random value selected between the user-specified upper and lower bounds for that gene. This mutation operator can only be used for integer and float genes.
This operator adds a unit Gaussian distributed random value to the chosen gene. If it falls outside of the user-specified lower or upper bounds for that gene,the new gene value is clipped. This mutation operator can only be used for integer and float genes.
Genetic algorithm
A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...
s of computing
Computing
Computing is usually defined as the activity of using and improving computer hardware and software. It is the computer-specific part of information technology...
, mutation is a genetic operator
Genetic operator
A genetic operator is an operator used in genetic algorithms to maintain genetic diversity, known as Mutation and to combine existing solutions into others, Crossover...
used to maintain genetic diversity
Genetic diversity
Genetic diversity, the level of biodiversity, refers to the total number of genetic characteristics in the genetic makeup of a species. It is distinguished from genetic variability, which describes the tendency of genetic characteristics to vary....
from one generation of a population of algorithm chromosomes
Chromosome (genetic algorithm)
In genetic algorithms, a chromosome is a set of parameters which define a proposed solution to the problem that the genetic algorithm is trying to solve...
to the next. It is analogous to biological mutation
Mutation
In molecular biology and genetics, mutations are changes in a genomic sequence: the DNA sequence of a cell's genome or the DNA or RNA sequence of a virus. They can be defined as sudden and spontaneous changes in the cell. Mutations are caused by radiation, viruses, transposons and mutagenic...
.Mutation alters one or more gene values in a chromosome from its initial state.In mutation,the solution may change entirely from the previous solution.Hence GA can come to better solution by using mutation.Mutation occurs during evolution according to a user-definable mutation probability.This probability should be set low. If it is set to high, the search will turn into a primitive random search.
The classic example of a mutation operator involves a probability that an arbitrary bit
Bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
in a genetic sequence will be changed from its original state. A common method of implementing the mutation operator involves generating a random variable
Random variable
In probability and statistics, a random variable or stochastic variable is, roughly speaking, a variable whose value results from a measurement on some type of random process. Formally, it is a function from a probability space, typically to the real numbers, which is measurable functionmeasurable...
for each bit in a sequence. This random variable tells whether or not a particular bit will be modified. This mutation procedure, based on the biological point mutation
Point mutation
A point mutation, or single base substitution, is a type of mutation that causes the replacement of a single base nucleotide with another nucleotide of the genetic material, DNA or RNA. Often the term point mutation also includes insertions or deletions of a single base pair...
, is called single point mutation. Other types are inversion and floating point mutation. When the gene encoding is restrictive as in permutation problems, mutations are swaps, inversions and scrambles.
The purpose of mutation in GAs is preserving and introducing diversity. Mutation should allow the algorithm to avoid local minima by preventing the population of chromosomes from becoming too similar to each other, thus slowing or even stopping evolution. This reasoning also explains the fact that most GA systems avoid only taking the fittest
Fitness function
A fitness function is a particular type of objective function that is used to summarise, as a single figure of merit, how close a given design solution is to achieving the set aims....
of the population in generating the next but rather a random (or semi-random) selection with a weighting toward those that are fitter.
For different genome types, different mutation types are suitable:
- Bit string mutation
-
- The mutation of bit strings ensue through bit flips at random positions.
-
- Example:
- {|
|1 || 0 || 1 || 0 || 0 || 1 || 0
|-
| || || || || ↓ || ||
|-
|1 || 0 || 1 || 0 || 1 || 1 || 0
|}
-
- The probability of a mutation of a bits is
, where 
is the length of the binary vector. Thus, a mutation rate of 
per mutation and individual selected for mutation is reached.
- The probability of a mutation of a bits is
- Flip Bit
This mutation operator takes the chosen genome and invert the bits.
(i.e. if the genome bit is 1,it is changed to 0 and vice versa)
- Boundary
This mutation operator replaces the genome with either lower or upper bound randomly.
This can be used for integer and float genes.
- Non-Uniform
The probability that amount of mutation will go to 0 with the next generation is increased by using non-uniform mutation operator.It keeps the population from stagnating in the early stages of the evolution.It tunes solution in later stages of evolution.This mutation operator can only be used for integer and float genes.
- Uniform
This operator replaces the value of the chosen gene with a uniform random value selected between the user-specified upper and lower bounds for that gene. This mutation operator can only be used for integer and float genes.
- Gaussian
This operator adds a unit Gaussian distributed random value to the chosen gene. If it falls outside of the user-specified lower or upper bounds for that gene,the new gene value is clipped. This mutation operator can only be used for integer and float genes.