\chapter{Simulationsergebnisse}
\label{sec:ergebnis}
\section[Ergebnisse mit einem Regelsatz und variablen Stärkewerten] %
 {Simulationsergebnisse mit einem statischen Regelsatz und genetisch variierten Stärkewerten}
\label{sec:simbeispiel}
Dieser Abschnitt stellt die Ergebnisse einer Simulationsreihe dar, für die der Regelsatz
aus Tabelle \ref{rs1} verwendet wurde.
Es wurde jeweils eine Population von Agenten erzeugt, deren Anzahl durch den Parameter \texttt{numberofruns}
definiert wurde. Mit jedem der Agenten wurde eine einzelne Bausimulation durchgeführt und die Fitnesswerte
der jeweils erzeugten Struktur gespeichert.
Die Detektor- und Effektor-Strings der Klassifikatoren sind für jeden Agenten in \texttt{RuleSet1} festgelegt
und damit gleich. Nur die Stärkewerte der einzelnen Klassifikatoren werden für jeden Agenten per Zufall zugewiesen und
unterscheiden die Individuen dadurch voneinander.
In jedem Lauf gibt es nur einen einzelnen Agenten, der immer die gleiche Zahl von Zeitschritten läuft.
Wenn alle Individuen ihre Bausimulation beendet hatten, wurde wie in Abschnitt \ref{sec:strengthga} detailliert
erläutert der Genetische Algorithmus auf die Population angewendet,
um die Stärkewerte der Klassifikatoren zu variieren.
Mit der so veränderten Population wurde dann erneut gebaut, wobei die Anzahl der Durchläufe durch \texttt{numberofgaruns}
festgelegt ist.

In allen in diesem Abschnitt beschriebenen Simulationen wurden die folgenden Parameter verwendet
(Bedeutung siehe Abschnitt \ref{sec:parameter}), soweit nicht anders angegeben:
\begin{itemize}
 \item 
  \texttt{DX} = 41
 \item
  \texttt{DY} = 41
 \item
  \texttt{wespenanzahl} = 1 \\ Um die Ergebnisse besser bewerten zu können, wurde
   mit nur einem gleichzeitig aktiven Agenten simuliert.
  \item
   \texttt{MaxSteps} = 200
  \item
   \texttt{probmutation} = 0.2
\end{itemize}
Die sich unterscheidenden Parameter sind im jeweiligen Unterabschnitt angegeben.

\subsection{Ergebnisse ohne Beschränkung der Populationsgröße}
\label{sec:simergebnisse1}
In diesem Abschnitt werden die Ergebnisse einer Simulation vorgestellt, in der
die Größe der Population nicht beschränkt wurde und sich daher in jedem Durchlauf
erhöhte.
Die Simulation wurde mit folgenden zusätzlichen Parametern durchgeführt:
\begin{itemize}
 \item
   Größe der Population \texttt{numberofruns~=~20}
 \item
   Anzahl der Durchläufe des GA \texttt{numberofgaruns~=~20}
 \item
   Anzahl der pro Durchlauf des GA erzeugten neuen Individuen \texttt{elternzahl~=~2}
\end{itemize}
Es wurde eine Anfangspopulation von 20 Agenten erzeugt, die wie zuvor beschrieben mit dem gleichen Regelsatz
und unterschiedlichen Stärkewerten der einzelnen Regeln einen Bauvorgang simulierten. 
In dieser Simulation wurden durch den Genetischen Algorithmus keine Individuen aus der Population gelöscht.
Wegen \texttt{elternzahl~=~2} kommen mit jedem Durchlauf des GA                      
zwei neue Individuen zur Population dazu, weswegen die Population im Laufe der Simulation wächst. Am Ende der
Simulation, nach 20 Durchläufen, umfasst die Population 60 Inidviduen.
Nach Beendigung aller Simulationsläufe
wurde jeweils die maximal erreichte globale Fitness $F_{max}$ der entstandenen Strukturen festgehalten.
Die Entwicklung des maximalen Fitnesswertes $F_{max}$ ist in Abbildung \ref{ga2020maxfitness} zu sehen.

Trotz stochastischer Schwankungen ist in der Grafik ein deutlicher Aufwärtstrend zu erkennen, der vermuten lässt, dass
der Genetische Algorithmus den gewünschten Effekt hat und seine
weitere Anwendung noch zu einer weiteren Verbesserung geführt hätte.

\begin{figure}[!hb]
 \centering
 % Die Grafik zum Simulationslauf mit dem einfachen GA, 20 runs, 20 ga_runs
 \includegraphics[width=\textwidth]{./bilder/strengthga1_20_20_maxfitness}
 \caption[Maximale Fitness ohne Beschränkung der Populationsgröße] %
  {Entwicklung der maximal erreichten Overall-Fitness einer Anfangspopulation von 20 Individuen nach 20 Anwendungen des GA}
 \label{ga2020maxfitness}
\end{figure}

\subsection{Ergebnisse mit beschränkter Populationsgröße}
\label{sec:simergebnisse2}
In dieser Simulation wurde für jedes neu erzeugte Individuum
je ein Individuum aus der Population entfernt, wie in Abschnitt \ref{met:gaablauf}
beschrieben. Dies entspricht dem biologischen Vorbild des
Selektionsdruckes (siehe Abschnitt \ref{sec:evo}) und verspricht eigentlich bessere Ergebnisse.
Für die Simulation galten die folgenden zusätzlichen Parameter:
\begin{itemize}
 \item
   \texttt{numberofruns} = 100
 \item
   \texttt{numberofgaruns} = 100
 \item
   \texttt{elternzahl} = 4
\end{itemize}

\begin{figure}[!ht]
 \centering
 % Die Grafik zum Simulationslauf mit dem einfachen GA, 100 runs, 100 ga_runs
 \includegraphics[trim = 30mm 10mm 30mm 10mm, clip, width=\textwidth]{./bilder/strengthga1_100_100_fitness}
 \caption[Fitness bei Population von 100 und 100 GA-Durchläufen] %
  {Entwicklung der durchschnittlich ($F_{avg}$, rot) und maximal ($F_{max}$, blau) erreichten globalen Fitness %
   einer Population von 100 Individuen über 100 Anwendungen des GA}
  \label{ga100100fitness}
\end{figure}

Unter allen 100 Individuen wurde der maximal erreichte Fitnesswert $F_{max}$ ermittelt
und abgespeichert. Zusätzlich wurde in diesem Versuch ein Wert $F_{avg}$ berechnet,
der den durchschnittlichen Fitnesswert der Population nach jedem Durchlauf des Genetischen Algorithmus
repräsentiert. Die Entwicklung
von $F_{max}$ und $F_{avg}$ nach wiederholter Anwendung des GA ist in Abbildung \ref{ga100100fitness} dargestellt.

Für beide Werte ist in Grafik \ref{ga100100fitness} keine eindeutige Tendenz nach oben oder unten zu erkennen.
Beide Werte schwanken zwar mehr oder weniger stark, tendieren aber nicht eindeutig
zu einer Verbesserung. Wie dieses Ergebnis zu bewerten ist, wird ausführlich in Abschnitt \ref{sec:diskussion}
diskutiert.

\subsection[Ergebnisse mit Crossover"=Wahrscheinlichkeit] %
 {Ergebnisse mit stochastischer Entscheidung über Crossover}
\label{sec:simergebnisse3}
Da die Ergebnisse der vorhergehenden Simulation (s. Abschnitt \ref{sec:simergebnisse2}) nicht zufriedenstellend waren,
wurde das Programm nochmals um einen entscheidenden Punkt verändert; es wurde ein Parameter 
$p_{xover}$ als Variable \texttt{probxover} in \texttt{strengthga.m} eingeführt,
der die Crossover"=Wahrscheinlichkeit für den Genetischen Algorithmus
festlegt. Mit Wahrscheinlichkeit $p_{xover}$ wird also ein Crossover durchgeführt, mit Wahrscheinlichkeit $1-p_{xover}$
werden die genetischen Strings der Eltern-Individuen unverändert auf die Kinder kopiert. Diese Änderung kann unter Umständen
verhindern, dass Individuen mit hoher Fitness durch Cross\-over zerstört werden.
Außerdem wurde in diesem Simulationslauf der Selektionsdruck dadurch erhöht, dass pro Durchlauf des Genetischen Algorithmus
20 Eltern-Individuen mit Roulette"=Wheel"=Selektion ausgewählt und somit auch 20 neue Individuen erzeugt wurden.

Es wurde also mit folgenden Parametern simuliert:
\begin{itemize}
 \item
   \texttt{numberofruns} = 100
 \item
   \texttt{numberofgaruns} = 20
 \item
   \texttt{elternzahl} = 20
 \item
   Crossover-Wahrscheinlichkeit ($p_{xover}$) \texttt{probxover} = 0.6
\end{itemize}

\begin{figure}[!ht]
 \centering
 % Die Grafik zum Simulationslauf mit dem einfachen GA, 100 runs, 20 ga_runs
 \includegraphics[trim= 30mm 10mm 30mm 10mm, clip, width=\textwidth]{strengthga1_100_20_fitness}
 \caption[Entwicklung der Fitness mit Crossover"=Wahrscheinlichkeit] %
  {Entwicklung von $F_{max}$ (blau) und $F_{avg}$ (rot) bei einer Population von 100 Individuen über 20 Anwendungen des GA}
  \label{ga10020fitness}
\end{figure}

Die erreichten maximalen bzw. durchschnittlichen Fitnesswerte $F_{max}$ und $F_{avg}$ nach jedem Lauf des GA sind in
der Grafik \ref{ga10020fitness} zu sehen.
Die Ergebnisse unterscheiden sich kaum von denen in Abschnitt \ref{sec:simergebnisse2}. Auch hier ist keine Verbesserung
oder Verschlechterung des erreichten Fitnesswertes mit wiederholter Anwendung des GA zu erkennen. Vielmehr bleibt der Fitnesswert
von stochastischen Abweichungen abgesehen mehr oder weniger konstant.

\subsection{Ergebnisse mit Mehrfachauswahl der Elternindividuen}
In den vorherigen Simulationsläufen
konnte ein Individuum aus der Population nur einmal als Elternindividuum gewählt werden.
Da dies der Vorstellung widerspricht, dass sich Individuen mit hoher Fitness überdurchschnittlich oft
vermehren, wurde die Implementation für diese Simulation abgeändert,
so dass ein Individuum in einem Durchlauf
des GA beliebig oft ausgewählt werden kann. Der Roulette"=Wheel"=Se\-lek\-ti\-ons\-al\-go\-rith\-mus wurde also
\textit{mit Zurücklegen} programmiert (siehe Abschnitt \ref{met:gaablauf}).

Die Simulationsparameter waren wie folgt:
\begin{itemize}
 \item
   \texttt{numberofruns} = 200
 \item
   \texttt{numberofgaruns} = 100
 \item
   \texttt{elternzahl} = 100
 \item
   \texttt{probxover} = 0.6
\end{itemize}

Die minimal ($F_{min}$), durchschnittlich ($F_{avg}$) und maximal ($F_{max}$) erreichten
Fitnesswerte nach jedem Durchlauf des Genetischen Algorithmus sind in Abbildung \ref{ga200_100_100_fitness}
dargestellt.

\begin{figure}[!ht]
 \centering
 % Die Grafik zum Simulationslauf mit dem einfachen GA, 100 runs, 20 ga_runs
 \includegraphics[trim= 35mm 0mm 35mm 0mm, clip, width=\textwidth]{strengthga1_200_100_mz_100e_fitness}
 \caption[Entwicklung der Fitness mit Zurücklegen] %
  {Entwicklung von $F_{max}$ (blau), $F_{avg}$ (grün) und $F_{min}$ (rot) bei einer Population %
   von 200 Individuen über 100 Anwendungen des Genetischen Algorithmus}
  \label{ga200_100_100_fitness}
\end{figure}

\section{Simulation mit statischem Regelsatz ohne Genetischen Algorithmus}
\label{sec:simstat}
Um zu ermitteln, inwieweit das Schwanken der Fitnesswerte in Abschnitt \ref{sec:simbeispiel} zufällig ist und
ob überhaupt ein direkter Zusammenhang zwischen der Verteilung der Stärkewerte der einzelnen Klassifikatoren
und der Fitness der gebauten Struktur besteht, wurde eine Simulation durchgeführt, in der wie in Abschnitt
\ref{sec:simbeispiel} der Regelsatz aus Tabelle \ref{rs1} verwendet wurde.
Der Programmcode wurde für diese Simulation angepasst. Für die jedem Klassifikator des Individuums zu Beginn der Simulation
zugewiesenen Stärkewerte wurden keine zufälligen Werte zwischen 0 und 255 erzeugt, sondern jeder Regel ein bestimmter Wert
zugewiesen. Der Genetische Algorithmus wurde außerdem deaktiviert.
In diesem Experiment wurden also hintereinander 100 Wabenstrukturen von 100 identischen Individuen mit identischem
Regelsatz gebaut und die erzielten Ergebnisse verglichen.

Die relevanten Simulationsparameter im Detail:
\begin{itemize}
 \item 
  \texttt{DX = 41}
 \item
  \texttt{DY = 41}
 \item
  \texttt{wespenanzahl = 1}
 \item
  \texttt{MaxSteps = 200}
 \item
  \texttt{numberofruns = 100}
 \item
  Regelsatz siehe Tabelle \ref{rs1}
 \item
  Stärkewerte der Klassifikatoren siehe Tabelle \ref{tab:staticrs1}.
  Die Werte wurden so gewählt, dass die Wahrscheinlichkeit für den Bau einer Zelle mit der Anzahl der
  bereits bebauten Nachbarzellen ansteigt.
  Dies entspricht den empirischen Beobachtungen beim Nestbau realer Wespen (siehe Abschnitt \ref{sec:stigmergie})
  und sollte der Erwartung nach Strukturen mit hoher Fitness erzeugen.
\end{itemize}

\begin{table}[ht]
 \centering
 \begin{tabular}{rr}
  \toprule
  Regelindex & Stärkewert $S$ \\
  \midrule
  1 & 255 \\
  2 & 250 \\
  3 & 250 \\
  4 & 250 \\
  5 & 250 \\
  6 & 250 \\
  7 & 250 \\
  8 & 230 \\
  9 & 230 \\
  10 & 230 \\
  11 & 230 \\
  12 & 230 \\
  13 & 230 \\
  14 & 150 \\
  15 & 150 \\
  16 & 150 \\
  17 & 150 \\
  18 & 150 \\
  19 & 150 \\
  20 & 50 \\
  21 & 50 \\
  22 & 50 \\
  23 & 50 \\
  24 & 50 \\
  25 & 50 \\
  26 & 250 \\
  27 & 250 \\
  28 & 250 \\
  29 & 250 \\
  30 & 250 \\
  31 & 250 \\
  \bottomrule
 \end{tabular}
 \caption{Stärkewerte des Regelsatzes in Simulation \ref{sec:simstat}}
 \label{tab:staticrs1}
\end{table}

\begin{figure}[!hp]
 \centering
 \includegraphics[trim = 30mm 10mm 30mm 10mm, clip, width=\textwidth]{fitness_r_identisch}
 \caption[Vergleich von Waben von 100 identischen Individuen] %
  {Vergleich der Fitnesswerte der von 100 identischen Individuen gebauten Wabenstrukturen}
  \label{graph:staticrs1}
\end{figure}
\begin{figure}[!hp]
 \begin{minipage}[t]{0.49\textwidth}
  \flushleft
  \includegraphics[width=\textwidth]{staticrs1_vergleich_21}
  \centering
  \\ (a) $F_{21} = 0.24$
 \end{minipage}
 \begin{minipage}[t]{0.49\textwidth}
  \flushright
  \includegraphics[width=\textwidth]{staticrs1_vergleich_18}
  \centering
  \\ (b) $F_{18} = 0.63$
 \end{minipage}
 \caption[Von identischen Individuen gebaute Wabenstrukturen] %
  {Von identischen Individuen (a) Nr. 21 und (b) Nr. 18 gebaute Strukturen mit zugehörigem Fitnesswert $F$}
 \label{bild:fitnessvergleich}
\end{figure}

In Abbildung \ref{graph:staticrs1} sind die von den 100 identischen Individuen erzielten Fitnesswerte dargestellt.
Es ist sehr starkes Schwanken festzustellen. Die Fitnesswerte schwanken zwischen $F_{min} = 0.24$ und $F_{max} = 0.63$
bei einer durchschnittlichen Fitness $F_{avg} = 0.43$.
Zur weiteren Veranschaulichung zeigt Abbildung \ref{bild:fitnessvergleich} die beiden zu $F_{min}$ und $F_{max}$
gehörenden Strukturen. Die beiden Waben wurden von identischen Individuen mit gleichem Regelsatz und ebenso gleicher
Stärkeverteilung der Klassifikatoren erzeugt. Die starken Unterschied in optischem Erscheinungsbild und Fitnesswert
können daher nur durch die zufällige Bewegung der Agenten und die stochastische Auswahl über die zu aktivierende Regel
zustande kommen.

\section{Simulation mit zwei hierarchisch geordneten Regelsätzen}
\label{sec:simhierarch}
Durch die Erweiterung des Simulationsmodells um einen zweiten Regelsatz, der nach einer festgesetzten Anzahl
von Simulationsschritten an Stelle des ersten Regelsatzes aktiviert wird (siehe Abschnitt \ref{sec:hierarchie}),
konnten komplexere Strukturen gebaut werden. Mit dem verwendeten zweiten Regelsatz (siehe Tabellen
\ref{rs2_part1} und \ref{rs2_part2}) wurde um die bereits mit Regelsatz 1 gebaute Struktur
(Bausteintyp 1, rot)
ein geschlossener Ring gebaut (Bausteintyp 2, grün). Das Ergebnis ist in Abbildung \ref{ringstruktur_simuliert} zu
sehen.

Der Simulation lagen die folgenden Parameter zugrunde:
\begin{itemize}
 \item 
  \texttt{DX = 41}
 \item
  \texttt{DY = 41}
 \item
  \texttt{wespenanzahl = 1}
 \item
  \texttt{MaxSteps = 100}
 \item
  \texttt{MaxSteps2 = 1000}
 \item
  Zahl der hierarchischen Ebenen von Klassifikatoren: \texttt{rulesetanzahl = 2}
 \item
  Regelsatz der ersten hierarchischen Ebene: \texttt{RuleSet1} (Tabelle \ref{rs1})
 \item
  Regelsatz der zweiten hierarchischen Ebene: \texttt{RuleSet2} (Tabellen \ref{rs2_part1} und \ref{rs2_part2})
\end{itemize}

\texttt{MaxSteps} und \texttt{MaxSteps2} sind so zu interpretieren, dass die Simulation nach \texttt{MaxSteps} Schritten
auf den zweiten Regelsatz umschaltet und dann nach insgesamt \texttt{MaxSteps2} Schritten die Simulation beendet.
In diesem Beispiel wurde also 100 Schritte lang \texttt{RuleSet1} verwendet und danach 900 Schritte lang \texttt{RuleSet2}.
\texttt{MaxSteps2} wurde vergleichsweise hoch gewählt, um zu gewährleisten, dass der Agent trotz stochastischer Bewegung die
Gelegenheit bekommt, an jede Randposition der Struktur zu kommen, und dadurch einen geschlossenen Ring grüner Bausteine zu
bauen.
\begin{figure}[!hb]
 \centering
 \includegraphics[width=\textwidth]{ring_100_1000_steps}
 \caption[Ringstruktur bei Simulation mit zwei Regelsätzen] %
  {Endzustand einer Beispielsimulation mit zwei hierarchisch hintereinandergeschalteten Regelsätzen}
 \label{ringstruktur_simuliert}
\end{figure}