\section{Learning Classifier Systems}
\label{sec:lcs}
Da die Agenten des implementierten Simulationsmodells nach dem Vorbild der \emph{Learning Classifier Systems} entworfen wurden,
wird die Funktionsweise dieser Systeme im Folgenden erläutert.
Lernende Klassifizierende Systeme (\textit{LCS}, engl. \emph{Learning Classifier Systems}) gehen wie die
Genetischen Algorithmen zurück auf Arbeiten von \citet{holland:76}.
LCS wurden als regelbasierte Systeme für Maschinelles Lernen konzipiert, die ihr Verhalten
durch Verarbeitung von Rückmeldungen aus ihrer Umgebung optimieren sollen.
Interessant sind LCS für die Lösung von Problemen, deren Bewertung nicht sofort nach einer einzelnen Aktion, sondern
erst nach mehreren Aktionsschritten erfolgen kann. 

\begin{figure}[!ht]
 \centering
 \includegraphics[width=0.6\textwidth]{bernauer_animat}
 \caption[Das Animat-Problem \citep{bernauer:07}]{Illustration des Animat-Problems \citep{bernauer:07}}
 \label{animat}
\end{figure}
Ein einfaches Beispiel für derartige Fragestellungen ist das \emph{Animat-Problem}
\citep{bernauer:07}, bei dem es darum geht, dass eine Figur sich durch ein Labyrinth bewegt und auf schnellstem Weg
zu einem Ziel kommen soll (Abbildung \ref{animat}). Die Figur bekommt eine Belohnung, wenn sie das markierte Ziel erreicht.
Da sich die Figur in jedem Zeitschritt aber nur um ein Feld weiterbewegen kann, stellt sich die zentrale Frage, wie
die Figur lernen kann, dass vor Erreichen des Ziels und der Belohnung scheinbar sinnlose (weil unbelohnte) Schritte
ausgeführt werden müssen.

\begin{figure}[!hb]
 \includegraphics[width=\textwidth]{zirngibl_lcs}
 \caption[Schema eines \emph{Learning Classifier System} (nach \citet{bernauer:07})] %
  {Schematische Darstellung eines \emph{Learning Classifier System} (verändert, nach \citet{bernauer:07})}
 \label{lcsschema}
\end{figure}
Ein LCS besteht im Wesentlichen aus einem beliebig großen Satz von \emph{Klassifikatoren},
welche das Verhalten des
LCS steuern. 
Jeder Klassifikator $R$ besteht für sich aus einem \textit{Detektor-String} $B$, einem \textit{Effektor-String} $A$ und einem numerischen \textit{Stärkewert} $S$ (siehe Abbildung \ref{lcsschema}).
Für den Begriff \emph{Klassifikator} wird synonym auch der Begriff \emph{Regel} verwendet, deswegen wird die Menge aller im
LCS vorhandenen Klassifikatoren als Regelsatz $\mathcal{R}$ bezeichnet.
Nachrichten aus der Umgebung werden von \textit{Detektoren} angenommen und mit den Detektor-Strings der einzelnen Klassifikatoren
verglichen. Die Codierung und Länge der Nachrichten muss bekannt sein und mit den Detektor-Strings übereinstimmen.
Im einfachsten Fall wird eine binäre Codierung mit fester Stringlänge verwendet.

In LCS ist jede Regel mit einem numerischen Wert verknüpft, der ihre \textit{Stärke} oder auch
\textit{Fitness} definiert. Um Verwechslungen mit der globalen Fitness der Wabenstrukturen zu vermeiden
soll im Folgenden der Begriff \emph{Stärke} verwendet werden.
% Die Regeln werden im Kontext der LCS \textit{Klassifikatoren} genannt.
% In jedem Zustand des Systems wird von \citet{holland:76} außerdem jeder Regel ihre \textit{matching score}
% zugewiesen, die zusammenfasst, ob eine Regel zur erfassten Umgebung passt und auch, wie speziell die
% Regel ist. Konkret bedeutet das, dass die \textit{matching score} einer Regel 0 ist, wenn die Umgebung
% ihr widerspricht, und die Anzahl der definierenden Symbole (außer \textasteriskcentered),
% wenn sie zur Umgebung passt.
% Das führt dazu, dass die \textit{matching score} einer Regel umso höher ist, je spezieller sie den
% benötigten Input definiert. Außerdem wird jeder Regel ein Alterswert (\textit{age}) zugeordnet, der
% sich automatisch erhöht, falls die Regel nicht benutzt wird. Wird die Regel angewendet, wird das Alter 
% reduziert. Regeln sollen aus dem Regelpool gelöscht werden können, und die Wahrscheinlichkeit hierfür
% erhöht sich bei steigendem Alter der Regel.
% einerseits ihre durchschnittliche Nützlichkeit
% im bisherigen Simulationsverlauf (also wie oft die Regel bereits angewendet wurde), andererseits hängt 
Die \textit{Stärke} eines Klassifikators beeinflusst wesentlich die Wahrscheinlichkeit für seine Anwendung.
In Hollands Modell wird jedem erfüllten Klassifikator ein bestimmter Wert zugeordnet, der \textit{bid}
(dt. \emph{Gebot}) genannt wird. Holland vergleicht die Auswahl eines Klassifikators mit einer Auktion, in der
jeder passende Klassifikator ein Gebot abgibt und die Höhe des Gebots die Wahrscheinlichkeit
bestimmt, mit der der Klassifikator tatsächlich Anwendung findet. Außer von der Stärke $S(R)$ des Klassifikators $R$
ist $bid(R)$ noch abhängig von einem Wert, den Holland \textit{Spezifizität} $sp(R)$
nennt. Die Spezifizität des Klassifikators entspricht der Anzahl der Stellen in seinem Detektor-String $B$, die
an der entsprechenden Stelle im Input-String $I$ einen bestimmten Wert erwarten. Bei der hier verwendeten binären
Codierung entspricht das die Anzahl der Nullen und Einsen in $B$. Das sogenannte \emph{don't-care-Symbol}
bedeutet, dass der Wert von $I$ an dieser Stelle nicht relevant für die Regel ist. In Abbildung \ref{lcsschema}
wird das \emph{don't-care-Symbol} als \texttt{\#} bezeichnet, sonst meistens als \texttt{\textasteriskcentered}.
% , was in unserer konkreten Anwendung
% die Anzahl der signifikanten Nachbarzellen bedeutet. Eine Regel, die von der Belegung mehrerer
% Nachbarzellen abhängig ist, hat somit eine höhere Spezifizität als eine Regel, die nur von
% einer Nachbarzelle abhängt.

Sind in einem Zeitschritt mehrere Regeln gleichzeitig gültig, so wird anhand ihrer entsprechenden
\textit{bid}"=Werte entschieden, welche Regel zur Anwendung kommt. 
% Offen ist noch, wie das tatsächlich
%  implementiert wird. Sinnvoll wäre ein Ausschlussverfahren, in dem die Wahrscheinlichkeit für eine
%  Regel $r$ durch den Wert $bid(r)$ bestimmt wird.
Wird ein Input $I$ als \emph{passend} zu einem Klassifikator $R$ klassifiziert,
wird $R$ einer Liste von passenden Klassifikatoren (engl. \textit{match set}) $\mathcal{M}_{t}$ hinzugefügt. Nach einem
stochastischen Verfahren wird aus allen Klassifikatoren in $\mathcal{M}_{t}$ derjenige ausgewählt, der ausgeführt werden soll,
wobei der Stärkewert $S$ in diese Auswahl miteinfließt.
Der Effektor-String $A$ der
ausgewählten Regel bestimmt die von den Effektoren auszuführende Aktion des LCS.
Analog zu den Detektoren, die die "`Sinnesorgane"' des LCS repräsentieren,
bezeichnen Effektoren diejenigen Komponenten des LCS, die aktiv mit der Umwelt kommunizieren bzw. diese
manipulieren.

Von der Umgebung bekommt das LCS Rückmeldungen darüber,
wie das Verhalten des LCS zu bewerten ist. Eine positive Rückmeldung wird als \emph{Belohnung} und
eine negative Rückmeldung als \emph{Bestrafung} interpretiert.
Allerdings kommen diese Rückmeldungen im Allgemeinen nicht nach jeder einzelnen Aktion,
so dass das LCS dafür sorgen muss, die
positive bzw. negative Rückmeldung an die verantwortlichen Klassifikatoren zurückzugeben.
Ziel dieses Verfahrens ist es, dass sich das System
mit der Zeit an das erwünschte Verhalten anpasst, da der Stärkewert von Klassifikatoren
mit positiver Rückmeldung erhöht und von solchen mit
negativer Rückmeldung abgeschwächt wird. Positiv bewertete Regeln sollen in Zukunft mit höherer Wahrscheinlichkeit
ausgewählt werden als negativ bewertete.

% Bei den ersten Versuchen, Hollands ursprüngliches System praktisch zu implementieren, wurde das Konzept
% als zu kompliziert und schwierig realisierbar wahrgenommen, weil zu viele in der Praxis überflüssige
% Komponenten enthalten waren \citep{bull:05}.
% Daher schwand das Interesse an LCS für längere Zeit, bis \citet{wilson:94} eine vereinfachte und verständlichere
% Version des LCS veröffentlichte, die er \textit{zeroth-level classifier system} (ZCS) nannte.
% In seiner ersten Veröffentlichung des Systems XCS \citep{wilson:95} wurde der Ansatz des Credit Assignment in
% Learning Classifier Systemen
% grundlegend überarbeitet. Beide Systeme stellten grundsätzliche Neuerungen im Bereich der LCS dar und
% werden in Abschnitt \ref{sec:zcs} (ZCS) und \ref{sec:xcs} (XCS) kurz vorgestellt.
Im Folgenden werden die Bestandteile eines einfachen
Learning Classifier Systems formal eingeführt. Die Darstellung geht von einer binären
Codierung aus und orientiert sich an \citet{weicker:02}. Eine schematische Darstellung der Funktionsweise
ist in Abbildung \ref{lcsschema} zu sehen.

Ein Klassifikator $R$ besteht aus einer Bedingung (Detektor-String) $B$ der Länge $l$, einer Ausgabe (Effektor-String) $A$ 
der Länge $m$ und einem numerischen Stärkewert $S$. 
Jeder binäre Input-String $I$ hat wie der Detektor-String die Länge $l$.

Für jede Bedingung (Detektor-String) $B$ gilt:
\begin{equation}
 B \in \mathcal{B} = \{ 0,1,* \}^{l}
\end{equation}

Für jede Ausgabe (Effektor-String) $A$ gilt:
\begin{equation}
 A \in \mathcal{A} = \{ 0,1 \}^{m}
\end{equation}

Für jeden Stärkewert $S$ gilt:
\begin{equation}
 S \in \mathbb{R}
\end{equation}
Die Stärkewerte $S$ werden bei Initialisierung des Systems auf bestimmte Werte gesetzt,
was in der implementierten Version mit Zufallszahlen geschieht.

Jeder Klassifikator $R$ besteht also aus einer Bedingung $B$, einer Ausgabe $A$ und einem Fitnesswert $S$:
\begin{equation} 
 R = (B,A,S) \in \mathcal{B} \times \mathcal{A} \times \mathbb{R}
\end{equation}

Die Gesamtheit aller Klassifikatoren eines LCS wird Regelsatz $\mathcal{R}$ genannt:
\begin{equation}
 \mathcal{R} \subset \mathcal{B} \times \mathcal{A} \times \mathbb{R}
\end{equation}

Ein Klassifikator $R$ heißt genau dann \textit{aktiviert} oder \textit{passend} zum Zeitpunkt $t$, wenn die Eingabe $I$ zum
Zeitpunkt $t$ mit der
Bedingung des Klassifikators übereinstimmt. In diesem Zusammenhang bedeutet Übereinstimmung, dass jedes Zeichen des
Input-Strings $I$ dem entsprechenden Zeichen im Detektor-String $B$ entspricht, außer wenn bei $B$ an der Stelle ein
\textit{don't-care-Symbol}~\texttt{\textasteriskcentered }
steht, was bedeutet dass die Zeichen nicht übereinstimmen müssen. Formal geschrieben heißt das mit
$I \in \mathcal{I} = \{ 0,1 \}^{l}$,
dass ein Klassifikator $R$ zum Zeitpunkt $t$ mit Input $I$ aktiviert ist, wenn folgendes Prädikat wahr ist:

\begin{equation}
 \bigwedge_{i=1}^{l} ( B_{i} \neq * \Rightarrow B_{i} = I_{i} )
\end{equation}
$B_{i}$ bezeichnet das Zeichen an Stelle $i$ im Detektor-String $B$.

Alle zum Zeitpunkt $t$ aktivierten Klassifikatoren im Regelsatz $\mathcal{R}$ werden zum \textit{match set} $\mathcal{M}_{t}$
hinzugefügt.
Werden verschiedene Ausgaben von den Klassifikatoren in $\mathcal{M}_{t}$ vorgeschlagen,
so wird durch ein stochastisches Verfahren
für jede Ausgabe $A$ eine Auswahlwahrscheinlichkeit berechnet.
Diese berücksichtigt sowohl den
Stärkewert $S$ als auch die Spezifizität $sp$ aller Klassifikatoren $R$ in $\mathcal{M}_{t}$,
die $A$ vorschlagen. 
$sp$ ist die Anzahl der Zeichen in $B$,
die für die entsprechende Stelle in $I$ ein spezifizisches Zeichen verlangen. Grundsätzlich sind das alle Zeichen, die
kein \emph{don't"=care"=Symbol}~\texttt{\textasteriskcentered} sind. Es gilt z.B.
$sp$\texttt{(\textasteriskcentered\textasteriskcentered0011\textasteriskcentered\textasteriskcentered) = 4} und
$sp$\texttt{(101\textasteriskcentered\textasteriskcentered010) = 6}.
Je höher Spezifizität und Fitness von $R$ sind, desto höher ist die Wahrscheinlichkeit dafür, dass $R$ ausgewählt wird.

Das Gebot eines Klassifikators $R$ mit Stärke $S(R)$ berechnet sich wie folgt:
\begin{equation}
 bid(R) = S(R) \cdot \log_{2} [sp(R)]
\end{equation} 
Die Spezifizität wird logarithmisch in die Formel mit einberechnet, um ihren Einfluss gegenüber
der Stärke zu reduzieren.

% Im Modell von \citet{holland:86} gibt jeder Klassifikator $R$ in $\mathcal{M}_{t}$ ein Gebot
% (engl. \textit{bid}) ab, welches aus $sp(R)$ und dem momentanen Stärkewert $S(R,t)$ berechnet wird.
% Außerdem wird eine systemabhängige Konstante $\beta $
% einberechnet, womit für das Gebot für eine Regel $R$ zum Zeitpunkt $t$ gilt:
% \begin{equation}
%  bid(R,t) = \beta \cdot sp(R) \cdot S(R,t)
% \end{equation}
Die Aktion $A$ der so ausgewählten Regel wird ausgeführt, und das System wartet auf den nächsten Input $I$
zum Zeitpunkt $t+1$.

Learning Classifer Systeme kombinieren zwei grundlegende Mechanismen für Maschinelles Lernen \citep{bull:05}.
Beide Mechanismen adressieren jeweils ein grundlegendes Teilproblem, das in Zusammenhang mit LCS auftritt.
Das erste Teilproblem wird \textit{Credit Assignment} oder "`apportionment of credit problem"'
\citep{geyer:95} genannt und dreht sich um die Frage, wie das System entscheiden soll, welche der zu einem Zeitpunkt $t$
aktivierten Regeln zur Erreichung eines Ziels zu einem zukünftigen Zeitpunkt $t+n$ beigetragen haben und wie das positive
bzw. negative Feedback auf diese Regeln verteilt werden soll (siehe Abschnitt \ref{sec:reinf}).
Das zweite Teilproblem ist das Finden neuer Klassifikatoren
(engl. \textit{Rule Discovery}), wofür in LCS ein Genetischer
Algorithmus verwendet wird. Die Grundprinzipen Genetischer Algorithmen wurden bereits in Abschnitt \ref{sec:gafunction} erläutert,
wobei die Anwendung im Kontext der LCS in Abschnitt \ref{sec:ga_lcs} beschrieben wird.

\subsection{Credit Assignment: Reinforcement Learning}
\label{sec:reinf}
In einem Learning Classifier System werden die Fitnesswerte der einzelnen Klassifikatoren durch Rückmeldung aus der Umgebung
schrittweise angepasst, was \textit{Credit Assignment} genannt wird.
Das zugrundeliegende Verfahren heißt \textit{Reinforcement Learning (RL)} \citep{sutton:98} und basiert darauf,
dass Klassifikatoren mit positivem Effekt auf die Umgebung verstärkt und solche mit negativem Effekt abgeschwächt werden sollen.
Eine mögliche Definition von Reinforcement Learning lautet "` [\dots ] learning from interaction with an environment,
from the consequences of action, rather than from explicit teaching."' \citep{sutton:04}
Die Herausforderung für das System besteht darin, die Rückmeldung der Umgebung an alle beteiligten Klassifikatoren
zu verteilen, da normalerweise nicht nach einem einzelnen Zeitschritt beurteilt werden kann, ob der Gesamteffekt auf die Umwelt
positiv oder negativ ist. Sehr anschaulich wird dies bei Betrachtung eines Brettspiels wie Schach, wo oft erst nach sehr vielen Schritten
beurteilt werden kann, ob ein Zug zu Beginn des Spiels gut oder schlecht war.

\label{sec:bba}
Die im ursprünglichen
Modell von \citet{holland:75} eingesetzte Methode für das \emph{Credit Assignment} wurde
\textit{Bucket-Brigade-Algorithmus} (BBA) genannt. Das System merkt sich in
jedem Zeitschritt $t$ alle passenden nach $\mathcal{M}_{t}$ übertragenen Regeln.
Im nächsten Zeitschritt $t+1$ wird das Gebot jeder ausgewählten Regel
in einem sogenannten \textit{bucket} abgespeichert. Der Inhalt dieses \textit{bucket} wird dann
zu gleichen Teilen unter den in Zeitschritt $t$ aktivierten Regeln aufgeteilt \citep{bull:05}.
Das heißt,
der Stärkewert $S(R)$ wird mit dem entsprechenden Anteil des Inhalts des \textit{bucket} verrechnet.
Bekommt das System eine Rückkopplung aus der Umgebung, so wird diese Rückkopplung ihrerseits mit dem Stärkewert
der letzten aktivierten Regel verrechnet.

Holland modellierte den Bucket"=Brigade"=Algorithmus bewusst in Analogie zu einem Wirtschaftskreislauf. Das System kann als
Handelskette gesehen werden, in dem jede Regel als Geschäftspartner mit ihrer Stärke als Kapital agiert.
In den meisten neueren LCS-Varianten wie XCS \citep{wilson:95} wird ein RL-Algorithmus namens \textit{Q Learning} eingesetzt, der erstmals
von \citet{watkins:89} beschrieben wurde. 

\subsection{Rule Discovery: Genetische Algorithmen}
\label{sec:ga_lcs}
Das Finden neuer Klassifikatoren % (engl. \textit{Rule Discovery}) 
geschieht in Learning Classifier Systemen mithilfe
Genetischer Algorithmen (GA, siehe Abschnitt \ref{sec:ga}).
Es gibt verschiedene Möglichkeiten, den Genetischen Algorithmus im LCS einzusetzen, wobei grundsätzlich zwei
Varianten der LCS unterschieden werden: \textit{Pittsburgh-} und \textit{Michigan-}LCS \citep{sigaud:07}.
Pittsburgh-LCS, so genannt, weil der Ansatz von \citet{smith:80} an der University of Pittsburgh entwickelt wurde,
setzen, wie oben beschrieben, einen GA auf einer Population von Regelsätzen ein.
Im Gegensatz dazu betrachten Michigan-LCS, entwickelt von John Holland an der University of Michigan, den einzelnen
Klassifikator als Individuum. Es wird also nur ein einziger Regelsatz betrachtet, der für den GA eine Population von
Klassifikatoren darstellt, und der durch Reinforcement Learning und den Genetischen Algorithmus optimiert werden soll.
Im Folgenden wird die Pittsburgh-Variante für den Einsatz Genetischer Algorithmen in LCS beschrieben, da diese
im Rahmen der vorliegenden Arbeit für die Implementation verwendet wurde. 

In Pittsburgh-LCS operiert ein Genetischer Algorithmus auf einer Population von Regelsätzen.
Es werden mehrere Simulationsläufe
mit verschiedenen Regelsätzen durchgeführt und die Ergebnisse der Simulationen jeweils von einer
Fitnessfunktion $F$ bewertet. Das Ergebnis dieser Bewertung wird \emph{Globaler Fitnesswert}
oder englisch \textit{Overall Fitness} genannt.
Zu jedem verwendeten Regelsatz wird der erzielte globale Fitnesswert gespeichert.

Der GA wählt nun nach einem stochastischen Selektionsverfahren Regelsätze aus
und erzeugt durch Rekombination und Mutation (siehe Abschnitt \ref{sec:ga}) neue Regelsätze,
die dann im nächsten Durchlauf
getestet werden und im Idealfall bessere Ergebnisse erzielen.
Als Selektionsverfahren wird hier die \textit{Roulette"=Wheel"=Selektion} (siehe Abschnitt \ref{ga:selection})
verwendet, bei der die Wahrscheinlichkeit für die Auswahl
eines Individuums, also eines Regelsatzes $\mathcal{R}$, von seinem globalen Fitnesswert
$F(\mathcal{R})$ abhängt, also von der Rückmeldung der Umgebung.

% \subsection{ZCS: Zeroth-Level Classifier System}
% \label{sec:zcs}
% Als \citet{wilson:94} sein Learning Classifier System ZCS entwarf, hatte er vor allem im Sinn, ein leichter verständliches
% und gleichzeitig zu besseren Ergebnissen führendes LCS zu konzipieren \citep{bull:05}.
% Vor allem entfernte er dazu die interne \textit{message list} und das System der \textit{bids} aus dem LCS.
% Sobald ein \textit{match set} $\mathcal{M}_{t}$ für einen Zeitpunkt $t$ gebildet wurde, wird eine einzelne Regel $R$
% aufgrund ihres Fitnesswerts $F(R)$ stochastisch ausgewählt.
% Alle Regeln aus $\mathcal{M}_{t}$, die die gleiche Aktion vorschlagen
% wie $R$, bilden zusammen mit $R$ das \textit{action set} $[A]_{t}$. Im nächsten Zeitschritt $t+1$ profitieren alle Regeln
% in $[A]_{t}$ zu gleichen Teilen vom zurückgegebenen Feedback der Regeln im nächsten \textit{action set} $[A]_{t+1}$.
% 
% Die Rückgabe des Feedbacks funktioniert auch hier nach dem Prinzip des Bucket-Brigade Algorithmus.
% Ein fester Bruchteil des Fitnesswerts jeder Regel aus $[A]_{t}$ wird in einem \textit{bucket} deponiert.
% Da jeweils das vorhergehende \textit{action set} $[A]_{t-1}$ noch gespeichert bleibt, kann der Inhalt des \emph{bucket}
% zu gleichen Teilen auf alle Klassifikatoren aus $[A]_{t-1}$ aufgeteilt werden. Vorher wird der Inhalt des \emph{bucket}
% allerdings noch um eine vorher festgelegte Konstante $\gamma$ verringert.
% Die Fitnesswerte aller Regeln im match set $\mathcal{M}_{t}$, die nicht in $[A]_{t}$ sind, werden schließlich um
% eine festen Faktor $\tau$ verringert, was ihre Chance auf spätere Auswahl weiter verschlechtert.
% Mit einer konstanten Lernrate $\beta$ mit $0 \leq \beta \leq 1$ wird das \emph{Credit Assignment} bei ZCS formal
% folgendermaßen geschrieben:
% \begin{equation}
%  F([A]_{t}) = F([A]_{t}) + \beta \cdot [ bucket + \gamma \cdot F([A]_{t+1}) - F([A]_{t}) ]
% \end{equation}
% Bei ZCS wird in jedem Zeitschritt $t$ mit einer Wahrscheinlichkeit $p$ ein Genetischer Algorithmus auf den
% Regelsatz $\mathcal{R}$ angewendet, wobei der GA die einzelnen Klassifikatoren als Individuen betrachtet.
% Mittels Roulette-Wheel-Selektion werden zwei Regeln als Eltern ausgewählt und über die bekannten Mechanismen
% Rekombination und Mutation zwei neue Regeln erstellt. Jeweils die Hälfte des Fitnesswertes beider Elternindividuen
% wird an die neu erstellten Regeln abgegeben. Die neuen Klassifikatoren ersetzen ihrerseits zwei Regeln aus $\mathcal{R}$,
% die durch reziproke Roulette-Wheel-Selektion ausgewählt werden, was heißt, dass die Auswahlwahrscheinlichkeit desto
% höher ist, je kleiner der Fitnesswert ist.
% 
% \subsection{XCS}
% \label{sec:xcs}
% Die bedeutendste Weiterentwicklung bei XCS gegenüber klassischen Learning Classifier Systemen besteht in der Art und Weise,
% wie die Stärkewerte der einzelnen Klassifikatoren berechnet werden.
% Wurde die Stärke eines Klassifikators $R$ vorher üblicherweise
% über die Höhe der eingehenden Rückmeldung berechnet, so wird sie bei XCS durch die Genauigkeit bestimmt, mit
% der der Klassifikator die erhaltene Rückmeldung von der Umgebung vorhersagt \citep{bull:05}. 
% Aufgrund dieses Unterschiedes haben sich die Begriffe \emph{stärkebasiertes LCS} und
% \emph{genauigkeitsbasiertes LCS} durchgesetzt.
% Da im Rahmen dieser Arbeit ein rein stärkebasiertes System implementiert wurde, wird im Folgenden nicht näher auf
% XCS eingegangen.
