\chapter{Methode}
\label{sec:methode}
Um eine Antwort auf die in Abschnitt \ref{sec:complexity} erläuterte Frage zu erhalten,
wurde im Rahmen dieser Arbeit eine Simulationsumgebung entwickelt.
Ziel der damit durchgeführten Simulationsläufe war es zu klären,
ob die Vorgänge beim Wabenbau von Insekten auf ein
Modell übertragbar und inwieweit die Ergebnisse
eines solchen Systems mit realen Insektennestern vergleichbar sind.
Aufgrund der Größe des Zustandsraumes der Problemstellung ist eine direkte Berechnung
der optimalen Lösung nicht praktikabel (siehe Abschnitt \ref{sec:complexity}), weswegen
eine Simulationsumgebung auf Basis Lernender Klassifizierender Systeme entwickelt wurde.
Zur Veranschaulichung der Ergebnisse wurde außerdem eine graphische
Darstellung der durch die Simulation entstandenen Wabenstrukturen realisiert.

Da Begriffe wie \emph{Population} und
\emph{Individuum} sowohl im Kontext staatenbildender Insekten als auch in der Nomenklatur der Genetischen Algorithmen
eine zentrale Bedeutung besitzen, ist es wichtig, klar voneinander abzugrenzen, was die Bedeutung welchen Begriffes
im jeweiligen Zusammenhang ist.
Ein Insektenstaat - natürlich wie simuliert - besteht aus einer Menge von Insekten. Das einzelne Insekt wird
als \textit{Individuum}, die Gesamtheit aller Individuen als \textit{Population} bezeichnet. Im Kontext des
Simulationsmodells
wird das simulierte Insekt vorwiegend als \textit{Agent} bezeichnet, um Verwechslungen zu vermeiden.
Ein Genetischer Algorithmus arbeitet ebenfalls mit einer Population von Individuen,
wobei die interne Repräsentation eines
Individuums \textit{Genotyp} und die von ihm vorgeschlagene Problemlösung \textit{Phänotyp} genannt werden.

In diesem Kapitel werden die Komponenten des implementierten Modells im Einzelnen beschrieben.
Sofern Bezug auf den in Anhang \ref{matlab} beigefügten MATLAB-Quellcode genommen wird,
bezeichnen in \texttt{Schreibmaschinenschrift} geschriebene Wörter die entsprechenden
Variablen- oder Funktionsnamen. \texttt{\textless dateiname\textgreater .m} bezeichnet die entsprechende Datei.

\section{Benutzte Werkzeuge}
\label{sec:werkzeuge}
Die Simulationsumgebung wurde in MATLAB\textsuperscript{\textregistered} ~7.7.0.471~(R2008b) implementiert und
die Simulationen auf einem PC mit 2~Giga\-byte RAM und Ubuntu
mit Linux-Kernel 2.6.28 als Betriebssystem durchgeführt.
MATLAB ist eine proprietäre Skriptsprache mit Möglichkeit zu objektorientierter Programmierung und umfangreicher
graphischer Darstellung.

\section{Konzept des Simulationsmodells}
\label{sec:simkonzept}
Zur Simulation des Wabenbaus wurde ein \textit{zeitdiskretes} Simulationsmodell implementiert.
Zeitdiskrete Simulationsmodelle zeichnen sich dadurch aus, dass Änderungen des
Systemzustands nur zu bestimmten, diskreten Zeitpunkten betrachtet werden
und der Systemzustand zwischen den diskreten Zeitpunkten für die Simulation als konstant
angenommen wird  \citep{page:00}. Konkret bedeutet das in diesem Modell,
dass jeder Agent pro Zeitschritt einen neuen Baustein bauen und sich danach um
eine festgelegte Schrittweite auf der Wabe in eine zufällig gewählte Richtung bewegen kann.
Im nächsten Zeitschritt ist der Baustein gebaut und der Agent befindet sich auf seiner neuen
Position, die verstrichene Zeit wird nicht direkt berücksichtigt.
Hierin unterscheiden sich diskrete Simulationsmodelle
von \textit{kontinuierlichen} Modellen, bei denen sich der Systemzustand stetig
über die Zeit ändert.
\begin{figure}[!ht]
 \centering
 \includegraphics[width=0.5\textwidth]{sechs_waben_klein}
 \caption[Ergebnis einer Simulation nach sechs Bauschritten] %
  {Eine begonnene Simulation nach sechs Bauschritten. Der schwarze Baustein markiert die Ausgangswabe, %
   die roten und grünen Steine markieren die gebauten Zellen von Typ 1 (rot) und Typ 2 (grün). Der kleine blaue Punkt %
    auf der schwarzen Zelle markiert die Position des Agenten.}
 \label{bild:kleinewabe}
\end{figure}

\section{Programmierung der Simulationsumgebung}
\label{sec:simumgebung}
Das Skript \texttt{simulationsumgebung.m} stellt das Rahmenwerk für den gesamten Simulationsablauf
zur Verfügung. Hier wird der Simulationsraum und die Bauagenten als Modelle der nestbauenden Insekten
erzeugt. Auch die global geltenden Parameter werden hier eingestellt.
Bei Ausführung des Skripts wird eine von den angegebenen Parametern abhängige Anzahl von Simulationsläufen
gestartet.
Über den zweidimensionalen kontinuierlichen Raum wird eine Struktur aus regelmäßigen Sechsecken gelegt,
welche den Raum in gleich große Zellen aufteilt. 
Die Größe des Raumes ist frei wählbar und wird vom Sechseckgitter maximal ausgenutzt.

\begin{figure}[!ht]
 \centering
 \includegraphics[width=0.5\textwidth]{gitter_initial}
 \caption{Initialzustand der Simulation mit bebauten Anfangszellen}
 \label{gitter_initial}
\end{figure}
Auf jedem sechseckigen Feld des Gitters können verschiedene Arten von Wabenzellen gebaut werden, die
in der graphischen Darstellung mit verschiedenen Farben markiert werden (siehe Abschnitt \ref{sec:grafik}).
Vor Beginn der Simulation
werden sieben Zellen in der Mitte des Gitters als Ausgangspunkt mit Bausteinen vom Typ 1 bebaut,
was als Analogie zum Aufhängepunkt
eines realen Wespennestes (siehe Abschnitt \ref{sec:nestbau}) verstanden werden kann. Zur Unterscheidung
von den anderen Bausteinen werden die initial gebauten Zellen schwarz markiert
(siehe Abbildung \ref{gitter_initial}).

\subsection{Regelsatz und Parameter}
\label{sec:parameter}
Der genaue Ablauf einer Simulation ist abhängig von mehreren variablen Parametern sowie
dem Regelsatz, nach dem die Agenten ihre Umgebung klassifizieren. Im Folgenden sind alle Parameter der
Simulationsumgebung aufgeführt:
\begin{itemize}
 \item 
   Größe des Simulationsraumes in X- (\texttt{DX}) und Y"=Richtung (\texttt{DY})
 \item
   Anzahl der gleichzeitig aktiven Agenten (\texttt{wespenanzahl})
 \item
   Maximale Anzahl der Schritte pro Agent und Simulationsdurchgang (\texttt{MaxSteps})
 \item
   Größe der Population des Genetischen Algorithmus - entspricht der Anzahl der
   Simulationen, die mit der Population pro Durchlauf des GA durchgeführt werden (\texttt{numberofruns})
 \item
   Anzahl der Anwendungen des Genetischen Algorithmus (\texttt{numberofgaruns})
 \item
   In jedem Simulationslauf arbeitet der einzelne Agent mit dem gleichen statischen Regelsatz von 31 Regeln
   (siehe Tabelle \ref{rs1}), der im Array \texttt{RuleSet1} abgelegt ist.
   Eine detaillierte Erklärung der
   Regelcodierung findet sich in Abschnitt \ref{sec:classification}.
\end{itemize}

\section{Programmierung der Agentenobjekte}
\label{sec:bauagent}
Die Insekten, die im Rahmen der Simulation an der Wabenstruktur bauen, wurden als
autonome \textit{Agenten} modelliert, die sich unabhängig voneinander frei im zweidimensionalen
Raum bewegen können. Hierzu wurden die Möglichkeiten von MATLAB zur
objektorientierten Programmierung genutzt und in der Datei \texttt{bauagent.m} (Listing
in Anhang \ref{code:bauagent}) eine eigene Objektklasse zur Beschreibung
der Agenten programmiert.

Die Position der Agentenobjekte im Raum wird als kontinuierlicher Wert angegeben und gespeichert,
das heißt jeder Agent besitzt zu jedem Zeitpunkt einen absoluten zweidimensionalen Positionsvektor
bestehend aus X- und Y-Koordinate. Die Position wurde derart modelliert, um möglichst nah am biologischen
Vorbild zu bleiben. Da für die Regelverarbeitung des Agenten entscheidend ist, auf welcher Zelle des Gitternetzes
er sich befindet, wird die Nummer der entsprechenden Zelle in jedem Zeitschritt berechnet.

Die Funktionsweise der Agenten entspricht in den Grundzügen der eines
Learning Classifier Systems (siehe Abschnitt \ref{sec:lcs}). Jeder Agent besitzt einen Satz von Klassifikatoren,
mit deren Hilfe die lokale Umgebung \textit{klassifiziert} und über eine entsprechende Aktion entschieden wird.
Die Agenten können nicht miteinander kommunizieren, haben keine Wahrnehmung der globalen Wabenstruktur
und auch keinen Bauplan, wie die fertige Wabe auszusehen hat. Die einzige Wahrnehmungsfähigkeit ist die Erkennung
ihrer direkten Umgebung, wie sie in Abschnitt \ref{sec:classification} detailliert beschrieben ist.

Zu jedem diskreten Zeitpunkt $t$ wird für jeden Agenten die Funktion \texttt{movebuild} aufgerufen, die die Aktivität
des Agenten steuert. Diese Aktivität setzt sich aus zwei
Einzelschritten zusammen. Zuerst erfolgt die Klassifikation der Umgebung mit eventueller Manipulation des Wabengitters,
danach die Bewegung des Agenten auf eine neue Position im Raum.

\subsection{Implementation der Klassifikatoren}
\label{sec:classifier}
In der Datei \texttt{classifier.m} (Listing in Anhang \ref{code:classifier})
wird die interne Struktur der Klassifikatoren festgelegt.
Dazu wird wie für die Agenten eine eigene Objektklasse \texttt{classifier} definiert.
Die Klasse enthält außer einer Konstruktor-Funktion zur Erzeugung der \texttt{classifier}"=Objekte
alle Eigenschaften zur Beschreibung des Klassifikators,
die in objektabhängigen Variablen gespeichert werden.

In der folgenden Liste sind alle Eigenschaften der \texttt{classifier}-Klasse aufgeführt:
\begin{itemize}
 \item 
  \texttt{detector} enthält den Detektor"=String als Zeichenkette (siehe Abschnitt \ref{sec:classification}).
 \item
  \texttt{effector} enthält die bei Aktivierung des Klassifikators auszuführende Aktion
  als numerischen Wert. \texttt{0} steht hier für \textit{nicht bauen} und die Zahlen
  \texttt{1,2,3} für den entsprechenden Bausteintyp.
 \item
  \texttt{strength} ist eine ganze Zahl, die die \textit{Stärke} des Klassifikators
  angibt. Dieser Wert wird bei Erzeugung des \texttt{bauagent}-Objektes für alle Klassifikatoren
  stochastisch unabhängig voneinander per Zufall auf einen Wert zwischen 0 und 255 gesetzt.
 \item
  \texttt{fitnessstring} enthält den \textit{Stärke}-Wert aus \texttt{strength} als 8"=bit"=Gray"=Code
  (siehe Abschnitt \ref{sec:codierung}) in Form einer binären achtstelligen Zeichenkette.
  Ein \texttt{strength}"=Wert von 11 wäre in \texttt{fitnessstring} z.B. als '00001111' gespeichert.
  Diese Form der Codierung ist wichtig für die Funktion des Genetischen Algorithmus (siehe Abschnitt \ref{sec:strengthga}).
 \item
  \texttt{specificity} bezeichnet die Spezifizität $sp(R)$ des Klassifikators. Das entspricht der Zahl der Stellen
  im De\-tek\-tor"=String, die ungleich dem \textit{don't"=care"=Sym\-bol}~\texttt{\textasteriskcentered} sind.
 \item
  \texttt{bid} ist der aus \texttt{strength} und \texttt{specificity} für alle passenden Klassifikatoren
  in einem Zeitschritt berechnete Wert, der zur Entscheidung über die Aktivierung eines Klassifikators
  verwendet wird. Die genaue Beschreibung des Verfahrens ist in Abschnitt \ref{sec:classification} zu finden.
\end{itemize}

\subsection{Klassifikation und Manipulation der Umgebung}
\label{sec:classification}
Die Klassifikation der Umgebung erfolgt durch eine Verknüpfung von Umgebungsmustern mit entsprechenden Aktionen.
Im String-Array \texttt{RuleSet1} werden die Muster und die damit verknüpfte Aktion abgespeichert.
Die ersten sechs Zeichen in einer solchen Zeichenkette repräsentieren die direkte Umgebung der potentiellen
Bauposition und werden wie bei LCS-Systemen \textit{Detektor-String} genannt.
Das siebte Zeichen steht für die Aktion, die der Agent bei Aktivierung des Klassifikators ausführt, und wird
als \textit{Effektor-String} bezeichnet.

Da der Agent sich nur auf bereits bebauten Zellen befinden darf, muss zunächst eine leere Zelle in unmittelbarer
Umgebung ausgewählt werden, auf der ein neuer Baustein gebaut werden könnte. Dazu werden die direkt angrenzenden
Zellen - bei der senkrecht oberhalb angrenzenden Zelle angefangen - im Uhrzeigersinn getestet, ob sie noch unbebaut
sind. Findet der Agent eine unbebaute Zelle, ist dies eine potentielle Bauposition.

Im nun folgenden eigentlichen Klassifizierungsvorgang wird der Zustand der die potentielle Bauposition direkt umgebenden
Zellen - ebenfalls bei der oberen Zelle angefangen im Uhrzeigersinn - nacheinander abgefragt. Die Zustände der
umgebenden Zellen bilden aneinandergereiht die \textit{Input-String} $I$ genannte Eingabe in das System.
% hier vielleicht ein Bild von einem Input-String
Eine \texttt{0} in $I$ steht dabei für eine unbebaute Zelle, \texttt{1}, \texttt{2} oder \texttt{3} steht für eine
mit Bausteintyp \texttt{1}, \texttt{2} bzw. \texttt{3} bebaute Zelle.
$I$ wird dann nacheinander mit allen im Regelsatz vorhandenen Klassifikatoren verglichen.
Für jeden Klassifikator werden die einzelnen Positionen in $I$ der Reihe nach
mit den einzelnen Positionen des Detektor-String $B$
verglichen. Die getestete Regel gilt als \emph{passend}, wenn es keine Widersprüche zwischen $I$
und $B$ gibt. Die Symbole \texttt{0}, \texttt{1}, \texttt{2} und \texttt{3} haben in $B$ die
gleiche Bedeutung wie in $I$. Zusätzlich sind für $B$ noch die Symbole \texttt{B} und \texttt{\textasteriskcentered}
definiert. \texttt{B} steht für eine Zelle, die mit einem \emph{beliebigen Baustein} besetzt ist, und
\texttt{\textasteriskcentered} wird \emph{don't-care-Symbol} genannt, das heißt dass die entsprechende Position
für die Regel nicht relevant ist.

Für $I =$ \texttt{110011} würde z.B. sowohl $B_{1} =$ \texttt{110011}
wie auch $B_{2} =$ \texttt{11**11} oder $B_{3} =$ \texttt{BB**11} als passend erkannt werden.
Eine graphische Übersicht über die Regelsyntax ist in Tabelle \ref{tab:zeichen} zu finden.

\begin{table}[!ht]
 \centering
 \begin{tabular}{ccc}
  \toprule
  Zeichen & Bedeutung & Graphische Darstellung \\
  \midrule
  \texttt{0} & leeres Feld & \includegraphicstotab[height=20pt]{leerezelle} \\
  \texttt{1} & Baustein von Typ 1 & \includegraphicstotab[height=20pt]{typ1} \\
  \texttt{2} & Baustein von Typ 2 & \includegraphicstotab[height=20pt]{typ2} \\
  \texttt{3} & Baustein von Typ 3 & \includegraphicstotab[height=20pt]{typ3} \\
  \texttt{B} & beliebiger Baustein & \includegraphicstotab[height=20pt]{typB} \\
  \texttt{*} & \emph{don't-care} - Zustand egal & \includegraphicstotab[height=20pt]{dontcare} \\
  \bottomrule
 \end{tabular}
 \caption{Vom Regelwerk verwendete Zeichen und ihre Bedeutung}
 \label{tab:zeichen}
\end{table}

Wie in Abschnitt \ref{sec:lcs} bereits erläutert werden alle zu einem Zeitpunkt $t$ als passend
erkannte Klassifikatoren in einer Menge $\mathcal{M}_{t}$ zuammengefasst. Aus $\mathcal{M}_{t}$ wird nun
ein Klassifikator ausgewählt. Dazu wird für jeden Klassifikator $R$ ein entsprechendes Gebot $bid(R)$ berechnet.
Es gilt
\[
 bid(R) = S(R) \cdot \log_{2} (sp(R))
\]
$bid(R)$ berechnet sich also aus Stärke und Spezifizität des Klassifikators.

Mittels \emph{Roulette-Wheel-Selektion} (siehe Abschnitt \ref{ga:selection}) wird nun anhand der \emph{bid}-Werte
einer der Klassifikatoren aus $\mathcal{M}_{t}$ ausgewählt. Die Auswahlwahrscheinlichkeit ist hierbei direkt
proportional zum \emph{bid}-Wert des Klassifikators.

Wurde ein Klassifikator $R$ aus $\mathcal{M}_{t}$ ausgewählt, so wird die in \texttt{effector} als Zahlenwert gespeicherte Aktion
ausgeführt. Mögliche Aktionen sind in diesem Modell das Bauen verschiedener Typen von Zellen (\texttt{effector} = 1, 2 oder 3)
oder das explizite Nicht"=Bauen einer Zelle (\texttt{effector} = 0).
Die verschiedenen Bausteintypen haben keine konkrete Bedeutung, sondern sollen auf das Modell abbilden, dass
Wespen und Bienen die Wabenzellen ihrer Nester für unterschiedliche Aufgaben nutzen. Es könnten z.B. Zellen von Typ 1
für Zellen stehen, in denen die Brut gepflegt wird, Zellen von Typ 2 für die Lagerung von Nahrung und Zellen von Typ 3
für eine beliebige andere Nutzung.

Der komplette verwendete Regelsatz \texttt{RuleSet1} ist in Tabelle \ref{rs1} zu sehen. Die graphische Darstellung
ist folgendermaßen zu interpretieren, dass die mittlere sechseckige Zelle die zu bebauende Position darstellt und
die umgebenden sechs Zellen den für den Klassifikator relevanten Input $I$ repräsentieren. Die farbige Markierung
entspricht der in Tabelle \ref{tab:zeichen} angegebenen.

\begin{table}[p]
   \begin{minipage}[t]{0.45\textwidth}
    \centering
    \begin{tabular}{cccc}
     \toprule
     $Index$ & $B$ & $A$ & Grafik \\
     \midrule
     1 & \texttt{BBBBBB} & 1 & \includegraphicstotab[height=30pt]{./bilder/regel_simplega_01} \\
     2 & \texttt{BBBBB0} & 1 & \includegraphicstotab[height=30pt]{./bilder/regel_simplega_02} \\
     3 & \texttt{0BBBBB} & 1 & \includegraphicstotab[height=30pt]{./bilder/regel_simplega_03} \\
     4 & \texttt{B0BBBB} & 1 & \includegraphicstotab[height=30pt]{./bilder/regel_simplega_04} \\
     5 & \texttt{BB0BBB} & 1 & \includegraphicstotab[height=30pt]{./bilder/regel_simplega_05} \\
     6 & \texttt{BBB0BB} & 1 & \includegraphicstotab[height=30pt]{./bilder/regel_simplega_06} \\
     7 & \texttt{BBBB0B} & 1 & \includegraphicstotab[height=30pt]{./bilder/regel_simplega_07} \\
     8 & \texttt{BBBB00} & 1 & \includegraphicstotab[height=30pt]{./bilder/regel_simplega_08} \\
     9 & \texttt{0BBBB0} & 1 & \includegraphicstotab[height=30pt]{./bilder/regel_simplega_09} \\
     10 & \texttt{00BBBB} & 1 & \includegraphicstotab[height=30pt]{./bilder/regel_simplega_10} \\
     11 & \texttt{B00BBB} & 1 & \includegraphicstotab[height=30pt]{./bilder/regel_simplega_11} \\
     12 & \texttt{BB00BB} & 1 & \includegraphicstotab[height=30pt]{./bilder/regel_simplega_12} \\
     13 & \texttt{BBB00B} & 1 & \includegraphicstotab[height=30pt]{./bilder/regel_simplega_13} \\
     14 & \texttt{BBB000} & 1 & \includegraphicstotab[height=30pt]{./bilder/regel_simplega_14} \\
     15 & \texttt{0BBB00} & 1 & \includegraphicstotab[height=30pt]{./bilder/regel_simplega_15} \\
     16 & \texttt{00BBB0} & 1 & \includegraphicstotab[height=30pt]{./bilder/regel_simplega_16} \\
     \bottomrule
    \end{tabular}
   \end{minipage}
   \begin{minipage}[t]{0.45\textwidth}
    \centering
    \begin{tabular}{cccc}
     \toprule
     $Index$ & $B$ & $A$ & Grafik \\
     \midrule
     17 & \texttt{000BBB} & 1 & \includegraphicstotab[height=30pt]{./bilder/regel_simplega_17} \\
     18 & \texttt{B000BB} & 1 & \includegraphicstotab[height=30pt]{./bilder/regel_simplega_18} \\
     19 & \texttt{BB000B} & 1 & \includegraphicstotab[height=30pt]{./bilder/regel_simplega_19} \\
     20 & \texttt{BB0000} & 1 & \includegraphicstotab[height=30pt]{./bilder/regel_simplega_20} \\
     21 & \texttt{0BB000} & 1 & \includegraphicstotab[height=30pt]{./bilder/regel_simplega_21} \\
     22 & \texttt{00BB00} & 1 & \includegraphicstotab[height=30pt]{./bilder/regel_simplega_22} \\
     23 & \texttt{000BB0} & 1 & \includegraphicstotab[height=30pt]{./bilder/regel_simplega_23} \\
     24 & \texttt{0000BB} & 1 & \includegraphicstotab[height=30pt]{./bilder/regel_simplega_24} \\
     25 & \texttt{B0000B} & 1 & \includegraphicstotab[height=30pt]{./bilder/regel_simplega_25} \\
     26 & \texttt{B00000} & 0 & \includegraphicstotab[height=30pt]{./bilder/regel_simplega_26} \\
     27 & \texttt{0B0000} & 0 & \includegraphicstotab[height=30pt]{./bilder/regel_simplega_27} \\
     28 & \texttt{00B000} & 0 & \includegraphicstotab[height=30pt]{./bilder/regel_simplega_28} \\
     29 & \texttt{000B00} & 0 & \includegraphicstotab[height=30pt]{./bilder/regel_simplega_29} \\
     30 & \texttt{0000B0} & 0 & \includegraphicstotab[height=30pt]{./bilder/regel_simplega_30} \\
     31 & \texttt{00000B} & 0 & \includegraphicstotab[height=30pt]{./bilder/regel_simplega_31} \\
     \bottomrule
    \end{tabular}
   \end{minipage}
   \caption[Kompletter Regelsatz \texttt{RuleSet1}] %
    {Die 31 Klassifikatoren aller Simulationen in Abschnitt \ref{sec:simbeispiel} mit Indexnummer, %
     Detektor-String $B$, Effektor-String $A$ und graphischer Darstellung}
   \label{rs1}
\end{table}

\subsection{Erweiterung durch hierarchische Klassifikatoren}
\label{sec:hierarchie}
Zur Implementierung einer zweiten hierarchischen Ebene von Klassifikatoren wurde das ursprüngliche Modell
um einen zweiten Regelsatz erweitert, der analog zum ersten Regelsatz im Array \texttt{RuleSet2}
abgelegt ist. Es wurde eine neue globale Variable \texttt{rulesetanzahl} in \texttt{simulationsumgebung.m}
angelegt, die die Zahl der hierarchisch hintereinandergeschalteten Regelsätze angibt. Gültige Werte
für \texttt{rulesetanzahl} sind 1 und 2. Setzt man die Variable auf 1, verhält sich das Modell so, als
existiere der zweite Regelsatz nicht. Setzt man sie auf 2, wird nach Ausführung der Simulationen mit Regelsatz 1
derjenige Regelsatz mit der höchsten erreichten Fitness ausgewählt und in \texttt{bestclassifierset1}
zwischengespeichert.
Die neu gestartete Simulation arbeitet zunächst nach wie vor mit Regelsatz \texttt{RuleSet1}, jedoch nur so lange bis
die maximale Schrittzahl \texttt{MaxSteps} erreicht ist. An diesem Punkt wird auf den zweiten Regelsatz
\texttt{RuleSet2} umgeschaltet. Alle vorhandenen Klassifikatoren der Agenten werden gelöscht und durch die
neuen Regeln aus \texttt{RuleSet2} ersetzt. Die Initialisierung der Stärkewerte erfolgt wie beim ersten
Regelsatz zufällig. Danach läuft die Simulation auf der bereits entstandenen Struktur mit dem neuen Regelsatz weiter,
bis die maximale Schrittzahl \texttt{MaxSteps2} erreicht ist.

Der komplette Regelsatz aus \texttt{RuleSet2} ist in den Tabelle \ref{rs2_part1} und \ref{rs2_part2} aufgelistet.

\begin{table}[p]
   \begin{minipage}[t]{0.45\textwidth}
    \centering
    \begin{tabular}{cccc}
     \toprule
     $Index$ & $B$ & $A$ & Grafik \\
     \midrule
     1 & \texttt{110000} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_01} \\
     2 & \texttt{011000} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_02} \\
     3 & \texttt{001100} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_03} \\
     4 & \texttt{000110} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_04} \\
     5 & \texttt{000011} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_05} \\
     6 & \texttt{100001} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_06} \\
     7 & \texttt{211000} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_07} \\
     8 & \texttt{021100} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_08} \\
     9 & \texttt{002110} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_09} \\
     10 & \texttt{000211} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_10} \\
     11 & \texttt{100021} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_11} \\
     12 & \texttt{110002} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_12} \\
     13 & \texttt{112000} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_13} \\
     14 & \texttt{011200} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_14} \\
     15 & \texttt{001120} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_15} \\
     16 & \texttt{000112} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_16} \\
     17 & \texttt{200011} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_17} \\
     18 & \texttt{120001} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_18} \\
     19 & \texttt{211200} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_19} \\
     20 & \texttt{021120} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_20} \\
     \bottomrule
    \end{tabular}
   \end{minipage}
   \begin{minipage}[t]{0.45\textwidth}
    \centering
     \begin{tabular}{cccc}
     \toprule
     $Index$ & $B$ & $A$ & Grafik \\
     \midrule
     21 & \texttt{002112} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_21} \\
     22 & \texttt{200211} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_22} \\
     23 & \texttt{120021} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_23} \\
     24 & \texttt{112002} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_24} \\
     25 & \texttt{212000} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_25} \\
     26 & \texttt{021200} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_26} \\
     27 & \texttt{002120} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_27} \\
     28 & \texttt{000212} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_28} \\
     29 & \texttt{200021} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_29} \\
     30 & \texttt{120002} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_30} \\
     31 & \texttt{120000} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_31} \\
     32 & \texttt{012000} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_32} \\
     33 & \texttt{001200} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_33} \\
     34 & \texttt{000120} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_34} \\
     35 & \texttt{000012} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_35} \\
     36 & \texttt{200001} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_36} \\
     37 & \texttt{210000} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_37} \\
     38 & \texttt{021000} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_38} \\
     39 & \texttt{002100} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_39} \\
     40 & \texttt{000210} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_40} \\
     \bottomrule
    \end{tabular}
   \end{minipage}
   \caption[Kompletter Regelsatz \texttt{RuleSet2} (Teil 1)] %
    {Die 78 Klassifikatoren des Regelsatzes der zweiten Hierarchieebene (Teil~1) mit Indexnummer, %
     Detektor-String~$B$, Effektor-String~$A$ und graphischer Darstellung}
   \label{rs2_part1}
\end{table}

\begin{table}[p]
   \begin{minipage}[t]{0.45\textwidth}
    \centering
    \begin{tabular}{cccc}
     \toprule
     $Index$ & $B$ & $A$ & Grafik \\
     \midrule
     41 & \texttt{000021} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_41} \\
     42 & \texttt{100002} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_42} \\
     43 & \texttt{211100} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_43} \\
     44 & \texttt{021110} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_44} \\
     45 & \texttt{002111} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_45} \\
     46 & \texttt{100211} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_46} \\
     47 & \texttt{110021} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_47} \\
     48 & \texttt{111002} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_48} \\
     49 & \texttt{111200} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_49} \\
     50 & \texttt{011120} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_50} \\
     51 & \texttt{001112} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_51} \\
     52 & \texttt{200111} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_52} \\
     53 & \texttt{120011} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_53} \\
     54 & \texttt{112001} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_54} \\
     55 & \texttt{211110} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_55} \\
     56 & \texttt{021111} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_56} \\
     57 & \texttt{102111} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_57} \\
     58 & \texttt{110211} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_58} \\
     59 & \texttt{111021} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_59} \\
     \bottomrule
    \end{tabular}
   \end{minipage}
   \begin{minipage}[t]{0.45\textwidth}
    \centering
     \begin{tabular}{cccc}
     \toprule
     $Index$ & $B$ & $A$ & Grafik \\
     \midrule
     60 & \texttt{111102} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_60} \\
     61 & \texttt{111120} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_61} \\
     62 & \texttt{011112} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_62} \\
     63 & \texttt{201111} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_63} \\
     64 & \texttt{120111} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_64} \\
     65 & \texttt{112011} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_65} \\
     66 & \texttt{111201} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_66} \\
     67 & \texttt{211111} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_67} \\
     68 & \texttt{121111} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_68} \\
     69 & \texttt{112111} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_69} \\
     70 & \texttt{111211} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_70} \\
     71 & \texttt{111121} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_71} \\
     72 & \texttt{111112} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_72} \\
     73 & \texttt{211120} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_73} \\
     74 & \texttt{021112} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_74} \\
     75 & \texttt{202111} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_75} \\
     76 & \texttt{120211} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_76} \\
     77 & \texttt{112021} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_77} \\
     78 & \texttt{111202} & 2 & \includegraphicstotab[height=25pt]{./bilder/rs2_78} \\
     \bottomrule
    \end{tabular}
   \end{minipage}
   \caption[Kompletter Regelsatz \texttt{RuleSet2} (Teil 2)] %
    {Die 78 Klassifikatoren des Regelsatzes der zweiten Hierarchieebene (Teil~2) mit Indexnummer, %
     Detektor-String~$B$, Effektor-String~$A$ und graphischer Darstellung}
   \label{rs2_part2}
\end{table}

Ergebnisse der Simulationen mit zwei hierarchisch geordneten Sätzen von Klassifikatoren sind in Abschnitt
\ref{sec:simhierarch} zu finden.

\subsection{Bewegung der Agenten}
\label{sec:bewegung}
Die Ausgangsposition aller Agenten befindet sich auf der mittleren der zu Beginn bebauten Zellen.
Nachdem die Klassifizierung und Manipulation der Umgebung durch den Agenten innerhalb eines Zeitschrittes
abgeschlossen ist (siehe Abschnitt \ref{sec:classification}),
wird die Drehrichtung des Agenten nach dem Zufallsprinzip 
neu festgelegt. Hierzu wird eine Zufallszahl zwischen 0 und 1 mit 360 multipliziert. Das Ergebnis bestimmt den
Drehwinkel des Agenten.
Anschließend bewegt sich der Agent in der bestimmten Drehrichtung um eine in der Variable \texttt{Speed} festgelegte
Entfernung im zweidimensionalen Raum. Die Agenten bewegen sich nur auf Zellen, die bereits bebaut sind und
verlassen die gebaute Wabenstruktur nicht.

\section{Berechnung der Gesamtfitness der Wabenstruktur}
\label{sec:fitness}
Die Funktion \texttt{fitness} (Listing siehe Anhang \ref{code:fitness})
dient zur Berechnung der Gesamtfitness einer in der Simulation entstandenen Wabenstruktur.
Als Grundlage der Berechnung dient das Kriterium der \textit{Kompaktheit}.
Kompaktheit bedeutet in diesem Kontext, dass
die Wabenstruktur möglichst wenige Verästelungen oder Löcher aufweist, wobei eine kreisförmige Wabenstruktur
den Idealfall von Kompaktheit darstellt. 
In Abbildung \ref{kompaktbild} a) ist eine stark verästelte
Struktur mit relativ niedrigem Fitnesswert zu sehen, in Abbildung \ref{kompaktbild} b) eine
kompaktere Struktur mit wenig Verzweigungen und entsprechend höherem Fitnesswert.

\begin{figure}[!ht]
 \begin{minipage}[t]{0.45\textwidth}
  \flushleft
  \includegraphics[width=\textwidth]{staticrs2_fitness_023}
  \centering
  \\ (a) $F = 0.23$
 \end{minipage}
 \begin{minipage}[t]{0.45\textwidth}
  \flushright
  \includegraphics[width=\textwidth]{staticrs1_fitness_057}
  \centering
  \\ (b) $F = 0.57$
 \end{minipage}
 \caption[Vergleich zwischen Wabenstrukturen] %
  {Vergleich zwischen zwei Wabenstrukturen mit (a) niedrigem und (b) hohem Fitnesswert $F$}
 \label{kompaktbild}
\end{figure}

Die Kompaktheit bzw. der globale Fitnesswert $F$ der entstandenen Wabenstruktur wird nach jedem einzelnen Simulationslauf bestimmt.
Die dazu verwendete
Fitnessfunktion berechnet einen Wert, der den Grad der Kompaktheit der entstandenen Struktur angeben soll.
Um die Kompaktheit einer Struktur als numerischen Wert darzustellen, wird die Gesamtfläche der Wabe durch
ihren Umfang geteilt. Die Ausgangsidee für diese Berechnung ist, dass ein Kreis von allen geometrischen
Figuren für eine gegebene Fläche den kleinsten Umfang besitzt
und eine kreisförmige Wabe einen (nicht erreichbaren) Idealzustand darstellen würde.
Zur Berechnung der Fitness wird das Verhältnis der Oberfläche $A_{W}$ der Wabe
zu ihrem Umfang $U_{W}$ berechnet und angenommen, dass der Grad der
Kompaktheit proportional zu diesem Wert verläuft. Da dieses Verhältnis bei einer kreisförmigen Figur maximal wäre,
wird der Umfang $U_{K}$ eines hypothetischen Kreises mit gleicher Fläche wie der entstandenen Wabenstruktur berechnet, und
das Verhältnis des Kreisumfangs zur Fläche als idealer Fitnesswert $F_{ideal}$ betrachtet.
Aus den bekannten Kreisgleichungen $U_{K} = 2 \cdot r \cdot \pi$ und $A_{K} = r^{2} \cdot \pi$ ergibt sich das Verhältnis
\begin{equation}
F_{ideal} = \dfrac{A_{K}}{U_{K}} = \dfrac{r}{2} = \dfrac{U_{K}}{4 \cdot \pi}
\end{equation}
Der Quotient aus tatsächlichem Fitnesswert $F$ und idealem Fitnesswert $F_{ideal}$ ist der endgültige
Fitnesswert $F_{GA}$, den der Genetische Algorithmus verwendet.
Im Unterschied zum üblichen Vorgehen bei Lernenden Klassifizierenden Systemen, wird in diesem Modell
der globale Fitnesswert nicht wie in Abschnitt \ref{sec:reinf} beschrieben mittels \emph{Reinforcement Learning}
zu allen beteiligten Regeln zurückpropagiert. Stattdessen erfolgt die Bewertung ausschließlich durch einen
Genetischen Algorithmus, wie im folgenden Abschnitt erläutert wird.

\section{Implementation des Genetischen Algorithmus}
\label{sec:strengthga}
In der Funktion \texttt{strengthga}
(Listing in Anhang \ref{code:strengthga})
ist ein Genetischer Algorithmus implementiert, der die in Abschnitt
\ref{sec:ga} beschriebenen Methoden verwendet, um neue Regelsätze für
die Simulation des Wabenbaus zu erzeugen. In dieser Implementation
bleiben dabei Detektor- und Effektor-String aller Klassifikatoren
gleich, der Genetische Algorithmus verändert jedoch die \textit{Stärke}"=Werte
der Klassifikatoren, mit dem Ziel, eine möglichst gute Verteilung der \textit{Stärke}"=Werte
zu erreichen.

Es gibt zwei prinzipiell zu unterscheidende Möglichkeiten, einen Genetischen Algorithmus
in Zusammenhang mit einem LCS anzuwenden. Diese unterscheiden sich darin, was als
\emph{Individuum} und \emph{Population} für den GA definiert wird:
\begin{enumerate}
 \item 
   Das Individuum entspricht einem \emph{Regelsatz}, also der \textit{Gesamtheit aller Klassifikatoren} eines Agenten.
   Man arbeitet mit Agenten mit unterschiedlichen  Regelsätzen, die zusammen genommen
   die Population des GA darstellen. Man testet das System mit den verschiedenen Regelsätzen
   und lässt den GA den bestmöglichen Regelsatz suchen. Dies entspricht dem Pittsburgh-Ansatz für LCS
   (siehe Abschnitt \ref{sec:ga_lcs}).
 \item
   Das Individuum entspricht einem \emph{einzelnen Klassifikator}.
   Der gesamte benutzte Regelsatz ist damit die Population des Genetischen Algorithmus.
   Das entspricht dem Michigan-Ansatz für LCS (siehe Abschnitt \ref{sec:ga_lcs}). Man arbeitet mit einem anfangs
   festgelegten Regelsatz, wobei die einzelnen Klassifikatoren durch den GA verändert werden.
\end{enumerate}

Im Rahmen der vorliegenden Arbeit wurde ein LCS nach dem Pitts\-burgh"=An\-satz implementiert und beschrieben. Eine
ausführliche Betrachtung von Learning Classifier Systemen nach dem Mi\-chi\-gan"=An\-satz ist bei \citet{butz:06}
zu finden und soll hier nicht näher behandelt werden. Eine Implementation für das vorliegende Problem könnte
trotzdem interessante Ergebnisse bringen.
Für den Ge\-ne\-ti\-schen Al\-go\-rith\-mus stellt die Ge\-samt\-heit der ver\-wen\-de\-ten
Regelsätze und die aus ihnen resultierenden Wabenstrukturen seine
\textit{Population} dar, in der jeder einzelne Regelsatz als \textit{Individuum}
zu sehen ist. \textit{Genotyp} des Individuums ist die Menge der
Stärke"=Werte aller Klassifikatoren des entsprechenden Regelsatzes.
Es wird die in \texttt{fitnessstring} gespeicherte Gray"=Code"=Darstellung
jeder einzelnen Regel aneinandergehängt und in \texttt{classifierfitnessstring}
abgespeichert. Hätte man zum Beispiel einen aus drei Klassifikatoren $R_{1}$, $R_{2}$
und $R_{3}$ bestehenden Regelsatz $\mathcal{R}$ und die drei Klassifikatoren hätten die folgenden
Fitnesswerte in Gray"=Code"=Darstellung: \texttt{fitnessstring($R_{1}$)} = '11010011',
\texttt{fitnessstring($R_{2}$)} = '00101101' und \texttt{fitnessstring($R_{3}$)} = '01011010',
dann wäre % der aneinandergereihte Fitnessstring des Regelsatzes
\texttt{classifier\-fitness\-string ($\mathcal{R}$)} = '110100110010110101011010'
und repräsentierte den Genotyp des Individuums
für den Genetischen Algorithmus.

Im beschriebenen Regelsatz von 31 Klassifikatoren (siehe Abbildung \ref{rs1}) mit einem 8"=bit"=Stärkewert
besteht der Genotyp
eines Individuums somit aus einer Kette von $8 \times 31 = 248$ Nullen und Einsen.
Als \textit{Phänotyp} des Individuums kann die durch Anwendung des Regelsatzes entstandene
Wabenstruktur gesehen werden.

\subsection{Parameter des Genetischen Algorithmus}
\label{subsec:gaparameter}
In \texttt{strengthga.m} können drei Parameter für den Genetischen
Algorithmus direkt angegeben werden:
\begin{itemize}
 \item 
  \texttt{probcrossover} gibt die Wahrscheinlichkeit $p_{xover}$ an, mit der bei der Reproduktion
  der Individuen eine Rekombination der genetischen Codes der Eltern  stattfindet. 
 \item
  \texttt{probmutation} definiert die Mutationswahrscheinlichkeit $p_{mut}$,
  mit der ein ausgewähltes Bit in einem neu erzeugten Individuum verändert wird (siehe Abschnitt \ref{sec:steprep}).
 \item
  \texttt{elternzahl} ist die Anzahl der Individuen, die pro Durchlauf des Genetischen
   Algorithmus für eine "`Fortpflanzung"' ausgewählt werden. Der Wert muss ein Vielfaches von
   2 sein, da jeweils zwei Individuen für einen Rekombinationsvorgang benötigt werden.
\end{itemize}

\subsection{Ablauf des Genetischen Algorithmus}
\label{met:gaablauf}
\subsubsection{Selektion der Elternindividuen}
Zur \textit{Selektion} der Elternindividuen wird ein \textit{Roulette"=Wheel}"=Selektionsalgorithmus
(siehe Abschnitt \ref{ga:selection}) verwendet, der als Funktion \texttt{roulettemz} implementiert ist.
Anhand der in \texttt{overallfitness} gespeicherten Fitnesswerte der gebauten Strukturen wird in
jedem Durchlauf des Selektionsalgorithmus ein Agent ausgewählt, wobei die Auswahlwahrscheinlichkeit
direkt proportional zum Fitnesswert ist. Es handelt sich um stochastische Auswahl \textit{mit Zurücklegen},
das heißt jedes Individuum kann beliebig oft zur Replikation ausgewählt werden. Dadurch wird erreicht, dass
sich Individuen mit überdurchschnittlich hoher Fitness auch überdurchschnittlich vermehren können.
% TODO noch genauer erklären. eventuell Grafik einbauen
% Individuen werden aus Population "herauskopiert", man arbeitet auf den Kopien

\subsubsection{Rekombination}
Nach Auswahl der Elternindividuen erfolgt ihre Replikation durch die Funktion
\texttt{one\-point\-xover}. Die genetischen Strings der Elternindividuen (gespeichert in
\texttt{clas\-si\-fier\-fit\-ness\-string}) werden zuerst in zwei neue Strings kopiert.
Danach wird eine stochastische Auswahl darüber getroffen, ob eine Rekombination der beiden
Strings erfolgt. Mit Wahrscheinlichkeit $p_{xover}$ werden die Strings rekombiniert, mit
Wahrscheinlichkeit $1 - p_{xover}$ wird die Rekombination übersprungen.
Entscheidet der Zufall für eine Rekombination, wird einfaches \textit{Ein"=Punkt"=Crossover}
angewendet (siehe Abschnitt \ref{sec:steprep}),
das heißt es wird eine zufällige Stelle auf dem Bitstring ausgewählt und die Teile der beiden
neu erzeugten Strings werden hinter diesem Crossover"=Punkt miteinander vertauscht.
Abbildung \ref{crossoverbild} veranschaulicht diesen Vorgang.

\begin{figure}[!htb]
 \centering
 \includegraphics{nissen_crossover}
 \caption[Schema von \emph{Ein"=Punkt"=Crossover} \citep{nissen:97}] %
  {Schematische Darstellung von \emph{Ein"=Punkt"=Crossover} \citep{nissen:97}}
 \label{crossoverbild}
\end{figure}

\subsubsection{Mutation}
Auf die so entstandenen genetischen Strings wird im nächsten Schritt die Funktion \texttt{mutation}
angewendet. Sie implementiert den in Abschnitt \ref{sec:steprep} beschriebenen Mutationsvorgang.
Wie bei der Rekombination erfolgt vor der eigentlichen Durchführung der Mutation eine stochastische
Entscheidung darüber, ob tatsächlich eine Mutation durchgeführt wird oder nicht. Mit Wahrscheinlichkeit
$p_{mut}$ wird ein Bit im String mutiert, mit Wahrscheinlichkeit $1 - p_{mut}$ nicht.
Wird für eine Mutation entschieden, wird zufällig eine Stelle auf dem String gewählt und das entsprechende
Bit gekippt, d.h. aus einer '0' wird eine '1' und aus einer '1' eine '0'.

\subsubsection{Einfügen in die Population}
Da die Größe der Population konstant gehalten werden soll, unter anderem um einen Selektionsdruck aufzubauen und
Individuen mit niedrigerer Fitness aus der Population zu entfernen, müssen ebenso viele Individuen aus der
bisherigen Population entfernt werden, wie bei der Elternselektion zur Vermehrung ausgewählt wurden.
Die Auswahl der zu entfernenden Individuen erfolgt ebenfalls durch Roulette"=Wheel"=Selektion,
die in Funktion \texttt{roulette}
implementiert wurde. Es gibt zwei entscheidende Unterschiede zu dem bei der Selektion
der Elternindividuen verwendeten Algorithmus.
Die Auswahlwahrscheinlichkeit hängt nicht direkt proportional vom erreichten Fitnesswert ab wie bei
der Elternselektion, sondern umgekehrt proportional.
Je geringer die vom Individuum erreichte Fitness ist, desto höher ist die Wahrscheinlichkeit,
dass es aus der Population gelöscht wird.
Außerdem erfolgt in dieser Variante eine Auswahl aus der Population ohne Zurücklegen, d.h. jedes Individuum
darf in einem Durchgang des GA nur einmal gewählt werden. Dies ist äußerst wichtig, da für jedes neu
dazukommende Individuum ein anderes aus der Population gelöscht werden muss. Würde man ein Individuum
in diesem Schritt zweimal auswählen, könnte man es trotzdem nur einmal aus der Population entfernen,
was eine relative Vergößerung der Population zur Folge hätte.
Die beschriebenen Schritte des Genetischen Algorithmus werden so oft wiederholt, bis die festgelegte Anzahl von
neuen Individuen erzeugt wurde.

\section{Graphische Darstellung}
\label{sec:grafik}
Um eine Vorstellung davon vermitteln zu können, wie die in der Simulation entstandenen Strukturen aussehen,
wurde eine graphische Darstellung des Simulationsraumes implementiert.
MATLAB stellt umfangreiche Möglichkeiten zur Graphikprogrammierung zur Verfügung.
Als Anforderungen an die Darstellung wurden eine übersichtliche Repräsentation des sechseckigen Gitternetzes,
die farbige Markierung von bebauten Zellen mit je nach Bausteintyp unterschiedlichen Farben
und die Möglichkeit der Markierung der momentanen Agentenposition festgelegt.

\subsection{Darstellung des hexagonalen Gitters}
 \label{sec:plotgitter}
Die Darstellung des Gitternetzes wurde in der Funktion \texttt{plotgitter}
(Listing in Anhang \ref{code:plotgitter}) realisiert.
Um den Mittelpunkt jeder sechseckigen Zelle wird ein regelmäßiges sechseckiges
\texttt{patch}-Objekt erzeugt, welches genau die Umrisse der Zelle nachzeichnet.
\texttt{patch}-Objekte sind graphische Objekte in MATLAB und können beliebige Formen
und Farben haben. Die hier benutzten Objekte haben eine weiße Oberfläche und schwarze
Ränder, wodurch in ihrer Aneinanderreihung das Gitternetz entsteht (siehe Abbildung \ref{gitter_leer}).

\begin{figure}
 \centering
 \includegraphics[width=\textwidth]{gitter_leer}
 \caption{Unbebaute sechseckige Gitterstruktur}
 \label{gitter_leer}
\end{figure}

 \subsection{Darstellung der einzelnen Wabenzellen}
 \label{sec:plotwabe}
 Um die bebauten Wabenzellen zu markieren, wurde die Funktion \texttt{plotwabe}
 geschrieben. Die Funktion benötigt als übergebene Parameter den logischen
 Index der zu markierenden Zelle und ihre Farbe.
 Es wird ein zusätzliches sechseckiges \texttt{patch}-Objekt an der Position der Zelle
 erzeugt, wobei die Flächen des Objekts in der dem Bausteintyp entsprechenden Farbe
 eingefärbt werden. Um das Modell für eine spätere dreidimensionale Erweiterung offenzuhalten,
 wurden die Bausteine nicht als flache Sechsecke
 sondern als dreidimensionale Polygonobjekte modelliert. Ein Beispiel für eine
 von vier Agenten gleichzeitig gebaute Wabenstruktur findet sich in Abbildung \ref{simbeispielbild}.
  
 \begin{figure}
 \centering
 \includegraphics[width=\textwidth]{beispiel_4ag_500step}
 \caption[Wabenstruktur aus drei Bausteintypen] %
  {Graphisches Beispiel einer von vier Agenten mit drei Bausteintypen gebauten Wabe}
 \label{simbeispielbild}
\end{figure}

\section{Durchführung der Simulationen}
Der Ablauf der mit Hilfe des in diesem Kapitel beschriebenen Modells
durchgeführten Simulationen erfolgte nach dem folgendem Schema:
\begin{enumerate}
  \item 
    Festlegen der Simulationsparameter: Größe des Feldes, Anzahl der Agenten, Anzahl der Schritte pro Simulationslauf,
    Größe der Population des GA, Anzahl der Durchläufe des Genetischen Algorithmus
  \item
    Festlegen des Ausgangsregelsatzes: Es wird ein Satz von Klassifikatoren definiert und für jeden Klassifikator
    seine Bedingung (Detektor-String $B$), die entsprechende Aktion (Effektor-String $A$) und sein anfänglicher Stärkewert $S$ definiert.
    Die Stärkewerte der einzelnen Regeln werden für jede Simulation von neuem
    vergeben, wobei $S$ für jeden Klassifikator als zufälliger ganzzahliger Wert zwischen 0 und 255 zugewiesen wird.
    Die Beschränkung auf ganze Zahlen $S$ mit $0 \leq S \leq 255$ ist notwendig, da die Stärkewerte in
    8"=bit"=Gray"=Code abgespeichert werden (siehe Abschnitt \ref{sec:codierung}).
  \item
    Durchführung der Simulationsläufe
  \item
    Auswertung der Ergebnisse
\end{enumerate}
Die genauen Parameter der durchgeführten Simulationen sowie die erzielten Ergebnisse werden in Abschnitt \ref{sec:ergebnis}
im Einzelnen betrachtet.

Die zum Sechseckgitter relative Positionsbestimmung stellte sich im Verlauf der Simulationen
als sehr zeitraubend heraus. Ein Simulationslauf mit einer Population von 100 Individuen
und 100 Durchläufen des Genetischen Algorithmus benötigte ca. 70 Stunden Rechenzeit.
Ein Großteil der Rechenzeit entfiel dabei auf die Positionsbestimmung.
Eine Neuimplementierung mit weniger Zeitaufwand wäre von Vorteil, wobei man
alternativ dazu das Modell auch dahingehend
vereinfachen könnte, dass die Position des Agenten nur durch den Index der Zelle definiert wird, auf dem sich der Agent
befindet. Der Agent könnte sich damit nur von Zellenmittelpunkt zu Zellenmittelpunkt bewegen, was die
zeitaufwendige Positionsbestimmung überflüssig machen würde.
Es bleibt allerdings zu prüfen, ob dies nicht eine Vereinfachung wäre,
die sich negativ auf das Verhalten des Modells auswirken würde.
