GA with Multicompartment Genomes

Figure 3.37: Generic GA Template

In figure 3.37 the case of Genomes with multiple compartments is described. A population $\cal{P}$ consists of pairs of genomes $\gamma_{i}\in 2^l$ with $l$ as length of the binary genomes accompanied with fitness values $\phi_{i} = f_{i}(\gamma_{i})$ written as $(\gamma_{i}, \phi_{i})$. The fitness function $f_{i}$ extracts information from a world $\cal{W}$ in such a way, that the set of fitness values $\Phi$ can be ordered. If the set $\Phi$ is unordered, then it is not possible that the genetic operator $go = \mu \oplus \kappa \oplus \sigma$ with $\mu$ as mutation, $\kappa$ as crossover and $\sigma$ can generate a population which is moving towards a goal.

An example with a simple fitness function $f_{1}= x^2$ with an ordered range was given in the introductory section 3.3.2.

In the following we show a simple world $\cal{W}$ which is once interpreted with a fitness function $f_{2a}$ = goal if $\gamma_{i} \in \cal{W}$ else = rand(0,upper), which generates an unordered set of fitness values and a fitness function $f_{2b}$ = $\sum_{j}f_{2a.j}$, which generates an ordered set of fitness values.

The world $\cal{W}$ is generally assumed as a world built up as a table mapping one set of values $D$ into another set of values $R$. This can be e.g. the pictures of objects associated with with language expression of some language. The objects are encoded as binary numbers of some length as well as the words. The number of bits $l$ depends on the amount of values needed.

Other possible interpretations of the table are that of a finite function or as the program of a finite state automaton. In the latter case one can look to this kind of genetic algorithm as an example of evolutionary programming. In this case one can implement additional fitness functions by placing the automata into a certain world where they can do some work which implies some special feedback.

The following experiments assume two different worlds: a world $\cal{W}$$_{1}$ with only three pairs of object - word with each two bits and a world $\cal{W}$$_{2}$ with 6 pairs each with three bits.

In case of world $\cal{W}$$_{1}$ each genome of the population encodes exactly one pair, while in case of world $\cal{W}$$_{2}$ each genome encodes as many pairs as are in the world. Thus one genome can represent a whole program on its own. It is then shown that world $\cal{W}$$_{1}$ with fitness function $f_{2a}()$ generates an unordered set of fitness values while world $\cal{W}$$_{2}$ with fitness function $f_{2b}()$ generates an ordered set. An unordered set of fitness values produces a non-stable behavior of the population while the ordered set of fitness values drives the population steadily towards an optimum.

For the examples see the technical appendix with GA examples.