GA without Phenotype

Taking the introductory example of Goldberg [122] in the preceding chapters we can generalize this example a bit more.

Figure 5.1: Simple example with world, fitness-function, and population

We assume a world $W$ consisting of events $E$ $E=\{1,2, ..., n\}$. These events can be produced by a population $POP \subseteq P$ ($POP$ in the following abbreviated as $P'$) or - in simple cases - a member of the population $P'$ as such is an event $e \in E$.

The set $P$ represents the set of all possible patterns, which can be represented within a population (E.g.: If we use binary encoding of information then a population with a length of $l=2$ would have $2^{2} = 4$ many possible patterns. Thus $\vert P_{2}\vert= 2^{2} = 4$.). The set of all possible combinations of information length $l$ $P_{l}$ is usually only a theoretical concept compared to the real population $P'$, which therefore is usually only a subset of this theoretical set $P$ (E.g.: The set $P' = \{\langle0 0\rangle,\langle 0 1\rangle\}$ is a subset of $P_{2}$.).

The fitness function $f$ maps these events into some value space $V$ like $f: E \longmapsto V$. This value space $V$ has to follow some ordering relation $ORD$ with $(v,v') \in ORD$ (like $4 < 5$). Thus with the fitness function $f$ one can compute for every member $p_{i}$ of the set $P$ a fitness value $f(p_{i})$. These fitness values can be ordered. Corresponding to their 'size' do these values indicate the success of an individual and summed up the success of the real population $P' \subseteq P$ as a whole.

The individuals with the least success will be suppressed and those with the highest success will be supported. This is a selection process - also often called 'recombination' - with a selection function $sel$ mapping the old population $P'_{old}$ in a new population $P'_{new}$.

After this selection one can apply a mating function which works like a mixing function usually called crossover. During such a crossover-mixing one takes two individuals $p,p'$ of $P'_{old}$, takes a random position $k$ in these individuals and cuts all positions from $k$ to the end of the individual and exchanges these marked parts of each individual with each other. Thus $p=\langle 0,0\rangle$ and $p'=\langle 0,1\rangle$ with $k=1$ would produce the 'new' members $p_{new}=\{ 0, 1\}$ and $p'_{new}=\{0,0 \}$. This does not change the overall fitness, and - as one can easily verify - the repetition of crossover in next cycles will not change this situation. Therefore crossover does not guarantee that a given set of informations can be mixed in a way that the whole set reaches the theoretical maximum. The crossover-set of a population $P'$ will be written as $Cross(P')$. Then we can state the postulate, that the difference between the Maximal Fitness Set of a real population $P'$ called $MXF(P')$ and the sum of the fitness values of a crossover-set $F(Cross(P'))$ can not be negative: $MXF(P') - F(Cross(P')) \ge 0$.

Because the idea is to reach the maximal values of fitness for a population $P'$ one has to allow an additional operation introducing new elements by random if crossover reaches its limits. These new elements can be 'bad' or can be 'good' according to the fitness function f. The probability to get some 'good' values depends in the general case from the ratio of 'still available' good values and 'already possessing' good ones. The 'proportion' depends from the number of elements as well as of the distribution of 'good' ones to 'bad' ones. Because we assume an ordering of the values based on the fitness function $f$ one can compute the amount of values which are 'better' in $P$ compared to the values in $P'$ as $good(P',P)$. Then we have the probability to get 'better' values than given in $P'$ as ProbGood= $\frac{\vert good(P',P)\vert}{\vert P\vert}$. The probability to get a bad value is then $ProbBad=1-ProbGood$. Thus if the population $P'$ becomes 'better' then $ProbGood$ decreases and $ProbBad$ increases. From this follows that a population $P'$ will never be 'constant' but will 'oscillate'. Thus in the case of a set $P'={\langle 0 0\rangle,\langle 0 0\rangle}$ compared to a set $P={\langle 0 0\rangle,\langle 0 1\rangle,\langle 1 0\rangle,\langle 1 1\rangle}$ we would have the set of 'directly available good values' in $P$ as $good(P',P)={\langle 0 1\rangle,\langle 1 0\rangle,\langle 1 1\rangle}$ with $\vert good(P',P)\vert=3$ and therefore ProbGood= $\frac{3}{4}$.

But this general considerations have to be re-considered because the mutation operator has the constraint that he has to operate on the set of available patterns in $P'$, e.g. $P'={\langle 0 0\rangle,\langle 0 0\rangle}$. Mutation can - usually - change only one position of l-many. The probability to change $p$ to a 'better' value depends therefore from the probability of a 'positive' change in the actual pattern $p$. In case of binary encoding only a change from '0' to '1' can increase the value. Thus the proportion of 'zeros' to 'ones' $pp=\frac{\vert zeros\vert}{l}$ if $\vert zeros\vert > 0$, otherwise $pp=0$. The complement of bad values is $pn=1-pp$. Thus a single pattern would oscillate between high probabilities for improvements and high probabilities for becoming weaker.

If we allow only one mutation in the whole population then we have a disjunction of all the available values $pp_{1} \vee ... \vee pp_{n}$

In a set of patterns which are in the beginning randomly distributed the probabilities for becoming better oder becoming more worse should be 'equal'. But because selection supports the 'better' ones the distribution will be forced to a greater 'uniformity' having more 'good' values than 'bad' ones. When such a process of increasing uniformity happens then the overall probabilities would tend to behave more and more 'monotonously'.

The 'combined effect' of selection and mutation then should be that a whole population should 'oscillate' between a 'good' and a 'bad' population.

To overcome the drawback of falling back again the population should have some protection mechanisms to inhibit mutations to become effective if the result of the mutations is weaker than the given patterns. In artificial devices built intentiously by some experts this is possible.

To sum up some of the assumed constraints:

1. Crossover needs at least $n \ge 2$ positions to be applied.
2. There must be at least two individuals $p,p'$ which differ in at least one position, that crossover induces a change.
3. A crossover-induced-change can individually increase the value or decrease it, but the sum of both values stays the same. Therefore crossover is redundant with regard to the sum of all values in a population $P'$.
4. If it holds that for the population $P' \subseteq P$ the sum of all fitness values $F(P')$ is less than the maximum fitness values $MXF(P')$ then crossover alone can not improve the value $F(P')$ of a population $P'$.

Remark: This 'Generalization No.1' is - as the number '1' indicates - not the only and not the 'last' version, how one can generalize the problem of genetic algorithms. Therefore look please to further versions of these generalizations. Especially the statement ``the sum of both values stays the same. Therefore crossover is redundant with regard to the sum of all values in a population $P'$'' is not completely true. This will be discussed in the 'Generalizations No.2' (see 5.4).

Illustrating these ideas step by step.