Genetic and evolutionary algorithms

Since the 1970s, numerous stochastic optimization methods have been developed based on simplified principles of Darwinian evolution. The term "evolutionary algorithms (EA)" chosen to describe these methods is intentional: the French community using these methods felt it was important to distinguish between evolutionary work, which deals with highly complex biological models, and evolutionary approaches, which use highly simplified computer models.

Currently, so-called "genetic" algorithms (GA) are the most widely publicized of these techniques, but there are others (genetic programming, evolutionary strategies, grammatical evolution, for example) that differ in their interpretation of Darwinian principles. The common component of these techniques is that they evolve populations organized into generations under the combined action of two categories of stochastic operators producing:

•  a selection pressure that allows individuals authorized to reproduce to be selected: "the best" in terms of a function defined for the search space in question, known as the "evaluation function," "performance function," or "fitness," which reflects the problem being sought to be solved;

•  random variations that produce new individuals to form the next generation: crossover through the exchange of information between several points, mutation through local disturbance at a single point, to draw a parallel with genetics.

A classic example is to evolve a population of points in the definition space of a function in order to find the maximum value of that function. The effectiveness of this approach is based on the assumption that the action of genetic operators on selected individuals statistically produces individuals that are increasingly close to the desired solution. In other words, the stochastic process represented by successive populations must be correctly calibrated and parameterized in order to converge towards the desired result, which is most often the global optimum of the performance function. Much of the theoretical research on evolutionary algorithms is devoted to this thorny problem of convergence and to the question of what makes the task easy or difficult for an evolutionary algorithm (the concept of EA difficulty). As we will see in this overview, there are reassuring theoretical answers (yes, convergence occurs if certain assumptions are met), but other crucial questions from a practical point of view remain open (convergence speeds, in particular). However, we can say that the theoretical results justify the effectiveness of evolutionary algorithms as random search heuristics, thus confirming their widespread empirical use.

From an optimization perspective, the great...