\chapter{Genetische Algorithmen (GAs)}
\section{Allgemein}
Evolutionäre Algorithmen versuchen das Prinzip der Evolution, das Überleben des Stärkeren, zu nutzen. Die Suche nach einer Lösung wird hierbei durch Heuristiken gesteuert.\\
Die Fähigkeit der Natur, sich durch die Evolution weiter zu entwickeln und sich zu spezialisieren, wurde von Charles Darwin entdeckt und 1859 in seinem Werk über den Ursprung der Arten beschrieben. Es gibt verschiedene Annäherungen an das Problemlösen durch Evolution, eine davon ist der Genetische Algorithmus. Dabei werden aus einer Menge von potentiellen Lösungen bessere Lösungen durch eine entsprechende Wahrscheinlichkeitsverteilung eher ausgewählt als schlechtere. Diese Auswahl wird als {\em Selektion} bezeichnet. Aus jeweils zwei dieser selektierten Lösungen werden durch {\em Rekombination} neue Lösungen erzeugt und durch {\em Mutation} noch zufällig verändert. Diese Operatoren verändern die Lösungen genügend, um den Lösungsraum zu erforschen. Sie sind zwar für einen Biologen eine grobe Vereinfachung der Vorgänge der Natur, aber für den Informatiker bieten sie ein robustes und mächtiges Instrument für die adaptive Suche. Um diese Prozesse im Sinne der Evolution durchführen zu können, müssen diese möglichen Lösungen auf ihre Fähigkeit zu überleben, ihre Fitneß, getestet werden können.\\ 
Klassische Probleme, bei denen ein GA eingesetzt werden kann, sind zum Beispiel: das Rucksackproblem, das Traveling Salesman Problem und das Gefangenen Dilemma.\\
Das allgemeine Rucksackproblem, auch bekannt als {\em Multiple Knapsack Problem} (MKP), wird genauer in \cite{Chu97} behandelt.\\
Eine allgemeine Beschreibung von Genetischen Algorithmen ist in \cite{Mic92} zu finden. Unterschiedliche Einsatzmöglichkeiten von GAs sind in \cite{Gol89} beschrieben.

%\newpage
\subsection{Aufbau eines GA}
\begin{tabbing}
{\bf Prozedure} GA\\
{\bf beg}\={\bf in}\\
\> $t \leftarrow 0$;\\
\> Initialisierung (P(t));\\
\> Evaluierung(P(t));\\
\> {\bf whi}\={\bf le} (Abbruchbedingung nicht erfüllt)\\
\> {\bf begin}\\
\> \> $t \leftarrow t + 1$;\\
\> \> $Q_{s}(t) \leftarrow Selektion(P(t-1))$;\\
\> \> $Q_{r}(t) \leftarrow Rekombination(Q_{s}(t))$;\\
\> \> $P(t) \leftarrow Mutation(Q_{r}(t))$;\\
\> \> Evaluierung(P(t));\\
\> {\bf end}\\
{\bf end}\\
\end{tabbing}

\subsection{Wesentliche Begriffe für die Codierung}
\subsubsection{Die Population:}
Sie besteht aus einer im allgemeinen fixen Anzahl von potentiellen Lösungen, die auch Individuen genannt werden.\\
P(t) ist die Population zum Zeitpunkt t.
\subsubsection{Das Individuum:}
Es repräsentiert einen Punkt im Suchraum und kann somit auch als eine Lösung des Problems betrachtet werden. Im GA wird eine solche Lösung in codierter Form als sogenanntes {\em Chromosom} gespeichert. Ein Chromosom besteht aus Genen.
\subsubsection{Das Gen:}
Im klassischen GA wird für die Speicherung von Chromosomen ein aus Genen bestehender String fixer Länge verwendet. Jedes Gen kann einen Wert einer diskreten Wertemenge annehmen.

\subsection{Erläuterung des Algorithmus}
\subsubsection{Die Initialisierung:}
Zum Zeitpunkt $t = 0$ werden die Individuen, welche die Population bilden, initialisiert. Dies bedeutet sie erhalten eine meist nicht sehr gute, aber leicht berechenbare Lösung des Problems. Es entsteht eine Anfangspopulation. 
\subsubsection{Die Evaluierung:}
Mittels einer bestimmten Funktion wird die Güte der erzeugten Individuen bestimmt. Diese Güte kann entweder direkt aus der Problemstellung, wie zum Beispiel bei Minimierungs- und Maximierungsproblemen berechnet werden, oder durch spezielle Bewertungen, welche dem gestellten Problem entsprechen und somit gute und schlechte Individuen voneinander unterscheiden.
\subsubsection{Die ``while''-Schleife:}
Aus der Anfangspopulation wird mittels der Operatoren Selektion, Rekombination und Mutation eine neue Population zum Zeitpunkt $t + 1$ erzeugt. Einen solchen Schritt nennt man Generation. Die neu entstandene Population wird zur Ausgangspopulation, und eine neue Population entsteht in der nächsten Generation. So nähert sich der GA einer besseren Lösung des Problems.
\subsubsection{Die Selektion:}
Die Selektion bestimmt, welche Individuen und wie oft diese als Eltern für die Rekombination ausgewählt werden. Meist werden bessere Individuen eher und öfter selektiert, da aus ihnen eher bessere Individuen entstehen können. Es kann durchaus sein, und ist auch erwünscht, daß bessere Individuen mehrfach selektiert werden.\\
Wie stark gute Individuen schlechten vorgezogen werden, ist oft entscheidend und wird als {\em Selektionsdruck} bezeichnet. Zu starker Selektionsdruck bewirkt eine zu rasche Vermehrung der guten Individuen. Somit geht die Vielfalt in der Population zurück, und der GA konvergiert vorzeitig gegen ein lokales Optimum. Zu niedriger Selektionsdruck bewirkt hingegen, daß schlechte Individuen in der Population bleiben, der GA kaum konvergiert und somit eine Zufallssuche entsteht. \\Durch eine Bewertungsfunktion $g(i)$ kann zu jedem Individuum ein Wert berechnet werden, der die Güte dieses Individuums festlegt. Eine Selektionsmethode kann direkt diese Werte verwenden um Individuen zu selektieren bzw. diese Werte durch eine Fitneßfunktion $f(i) = scale(g(i))$ so verändern ({\em skalieren}), daß dadurch der Selektionsdruck gesteuert werden kann. Es kann zum Beispiel durch Skalierung der Wertebereich zwischen dem besten und dem schlechtesten Individuum so transformiert werden, daß das beste Individuum im Durchschnitt $k$-mal je Generation selektiert wird.\\ \\
\underline{Wichtige Selektionsmethoden sind:}
\begin{description}
\item[Fitness Proportional Selection:]
Diese Selektionsmethode ist auch unter dem Namen {\em Roulette-Wheel Selection} bekannt. Die Wahrscheinlichkeit für Individuen, bei der Selektion ausgewählt zu werden, ist proportional zu ihrer Fitneß (siehe Abb.~\ref{selection}, entnommen aus \cite{evol}). 
\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.7]{./data/roulettewsel.eps}
\caption{Fitness Proportional Selection} \label{selection}
\end{center}
\end{figure}

\item[Tournament Selection:]
Bei Tournament Selection werden, um ein Individuum zu selektieren, $k$ zufällig gewählte Individuen aus der Population verglichen und das beste davon genommen. Die Gruppengröße $k$ steuert somit den Selektionsdruck. Bei kleinem $k$ ist der Selektionsdruck niedrig, schlechte Individuen werden durchaus auch selektiert. Bei großem $k$ ist der Selektionsdruck groß, da fast ausschließlich die besten Individuen selektiert werden.
\end{description}

\subsubsection{Die Rekombination:}
Aus selektierten Individuen werden mittels Rekombination Nachfolger erzeugt. Diese Nachfolger beinhalten Gene aus ihren ``Eltern''. Die Rekombination ist der primäre Operator in einem GA und wird entweder für alle selektierten Individuen oder für den größten Teil davon zufallsgesteuert durchgeführt. Ein Beispiel für einen möglichen Rekombinationsoperator stellt der in Abb.~\ref{onepoint}, entnommen aus \cite{evol}, gezeigte {\em 1-point Crossover} dar. Dabei werden die Genstrings der beiden Eltern an einem zufällig gewählten Punkt aufgetrennt, und der Genstring des Nachfolgers wird aus den unterschiedlichen Teilen seiner Eltern zusammengesetzt.
\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.7]{./data/1ptCrossover.eps}
\caption{1-point Crossover} \label{onepoint}
\end{center}
\end{figure}

\subsubsection{Die Mutation:}
Die entstandenen Nachfolger können noch durch Mutation verändert werden. Sie dient zum Einbringen von neuem bzw. verlorengegangenem Genmaterial in die Population. Hierbei werden meist kleine Änderungen im Aufbau eines Individuums bewirkt. Die Mutation ist der sekundäre Operator in einem GA und wird nur sehr selten und zufallsgesteuert ausgeführt (siehe Abb.~\ref{mutation}, entnommen aus \cite{evol}).
\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.7]{./data/Mutation.eps}
\caption{Bitweise Mutation} \label{mutation}
\end{center}
\end{figure}

\subsection{Erweiterte Möglichkeiten}
\subsubsection{Elitismus:}
Unabhängig von der Selektion wird das beste Individuum der Ausgangspopulation unverändert in die neue Population übernommen.\\
Dadurch kann eine besonders gute gefundene Lösung nicht mehr verloren gehen. Die Fitneß des besten Individuums steigt pro Generation monoton an.
\subsubsection{Overlapping Populations:}
Pro Generationsschritt wird nur ein Teil der neuen Population erzeugt. Als restliche Individuen werden die besten aus der alten Population übernommen. Im Extremfall wird je Generation immer nur ein neues Individuum gebildet und ein altes damit ersetzt. Der hierbei entstehende GA wird als {\em steady state GA} bezeichnet.\\
Dadurch bleibt ein Teil der Population immer erhalten und muß nicht neu generiert werden. Dies ist besonders für sehr aufwendige Operatoren von Vorteil. Trotzdem werden aber immer die schlechtesten Individuen der Population durch die neu entstandenen ersetzt.


\newpage
\section{GAs für Reihenfolgeprobleme}
Für Reihenfolgeprobleme, wie das TSP, hängt die Lösung des Problems nur von der Anordnung der Gene ab. Im wesentlichen ist daher eine Permutation von Elementen einer vorgegebenen Menge gesucht. Im Falle des TSP repräsentiert ein Gen eine Stadt. Das erste Gen des Individuums repräsentiert also die Ausgangsstadt, das nächste Gen die von der Ausgangsstadt besuchte Stadt und so fort (siehe Abb.~\ref{tspbsp}). Es muß die optimale Anordnung der Gene gefunden werden, welche der kürzesten Rundreise entspricht.\\
Die Operatoren für Reihenfolgeprobleme unterscheiden sich von anderen dadurch, daß sie ausschließlich die Reihenfolge der Gene verändern. Dabei muß sichergestellt sein, daß keine ungültigen Individuen entstehen (siehe Abb.~\ref{cross} und Abb.~\ref{mut}). Ungültige Individuen sind hierbei Individuen, welche eine ungültige Lösung des TSP darstellen und somit zum Beispiel Städte doppelt oder gar nicht besucht würden.\\
Für die Mutation werden sogenannte Umordnungs-Operatoren verwendet. Diese bewirken, daß Gene des betroffenen Individuums lediglich vertauscht werden.
\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.7]{./data/cross.eps}
\caption{Fehler durch Rekombination} \label{cross}
\end{center}
\end{figure}
\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.7]{./data/mut.eps}
\caption{Fehler durch Mutation} \label{mut}
\end{center}
\end{figure}

%\newpage
\subsection{Die Mutationsoperatoren}
\subsubsection{Inversion:}
Bei diesem Mutationsoperator (siehe Abb.~\ref{inversion}) wird ein zufälliger Bereich aus dem Genstring ausgewählt. Dieser Bereich wird dann in umgekehrter Reihenfoge in den neuen Genstring eingefügt.
\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.7]{./data/han1.eps}
\caption{Inversion} \label{inversion}
\end{center}
\end{figure}

\subsubsection{Insertion:}
Bei diesem Mutationsoperator (siehe Abb.~\ref{insertion}) wird ein Gen zufällig aus dem Genstring ausgewählt und an einem beliebigen anderen Platz im neuen Genstring eingefügt.
\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.7]{./data/han2.eps}
\caption{Insertion} \label{insertion}
\end{center}
\end{figure}

\subsubsection{Displacement:}
Bei diesem Mutationsoperator (siehe Abb.~\ref{displacement}) wird ein zufälliger Bereich aus dem Genstring ausgewählt. Dieser Bereich wird dann an einer beliebigen Stelle in den neuen Genstring eingefügt.
\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.7]{./data/han3.eps}
\caption{Displacement} \label{displacement}
\end{center}
\end{figure}

\subsubsection{Reciprocal Exchange (Swap):}
Bei diesem Mutationsoperator (siehe Abb.~\ref{swap}) werden zwei Gene zufällig aus dem Genstring ausgewählt. Diese Gene werden im neuen Genstring miteinander vertauscht.
\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.7]{./data/han4.eps}
\caption{Reciprocal Exchange (Swap)} \label{swap}
\end{center}
\end{figure}

\subsection{Die Rekombinationsoperatoren}
\subsubsection{Partially Matched Crossover (PMX):}
Bei diesem Rekombinationsoperator (siehe Abb.~\ref{pmx}, entnommen aus \cite{evol}) wird anfangs ein zufälliger Bereich, der Crossover-Bereich, aus dem Genstring ausgewählt. Als Ausgangspunkt zur Entstehung der beiden Nachfolger wird das Individuum A auf A' und B auf B' kopiert. A' soll den Crossover-Bereich von B exakt enthalten. Als erstes Gen des Crossover-Bereichs soll `2' von B nach A' übernommen werden. Damit kein ungültiges Individuum entsteht, wird das an dieser Stelle stehende Gen `5' in A' mit dem Gen `2' in A' vertauscht. Dieser Vorgang wiederholt sich bis der ganze Crossover-Bereich übertragen wurde. Für B' funktioniert dieser Operator analog.\\ \\
\underline{Eigenschaften:} Der Crossover-Bereich wird exakt ausgetauscht. Die restlichen Gene und ihre Positionen werden ``so gut wie möglich'' erhalten. Es werden also die absolute Position und die Ordnung der Gene teilweise vererbt.\\
Für das TSP ist die absolute Position der Gene nicht relevant, nur ihre Ordnung ist von Bedeutung. Daher ist dieser Operator für das TSP nur mäßig geeignet.

\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.7]{./data/pmx.eps}
\caption{Partially Matched Crossover} \label{pmx}
\end{center}
\end{figure}

\subsubsection{Order Crossover (OX):}
Bei diesem Rekombinationsoperator wird anfangs ein zufälliger Bereich, der Crossover-Bereich, aus dem Genstring ausgewählt. Als Ausgangspunkt zur Entstehung der beiden Nachfolger wird das Individuum A auf A' und das Individuum B auf B' kopiert. Da der Crossover-Bereich von dem Individuum B in A' kopiert werden soll, müssen sämtliche Gene aus diesem Bereich in A' gelöscht werden (siehe Abb.~\ref{order1}). Danach werden die Gene in A' so umgeordnet, daß an den ersten Stellen der Crossover-Bereich des Individuums A steht, dann die durch das Löschen frei gewordenen Plätze und abschließend alle anderen Gene, hinter dem Crossover-Bereich beginnend  (siehe Abb.~\ref{order2}). Jetzt werden die freien Plätze mit dem Crossover-Bereich des Partners B ausgefüllt  (siehe Abb.~\ref{order3}). Für B' funktioniert dieser Operator analog.\\ \\
\underline{Eigenschaften:} Die relative Ordnung der Gene bleibt weitgehend erhalten, die absoluten Genpositionen werden kaum beibehalten.\\
Dieser Operator liefert für das TSP im allgemeinen gute Ergebnisse.
 
\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.7]{./data/OX1.eps}
\caption{Order Crossover: Schritt löschen} \label{order1}
\end{center}
\end{figure}
\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.7]{./data/OX2.eps}
\caption{Order Crossover: Schritt umordnen} \label{order2}
\end{center}
\end{figure}
\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.7]{./data/OX3.eps}
\caption{Order Crossover: Schritt einfügen} \label{order3}
\end{center}
\end{figure}

\newpage
\subsubsection{Cycle Crossover (CX):}
\underline{Randbedingung:} Jedes Gen wird von einem Elternteil unter Beibehaltung seiner absoluten Position übernommen.\\ \\
Bei diesem Rekombinationsoperator wird für A' das erste Gen von A übernommen.  Um der Randbedingung zu genügen, muß ein ganzer Zyklus von A übernommen werden (siehe Abb.~\ref{cycle}, oberes A'). Im gezeigten Beispiel bedeutet dies, daß `9' die Ausgangsstadt ist. Das erste Gen von B kann jetzt nicht mehr unter Beibehaltung seiner Position übernommen werden. Daher muß auch dieses Gen, nämlich `1', von A übernommen werden. Dieser Vorgang wird solange wiederholt, bis ein bereits gesetztes Gen, in diesem Fall `9' in B, an der zuletzt gesetzten Stelle steht. Alle frei verbliebenen Plätze werden von B übernommen (siehe Abb.~\ref{cycle}, unteres A'). Für B' funktioniert dieser Operator analog.\\ \\
\underline{Eigenschaften:} Die absolute Position der Gene bleibt erhalten, die Ordnung der Gene aber nicht.\\
Dieser Operator liefert für das TSP weniger gute Ergebnisse.

\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.7]{./data/CX.eps}
\caption{Cycle Crossover} \label{cycle}
\end{center}
\end{figure}

\subsubsection{Uniform Order Based Crossover (UOBX):}
Bei diesem Rekombinationsoperator wird für jede Position zufällig entschieden, ob das Gen vom ersten Elternteil übernommen wird oder nicht. Wie zum Beispiel in Abb.~\ref{uobx} dargestellt, werden mit Hilfe der Bitmaske M jene Gene aus A in das obere A' übernommen, an deren Stelle in M eine `1' steht. Alle anderen Positionen werden mit noch nicht vorkommenden Genen belegt, wobei deren Reihenfolge vom zweiten Elternteil übernommen wird (siehe Abb.~\ref{uobx}, unteres A'). Für B' funktioniert dieser Operator analog.\\ \\
\underline{Eigenschaften:} Die Ordnung und die absoluten Genpositionen werden teilweise vererbt.\\
Dieser Operator liefert für das TSP weniger gute Ergebnisse.

\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.7]{./data/UOBX.eps}
\caption{Uniform Order Based Crossover} \label{uobx}
\end{center}
\end{figure}

\subsubsection{Edge Recombination Crossover (ERX):}
Folgende Elternindividuen sind gegeben:\\[10pt]
$A = 1~2~3~4~5~6~7~8~9$\\
$B = 4~1~2~8~7~6~9~3~5$\\[10pt]
Bei diesem Rekombinationsoperator werden anfangs Kantenlisten für alle Städte aus den Eltern erzeugt (siehe Abb.~\ref{erxd}, erste Spalte).
\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.7]{./data/erxd.eps}
\caption{Edge Recombination Crossover} \label{erxd}
\end{center}
\end{figure}
Es wird zufällig eine Ausgangsstadt (zum Beispiel die erste Stadt vom ersten Elternteil) ausgewählt. Diese Stadt wird aus allen Kantenlisten entfernt. Die Stadt mit der kleinsten Kantenliste, welche von der Ausgangsstadt erreichbar ist, wird als nächste Stadt gewählt. Wenn hierbei mehrere Städte in Frage kommen, so wird eine von ihnen zufällig gewählt, wie in Abb.~\ref{erxd}~in der zweiten und dritten Spalte zu sehen ist. Ist aber keine Stadt möglich ({\em edge failure}), so wird eine der noch nicht besuchten Städte zufällig gewählt. Solange noch unbesuchte Städte vorhandenbleiben, wird dieser Vorgang wiederholt.\\ \\
\underline{Ein Ergebnis für die obig angegebenen Individuen wäre:}\\
$A = 1~4~5~6~7~8~2~3~9$\\

\subsubsection{Verbesserter Edge Recombination Crossover:}
Eine Verbesserung des vorhergegangenen ERX ist, Kanten welche in beiden Eltern vorkommen in den Kantenlisten zu markieren und bei der Rekombination anderen, einfach vorkommenden Kanten vorzuziehen. Obige Kantenlisten würden wie in Abb.~\ref{erxvd} verändert. Im Gegensatz zum ERX ohne Verbesserung wird hier die Stadt `2' als nächste Stadt genommen, da sie über eine markierte Kante erreicht werden kann.\\ \\
\underline{Ein Ergebnis für die obig angegebenen Individuen wäre:}\\
$A = 1~2~8~7~6~9~3~4~5$\\
\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.7]{./data/erxvd.eps}
\caption{Verbesserter Edge Recombination Crossover} \label{erxvd}
\end{center}
\end{figure}
\\
\underline{Eigenschaften:} Hierbei sind die Verbindungen zwischen den Städten wesentlich. Der Nachkomme wird so erzeugt, daß möglichst viele Kanten erhalten bleiben. Die Richtung der Kanten spielt keine Rolle.\\
Für das ``blinde'' TSP, bei dem der tatsächliche Abstand der Städte zueinander in der Rekombinationsmethode nicht betrachtet wird, ist dieser Operator einer der besten.

\subsubsection{Hybrides Verfahren mit Heuristik (nach Grefenstette):}
Diese Rekombinationsmethode basiert auf dem vorhergegangenen ERX. Bei der Auswahl, welche Stadt die nächste werden soll, werden die tatsächlichen Abstände zu diesen Städten berücksichtigt. Nach einer Wahrscheinlichkeitsverteilung proportional zu diesen Abständen wird die nächste Stadt ausgewählt. Bei dieser Verteilung wird sichergestellt, daß nähergelegenere Städte eher gewählt werden als entferntere Städte. Ist keine Stadt mehr vorhanden, so wird wie beim ERX eine noch unbesuchte Stadt zufällig gewählt.\\ \\
\underline{Eigenschaften:} Durch Ausnutzung der Heuristik erreicht man noch bessere Ergebnisse.


