
%\newpage
%\label{GP-Erweiterungen}


%----------------------------------------------------------------------
%\section{Erweiterung von GP für GeneticChess}
%----------------------------------------------------------------------

Das Ziel von GeneticChess ist das Schachspiel, also muss es
dem GP-System möglich sein, Algorithmen zu entwickeln, die dieses
komplexe Problem lösen. Im Abschnitt~\ref{sec:comptTheo} wurden die
verschiedenen Algorithmen vorgestellt, mit deren Hilfe der Computer
Schach spielen kann. Diese Algorithmen sind die Kernalgorithmen für
die Berechnung des nächsten Zuges, also der Suchalgorithmus ohne
Erweiterungen durch Datenbanken, wie sie heute in Schachprogrammen
üblich sind.  Wenn man diese Algorithmen aber analysiert, sieht man
sehr schnell, dass es sich um rekursive Algorithmen handelt, deren
Programmfluss stark von der
Berechnung von Zwischenergebnissen abhängt. Vergleicht man dies mit
dem Verhalten von GP-Programmen, sieht man sofort den Unterschied %. Die
zu den bekannten Individuenstrukturen %in GP-Systemen
%\begin{itemize}
 Baum GP~\cite{koza1,koza2},
 Linear GP~\cite{nordin:linGP,banzhaf:1997:book} und
 Graph GP~\cite{Ang98,Pol97}. %graph nur mit datenfluss
%\end{itemize}
%zeichnen sich dadurch aus, dass der Programmfluss fast ausschließlich
%durch die Struktur der Programme festgelegt ist. 
Nur durch Funktionen,
die Konditionale oder Sprünge enthalten, kommt es zu einem begrenzten
Einfluss auf den Programmfluss. Keine dieser Strukturen ruft sich
rekursiv auf. Aus diesem Grund ist eine Neuentwicklung
von Individuentypen für ein GP-System notwendig, die
Suchprobleme lösen sollen. Daher wurden Individuentypen entwickelt,
die eine stärkere Flexibilität im Programmfluss haben und ein
Individuentyp, dem es möglich ist Probleme, rekursiv zu behandeln.

Ein weiteres Hindernis bei der Entwicklung von Schachprogrammen mit
evolutionären Systemen ist einerseits die Komplexität eines
Algorithmus, der das Problem lösen kann, und andererseits die
benötigte Rechenzeit, um ein Individuum zu bewerten. Aus diesen
Gründen hat sich die Notwendigkeit ergeben, das Schachproblem in
einzelne Module zu unterteilen und in einem modularen und hierarchischen
Individuum wieder zusammenzufassen.



%----------------------------------------------------------------------
%\section{Neue Individuentypen}
%----------------------------------------------------------------------
\label{sec:IndType}

Für das GeneticChess System wurden im Rahmen der vorliegenden Arbeit
drei neue Individuentypen entwickelt:
\begin{itemize}
\item \emph{Linear-Tree},
\item \emph{Linear-Graph},
\item \emph{State-Space-GP}.
\end{itemize}


Alle neuen Individuentypen sollen zu einer größeren Komplexität der
Lösungen und zu einer höheren Flexibilität der evolvierten Programme
führen. Wenn im
weiteren über \emph{Individuenstrukturen}\index{Individuenstruktur}
gesprochen wird, sind immer die Standardstrukturen, Linear-Tree
oder Linear-Graph gemeint.

Die Individuenstrukturen \emph{Linear-Tree} und \emph{Linear-Graph} sind
\emph{hybride Individuen}\index{hybride Individuen}, damit sind
GP-Strukturen gemeint, die sich aus verschiedenen Strukturen
zusammensetzen. Normalerweise besteht der Aufbau eines Individuentyps
immer nur aus einer Struktur, also reine lineare Individuen,
Bäume oder Graphen. Jedoch wurde vorher nie versucht zwei oder
mehrere Strukturen in einem Individuum zu verbinden. Die
Individuentypen Linear-Tree und Linear-Graph beruhen aber genau auf
diesem Ansatz. Diese Verschmelzung zweier Strukturen erzwingt in den
Individuen einen Aufbau, der es der Evolution erleichtern soll, ein
Problem in Teilprobleme aufzuteilen.

Das \emph{State-Space GP}\index{State-Space GP} unterscheidet sich von
den beiden anderen
Individuenstrukturen dadurch, dass es nicht eine Erweiterung der Struktur
eines Individuums ist, sondern dass der Programmfluss des Individuums in
gewissen Bereichen vorgegeben ist. Der Programmfluss in diesem
Individuum ist so angelegt, dass es Teile seines Codes
rekursiv aufrufen kann.

%
Die Besonderheit des Programmflusses\index{Programmfluss} verbindet
die drei neuen Individuenstrukturen miteinander. In den
Individuenstrukturen \emph{Linear-Tree} und \emph{Linear-Graph}  wird
der Baum oder der Graph als Grundlage des Programmflusses benutzt, bei
dem \emph{State-Space GP} wird der Programmfluss durch die Definition
der einzelnen Individuenteile und deren Aufrufreihenfolge bestimmt. %Die
%Kombination von Programmfluss und Datenfluss in einer Individuenstruktur war
%einer der
%Gründe diese Strukturen zu entwickeln. 
Wenn man die aktuellen
Strukturen von GP-Individuen untersucht, sieht man sofort, dass die
Individuenstruktur keine Kontrollstrukturen für den Programmfluss
besitzt. Individuen erzielen ihr Ergebnis allgemein durch
Modifikation des Datenflusses. %, damit ist es aber nur sehr begrenzt möglich
%Individuen für Probleme zu evolvieren, die keinen linearen
%Programmfluss besitzen. Um dieses Problem zu umgehen werden
%normalerweise die Funktionsmengen um Funktionen erweitert, die
%Verzweigungen zulassen, um somit einen nicht linearen Programmfluss
%zu erreichen. 
In linearen Strukturen ist dies ein Sprungbefehl, der
Knoten des Individuums überspringt, wenn die Aussage des
Sprungs wahr ist. Durch Verwendung dieses Befehls können nicht nur Knoten zu
Exons\index{Exon} werden, die vorher
Introns\index{Introns}~\cite{brameier:2001,levenick91inserting} waren.
Der Effekt
des Sprungbefehls ist somit mehr als nur das Überspringen eines Knotens,
sondern die Folge der Exons ab dem Sprungbefehl. Jedoch muss es der Evolution
hier
gelingen, mehrere Programmflüsse in eine lineare Sequenz
einzubauen. %Das heißt, die Sequenz von Knoten, die nach dem
%Sprungbefehl kommt, muss sowohl für den Fall eines Sprunges als auch
%den ohne Sprung zu sinnvollen Ergebnissen kommen. Dies ist allgemeinen
%eine komplizierte Aufgabe und kann durch eine Mutation oder ein
%Crossover schnell zerstört werden.
Durch die Vorgabe einer Struktur, die nur den Programmfluss
darstellt, erleichtert man somit der Evolution, solche Programmflüsse
zu finden. Die Vereinfachung sollte den Individuen nun ermöglichen die
gegebenen Resourcen zu nutzen, um schneller eine gute Lösung zu finden.

Wenn man sich den Kontrollfluss in Programmen verdeutlicht, die von
Menschen geschrieben wurden, findet man nur in einfachen Routinen
lineare Programmflüsse. Normalerweise enthalten diese Programme sehr
komplexe Programmflüsse, betrachtet man ein einfaches
Schachprogramm, so findet man auch in ihnen einen
komplexen Programmfluss. Wenn man dies als Grundlage nimmt, kann man
davon ausgehen, dass der Programmfluss ein wichtiges Instrument ist, um
komplexe Programme zu implementieren. Daher wurden die neuen
GP-Strukturen mit dem Ziel entwickelt, Individuen und damit auch
Programme zu evolvieren, die nicht nur auf dem Datenfluss beruhen,
sondern einen starken Gebrauch von dem Programmfluss machen. %Aus
%diesem Grund wurden Individuen aus zwei Strukturen entwickelt, wobei
%eine Struktur den Datenfluss und die zweite den Programmfluss
%darstellt. Durch diese Kombination kommen die neuen
%Individuenstrukturen der Komplexität von Programmen, die nicht automatisch
%erzeugt wurden, etwas näher, ohne diese schon erreichen zu können.

In den folgenden Abschnitten werden nun die verschiedenen
Individuenstrukturen genauer beschrieben, wobei die Reihenfolge der Kapitel
deren zeitlicher Entwicklung folgt. Abschließend werden die
Ergebnisse der einzelnen Strukturen auf verschiedenen
Benchmarkproblemen verglichen. Hierbei wird das \emph{State-Space GP}
nicht mit analysiert, da die implementierte Variante starke
Spezialisierungen für das Schachproblem beinhaltet und so nur in
diesem Umfeld ihre Stärken zeigen kann.




%----------------------------------------------------------------------
\section{Linear-Tree GP}
%----------------------------------------------------------------------
\label{sub:LinTree}

\emph{Linear-Tree}\index{Linear-Tree} ist eine neue Repräsentation
eines GP-Programms, die erstmals eine Kombination von Daten- und
Programmfluss durch die Struktur der Individuenrepräsentation
vorgibt. Der Name des Individuentyps impliziert schon, dass das
Individuum eine Kombination aus einer linearen und einer Baumstruktur
ist. Die lineare Struktur des Individuums stellt den Datenfluss während
der Evaluation dar und die Baumstruktur den Programmfluss.
%Die Grundstruktur ist ein Baum, in dessen Knoten lineare Sequenzen von
%Befehlen enthalten sind.
Weitere Ergebnisse zu dieser Struktur wurden auf der EuroGP Konferenz
2001 veröffentlicht~\cite{kantschik:2001:EuroGP}.


%In den folgenden Abschnitten werden nun der Aufbau dieser Struktur, die
%Interpretation eines solchen Individuums und die Besonderheiten beim
%Crossover und der Mutation genauer beschrieben.




%----------------------------------------------------------------------
\subsection{Die Struktur}
%----------------------------------------------------------------------
\label{sec:linTreeStrukt}

Die \emph{Linear-Tree} Struktur ist eine Kombination aus einer
Baumstruktur und einer linearen Struktur. Abbildung~\ref{fig:linTreeProg}
verdeutlicht den Aufbau der Linear-Tree Struktur, bestehend aus
einem Baum als Grundstruktur, und den Aufbau der einzelnen Knoten des Baumes.
\begin{wrapfigure}{r}{80mm}
%\begin{figure}
\centerline{\epsfig{figure=Pictures/Graphik/linearTree.eps,width=8cm}}
\caption{Struktur eines Linear-Tree Individuums. %Der Baum bildet den
 %möglichen Programmfluss ab und die linearen Sequenzen den Datenfluss
%in den einzelnen Knoten. Die Knoten des Baumes bestehen aus einem
%linearen GP-Programm, hier blau dargestellt, und dem Branching Knoten,
%als rote Pyramide dargestellt. 
}
\label{fig:linTreeProg}
\end{wrapfigure}%{figure}


Die Baumstruktur eines Linear-Tree Individuums ist nicht mit
der Baumstruktur eines baumbasierten GP-Individuums zu vergleichen. Es
ergeben sich hierbei Unterschiede in der Auswertung der Individuen und
lineare Sequenzen in den einzelnen Knoten des Baums. %Im Falle des Baum GP's
%enthalten die Knoten jeweils eine Funktion, ein Terminal oder eine
%Konstante. 
Im Falle von Linear-Tree ist der Knoten in zwei
Komponenten unterteilt, eine \emph{lineare Sequenz} von Befehlen und
einn \emph{Branching Knoten}. Abbildung~\ref{fig:lintreeNode} zeigt
den Aufbau des Knotens mit den beiden Komponenten.

\begin{wrapfigure}{r}{80mm}
%\begin{figure}
\centerline{\epsfig{figure=Pictures/Graphik/knoten.eps,width=8cm}}
\caption{Der Aufbau eines Linear-Tree Knotens. %Der Knoten besteht aus
%einer linearen Sequenz von Befehlen und dem Branching Knoten. Dieser
%Knoten kontrolliert den Programmfluss während der Evaluierung der
%Struktur.
}
\label{fig:lintreeNode}
\end{wrapfigure}%{figure}

Die \emph{lineare Sequenz}\index{lineare Sequenz} hat den Aufbau eines
normalen linearen Individuums mit variabler Länge. Jeder Knoten in
dieser Sequenz ist eine Funktion, die auf indexierte Variablen,
Konstanten oder Terminale zugreifen kann. Die Knoten werden dabei
immer als Registeraufrufe implementiert, also in der Form:
\[
        Reg(1)= op(Reg(2),x) , \text{mit } x \in \Rc, \Kc, \Tc.
\]

Wobei \Rc\ die Menge der indexierten Variablen oder auch Register ist,
\Kc\ die Menge der Konstanten und \Tc\ die Menge der Terminale.
Während der Interpretation eines Individuums wird über die Register
der Datenfluss der linearen Sequenz etabliert. Während der gesamten
Evolution gilt für die lineare Sequenz, dass ihre Länge in einem
vorgegebenen Intervall liegen muss. Dadurch erzwingt man, dass sich
keine Knoten bilden können, deren lineare Sequenz die Länge 0 hat und die
somit nicht zum Gesamtergebnis beitragen können oder durch die Bloat
Problematik zu unendlichem Wachstum tendieren (siehe auch \cite{brameier:2002:EuroGP}).


Der \emph{Branching Knoten}\index{Branching Knoten} enthält immer eine
Entscheidungsfunktion, die auf der Grundlage der durch die lineare
Sequenz berechneten Werte eine der Nachfolgerknoten des Knotens
bestimmt, der dann ausgewertet wird.
Dadurch bestimmt auch die \emph{Branching Funktion} den Ausgrad des
Knotens im Baums. Kann eine Funktion nur eine binäre Entscheidung
treffen, hat der Knoten nur zwei ausgehende Kanten. Die Struktur des
Baumes wird somit indirekt über die gewählten Branching Funktionen
bestimmt. %Wenn alle Funktionen binär sind, erhält man also einen
%binären Baum. 
Wählt man Funktionen mit höherem Ausgrad, erhält man
somit auch Bäume mit einem höheren Verzweigungsgrad. Es wird jedoch
auch zugelassen, dass bei binären Funktionen beide Kanten den gleichen
Nachfolger verbinden.

Wenn man diese Struktur nun auf einer abstrakteren Ebene
betrachtet, bildet der Baum die Struktur eines Programms ab. Jeder
Knoten ist ein Unterprogramm mit dem Branching Knoten als das Element,
welches den Programmfluss steuert.


%----------------------------------------------------------------------
\subsection{Evaluierung der Linear-Tree Struktur}
%----------------------------------------------------------------------

Der entscheidende Unterschied zwischen einem Linear-Tree Individuum
und einem normalen baumbasierten Individuum ist bei der Evaluierung
des Individuums zu sehen. In einem Linear-Tree Individuum werden nicht
alle Knoten des Baumes für jeden Fitnesscase ausgewertet, es wird
immer nur ein Pfad durch den Baum bearbeitet. Die Interpretation
beginnt in der Wurzel des Baumes, dort wird zuerst die lineare Sequenz
ausgewertet. Sie berechnet verschiedene Werte, die in den Registern
zwischengespeichert werden. Ist die gesamte Sequenz des Knotens
abgearbeitet,  wird die Funktion im Branching Knoten berechnet. Sie
entscheidet mit Hilfe der Zwischenergebnisse, welcher der
Nachfolgerknoten als nächstes ausgewertet wird. Dies wird solange
durchgeführt, bis ein Knoten erreicht wird, der keine Nachfolgerknoten
mehr hat. Als Ergebnis wird dann der Wert eines Registers
zurückgegeben, welches vorher als Ergebnisregister definiert wurde.


\begin{wrapfigure}{r}{60mm}
%\begin{figure}
\centerline{\epsfig{figure=Pictures/Graphik/linearTreeFlow.eps,width=6cm}}
\caption{Der Programmfluss durch ein Linear-Tree Individuum. Mit Rot
sind die Kanten für den Programmfluss für eine Eingabe X
gekennzeichnet und mit Blau die Kanten für den Programmfluss für eine
Eingabe Y. %Man sieht sofort, dass für verschiedene Eingaben
%verschiedene Teile des Individuums interpretiert werden und somit
%verschiedene Unterprogramme zum Gesamtergebnis beitragen.
}
\label{fig:lintreeProgFlow}
\end{wrapfigure}%{figure}

Da der Weg durch den Baum, also der Programmfluss, abhängig von dem
Ergebnis der Branching Funktion ist, ist er somit auch abhängig
von den Eingabewerten. Damit ergeben sich für verschiedene Eingaben
verschiedene Wege durch den Baum. Die
Abbildung~\ref{fig:lintreeProgFlow} zeigt beispielhaft verschiedenen
Programmflüsse durch den Baum. %Dies war notwendig um den evolvierten
%Schachprogrammen
%eine höhere Flexibilität zu geben, als sie durch die Standardtypen
%gewährleistet wäre.  
Ein Knoten des Programmbaumes kann dadurch für einige
Eingaben aktiv sein und für andere nicht. Dies ermöglicht es der
Evolution, Module zu entwickeln, die einen Teil des Problems lösen
können. Durch die Komposition verschiedener Module für verschiedene
Eingabemengen kann somit ein Gesamtprogramm geschaffen werden.
Anders ausgedrückt ermöglicht diese Struktur eine Dekomposition des
Problems in einfache Teilprobleme.

Um die Module aber für verschiedene Eingaben aktivieren zu können
benötigt man Funktionen, die den Programmfluss steuern. Diese werden
im weiteren immer \emph{Branching Funktionen} \index{Branching
Funktionen} genannt. Die Aufgabe der Funktionen ist es aufgrund der
Zwischenergebnisse zu entscheiden, welcher der Nachfolgerknoten
aktiviert wird. Dazu muss eine Funktion die Zwischenergebnisse
betrachten können, alle Ergebnisse einer Berechnung werden in linearen
GP Systemen immer in den Registern gespeichert. Eines der wichtigsten
Register ist das Ergebnisregister\index{Ergebnisregister}, also das
Register, aus dem am Ende der Evaluation der Wert entnommen wird, der als
Ausgabe interpretiert wird. Somit ist es logisch, diese Register
während der Evaluation zu überwachen, um anhand der Änderungen des
Inhaltes eine Entscheidung zu treffen. Die Tabelle~\ref{tab:BinaerBranchFunk}
enthält eine Sammlung von Funktionen, wie sie während der Testläufe
benutzt wurden. Es sind auch andere Funktionen möglich, jedoch sind
mit diesen Funktionen gute Ergebnisse erzielt worden.

\begin{table}
\begin{center}
\begin{tabular}{|l|p{8cm}|}
\hline
 Branching Funktion & Beschreibung der Funktion\\
\hline 
 Ergebnisregister $ < 0$ & Wenn der Wert des Ergebnisregisters größer
 Null ist, wird der linke Nachfolger gewählt, sonst der rechte. \\
\hline
 Ergebnisregister $ > 0$ & Wenn der Wert des Ergebnisregisters kleiner
 Null ist, wird der linke Nachfolger gewählt, sonst der rechte.\\
\hline
 Ergebnisregister $ == 0$ &   Wenn der Wert des Ergebnisregisters gleich
 Null ist, wird der linke Nachfolger gewählt, sonst der rechte.\\
\hline
 Ergebnisregister $ < $ Konstante & Wenn der Wert des Ergebnisregisters größer
 einer Konstante des Knotens ist, wird der linke Nachfolger gewählt,
 sonst der rechte. \\
\hline
 Ergebnisregister $ > $ Konstante& Wenn der Wert des Ergebnisregisters kleiner
 einer Konstante des Knotens ist, wird der linke Nachfolger gewählt,
 sonst der rechte.\\
\hline
 Ergebnisregister $ == $ Konstante&   Wenn der Wert des Ergebnisregisters gleich
 einer Konstante des Knotens ist, wird der linke Nachfolger gewählt,
 sonst der rechte.\\
\hline
  Ergebnisregister $ < $ Register$(i)$ & Wenn der Wert des Ergebnisregisters größer
 als der Wert des Registers $i$ ist, wird der linke Nachfolger gewählt, sonst der rechte. \\
\hline
 Ergebnisregister $ > $ Register$(i)$ & Wenn der Wert des Ergebnisregisters kleiner
 als der Wert des Registers $i$ ist, wird der linke Nachfolger gewählt, sonst der rechte.\\
\hline
 Ergebnisregister $ == $  Register$(i)$  &   Wenn der Wert des Ergebnisregisters gleich
 dem Wert des Registers $i$ ist, wird der linke Nachfolger gewählt, sonst der rechte.\\
\hline
\hline
\end{tabular}
\end{center}
\caption{Beispiele für binäre Branching Funktionen, wie sie auch in
 den Tests benutzt wurden. Das Ergebnisregister ist in den meisten
 Fällen das Register 0.}
\label{tab:BinaerBranchFunk}
\end{table}


Die Module oder auch Unterprogramme, die durch die Struktur gebildet
werden können, stellen somit in Kombination mit einer durch den
Programmfluss gesteuerten Aktivierung dieser Module einen großen
Vorteil gegenüber den Standard GP-Systemen dar. Dadurch, dass ein Knoten
im Baum einem Modul entspricht, werden die Module durch die Struktur
nicht nur gebildet, sondern auch, anders als bei Standard GP
Strukturen, während des Crossovers und der Mutation geschützt. Wie man im
folgenden durch das Vorgehen des Crossover Operators klar erkennen kann.



%----------------------------------------------------------------------
\subsection{Rekombination der Linear-Tree Struktur}
%----------------------------------------------------------------------
\label{subsec:Recom}

Die Crossover Operation ist eine der wichtigsten
Rekombinationsoperationen in der Genetischen Programmierung, sie ermöglicht
es, dass große Mengen genetischen Materials von einem
Rekombinationspartner zum nächsten gelangen. Dies ermöglicht es den
Individuen, während der Evolution sogenannte \emph{Building
Blocks}\index{Building Blocks} auszutauschen.

Der Crossover Operator für die Linear-Tree Struktur hat zwei
Möglichkeiten, genetisches Material zwischen Individuen zu
transportieren. Die eine Möglichkeit ist äquivalent der des Baum GP's,
in der Teilbäume zwischen den Individuen getauscht werden (siehe
\cite{Ang97}). Die Abbildung~\ref{fig:lintreeXoverTree} zeigt die Baum
basierte Crossovermethode für ein Linear-Tree Individuum. Aus jedem
Eltern-Individuum werden zufällig Teilbäume ausgewählt und zwischen den
Individuen ausgetauscht. Wichtig ist beim baumbasierten Crossover,
dass nicht zu oft Terminale als Knoten gewählt werden, da die Bäume
sonst sehr schnell degenerieren. Daher werden bei diesem Ansatz die
inneren Knoten eines Baumes immer mit einer höheren Wahrscheinlichkeit
ausgewählt als die Blätter des Baumes. Normalerweise werden innere
Knoten mit einer Wahrscheinlichkeit zwischen 70 und 90~\% gewählt.
Durch diese Wahl der Crossoverpunkte im Baum ergibt sich ein starkes
\emph{Bloat Problem}\index{Bloat Problem}. %Es gibt nun verschiedene
%Verfahren für das Baum GP um dies zu verhindern. Im Fall des
%Linear-Tree wird dann diese Crossovermethode abgebrochen und ein
%linearbasiertes Crossover durchgeführt.
%NEU ANFANG
Um dies zu verhindern wird diese Crossovermethode abgebrochen und ein
linearbasiertes Crossover durchgeführt.
%NEU ENDE
Weiteres zu den gewählten Verfahren und Parametern ist im
Abschnitt~\ref{TEST:linTreeXover} zu finden.

Die zweite Möglichkeit des Crossovers ist die des Crossovers zwischen
den linearen Sequenzen in den Knoten (siehe~\cite{banzhaf:1997:book}).
Wie die Abbildung~\ref{fig:lintreeXoverLin} zeigt, werden bei dieser
Rekombinationsmethode lineare Segmente zufälliger Länge zwischen den
beiden Knoten ausgetauscht. Da es auch bei diesem Verfahren sehr schnell
zum Wachstum der linearen Sequenz kommt, wird das Crossover beschränkt,
wenn es die Maximallänge der Sequenz erreicht. Falls dies passiert,
werden Segmente gleicher Länge zwischen den Sequenzen ausgetauscht.
Dieses Standardverfahren für lineare GP Individuen verhindert das
unkontrollierte Wachstum der Sequenzen.

Für ein Linear-Tree Individuum werden beide Möglichkeiten des
Austausches von genetischem Material benutzt. Es wird für jede
Crossoveroperation vorher mit einer festgelegten Wahrscheinlichkeit
bestimmt, welches der beiden Verfahren verwendet wird. Der
Rekombinationsoperator folgt dabei dem folgenden Algorithmus:

\begin{enumerate}
\item Wähle die Crossoverpunkte $p_1,p_2$ in beiden Individuen.

\item Wähle mit der Wahrscheinlichkeit $prob_{\textit{xover}}$ die
        baumbasierte Crossovermethode (gehe zu Schritt
         \ref{treeXover}).
        Wähle mit der Wahrscheinlichkeit $1-prob_{\textit{xover}}$ die
        linearbasierte Crossovermethode (gehe zu Schritt \ref{linXover}).

\item \label{treeXover} Wenn die Tiefe des neuen Baumes die maximale
         Tiefe nicht überschreitet, wird das baumbasierte Crossover
          ausgeführt, sonst wird mit Schritt \ref{linXover} weitergemacht.

\item \label{linXover} Führe ein linearbasiertes Crossover aus.

\end{enumerate}

Für den Parameter $prob_{\textit{xover}}$ wurde während der Tests ein
Wert von 20~\% gewählt. Dies kann dazu führen, dass das baumbasierte
Crossover nur bei maximal 20~\% der Crossoveroperationen durchgeführt
wird. Durch das Verfahren kommt es allerdings dazu, dass der Anteil
des baumbasierten Crossovers in Wirklichkeit noch geringer ist. Dies
geschieht dann, wenn die Bäume zu groß werden und die lineare
Crossovermethode aufgerufen wird. Die Grundidee hinter diesem Ansatz
ist, dass ein baumbasierter Crossoverschritt größere Auswirkungen
auf ein Individuum hat als ein linearbasierter Crossoverschritt. Die
baumbasierte Crossovermethode verändert die Struktur des Individuums
auf Baumebene und auf linearer Ebene. Damit verändert er sowohl die
Struktur des Programmflusses als auch den Datenfluss des Individuums,
ein Crossover auf linearer Ebene kann zwar auch den Programmfluss eines
Individuums verändern, dadurch dass es im Branching Knoten durch ein
verändertes Ergebnis zu einem anderen Ergebnis kommen kann. %Jedoch wird
%nicht die Struktur des Baumes verändert. 
Diese starken Veränderungen
sind aber besonders am Ende der Evolution mehr zerstörend als
aufbauend, daher sollen durch den kleineren Wert für das baumbasierte
Crossover die starken Veränderungen beschränkt werden. Die
Wahrscheinlichkeit, dass es zu einem baumbasierten Crossover in der
späteren Phase der Evolution kommt, wird durch den verwendeten
Algorithmus selbst noch verringert. Denn wenn ein Baum durch das
Crossover zu groß wird, wird das lineare Crossover durchgeführt. Dies
passiert am häufigsten am Ende der Evolution, wenn die Bäume schon
sehr tief geworden sind, dies ergibt eine automatische Anpassung des
Parameters durch die Evolution.


\begin{figure}
\begin{minipage}{7cm}
\centerline{\epsfig{figure=Pictures/Graphik/linTreeXoverTree.eps,width=7cm}}
\caption{Crossover Operation Linear-Tree von Individuen, die die
        baumbasierte Crossovermethode benutzen. Diese Methode tauscht,
        nachdem zwei Crossoverpunkte gewählt wurden, die Teilbäume aus.}
\label{fig:lintreeXoverTree}
%\end{figure}
\end{minipage}
\hfill
%\begin{wrapfigure}{r}{60mm}
%%\begin{figure}
\begin{minipage}{7cm}
\centerline{\epsfig{figure=Pictures/Graphik/linearTreeXoverLinear.eps,width=7cm}}
\caption{Crossover Operation Linear-Tree von Individuen, die die
        linear-basierte Crossovermethode benutzen. Diese Methode führt
        ein Zwei-Punkte-Crossover zwischen zwei linearen Sequenzen aus.}
\label{fig:lintreeXoverLin}
\end{minipage}
\end{figure}

%----------------------------------------------------------------------
\subsection{Mutation}
%----------------------------------------------------------------------
\label{sub:LinTreeMut}

Die Mutation ist die zweite Operation, die eine Veränderung des
genetischen Materials während der Evolution durchführt. Wie schon der
Crossoveroperator für ein Linear-Tree Individuum hat auch der
Mutationsoperator zwei Phasen. In der einen Phase wird eine Mutation der
linearen Sequenzen durchgeführt und in einer weiteren Phase wird eine
Mutation durchgeführt, die zu einer Veränderung des
Programmflusses führt.

Während der Mutation werden zufällig Knoten in der Baumstruktur des
Individuums ausgewählt. Die Anzahl der Knoten wird durch einen
Parameter festgelegt, der vor der Evolution festgelegt wird. Danach
durchläuft jeder Knoten die beiden Phasen der Mutation, dies
unterscheidet den Mutationsoperator vom Crossoveroperator, bei dem
immer nur eine der beiden Möglichkeiten benutzt wurde.
Die Mutation der linearen Sequenzen entspricht der Mutation von
linearen Individuen (siehe \cite{banzhaf:1997:book}), hierzu werden
zufällig Knoten des Individuums ausgewählt und die Funktionen, die
Terminale, die Register oder die Konstanten verändert. Anschließend
wird die zweite Phase der Mutation begonnen, wodurch der Programmfluss
des Individuums verändert wird. Hierzu wird nicht die
Baumstruktur verändert, indem Unterbäume vertauscht werden, sondern die
Branchingfunktion wird ersetzt oder verändert. Dies führt dazu, dass
nun bei einer Eingabe nicht der rechte, sondern der linke Sohn
ausgeführt wird.
Da dies eine starke Veränderung des Ein- Ausgabeverhaltens des
Individuums bewirkt, wird die zweite Phase der Mutation auch nicht
immer ausgeführt, sondern nur mit einer Wahrscheinlichkeit von
5~\%. Dadurch wird gewährleistet, dass der Programmfluss nicht zu stark
beeinflusst wird.





%----------------------------------------------------------------------
\section{Linear-Graph GP}
%----------------------------------------------------------------------
\label{sub:LinGraph}


Die \emph{Linear-Graph} Struktur\index{Linear-Graph} ist eine direkte
Weiterentwicklung der Linear-Tree Struktur aus Kapitel~\ref{sub:LinTree}.
Der Unterschied zur \emph{Linear-Tree} Repräsentation
eines GP-Programms, die erstmals eine Kombination von Daten- und
Programmfluss durch die Struktur der Individuenrepräsentation
vorgibt, ist, dass die Struktur, über die der Programmfluss
kontrolliert wird, ein Graph ist. Die lineare Struktur des Individuums
stellt den Datenfluss während
der Evaluation dar und die Graphstruktur den Programmfluss.
Die Grundstruktur ist ein Graph, in deren Knoten lineare Sequenzen von
Befehlen enthalten sind.
Weitere Ergebnisse zu dieser Struktur wurden auf der EuroGP Konferenz
2002 veröffentlicht~\cite{kantschik:2002:EuroGP}.





%----------------------------------------------------------------------
\subsection{Die Struktur}
%----------------------------------------------------------------------

\begin{wrapfigure}{r}{60mm}
%\begin{figure}
  \centerline{\epsfig{figure=Pictures/Graphik/linearGraph.eps,width=6cm}}
  \caption{Struktur eines Linear-Graph Individuums. Der Graph bildet den
 möglichen Programmfluss ab und die linearen Sequenzen den Datenfluss
in den einzelnen Knoten.% Die Knoten des Graphen bestehen aus einem
%linearen GP-Programm, hier blau dargestellt und dem Branching Knoten,
%als rote Pyramide dargestellt.
}
  \label{fig:linGraphProg}
\end{wrapfigure}%{figure}

In der \emph{Linear-Graph} Struktur wird der Programmfluss durch
einen  gerichteten azyklischen Graphen repräsentiert. %Dies
%ermöglicht den Individuen einfacher als bei der Linear-Tree Struktur
%bestimmte Programmflüsse zu erzeugen. 
Abbildung~\ref{fig:linGraphProg}
verdeutlicht den Aufbau der Linear-Graph Struktur, bestehend aus
einem azyklischen, gerichteten Graphen als Grundstruktur und dem Aufbau der
einzelnen Knoten. Es wurde ein azyklischer
gerichteter Graph gewählt, da sich hierdurch keine Zyklen in dem
Programmfluss ergeben können. Ein Zyklus im Graphen würde dazu führen,
dass die Evaluierung des Individuums nicht terminiert.



Als weitere Vereinfachung der Struktur und somit eine bessere
Möglichkeit, die Individuen bei der Rekombination zu kontrollieren,
wurde ein schichtweiser Aufbau gewählt. Der Startknoten des Graphen
liegt immer auf der Ebene 1 und seine Nachfolger auf der Ebene
2. Jeder Nachfolger eines Knotens befindet sich immer auf einer Ebene,
die mindestens um eins größer ist als die Ebene, auf der sich der
Elternknoten befindet. Es sind auch keine Kanten zwischen Knoten einer
Ebene oder eine Kante mit der Richtung von Ebene $i$ nach $i-1$
erlaubt. Dadurch erhält man sofort einen azyklischen Graphen.
Durch diese Definition der Graphstruktur des Individuums ermöglicht man
zwar nur eine Teilmenge aller möglichen azyklischen Graphen, jedoch
ist diese Beschränkung für die Entwicklung möglicher Programmflüsse zu
vernachlässigen.


Die Knoten, die keine Nachfolger
haben, werden auch als Terminale bezeichnet, dies wird im Abschnitt über
das Crossover der Linear-Graph Struktur~\ref{sub:LinGraphRecom} an
Bedeutung gewinnen. Die Terminalknoten des Graphen können auf jeder Ebene des
Graphen liegen, sie werden nur über ihr Nicht-Vorhandensein von
Nachfolgerknoten definiert. An den Terminalknoten wird die Evaluierung
eines Individuums beendet, da an ihnen immer ein Pfad durch den
Graphen endet (siehe Abschnitt~\ref{sub:evalLinGraph}).
Die Abbildung~\ref{fig:linGraphLevel} verdeutlicht
noch einmal den Aufbau der Graphstruktur  die möglichen
Verbindungen und die verbotenen Verbindungen zwischen zwei Knoten des
Graphen.




Durch die Veränderung der Grundstruktur der Linear-Graph Struktur
gegenüber der Linear-Tree Struktur ermöglicht man den Individuen,
gewisse Programmflüsse einfacher darzustellen. Ein Beispiel ist eine
Aufspaltung des Programmflusses und ein späterer Zusammenfluss.
Dies konnte in den Linear-Tree Individuen nur durch Kopien der
linearen Sequenzen geschehen, was auch oft bei Linear-Tree
Programmen geschehen ist (siehe hierzu Abschnitt~\ref{sub:linTreeAna}).
\begin{wrapfigure}{r}{70mm}
%\begin{figure}
  \centerline{\epsfig{figure=Pictures/Graphik/linearGraphLevel.eps,width=7cm}}
  \caption{%Der Graph ist hier exemplarisch in 5 Ebenen aufgeteilt. 
  Auf den Ebenen 3, 4
  und 5 findet man Terminalknoten. Die grünen Kanten zeigen 
  erlaubte Verbindungen im Graphen, die roten verbotene Verbindungen. }
  \label{fig:linGraphLevel}
\end{wrapfigure}%{figure}
Jedoch ist es in der Linear-Tree Struktur komplizierter, im
evolutionären Prozess durch Rekombination und Mutation zu solchen
Programmflüssen zu gelangen als in einer Linear-Graph
Struktur. Hierzu muss nur eine Kante durch eine Mutation verändert
werden, im anderen Fall kann dies erst durch die Rekombination zweier
Individuen geschehen, die gleiche lineare Sequenzen enthalten. Die
Komplexität des Aufbaus steigt für ein Linear-Tree Individuum mit der
Anzahl der Ebenen, die zwischen der Aufspaltung des Programmflusses und
der Zusammenführung liegen.
Dies zeigt auch, dass durch die Graphstruktur kompliziertere
Programmflüsse implementiert werden können als durch eine Baumstruktur.
%Somit ist diese Struktur wieder ein Schritt näher an
%Programme gerückt, die durch Menschen entwickelt werden.



Ein Knoten eines Linear-Graph Individuums
%NEU ANFANG
entspricht im Aufbau dem Knoten der Linear-Tree Struktur, siehe dazu
Abschnitt~\ref{sec:linTreeStrukt} und Abbildung~\ref{fig:lintreeNode}.
%NEU ENDE
% besteht aus zwei
%Komponenten, einer \emph{linearen Sequenz} von Registerbefehlen und
%einem \emph{Branching Knoten}. Die Abbildung~\ref{fig:lintreeNode} zeigt
%den Aufbau des Knotens mit den beiden Komponenten.

%Die \emph{lineare Sequenz}\index{lineare Sequenz} entspricht dem
%Aufbau eines linearen Individuums variabler Länge.
%Während der Interpretation eines Individuums wird über die Register
%der Datenfluss der linearen Sequenz etabliert. Innerhalb der linearen
%Sequenzen wird der Datenfluss des Individuums etabliert, wenn
%dieser durch den Programmfluss aktiviert wird. Ein Knoten wird
%aktiviert, wenn er durch den Vorgängerknoten aufgerufen wird.
%Das Gesamtergebnis eines Individuums setzt sich somit aus der
%Zusammenarbeit der Ergebnisse der einzelnen Knoten zusammen.


%\begin{figure}
%\centerline{\epsfig{figure=Pictures/Graphik/knoten.eps,width=11cm}}
%\caption{Der Aufbau eines Knotens im Linear-Graph Individuum. Die
%blauen Bereiche der Abbildung grenzen die lineare Sequenz von dem
%Branchingteil (rot) ab.}
%\label{fig:linGraphNode}
%\end{figure}


%Der \emph{Branching Knoten}\index{Branching Knoten} steuert durch
%entsprechende Funktionen den Programmfluss. Diese Funktionen sind
%immer Entscheidungsfunktionen, die auf der Grundlage der durch die
%lineare Sequenz berechneten Werte oder die der Eingabedaten einen der
%Nachfolgerknoten des Knotens bestimmt, der dann weiter ausgewertet
%wird.
%Dadurch bestimmt auch die \emph{Branching Funktion} den Ausgrad des
%Knotens im Graphen. Kann eine Funktion nur eine binäre Entscheidung
%treffen, hat der Knoten nur zwei ausgehende Kanten. Die Struktur des
%Graphen wird somit indirekt über die gewählten Branching Funktionen
%bestimmt. Wählt man Funktionen mit höherem Ausgrad, erhält man
%somit auch Graphen mit einem höheren Verzweigungsgrad.



%----------------------------------------------------------------------
\subsection{Evaluierung der Linear-Graph Struktur}
%----------------------------------------------------------------------
\label{sub:evalLinGraph}

Die Evaluierung der Linear-Graph Struktur
zeichnet sich dadurch aus, dass nicht
alle Knoten des Graphen für jeden Fitnesscase ausgewertet werden.

Da der Datenfluss in der linearen Sequenz und den Knoten des Graphen
untereinander geschieht, werden zu Beginn jeder Auswertung die
globalen Register mit eins initialisiert und die Datenregister mit den
entsprechenden Daten. Somit ergeben sich für jedes Individuum auf jeder
Eingabe immer die gleichen Voraussetzungen.

Es wird immer nur ein Pfad durch den Graphen, beginnend mit dem Startknoten,
ausgewertet. Durch den schichtweisen Aufbau des Graphen ergibt sich
eine natürliche Reihenfolge der Knoten des Graphen.
Der Startknoten, an dem jede Evaluierung des Individuum beginnt, ist
der einzige Knoten auf der ersten Ebene des Graphen (siehe
Abbildung~\ref{fig:linGraphLevel}). Nachdem die lineare Sequenz des
ersten Knotens ausgewertet ist und das Resultat dieser Berechnung in
den Registern gespeichert ist, wird der Branching Knoten ausgewertet.
Die Auswertung der linearen Sequenz ist analog zu der Auswertung von
linearem GP. Nach der Auswertung wird der Branchingteil jedes Knotens
ausgewertet.

Die Branchingfunktion\index{Branchingfunktion} unterliegt nur einer
Einschränkung durch die Individuenstruktur, die Funktion muss eine
Entscheidungsfunktion sein. Sie ist aber nicht auf binäre
Entscheidungen begrenzt, auch der Eingaberaum der Funktion wird nur
durch die dem GP System zur Verfügung stehenden Daten oder durch das
System erzeugte Daten beschränkt. In der
Tabelle~\ref{tab:BinaerBranchFunk} werden die Branchingfunktionen
beschrieben, die für die Tests benutzt wurden. Nachdem die Branchingfunktion
ausgewertet wurde, wird
der berechnetete Nachfolgerknoten als nächstes ausgewertet.

Vor der Interpretation des nächsten Knotens werden die Inhalte der
globalen Register oder der Datenregister nicht verändert, denn der
Datenfluss der Knoten untereinander funktioniert wie beim linearen GP
durch die Register. Durch diesen Aufbau ergeben sich keine Probleme
bei der Ausführung der verschiedenen Knoten beim Crossover und bei
der Mutation der Individuen.

Die Interpretation der Struktur wird dann beendet, wenn ein Knoten ohne
Nachfolger, also ein Terminal, gefunden wird. Da durch den Aufbau des
Individuums Terminale auf verschiedenen Ebenen liegen können, ist die
Länge des Pfades auch nicht bei jeder Eingabe gleich.

Die Abbildung~\ref{fig:lintreeProgFlow} %{fig:graphProgFlow} 
verdeutlicht, mit Hilfe der Linear-Tree Struktur, die verschiedenen
Pfade durch den Graphen für verschiedene Eingaben. Hier wird auch
deutlich, dass Bereiche des Graphen nicht evaluiert werden, sondern dass
immer nur ein Pfad durch den Graphen genutzt wird.



%\begin{figure}
%\centerline{\epsfig{figure=Pictures/Graphik/linearGraphFlow.eps,width=11cm}}
%\caption{Der Programmfluss durch ein Linear-Graph Individuum. Mit Rot
%sind die Kanten für den Programmfluss für eine Eingabe X
%gekennzeichnet und mit Blau die Kanten für den Programmfluss für eine
%Eingabe Y. Man sieht sofort, dass für verschiedenen Eingaben
%verschiedene Teile des Individuums interpretiert werden und somit
%verschiedene Unterprogramme zum Gesamtergebnis beitragen.}
%\label{fig:graphProgFlow}
%\end{figure}


%----------------------------------------------------------------------
\subsection{ Crossover der Linear-Graph Struktur }
%----------------------------------------------------------------------
\label{sub:LinGraphRecom}


Der Crossover Operator für die Linear-Graph Struktur hat wie der Crossover
Operator der Linear-Tree Struktur zwei
Möglichkeiten genetisches Material zwischen Individuen zu
transportieren. Die eine Möglichkeit ist die des Graph GP, in der
Teilgraphen zwischen den Individuen getauscht werden (siehe
\cite{teller1,Ang98,Pol97}). Die Abbildung~\ref{fig:lingraphXover}
zeigt die graphbasierte Crossovermethode für ein Linear-Graph Individuum. Aus jedem
Elternpaar werden zufällig Teilgraphen ausgewählt und zwischen den
Individuen ausgetauscht.
Ähnlich wie beim linearen und Baum GP gibt es auch in Linear-Graph
Strukturen ein \emph{ Bloat Problem}\index{ Bloat Problem}, diese Struktur
hat dieses Problem sogar auf zwei Ebenen. Eines liegt
auf der Ebene der Graphstruktur und das andere auf der Ebene der
linearen Sequenzen. Das Bloat Problem auf der Graphebene hat zur
Folge, dass die Graphen in ihrer Tiefe immer weiter wachsen. Dies
ergibt sich automatisch aus dem Schichtenaufbau des Graphen. Damit es
nicht zu einem zu starken Tiefenwachstum der Graphen kommt, wird durch
einen Parameter die maximale Anzahl von Ebenen der Individuen angegeben.
Falls der Graph die maximale Anzahl der Ebenen durch ein Crossover
überschreiten würde, wird diese Crossovermethode abgebrochen und ein
linearbasisertes Crossover durchgeführt.
Eine andere Variante wäre es, gleich tiefe Teilgraphen auszutauschen,
wie es auch im Falle der linearen Strukturen gemacht wird. Es hat sich
aber in Tests gezeigt, dass diese Crossovervariante für die Evolution
in späteren Generationen nicht mehr so wichtig ist. Da die Graphen
durch den Bloat Effekt bis an die gegebenen Grenzen wachsen, kommt es dann
hauptsächlich zu Crossover der linearen Sequenzen. Somit verändert
sich der Anteil des Graph Crossover automatisch durch den Algorithmus,
ohne einen weiteren Parameter einzuführen oder eine Selbstanpassung
durchzuführen.
Weiteres zu den gewählten Verfahren und Parametern ist im
Abschnitt~\ref{subsec:Recom} zu finden.

Die zweite Möglichkeit des Crossovers ist die des Crossovers zwischen
den linearen Sequenzen in den Knoten.
Wie auch die Abbildung~\ref{fig:lintreeXoverLin} zeigt, werden bei dieser
Rekombinationsmethode lineare Segmente zufälliger Länge zwischen den
beiden Knoten ausgetauscht. Da es bei diesem Verfahren sehr schnell
zum Wachstum der linearen Sequenz kommt, wird das Crossover beschränkt,
wenn es die Maximallänge der Sequenz erreicht. Falls dies passiert,
werden Segmente gleicher Länge zwischen den Sequenzen ausgetauscht.
Dieses Standardverfahren für lineare GP Individuen verhindert das
unkontrollierte Wachstum der Sequenzen.

Für ein Linear-Graph Individuum werden beide Möglichkeiten des
Austausches von genetischem Materials benutzt. Es wird für jede
Crossoveroperation vorher mit einer festgelegten Wahrscheinlichkeit
bestimmt, welches der beiden Verfahren verwendet wird. Der
Rekombinationsoperator folgt dabei dem folgenden Algorithmus:

\begin{enumerate}
\item Wähle die Crossoverpunkte $p_1,p_2$ in beiden Individuen.

\item Wähle mit der Wahrscheinlichkeit $prob_{\textit{xover}}$ die
        graphbasierte Crossovermethode (gehe zu Schritt
         \ref{graphXover}).
        Wähle mit der Wahrscheinlichkeit $1-prob_{\textit{xover}}$ die
        linearbasierte Crossovermethode (gehe zu Schritt \ref{linGraphXover}).

\item \label{graphXover} Wenn die Anzahl der Ebenen des neuen Graphen die maximale
         Anzahl nicht überschreitet, wird das graphbasierte Crossover
          ausgeführt, sonst wird mit Schritt \ref{linGraphXover} weitergemacht.

\item \label{linGraphXover} Führe ein linearbasiertes Crossover aus.

\end{enumerate}

Der Parameter $prob_{\textit{xover}}$ wurde während der Tests auf einen
Wert von 20~\% festgelegt. Dies führt dazu, dass das graphbasierte
Crossover nur bei maximal 20~\% der Crossoveroperationen durchgeführt
wird. Durch das Verfahren kommt es allerdings dazu, dass der Anteil
des graphbasierten Crossovers bei der gesamten Evolution geringer ist. Wie
oben erwähnt nutzt der Crossover Operator das linearbasierte Crossover, wenn
der Graph zu groß wird. Die Einschränkung des
Bloat Problems soll durch diesen Ansatz gefördert werden. Ein graphbasierter
Crossoverschritt hat  einen größeren Effekt auf ein
Individuum als ein linearbasierter Crossoverschritt, da es dann auch zu
Veränderungen im Programmfluss des Individuums kommt.
%(siehe~\ref{fig:lingraphXover}). 
Daher ist es sinnvoll, dass am Ende der
Evolution, wenn das System in einer Optimierungsphase ist, nur noch kleinere
Schritte gemacht werden.


\begin{figure}
%\begin{minipage}{6.3cm}
\centerline{\epsfig{figure=Pictures/Graphik/linGraphXover.eps,width=11cm}}
\caption{Crossoveroperation zweier Linear-Graph Programme. Hier wird das
  graphbasierte Crossover genutzt. Das Crossover tauscht zwei
  Teilgraphen der Individuen aus.}
\label{fig:lingraphXover}
\end{figure}

%%\end{minipage}
%%\hfill
%%\begin{minipage}{6.3cm}

%\begin{figure}
%\centerline{\epsfig{figure=Pictures/Graphik/linGraphXoverLinear.eps,width=11cm}}%width=10cm,
%\caption{Crossoveroperation zweier Linear-Graph Programme. Hier wird das
%  linear basierte Crossover genutzt. Der Operator führt ein zwei Punkt
%  Crossover bei zwei Knoten des Graphen aus.}
%\label{fig:lingraphXoverLin}
%%\end{minipage}
%\end{figure}





%----------------------------------------------------------------------
\subsection{Mutation}
%----------------------------------------------------------------------
\label{sub:LinGraphMut}

Die Mutation ist eine weitere wichtige Operation zur Variation des
genetischen Materials während der Evolution. Auch der
Mutationsoperator wird wie der Crossoveroperator für ein Linear-Graph
in zwei Phasen durchgeführt. In der ersten Phase wird eine Mutation der
linearen Sequenzen durchgeführt und in der zweiten Phase wird eine
Mutation durchgeführt, die an dem Individuum zu einer Veränderung des
Programmflusses führt.

Während der Mutation werden zufällig Knoten der Graphstruktur des
Individuums ausgewählt. Die Anzahl der Knoten wird durch einen
Parameter festgelegt, der vor der Evolution festgelegt wird. Danach
durchläuft jeder Knoten die beiden Phasen der Mutation, dies
unterscheidet den Mutationsoperator vom Crossoveroperator, bei dem
immer nur eine der beiden Möglichkeiten benutzt wurde.
Die Mutation der linearen Sequenzen entspricht der Mutation von
linearen Individuen (siehe \cite{banzhaf:1997:book}), hierzu werden
zufällig Knoten des Individuums ausgewählt und die Funktionen, die
Terminale, die Register oder die Konstanten verändert.

Die zweite Phase der Mutation, in der der Programmfluss variiert
wird, wird jedoch nur bei einem kleineren Teil aller Mutationen
durchgeführt. Die Wahrscheinlichkeit, dass die zweite Phase ausgeführt
wird, liegt bei dem System bei 5~\%. Dieser Wert ist experimentell
ermittelt, er ist nicht der optimale Wert für jedes Problem,
aber doch ein guter Mittelwert. An dieser Stelle scheint auch eine
automatische Adaptation möglich und nützlich. %Dass die Variation des
%Programmflusses nicht bei jeder Mutation durchgeführt wird, ist auch
%sinnvoll, da es sonst zu starken Veränderungen des Individuums kommt,
%die besonders dann nicht sinnvoll sind, wenn die Evolution nur noch
%kleine Verbesserungen durchführen muss.
Um eine Veränderung des Programmflusses durchzuführen hat der
Mutationsoperator zwei Möglichkeiten: einmal kann eine Kante zu einem
neuen Knoten gelegt werden oder die Branchingfunktion kann mutiert
werden. Beide Möglichkeiten werden vom Mutationsoperator genutzt,
wobei die Wahrscheinlichkeit für die Mutation der Branchingfunktion
bei 20~\% liegt, auch dieser Wert ist experimentell ermittelt worden.
Dabei hat sich zwar gezeigt, dass der Wert vom gestellten Problem abhängig
ist, aber auch, dass er sehr robust ist. Das heißt, der Wert liefert für ein
größeres Intervall gute Ergebnisse.




%----------------------------------------------------------------------
\section{State-Space GP}
%----------------------------------------------------------------------
\label{sec:stateSpaceGP}

Das \emph{State-Space GP}\index{State-Space GP} ist eine Struktur, die
speziell mit dem Ziel entwickelt wurde, im \emph{GeneticChess System}
verwendet zu werden. Der Fokus dieses Individuums sind allgemeine
Suchverfahren für Problemlösungsansätze, die als State-Space Ansatz
modelliert wurden. Mit dieser Struktur  wurden keine
Tests auf den Benchmarkproblemen durchgeführt, da dieser Lösungsansatz für
solche
Probleme nicht sinnvoll ist. Es wird jedoch
in diesem Kapitel vorgestellt, da diese Struktur nicht nur auf
Schachanwendungen beschränkt ist, sondern auf alle Probleme angewendet
werden kann, die eine \emph{State-Space Repräsentation}
verwenden~\cite{problem71}.
%\textbf{Kurze Definition der State-Space Verfahren!!}


Es stellt sich sofort die Frage, warum die Entwicklung einer speziellen
GP Struktur sinnvoll oder notwendig ist. Es hat sich in der
Vergangenheit gezeigt, dass gute Schachprogramme Suchverfahren sind.
Alle Schachprogramme, die muster-~, wissens- oder regelbasiert arbeiteten,
konnten bis jetzt nicht annähernd die Ergebnisse der Programme
erreichen, die mittels Suchverfahren arbeiten. Daher scheint es sinnvoll sich
auf Suchverfahren zu konzentrieren, wenn man das Schachproblem lösen will.  
%Eine rekursive Formulierung eines Suchverfahrens vereinfacht die
%Programmierung und Beschreibung des Algorithmus.
Viele der verwendeten Suchverfahren
beinhalten auch Heuristiken, welche die Rekursionsentscheidung
durchführen. Besonders bei der Lösung des Schachproblems kann man
erkennen, wieviel verschiedene Heuristiken für die
Rekursionsentscheidung entwickelt wurden (siehe
Kapitel~\ref{sub:SchachHeuristiken}).
Dies gilt nicht nur für die Problematik der Schachprogramme oder etwas
allgemeiner für verschiedene Strategiespiele, sondern für
verschiedene, schwere Suchprobleme, die nur durch Heuristiken berechnet
werden können.



%----------------------------------------------------------------------
\subsection{Die Struktur}
%----------------------------------------------------------------------
\label{sec:StateSpaceStrukt}

Die Struktur eines \emph{State-Space Individuums}\index{State-Space
Individuum} unterscheidet sich von den oben vorgestellten GP
Strukturen insoweit, dass das Individuum aus drei \emph{Substrukturen}
besteht, die jede eine eigenständige Bedeutung haben und nur durch 
Zusammenarbeit zu einer Lösung kommen können. Jede dieser
\emph{Substrukturen}\index{Substrukturen} ist selbst wieder ein GP
Individuum, welches durch seine Aufgabe, nicht aber durch seine Struktur
definiert ist.

Die Aufgaben der drei Substrukturen im Individuum sind:
\begin{enumerate}
\item das Modul der Tiefenentscheidung,
\item das Modul der Problembewertung und
\item das Modul der Blattbewertung.
\end{enumerate}

Neben diesen Substrukturen enthält das Individuum den Suchbaum
der aufgespannten Knoten (State). Dieser Suchbaum ist noch eine weitere
Möglichkeit für das Individuum, Daten zu extrahieren, da es auf die
Ergebnisse der aktuellen Berechnung und der Vergangheit zugreifen kann.
In der Abbildung~\ref{fig:stateSpaceProg} kann man die Kombination des
Individuums aus den drei Substrukturen erkennen.



\begin{figure}
  \centerline{\epsfig{figure=Pictures/Graphik/stateSpace.eps,width=11cm}}
  \caption{Struktur eines State-Space Individuums. Man kann die drei
  Substrukturen des Individuums erkennen und die Kombination dieser
  Substrukturen über den Programmflussabschnitt.}
  \label{fig:stateSpaceProg}
\end{figure}




Die \emph{Tiefenentscheidung}\index{Tiefenentscheidung} hat
die Aufgabe, für den aktuellen Aufruf des Programms zu bestimmen, ob
die Berechnung beendet wird, also die Blattbewertung aufgerufen wird,
oder ob es durch die Problembewertung zu einem weiteren Aufruf kommt.
Die Substruktur wird durch ein Linear-Graph Individuum realisiert.
%Für einfache Probleme ist
%die Rekursionsentscheidung oft, eine einfache Abfrage ob das
%Teilproblem direkt gelöst werden kann oder nicht. Aber für
%schwierigere Probleme, zum Beispiel
Im Bereich der Problemlösung oder
spezieller in der von Schach, ist die Entscheidung, ob man einen Knoten
im Suchbaum weiter expandiert, ein wichtiges Problem, welches die
Güte eines Programms sehr stark beeinflussen kann.
Daher werden auch für die Tiefenentscheidung verschiedenste
\emph{Heuristiken}\index{Heuristik} angewendet um eine \emph{gute
Entscheidung} zu treffen. Die Heuristik wird aus problem- und
domänenspezifischem Wissen erzeugt, wobei spezifisches Wissen oft
vorhanden ist, aber die Implementierung einer guten Heuristik durch die
\emph{richtige} Kombination dieses Wissens nur sehr schwer zu
erreichen ist. An dieser Stelle soll ein GP
Individuum, dessen Funktions- und Terminalmengen problemspezifisches
Wissen enthalten, die Aufgabe der Heuristikerstellung erhalten.
Die Aufgabe der Substruktur ist es dann, eine Klassifikation der
Eingabe unter Berücksichtigung der aktuellen Suchtiefe durchzuführen
und zu entscheiden, ob es zu einer weiteren Suche oder zum Abbruch kommen soll.
Dazu werden sowohl die Ergebnisse der Teile des Suchbaums genutzt, die schon
erreicht wurden, und durch das zweite Modul bewertet wurden. Das Ergebnis
der Substruktur wird %jedoch nicht sofort als Klassifikationsergebnis
%gewertet, sondern 
als Eingabe für den
\emph{Programmflussabschnitt}\index{Programmflussabschnitt}
genutzt. Der Programmflussabschnitt besteht aus zwei Funktionen, die
miteinander kombiniert werden. Einerseits hat man eine binäre
Entscheidungsfunktion, die Ergebnisse des Tiefenentscheidungsmoduls für die
Entscheidung nutzen, ob die Problembewertung oder die Blattbewertung
aufgerufen wird oder nicht. Durch diese Funktionen können verschiedenste Werte
betrachtet werden, die während der Evaluation berechnet werden. Die
Programmflussfunktionen erweitern jeden Terminalknoten der
Linear-Graph Struktur der Tiefenentscheidungsstruktur. Dadurch werden
verschiedene Programmflussabschnitte durch verschiedene Eingaben
aktiviert. 

Die zweite Funktion bestimmt, welche
möglichen Züge im Suchbaum im nächsten Schritt erzeugt werden. Bei der
Erzeugung der
möglichen Züge kann man verschiedene Kriterien benutzen, so kann man
alle möglichen Züge erzeugen oder für eine Schachstellung nur die
Schlagzüge, im allgemeineren Fall wäre dies eine Greedymethode, die
nur Verbesserungen der Situation zulässt. Weiterhin kann man auch nur
defensive Züge erzeugen. 
Tabelle~\ref{tab:flussfun} gibt die verschiedenen
Funktionen an, die im System implementiert sind, aus denen der
Programmflussabschnitt kombiniert werden
kann. Durch den Programmflussabschnitt
ermöglicht man den Individuen einen sehr variablen Aufbau
des Suchbaums und somit die Möglichkeit andere Wege im Suchraum zu finden.


\begin{table}
\begin{center}
\begin{tabular}{|l|p{9cm}|}
\hline
 Entscheidungsfunktion & Beschreibung der Funktion\\
\hline 
 Ergebnisregister $< 0$ & Wenn der Wert des Ergebnisregisters kleiner
 Null ist, wird der Knoten expandiert, sonst wird er bewertet. \\
\hline
 Ergebnisregister $<$ Konstante & Wenn der Wert des Ergebnisregisters kleiner
 einer Konstante ist, wird der Knoten expandiert, sonst wird er bewertet.\\
\hline
 Brettwert $<$ Alpha & Die Funktion identifiziert einen Alphaschnitt.\\
\hline
 Brettwert $>$ Beta & Die Funktion identifiziert einen Betaschnitt.\\
\hline
\hline
 Zugerzeugung & Beschreibung der Funktion\\
\hline 
 Alle Züge  &  Alle erlaubten Züge werden expandiert.\\
\hline
 aggressive Züge & Nur Schlagzüge werden expandiert. \\
\hline
 defensive Züge & Nur defensive Züge werden expandiert. \\
\hline
 Nullzug & Es wird ein Nullzug gemacht, also das Zugrecht an den Gegner
 abgegeben. \\
\hline
\end{tabular}
\end{center}
\caption{Die verschiedenen Funktionen die dem Individuum
 zur Verfügung stehen, um den Programmflussabschnitt zu implementieren.}
\label{tab:flussfun}
\end{table}



Die \emph{Problembewertung}\index{Problembewertung} ist der Teil des
Individuums, der alle Knoten des Suchbaums der nächsten Ebene bewertet
und so eine Reihenfolge vorgibt, in der die Teilprobleme abgearbeitet
werden. Dies ist ein wichtiger Schritt, da die Ergebnisse der Knoten
des Suchbaums, deren Suche schon beendet wurde, mit in die
Tiefenentscheidung eingehen. Wenn schon frühzeitig gute Lösungen
gefunden wurden, kann die Suche im Suchbaum eingeschränkt werden.
Könnte die Aufgabe der Problembewertung exakt durchgeführt werden,
würden schon diese Module ausreichen um das Problem mit einem Schritt
zu lösen (siehe Abschnitt~\ref{sec:alphaBeta}). Da dies jedoch für die
gestellten Probleme nicht exakt möglich
ist, muss auch hier eine Heuristik verwendet werden. Die Aufgabe der
Problembewertung wird daher darauf reduziert zu bestimmen, ob ein
möglicher Lösungsweg relativ besser ist als alle anderen Lösungswege
auf dieser Ebene des Suchbaums. Für einen Suchalgorithmus ist es
vorteilhaft, gute Lösungen früh während der Berechnung zu finden, da
dann später nicht so gute Lösungsansätze schnell verworfen werden
können. Das heißt, je besser die Heuristik an dieser Stelle ist, desto
kleiner wird der Suchbaum und desto schneller wird die Berechnung
abgeschlossen. %Dabei wird aber auch sofort klar, dass diese Heuristik
%Spezialwissen über das Problem benötigt um zu guten Ergebnissen zu
%kommen.

Das letzte Modul ist die \emph{Blattbewertung}\index{Blattbewertung},
es bewertet die Blätter des Suchbaums. Die Aufgabe des Moduls ist es,
für verschiedene Situationen eine relative Bewertung zu finden. Das
Problem für das Modul liegt darin, dass es die Bewertung aufgrund von
unvollständigen Informationen treffen muss. Denn Entscheidungen, die
während der Suche noch getroffen werden, haben entscheidenden Einfluss
auf die Bewertung in der aktuellen Situation. Dieses Modul versucht
nun die möglichen Entscheidungen in die Bewertung der aktuellen
Situation einzubeziehen. Dadurch wird sofort deutlich, dass es sich
an dieser Stelle des Individuums wieder um eine Heuristik handeln
muss. Für das Schachproblem wurden für diese Probleme die
verschiedensten Bewertungen
entwickelt~\cite{beal97,beal99e,birmingham77,birmingham80,buro99a}. Da
es sich um ein Problem handelt, welches großen Einfluss auf die
Güte des Algorithmus hat, wird auch hier problemspezifisches Wissen verwendet.


Die einzelnen Substrukturen werden nun durch die Zusammenarbeit während der
Ausführung zu einem Individuum, d.h. der Programmfluss vereinigt die
Elemente zu einem Individuum. Durch die Unabhängigkeit der Teilstrukturen
untereinander unterliegen sie keinem Zwang einer einheitlichen
Struktur, so kann jede Teilstruktur theoretisch eine andere GP
Struktur nutzen. Nur die Tiefenentscheidungstruktur unterliegt dem
Zwang, entweder aus einer Linear-Graph oder Linear-Tree Struktur zu
bestehen, da die Terminalknoten der Struktur durch die
Programmflussabschnitte erweitert werden müssen. Für alle anderen
Strukturen hätte diese Substruktur sonst nur einen möglichen
Programmflussabschnitt. 
In der aktuellen Version des Systems werden aber alle Substrukturen
durch Linear-Graph Strukturen implementiert.
Denn in den Tests der einzelnen Strukturen hat sich gezeigt, dass die
Linear-Graph Struktur die robusteste Struktur bezogen auf die Ergebnisse
ist. Sie erzielte immer gute bis sehr gute Ergebnisse und die Varianz
der Ergebnisse war sehr klein. Das ist für die gestellt Aufgabe sehr wichtig,
da die Rechenzeiten sehr groß sind und dadurch nicht sehr viele Läufe
durchgeführt werden können. Denn für das Schachproblem ist weniger das
Durchschnittsverhalten des Systems interessant als die besten Ergebnisse
aller Läufe.



%----------------------------------------------------------------------
\subsection{ Evaluierung der State-Space Struktur}
%----------------------------------------------------------------------

Die Evaluierung eines State-Space Individuums unterscheidet sich stark
von der anderer GP Individuen, denn diese Struktur ruft sich selbst
wieder auf. Das hat zur Folge, dass die Evaluation ein weiteres
Abbruchkriterium benötigt, da es sonst dazu kommen kann, dass das
Individuum nicht terminiert. Das Abbruchkriterium des Individuums
ergibt sich direkt aus der Aufgabe des Individuums und ist die maximale
Tiefe
und die Anzahl der Knoten im Suchbaum. Der Suchbaum wird von dem
Individuum während der Evaluation erzeugt und als zusätzliche
Eingabedimension verwendet.

Die Evaluation beginnt mit dem Tiefenentscheidungsmodul. Als Eingabe
erhält das Individuum den aktuellen Suchbaum, dieser besteht am Beginn
der Evaluation nur aus einem Knoten. Weiterhin erhält es als
Zusatzinformation die aktuelle Tiefe des Knotens im Suchbaum, die
maximale Tiefe des Suchbaums, die Anzahl der schon expandierten
Knoten im Suchbaum, die Blattwerte und die Werte der Problembewertung der bis
dahin expandierten Knoten.
Die Aufgabe der Substruktur ist es nun zu entscheiden, ob die aktuelle
Situation genauer untersucht werden soll oder ob sie nicht so
interessant ist und die Suche hier abgebrochen werden soll und die
aktuelle Stellung bewertet werden kann. Kommt das Modul zu der
Entscheidung, dass der Knoten weiter expandiert werden muss, wird die
entsprechende Funktion zur Erzeugung der möglichen nächsten Zustände im
Suchbaum aufgerufen, die durch den Programmflussabschnitt des
Terminalknotens gegeben wird.

\begin{figure}
\centerline{\epsfig{figure=Pictures/Graphik/stateSpaceInterpret.eps,width=11cm}}
\caption{Der Programmfluss eines State-Space Individuums. Die
Evaluation beginnt mit dem Entscheidungsmodul; wenn der Knoten
expandiert werden soll, werden entsprechend der Funktionen im
Programmflussabschnitt die möglichen Knoten im Suchbaum erzeugt. Dann
werden alle diese Knoten in der Sortierungsphase bewertet und relativ
zu diesen Werten sortiert. Danach wird für den besten Knoten wieder
das Entscheidungsmodul aufgerufen. Kommt dieses Modul zu der
Entscheidung, dass der Knoten nicht weiter untersucht werden muss, wird
das Blattbewertungsmodul aufgerufen. Der Knoten wird bewertet und das
Entscheidungsmodul wird dann für den nächsten Knoten auf dieser Ebene
aufgerufen. Sind alle Knoten auf einer Ebene abgearbeitet, wird der
nächste Knoten auf der höheren Ebene des Suchbaums behandelt.}
\label{fig:rekursivFlow}
\end{figure}

Alle diese Knoten im Suchbaum werden dann von der Substruktur für die
Problembewertung bewertet. Das Modul wird für jeden dieser Knoten
aufgerufen und berechnet für jeden Knoten einen Wert. Diese Werte
werden im weiteren als ein Gütemaß interpretiert und aufgrund
dieser Werte wird die Reihenfolge festgelegt, in der die Knoten im
weiteren Verlauf der Evaluation ausgewertet werden. Im System wird
ein hoher Wert als besser interpretiert als ein kleiner Wert,
d.h. der Knoten mit dem höchsten Wert wird im nächsten Schritt als
erstes weiter expandiert. Für diesen Knoten wird dann wieder die
Tiefenentscheidung aufgerufen. Kommt dieses Modul dann zum Ergebnis,
dass der Knoten nicht weiter expandiert werden muss, wird die Substruktur
für die Blattbewertung aufgerufen. Der resultierende Wert wird mit den
entsprechenden Alpha- und Betawerten verglichen und, wenn notwendig
ersetzt, falls Funktionen diese Werte benutzen. Anschließend wird das
Modul der Tiefenentscheidung am Knoten mit dem nächst kleineren
Wert auf der höheren Ebene des Suchbaums weitergeführt.
Die Abbildung~\ref{fig:rekursivFlow} zeigt die drei Phasen, die
jeder Knoten des Suchbaums während der Interpretation des Individuums
durchläuft.

Man kann leicht erkennen, dass dieses Individuum eine Rekursion bei der
Evaluation durchläuft, wobei die Tiefenentscheidung den
Rekursionsschritt durchführt und die Blattbewertung das Rekursionsende
markiert. %Bei Rekursionen kann es dazu kommen, dass der Algorithmus
%nicht terminiert und bei einem GP Lauf muss dies verhindert
%werden. Hierzu wird eine Obergrenze bei der Anzahl der expandierten
%Knoten und der Tiefe des Baumes angegeben. Die Tiefe des Baumes würde
%theoretisch ausreichen um die Terminierung des Individuums
%sicherzustellen, die Anzahl der expandierten Knoten wurde nur für die
%Schachevolution
%eingeführt,
%um eine bessere Kontrolle über die verbrauchten Ressourcen des
%Individuums zu haben.
Im Bereich der Genetischen Programmierung gibt es nicht viele Beispiele,
die Rekursionen in die Individuen einbauen, ein Beispiel ist das 
Generic Genetic Programming System (GGP) von Man Leung Wong~\cite{wong:1996:aigp2}.



%----------------------------------------------------------------------
\subsection{Die Evolution eines State-Space Individuums}
%----------------------------------------------------------------------
\label{sec:evoState-Space}

Für die Evolution eines State-Space Individuums ergeben sich durch den
modularen Aufbau des Individuums mehrere Möglichkeiten. Die einfachste
Möglichkeit ist die direkte Evolution aller Substrukturen.% in einem Schritt. 
Die zweite Möglichkeit besteht in einer mehrstufigen
Evolution, in der jede Substruktur nacheinander evolviert  und
anschließend zu einem Individuum zusammengesetzt wird. Die
letzte Möglichkeit ist eine stufenweise Evolution. %, dabei wird erst die
%Blattbewertung alleine evolviert. Anschließend wird die
%Problembewertung evolviert, wobei jedoch ein vorher evolviertes
%Blattbewertungsmodul genutzt wird, und in einem dritten Schritt wird
%das Tiefenentscheidungsmodul evolviert, wobei die beiden anderen
%Module aus der vorhergehenden Evolution genutzt werden.

Das Verfahren, in dem das komplette Individuum evolviert wird, hat den
Vorteil, dass sich so die einzelnen Substrukturen aufeinander
einstellen können und zu einer Aufgabenteilung 
kommen.


Das zweite Verfahren, jedes Modul unabhängig zu evolvieren und
anschließend zu einem Individuum zusammenzusetzen, hat zwar den
Vorteil, dass man unabhängige Evolutionen parallel auf mehreren
Rechnern durchführen kann. Jedoch hat sich gezeigt, dass die Module
nicht sehr gut zusammenarbeiten. Da die Umgebung, also das
Ausgabeverhalten der anderen Module während der Evolution simuliert
werden muss, kann sich so nicht etwas wirklich Neues entwickeln. Denn
die Vorgaben für die Substrukturen bestimmen das Gesamtergebnis zu
stark. Da diese Art der Evolution schon in den ersten Untersuchungen nur
schlechte Ergebnisse erzeugte, wurde diese Variante nicht weiter untersucht.

Das letzte Verfahren ist eine Kombination aus den beiden Verfahren,
wobei es für dieses Verfahren auch zwei Varianten gibt. Die eine
Möglichkeit ist es, die vorevolvierten Module während der Evolution des
nächsten Moduls nicht mehr zu verändern, die andere Variante ist es, auch
diese Module, jedoch mit einer kleinen Wahrscheinlichkeit, während der
Evolution zu verändern. Das Ziel dieser Variante ist es, die Zeit zur
Evolution eines vollständigen Individuums zu verkürzen, da die
Substrukturen durch die vorhergegangenen Evolutionen schon die Aufgabe
sinnvoll lösen können. Da die Evolutionen nicht ganz unabhängig
voneinander durchgeführt wurden, sondern zuerst die Evolution für die
Blattbewertung, dann die Evolution für die Problembewertung mit einem
evolvierten Modul für die Blattbewertung und zuletzt die Bewertung
für die Tiefenentscheidung, haben sich die später evolvierten Module
auch auf die Ergebnisse der anderen Module einstellen können. Der
Nachteil dieses Verfahrens ergibt sich daraus, dass die zuletzt
evolvierten Module immer simuliert werden müssen und so das
Gesamtindividuum durch das simulierte Verhalten der später evolvierten Module
beschränkt wird. Die Möglichkeit diese Module in die weitere Evolution mit
einzubeziehen sollte diesem Problem entgegenwirken.

Die vorbereitenden Experimente haben jedoch gezeigt, dass auch diese Variante
zu keinem guten Ergebnissen führte, so dass sie nicht weiter verfolgt
wurde. So konnten in beiden Fällen die Blattbewertungen keine signifikante
Verbesserung der Fitness erreichen. 
Bei der dritten
Variante ergab sich das gleiche Problem auch für die anderen beiden Module und
die Fitness des gesamten Individuums war anschließend sehr viel schlechter als
bei den Individuen, die mit der ersten Variante entwickelt wurden. Die
Ergebnisse der zweiten Variante waren etwas besser als die der dritten
Variante, jedoch erreichten auch sie nie die Ergebnisse der ersten
Variante. Da die erste Variante gleichzeitig noch Rechenzeit einspart, wurden
alle Haupttests mit dieser Variante durchgeführt.



%----------------------------------------------------------------------
\subsection{ Crossover der State-Space GP Struktur}
%----------------------------------------------------------------------

Der Crossover-Operator für die State-Space Struktur hat maximal drei
Möglichkeiten genetisches Material zwischen Individuen zu
transportieren. Dabei ist jedoch zu beachten, mit welchen Verfahren das
Individuum evolviert wird. Die drei Möglichkeiten sind nur dann
sinnvoll, wenn das gesamte Individuum in einem Schritt evolviert
wird.


\begin{figure}
\begin{minipage}{7cm}

%\begin{figure}
\centerline{\epsfig{figure=Pictures/Graphik/stateSpaceXover.eps,width=7cm}}
\caption{Die Crossoveroperation auf der Ebene des State-Space
Individuums. Da das Individuum aus drei Substrukturen besteht, kann auf
dieser Ebene des Crossovers nur die gesamte Substruktur getauscht
werden. %Dabei ist zu beachten, dass immer die gleichen Substrukturen
%miteinander getauscht werden, da sie verschiedene Funktionen im
%Individuum haben und somit nicht untereinander ersetzt werden können.
}
\label{fig:xover1}
%\end{figure}
\end{minipage}
\hfill
\begin{minipage}{7cm}

%\begin{figure}
\centerline{\epsfig{figure=Pictures/Graphik/stateSpaceXoverIntern.eps,width=7cm}}
\caption{Die Crossoveroperation auf der Ebene einer Substruktur. Dabei
wird nach der Auswahl einer Substruktur zwischen den Substrukturen der
Individuen ein Crossover auf der Graphebene der Substruktur durchgeführt.}
\label{fig:xover2}
\end{minipage}
\end{figure}



Eine Variante des Crossoveroperators für eine State-Space Struktur ist
der Austausch ganzer Substrukturen. Dabei wird eine Substruktur
zufällig ausgewählt, dann zwischen den Individuen ausgetauscht (die
Abbildung~\ref{fig:xover1} zeigt dieses Vorgehen), diese
Crossovervariante wird im folgenden
\emph{Strukturcrossover}\index{Strukturcrossover} genannt. Beim
Strukturcrossover werden ganze Substrukturen ausgetaucht, dabei muss darauf
geachtet werden, dass immer Module der gleichen Art ausgetauscht werden. Denn
es macht für ein Individuum keinen Sinn ein Tiefenmodul als
Blattbewertungsmodul aufzurufen. Da diese Variante des Crossovers
nur Substrukturen austauscht, die möglicherweise mit anderen Modulen
besser zusammenarbeiten, wird diese Variante mit einer sehr kleinen
Wahrscheinlichkeit gewählt, da die Gefahr eines zu schnellen Verlustes
der Diversität in der Population besteht. 

Die Abbildung~\ref{fig:xover2} zeigt die zweite Möglichkeit eines
Crossovers. Sie entspricht der Graph-basierten Crossovermethode für ein
Linear-Graph Individuum. %Aus jedem
%Elternpaar werden zufällig Teilgraphen ausgewählt und zwischen den
%Individuen ausgetauscht. 
Hierbei ist wieder zu beachten, dass gleiche
Substrukturen gewählt werden, da jede Substruktur andere Funktions-
und Terminalmengen hat und es somit zu nicht ausführbaren Individuen
kommen könnte. Dabei handelt es sich um die graphbasierte
Crossovervariante der Linear-Graph Struktur (siehe
Abschnitt~\ref{sub:LinGraphRecom}). Falls diese Variante des
Crossovers nicht möglich ist, da die Graphen die maximale Tiefe
erreicht haben, wird die Crossovervariante auf den linearen Sequenzen
der Graphknoten durchgeführt. %Die Abbildung~\ref{fig:xover3}
%zeigt diese Variante. Bei dieser Variante wird je ein Knoten in jedem
%Graphen gewählt und anschließend wird ein Zweipunkt-Crossover mit den
%linearen Sequenzen durchgeführt. Da es bei diesem Verfahren sehr schnell
%zum Wachstum der linearen Sequenz kommt, wird das Crossover beschränkt,
%wenn es die Maximallänge der Sequenz erreicht. Falls dies passiert,
%werden Segmente gleicher Länge zwischen den Sequenzen ausgetauscht.
%Dieses Standardverfahren für lineare GP Individuen verhindert das
%unkontrollierte Wachstum der Sequenzen.



Für ein State-Space Individuum werden alle drei Möglichkeiten des
Austausches von genetischem Materials benutzt. Es wird für jede
Crossovervariante vorher eine festgelegte Wahrscheinlichkeit
bestimmt, mit welcher die Verfahren verwendet werden. Der
Rekombinationsoperator folgt dabei dem folgenden Algorithmus.

\begin{enumerate}
\item Wähle gleichwahrscheinlich eine Substruktur aus.
\item Wähle mit der Wahrscheinlichkeit $prob_{\textit{sXover}}$ die
        Strukturcrossover Methode, sonst gehe zu \ref{StXover}.

\item \label{StXover}Wähle die Crossoverpunkte $p_1,p_2$ in beiden Substrukturen.

\item Wähle mit der Wahrscheinlichkeit $prob_{\textit{xover}}$ die
        graphbasierte Crossovermethode, gehe zu Schritt
         \ref{StgraphXover}. \\
        Wähle mit der Wahrscheinlichkeit $1-prob_{\textit{xover}}$ die
        linearbasierte Crossovermethode, gehe zu Schritt \ref{StlinGraphXover}.

\item \label{StgraphXover} Wenn die Anzahl der Ebenen des neuen Graphen die maximale
         Anzahl nicht überschreitet, wird das graphbasierte Crossover
          ausgeführt, sonst wird mit Schritt \ref{StlinGraphXover} weitergemacht.

\item \label{StlinGraphXover} Führe ein linearbasiertes Crossover aus.

\end{enumerate}



Für den Parameter $prob_{\textit{sXover}}$ wurde während der Evolution ein
Wert von 2~\% gewählt, für den Wert $prob_{\textit{xover}}$ wurde ein
Wert von 20~\% festgelegt. Der Wert von 2~\% für
$prob_{\textit{sXover}}$ führt dazu, dass ein Strukturcrossover nur
sehr selten durchgeführt wird. Dadurch wird verhindert, dass der
Diversitätsverlust während der Evolution zu schnell passiert und man
gibt gleichzeitig den Individuen die Möglichkeiten gute Substrukturen
auszutauschen. Man könnte auch noch Wahrscheinlichkeiten für die Wahl
der einzelnen Substrukturen einführen, so könnte es sinnvoll sein, zu
Beginn der Evolution verstärkt die Blattbewertung zu tauschen, später
die Problembewertung und erst sehr spät in der Evolution die
Tiefenbewertung in das Crossover einzubeziehen. Damit könnten sich die
Substrukturen, welche die Ergebnisse der anderen Substrukturen nutzen,
besser auf die neuen Bewertungen einstellen. Jedoch führt dies zu
mindestens drei neuen Parametern und im Fall der
Gleichwahrscheinlichkeit werden sich während der Evolution natürlich
gewisse Substrukturen durchsetzen, da sie zu guten Ergebnissen
gelangen. Die  Substrukturen passen sich durch den
normalen Diversitätsverlust in der Population an und man erhält dadurch
automatisch eine Anpassung des Wertes ohne ihn direkt
vorzugeben~\cite{niehaus:2001:EuroGP}.

%\begin{wrapfigure}{r}{60mm}
%%\begin{figure}
%\centerline{\epsfig{figure=Pictures/Graphik/stateSpaceXoverInterLin.eps,width=6cm}}
%\caption{Die Crossoveroperation auf der Ebene einer Substruktur.% Dabei
%%wird nach der Auswahl einer Substruktur zwischen den Substrukturen der
%%Individuen ein Crossover auf der Knotenebene des Graphen der Substruktur durchgeführt.
%}
%\label{fig:xover3}
%\end{wrapfigure}%{figure}

Der Wert von 20~\% für das graphbasierte Crossover hat sich aus den Versuchen
mit dem Linear-Graph Crossoveroperator entwickelt (siehe
Abschnitt~\ref{sub:LinGraphRecom}).




%----------------------------------------------------------------------
\subsection{ Mutation der State-Space GP Struktur}
%----------------------------------------------------------------------

Der Mutationsoperator für ein State-Space Individuum wird immer nur in einer
Substruktur des Individuums durchgeführt, dadurch soll erreicht werden, dass
sich die Substrukturen einander anpassen können. Die Wahrscheinlichkeit für
die einzelnen Substrukturen ist gleich verteilt, da man hier nicht sagen kann,
dass eine Substruktur stärker verändert werden muss als eine andere.

Die Mutation innerhalb der Substrukturen entspricht der Mutation eines
Linear-Graph Individuums, wie es in Abschnitt~\ref{sub:LinGraphMut}
beschrieben wurde. Die einzige Besonderheit ist die Substruktur für die
Tiefenentscheidung, da es hier noch die zusätzlichen Knoten an den Terminalen
der Linear-Graph Struktur gibt.
Der Mutationsoperator achtet darauf, ob er einen Terminalknoten
mutiert hat. Wenn das der Fall ist, wird der Programmflussabschnitt des
Knotens mit einer
Wahrscheinlichkeit von 5~\% mutiert.
Dies wird gemacht, damit die Variation der Rekursionsaufrufe  seltener
durchgeführt wird, da es sonst zu starken Veränderungen des Individuums kommt,
die besonders dann nicht sinnvoll sind, wenn die Evolution nur noch
kleine Verbesserungen durchführen muss.
Um eine Veränderung der Rekursionsaufrufe durchzuführen hat der
Mutationsoperator zwei Möglichkeiten, einmal kann er die
Entscheidungsfunktion variieren und zum zweiten kann er die
Zugerzeugungsfunktion verändern. Während der Mutation darf immer nur
eine der beiden Funktionen variiert werden, die Auswahl, welche variiert
wird, ist jedoch gleich wahrscheinlich.

%\newpage


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