From Multicompartment Genomes to Classifiers

In the text below classifier systems will be introduced. In some sense one can understand multicompartment genomes as classifiers by interpreting one single compartment as an if-then rule. We will discuss here a bit the transformation of a multicompartment genome into a classifier system and how a fitness function can be constructed for such a system. We will do a case study using the simple game 'tic tac toe' as an example (cf. diagram 3.38).

Figure 3.38: Idea for the Construction of a Classifier System

The following points characterize a classifier system compared to a multi-compartment genome:

1. The population POP consists of genomes which are binary information strings with the implicit structure $\langle IF-Part THEN-Part FITNESS \rangle$.
2. The $IF-Part$ represents the input from some world $W$ and the input includes information which can be used as fitness value. The input presupposes a function $ainp: W \longmapsto A$ where $A$ represents an agent which uses the population of information strings as its knowledge model of the world.
3. The $THEN-Part$ represents a possible output of the system into the world $W$ which can be interpreted as an action which can change the state of the world. The output presupposes also a function $aout: A \longmapsto W$.
4. The $FITNESS$ part represents some fitness value $\phi \in \Phi$ to qualify the importance of this if-then rule for the whole system.

Independent of the problem to be learned one can state that the set of fitness values $\Phi$ must be ordered in a way that it holds for all $\phi_{i}, \phi_{j} \in \Phi$ that $\phi_{i} \leq \phi_{j}$. Only then can a system using the fitness values as inputs use these fitness values as a guide to navigate from the 'lower' values to the 'higher' values, thereby 'approaching' the goal states more and more. Because the fitness function $f$ is a mapping from the set of possible world states $\cal{W}$ into the set of fitness values $f:\cal{W}$ $\longmapsto \Phi$ one can interpret all those world states $w_{j} \subset \cal{W}$ which have the same fitness value $\phi_{i}$ as 'equivalent' with regard to this fitness value, thus inducing a kind of equivalence classes $w_{j.\phi_{i}}$. From this follows that the set of fitness values $\Phi$ should contain at least two different values $\Phi = \Phi_{g} \cup \Phi_{ng}$ with $\Phi_{ng} = \Phi - \Phi_{g}$.

The challenge for every problem $\cal{P}$ is then to find a fitness function $f$ whose domain includes exactly those properties which are important for a LCS system to change its classifiers appropriately.