Evolution

The key part of the genetic algorithm if the evolutionary step of producing a child-population ${\bf P}'$ out of a parent-population ${\bf P}$ and thereby generating new generations of the initial population ${\bf P}$. This process consists of two main parts: selection and genetic transformation by applying genetic operators to the selected individuals.

Selection

The selection operator ${\cal S}$ selects an individual of the given population according to its fitness. The operator ${\cal S}_n$ selects a set of $n$ individuals and is defined as follows.

$${\cal S}_0 {\bf P} =\emptyset, \qquad {\cal S}_{n+1} {\bf P} = \{{\cal S}{\bf P}\} \cup {\cal S}_{n} {\bf P}$$

In the following examples, ${\bf P}=\{S_1,S_2, \ldots S_p\}$, $f_k=f(S_k)$ and the function $\mbox{\rm rnd}()$ returns a random number of the interval $[0,1)$.

Random Selection

Since this method ignores fitness, it leads to a blind search unless used in combination with another method.

$${\cal S}_{RD} \, {\bf P} = S_r, \quad r=\lfloor p\, \mbox{\rm rnd}() \rfloor$$

Roulette Wheel Selection

This method selects a individual with a probability directly proportional to its fitness. The disadvantage of this method is, that is strongly depends on the actual definition of $f$. A simple transformation $f'=\phi(f)$ with a strictly monotonously increasing function $\phi$ would result in a different distribution.

$${\cal S}_{RW} \, {\bf P}=\left\{ \begin{array}{cl} S, & S={... ...ad \mbox{with} \quad \hat{f}(S)={f(S) \over \sum_{k=1}^p f_k}$$

Rank Selection

This method avoids the disadvantage of the Roulette Wheel selection by selecting individuals according to their rank in the whole population and thereby gaining a fixed distribution. In the case of a linear distribution with a uniform fraction of $u$, ${\cal S}_{RS}$ is defined as

$${\cal S}_{RS} = {\cal S}_{RW}[f'], \qquad f'(S)={(1-u) \over... ...rt \{S' \in {\bf P} \,\vert\, f(S) \geq f(S')\} \right\vert +u$$

This selection mechanism is used in this project, but to avoid the calculation of the ranks, the following equivalent method is used. ²

$${\cal S}_{RS} \, {\bf P}=\left\{ \begin{array}{cl} {\cal S}... ...al S}_{TS} \, {\bf P}, & \mbox{otherwise} \end{array} \right.$$

Tournament Selection

This method is often used in optimising game strategies, where two individuals play and the winner is selected. This method can be used even without knowing $f$.

$${\cal S}_{TS} \, {\bf P}=\left\{ \begin{array}{cl} A, & f(A... ...= {\cal S}_{RD} \, {\bf P}, \quad B = {\cal S}_{RD} \, {\bf P}$$

Genetic Operators

The most commonly used genetic operators are n-point mutation (${\cal M}_n$), crossover (${\cal C}$) and reproduction (${\cal R}$). The simulation parameters $m$, $c$ and $r$ declare on how many selected individuals of the parent generation ${\bf P}$ each operator is applied to produce the child generation ${\bf P}'$.

$${\bf P}_{k+1}={\bf P}'_k \quad {\bf P}' = {\bf P}'_M \cup {\bf P}'_C \cup {\bf P}'_R$$

$${\bf P}'_M = \{{\cal M}\,S \,\vert\, S \in {\bf P}_M \}, \; ... ...}, \; {\bf P}'_R = \{{\cal R}\,S \,\vert\, S \in {\bf P}_R \}$$

$${\bf P}_M = {\cal S}_m \,{\bf P}, \quad {\bf P}_C = \bigcup_... ...,{\cal S}\,{\bf P})\}, \quad {\bf P}_R = {\cal S}_r \,{\bf P}$$

$$\mbox{with} \quad m+c+r=p, \quad c \bmod 2=0, \quad p=\vert{\bf P}\vert=\vert{\bf P}'\vert$$

In the following definitions, the function $\mbox{\rm rint}(l)$ returns a random integer between $0$ and $l-1$ and $A$, $B$ and $S$ are individuals with $A,B,S \in {\bf B}^l$.

Mutation

The operator ${\cal M}$ inverts one bit of the individual, the $n$-point mutation operator ${\cal M}_n$ applies ${\cal M}$ $n$ times. The parameter n can be fix for the whole simulation, or be chosen randomly each time the operator is applied. (In this project $n=1+\mbox{\rm rint}(N-1)$, where $N$ is a simulation parameter.)

$$S'={\cal M}\,S,\quad S'_i=\left\{ \begin{array}{cl} 1-S_i, ... ...\right. \quad r=\mbox{\rm rint}(l) \quad {\cal M}_n={\cal M}^n$$

Crossover

The operator ${\cal C}$ exchanges the chromosome strings of two individuals starting from a random index.

$$(A',B')={\cal C}\,(A,B)$$

$$(\forall\, i<r) \, (A'_i=A_i \,\wedge\, B'_i=B_i), \quad (\f... ... \, (A'_i=B_i \,\wedge\, B'_i=A_i), \quad r=\mbox{\rm rint}(l)$$

Reproduction

The operator ${\cal R}$ simply reproduces the individual.

$$S' = {\cal R}\,S, \quad S'=S$$

Footnotes

... used.²

In fact, the method is only equivalent if $f(A) = f(B) \, \Longleftrightarrow \, A=B$. They are, however, totally equivalent, if the ranks are determined by sorting.