8.4.1 Evolutionary Computation

An evolutionary algorithm is a probabilistic algorithm based on populations of possible solutions. The most general form of an evolutionary algorithm works as follows and includes practically all methods from evolutionary computation as special cases [101,112,36,49,77,63].

1. Set the time (i.e., the generation number) $t:=0$.
2. Initialize the population $P(0)$, usually randomly.
3. Evaluate all individuals in the set $P(0)$ using the given objective function $f$.
4. While the population has not converged (or another termination criterion has been met), do
   1. Increase time, $t:=t+1$.
   2. Select individuals from the old population $P(t-1)$ and recombine them into the new population $P(t)$.
   3. Evaluate $P(t)$. Remember the best individual ever found.
   4. Repeat.
5. Finally return the best individual.

Usually each of the variables of the objective function is chosen from an interval so that the domain of the objective function is a multidimensional interval.

Without loss of generality it can always be assumed by considering the objective function $-f$ instead of $f$ that a given optimization problem is either a minimization or maximization problem depending on which is more convenient for the analysis of the algorithm.

There is obviously ample room for variations of the algorithm in the selection and recombination step, where the new population is constructed from the old one (cf. Section 8.3). This is also the crucial part of the algorithm, where the right balance between a comprehensive search of the domain of $f$ and the precise determination of extrema has to be found. This is usually achieved by the interplay of selection, where the probability that individuals proliferate is determined, mutation, and crossover.

Constraints on the set of admissible solutions can be handled in a straightforward manner. Whenever a possible solution or individual is not admissible, a penalty value is substituted for (or added to) the objective function. In view of Section 8.5 this means that schemata favoring non-admissible solutions receive exponentially decreasing trials in subsequent generations.