%----------------------------------------------------------------------
%\section{Einführung in die Genetischen Programmierung}
%----------------------------------------------------------------------
\label{sec:gpEinfuehrung}

Die \emph{Genetische Programmierung}\index{GP,Genetische
Programmierung} ist eine Suchheuristik, die den Raum der 
\emph{Programme} nach Lösungen durchsucht. Dabei macht sie sich das Prinzip der
 Evolution zunutze, um ein definiertes Ziel zu erreichen.

Das Prinzip Darwins\index{Darwin}, die natürliche Selektion, wird als
Motor der Evolution
aller Lebensformen auf der Erde betrachtet. Das Prinzip der Evolution  wird
schon über 30 Jahre in verschiedenen Bereichen der Informatik eingesetzt,
wodurch sich verschiedene Forschungszweige wie die
Evolutionsstrategien~\cite{schwefel1} \index{Evolutionsstrategien} ,
die Genetischen
Algorithmen~\cite{holland} und die Evolutionäre Programmierung~\cite{fogel:66}
entwickelt haben. Diese Methoden wurden in den letzten Jahren erfolgreich auf
zahlreiche theoretische und praktische Probleme angewendet.

\begin{wrapfigure}{r}{70mm}
%\begin{figure} [ht]
  \begin{center}
    \epsfig{file=Pictures/Graphik/evoSchleife.eps,height=7cm}
    \caption{Evolutionsschleife}
    \label{abb:evocycle}
  \end{center}
%\end{figure}
\end{wrapfigure}

Die Genetische Programmierung ist das neueste Forschungsgebiet, das
die Evolution zur Erzeugung von Programmen nutzt. Im Unterschied zu
anderen evolutionären Methoden ist der Suchraum der \GP\ \emph{nicht} wie oft
ein Vektor von reellen, natürlichen oder binären Werten, sondern der Raum der
Programme. GP-Systeme optimieren während eines evolutionären Prozesses eine
Population von \emph{symbolisch} repräsentierten Programmen mittels
\emph{Genetischer Operatoren}.
Der Ablauf eines GP-Systems zur Optimierung der Individuen innerhalb der
Population folgt dabei in einer
Evolutionsschleife\index{Evolutionsschleife}, wie sie in der
Abbildung~\ref{abb:evocycle} dargestellt ist. Die Evolutionsschleife wird
dabei solange ausgeführt, bis ein Abbruchkriterium erfüllt ist.



Die Methode der Genetischen Programmierung geht auf Forschungen Ende der
50ziger Jahre zurück~\cite{friedberg}, die jedoch keinen großen Erfolg
hatten. Selbst als die ersten positiven Ergebnisse erzielt wurden, konnte sich
die Methode der GP nicht etablieren~\cite{cramer}.
Erst durch Koza~\cite{koza1}, der die Individuen  als Baumstrukturen
repräsentierte, konnte sich die Methode der Genetischen Programmierung in der
Forschung behaupten.
Seitdem haben sich im Bereich der GP weitere Repräsentationsformen der
Individuen mit ihren eigenen Besonderheiten gebildet, wie lineare Individuen
im CGPS~\cite{nordin:linGP, nordin2, nordin3} und graphbasierte Individuen im
PADO-System~\cite{teller96pado}.

%
% GP = Komplexitaet von Peter zurueckgewiesen
%
%

Der Grundgedanke der Genetischen Programmierung ist es, den Individuenpool von
einem zufälligen Initialzustand durch einen Selektionsprozess, der die
\emph{guten} Individuen bevorzugt, zu einem Zustand höherer Ordnung zu führen.
Während dieses Prozesses steigt im System die Komplexität an, solange kein
Gleichgewichtszustand erreicht wird.\\
Der Anstieg der Komplexität bezieht sich sowohl auf die Struktur der
Individuen im Pool als auch auf das Ein- und Ausgabeverhalten der
Individuen. Die Selektion und Rekombination ändert das Ein- und
Ausgabeverhalten von einer zufälligen Abbildungsvorschrift zu einer Abbildung,
die das gestellte Problem löst oder annähert. \\
Hier wird der Begriff der \emph{Komplexität}\index{Komplexität} in
einem mehr intuitiven Sinne
benutzt, als ein Zustand zwischen Ordnung und Chaos, periodisch und zufällig,
und nicht im Sinne der \emph{algorithmischen Komplexität}. Das Verhältnis
zwischen Komplexität und Ordnung kann man sich vereinfacht, wie in der
Abbildung~\ref{abb:komplex} dargestellt, vorstellen. Damit liegt der Punkt der
höchsten Komplexität zwischen Ordnung und Unordnung.
\begin{wrapfigure}{r}{60mm}
%\begin{figure} [ht]
  \begin{center}
    \epsfig{file=Pictures/Graphik/komplexitaet.eps,,width=6cm}
    \caption{Komplexität liegt zwischen Ordnung und Unordnung.}
    \label{abb:komplex}
  \end{center}
\end{wrapfigure}%{figure}

Somit hat ein Individuum, welches zu jeder Eingabe die gleiche oder eine
zufällige Ausgabe liefert, eine kleinere Komplexität als ein Individuum, das
zu einer Eingabe eine dem Problem entsprechende Ausgabe liefert.\\
Der Initalpool, der durch einen zufälligen Prozess entsteht, hat somit
eine geringere Komplexität als der Pool einer späteren Generation, denn
durch
den Rekombinationsprozess haben sich Individuen gebildet, die einander ähnlich,
jedoch nicht identisch sind.

Betrachtet man Komplexität als den durch Charles
Bennet~\cite{bennet1} definierten Prozess der \emph{logischen
  Tiefe}\index{logische Tiefe}, wonach
Komplexität nicht von der nominalen Information, sondern von dem
zugrundeliegenden Prozess der Beseitigung von (überflüssiger) Information ist,
so ist sie ein Ausdruck für den Prozess, der zu einer bestimmten Menge von
Information führt, die sich auf das gestellte Problem bezieht. Diese
Information
erhält man durch einen Prozess, der aus der Menge aller Informationen des
Problems die Informationen löscht, die für die Lösung überflüssig sind.

Man kann zum Beispiel die Abbildung $f(x)= x^{2}$ durch eine unendliche Menge
von Zahlenpaaren $ \ldots,(-2,4), (-1,1), (0,0), (1,1), (2,4) ,\ldots $ und
die Abbildungsvorschrift selbst beschreiben, jedoch ist die Menge der
Zahlenpaare für eine vollständige Beschreibung der Abbildung überflüssig. So
hat nach Bennet die Abbildungsvorschrift eine höhere logische Tiefe als die
Menge der Zahlenpaare.

Im Falle der Genetischen Programmierung geschieht dies auf zwei Ebenen,
auf der Ebene der Individuen in der Population und auf der Ebene des
Abbildungsverhaltens.

Auf der ersten Ebene werden, ausgehend von einer endlichen (aber großen) Menge
aller Individuenkonfigurationen, die Konfigurationen durch den Evolutionsprozess
erzeugt, die das Problem lösen können. Von der großen Informationsmenge wird
eine große Anzahl von Individuen (Informationen) ausgesondert, also wird nach
der Definition von Bennet in der Population \emph{logische Tiefe} erzeugt.

Das Gleiche geschieht auf der Ebene der Abbildungsvorschriften, aus allen
Abbildungsvorschriften, die die Individuen erzeugen könnten, werden durch den
evolutionären Prozess die ausgewählt, die das Problem lösen.

Die Individuen der Genetischen Programmierung sind das Resultat der Simulation
einer evolutionären Berechnung, vergleichbar mit biologischen Wesen, die
ebenfalls das Resultat einer sehr langen evolutionären Berechnung sind.

Da aus dem Suchraum aller Individuen die Individuen ausgesondert wurden, die
die Aufgabe nicht lösen, erhält man einen informationslöschenden
Prozess. \GP\ erfüllt damit, ebenso wie die natürliche Evolution, die
Definition
der logischen Tiefe.

Genetisches Programmieren ist folglich ein Prozess, der Ordnung, Komplexität und
somit logische Tiefe schafft.


%----------------------------------------------------------------------
%\section{Grundlegende Begriffe und Konzepte der \GP}
%----------------------------------------------------------------------
%\label{sec:gpBegriffe}

Viele Begriffe der \GP, die eine
zentrale Bedeutung haben, sind  nicht allgemein bekannt und
überschneiden sich teilweise mit Begriffen aus anderen Forschungsbereichen, wie
denen der Evolutionsstrategien (\textbf{ES})
\index{ES,Evolutionsstrategien} \cite{schwefel1}. Um
Fehlinterpretationen zu vermeiden, werden die Begriffe \emph{Genetische
  Operatoren, Fitnessfunktionen, Fitnesscases und Selektion} im folgenden für
diese Arbeit kurz genauer beschrieben.


%----------------------------------------------------------------------
\section{Strukturen von GP Individuen}
%----------------------------------------------------------------------
\label{sub:genStrukt}

Die Genetischen Programme bestehen aus Operationen, die selber
Funktionen, Prozeduren, Konstanten oder Terminale sein können, die in
einer vorgegebenen Struktur
zusammengefasst werden. Diese \emph{Struktur} bestimmt den Aufbau,
die Programmausführung und die Genetischen Operatoren.
Die Standardvarianten in GP-Systemen sind
\begin{itemize}
\item (1) Baum GP \cite{koza1,koza2},
\item (2) Lineare GP \cite{nordin:linGP,banzhaf:1997:book} und
\item (3) Graph GP \cite{Ang98,Pol97,teller1}.
\end{itemize}


%----------------------------------------------------------------------
\subsection{Baum GP}
%----------------------------------------------------------------------


\begin{wrapfigure}{r}{75mm}
%\begin{figure} [ht]
  \begin{center}
    \epsfig{file=Pictures/Graphik/tree.eps,width=7.5cm}
    \caption{Aufbau eines baumbasierten Individuums. Die inneren
    Knoten des Individuums enthalten die Operationen und die Blätter
    die Terminale und Konstanten.}
    \label{fig:Tree}
  \end{center}
\end{wrapfigure} %{figure}

Das \emph{Baum GP}\index{Baum GP} zeichnet sich dadurch aus, dass die
Operationen in einer Baumstruktur eingebettet sind, wobei die Kinder
eines Knotens immer die Operanden einer Operation enthalten. Die
Blätter des Baumes enthalten dann die Terminale oder Konstanten des
Individuums. Neben der Form ist aber auch die Auswertungsreihenfolge
des Baumes wichtig. Die Konvention zur Auswertung von Bäumen ist, dass
sie von den Blättern zur Wurzel hin ausgewertet werden. Hierzu wird
oft ein Tiefendurchlauf durch den Baum gewählt um die Reihenfolge der
Auswertungen zu bestimmen.

Die Abbildung~\ref{fig:Tree} zeigt den Aufbau eines Baum Individuums
graphisch, wichtige Knoten sind farblich markiert. Die inneren Knoten
des Individuums enthalten die Operationen
und die Blätter die Terminale und Konstanten.


Die Kanten des Baumes stellen den Datenfluss zwischen den
Operationen dar. Somit brauchen Baumstrukturen keinen externen
Speicher, damit die einzelnen Operationen miteinander kommunizieren
können. Dies ist ein Unterschied zu den meisten anderen Strukturen,
die immer einen externen Speicher zur Kommunikation benutzen.

%----------------------------------------------------------------------
\subsection{Lineares GP}
%----------------------------------------------------------------------

Das \emph{lineare GP} \index{lineare GP} ordnet die Operationen in einer
linearen
Sequenz an. Die Operationen werden der Reihe nach von vorne
nach hinten ausgewertet. Die Anordnung der Operationen stellt hier
den Programmfluss dar, der Datenfluss zwischen den Operationen wird
über externe Speicher durchgeführt. Daher sind lineare GP Individuen
im allgemeinen Zwei- oder Dreiadress Registermaschinen
\cite{nordin:linGP,huelsbergen96}.
Der externe Speicher linearer Individuen wird deshalb auch als Register
bezeichnet. Ein Instruktion eines linearen Individuums hat die Form:
\[
        Reg(1)= op(Reg(2),x) , \text{mit } x \in \Rc, \Kc, \Tc.
\]

Wobei \Rc\ die Menge der Register, \Kc\ die Menge der Konstanten und
\Tc\ die Menge der Terminale ist.  
Durch diesen Aufbau einer Instruktion wird sichergestellt, dass
Ergebnisse aus früheren Instruktionen weiter verarbeitet und
somit der Datenfluss zwischen den Instruktionen erzwungen wird. %Die
%Abblidung~\ref{fig:Linear} zeigt den Aufbau eines linearen Individuums
%mit den Registern.

%\begin{figure} [ht]
%  \begin{center}
%    \epsfig{file=Pictures/Graphik/linearStruct.eps,width=11cm}
%    \caption{Aufbau eines linearen Individuums. Die Sequenz von
%    Instruktionen wird von rechts nach links abgearbeitet. Die
%    Ergebnisse jeder Instruktion werden in den Registern gespeichert.}
%    \label{fig:Linear}
%  \end{center}
%\end{figure}

Eine Besonderheit des linearen GP ist noch das Maschinensprache GP,
der Aufbau der Individuen ist identisch, der Unterschied liegt in der
Repräsentation, mit der die Individuen im Speicher dargestellt
werden. Normalerweise ist dies eine Datenstruktur, die durch ein
Programm interpretiert wird. Beim Maschinensprache GP liegen die
Individuen aber direkt in Maschinensprache vor und können daher sofort
von der CPU verarbeitet werden. Dies hat zur Folge, dass dieses
Verfahren sehr effizient und schnell ist.


%----------------------------------------------------------------------
\subsection{Graph GP}
%----------------------------------------------------------------------

\begin{wrapfigure}{r}{75mm}
%\begin{figure} [ht]
  \begin{center}
    \epsfig{file=Pictures/Graphik/graphKnotenT.eps,width=7.5cm}
    \caption{Aufbau eines PADO Knotens. Man kann deutlich die
    Zweiteilung des Knotens in den Funktions- und Branchingteil erkennen. 
    Gleichzeitig wird der Datenfluss dargestellt, der über den Stack läuft.}
    \label{fig:graphKnoten}
  \end{center}
\end{wrapfigure}%{figure}

Das \emph{Graph GP} \index{Graph GP} nimmt unter den Strukturen eine
Sonderrolle ein, da die Struktur nicht so eindeutig definiert ist wie
die beiden anderen Strukturen und unter dem gleichen Namen
verschieden aufgebaute Individuen verstanden werden.


Ein Vertreter des Graph GP's ist das \emph{PADO-System}
\index{PADO-System} von Teller und
Veloso~\cite{teller1,kantschik:1999:EuroGP,kantschik:1999:CEC}.
Die Operationen werden in dieser Struktur in einem gerichteten Graph
organisiert. %Die Abbildung~\ref{fig:graph} zeigt die Struktur eines Graph
%Individuums.


%\begin{figure} [ht]
%  \begin{center}
%    \epsfig{file=Pictures/Graphik/graphT.eps,width=11cm}
%    \caption{Aufbau eines PADO Individuums. Der Startknoten ist durch
%    die grüne Farbe gekennzeichnet und der Stopknoten durch die rote Frabe. }
%    \label{fig:graph}
%  \end{center}
%\end{figure}




Die Kanten zwischen den Knoten stellen in dieser Struktur
den potentiellen Programmfluss des Individuums dar. Der Datenfluss
verläuft in dieser Struktur über einen Stack, von dem die Operationen
ihre Eingaben nehmen und ihre Ausgaben schreiben. Zusätzlich gibt es
 noch einen externen Speicher, in dem Zwischenergebnisse
länger gespeichert werden können. Die Abbildung~\ref{fig:graphKnoten}
verdeutlicht den Aufbau eines Knotens und dessen Interpretation.
Die Funktion des Knotens nimmt ihre Parameter vom Stack
und schreibt das Ergebnis anschließend wieder auf den Stack. Danach
wird die Branching Funktion des Knotens ausgewertet, hierzu wird mit
Hilfe des vorher berechneten Ergebnisses die Kante zum
Nachfolgerknoten gewählt. Über diese Funktionen wird der Programmfluss
gesteuert.


Der Aufbau dieses Individuums verhindert weder Zyklen noch Rekursionen, so dass
Programme entstehen können, die nicht terminieren. Um dies zu
verhindern erhält jedes Programm eine Laufzeitbeschränkung. Diese
bewirkt, dass ein Programm nach einer maximalen Laufzeit beendet
wird. Im
optimalen Fall sollten die Programme jedoch mit dem \emph{Stopknoten}
beendet werden. Die Interpretation des Individuums beginnt immer mit
dem \emph{Startknoten}.

Ein anderer Vertreter des Graph GP benutzt die Graphstruktur nicht zur
Kontrolle des Programmflusses, sondern für den Datenfluss, wie es beim
Baum GP benutzt wird (siehe
\cite{Ang98,Pol97,niehaus:2001:EuroGP,niehaus03}). Bei dieser
Struktur muss man jedoch darauf achten, dass es nicht zu Kreisen und
Rekursionen kommt, da derartige Programme sonst nicht terminieren würden.
Dies hat zur Folge, dass bei diesen Strukturen meistens auf Crossover
verzichtet wird (siehe hierzu~\ref{sub:Rekom}).
Eine Ausnahme stellt das GGP System von Jens Niehaus dar, welches ein
Crossoververfahren für ein Graph GP System entwickelt hat, in dem die Kanten
des Graphen den Datenfluss darstellen~\cite{niehaus03:Diss}.
Die erhöhte Komplexität verhindert die Verbreitung dieser Strukturen,
da mit Baum und Linearem GP auch gute Ergebnisse erzielt werden.


%----------------------------------------------------------------------
\section{Genetische Operatoren}
%----------------------------------------------------------------------
\label{sec:genOp}

Die Initialpopulation hat im allgemeinen eine schlechte Fitness, die durch
den evolutionären Prozess verbessert wird. Die Verbesserung der Fitness
während des
evolutionären Prozesses wird mittels \emph{genetischer
  Operatoren}~\cite{banzhaf:1997:book} \index{genetische Operatoren}
durchgeführt. Die
\emph{genetischen Operatoren} manipulieren dabei einzelne Individuen innerhalb
der Population.
Prinzipiell unterscheidet man \emph{Rekombinations-, Mutations-} und
\emph{Replikations-}Operatoren.
Der \emph{Replikations-Operator}\index{Reproduktions-Operator} ist der
einfachste der drei Operatoren. Er erstellt eine einfache Kopie von einem Individuum.
%die an einer anderen Stelle innerhalb der Population gespeichert wird.

%----------------------------------------------------------------------
\subsection{Rekombination}
%----------------------------------------------------------------------
\label{sub:Rekom}

\begin{wrapfigure}{r}{70mm}
%\begin{figure} [ht]
  \begin{center}
    \epsfig{file=Pictures/Graphik/graphXoverT.eps,width=7cm}
    \caption{Graphbasiertes Crossover.}
    \label{abb:GraphXover}
  \end{center}
\end{wrapfigure}%{figure}

Die \emph{Rekombination} ist ein Verfahren, bei dem aus mindestens zwei
Individuen  neue Individuen erzeugt werden, indem es zwischen den
Elternindividuen \emph{Strukturelemente} austauscht. Eine Variante der
Rekombination ist der \emph{Crossover}\index{Crossover}-Operator. 


Grundsätzlich unterscheidet sich dabei das Vorgehen des Crossover-Operators bei
den verschiedenen Strukturen, die die Individuen aufweisen.


Bei baumbasierten Individuen wählt der Crossover-Operator aus beiden Eltern
je einen Unterbaum zufällig aus. Die ausgewählten Unterbäume werden dann
zwischen den beiden Individuen ausgetauscht~\cite{koza1, koza2}.

Abbildung~\ref{abb:TreeXover} skizziert dieses Vorgehen, wobei die mit Eltern
bezeichneten Bäume die Ausgangsbäume und die mit Kinder bezeichneten Bäume die
durch das Crossover entstandenen Bäume sind.

\begin{figure} [!h]
\begin{minipage}{7cm}
  \begin{center}
    \epsfig{file=Pictures/Graphik/treeXover.eps,width=7cm}
    \caption{Baumbasiertes Crossover.}
    \label{abb:TreeXover}
  \end{center}
%\end{figure}
\end{minipage}
\hfill
\begin{minipage}{7cm}
%\begin{figure} [!h]
  \begin{center}
    \epsfig{file=Pictures/Graphik/linearesXover.eps,width=7cm}
    \caption{Linearbasiertes Zwei-Punkte-Crossover. In jedem der
    Individuen wird jeweils ein Segment von Knoten ausgetauscht.}
    \label{abb:LinXover}
  \end{center}
  \end{minipage}
\end{figure}

Beim Crossover linearer Individuen wird zufällig ein Punkt in beiden
Eltern bestimmt, von dem aus eine lineare Sequenz von Befehlen ausgetauscht
wird. Dabei müssen weder die relative Lage der Punkte noch die Längen der
Sequenzen übereinstimmen~\cite{nordin:linGP,nordin3,NoFrBa95}.
In der Abbildung~\ref{abb:LinXover} wird graphisch
das Vorgehen des Crossover-Operators dargestellt.





Der Crossover-Operator des graphbasierten GP tauscht prinzipiell zwischen den
beiden Elterngraphen eine zufällige Menge von Knoten aus. Die in der
Abbildung~\ref{abb:GraphXover} farblich markierten Knoten sind die Knoten, die
während des Crossovers zwischen den Eltern ausgetauscht werden. Die
roten Kanten in den neuen Graphen sind die Kanten, die durch das
Crossover durchtrennt wurden. Sie werden in beiden Teilgraphen anschließend
durch zufällig gewählte Kanten verbunden~\cite{Astro5, Astro3}.


Jedoch müssen beim Crossover zwischen zwei Graphen noch weitere Punkte
beachtet werden, zum Beispiel, wie die neuen Kanten gesetzt werden.
Wenn man beim Graph GP die Variante nutzt, die den Datenfluss über die
Kanten befördert, so muss man darauf achten, dass die Teilgraphen die
gleiche Anzahl von eingehenden und ausgehenden Kanten haben.
Dies führt dazu, dass man ein exponentielles Laufzeitverhalten erhält, wenn man
einen einfachen Algorithmus für dieses Problem nutzt. Daher werden in den meisten
Systemen Heuristiken verwendt um die richtigen Teilgraphen zu finden, siehe
hierzu~\cite{niehaus03:Diss}.

%----------------------------------------------------------------------
\subsection{Mutation}
%----------------------------------------------------------------------

%Die \emph{Mutation}\index{Mutation} ist eine weitere Möglichkeit ein
%Individuum während der Evolution zu verändern. Der Unterschied zwischen dem
%Mutations-Operator und dem Crossover-Operator liegt darin, daß der
%Mutations-Operator nur auf ein Individuum angewendet wird.

Die \emph{Mutation}\index{Mutation} ist eine \emph{zufällige}, aber strukturell
erlaubte Veränderung des genetischen Codes eines Individuums. Der
genetische Code kann dabei an einer Stelle oder an mehreren Stellen
des Individuums geändert werden. Die Funktionsweise des
Mutations-Operators hängt von der Struktur der Individuen ab.

Bei der Mutation eines Baumes wird zufällig ein Knoten gewählt, dann wird
entweder  die Operation in diesem Knoten ausgetauscht oder
der ganze Unterbaum an diesem Knoten wird durch einen zufällig erzeugten
Unterbaum ersetzt.

Bei der Mutation einer linearen Struktur wählt der Operator eine Instruktion
im Individuum aus.
Diese Instruktion wird mutiert, indem entweder die Instruktion durch
eine andere ersetzt wird oder die Operanden der Instruktion variiert werden.
Auch hier kann entweder nur eine Instruktion oder eine Folge von Instruktionen, die von
einem bestimmten Punkt des Individuums ausgeht mutiert werden.

Bei graphbasierten Strukturen ergeben sich noch weitere Möglichkeiten für den
Mutations-Operator. Grundsätzlich wird auch hier an einem oder mehreren Knoten
der Inhalt verändert, jedoch ist der Aufbau eines Knotens in einem Graphen
anders. So kann nicht nur der Knoteninhalt verändert werden, sondern auch die
Kanten eines Graphen (siehe \cite{Astro3}). 


%----------------------------------------------------------------------
\section{Selektion und Fitness}
%----------------------------------------------------------------------
\label{sec:Fitness}

GP führt keine vollständige Suche im Suchraum durch.
% noch ein Hill-Climbing-Verfahren, daß von einer momentanen
%Position im
%Suchraum versucht ein Optimum zu finden.
Vielmehr bietet die GP-Population die Möglichkeit einer parallelen
Suche, die durch die Rekombination und Mutation von \emph{guten} Individuen
einen Weg zu einer guten (optimalen) Lösung im Suchraum zeigt.

Um diese \emph{besseren} Individuen zu finden, muss dem GP System eine Güte für
die
einzelnen Individuen zur Verfügung gestellt werden, mit der es möglich ist
diese Individuen im Pool zu finden, damit sie anschließend von den
\emph{genetischen Operatoren} zur Reproduktion herangezogen werden können. Die
Güte wird in GP-Systemen im allgemeinen durch eine \emph{fitnessbasierte
  Selektion} erzeugt, die aus zwei Bestandteilen besteht, einer
\emph{Fitnessfunktion} und einer \emph{Selektionsmethode}. 

%----------------------------------------------------------------------
\subsection{Die Fitnessfunktion}
%----------------------------------------------------------------------

Die \emph{Fitnessfunktion}\index{Fitnessfunktion} bildet die einzelnen
Individuen auf einen Wert ab, der als \emph{Fitness} bezeichnet wird.
Die \emph{Fitness} bestimmt die Güte des Individuums bezüglich des zu
lösenden Problems. Damit ordnet die Fitness jedem Individuum einen Rang
innerhalb der Population zu.



In GP wird die Fitnessfunktion  oft bezüglich einer \emph{Trainingsmenge}
berechnet, die aus \emph{Fitnesscases}\index{Fitnesscases} besteht.
Ein Fitnesscase $c$ ist ein Tupel $c = (e, a)$ von einem Eingabedatum $e \in
\einmenge$ und dem zum Eingabedatum gehörenden Ausgabedatum $a \in \ausmenge$.
Eine Teilmenge aller möglichen Fitnesscases
wird als Trainingsmenge  bezeichnet. 



%----------------------------------------------------------------------
\subsection{Selektionsmethoden}
%----------------------------------------------------------------------
\label{sec:Selektionsmethoden}

Die Aufgabe der Selektion ist es, nachdem die Qualität der Individuen durch
die Berechnung ihrer Fitness bestimmt wurde, die Individuen zu selektieren, die
den genetischen Operatoren zur Verfügung gestellt werden und die Individuen in
der Population zu bestimmen, die ersetzt werden sollen.

In der Literatur findet man verschiedene Selektionsmethoden, denn
die Selektion selbst ist ein sehr entscheidender Punkt innerhalb
der evolutionären Berechnung und somit ist die Auswahl der richtigen Methode
eine wichtige Entscheidung. Die verschiedenen Methoden haben
unterschiedliche Auswirkungen auf die Geschwindigkeit und den Erfolg des
evolutionären Prozesses.

Die hier vorgestellten Selektionsmethoden\index{Selektionsmethoden} sind ein
kurzer Überblick über die bekannten Methoden.
%Auf die Methoden die
%im \gps-System verwendet werden wird in Kapitel~\ref{sec:Selektion}
%näher eingegangen.




%----------------------------------------------------------------------
%\paragraph*{Proportionale Selektion }
%----------------------------------------------------------------------

Die proportionale Selektion\index{proportionale Selektion} wird in
\GA-Systemen als allgemeiner Selektionsmechanismus verwendet~\cite{holland}.
Die  proportionale Selektion ordnet jedem Individuum einen
Wahrscheinlichkeitswert $p_{i}$ zu, der die Chance des Individuums angibt in
die nächste Generation zu gelangen.



%----------------------------------------------------------------------
%\paragraph*{Truncation oder ($\mu$, $\lambda$)-Selektion }
%----------------------------------------------------------------------

Die Truncation\index{Truncation}-Selektionsmethode kommt aus dem Bereich der
ES, in der sie als ($\mu$ ,$\lambda$)
Selektion~\cite{schwefel1}\index{($\mu$ ,$\lambda$) Selektion} bekannt
ist. Bei dieser Methode werden durch
Rekombination der $\mu$ Eltern  $\lambda$ Nachkommen erzeugt, aus denen die
besten $\mu$ Individuen als Eltern der nächsten Generation ausgewählt werden.

Eine Variante dieser Methode ist die ($\mu + \lambda$) Selektion\index{($\mu +
  \lambda$) Selektion}, hierbei werden die Eltern in den
Selektionsprozess mit einbezogen. Wenn alle Kinder schlechtere Fitnesswerte
aufweisen als ihre Eltern, wird die nächste Generation wieder aus denselben
$\mu$  Eltern gebildet.


%----------------------------------------------------------------------
%\paragraph*{Rangselektion }
%----------------------------------------------------------------------

Die Rangselektion\index{Rangselektion} basiert auf der Eigenschaft der
Fitnesswerte, den Individuen eines Pools durch Sortieren einen Rang
zuzuordnen~\cite{banzhaf:1997:book}. Die
Selektionswahrscheinlichkeit eines Individuums wird dann als eine Funktion aus
dem Rang des Individuums innerhalb der Population bestimmt.

%----------------------------------------------------------------------
%\paragraph*{Turnierselektion }
%----------------------------------------------------------------------

Die Turnierselektion\index{Turnierselektion}~\cite{banzhaf:1997:book} basiert
auf der Idee
des Wettkampfes einer Teilmenge von Individuen innerhalb der Population. Eine
Anzahl von Individuen, die durch eine Turniergröße bestimmt werden, wird
zufällig ausgewählt, die Hälfte der Individuen mit den besseren Fitnesswerten
in der Turniermenge ersetzen anschließend die schlechteren durch Reproduktion
(Überschreiben).


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