Erwähne die Arbeiten von Hillis und Juillé.

[diplomarbeit.git] / diplomarbeit.tex

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index 7273cbe..c090c39 100644 (file)
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -327,6 +327,47 @@ Sortiereigenschaft erhält. 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{H1992} 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{H1992}. Diese \emph{Parasiten} genannten Eingaben wurden
+daran gemessen, bei wievielen Komparatornetzwerken sie beweisen konnten, dass
+sie keine Sortiernetzwerke sind. So mussten bei neuen Individuen~/
+Komparatornetzwerken nicht alle 0-1-Folgen, sondern nur erfolgreiche
+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.
+
+\begin{figure}
+  \centering
+  \subfigure{\input{images/13-juille-0.tex}}
+  \subfigure{\input{images/13-juille-1.tex}}
+  \caption{13-Sortiernetzwerke, die von \textit{Hugues Juillé} mithilfe des
+  END-Algorithmus gefunden wurden. Sie bestehen jeweils aus 45~Komparatoren in
+  10~Schichten.}
+  \label{fig:13-juille}
+\end{figure}
+\textit{Hugues Juillé} entwickelte ein Verfahren, das er \emph{Evolving
+Non-Determinism} (END) nannte. Dabei handelt es sich nicht um einen
+\emph{Evolutionären Algorithmus}, wie sie hier vorgestellt wurden, sondern um
+eine verteilte, probabilistische Breitensuche, die an die \emph{Strahlsuche}
+(englisch: \textit{beam search}), ein Verfahren der Künstlichen Intelligenz,
+angelehnt ist. Die aufwendigste Operation bei diesem Ansatz ist die
+Bewertungsfunktion, die abschätzt, wieviele Komparatoren zu einem
+Komparatornetzwerk hinzugefügt werden müssen, um ein Sortiernetzwerk zu
+erhalten. Mit diesem Ansatz gelang es \textit{Juillé} zwei 13-Sortiernetzwerke
+anzugeben, die mit 45~Komparatoren effizienter sind als alle bis dahin
+Bekannten (Abbildung~\ref{fig:13-juille}).
+
 \newpage
 \section{Bekannte konstruktive Sortiernetzwerke}
 \label{sect:konstruktive_netzwerke}