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


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 game5.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.

Gerd Doeben-Henisch 2013-01-14