\subsection{Schematheorie}
\label{sec:schema}
Der Begriff des Schemas wurde von John \citet{holland:75} zur formalen Beschreibung
der von ihm untersuchten Vorg"ange in adaptiven Systemen eingeführt.
Hollands Definition des Schemas ist ein Muster, welches eine
Menge von Strings definiert, indem es Bits an bestimmten Positionen
im String festlegt. Zur Veranschaulichung kann man sich ein Schema als Schablone vorstellen,
die "uber die einzelnen Strings gelegt und auf "Ubereinstimmung getestet wird.
Die urspr"ungliche Definition bezog sich auf den
einfachen \textit{kanonischen} Genetischen Algorithmus, mit bin"aren
Individuen bzw. Strings und Ein"=Punkt"=Crossover, wie er in Abschnitt \ref{sec:gafunction}
vorgestellt wurde. Sp"ater wurde die Schematheorie von anderen
Autoren unter anderem auf nicht-bin"are L"osungsrepr"asentationen
verallgemeinert. Hier wird das
ursprüngliche Konzept dargestellt, wie es u.a. in \citet{holland:86,holland:92}
zu finden ist.

Die zentrale Aussage der Schematheorie ist, dass sich Schemata mit bestimmten Eigenschaften in evolutionären
Prozessen (wie z.B. Genetischen Algorithmen) besser durchsetzen können als andere. 
Im Zusammenhang der vorliegenden Arbeit ist die Schematheorie relevant, weil sich die Idee der Schemata
auf die Klassifikatoren der bauenden Wespenagenten übertragen lässt und die aus ihr folgenden Überlegungen
in die Konzipierung des LCS miteinfließen.

Legt man eine binäre Codierung zugrunde, das heißt f"ur jeden String~$\vec{a}$
mit L"ange~$L$ gelte
\[
\vec{a} \in (0,1)^{L}
\]
so gilt f"ur ein Schema~$H$ analog
\[
H \in (0,1,*)^{L}
\]

Ein Schema kann somit f"ur jedes der $L$ Bits entweder festsetzen, dass es 0 oder 1
sein muss, oder aber mittels des \textit{don't-care-Symbols}~\textasteriskcentered ~anzeigen, dass
der Wert des entsprechenden Bits für das Schema nicht relevant ist.
Ein String, der einem Schema~$H$ entspricht, wird Instanz von $H$ genannt.
Hierbei kann jeder beliebige bin"are String mit L"ange~$L$ Instanz von genau $2^{L}$
Schemata sein, da f"ur jedes Bit im String gilt, dass es im korrespondierenden Schema
entweder gleich oder egal sein muss. % (d.h. 0 bzw. 1 oder *).

Man betrachte beispielsweise Strings der L"ange $L = 5$ und das Schema
$H_{1} = $~\texttt{\textasteriskcentered1\textasteriskcentered10}. Dieses Schema
steht f"ur alle Individuen mit L"ange $L = 5$, deren zweites Bit eine 1, viertes Bit eine 1 und
f"unftes Bit eine 0 ist. Dies entspricht der folgenden Menge von Individuen: $\{ 01010, 01110, 11010, 11110 \}$.
Diese vier Individuen sind also \textit{Instanzen} des Schemas $H_{1}$.
Wichtig ist hierbei zu verstehen, dass jedes Individuum Instanz verschiedener Schemata sein kann. So sind alle
Instanzen des Schemas $H_{1}$ auch gleichzeitig Instanzen des Schemas
$H_{2} = $~\texttt{\textasteriskcentered1\textasteriskcentered1\textasteriskcentered}. Die Menge aller
Instanzen von $H_{1}$ ist eine echte Teilmenge aller Instanzen von $H_{2}$, da $H_{2}$ ein Bit weniger
definiert als $H_{1}$.

In diesem Zusammenhang wird die \textit{Ordnung} $o(H)$ eines Schemas $H$ als Anzahl der in $H$ festgelegten
Bits definiert. Beispielsweise ist $o(H_{1}) = 3$ und $o(H_{2}) = 2$. Als weitere Eigenschaft wird die 
\textit{definierende L"ange} $\delta (H)$ eines Schemas $H$ als Abstand zwischen erstem und letztem vorgegebenen Bit
festgelegt, also $\delta (H_{1}) = 5 - 2 = 3$ und $\delta (H_{2}) = 4 - 2 = 2$.

So wie in Abschnitt \ref{subsec:bewertung} die Fitness eines einzelnen Individuums definiert wurde,
kann ebenso die Fitness eines Schemas bewertet werden.
Es bezeichnet hierbei $I(H)$ die Menge aller m"oglichen Instanzen von $H$, $P(t)$ die Population zum Zeitpunkt $t$
und $N(H,t)$ die tats"achliche Anzahl von Instanzen von $H$ in der Population zum Zeitpunkt $t$.

Die durchschnittliche Fitness aller Instanzen von $H$ zum Zeitpunkt $t$ wird folgenderma"sen berechnet:

\begin{equation}
 F(H,t) = \dfrac{\sum F(\vec{a}(t))}{N(H,t)} \quad \textnormal{für alle} \quad \vec{a}(t) \in I(H) \cap P(t)
\end{equation}

F"ur eine Anzahl von $\mu$ Individuen in der Population ergibt sich die durchschnittliche Fitness
$\overline{F}(t)$ aller Individuen in $P(t)$:

\begin{equation}
 \overline{F}(t) = \frac{1}{\mu} \cdot \sum \limits_{i=1}^{\mu} \vec{a}_{i}(t)
\end{equation}

Im Verh"altnis von $F(H,t)$ zu $\overline{F}(t)$ dr"uckt sich nun implizit die Qualit"at oder Fitness
des Schemas $H$ aus. Unter Vernachl"assigung externer Einflussfaktoren wie Mutation und Crossover ergibt sich f"ur
die Anzahl der Instanzen von $H$ in der n"achsten Generation folgende Differenzengleichung:

\begin{equation}
\label{schema:1}
 N(H,t+1) = N(H,t) \cdot \dfrac{F(H,t)}{\overline{F}(t)}
\end{equation}

Dies bedeutet, dass das Verh"altnis von $F(H,t)$ zu $\overline{F}(t)$ dar"uber bestimmt, ob sich ein
Schema $H$ in einer Population durchsetzt oder nicht. Falls die durchschnittliche Fitness der Instanzen eines
bestimmten Schemas $H$ "uber dem Durchschnitt aller Individuen liegt ($F(H,t) > \overline{F}(t)$), so
wird die Anzahl der Instanzen dieses Schemas von einer Generation zur n"achsten zunehmen und über die Zeit
exponentiell wachsen.
Gilt dagegen $F(H,t) < \overline{F}(t)$, so kann man eine Verminderung der
Instanzen von $H$ in der n"achsten Generation sowie eine exponentielle Abnahme im zeitlichen Verlauf erwarten.

Durch Mutation und Cross\-over wird das "Uberleben einzelner Individuen und demzufolge bestimmter Schemata zus"atzlich
beeinflusst. Die Wahrscheinlichkeit, dass ein Schema $H$ eine Mutation bzw. ein Ein"=Punkt"=Cross\-over "uberlebt,
kann "uber die
Ordnung~$o(H)$ und die definierende L"ange~$\delta (H)$ berechnet werden.

Wie bereits erw"ahnt, wird bei der Mutation jedes Bit stochastisch unabh"angig mit der Mutationswahrscheinlichkeit
$p_{mut}$ invertiert. Die Wahrscheinlichkeit, dass ein einzelnes Bit eines Schemas $H$ einen Mutationsschritt "uberlebt,
ist daher $1 - p_{mut}$, und f"ur das gesamte Schema $H$ mit $o(H)$ Bits ergibt sich folgende "Uberlebenswahrscheinlichkeit
bei der Mutation:
\[
 p_{\text{mu\_survive} }(H)=(1-p_{mut})^{o(H)}
\]
F"ur $p_{mut} \ll 1$, also eine sehr geringe und in der Praxis oft gegebene Mutationswahrscheinlichkeit gilt n"aherungsweise:
\begin{equation}
\label{schema:2}
 p_{\text{mu\_survive} }(H)=(1-p_{mut})^{o(H)} \approx 1-p_{mut}\cdot o(H)
\end{equation}
Die Weiterverbreitung eines Schemas wird aber nicht nur von der Mutation, sondern auch vom \textit{Crossover} bedroht.
Betrachtet man als
einfachste Variante das \emph{Ein"=Punkt"=Cross\-over}, so wird ein Schema $H$ durch das \textit{Cross\-over}
genau dann zerst"ort, wenn
ein \textit{Cross\-over"=Punkt} zwischen erstem und letztem definierendem Bit des Schemas gew"ahlt wird.
Auf der anderen Seite muss der Fall
ber"ucksichtigt werden, dass beide Eltern Instanzen von $H$ sind, da das Schema dann auch bei einem Austausch bestehen bleibt.
F"ur eine allgemeine Cross\-over"=Wahrscheinlichkeit~$p_{xover}$ und eine Population von $\mu$ Individuen mit Stringl"ange $L$
ergibt sich f"ur $H$ folgende "Uberlebenswahrscheinlichkeit beim Ein"=Punkt"=Crossover:
\begin{equation}
\label{schema:3}
 p_{\text{xo\_survive} }(H)=1-p_{xover} \cdot \dfrac{\delta(H)}{L-1} \cdot (1-\dfrac{N(H)}{\mu})
\end{equation}

Bei großen heterogenen Populationen ist die Wahrscheinlichkeit für den Fall, dass beide Elternindividuen
Instanzen des Schemas $H$ sind, vergleichsweise gering. Somit
ist die Zahl der Individuen, die ein Schema $H$ repräsentieren,
im Vergleich zur Gesamtpopulation sehr gering. Es gilt also $N(H) \ll \mu$ und daraus resultierend
$1 - \dfrac{N(H)}{\mu} \approx 1$.
Als vereinfachte Näherung für Gleichung \ref{schema:3} wird daher auch folgende Gleichung verwendet:
\begin{equation}
 \label{schema:3a}
 p_{\text{xo\_survive} }(H)=1-p_{xover} \cdot \dfrac{\delta(H)}{L-1} \cdot (1-\dfrac{N(H)}{\mu}) %
 \approx 1-p_{xover} \cdot \dfrac{\delta(H)}{L-1} 
\end{equation}

Aus den Gleichungen \ref{schema:1}, \ref{schema:2} und \ref{schema:3} l"asst sich die Ungleichung zusammensetzen, die
als \textit{Hollands Schematheorem} \citep{holland:92} bekannt wurde:
\begin{equation}
 \label{schema:exakt}
 N(H,t+1)\geq N(H,t)\cdot \dfrac{F(H,t)}{\overline{F}(t)}\cdot [1-p_{xover}\cdot \dfrac{\delta(H)}{L-1} %
 \cdot (1-\dfrac{N(H)}{\mu})]\cdot(1-p_{mut})^{o(H)}
\end{equation}

Um die Gleichung \ref{schema:exakt} zu vereinfachen, werden die Näherungsgleichungen \ref{schema:2} und \ref{schema:3a}
verwendet, woraus die folgende Version des Schematheorems resultiert:
\begin{equation}
 \label{schema:approx}
 N(H,t+1) \geq N(H,t) \cdot \dfrac{F(H,t)}{\overline{F}(t)} \cdot [1-p_{xover}\cdot \dfrac{\delta (H)}{L-1} %
 -p_{mut} \cdot o(H)]
\end{equation}

Die zentralen Aussagen des Schematheorems sind:
\begin{enumerate}
 \item Schemata mit "uberdurchschnittlicher Fitness ($F(H,t) > \overline{F}(t)$) "uberleben mit h"oherer
 Wahrscheinlichkeit.
 \item Je kleiner die Ordnung $o(H)$ des Schemas, desto h"oher die "Uberlebenswahrscheinlichkeit
 \item Je k"urzer die definierende L"ange $\delta (H)$, desto h"oher die "Uberlebenswahrscheinlichkeit
\end{enumerate}

Eine h"ohere "Uberlebenswahrscheinlichkeit bedeutet gleichzeitig, dass sich die Instanzen des betreffenden Schemas
gegen andere Individuen besser durchsetzen k"onnen.
Instanzen von Schemata mit "uberdurchschnittlicher Fitness, niedriger Ordnung und kurzer definierender
L"ange nehmen im Laufe mehrerer Generationen exponentiell zu.

\citet{goldberg:89} nannte diejenigen Schemata mit oben angef"uhrten Eigenschaften
\textit{building~blocks}
und formulierte die anschauliche aber inzwischen umstrittene \textit{Building"=Block"=Hypothese}, welche besagt,
dass ein Genetischer Algorithmus seine endg"ultige L"osung aus einzelnen \textit{building~blocks} zusammensetzt:

\begin{quotation}
 "`Because highly fit schemata of low defining length and low order play such an important role in the action of genetic
 algorithms, we have already given them a special name: building blocks. Just as a child creates magnificent fortresses
 through the arrangement of simple blocks of wood, so does a genetic algorithm seek near optimal performance through the
 juxtaposition of short, low"=order, high"=performance schemata, or building~blocks."' \citep[S.41]{goldberg:89}
\end{quotation}

Der von Goldberg hier benutzte Vergleich eines Genetischen Algorithmus mit einem Kind, das komplexe Gebilde aus vielen
kleinen Holzkl"otzen erschafft, veranschaulicht sehr klar auch den zentralen Kritikpunkt an der Building"=Block"=Hypothese:
sie vereinfache die Funktionsweise des GA zu stark. Kritiker sehen den Fehler unter anderem darin, dass
vorausgesetzt wird, das vom GA zu l"osende
Problem lie"se sich in voneinander unabh"angige Teilprobleme aufspalten, was in der Realit"at eher die Ausnahme darstellt.
