Editing Mutation (evolutionary algorithm) (section)

{{Short description|Genetic operation used to add population diversity}}{{Evolutionary algorithms}}
'''Mutation''' is a [[genetic operator]] used to maintain [[genetic diversity]] of the [[chromosome (genetic algorithm)|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 [[genome (genetic algorithm)|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 model (evolutionary algorithm)|population]]. Mutation operators are used in an attempt to avoid [[local minimum|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 [[Fitness function|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.<ref>{{cite web
| accessdate = 2011-04-07
| publisher = Marek Obitko 
| title = XI. Crossover and Mutation
| url = http://www.obitko.com/tutorials/genetic-algorithms/crossover-mutation.php}}</ref>

The following requirements apply to all mutation operators used in an EA:<ref>{{Cite book |last1=Eiben |first1=A.E. |url=http://link.springer.com/10.1007/978-3-662-44874-8 |title=Introduction to Evolutionary Computing |last2=Smith |first2=J.E. |date=2015 |publisher=Springer |isbn=978-3-662-44873-1 |series=Natural Computing Series |location=Berlin, Heidelberg |pages=31–32 |chapter=Variation Operators (Mutation and Recombination) |doi=10.1007/978-3-662-44874-8 |s2cid=20912932}}</ref><ref name=":3">{{Cite book |last1=Bäck |first1=Thomas |url=https://www.worldcat.org/oclc/45730387 |title=Evolutionary computation. Vol. 1, Basic algorithms and operators |last2=Fogel |first2=David B. |last3=Whitley |first3=Darrell |last4=Angeline |first4=Peter J. |publisher=CRC Press |year=1999 |isbn=0-585-30560-9 |editor-last=Bäck |editor-first=Thomas |location=Boca Racon |pages=237–255 |language=en |chapter=Mutation operators |oclc=45730387 |editor-last2=Fogel |editor-first2=David B. |editor-last3=Michalewicz |editor-first3=Zbigniew}}</ref>
# every point in the search space must be reachable by one or more mutations.
# there must be no preference for parts or directions in the search space (no drift).
# 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.<ref>{{Citation |last=Mirjalili |first=Seyedali |title=Genetic Algorithm |date=2019 |url=https://doi.org/10.1007/978-3-319-93025-1_4 |work=Evolutionary Algorithms and Neural Networks: Theory and Applications |pages=43–55 |editor-last=Mirjalili |editor-first=Seyedali |access-date=2023-05-26 |series=Studies in Computational Intelligence |volume=780 |place=Cham |publisher=Springer International Publishing |language=en |doi=10.1007/978-3-319-93025-1_4 |isbn=978-3-319-93025-1|s2cid=242047607 |url-access=subscription }}</ref><ref>{{Cite journal |last1=Harifi |first1=Sasan |last2=Mohamaddoust |first2=Reza |date=2023-05-01 |title=Zigzag mutation: a new mutation operator to improve the genetic algorithm |url=https://doi.org/10.1007/s11042-023-15518-3 |journal=Multimedia Tools and Applications |volume=82 |issue=29 |pages=45411–45432 |language=en |doi=10.1007/s11042-023-15518-3 |s2cid=258446829 |issn=1573-7721|url-access=subscription }}</ref><ref>{{Cite journal |last1=Katoch |first1=Sourabh |last2=Chauhan |first2=Sumit Singh |last3=Kumar |first3=Vijay |date=2021-02-01 |title=A review on genetic algorithm: past, present, and future |url=https://doi.org/10.1007/s11042-020-10139-6 |journal=Multimedia Tools and Applications |language=en |volume=80 |issue=5 |pages=8091–8126 |doi=10.1007/s11042-020-10139-6 |issn=1573-7721 |pmc=7599983 |pmid=33162782}}</ref> An overview and more operators than those presented below can be found in the introductory book by Eiben and Smith<ref>{{Cite book |last1=Eiben |first1=A.E. |url=http://link.springer.com/10.1007/978-3-662-44874-8 |title=Introduction to Evolutionary Computing |last2=Smith |first2=J.E. |date=2015 |publisher=Springer |isbn=978-3-662-44873-1 |series=Natural Computing Series |location=Berlin, Heidelberg |pages=49–78 |chapter=Representation, Mutation, and Recombination |doi=10.1007/978-3-662-44874-8|s2cid=20912932 }}</ref> or in.<ref name=":3" /><ref name=":0">{{Cite book |last=Michalewicz |first=Zbigniew |url=http://link.springer.com/10.1007/978-3-662-02830-8 |title=Genetic Algorithms + Data Structures = Evolution Programs |date=1992 |publisher=Springer Berlin Heidelberg |isbn=978-3-662-02832-2 |series=Artificial Intelligence |location=Berlin, Heidelberg |doi=10.1007/978-3-662-02830-8 |s2cid=33272042}}</ref>