8.4.2 The Classic Genetic Algorithm

The first genetic algorithms used were inspired by and strictly modeled after the biological process. In the classic genetic algorithm discussed in the following it is assumed that the problem considered is a maximization problem and that the objective function is positive. More precisely a real function of real variables is to be maximized, where the domain of the function is a multidimensional interval.

Each variable is represented as a vector $x$ of the form $\{0,1\}^n$. The length $n$ of the vector determines the precision of the variable and thus the precision of the solution. Each vector $x$ is mapped to the domain $[a,b]$ of the variable by

$$x \mapsto a + \frac{b-a}{2^n-1} \sum_{k=1}^n 2^{k-1} x_k,$$

i.e., the interval $[a,b]$ is divided by equidistant points. Then an individual (or chromosome) is represented by the concatenated bit vectors of each variable.

The inner loop of the classic algorithm is as follows.

1. $t:=t+1$.
2. Construct the new generation $P(t)$ from the old one $P(t-1)$:
   1. Select $\vert P(t-1)\vert$ individuals from the old population $P(t-1)$ by the roulette wheel method (cf. Section 8.3.1).
   2. Each individual has the crossover probability $p_c$. Choose the individuals according to this probability. Apply the one point crossover operator (cf. Section 8.3.2) to the chosen individuals, where two individuals generate two offspring individuals.
   3. Finally apply mutation on a bit-by-bit basis, where each bit is changed according to the mutation probability $p_m$. This classic discrete mutation operator works on vectors of bits and changes each bit from 0 to $1$ or vice versa with probability $p_m$.
3. Evaluate $P(t)$.
4. Repeat.

Roulette wheel selection is described in Section 8.3.1. Typical values for the population size are between 20 and 50, for the crossover probability $p_c=0.25$, and for the mutation probability $p_m=0.01$.

The major drawback of this classic algorithm is the awkward representation of real variables, when it is used for the maximization of real valued functions of real variables. This issue is discussed in more detail in Section 8.2. Another disadvantage is the naive way of the roulette wheel selection. When a population contains only individuals with scores of large, nearly equal, absolute value, the selection probability of all individuals becomes nearly identical, which works against the basic idea of genetic algorithms (cf. Section 8.5).

In order to overcome these limitations the following algorithm was devised for TCAD applications.