Evolutionary algorithms are a family of optimization algorithms based on the principle of Darwinian natural selection. As part of natural selection, a given environment has a population of individuals that compete for survival and reproduction. The ability of each individual to achieve these goals determines their chance to have children, in other words, to pass on their genes to the next generation of individuals, who, for genetic reasons, will have an increased chance of doing well, even better, in realizing these two objectives.
This principle of continuous improvement over the generations is taken by evolutionary algorithms to optimize solutions to a problem. In the initial generation, a population composed of different individuals is generated randomly or by other methods. An individual is a solution to the problem, more or less good: the quality of the individual in regards to the problem is called fitness, which reflects the adequacy of the solution to the problem to be solved. The higher the fitness of an individual, the higher it is likely to pass some or all of its genotype to the individuals of the next generation.
An individual is coded as a genotype, which can have any shape, such as a bit vector (genetic algorithms) or a vector of real (evolution strategies). Each genotype is transformed into a phenotype when assessing the individual, i.e. when its fitness is calculated. In some cases, the phenotype is identical to the genotype: it is called direct coding. Otherwise, the coding is called indirect. For example, suppose you want to optimize the size of a rectangular parallelepiped defined by its length, height and width. To simplify the example, assume that these three quantities are integers between 0 and 15. We can then describe each of them using a 4-bit binary number. An example of a potential solution may be to genotype 0001 0111 1010. The corresponding phenotype is a parallelepiped of length 1, height 7 and width 10.
During the transition from the old to the new generation, the variation operators, whose purpose is to manipulate individuals, are applied. There are two distinct types of variation operators:
- the mutation operators, which are used to introduce variations within the same individual, as genetic mutations;
- the crossover operators, which are used to cross at least two different genotypes, as genetic crosses from breeding.
Evolutionary algorithms have proven themselves in various fields such as operations research, robotics, biology, nuance, or cryptography. In addition, they can optimize multiple objectives simultaneously and can be used as black boxes because they do not assume any properties in the mathematical model to optimize. Their only real limitation is the computational complexity.