GA Interface to Problems

From a theoretical point of view one is interested to compare different tasks $\tau \in \Gamma$ with regard to the applied genetic algorithm $ga()$ (e.g. to find a solution needs 'more time' for $\tau$ than for $\tau'$). One strategy to enable such comparisons is to translate all tasks into a common format. One very useful format is the binary format representing all information as binary strings. Because it can be proven that any kind of alphabet $\Sigma$ can be translated into a binary representation this requirement of a binary representation will no be a reduction of the general character of the approach.

From this follows that the only 'real work' which has to be done to apply a GA is the encoding of a task $\tau$ into a binary representation accompanied by the provision of an appropriate fitness function $fit()$^5.1. The fitness function has to encode the 'nearness' of a given (measurable) property to the set of 'good' properties $P^{+} \subseteq P$ where the working set $P'$ shall be 'processed' by $ga()$ in a way that there will be a point in time where ideally $P' \cap P^{+} = P'$. Every fitness function has to obey some ordering thus that for any $x,y \in rng(fit)$ we have $(x < y) \vee (x = y) \vee (y > x)$.

Figure 5.10: Example 5-Queens-Problem: Encoding for a GA

Example:

Figure 5.10 shows the example of the 5-Queens-Problem as a 2-dimensional space with objects in a grid required not to collide according to the 'queens rule' of the chess game^5.2. This spatial situation is first encoded into a vector of numbers representing the columns with queens following the direction from 'top' to down'. This encoding is then further encoded into a binary representation. The primary information string has then the length $n=15$, which allows $2^{15}$ many different strings; this gives us the ideal set $P$. The simple fitness function counts the number of queens involved in a 'collision' according to the queens rule.