Makefile: Das Bauen der Bilder korrigiert / vereinfacht.

[diplomarbeit.git] / diplomarbeit.tex

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index a58d629..40ade90 100644 (file)
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -102,6 +102,21 @@ Sortiernetzwerke angegeben.
 \end{abstract}
 \newpage
 
+\section*{Eidesstattliche Erklärung}
+
+Ich versichere, dass ich die vorliegende wissenschaftliche Arbeit
+selbstständig verfasst und keine anderen als die angegebenen Hilfsmittel
+verwendet habe. Die Stellen der Arbeit, die anderen Werken dem Wortlaut oder
+dem Sinn nach entnommen sind, wurden unter Angabe der Quelle als Entlehnung
+deutlich gemacht. Das Gleiche gilt auch für beigegebene Skizzen und
+Darstellungen. Diese Arbeit hat in gleicher oder ähnlicher Form meines Wissene
+nach noch keiner Prüfungsbehörde vorgelegen.
+\\[3cm]
+München, den 20.~März 2011,\\
+\\[1cm]
+Florian Forster
+\newpage
+
 \tableofcontents
 
 \newpage
@@ -349,14 +364,18 @@ Optima nicht mehr findet. Werden gute Lösungen hingegen nur wenig bevorzugt,
 erforscht der Algorithmus den Lösungsraum in viele Richtungen. Dieses
 \textit{Exploration} (Englisch für „Erforschung“) genannte Verhalten sorgt
 zwar dafür, dass der Algorithmus langsamer auf ein Optimum zusteuert, dafür
-findet er aber in der Regel bessere Lösungen.
+findet er aber in der Regel bessere Lösungen. Die Rolle, die
+\textit{Exploitation} und \textit{Exploration} bei evolutionären
+Optimierungsalgorithmen spielen, wird von \textit{Eiben} und
+\textit{Schippers} in~\cite{ES1998} untersucht.
 
 Die Parameter evolutionärer Algorithmen so einzustellen, dass sich ein guter
 Mittelweg zwischen den beiden Extremen einstellt, ist eine Aufgabe, die sich
 nur experimentell lösen lässt. Die genauen Parameter hängen nicht nur vom
 eigentlichen Algorithmus, sondern auch vom konkreten Problem ab, so dass sich
 beispielsweise bei der Optimierung von Sortiernetzwerken die Parameter
-zwischen verschiedenen Leitungszahlen stark unterscheiden.
+zwischen verschiedenen Leitungszahlen stark unterscheiden. Einen Überblick
+geben \textit{Kalyanmoy Deb} und \textit{Samir Agrawal} in~\cite{DA1998}.
 
 Die Erforschung (\textit{Exploration}) kann von einem weiteren Mechanismus
 unterstützt werden, der ebenfalls der Evolutionslehre entliehen ist, der
@@ -380,10 +399,15 @@ die Sortiereigenschaft erhalten. Transformationen von Sortiernetzwerken werden
 in Abschnitt~\ref{sect:tranformation} beschrieben, ein Algorithmus, der
 Mutation einsetzt, wird in Abschnitt~\ref{sect:sn-evolution-cut} vorgestellt.
 
-\begin{figure} \begin{center} \input{images/16-hillis.tex} \end{center}
-\caption{Das 16-Sortiernetzwerk, das \textit{Hillis} in~\cite{H1990} angibt.
-Es besteht aus 61~Komparatoren in 11~Schichten.} \label{fig:16-hillis}
-\end{figure} Evolutionäre Algorithmen wurden bereits mehrfach eingesetzt, um
+\begin{figure}
+  \begin{center}
+    \input{images/16-hillis.tex}
+  \end{center}
+  \caption{Das 16-Sortiernetzwerk, das \textit{Hillis} in~\cite{H1990} angibt.
+  Es besteht aus 61~Komparatoren in 11~Schichten.}
+  \label{fig:16-hillis}
+\end{figure}
+Evolutionäre Algorithmen wurden bereits mehrfach eingesetzt, um
 Sortiernetzwerke zu untersuchen. \textit{W.~Daniel Hillis} verwendete
 \emph{Co-Evolution} um neben Komparatornetzwerken auch „schwierige Eingaben“
 zu optimieren~\cite{H1990}. Diese \emph{Parasiten} genannten Eingaben wurden
@@ -394,6 +418,14 @@ Parasiten (schwierige Eingaben) überprüft werden. Auf diese Art und Weise
 gelang es \textit{Hillis} ein 16-Sortiernetzwerk mit 61~Komparatoren
 anzugeben, das in Abbildung~\ref{fig:16-hillis} zu sehen ist.
 
+\textit{Michael~L. Harrison} und \textit{James~A. Foster} nutzten ebenfalls
+\emph{Co-Evolution} in~\cite{HF2004}, um die Stabilität von Sortiernetzwerken
+zu erhöhen. Die zweite Population bestand aus \emph{Fehlern} -- der
+Information, welche Komparatoren defekt, beziehungsweise inaktiv sind. So
+generierte Sortiernetzwerke können auch dann noch für viele Eingaben eine
+korrekt sortierte Ausgabe erzeugen, wenn ein oder mehrere Komparatoren
+(zufällig) entfernt werden.
+
 \begin{figure}
   \centering
   \subfigure{\input{images/13-juille-0.tex}}
@@ -1299,7 +1331,9 @@ verschiedener Netzwerke kleiner, was die {\em Exploration}, das Absuchen des
 gesamten Lösungsraums, begünstigt. Wählt man $w_{\mathrm{Basis}}$ hingegen
 klein -- in Abhängigkeit von den anderen beiden Parametern sind auch negative
 Werte möglich -- werden die relativen Unterschiede groß. Dadurch wird die {\em
-Exploitation}, das Streben zu (lokalen) Optima, verstärkt.
+Exploitation}, das Streben zu (lokalen) Optima, verstärkt. In~\cite{WW2002}
+geben \textit{Karsten und Nicole Weicker} einen Überblick über
+Selektionsmethoden und Rekombinationsmöglichkeiten.
 
 Diese Parameter haben einen großen Einfluss auf die Geschwindigkeit, mit der
 der \textsc{SN-Evolution}-Algorithmus konvergiert und ob er tatsächlich gute