Genetic and evolutionary algorithms

Since the 1970s, numerous stochastic optimization methods have been developed on the basis of simplified Darwinian evolutionary principles. The Anglicism "evolutionary algorithms (AE)" chosen to designate these methods is intentional: the French community employing these methods felt it important to distinguish evolutionary work, involving highly complex biological models, from evolutionary approaches, using ultra-simplified computer models.

Genetic algorithms (GA) are currently the most widely publicized of these techniques, but there are others (genetic programming, evolutionary strategies, grammatical evolution, for example) which differ in their interpretation of Darwinian principles. What these techniques have in common is that they evolve populations organized in generations – which represent, for example, points in a search space when we wish to optimize a function – under the combined action of two categories of stochastic operators producing :

• selection pressure to select individuals authorized to reproduce: "the best" in terms of a function defined in the search space under consideration, known as the "evaluation function", "performance function" or "fitness", and which reflects the problem we're trying to solve;

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

The effectiveness of this scheme 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 the successive populations must be correctly calibrated and parameterized to converge towards what is desired, i.e. 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 notion of AE-difficulty). As we shall see in this overview, reassuring theoretical answers exist (yes, it converges, if certain assumptions are respected), but other crucial questions from a practical point of view remain open (convergence speeds, in particular). However, it can be said that the theoretical results justify the efficacy of evolutionary algorithms as random search heuristics, thus confirming their widespread empirical use.

From an optimization point of view, the great advantage of evolutionary algorithms is that they are stochastic methods of order 0, i.e. only knowledge of the values...