Genetic algorithms are heuristic, stochastic optimization methods that were proposed for the first time in 1975 by Holland. They are based on the idea of evolution with natural selection, which was proposed by Darwin.
Genetic algorithms work with many individuals, that is, a population where each individual can serve as a solution to a particular problem. Each individual has to be assessed for the degree of its fitness, depending on how good the solution to the problem is, corresponding to it. If we consider this in relation to nature, then we evaluate the degree of efficiency of the organism in the competition for resources. Individuals that are noticeably better adapted can reproduce offspring by cross-breeding with other members of the population. This is the reason for the emergence of new individuals that combine some of the characteristics inherited from parents.
Less adapted individuals will be able to reproduce offspring with less probability, so that the properties that they possess will gradually disappear in the process of evolution from the entire population. Spontaneous changes in genes, or mutations, sometimes occur. It turns out that good characteristics from generation to generation will be distributed throughout the population. The crossing of individuals that are the most adapted leads to the fact that the search sites representing the greatest prospect are investigated. Ultimately, a solution to the problem is found. Genetic algorithms have the advantage of finding approximate solutions that are optimal over a relatively short period of time. 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 initial;
- a set of operators (intended to generate new solutions based on new populations);
- objective function (designed to assess the fitness of decisions).
For genetic algorithms, there is a standard set of operators: selection, mutation, and crossbreeding. You can consider the use of genetic algorithms by clarifying what each particular operator is designed for. The selection operator selects chromosomes in accordance with the values of their fitness functions. Here are presented at least two of the most popular operators: tournament and roulette. The roulette method involves the selection of individuals through n starts. For each member of the population used, one sector of the required size is contained in the roulette wheel. Members of a population with a markedly higher fitness indicator for this selection will be more often selected than representatives with low fitness. In the tournament method, n tournaments are implemented, allowing n individuals to be selected. Each tournament is based on a selection of k elements from a population, and the best individual should be selected among them.
If we continue to consider programming algorithms, then it is worth mentioning a method called crossing. The crossing operator exchanges parts of chromosomes between a pair or chromosomes in the same population.
The last operator, mutations, is a stochastic change in part of the chromosomes.
A specific consideration of the use of genetic algorithms is more voluminous material than can fit in the article, so it should be considered separately.