Genetic algorithms

Genetic algorithms are heuristic, stochastic optimization methods that were first proposed in 1975 by Holland. They are based on the idea of evolution with natural selection, which was proposed by Darwin.

Genetic algorithms work with a lot of individuals, that is, a population where each individual can serve as a solution to some particular problem. Each individual has to be evaluated for the degree of its fitness, depending on how good the solution of the problem corresponding to it is. If we consider this in relation to nature, then it assesses the degree of efficiency of the organism in the competitive struggle for resources. Individuals, which are much more adapted, can reproduce the offspring by cross-crossing with other representatives of the population. This is the reason for the appearance of new individuals, in which some characteristics, inherited from parents, are combined.

Less adapted individuals will be able to reproduce the offspring with less probability, so that the properties they possess will gradually disappear in the course of evolution from the entire population. Sometimes spontaneous changes in genes, or mutations, occur. It turns out that good characteristics from generation to generation will be distributed throughout the population. Crossing of individuals, which are the most adapted, leads to the fact that the search sites that represent the greatest prospect are investigated. In the final analysis, the problem is solved. Genetic algorithms have the advantage that in a relatively short period of time they find approximate solutions that are optimal. It is worth considering this issue regarding programming.

Genetic algorithms consist of the following components:

- the chromosome, which is the solution to the problem under consideration, consists of genes. This population of chromosomes is considered to be the initial one;

- a set of operators (intended to generate new solutions based on new populations);

- objective function (designed to assess the fitness of solutions).

For genetic algorithms, there is a standard set of operators: selection, mutation and crossing. One can consider the application of genetic algorithms by clarifying what each particular operator is intended for. The selection operator selects chromosomes in accordance with what the values of their fitness functions are. There are at least two most popular operators: a tournament and a roulette. The roulette method assumes the selection of individuals through n launches. For each member of the population used, the roulette wheel contains one sector of the required size. Members of a population with a markedly higher fitness indicator for such a selection will be more likely to be selected than representatives with low fitness. With the tournament method, n tournaments are implemented, allowing you to select n individuals. Each tournament is based on a sample of k elements from the population, with the best individual among them.

If you continue to consider programming algorithms, then it's worth mentioning about the method called crossing. The crossing operator exchanges chromosome parts between a pair or chromosomes in one population.

The last operator - mutations - is a stochastic change in a part of the chromosomes.

Specific consideration of the application of genetic algorithms is a more voluminous material than can fit in the article, so it should be considered separately.