

%----------------------------------------------------------------------
\section{Empirische Analyse der Individuentypen}
%----------------------------------------------------------------------
\label{sec:EmpAnaInd}

Die neuen Individuentypen wurden zwar mit der Intention entwickelt im
 GeneticChess-System verwendet zu werden, da es sich aber bei den
meisten Individuen um allgemeine GP-Strukturen handelt, wurde eine
empirische Analyse der Individuen auf verschiedenen
Benchmarkproblemen durchgeführt. Um dabei die Performance der
Strukturen bewerten zu können, wurden sie mit den Standardstrukturen
Baum und linear GP verglichen.


Das \emph{State-Space-GP} wurde auf keines dieser
Benchmarkprobleme angewendet, da die Implementierung so schachspezifisch
ist, dass eine Anwendung auf Klassifikations- und
Regressionsprobleme nicht möglich war.




%----------------------------------------------------------------------
\subsection{Testprobleme}
%----------------------------------------------------------------------
\label{sub:Testprobleme}

Als Testprobleme wurden Probleme aus den Bereichen der
symbolischen Regression, der Klassifikationsprobleme
und ein boolesches Problem verwendet. Die Probleme wurden aus
diesen verschiedenen Problemklassen gewählt, um die Analyse
der neuen Individuentypen so fair wie möglich zu gestalten. %Wenn man
%sich noch mal die Intention vor Augen hält, aus der heraus die neuen
%Individuentypen entwickelt wurden, sollte man erwarten, dass sie zum
%Beispiel bei der Funktionsregression keinen Vorteil gegenüber den
%Standardstrukturen haben werden. Dieses Problemfeld wurde aber trotzdem
%verwendet, um die Performanz so objektiv wie möglich zu messen.

Weiterhin wurden aus Gründen der Objektivität alle Tests unter den
gleichen Voraussetzungen gestartet, das heißt, die 
Einstellungen für wichtige Parameter des GP-Systems wurden
für alle Tests gleich gewählt. Einige Parameter unterschieden sich für
die einzelnen Problemklassen, wurden dann aber in diesen nicht variiert.
Die Parameter, die in allen Tests nicht verändert wurden, sind in der
Tabelle~\ref{tab:GlobParameter} zu finden.


\begin{table}
\begin{center}
\begin{tabular}{|p{3cm}|p{3cm}|p{6cm}|}
\hline
 Parameter & Wert & Beschreibung \\
\hline 
 Läufe & 100  & Anzahl der Läufe des GP-Systems, über die die
 Ergebnisse gemittelt werden. \\
\hline 
 Evaluationen & 200.000 & Anzahl der Fitnessauswertungen pro Lauf \\
\hline 
 Population & 100/10 & Die Größe der Population für einen
 Lauf; jeweils ein Lauf mit 100 Individuen und ein Lauf mit 10 Individuen\\
\hline 
 Crossover & 0,8 & Wahrscheinlichkeit, dass zwei Individuen an einem
 Crossover teilnehmen\\
\hline 
 Mutation & 0,2 & Wahrscheinlichkeit, dass ein Individuum mutiert wird\\
\hline 
 Selektion & Turnierselektion 2*2 & Turnierselektion aus zwei Zweierturnieren\\
\hline 
 Initialisierung & ramped half and half & Initialisierungsart der Population \\
\hline 
 Minimale Individuengröße & 10  & Anzahl der Knoten, die ein Individuum
 minimal haben durfte \\
\hline 
 Maximale Individuengröße & 200 & Anzahl der Knoten, die ein Individuum
 maximal haben durfte \\
\hline 
 Linear-XXXX Tiefe & 5 & Die maximale Anzahl von Ebenen in einem
 Linear-Tree oder Linear-Graph Individuum\\
\hline 
 Konstanten & [-1,..,1] & Wertebereich der Konstanten\\
\hline 
 Branching\-konstanten & [-10,..,10] &  Wertebereich der Konstanten in
 den Branchingfunktionen der Individuen\\
\hline 
 Branching\-funktionen & R$<$0, R$>$0, R$=$0, x$<$0, x$>$0, x$=$0 & Branchingfunktionen \\
\hline
\end{tabular}
\end{center}
\caption{Diese Tabelle enthält alle Parameter, die für alle Tests
gleich waren. }
\label{tab:GlobParameter}
\end{table}

Für alle Probleme wurde in die Funktionsmenge der Individuen die
Funktion \emph{ifThen} benutzt. Diese Funktion implementiert einen
bedingten Sprung im linearen Genom der Individuen und ermöglicht eine
Verzweigung im Baum GP. Diese Funktion
wurde in die Funktionsmenge aufgenommen, um bei der empirischen
Analyse der neuen Individuentypen, im Vergleich zu den Standard GP-Strukturen,
diesen die Möglichkeit zu geben, ebenfalls den eigenen Programmfluss
zu modifizieren. Wichtig ist noch hervorzuheben, dass die Parameter für
Crossover und Mutation denen entsprechen, die von Koza für Baum GP verwendet
werden. %Es hat sich jedoch gezeigt, dass für die anderen Strukturen andere Werte
%für das Crossover besser geeignet sind. So kann man durch geringere Crossoverwerte und
%höhere Mutationswerte die Ergebnisse der anderen Strukturen in der Fitness um
%bis zu 15\% verbessern. Aus Gründen der Vergleichbarkeit wurde aber hier auf
%eine bessere Einstellung für die anderen GP Strukturen verzichtet, da sie von
%Struktur zu Struktur variieren. 
%Im Folgenden ist jedoch zu sehen, dass der
%qualitative  Eindruck zur Einordnung der Strukturen in eine Rangordnung,
%dadurch nicht verfälscht wird.


%-------------------------------------------------------------------------
\subsubsection{Symbolische Regression}
%-------------------------------------------------------------------------
\label{sub:SymReg}

Als Benchmarks für die symbolische Regression\index{symbolische Regression} wurden
Probleme ausgewählt, die häufig in Publikationen als Benchmarks herangezogen
werden.

%Die symbolische Regression\index{symbolische Regression} ist das
%Problem, aus einer Menge von $n$ nummerischen Input-Output Relationen
%$(x,y)$ eine symbolische Funktionen zu approximieren. Das System soll
%aus den gegebenen Daten eine Funktion erzeugen, die für jede Eingabe
%von $x$ eine Ausgabe $y'$ berechnet, die so nah wie möglich an dem
%vorgegebenen  Wert liegt und auch für unbekannte Werte Ergebnisse
%liefert, die plausibel sind.

Die Fitness eines Individuums $p$ ist für die Testprobleme definiert
als die Summe der quadratischen Fehler über alle Ausgabewerte.
Für eine gegebene Funktion $f(x)$ und den durch das Individuum
berechneten Wert $p(x)$ ist die Fitness des Individuums $p$ wie folgt
definiert:
\[
\text{fitness}(p) = \frac{\sum_{i=1}^{n} (p(x_i) - f(x_i))^{2}}{n}.
\]

Als Benchmarkprobleme für die symbolische Regression wurden die
folgenden Probleme benutzt:
\begin{itemize}
\item Sinus im Bereich von $[0,2\pi]$ mit 20 Fitnesscases. Die
Fitnesscases wurden uniform aus dem Intervall genommen und die beiden
Endpunkte des Intervalls wurden auch in die Menge aufgenommen.
\item Sinus im Bereich von $[0,4\pi]$ mit 40 Fitnesscases. Die Auswahl
der Fitnesscases entsprach den Nebenbedingungen für das Sinusproblem
mit einer Periode.
\item Rastrigin, $f(x)= x^2 - 5*cos(2\pi *x)$, im Bereich von
  $[-4,4]$ und 40 Fitnesscases. 
\end{itemize}


Die Parameter, die in allen Läufen zur Regression nicht verändert wurden,
sind in der Tabelle~\ref{tab:GlobParameter} zu finden. Als Funktionsmenge
wurden die Funktionen $+,-,*,/$ und ifThen verwendet.



%-------------------------------------------------------------------------
\subsubsection{Klassifikationsprobleme}
%-------------------------------------------------------------------------
\label{sub:KlassProblem}

Als Benchmarks für die
Klassifikationsprobleme\index{Klassifikationsprobleme} wurden die
folgenden Probleme verwendet:
\begin{itemize}
\item Das Chain Problem, ein Klassifikationsproblem besteht daraus,
  einen Punkt im Raum einer von zwei Klassen zuzuordnen. Die
  Punkte der beiden Klassen sind in zwei Ringen im Raum angeordnet, wie
  Abbildung~\ref{fig:chains} verdeutlicht.
\item Das Spiral Problem von Koza besteht aus zwei Spiralen in der
  Ebene. Eine Spirale entspricht der Klasse eins und die zweite Spirale
  der Klasse zwei, die Abbildung~\ref{fig:spiral} zeigt das
  Spiralproblem mit der Klassenzugehörigkeit.
\item Das 11-Multiplexer Problem, das Problem ist eigentlich ein boolesches
  Problem, jedoch entspricht die Fitnessfunktion der der
  Klassifikationsprobleme. Das Problem verwendet jedoch eine andere
  Funktionsmenge, die nur aus booleschen Funktionen besteht.
\end{itemize}


%Die Aufgabe des GP-Programmes bei den Klassifikationsproblemen ist das
%Finden einer Relation, die die gegebenen Eingaben $x$ den korrekten
%Klassen, hier $c \in {0,1}$, für jedes Tupel $(x,c)$ zuordnet.
Die Fitness eines Individuums ist die Fehlklassifikation auf den
Fitnesscases in Prozent, das heißt, die beste Fitness ist 0.
Für ein gegebenes Klassifikationproblem $k(x)$ und den durch das
Individuum $p$ berechneten Wert ist die Fitness des Individuums
$p$, als die Anzahl der Fehlklassifikationen definiert.
\begin{equation}
  \text{fitness}(p)= \sum_{i= 0}^{max}
                        \begin{cases}
                        1  & \text{wenn die Eingabe richtig klassifiziert wurde,}\\
                        0  & \text{sonst.}\\
                      \end{cases}
\end{equation}


Die Parameter, die in allen Läufen zur Klassifikation nicht verändert werden, entsprechen denen in
Tabelle~\ref{tab:GlobParameter}. Als Funktionsmenge wurden für das Chain- und
Spiral Problem die Funktionen  $+,-,*,/$, ifThen, Sinus und  Cosinus verwendet,
für das Multiplexerproblem die booleschen Funktionen \emph{und, oder, nicht}
und \emph{exclusive oder}.


%\clearpage
\begin{figure} [h]
\begin{minipage}{7cm}
\centerline{\epsfig{figure=Pictures/Probleme/chains.eps,width=7cm}}
\caption{Die Abbildung zeigt das Chain Problem mit den beiden Klassen,
die durch zwei Ringe im Raum dargestellt werden. Das Problem wurde in
dem Artikel~\cite{brameier:2000:TR} zum ersten Mal verwendet. \index{Chain-Problem} }
\label{fig:chains}

\end{minipage}
\hfill
\begin{minipage}{7cm}

\centerline{\epsfig{figure=Pictures/Probleme/spiral.eps,width=7cm}}%height=7cm
\caption{Die Abbildung zeigt das Spiral Problem, welches von Koza
 in~\cite{koza1} veröffentlicht wurde. Das Problem besteht aus zwei
Spiralen, die zu zwei verschiedenen Klassen gehören.\index{Spiral-Problem}}
\label{fig:spiral}
\end{minipage}
\end{figure}



%----------------------------------------------------------------------
\subsection{Experimentelle Ergebnisse}
%----------------------------------------------------------------------
\label{sec:GPResult}



Im folgenden Abschnitt werden die Ergebnisse der verschiedenen GP-Strukturen
auf den sechs Benchmarkproblemen diskutiert. Alle Graphiken zeigen den
Mittelwert der Fitness des besten Individuums von 100 Läufen. Für jedes Problem
wurden 200.000 Evaluationen durchgeführt, die Populationsgröße variierte dabei
zwischen 10 und 100 Individuen. Die Populationsgröße wird bei jedem
Plot angegeben.




%\clearpage
\begin{figure} [!h]
\begin{minipage}{7cm}
\centerline{\epsfig{figure=Pictures/Results/GNUsinus10.ps,width=7cm}}%,height=6cm}}
\caption{Die Kurven beschreiben den Mittelwert der Fitness über 100 Läufe mit
jeweils 10 Individuen pro Pool. Die guten Fitnesswerte für die Linear-Tree und
-Graph Strukturen und ihre kleinen Standardabweichungen im Vergleich zu den
linearen und Baumstrukturen sind sofort zu erkennen.}% Interessant ist hier die
%Fitnessentwicklung des linearen GP's es zeigt nach 200.000 Evaluationen noch
%kein Konvergenzverhalten, wie die anderen Strukturen.}
\label{fig:FitSin10}
%\end{figure}

\end{minipage}
\hfill
\begin{minipage}{7cm}
%\begin{figure} [!h]
\centerline{\epsfig{figure=Pictures/Results/GNUsinus100.ps,width=7cm}}%,height=6cm}}
\caption{Die 100 Läufe wurden mit 100 Individuen pro Pool durchgeführt. Alle Strukturen
  zeigen einen typischen Fitnessverlauf für evolutionäre Verfahren. Es zeigt
  sich hier, dass das Baum GP sehr
viel bessere Ergebnisse liefert als mit 10 Individuen und ungefähr so gut
ist wie die Linear-Tree Struktur.}% Auch die Standardabweichung der Ergebnisse
%ist viel besser als nur mit 10 Individuen. Die Linear-Graph Struktur erreicht
%jedoch die besten Ergebnisse.}
\label{fig:FitSin100}
\end{minipage}
\end{figure}



In den Abbildungen~\ref{fig:FitSin10} und~\ref{fig:FitSin100} zeigen die
Fitnesswerte der verschiedenen Strukturen für das Sinusproblem mit 10
beziehungsweise 100 Individuen pro Pool. In beiden Fällen ist die Anzahl der
Fitnessevaluationen gleich, trotzdem zeigt sich für das Baum GP und das lineare
GP ein Unterschied während der Evolution und in den erreichten
Ergebnissen. Die Linear-Tree und Linear-Graph Strukturen erreichen in beiden
Fällen ähnliche Ergebnisse, dies ist ein deutlicher Hinweis, dass diese
Struktur von der Populationsgröße nicht stark abhängt und die Diversität
während der Evolution auch in kleinen Populationen aufrecht erhalten kann.
Sehr gut sind auch die kleinen Standardabweichungen im Vergleich zu den
linearen und Baumstrukturen. Hierauf wird noch einmal später eingegangen,
wenn die Ergebnisse der letzten Generation für alle Läufe analysiert wird.
Interessant ist hier auch die Fitnessentwicklung des linearen GP's, in der
Abbildung~\ref{fig:FitSin10}, denn es
zeigt nach 200.000 Evaluationen noch kein Konvergenzverhalten wie die anderen
Strukturen. Das deutet darauf hin, dass es noch zu Verbesserungen kommen würde, 
wenn man die Evolution weiter laufen lassen würde.

In der Abbildung~\ref{fig:FitSin100} zeigen alle Strukturen einen typischen
Fitnessverlauf für evolutionäre Verfahren. Es zeigt sich nun, dass das Baum GP sehr
viel bessere Ergebnisse liefert als mit 10 Individuen und ungefähr so gut
ist wie die Linear-Tree Struktur. Auch die Standardabweichung der Ergebnisse
ist viel kleiner geworden als mit nur 10 Individuen. Dies ist ein deutlicher
Hinweis darauf, dass Baum GP größere Populationen benötigt als die anderen Strukturen,
dies zeigt sich immer wieder im Verlauf der Untersuchung.
Die Linear-Graph Struktur erreichte auch mit 100 Individuen die besten
Ergebnisse im Vergleich der verschiedenen Strukturen. Die Standardabweichung
hat sich von 0,0928409 auf 0,0770319 verringert, was im Vergleich zum Baum GP
gering ist, denn dort war der Schritt von 0,960098 zu 0,357485 zwar größer,
bleibt aber absolut gesehen sehr viel schlechter als beim Linear-Graph GP.


%\clearpage
\begin{figure} [!h]
\begin{minipage}{7cm}
\centerline{\epsfig{figure=Pictures/Results/GNU2sinus100.ps,width=7cm}}%,height=6cm}}
\caption{Dieser Plot zeigt die Fitness für die Regression einer Sinuskurve
  über 4$\pi$, also 2 Perioden. Auch hier zeigt die Fitnessentwicklung des
  linearen GP's nach 200.000 Evaluationen noch kein Konvergenzverhalten wie
  die anderen Strukturen. %Die Linear-Graph Struktur erreicht auch für diese
%  Problem den besten Fitnesswert, erstaunlicherweise schneidet die Linear-Tree
%  Struktur hier am schlechtesten ab.
}
\label{fig:Fit2Sin100}
%\end{figure}
\end{minipage}
\hfill
\begin{minipage}{7cm}
%\begin{figure} [!h]
\centerline{\epsfig{figure=Pictures/Results/GNUmexhat10.ps,width=7cm}}%,height=6cm}}
\caption{Der Plot zeigt das Verhalten der GP Strukturen für das Rastrigin
  Problem. Hier ist die Fitness der Baumstruktur im Vergleich zu allen anderen
  Strukturen sehr schlecht, so dass der weitere Plot~\ref{fig:FitMex10Zoom}
  die Ergebnisse der anderen Strukturen vergrößert.}
\label{fig:FitMex10}
\end{minipage}
\end{figure}

Dieser Unterschied ist sehr wichtig, da das Ziel der Dissertation die
Evolution von Schachprogrammen ist und die Evolution von Schachprogrammen
durch die Fitnessbewertung sehr rechenzeitintensiv ist. Bei den Ergebnissen
der Schachprogramme ist auch das absolut beste Programm interessant und nicht
die durchschnittlichen Ergebnisse. Somit sind geringe Variationen in den
Ergebnissen verschiedener Läufe gewünscht.


In der Abbildung~\ref{fig:Fit2Sin100} sieht man die Ergebnisse der
Strukturen auf das Sinusproblem über 2 Perioden, mit 100 Individuen pro
Lauf. Die Ergebnisse mit 10 Individuen werden hier nicht gezeigt, da bis auf
die Linear-Graph Struktur alle anderen Strukturen an dieser Aufgabe
gescheitert sind. Interessant ist hier jedoch die Ähnlichkeit zu dem Ergebnis
für das einfache Sinusproblem mit 10 Individuen, siehe
Abbildung~\ref{fig:FitSin10}. Hier schneidet nur das Baum GP deutlich besser
ab, ähnlich dem Ergebnis für das einfache Sinusproblem mit 100
Individuen. Aber das Verhalten der linearen Struktur ist direkt vergleichbar
mit den Ergebnissen mit 10 Individuen, dies ist ein erster Hinweis darauf, dass
man zur Lösung von schweren Problemen größere Populationen
benötigt. Gleichzeitig kann man aber auch durch andere Strukturen den
evolutionären Prozess unterstützen und somit wieder mit kleineren Populationen arbeiten.



%\clearpage
\begin{figure} [!h]
\begin{minipage}{7cm}
\centerline{\epsfig{figure=Pictures/Results/GNUmexhat10-Zoom.ps,width=7cm}}%,height=6cm}}
\caption{Die Ergebnisse der Evolution mit 10 Individuen zeigen für die lineare
Struktur wieder ein anderes Verhalten als für 100 Individuen. Die Kurve fällt
über die ganze Zeit viel gleichmäßiger und zeigt kein Konvergenzverhalten auf
dem Bereich mit 200.000 Evaluationen. Das beste Ergebnis mit der kleinsten
Standardabweichung erreicht wieder die Linear-Graph Struktur. }
\label{fig:FitMex10Zoom}
%\end{figure}
\end{minipage}
\hfill
\begin{minipage}{7cm}
%\begin{figure} [!h]
\centerline{\epsfig{figure=Pictures/Results/GNUmexhat100.ps,width=7cm}}%,height=6cm}}
\caption{Die Evolution mit 100 Individuen zeigt für das Rastrigin Problem ein
ganz anderes Ergebnis als mit nur 10 Individuen. Jetzt ist auch die
Baumstruktur konkurrenzfähig. Sie erreicht zwar die schlechtesten Ergebnisse,
der Unterschied ist aber nicht mehr so dramatisch. Auch hier erreicht die
Linear-Graph Struktur wieder die besten Ergebnisse.}
\label{fig:FitMex100}
\end{minipage}
\end{figure}


Die Abbildung~\ref{fig:FitMex10} zeigt das Verhalten der GP Strukturen für das
Rastrigin Problem. Hier ist die Fitness der Baumstruktur im Vergleich zu allen anderen
Strukturen sehr schlecht, so dass der weitere Plot~\ref{fig:FitMex10Zoom}
die Ergebnisse der anderen Strukturen vergrößert. Gleichzeitig zur schlechten
Fitness der Struktur ist auch die Standardabweichung für die Baumstruktur im
Vergleich sehr schlecht.
Die Ergebnisse der Evolution mit 10 Individuen, wie sie in
Abbildung~\ref{fig:FitMex10Zoom} gezeigt werden, zeigt für die lineare
Struktur wieder ein anderes Verhalten als für 100 Individuen. Die Kurve fällt
hier über die ganze Zeit viel gleichmäßiger aus und zeigt kein Konvergenzverhalten 
im Bereich von 200.000 Evaluationen. Das beste Ergebnis mit der kleinsten
Standardabweichung erreicht wieder die Linear-Graph Struktur. Die Ergebnisse
der Linear-Tree Struktur sind sogar etwas schlechter als die der linearen
Struktur und auch die Standardabweichung ist für die Linear-Tree Struktur
nicht so gut wie bei den anderen Problemen.
Ein Grund hierfür liegt in dem Problem selber, das Rastrigin Problem hat auf
dem betrachteten Intervall sehr viele Schwingungen, so dass die Baumstruktur
ein Polynom hohen Grades evolvieren muss, um die Problemstellung zu lösen. Für die
Linear-Tree Struktur ist hier die maximale Tiefe des Baumes ein Problem, bei
größeren Tiefen sind hier bessere Ergebnisse möglich, für den Vergleich wurde
dies aber nicht gemacht. Die Linear-Graph Struktur kann hier die Vorteile der
Graphstruktur gegenüber der Baumstruktur im Programfluss der Individuen nutzen
um kompaktere Individuen zu erzeugen.


Die Evolution mit 100 Individuen zeigt für das Rastrigin Problem ein
ganz anderes Ergebnis als mit nur 10 Individuen. Die
Abbildung~\ref{fig:FitMex100} zeigt jetzt, dass auch die Baumstruktur
konkurrenzfähig ist. Sie erreicht zwar die schlechtesten Ergebnisse, der
Unterschied zu den anderen Strukturen ist aber nicht mehr so dramatisch. Auch
hier erreicht die Linear-Graph Struktur wieder die besten Ergebnisse. Gut sind
die großen Unterschiede in der Standardabweichung zwischen Linear-Graph (0,48)
und Baum (2,50) in der Abbildung zu erkennen.



%\clearpage
\begin{figure} [!h]
\begin{minipage}{7cm}
\centerline{\epsfig{figure=Pictures/Results/GNUchain10.ps,width=7cm}}%,height=6cm}}
\caption{Die Abbildung zeigt die Fitness für das 2 Chain Problem mit 10
  Individuen. Keine der Fitnesskurven zeigt ein außergewöhnliches
  Verhalten. Das Baum GP schneidet in diesem Versuch am schlechtesten ab und
  das Linear-Graph GP am besten.}
\label{fig:FitChain10}
%\end{figure}
\end{minipage}
\hfill
\begin{minipage}{7cm}
%\begin{figure} [!h]
\centerline{\epsfig{figure=Pictures/Results/GNUchain100.ps,width=7cm}}%,height=6cm}}
\caption{Die Abbildung zeigt die Fitness für das 2 Chain Problem mit 100
  Individuen. Alle Verläufe der Fitnesskurven sehen typisch aus. Die
  Standardabweichung hat sich für alle Strukturen im Vergleich zu 10 Individuen
  verkleinert.}%, die Reihenfolge der Strukturen bleibt jedoch bestehen.}
\label{fig:FitChain100}
\end{minipage}
\end{figure}

Die Abbildungen~\ref{fig:FitChain10} und \ref{fig:FitChain100} zeigen die
Ergebnisse für das Klassifikationsproblem Chain. Im direkten Vergleich der
Abbildungen erkennt man kaum einen qualitativen Unterschied zwischen den
Fitnessverläufen der einzelnen Strukturen. Am stärksten kann man noch einen
Unterschied bei der Baum GP Struktur erkennen, die bei 100 Individuen sehr
viel bessere Fitnesswerte erreicht und auch die Standardabweichung über alle
Fitnessläufe reduziert sich erheblich. Deutlich zeigt die Linear-Graph
Struktur auch für dieses Problem die Überlegenheit gegenüber den anderen
Strukturen, diese kann sowohl durch die bessere Fitness als auch durch die
kleinere Standardabweichung gesehen werden.
 

%\clearpage
\begin{figure} [!h]
\begin{minipage}{7cm}

\centerline{\epsfig{figure=Pictures/Results/GNUspiral10.ps,width=7cm}}%,height=6cm}}
\caption{Die Fitness für das Spiral Problem mit 10 Individuen zeigt ein
  ähnliches Bild wie für das Chain Problem mit 10 Individuen. Das Besondere
  hier ist das gute Abschneiden der Linear-Tree Struktur, die hier etwa die
  gleichen Ergebnisse wie die Linear-Graph Struktur erreicht. }
\label{fig:FitSpiral10}
%\end{figure}

\end{minipage}
\hfill
\begin{minipage}{7cm}
%\begin{figure} [!h]
\centerline{\epsfig{figure=Pictures/Results/GNUspiral100.ps,width=7cm}}%,height=6cm}}
\caption{Die Fitnessverläufe für das Spiral Problem mit 100 Individuen unterscheiden
  sich stark von den mit 10 Individuen. Hier ist besonders das gute Abschneiden
  der Baumstruktur im Vergleich zu dem Lauf mit 10 Individuen zu
  erkennen. }%Obwohl die Linear-Graph Struktur die besten Ergebnisse liefert ist
%  der Unterschied zu der Baumstruktur sehr gering.}
\label{fig:FitSpiral100}
\end{minipage}
\end{figure}

Die Abbildungen~\ref{fig:FitSpiral10} und \ref{fig:FitSpiral100} zeigen die
Fitnessverläufe für das Spiral Problem mit 10 und 100 Individuen. Der
Unterschied zwischen den Läufen mit 10 und 100 Individuen ist für dieses
Problem ähnlich unterschiedlich wie für das Sinus Problem. Für das Sinus und
das Spiral Problem verbessert sich die Fitness der Baumstruktur so stark,
dass es im Durchschnitt mit 100 Individuen die zweitbeste Fitness erreicht. In
diesem Fall ist sogar der Unterschied der Fitness zwischen der Baum  (42,54) und
Linear-Graph Struktur (41,12) so gering, dass man aufgrund der
Standardabweichung von 1,01828 (Baum) und 0,856771 (Linear-Graph)  das
Ergebnis der Linear-Graph Struktur nicht als eindeutig besser bezeichnen kann.



%\clearpage
\begin{figure} [!h]
\begin{minipage}{7cm}
\centerline{\epsfig{figure=Pictures/Results/GNUmulti10.ps,width=7cm}}%,height=6cm}}
\caption{Die Fitness für das 11-Multiplexer Problem mit 10 Individuen. Die
  lineare und Baumstruktur können keine Lösung finden.}
\label{fig:FitMulti10}
%\end{figure}
\end{minipage}
\hfill
\begin{minipage}{7cm}
%\begin{figure} [!h]
\centerline{\epsfig{figure=Pictures/Results/GNUmulti100.ps,width=7cm}}%,height=6cm}}
\caption{Die Fitness für das 11-Multiplexer Problem mit 100 Individuen. Die
  lineare und Baumstruktur können keine Lösung finden. }
\label{fig:FitMulti100}
\end{minipage}
\end{figure}


Ein ganz anderes Ergebnis präsentiert sich für das Multiplexer Problem, hier
können sowohl die lineare als auch die Baum Struktur keine Lösung für das
Problem finden. Dies gilt sowohl für Populationen mit 10 als auch mit 100
Individuen. Die Abbildungen~\ref{fig:FitMulti10} und \ref{fig:FitMulti100}
zeigen die Ergebnisse für die Läufe. Es hat sich gezeigt, dass sowohl die
lineare als auch die Baumstruktur für das Multiplexer Problem Lösungen finden
können, die auch gut sind, jedoch benötigen sie dazu größere Populationen. So
können beide Strukturen mit einer Population von 200 Individuen zu Lösungen
kommen, besser sind jedoch Populationen von 500 Individuen, da dann der Anteil
der guten Lösungen größer ist als der Anteil der schlechten Lösungen.
Für dieses Problem generiert die Linear-Tree Struktur die besten Ergebnisse,
die Linear-Graph zeigt hier zwar auch gute Ergebnisse, aber herausragend ist
die geringe Standardabweichung in den Ergebnissen.


%
% !!!  Daten letzte Generation
%

%\newpage

Die folgenden Graphiken zeigen immer die Fitness des besten Individuums in der
letzten Generation für jeden der 100 Läufe. Die Ergebnisse wurden hierzu vorher
sortiert, sie zeigen also keine zeitliche Abfolge. Durch diese Graphiken kann
man nun die Daten sehen, aus der sich die Standardabweichung berechnet.


Die Abbildung~\ref{fig:LastFitSin10} und \ref{fig:LastFitSin100} zeigen die
Ergebnisse der Läufe für das Sinus Problem. Es zeigt sich immer,
dass die Variation der Ergebnisse für die Baumstruktur am größten ist im
Vergleich zu den anderen Strukturen, was auch zu den hohen
Standardabweichungen in den Fitnessplots führt. Gleichzeigt sieht man auch
die erhebliche Verringerung bei der Variation der Ergebnisse für die
Baumstruktur in den Abbildungen mit Populationen von 100 Individuen. 

Es hat sich sogar gezeigt, dass die Baumstruktur für das Rastrigin Problem
mit 100 Individuen Lösungen finden kann, die sehr gut sind, jedoch sind dies
sehr wenige und gleichzeitig werden auch sehr viele
schlechte Lösungen evolviert, siehe Abbildung \ref{fig:LastFitMex100}. Ein
ähnliches Argument gilt auch für die Linear-Tree Struktur, sie erzeugt hier
die besten Lösungen, aber auch mehr schlechtere als die Linear-Graph Struktur.

Für das Chain Problem kann die Baumstruktur nicht so gute Ergebnisse liefern
wie für das Rastrigin Problem, hier ist nicht nur die Varianz der Ergebnisse
größer als für die Linear-Tree und Linear-Graph Strukturen, sondern auch die
besten Lösungen sind viel schlechter, siehe Abbildung~\ref{fig:LastFitChain10}
und \ref{fig:LastFitChain100}.
Beim Spiral Problem sind die Unterschiede zwischen den einzelnen Ergebnissen
nicht so groß, jedoch kann man auch hier die geringe Varianz in den
Lösungen der Linear-Graph Struktur erkennen, siehe
Abbildung~\ref{fig:LastFitSpiral10} und \ref{fig:LastFitSpiral100}.

Die Abbildungen~\ref{fig:LastFitMulti10} und \ref{fig:LastFitMulti100} zeigen
das extreme Verhalten der linearen und Baumstruktur noch einmal sehr deutlich.
Gleichzeitig sieht man jetzt aber auch, dass die Linear-Tree Struktur sehr
viel bessere Lösungen schafft als die Linear-Graph Struktur, so kann die
Linear-Tree Struktur mehrmals die optimale Lösung erreichen, was der
Linear-Graph Struktur nicht gelingt.


%\clearpage
\begin{figure} [!h]
\begin{minipage}{7cm}
\centerline{\epsfig{figure=Pictures/Results/LGSinus10.eps,width=7cm}}%,height=6cm}}
\caption{Die Fitness des besten Individuums in der letzten  Generation von
  allen Strukturen. Für das Sinus Problem mit 10 Individuen.}
\label{fig:LastFitSin10}

\end{minipage}
\hfill
\begin{minipage}{7cm}

\centerline{\epsfig{figure=Pictures/Results/LGSinus100.eps,width=7cm}}%,height=6cm}}
\caption{Die Fitness des besten Individuums in der letzten  Generation von
  allen Strukturen. Für das Sinus Problem mit 100 Individuen. }
\label{fig:LastFitSin100}
\end{minipage}
\end{figure}



%\clearpage
\begin{figure} [!h]
\begin{minipage}{7cm}
\centerline{\epsfig{figure=Pictures/Results/LGMexHat10.eps,width=7cm}}%,height=6cm}}
\caption{Das Rastrigin Problem mit 10 Individuen. }
\label{fig:LastFitMex10}

\end{minipage}
\hfill
\begin{minipage}{7cm}

\centerline{\epsfig{figure=Pictures/Results/LGMexHat100.eps,width=7cm}}%,height=6cm}}
\caption{Das Rastrigin Problem mit 100 Individuen. }
\label{fig:LastFitMex100}
\end{minipage}
\end{figure}




%\clearpage
\begin{figure} [!h]
\begin{minipage}{7cm}

\centerline{\epsfig{figure=Pictures/Results/2Chains10.eps,width=7cm}}%,height=6cm}}
\caption{Das Chain Problem mit 10 Individuen.}
\label{fig:LastFitChain10}

\end{minipage}
\hfill
\begin{minipage}{7cm}

\centerline{\epsfig{figure=Pictures/Results/2Chains100.eps,width=7cm}}%,height=6cm}}
\caption{Das Chain Problem mit 100 Individuen. }
\label{fig:LastFitChain100}
\end{minipage}
\end{figure}


%\clearpage
\begin{figure} [!h]
\begin{minipage}{7cm}
\centerline{\epsfig{figure=Pictures/Results/LGSpiral10.eps,width=7cm}}%,height=6cm}}
\caption{Das Spiral Problem mit 10 Individuen. }
\label{fig:LastFitSpiral10}

\end{minipage}
\hfill
\begin{minipage}{7cm}

\centerline{\epsfig{figure=Pictures/Results/LGSpiral100.eps,width=7cm}}%,height=6cm}}
\caption{Das Spiral Problem mit 100 Individuen. }
\label{fig:LastFitSpiral100}
\end{minipage}
\end{figure}


%\clearpage
\begin{figure} [!h]
\begin{minipage}{7cm}
\centerline{\epsfig{figure=Pictures/Results/LGMultiplex10.eps,width=7cm}}%,height=6cm}}
\caption{Das Multiplexer Problem mit 10 Individuen. }
\label{fig:LastFitMulti10}

\end{minipage}
\hfill
\begin{minipage}{7cm}

\centerline{\epsfig{figure=Pictures/Results/LGMultiplex100.eps,width=7cm}}%,height=6cm}}
\caption{Das Multiplexer Problem mit 100 Individuen. }
\label{fig:LastFitMulti100}
\end{minipage}
\end{figure}



%----------------------------------------------------------------------
\subsection{Analyse der Linear-Tree und Linear-Graph Struktur }
%----------------------------------------------------------------------
\label{sub:linTreeAna}

Die Analyse der Linear-Tree und Linear-Graph Struktur zeigte zwei Verhaltensweisen der
neuen Strukturen. Eine bezieht sich auf das Verhalten der
Individuenstruktur während der Evolution und die zweite auf den Aufbau
der Individuen selber. Es zeigte sich nämlich bei dem Aufbau der
Individuen, dass in verschiedenen Knoten des Baums, aber auch des Graphen die
gleichen linearen Segmente existierten. Dies hatte einerseits zur Folge, dass
die Möglichkeit der
Verzweigung umgangen wurde, da beide Nachfolger eines Knotens den
gleichen Code enthielten, und anderseits, dass der Programmfluss
virtuell wieder zusammenfloss. Denn wenn die Blätter des Baumes die
gleichen Knoten enthielten, hätte man sie auch zu einem Knoten
zusammenfassen können und hätte somit einen Graphen erzeugt. Dies war
auch einer der Gründe, die Linear-Graph Individuenstruktur zu implementieren.
In den meisten Individuen wurden allerdings die Verzweigungen genutzt. 
Hierbei ist hervorzuheben, dass die Verzweigungen sowohl für
Klassifikationsprobleme als auch für Regressionsprobleme von Vorteil
sind. Wenn man die Ergebnisse der Individuen während der Evolution für
ein Regressionsproblem verfolgt, kann man sofort den Unterschied
zwischen Linear oder Baum GP Programmen und den Linear-Tree Programmen
erkennen. Anhand der Abbildungen~\ref{fig:sinEvo1} und \ref{fig:sinEvo2} kann
man die Unterschiede der Individuenstrukturen Linear-Tree und Linear-Graph
bezüglich der Evolution im Vergleich zu den anderen Strukturen erkennen. Es
wurde exemplarisch die Entwicklung  der Sinuskurve gewählt, da man hier sehr
gut den Unterschied in dem Evolutionsprozess zwischen der Linear-Tree
und den anderen Strukturen erkennen kann. So wird in diesem Beispiel von einem
Linear-Tree Individuum zuerst die erste Hälfte der Sinusfunktion approximiert
und die Evolution beginnt erst nach der Generation 11,
die zweite Hälfte der Funktion zu approximieren. Bei den anderen
beiden Strukturen erkennt man, dass verschiedene Polynome verwendet werden, um
die Sinusfunktion zu
approximieren. Wenn man sich nun das Individuum selbst betrachtet,
sieht man, dass ein Linear-Tree oder Linear-Graph Individuum oft bei einer
Branchingentscheidung überprüft, ob die Eingabe ungefähr größer als 3 ist.
%Diese Branchingentscheidung gab es schon in der Generation 11
% in dem besten Individuum des Pools.
Dies kann man auch
deutlich in der Abbildung~\ref{fig:sinEvo1} erkennen, da sich an dieser
Stelle eine Unstetigkeit gebildet hat. Weiter kann man erkennen, dass
die Evolution der zweiten Hälfte der Sinusfunktion in einer kürzeren
Zeit geschieht als für die erste Hälfte. Man kann auch einen
qualitativen Unterschied in der Entwicklung erkennen. So beginnt die
Approximationsphase für die zweite Hälfte der Sinusfunktion sehr
schnell mit einer Kurve, die der Kurve der ersten Hälfte der Funktion entspricht.

\begin{figure}% [ht]
\begin{minipage}{7cm}

\centerline{\epsfig{figure=Pictures/Results/kurve11A.eps,width=7cm}}
\caption{ Das Linear-Tree Individuum evolviert zuerst die erste Hälfte der Sinusfunktion
und beginnt erst nach der Generation 11, die zweite Hälfte der Funktion zu
approximieren. }
\label{fig:sinEvo1}
\end{minipage}
\hfill
\begin{minipage}{7cm}
\centerline{\epsfig{figure=Pictures/Results/kurve30A.eps,width=7cm}}
\caption{ In dieser Graphik sieht man das Ergebnis der Evolution nach 30
  Generationen, nun ist auch die zweite Hälfte der Funktion approximiert worden. }
\label{fig:sinEvo2}
\end{minipage}
\end{figure}

Man kann neben dem objektiven Unterschied in der Evolution der verschiedenen
Strukturen, der sich durch die unterschiedliche Entwicklung der Fitness
ergibt, auch einen eher subjektiven Unterschied erkennen, wie er oben
am Beispiel der Evolution für das Sinusproblem beschrieben wurde. Dieser
subjektive Unterschied gibt aber auch einen Hinweis auf die \emph{Building
  Blocks}, die während der Evolution zwischen den Individuen getauscht
werden. Der Unterschied zu der \emph{Building Block Hypothese}, wie sie
in~\cite{holland} und ~\cite{forrest93relative,thornton97bbh} beschrieben werden,
ist, dass die Blöcke
in den Linear-Tree und -Graph Strukturen durch den Aufbau des Individuums
selbst vorgegeben sind. Hier werden die Linear Segmente als \emph{Building Block}
benutzt, was durch die Struktur und durch die Rekombination unterstützt wird.


%----------------------------------------------------------------------
\subsection{ Analyse des Crossover Operators}
%----------------------------------------------------------------------
\label{TEST:linTreeXover}
 

Da der Crossover Operator der Linear-Tree und Linear-Graph Strukturen aus
zwei Phasen besteht, ergibt sich automatisch der Parameter
$prob_{\textit{xover}}$, der angibt, mit welcher Wahrscheinlichkeit eine
linearbasierte Crossovermethode oder eine baumbasierte-
bzw. graphbasierte Crossovermethode verwendet wird (siehe Abschnitt \ref{sub:LinGraphRecom}
und \ref{subsec:Recom}).
Da es sich bei beiden Strukturen um neue GP Strukturen handelt, ist nicht genau
klar, welchen Wert dieser Parameter haben sollte. Eine hohe Wahrscheinlichkeit
für $prob_{\textit{xover}}$ hat zur Folge, dass hauptsächlich das baum-
bzw. graphbasierte Crossover angewendet wird. Dadurch werden große
Teilsegmente des Individuums beim Crossover ausgetauscht und der Programmfluss
des Individuums verändert sich durch die neuen Elemente stark. Es stellt sich
automatisch die Frage, ob es einen optimalen Wert für diesen Parameter gibt und
wie er lautet. Hierzu wurden für das Sinus- und das 2-Chain Problem 100 Läufe
mit Werten von 0\% bis 100\% in 10\% Schritten durchgeführt. Da es nur um die
Analyse des Crossoveroperators geht, wurde die Mutation für diese Untersuchung
zuerst nicht verwendet.

In den Abbildungen~\ref{fig:chainXoverMutat} und~\ref{fig:sinXoverNoMutat}
sind die Ergebnisse für die Linear-Graph Struktur für die beiden Probleme
dargestellt. In den Abbildungen sind nur die Fitnesskurven für die
Parametereinstellung von 0, 30, 50 und 70 \% dargestellt, da sie unter allen
Ergebnissen das Minimum, das Maximum und durchschnittliche Werte darstellen.
In der Abbildung~\ref{fig:sinXoverNoMutatAll} sind noch mal die Fitnesskurven
mit allen Parametern für das Sinusproblem abgebildet. In der Abbildung kann
man deutlich
ein Cluster erkennen, in dem fast alle Einstellungen liegen. Die besten
Einstellungen für den Parameter sind 20 und 30\% und die schlechteste
Einstellung ist 0\%. Dieses Bild ähnelt dem für das Chain-Problem, nur die Werte
für die Extremwerte sind andere, so ist die beste Einstellung für den
Parameter 50\% und die schlechteste 30\%. Anhand dieser beiden Beispiele
erkennt man direkt, dass es keine optimale Einstellung gibt, die von der
Problemstellung unabhängig ist. Daher wäre eine Adaptation des Wertes während
der Evolution auf der Grundlage dieser Ergebnisse die beste Lösung. Es hat
sich jedoch gezeigt, dass der Wert des Parameters unkritisch ist, wenn man bei
den Evaluationen die Mutation mitverwendet. Denn dann liegen alle Werte so nahe
zusammen, dass man keinen signifikanten Unterschied für die verschiedenen Werte
erkennen kann. Somit wird der Einfluss, den der Parameter auf die Evolution hat,
durch die Mutation wieder aufgehoben. Gleichzeitig verbessern sich die Ergebnisse
der Evolution, so erreichen die Evolutionen ohne Mutation im Durchschnitt im besten
Fall eine Fitness von $1,7$ und mit Mutation von $1,1$. Dass der Mutationsoperator
die Einstellung der Crossoverparameter überschattet, ist nicht leicht zu
erklären. Für die Linear-Tree Struktur ergibt sich ein ähnliches Bild bezüglich
des Crossover- und Mutationsoperators: Wenn beide Operatoren aktiv sind, kann man
keinen Unterscheid zwischen den verschiedenen Parametereinstellungen für den
Crossoveroperator erkennen. Die Abbildung~\ref{fig:sinXoverLinTree} zeigt daher
das Verhalten der Linear-Tree Struktur für das Sinusproblem ohne Mutation
für die Parametereinstellungen 10\%, 50\% und 90\%. Hier zeigt sich deutlich, dass
90\% der beste Wert für dieses Problem wäre, wie aber schon erwähnt ergeben sich
Unterschiede für die verschiedenen Einstellungen, wenn der Mutationsoperator
auch aktiv ist.





\begin{figure} [!h]
\begin{minipage}{7cm}
\centerline{\epsfig{figure=Pictures/Results/GNUchainXSmall.ps,width=7cm}}%,height=6cm}}
\caption{Die Abbildung zeigt die Fitness für das 2 Chain Problem ohne Mutation
  für verschiedene Werte des Crossoverparameters $prob_{\textit{xover}}$ für
  die Linear-Graph Struktur.}
\label{fig:chainXoverMutat}
%\end{figure}
\end{minipage}
\hfill
\begin{minipage}{7cm}
%\begin{figure}% [ht]
\centerline{\epsfig{figure=Pictures/Results/GNUsinusXSmall.ps,width=7cm}}%,height=6cm}}
\caption{Die Abbildung zeigt die Fitness für das Sinusproblem ohne Mutation
  für verschiedene Werte des Crossoverparameters $prob_{\textit{xover}}$ für
  die Linear-Graph Struktur.}
\label{fig:sinXoverNoMutat}
\end{minipage}
\end{figure}


\begin{figure}% [!h]
\begin{minipage}{7cm}
\centerline{\epsfig{figure=Pictures/Results/GNUsinusX.ps,width=7cm}}%,height=6cm}}
\caption{Die Abbildung zeigt die Fitness für das Sinusproblem ohne Mutation
  für alle getesteten Werte des Crossoverparameters $prob_{\textit{xover}}$ für
  die Linear-Graph Struktur. Die besten Ergebnisse werden für das Problem mit
  20 oder 30\%, das schlechteste Ergebnis mit 0\% Wahrscheinlichkeit erreicht.}
\label{fig:sinXoverNoMutatAll}
%\end{figure}
\end{minipage}
\hfill
\begin{minipage}{7cm}
%\begin{figure}% [ht]
\centerline{\epsfig{figure=Pictures/Results/sinusXoverLinTree.eps,width=7cm}}%,height=6cm}}
\caption{Die Abbildung zeigt die Fitness für das Sinusproblem ohne Mutation
  für alle getesteten Werte des Crossoverparameters $prob_{\textit{xover}}$ für
  die Linear-Tree Struktur. Die Kurve `Mutation` zeigt zum Vergleich das Verhalten
  ganz ohne Crossover an.}
\label{fig:sinXoverLinTree}
\end{minipage}
\end{figure}


Abschließend kann man für die Crossoveroperatoren der Linar-Tree und
Linear-Graph Strukturen sagen, dass die Verwendung des Mutationsoperators wichtig
ist, wenn man gute Ergebnisse erreichen möchte. Der Parameter
$prob_{\textit{xover}}$ hat nur bei einem deaktivierten Mutationsoperator
Einfluss auf die Evolution, da die Ergebnisse für die verschiedenen
Parametereinstellungen aber nicht eindeutig sind, ist es schwer hierfür eine
Antwort zu finden. So führte ein kleiner Parameterwert von 20\% für das Chain-Problem
zu schlechten Ergebnissen, wobei er beim Sinus-Problem zu guten Ergebnissen führte.
Obwohl der Crossoveroperator für verschiedene Werte bei verschiedenen Problemen
zu den besten Lösungen gelangte, wird dies durch den Mutationoperator
ausgeglichen. Man kann also nicht behaupten, dass der Mutationsoperator nur eine
geringere Wahrscheinlichkeit des linearbasierten Crossovers ausgleicht, denn er kann auch
eine geringere Wahrscheinlichkeit des graphbasierten Crossovers ausgleichen.
Man kann sich aber anhand der Arbeitsweise des Mutationsoperators klar machen, dass er
sowohl das linearbasierte als auch das graphbasierte Crossover ersetzen kann
(zur Arbeitsweise siehe Abschnitt~\ref{sub:LinGraphMut} für das linearbasierte und
Abschnitt~\ref{sub:LinTreeMut} für das graphbasierte Crossover). Ein hoher Anteil
des linearbasierten Crossovers führt während der Evolution dazu, dass sich die
Baum- oder Graph-Struktur des Individuums nicht sehr stark verändern kann. Der
Mutationsoperator kann aber durch die Mutation der Branchingfunktion oder die
Veränderung der Kanten zu einem ähnlichen Effekt kommen wie der graphbasierte
Crossoveroperator. Dies gilt dadurch, dass es in die Individuen ganze Pfade gibt,
die Introns sind und durch eine Mutation aktiviert werden können und somit wie eine
graphbasierte Crossoveroperation wirken~\cite{angeline:94,levenick91inserting}.
Das gleiche Argument gilt auch für das linearbasierte Crossover, erstaunlich ist
nur, dass während der Evolution eine Mutationsrate von 20\% ausreichend ist, um den
negativen Effekt eines falschen Parameters zu kompensieren. Um dies abschließend
klären zu können, müssten jedoch genaue empirische Tests mit verschiedensten
Parameterkombinationen und Problemen durchgeführt werden, in dieser Arbeit ist
aber nicht der Raum um diese Fragestellung genauer zu untersuchen.




%----------------------------------------------------------------------
\subsection{Fazit der verschiedenen Strukturen}
%----------------------------------------------------------------------


Dieser Unterschied ist sehr wichtig, da das Ziel der Dissertation die
Evolution von Schachprogrammen ist und die Evolution von Schachprogrammen
durch die Fitnessbewertung sehr rechenzeitintensiv ist. Bei den Ergebnissen
der Schachprogramme ist weiter das absolut beste Programm interessant und nicht
die durchschnittlichen Ergebnisse. Somit sind möglichst geringe Variationen in den
Ergebnissen verschiedener Läufe gewünscht.

Bei der empirischen Analyse hat sich gezeigt, dass die Baumstruktur für das Rastrigin
Problem mit 100 Individuen Lösungen finden kann, die besser als die Ergebnisse der
Linear-Graph Struktur sind, jedoch passierte dies während der Analyse selten.
Durch sehr viele schlechte Ergebnisse werden diese Vorteile wieder aufgehoben,
siehe Abbildung~\ref{fig:LastFitMex100}.
Das Bild ändert sich aber sofort, wenn man die Anzahl der Individuen auf 10 reduziert,
die Anzahl der schlechten Resultate steigt für die Baumstruktur stark an und sie kann auch
nicht das Ergebnis erreichen, welches für diese Einstellung durch die Linear-Tree
Struktur erreicht wird, siehe Abbildung~\ref{fig:LastFitMex10}.
Ein ähnliches Argument gilt auch für
die Linear-Tree Struktur, sie erzeugt für dieses Problem die besten Lösungen, aber
auch mehr schlechtere als die Linear-Graph Struktur. Für fast alle anderen Probleme
lieferten die neuen GP Strukturen immer bessere Ergebnisse als die lineare oder
Baumstruktur. Die Ausnahme waren hier die Testläufe für das Spiralproblem mit
100 Individuen, in der sich die Baumstruktur zwar schlechter als die Linear-Graph
Struktur schlug, aber besser als die Linear-Tree Struktur, wie man in der
Abbildung~\ref{fig:FitSpiral100} gut erkennen kann. Das Bild ändert sich
aber sofort, wenn man sich die Testläufe mit 10 Individuen betrachtet. Dann
können die Ergebnisse der Baumstruktur nicht mehr mit den neuen GP Strukturen
konkurrieren, siehe Abbildung~\ref{fig:FitSpiral10}. Dies ist aber ein wichtiger Punkt für die Evolution von Schachprogrammen,
denn durch den hohen Rechenaufwand muss man mit wenigen Individuen und wenigen
Evaluationen auskommen. Die neuen Strukturen konnten schon nach weniger
als 10.000 Evaluationen die gleiche Fitness erreichen, welche die Baumstruktur
erst nach 200.000 Evaluationen erreichen konnte. Ein ähnliches Verhalten
erkennt man für das Chain-Problem, hier ist es nicht nur bei den Tests mit
10 Individuen, sondern auch mit 100 Individuen wiederzufinden. Für einige andere
Probleme sind die Ergebnisse der Linear-Tree und -Graph Strukturen so dramatisch
besser, dass man diese Strukturen den anderen vorziehen muss.

Während der Analyse hat sich aber auch klar gezeigt, dass die Linear-Graph Struktur
gegenüber der Linear-Tree Struktur einen wichtigen Vorteil hat, denn die Ergebnisse der
Linear-Graph Struktur haben eine viel kleinere Varianz als die der anderen Strukturen.
Dies ist schon an den Standardabweichungen in den Plots zu erkennen, aber besonders
gut kann man es in den Abbildungen~\ref{fig:LastFitSin10} bis~\ref{fig:LastFitMulti100}
erkennen. Hier ist immer die Fitness der letzten Generation für alle durchgeführten
Läufe abgebildet. Man erkennt gut, dass bis auf die Läufe für das
Sinusproblem mit 100 Individuen und das Spiralproblem mit 10 Individuen, in
beiden Fällen hatte die lineare Struktur die schlechtesten Ergebnisse erzeugt,
immer die GP Läufe mit Baumstruktur die schlechtesten Ergebnisse
lieferten. Diese Struktur hat zwar auch sehr gute Ergebnisse erzielt, erreichtet diese aber
sehr selten. Für die
Aufgabenstellung in dieser Arbeit, wird eine GP-Struktur benötigt, die mit kleinen
Pools arbeiten kann, die gute Ergebnisse findet und die eine möglichst geringe
Varianz in den Ergebnissen erzeugt. Der letzte Punkt ist eigentlich auch der
wichtigste Punkt für diese Arbeit, da Schachprogramme evolviert werden sollen, ist
das Ziel, \emph{ein} sehr gutes Programm zu erhalten und da die Rechenzeiten
sehr hoch sind, möchte man dieses Ziel mit so wenig Evolutionsläufen wie möglich erreichen.
Daher fiel für das GeneticChess System die Wahl für die interne Struktur der
Individuen auf die Linear-Graph Struktur.



%%% Local Variables:
%%% mode: latex
%%% TeX-master: "mainChessDiss"
%%% End:
%
