\documentclass[a4paper,german,12pt]{scrartcl}
\usepackage[utf8]{inputenc}
\usepackage[german]{babel}
\usepackage[T1]{fontenc}
\usepackage{natbib}
\usepackage{setspace}
% \usepackage{textcomp}

\parindent 0pt
\parskip 12pt

%opening
\title{Genetische Entwicklung hierarchischer Klassifikatoren beim Wabenbau sozialer Insekten}

\author{Marius Zirngibl - Matrikel 5299377 \\ 
        eMail 0zirngib@informatik.uni-hamburg.de}

\begin{document}
\maketitle

\begin{onehalfspace}
Der Nestbau sozialer Insekten ist ein anschauliches Beispiel für in der Natur auftretende emergente Phänomene.
Ameisen, Wespen oder Bienen bringen in kollektiver Arbeit Nestbauten zustande, deren Größe und Komplexität den menschlichen
Beobachter bei oberflächlicher Betrachtung zu der Annahme verleiten könnten, dass eine derartige Struktur nicht ohne einen
Bauplan oder einen übergeordneten "`Architekten"' entstehen kann  \citep[e.g.][]{matsuura:90,winston:91,camazine:01}. 
Da ein einzelnes Insekt nicht die Fähigkeiten besitzt, um eine globale Struktur wie die eines komplexen Nestes zu erfassen,
wird im Allgemeinen davon ausgegangen, dass soziale Insekten ihre Nester nach Prinzipien der Selbstorganisation bauen.
Das einzelne Individuum arbeitet nach einfachen, genetisch evolvierten lokalen Regeln, die in ihrer Gesamtheit eine
Struktur entstehen lassen, die trotz fehlender zentraler Koordination den Anforderungen von Brutpflege, Vorratshaltung
und Schutz gegen Feinde bei veränderlichen Umweltbedingungen entsprechen. 
Es ist davon auszugehen, dass hier Selbstorganisation in Form von \textit{Stigmergie} ein zentrales Prinzip
darstellt \citep{bonabeau:99,karsai:99}. Der Begriff Stigmergie wurde von \citet{grasse:59} geprägt und
ist von den griechischen 
Wörtern $\sigma \tau \iota \gamma \mu \alpha $ (\textit{stigma}: Zeichen, Markierung) und
$\epsilon \rho \gamma o \nu $ (\textit{ergon}: Arbeit, Aktion) abgeleitet.
Als Stigmergie wird eine Form der indirekten Kommunikation verstanden, die sich dadurch auszeichnet, dass
Individuen durch Manipulation ihrer Umgebung Informationen austauschen.
Die gesetzten Zeichen oder Markierungen (\textit{stigma}), auch \textit{Stimuli} genannt,
beeinflussen also das Verhalten bzw. die Aktionen (\textit{ergon}) des Individuums.
\citet{bonabeau:99} unterscheiden hier zwei Arten der Stigmergie: zum einen die \textit{quantitative Stigmergie},
bei der die Stärke der relevanten Stimuli über das Verhalten des Individuums entscheidet,
zum anderen die \textit{qualitative} oder \textit{diskrete Stigmergie}, bei der qualitativ verschiedene Stimuli
unterschiedliches Verhalten hervorrufen.
Die Wegmarkierung mittels Pheromonen, welche von Ameisen zur Anzeige einer Futterquelle genutzt werden, wäre ein Beispiel für
quantitative Stigmergie, da die Intensität der Pheromonspur dafür verantwortlich ist, wie stark deren Anziehungskraft
auf die einzelne Ameise ist.
Ein Beispiel für qualitative Stigmergie hingegen stellt der Nestbau verschiedener Wespenarten dar, wobei das Individuum
aufgrund unterschiedlicher Wabenstrukturen entscheidet, 
an welcher Stelle eine zusätzliche Wabe angebaut wird \citep{karsai:99}.

Ein zentrales Ziel der geplanten Arbeit ist es, ein vom realen Nestbau abstrahiertes Modell zu entwickeln, 
welches in Anlehnung an die beschriebenen Mechanismen 
mit einem Schwarm adaptiver Agenten eine Struktur aus hexagonalen Einzelbausteinen (Waben) zusammensetzen kann.
Die Agenten sollen
sich zufällig auf einem dreidimensionalen Gitternetz bewegen und an jedem Punkt des Gitters jeweils entscheiden, ob 
dort ein Baustein gesetzt wird oder nicht. Die Gesamtheit aller möglichen Zustände des Gitters stellt den Zustandsraum
des betrachteten Problems dar. Dabei wird als Zustand eines Punktes die Art der dort gebauten Wabe definiert.
Geht man von einem Gitternetz mit $W$ Punkten und $n$ möglichen Zuständen eines einzelnen
Punktes aus, arbeitet man in einem Zustandsraum der Größe $n^{W}$, was schon im einfachsten Fall 
(nur ein Wabentyp, also $n = 2$) zu einem exponentiell zu $W$ wachsenden Zustandsraum führt.
Die Entscheidung des Agenten über den Bau einer Wabe erfolgt nach dem Prinzip der diskreten
Stigmergie, das heißt die lokale Umgebung des Agenten an seiner Position gibt den Ausschlag für die Entscheidung, ob
an dieser Position gebaut wird oder nicht.
Hierbei soll explizit kein konkretes Zielmuster vorgegeben, sondern die entstehenden Strukturen anhand verschiedener
Kriterien wie z.B. Kompaktheit oder Symmetrie bewertet und die Verhaltensregeln der Agenten aufgrund dieser Bewertungen
angepasst werden. 
\begin{quotation}
 "` [\dots ] a few simple behavioural rules lead to coordinated building and the production of
 amazingly complex architectures without needing to develop a strategy."' \citep[S.327]{theraulaz:99}
\end{quotation}
 
Die adaptiven Agenten sollen
über einen Satz von Regeln verfügen, mit dessen Hilfe sie über ihr
konkretes Verhalten in einer bestimmten Situation entscheiden können. Regeln sollen hierbei im
Wettbewerb zueinander stehen, wobei der Agent mittels eines internen Bewertungssystems entscheidet,
welche der passenden Regeln angewandt werden soll. Die Bewertung der Regeln erfolgt zum einen durch eine
spezifische Gewichtung, welche die Bedeutung der Regel für das gesamte System repräsentieren soll, zum
anderen durch die Unterscheidung aufgrund des in einer Regel enthaltenen Informationsgehalts. Eine Regel mit
vielen signifikanten Bits hat einen höheren Informationsgehalt als eine Regel mit wenigen signifikanten Bits
und soll daher vorgezogen werden. Konkret bedeutet das für den Wabenbau, dass eine Regel, die den Zustand 
vieler benachbarter Waben berücksichtigt, mit größerer Wahrscheinlichkeit zur Anwendung kommt als eine Regel,
die nur von einer Nachbarwabe abhängt.
Dieser Mechanismus wurde sehr anschaulich von \citet{holland:95} beschrieben.
Regeln mit wenig Informationsgehalt werden als \textit{default rules} betrachtet, auf die der Agent zurückgreift,
wenn keine spezifischeren Regeln vorhanden sind.
Um verschiedene Abschnitte im Nestbau von Insekten zu berücksichtigen, soll es mehrere \textit{hierarchisch geordnete} 
Regelsätze geben, und an definierten Triggerzuständen von übergeordneten zu untergeordneten
Regelsätzen umgeschaltet werden. Die Agenten sollen also zu unterschiedlichen
Zeitpunkten der Simulation
nach verschiedenen Regeln funktionieren, was besonders bei einer komplexeren Neststruktur wichtig ist.

Die Gewichtung der einzelnen Regeln soll nach dem Prinzip des \textit{reinforcement learning} angepasst werden.
Vereinfacht ausgedrückt wird hierbei die Gewichtung von Regeln erhöht oder verringert,
abhängig davon, ob ihre wiederholte Anwendung zu einem als gut oder als schlecht bewerteten Endergebnis
geführt hat \citep{mitchell:97}.
Zusätzlich sollen die Regelsätze durch einen \textit{Genetischen Algorithmus} \citep{goldberg:89,nissen:97}
verändert werden, um diejenigen Regeln zu finden, die zu sinnvollen Ergebnissen führen.
Jeweils nach einem Simulationsdurchlauf mit einem bestimmten Satz von Regeln wird der Genetische Algorithmus (GA)
angewendet, wobei der komplette Regelsatz als Genotyp eines Individuums betrachtet wird. Der GA arbeitet
auf einer Population von Individuen, d.h. es werden unterschiedliche Regelsätze in der Simulation angewendet und die
jeweils entstandenen Strukturen durch den GA bewertet. Je nach Bewertung der entstandenen Struktur ändert sich die
Chance des verwendeten Regelsatzes, in der nächsten Generation des GA berücksichtigt zu werden.
Näheres zu dieser Anwendung Genetischer Algorithmen findet sich bei \citet{bonabeau:99}.
Diese Variante selbstorganisierten Lernens orientiert sich auch am Konzept der ebenfalls auf Holland zurückgehenden
\textit{Learning Classifier Systems} oder kurz \textit{LCS} \citep{sigaud:07,holland:92}.

Eine grobe Gliederung der geplanten Arbeit:
\begin{enumerate}
 \item Einleitung und theoretisches Konzept
 \begin{enumerate}
  \item Definition des Zustandsraumes (Gitternetz mit Belegung durch Waben)
  \item Bedeutung von Regeln und Klassifikatoren bei stochastischer Entscheidung zwischen einzelnen Aktionen
  \item Hierarchische Ordnung der Regeln
  \item Definition der Population von Regelsätzen
  \item Bewertung der Aktionen mittels \textit{Reinforcement Learning}
  \item Modifikation der Regelsätze durch einen \textit{Genetischen Algorithmus}
  \item Entwicklung von Populationsstrukturen
 \end{enumerate}
 \item Simulationsumgebung
 \begin{enumerate}
  \item Sechseckige Waben in der Ebene
  \item Erweiterung in den Raum
  \item Räumliche Umgebung mit Begrenzung
 \end{enumerate}
 \item Ergebnisse der Simulation
 \begin{enumerate}
  \item in der begrenzten Ebene
  \item in der unbegrenzten Ebene 
  \item im dreidimensionalen Raum
  \item nach weiteren Kriterien
  \begin{enumerate}
   \item Brutpflege
   \item Vorrat
   \item Schutzbegrenzung
  \end{enumerate}
  \item Konvergenzprobleme
 \end{enumerate}
 \item Diskussion
\end{enumerate}

Es soll eine Testumgebung entwickelt werden, in der die Regelsätze praktisch angewendet werden können.
Aufgrund der heuristischen Natur des Verfahrens können mehrere Testläufe mit gleichen Ausgangsparametern
sehr unterschiedliche Ergebnisse liefern, außerdem muss in diesem Zusammenhang untersucht werden,
unter welchen Bedingungen das Modell konvergiert.
Die relevanten Ergebnisse sollen grafisch und textuell dargestellt werden.

Zum Ende der Arbeit sollen die erzielten Ergebnisse bewertet und diskutiert werden.
Neben dem Verständnis und der Analyse selbstorganisierender
Prozesse in komplexen natürlichen Systemen ist ein weiterer Fokus der Arbeit auch, inwieweit deren
charakteristische Eigenschaften
wie Selbstorganisation, Stigmergie und Emergenz auf künstlich geschaffene komplexe Systeme übertragbar sind.
\end{onehalfspace}

\bibliographystyle{dinatneu}
\bibliography{literatur}

\end{document}
