Genetic and evolutionary algorithms

Since the 1970s, numerous stochastic optimisation methods have been developed based on simplified Darwinian evolutionary principles. These methods are collectively referred to as Evolutionary Algorithms (EAs).

Genetic algorithms (GA) are currently the most widely publicised of these techniques, but there are others (such as genetic programming, evolutionary strategies, grammatical evolution) that differ in their interpretation of Darwinian principles. What these techniques have in common is that they evolve populations organised in generations under the combined action of two categories of stochastic operators which produce:

• selection pressure to select individuals permitted to reproduce: “the best” in terms of a function defined over the search space under consideration, known as the “evaluation function”, “performance function” or “fitness function”, which reflects the problem being addressed;

• random variations that generate new individuals for the next generation: crossover, involving the exchange of information between several points, and mutation, involving local perturbation at a single point, drawing a parallel with genetics.

A classical example consists in evolving a population of points within the domain of a function in order to approximate its maximum value. The effectiveness of this scheme relies 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 parameterised to converge towards the intended outcome, most often the global optimum of the performance function. Much of the theoretical research on evolutionary algorithms is devoted to this challenging problem of convergence, as well as to understanding what makes a task easy or difficult for an evolutionary algorithm (the notion of EA-difficulty). As we shall see in this overview, reassuring theoretical answers do exist (yes, convergence occurs if certain assumptions are satisfied), but other crucial questions from a practical standpoint remain unresolved, particularly concerning convergence rates. Nevertheless, it can be asserted that the theoretical results support the efficacy of Evolutionary Algorithms as random search heuristics, thus confirming their widespread empirical use.

From an optimisation point of view, the major advantage of evolutionary algorithms is that they are zero-order stochastic methods, i.e. only the values of the function to be optimised at the sampling points are required (there is no need to know derivatives). This makes them suitable for optimising very irregular, poorly conditioned or computationally complex functions. On the other hand, the computational...