\section{Genetische Algorithmen}
\label{sec:ga}
Genetische Algorithmen sind heuristische Optimierungsverfahren, die sich an den
in der biologischen Evolution beobachteten Anpassungsmechanismen orientieren.
Sie arbeiten auf Grundlage einer Menge
von möglichen Lösungen f"ur ein spezifisches Problem, wobei in Anlehnung an die biologischen
Begriffe die einzelne L"osung \emph{Individuum} und die Gesamtmenge der L"osungen
\emph{Population} genannt wird.
Das Ziel eines Genetischen Algorithmus ist es, aus einer großen Anzahl möglicher Lösungen für
ein Problem eine oder mehrere möglichst gute Lösungen herauszufinden.
Besonders interessant ist die Methode zur Lösung von Problemen mit hoher Komplexität und
dementsprechend großem Zustandsraum, da eine analytische Lösung derartiger Probleme oft nicht
möglich ist.

Das Grundkonzept der Genetischen Algorithmen basiert im Wesentlichen auf Arbeiten
von John Holland, der sich als einer der ersten Wissenschaftler mit der Beschreibung
und Analyse adaptiver Systeme besch"aftigt hat.
Den Entwurf des Konzepts, das heute unter dem Begriff \textit{Genetischer Algorithmus}
(im Folgenden auch GA genannt)
gro"se Verbreitung gefunden hat, nannte Holland urspr"unglich \textit{reproductive plan}
\citep{holland:92}.
Obwohl oder vielleicht gerade weil dieses Konzept eine sehr einfache Version eines Genetischen
Algorithmus darstellt, wird im Folgenden mit einer detaillierten Vorstellung dieses in der heutigen
Literatur oft \textit{kanonischer GA} genannten Verfahrens begonnen.
Anschlie"send wird auf einige ausgew"ahlte interessante Erweiterungen und Modernisierungen sowie
Hollands \textit{Schematheorie} eingegangen.

\subsection{Funktionsweise}
\label{sec:gafunction}
Um die elementare Funktionsweise eines Genetischen Algorithmus zu verdeutlichen, wird hier
der \textit{kanonische GA} nach Holland vorgestellt (vgl. \citet{nissen:97}).
Jedes Individuum $\vec{a}$ wird als Bitstring dargestellt, dessen L"ange $L$
je nach Anwendung auf eine feste Anzahl von Bits festgelegt wird. Dabei wird eine
bin"are Darstellung gewählt, das hei"st die Bits k"onnen entweder den Wert 0 oder 1 haben: 
\[
 \vec{a} = (a_{1},a_{2},\ldots ,a_{L-1},a_{L}) \in \{ 0,1 \} ^{L}
\]
Der Bitstring $\vec{a}$ wird \textit{Genotyp} des Individuums genannt.
Jeder Genotyp wird in $n$ Segmente variabler L"ange aufgeteilt. Analog zur Betrachtung
des gesamten Strings als interne Repr"asentation einer Lösung entspricht jedes Segment
der internen Repräsentation einer Variable des zu lösenden Optimierungsproblems.

Man betrachtet bei einem Optimierungsproblem eine zu maximierende Zielfunktion $F(\vec{x})$,
die im Kontext Genetischer Algorithmen auch \emph{Fitnessfunktion} genannt wird.
$\vec{x} = x_{1},x_{2},\ldots ,x_{n}$ stellt den Vektor aller Variablen der Funktion dar. Da durch
die bin"are Codierung die Anzahl verschiedener Werte für eine Variable beschränkt ist,
muss f"ur jede Variable $x_{j}$ mit $(j = 1,2,\ldots ,n)$ festgelegt werden, welchen Wertebereich sie annehmen kann.
Auf die Verfahren bin"arer Codierungen wird in Abschnitt \ref{sec:codierung} noch n"aher eingegangen.
Ziel des GA ist es, einen Eingabevektor $\vec{x}$ zu finden, der die Fitnessfunktion maximiert.

In Anlehnung an das biologische Vorbild wird der Bitstring auch als \textit{Chromosom},
eine bestimmte Bitposition im String als \textit{Gen}
und deren konkreter Wert analog dazu als \textit{Allel} bezeichnet. Eine mögliche Lösung wird
\emph{Individuum} genannt, wobei
hier das konkrete Ergebnis einer einzelnen Lösung als \textit{Phänotyp}
und ihre interne binäre Repräsentation als \textit{Genotyp} des Individuums bezeichnet wird. 

\subsection{Schrittweiser Ablauf}
\label{ga:ablauf}
Im Folgenden soll der Ablauf eines Genetischen Algorithmus schrittweise beschrieben werden.

\subsubsection{Initialisierung}
\label{ga:initialize}
Als erster Schritt muss eine initiale Population $P$ von $\mu$ Individuen $\vec{a}_{i}$ mit $(i = 1,2,\ldots ,\mu)$
erzeugt werden, wobei die Anzahl $\mu$ der Individuen je nach Anwendung sehr unterschiedliche Werte besitzen kann.
In den meisten F"allen wird die Ausgangspopulation stochastisch erzeugt, d.h. sämtliche Bits aller Genotypen $\vec{a}_{i}$
werden in allen erzeugten Individuen stochastisch unabh"angig voneinander per Zufall auf 0 oder 1 gesetzt.

\subsubsection{Bewertung der Lösungen}
\label{subsec:bewertung}
Um einen Genetischen Algorithmus erfolgreich einsetzen zu k"onnen, ben"otigt man eine
geeignete Fitnessfunktion $F$.
% - Decodierungsfunktion rausgenommen
%, welche sich aus der zu maximierenden Zielfunktion $F$ und der Decodierungsfunktion $\Gamma$ zusammensetzt:
% $\varPhi = F \circ \Gamma$. Das bedeutet, das Individuum
$\vec{a}_{i}$ wird % von $\Gamma$ decodiert und anschlie"send
von $F$ auf seinen Fitnesswert abgebildet.
Geht man von einer zu maximierenden Zielfunktion $F$ aus, so folgt aus einem hohen Fitnesswert
eine gute Eignung des Individuums für das zu lösende Problem.
% Es gilt:
% \[
%  \varPhi (\vec{a}_{i}) = F(\Gamma (\vec{a}_{i}))
% \]
Der Erfolg eines Genetischen Algorithmus h"angt in hohem Ausma"s von der Wahl einer geeigneten
Fitnessfunktion ab.

\subsubsection{Selektion und Replikation}
\label{ga:selection}
Im Selektionsschritt werden aus der aktuellen Population $P$ diejenigen Individuen ausgew"ahlt,
die als "`Eltern"' f"ur die n"achste Generation fungieren sollen. Es werden $n$ Individuen
stochastisch ausgew"ahlt, wobei $n$ eine gerade Zahl zwischen 2 und $\mu$ sein muss.
Jedes Individuum $\vec{a}_{i} \in P$ besitzt eine spezifische Selektionswahrscheinlichkeit
$p_{s}$:

\[
 p_{s}(\vec{a}_{i}) = \dfrac{F(\vec{a}_{i})}{\sum \limits_{j=1}^{\mu} F (\vec{a}_{j})}
\]

Dieses Selektionsverfahren wird fitnessproportionale Selektion genannt und z"ahlt zu den
\textit{nicht diskriminierenden} Selektionsverfahren (engl. \textit{not extinctive}),
so genannt da jedes Individuum eine positive Selektionswahrscheinlichkeit besitzt und damit eine
theoretische Chance auf Reproduktion besitzt.
% Dabei werden ebenso viele Individuen
% ausgew"ahlt, wie in der Population vorhanden sind (n"amlich $\mu$).
Einzelne Individuen dürfen
beliebig oft gewählt werden, was zur Folge hat, dass sich in der Praxis Individuen mit hohem Fitnesswert
mehrmals und solche mit niedrigem Fitnesswert selten bis gar nicht "`fortpflanzen"' k"onnen.
% Bei den sogenannten \textit{diskriminierenden} Selektionsverfahren, wie sie in anderen evolution"aren
% Verfahren teilweise angewendet werden, bekommen hingegen nur bestimmte Individuen einer Population
% "uberhaupt die Chance auf Reproduktion.

In der Literatur wird hierzu gerne der anschauliche Vergleich mit einem Gl"ucksrad benutzt, welches
in $\mu$ Abschnitte eingeteilt ist. Jeder Abschnitt entspricht einem Individuum aus P und hat eine der
Selektionswahrscheinlichkeit des Individuums entsprechende Breite auf dem Gl"ucksrad. Das Rad wird
$n$-mal gedreht und das Ergebnis jeder Drehung festgehalten. Aufgrund des Vergleichs wird dieses
Auswahlverfahren auch \textit{Roulette"=Wheel"=Selektion} genannt.

Von den zur Reproduktion ausgewählten Individuen aus der Population $P$ werden Kopien erstellt
und in einen Behälter $\mathcal{M}_{t}$ gelegt, in welchen
$n$ Individuen passen. Nach $n$ Selektionsvorg"angen
erhält man ein $\mathcal{M}_{t}$, das mit $n$ Kopien von Individuen aus $P$ gef"ullt ist. 
Dabei darf jedes Individuum aus $P$ beliebig oft vom Selektionsalgorithmus ausgewählt und in $\mathcal{M}_{t}$
kopiert werden, weswegen man von einer stochastischen Auswahl \textit{mit Zurücklegen}
spricht.
Der beschriebene Kopierprozess wird als \textit{Replikation} bezeichnet.
% TODO Schematische Darstellung von Replikationsvorgang - Population P -> mating pool daRSTELLEN

\subsubsection{Reproduktion}
\label{sec:steprep}
Die folgenden Schritte 1 bis 4 müssen jeweils $\frac{n}{2}$"=mal durchlaufen werden, da in jedem Durchlauf zwei
Individuen aus $\mathcal{M}_{t}$ reproduziert werden.

\paragraph{Schritt 1: Partnerwahl}
Es werden zuf"allig zwei Elternindividuen $\vec{a}_{E_{1}}$ und $\vec{a}_{E_{2}}$ aus $\mathcal{M}_{t}$
ausgew"ahlt, aus denen in den n"achsten
drei Teilschritten zwei Nachkommen entstehen werden. Dabei wird in dieser einfachen Variante des GA jedes Individuum
in $\mathcal{M}_{t}$ mit gleicher Wahrscheinlichkeit $\frac{1}{n}$ gezogen. Die Fitness der einzelnen Individuen
wird bei der Auswahl nicht mehr berücksichtigt, weil schon die Wahrscheinlichkeit für die Übernahme in
$\mathcal{M}_{t}$ von den jeweiligen Fitnesswerten abhängt und Individuen mit außergewöhnlich hoher Fitness
statistisch häufiger in $\mathcal{M}_{t}$ vorhanden sind.

Die stochastische Auswahl aus
$\mathcal{M}_{t}$ erfolgt "`ohne Zurücklegen"', das bedeutet jedes Individuum kann nur einmal gew"ahlt werden
und steht im n"achsten Durchlauf nicht mehr zur Verf"ugung.

\paragraph{Schritt 2: Crossover}
Das Crossover im Genetischen Algorithmus entspricht der Rekombination des Erbguts zweier sich miteinander
fortpflanzender Lebewesen in der Natur. Es wird als zentraler Operator des GA betrachtet, da durch das Crossover
die gr"o"sten Ver"anderungen im digitalen Genpool passieren.

Im hier betrachteten kanonischen GA wird als einfachste Variante das \textit{Ein"=Punkt"=Crossover} verwendet.
Im Vorfeld wird eine Wahrscheinlichkeit $p_{xover}$ festgelegt, die bestimmt, mit welcher Wahrscheinlichkeit bei der
Reproduktion ein Crossover stattfinden soll.
Dabei wird ein stochastischer Auswahlprozess benutzt,
der mit Wahrscheinlichkeit $p_{xover}$ für ein Crossover und mit Wahrscheinlichkeit $1 - p_{xover}$
gegen ein Crossover entscheidet. 
Im Allgemeinen
wird $p_{xover}$ in einer Größenordnung von $p_{xover} \geq 0,6$ gew"ahlt. Bei zu groß gew"ahltem
$p_{xover}$ besteht die Gefahr,
dass sinnvolle Ergebnisse und auftretende Schemata zerst"ort werden (siehe Abschnitt \ref{sec:schema}).

Entscheidet der Zufall gegen ein Crossover, so werden die beiden Elternstrings
($\vec{a}_{E_{1}}$ und $\vec{a}_{E_{2}}$)
unver"andert in zwei Nachkommenstrings ($\vec{a}_{K_{1}}$ und $\vec{a}_{K_{2}}$) kopiert:

\[
 \vec{a}_{K_{1}} = \vec{a}_{E_{1}}
\]
\[
 \vec{a}_{K_{2}} = \vec{a}_{E_{2}}
\]

Soll ein Crossover stattfinden, so wird stochastisch ein Crossover"=Punkt~$c$ zwischen $1$ und $L-1$ festgelegt.
Beim Kopieren der
Elternstrings in die Nachkommenstrings werden nun jeweils die Bits hinter dem Crossover"=Punkt mit denen des
Reproduktionspartners ausgetauscht, was zur Folge hat, dass zwei Individuen entstehen, die aus dem Erbgut der
Eltern zusammengesetzt sind:

\[
 \vec{a}_{K_{1}} = (a_{E_{1},1},a_{E_{1},2}, \ldots ,a_{E_{1},c},a_{E_{2},c+1}, \ldots ,a_{E_{2},L})
\]
\[
 \vec{a}_{K_{2}} = (a_{E_{2},1},a_{E_{2},2}, \ldots ,a_{E_{2},c},a_{E_{1},c+1}, \ldots ,a_{E_{1},L})
\]

\paragraph{Schritt 3: Mutation}
Im Allgemeinen wird die Mutation als weniger bedeutend f"ur die Funktion eines Genetischen Algorithmus
eingestuft als das Crossover. Sie ist allerdings wichtig um zu gewährleisten, dass die Population
auch dann noch Veränderungen aufzeigt, wenn sich alle Individuen weitgehend ähnlich sind und
durch Rekombination kaum noch Veränderungen zu erreichen sind.

F"ur die Mutation wird ebenso eine feste Wahrscheinlichkeit festgelegt wie f"ur das Crossover, nur dass
die Mutationswahrscheinlichkeit~$p_{mut}$ meist sehr viel kleiner gew"ahlt wird. "Ubliche Werte sind etwa
$p_{mut} = 0,01$ oder $p_{mut} = 0,001$. Jedes Bit in jedem Individuum der Population wird nun mit dieser Wahrscheinlichkeit
$p_{mut}$ invertiert. Ein Wert von $p_{mut} = 0,01$ h"atte beispielsweise zur Folge, dass im Mittel eines von hundert
Bits invertiert w"urde.

\paragraph{Schritt 4: Übergang in die neue Population}
Die beiden Nachkommen $\vec{a}_{K_{1}}$ und $\vec{a}_{K_{2}}$ werden in die neue Population "ubernommen.
Für jeden Nachkommen wird ein Individuum aus der ursprünglichen Population entfernt, wobei die Auswahl
der zu entfernenden Individuen analog zur Auswahl der Elternindividuen erfolgt, mit dem Unterschied, dass
Individuen mit niedrigerem Fitnesswert mit höherer Wahrscheinlichkeit entfernt werden.

Die Schritte 1 bis 4 werden wiederholt, bis alle Individuen aus $\mathcal{M}_{t}$ verarbeitet wurden.
Die Populationsgröße $\mu$ bleibt dabei konstant, weil für jedes neu entstandene Individuum ein anderes
Individuum aus der Population entfernt wird. %Dieses Kriterium ist wichtig für den Aufbau von Selektionsdruck.

\subsubsection{Abbruchkriterium}
Die Schritte Bewertung, Selektion, Replikation und Reproduktion werden nun wiederholt,
bis ein festgelegtes Abbruchkriterium greift.
Abbruchkriterien k"onnen verschiedenartig sein, z.B. kann man eine Maximallaufzeit oder eine maximale
Generationenzahl $t_{max}$ definieren, nach deren Ablauf der Algorithmus terminiert.
Alternativ kann man die Termination des GA auch von Qualit"atsmerkmalen des Ergebnisses abh"angig machen.
Wenn z.B. "uber mehrere Generationen keine Verbesserung in den Ergebnissen mehr beobachtet werden kann
oder sich die Individuen einer Population weitgehend gleichen, ist meist keine Verbesserung mehr zu erwarten
und ein Abbruch vermutlich sinnvoll. 
Diese Festlegung eines Abbruchkriteriums ist notwendig, da Genetische Algorithmen mathematisch
gesehen nicht konvergieren. 
Nach Termination des Genetischen Algorithmus wird im Allgemeinen die beste der gefundenen Lösungen (sprich das
Individuum mit dem höchsten Fitnesswert) ausgegeben.

