📂Optimization

What is a Genetic Algorithm?

Definition ¹

$$ \argmax_{\mathbf{x} \in X} f \left( \mathbf{x} \right) $$ In an optimization problem that maximizes an objective function $f : X \to \mathbb{R}$, a method that repeats the following three operations is called a genetic algorithm.

• selection: Superior solutions are selected from the current set of solutions to form the set of solutions for the next generation.
• crossover: Several solutions are chosen from the set of solutions and part of their information is exchanged to generate new solutions.
• mutation: The information of some solutions in the set of solutions is randomly altered to secure diversity.

Explanation

A genetic algorithm is a population method inspired by the survival of the fittest in Darwin’s theory of evolution. Each individual is represented by a vector $\mathbf{x} \in X$ called a chromosome, and it is evaluated as $f \left( \mathbf{x} \right)$, taking that function value itself as its fitness. In the metaphor of evolutionary theory, $f$ signifies the environment itself, and what we want is to find the $\mathbf{x}$ that survives best in this environment, that is, the $\mathbf{x}$ for which $f$ is maximal.

Selection

Just as natural selection is explained in evolutionary theory, evolution is not the development of organs or physiology with some intention; it is rather a phenomenon that occurs through the repetition in which individuals of lower fitness are weeded out and individuals of higher fitness survive.

In a genetic algorithm, selection is implemented simply as an operation that causes solutions of low fitness to be removed from the set of solutions, and it is fundamentally the driving force that makes the genetic algorithm work.

Crossover

From the perspective of optimization, crossover is a global search method for broadly scanning the entire solution space; through abrupt rather than gradual change, it plays the role of preventing the algorithm from falling into local optima. This is likewise true in actual nature, in line with the fact that sexual reproduction—mainly explained as a strategy for resisting parasites—is advantageous for securing explosive diversity.

Mutation

Mutation is implemented by giving small changes to the chromosome, and, in contrast to crossover, it has the character of a local search method. If selection alone were repeated without mutation, it would be tantamount to having the final solution determined in the first generation without any need to go through successive generations; the point is to introduce small changes, even at the risk of failure, in order to seek a better solution.