\subsection{Motivation}\label{sect:motivation}
+\todo{Schreibe noch etwas zu …}
\begin{itemize}
\item Sortiernetzwerke sind toll, weil $\ldots$
\item Sortiernetzwerke sind einfach erklärt, aber trotzdem kompliziert.
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}
Übersicht über bekannte konstruktive Sortiernetzwerke.
+\todo{Einleitungssatz}
+
\subsection{Das Odd-Even-Transpositionsort-Netzwerk}
\label{sect:odd_even_transpositionsort}
Komparatoren, die in $\frac{1}{2} \log(n) \log(n+1) = \mathcal{O}(\log(n))$
Schichten angeordnet sind.
-%\begin{figure}
-%\begin{center}
-%\includegraphics[viewport=115 491 372 782,width=7.5cm]{images/sn-rekursiver-aufbau.pdf}
-%\end{center}
-%\caption{Rekursiver Aufbau von $S(n)$: Es besteht aus zwei Instanzen von
-%$S(n/2)$ und dem Mischer $M(n)$.}
-%\label{fig:bms_rekursiver_aufbau}
-%\end{figure}
-
\subsection{Das Odd-Even-Mergesort-Netzwerk}
Obwohl der Name ähnlich klingt, haben das \emph{Odd-Even-Mergesort-Netzwerk}
Sorting Network for 18~Elements“~\cite{BB2009} vorstellen, benötigt aber
6~Komparatoren weniger.
-% 9 9
-% 9 18
-% 9 27
-% 9 36
-% 9 45
-% 8 53
-% 8 61
-% 7 68
-% 7 75
-% 6 81
-% 5 86
-
Das Zusammenfassen von zwei Sortiernetzwerken durch Hintereinanderausführung
ist nicht sinnvoll: Da die Ausgabe des ersten Sortiernetzwerks bereits
sortiert ist, ist das zweite Sortiernetzwerk überflüssig. Eine
Komparatornetzwerks müsste überprüft werden, was nach heutigem Wissensstand
nur mit exponentiellem Aufwand möglich ist.
-%\begin{itemize}
-%\item Mit dem Bitonic-Merge
-%\item Mit dem Odd-Even-Merge
-%\item Nach dem Pairwise sorting-network Schema.
-%\end{itemize}
-
\subsection{Leitungen entfernen}
\label{sect:leitungen_entfernen}
\newpage
\section{Der \textsc{SN-Evolution}-Algorithmus}
+\label{sect:sn-evolution}
Der \textsc{SN-Evolution}-Algorithmus ist ein \emph{evolutionärer
Algorithmus}, der die in den vorherigen Abschnitten beschriebenen Mischer
für jedes Individuum in Population
{
reziproke Güte := 1.0 / Guete(Individuum)
- Wahrscheinlichkeit P := reziproke Güte / (reziproke Güte + Gütesumme)
+ Wahrscheinlichkeit P := reziproke Güte / (Gütesumme + reziproke Güte)
Gütesumme := Gütesumme + reziproke Güte
mit Wahrscheinlichkeit P
$\operatorname{OES}(n)$ in mindestens einem Merkmal übertrifft, konnte jedoch
nicht beobachtet werden.
-\begin{itemize}
-\item Güte von Sortiernetzwerken (Anzahl der Komparatoren, Anzahl der Schichten, kombiniert)
-\item Wie gut die Netzwerke werden, hängt stark vom verwendeten \emph{Mischer} ab.
-\item Ggf. Abschnitt „Shmoo-Äquivalenz“ kürzen und hier einbauen.
-\item Möglicherweise: Verwende den rekursiven Aufbau des \emph{Pairwise-Sorting}-Netzwerks um Sortiernetzwerke zu mergen.
-\end{itemize}
+\todo{Ggf. Abschnitt „Shmoo-Äquivalenz“ kürzen und hier einbauen.}
%\begin{figure}
%\begin{center}
$\operatorname{OES}(32)$ sehr schnell ein gutes 16-Schnittmuster findet.
Eines der eher zufälligen Schnittmuster ist $\operatorname{MIN}(1, 6, 11, 14,
-17, 23, 26, 29)$, $\operatorname{MAX}(2, 7, 8, 13, 18, 21, 27, 31)$. Das
+17, 23, 26, 29)$, $\operatorname{MAX}(2, 7, 8,$ $13, 18, 21, 27, 31)$. Das
Schnittmuster ist in Abbildung~\ref{fig:16-ec-from-oes32-cut} veranschaulicht,
das resultierende Netzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32} zu sehen.
Wie in Abschnitt~\ref{sect:anzahl_schnittmuster} beschrieben, ist die Anzahl
der \emph{unterschiedlichen} Schnittmuster und damit die Anzahl der Nachfolger
sehr groß. Bei den untersuchten 16-Sortiernetzwerken lag die Anzahl der
-Nachfolger zwar noch unter 20000, bei den untersuchten 32-Sortiernetzwerken
+Nachfolger zwar noch unter 20.000, bei den untersuchten 32-Sortiernetzwerken
wurden jedoch bereits bis zu $2,6 \cdot 10^8$ unterschiedliche Schnittmuster
geschätzt.
gib Netzwerk zurück
\end{verbatim}
+Die Abbildungen~\ref{fig:markov-comparators-12},
+\ref{fig:markov-comparators-14}, \ref{fig:markov-comparators-12},
+\ref{fig:markov-comparators-16} und~\ref{fig:markov-comparators-18} zeigen die
+Anzahl der Komparatoren der Sortiernetzwerke, die \textsc{SN-Markov} auf
+seinem zufälligen Pfad durchläuft. Ausserdem eingezeichnet ist eine
+\emph{Gamma-Verteilung}.
+
\begin{figure}
\begin{center}
\includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-cycles-16.pdf}
\label{fig:markov-cycles-16}
\end{figure}
-
+\todo{Schreibe noch etwas zu …}
\begin{itemize}
\item Beste erreichte Netzwerke (gleich zu \emph{OE-Mergesort}).
\item Anzahl der erreichbaren Sortiernetzwerke.
\end{figure}
\newpage
-\section{Empirische Beobachtungen}
-
-\begin{itemize}
-\item So schnell konvergiert der Algorithmus.
-\item $\ldots$
-\end{itemize}
-
-\newpage
\section{Ausblick}
-Das würde mir noch einfallen$\ldots$
-
-- SN-Evolution mit Pairwise als „Mischer“.
-- Co-Evolution von Netzwerken und Schnittmustern.
+Die Möglichkeiten, die Evolutionäre Algorithmen bei der Optimierung von
+Sortiernetzwerken bieten, sind durch die in dieser Arbeit vorgestellten
+Herangehensweisen bei weitem nicht erschöpft.
+
+Im Folgenden werden Ansätze umrissen, mit denen an die Untersuchungen in
+dieser Arbeit nahtlos angeknöpft werden könnte.
+
+\subsection{Verwendung des Pairwise-Sorting-Netzwerk in \textsc{SN-Evolution}}
+
+Die aktuelle Implementierung von \textsc{SN-Evolution}
+(Abschnitt~\ref{sect:sn-evolution}) kann sowohl den \emph{bitonen Mischer} als
+auch den \emph{Odd-Even-Mischer} verwenden, um zwei Individuen zu
+rekombinieren. Das \emph{Pairwise-Sorting}-Netzwerk verwendet zwar keinen
+Mischer, es ist aber ebenfalls rekursiv über kleinere Versionen von sich
+selbst definiert. Das heißt, dass \ps{n} aus zwei Instanzen von
+$\ps{\frac{n}{2}}$ und zusätzlichen Komparatoren besteht, die die Eingabe für
+die kleineren Sortiernetzwerke vorbereiten und anschließend für eine sortierte
+Ausgaben sorgen. Anstelle von $\ps{\frac{n}{2}}$ kann man natürlich beliebige
+Sortiernetzwerke mit $\frac{n}{2}$~Leitungen verwenden.
+
+Dies ließe sich für \textsc{SN-Evolution} nutzen, um zwei Individuen zu
+rekombinieren. Da es für das \emph{Pairwise-Sorting}-Netzwerk sehr viele
+\emph{unterscheidliche} Schnittmuster gibt
+(Abbschnitt~\ref{sect:anzahl_schnittmuster}), ist es möglich, dass die
+Verwendung dieser Rekombinationsmethode neue Ergebnisse ermöglicht. Leider
+wird die Aussicht auf Erfolg durch die Tatsache geschmälert, dass keine
+$n$-Schnittmuster für \ps{2n} gefunden werden konnten, die zu besseren
+$n$-Sortiernetzwerken als \ps{n} führen.
+
+\subsection{Kooperation von \textsc{SN-Evolution} und
+\textsc{SN-Evolution-Cut}}
+
+Ähnlich zu der parasitären \emph{Co-Evolution}, die \textit{W.~Daniel Hillis}
+in~\cite{H1992} beschreibt, könnte man die Algorithmen \textsc{SN-Evolution}
+und \textsc{SN-Evolution-Cut} versuchen zu kombinieren. Nach dem Zusammenfügen
+von zwei $n$-Sortiernetzwerken könnte der Algorithmus
+\textsc{SN-Evolution-Cut} beispielsweise einen möglichst guten Schnitt für
+\emph{dieses} Netzwerk ermitteln. Da sich die Lösungen, die Evolutionäre
+Algorithmen in ihre Population aufnehmen, in den ersten Schritten rasch
+verbessern, könnten selbst weniger Iterationen von \textsc{SN-Evolution-Cut}
+die Zwischenlösungen von \textsc{SN-Evolution} deutlich verbessern.
+
+Alternativ könnte man -- analog zur Herangehensweise von \textit{Hillis} --
+eine zweite Population von Schnittmustern evolvieren, die für die
+Sortiernetzwerke in der Population von \textsc{SN-Evolution} besonders gut
+funktionieren. In jeder Iteration wendet man alle oder eine zufällige Menge
+Schnittmuster auf das zusammengeführte Netzwerk an und gibt dem besten
+Ergebnis den Zuschlag. Anschließend erfährt das entsprechende Schnittmuster
+eine Aufwertung, so dass es wahrscheinlicher wird, dass \emph{dieses}
+Schnittmuster zur nächten Generation beiträgt. Im Gegensatz zum Ansatz der
+parasitären Eingaben entsteht eine \emph{Synergie} zweier Populationen, die
+das Gesamtergebnis oder zumindest die Konvergenzgeschwindigkeit verbessern
+könnte.
\newpage
\section{Implementierung}
projects / diplomarbeit.git / blobdiff