Genetic operator

Not to be confused with Operator (genetics).

A genetic operator is an operator used in evolutionary algorithms (EA) to guide the algorithm towards a solution to a given problem. There are three main types of operators (mutation, crossover and selection), which must work in conjunction with one another in order for the algorithm to be successful. ^[1] Genetic operators are used to create and maintain genetic diversity (mutation operator), combine existing solutions (also known as chromosomes) into new solutions (crossover) and select between solutions (selection). ^{[2] [3]}

The classic representatives of evolutionary algorithms include genetic algorithms, evolution strategies, genetic programming and evolutionary programming. In his book discussing the use of genetic programming for the optimization of complex problems, computer scientist John Koza has also identified an 'inversion' or 'permutation' operator; however, the effectiveness of this operator has never been conclusively demonstrated and this operator is rarely discussed in the field of genetic programming. ^{[4] [5]} For combinatorial problems, however, these and other operators tailored to permutations are frequently used by other EAs. ^{[6] [7]}

Mutation (or mutation-like) operators are said to be unary operators, as they only operate on one chromosome at a time. In contrast, crossover operators are said to be binary operators, as they operate on two chromosomes at a time, combining two existing chromosomes into one new chromosome. ^{[8] [9]}

Operators

Genetic variation is a necessity for the process of evolution. Genetic operators used in evolutionary algorithms are analogous to those in the natural world: survival of the fittest, or selection; reproduction (crossover, also called recombination); and mutation.

Selection

Main article: Selection (evolutionary algorithm)

Selection operators give preference to better candidate solutions (chromosomes), allowing them to pass on their 'genes' to the next generation (iteration) of the algorithm. The best solutions are determined using some form of objective function (also known as a 'fitness function' in evolutionary algorithms), before being passed to the crossover operator. Different methods for choosing the best solutions exist, for example, fitness proportionate selection and tournament selection. ^[10] A further or the same selection operator is used to determine the individuals for beeing selected to form the next parental generation. The selection operator may also ensure that the best solution(s) from the current generation always become(s) a member of the next generation without being altered; ^[11] this is known as elitism or elitist selection. ^{[2] [12] [13]}

Crossover

Main article: Crossover (evolutionary algorithm)

Crossover is the process of taking more than one parent solutions (chromosomes) and producing a child solution from them. By recombining portions of good solutions, the evolutionary algorithm is more likely to create a better solution. ^[2] As with selection, there are a number of different methods for combining the parent solutions, including the edge recombination operator (ERO) and the 'cut and splice crossover' and 'uniform crossover' methods. The crossover method is often chosen to closely match the chromosome's representation of the solution; this may become particularly important when variables are grouped together as building blocks, which might be disrupted by a non-respectful crossover operator. Similarly, crossover methods may be particularly suited to certain problems; the ERO is considered a good option for solving the travelling salesman problem. ^[14]

Mutation

Main article: Mutation (evolutionary algorithm)

The mutation operator encourages genetic diversity amongst solutions and attempts to prevent the evolutionary algorithm converging to a local minimum by stopping the solutions becoming too close to one another. In mutating the current pool of solutions, a given solution may change between slightly and entirely from the previous solution. ^[15] By mutating the solutions, an evolutionary algorithm can reach an improved solution solely through the mutation operator. ^[2] Again, different methods of mutation may be used; these range from a simple bit mutation (flipping random bits in a binary string chromosome with some low probability) to more complex mutation methods in which genes in the solution are changed, for example by adding a random value from the Gaussian distribution to the current gene value. As with the crossover operator, the mutation method is usually chosen to match the representation of the solution within the chromosome. ^{[15] [3]}

Combining operators

While each operator acts to improve the solutions produced by the evolutionary algorithm working individually, the operators must work in conjunction with each other for the algorithm to be successful in finding a good solution. ^[3] Using the selection operator on its own will tend to fill the solution population with copies of the best solution from the population. If the selection and crossover operators are used without the mutation operator, the algorithm will tend to converge to a local minimum, that is, a good but sub-optimal solution to the problem. Using the mutation operator on its own leads to a random walk through the search space. Only by using all three operators together can the evolutionary algorithm become a noise-tolerant global search algorithm, yielding good solutions to the problem at hand. ^[2]

References

1. Jiang, Dazhi; Tian, Zhihang; He, Zhihui; Tu, Geng; Huang, Ruixiang (1 September 2021). "A framework for designing of genetic operators automatically based on gene expression programming and differential evolution". Natural Computing. 20 (3): 395–411. doi:10.1007/s11047-020-09830-2. ISSN   1572-9796.
2. "Introduction to Genetic Algorithms". Archived from the original on 11 August 2015. Retrieved 20 August 2015.
3. Eiben, A.E.; Smith, J.E. (2015). "Representation, Mutation, and Recombination". Introduction to Evolutionary Computing. Natural Computing Series. Berlin, Heidelberg: Springer. pp. 49–78. doi:10.1007/978-3-662-44874-8. ISBN   978-3-662-44873-1. S2CID   20912932.
4. Koza, John R. (1996). Genetic programming : on the programming of computers by means of natural selection (6th ed.). Cambridge, Mass.: MIT Press. ISBN   0-262-11170-5.
5. "Genetic programming operators" . Retrieved 20 August 2015.
6. Eiben, A.E.; Smith, J.E. (2015). "Mutation for Permutation Representation". Introduction to Evolutionary Computing. Natural Computing Series (2nd ed.). Berlin, Heidelberg: Springer. pp. 69–70. doi:10.1007/978-3-662-44874-8. ISBN   978-3-662-44873-1.
7. Yu, Xinjie; Gen, Mitsuo (2010). "Mutation Operators". Introduction to Evolutionary Algorithms. Decision Engineering. London: Springer. pp. 286–288. doi:10.1007/978-1-84996-129-5. ISBN   978-1-84996-128-8.
8. "Genetic operators". Archived from the original on 30 December 2017. Retrieved 20 August 2015.
9. Eiben, A.E.; Smith, J.E. (2015). "Variation Operators (Mutation and Recombination)". Introduction to Evolutionary Computing. Natural Computing Series (2nd ed.). Berlin, Heidelberg: Springer. pp. 31–33. doi:10.1007/978-3-662-44874-8. ISBN   978-3-662-44873-1.
10. Eiben, A.E.; Smith, J.E. (2015). "Parent Selection". Introduction to Evolutionary Computing. Natural Computing Series (2nd ed.). Berlin, Heidelberg: Springer. pp. 80–87. doi:10.1007/978-3-662-44874-8. ISBN   978-3-662-44873-1.
11. Eiben, A.E.; Smith, J.E. (2015). "Survivor Selection". Introduction to Evolutionary Computing. Natural Computing Series (2nd ed.). Berlin, Heidelberg: Springer. pp. 87–90. doi:10.1007/978-3-662-44874-8. ISBN   978-3-662-44873-1.
12. "Introduction to Genetic Algorithm" . Retrieved 20 August 2015.
13. Eiben, A.E.; Smith, J.E. (2015). Introduction to Evolutionary Computing. Natural Computing Series (2nd ed.). Berlin, Heidelberg: Springer. p. 89. doi:10.1007/978-3-662-44874-8. ISBN   978-3-662-44873-1.
14. Whitley, Darrell; Starkweather, Timothy; Fuquay, D'Ann (1989), Schaffer, J.D. (ed.), "Scheduling Problems and Traveling Salesmen: The Genetic Edge Recombination Operator", Proceedings of the 3rd International Conference on Genetic Algorithms (ICGA), San Francisco: Morgan Kaufmann, pp. 133–140, ISBN   1558600663
15. Bäck, Thomas; Fogel, David B.; Whitley, Darrell; Angeline, Peter J. (1999). "Mutation operators". In Bäck, Thomas; Fogel, David B.; Michalewicz, Zbigniew (eds.). Evolutionary computation Vol. 1, Basic algorithms and operators. Boca Racon: CRC Press. pp. 237–255. ISBN   0-585-30560-9. OCLC   45730387.