\maketitle
\begin{abstract}
-\todo{Einleitung schreiben.}
-
-Sortiernetzwerke werden eingeführt und einige bekannte Konstruktionen werden
-vorgestellt (Odd-Even-Transposition, Bitonic-Merge, Odd-Even-Merge, Pairwise).
-Transformationsmöglichkeiten für Sortiernetzwerke werden besprochen.
-Evolutionäre Algorithmen werden beschrieben und ein evolutionärer
-Algorithmus für die Optimierung von Sortiernetzwerken wird angegeben.
-Die mindestens von diesem Algorithmus erreichte Güte wird angegeben und die
-Transformation zu einer Markov-Kette wird gezeigt. {\em Natürlich: So fern ich
-das hin bekomme bzw. Recht behalte.}
+Sortiernetzwerke erweisen sich als sehr schwieriges Optimierungsproblem. Zwar
+ist das Konzept leicht verständlich und schnell erklärt, effiziente und
+schnelle Sortiernetzwerke zu finden oder zu konstruieren bleibt aber eine
+Herausforderung.
+
+Diese Arbeit verwendet „Schnitte“ oder „Leitungselimination“ und
+Mischer-Netzwerke, um evolutionäre Algorithmen anzugeben, deren Individuen die
+Menge der gültigen Sortiernetzwerke nie verlassen. Bisherige Ansätze bewegten
+sich in der Regel in der Menge aller Komparatornetzwerke und suchten dort nach
+Sortiernetzwerken. Nach dem Vorstellen der zwei Algorithmen
+\textsc{SN-Evolution} und \textsc{SN-Evolution-Cut} sowie einiger Ergebnisse,
+die diese Algorithmen erzielen konnten, wird -- basierend auf dem
+evolutionären Algorithmus \textsc{SN-Evolution} -- eine Markov-Kette für
+Sortiernetzwerke angegeben.
\end{abstract}
\newpage
Konstruktionsvorschrift genutzt werden kann um die Korrektheit für beliebige
Eingabegrößen zu beweisen. Im Abschnitt~\ref{sect:konstruktive_netzwerke}
geschieht dies beispielsweise für zwei von \emph{Kenneth~E. Batcher} 1968
-gefundenen Konstruktionsvorschriften.
+gefundene Konstruktionsvorschriften.
-Um effiziente und schnelle Sortiernetzwerke zu finden, wurden schon früh
+Um effiziente und schnelle Sortiernetzwerke zu finden, wurden schon wiederholt
Computer und automatische Suchverfahren eingesetzt. Bisherige Ansätze
versuchen meist, in der Menge aller Komparatornetzwerke jene zu finden, die
die Sortiereigenschaft besitzen und aus wenigen Komparatoren bestehen. Die
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}
Bekannten (Abbildung~\ref{fig:13-juille}).
\newpage
-\section{Bekannte konstruktive Sortiernetzwerke}
+\section[Konstruktionsverfahren]{Bekannte konstruktive Sortiernetzwerke}
\label{sect:konstruktive_netzwerke}
-Übersicht über bekannte konstruktive Sortiernetzwerke.
-
-\todo{Einleitungssatz}
+Die bekannten Konstruktionsverfahren für Sortiernetzwerke, insbesondere
+sogenannte \emph{Mischer}, bilden die Grundlage für die beschriebenen
+evolutionären Algorithmen beziehungsweise dienen als initiale Eingabe. Im
+Folgenden werden daher drei Konstruktionsverfahren vorgestellt.
\subsection{Das Odd-Even-Transpositionsort-Netzwerk}
\label{sect:odd_even_transpositionsort}
finden. Häufig dient $\operatorname{OET}(n)$ als Eingabe für diese
Algorithmen.
+Außerdem bedienen sich die Algorithmen der Technik des Herausschneidens einer
+beziehungsweise mehrerer Leitungen, um die Anzahl der Leitungen eines
+Sortiernetzwerks zu reduzieren. Die Technik wird in Detail im
+Abschnitt~\ref{sect:leitungen_entfernen} beschrieben.
+
\subsection{Das bitone Mergesort-Netzwerk}
Das \emph{bitone Mergesort}-Netzwerk ($\operatorname{BS}(n)$) ist ein
w_{\mathrm{Schichten}} &=& \left|S\right|_\mathrm{Leitungen}
\end{eqnarray*}
-\subsection{Versuche mit dem bitonen Mischer}
+\subsection[Bitoner Mischer]{Versuche mit dem bitonen Mischer}
\begin{figure}
\begin{center}
das Sortiernetzwerk in Abbildung~\ref{fig:16-e1-bitonic-1296542566} benötigt
lediglich~67.
-\subsection{Versuche mit dem \emph{Odd-Even}-Mischer}
+\subsection[Odd-Even-Mischer]{Versuche mit dem Odd-Even-Mischer}
\begin{figure}
\begin{center}
in Abschnitt~\ref{sect:anzahl_schnittmuster} definiert wurden, als Individuen.
Um zwei Individuen zu rekombinieren werden die ersten $r$~Schnitte des einen
Schnittmusters verwendet und die letzten ${c-r}$~Schnitte des zweiten
-Schmittmusters. $r$ ist eine Zufallsvariable mit $0 \leqq r \leqq c$.
+Schnittmusters. $r$ ist eine Zufallsvariable mit $0 \leqq r \leqq c$.
Die Mutation setzt entweder die Leitungsnummer eines Schnitts~$i$ zufällig auf
einen neuen Wert $l$ mit $0 \leqq l \le n-i$ oder invertiert die
untersucht \textit{Moritz Mühlenthaler} ausführlich in~\cite{M2009}.
\subsection{Versuche mit dem Odd-Even-Mergesort-Netzwerk}
+\label{sect:sn-evolution-cut:oes}
In Abschnitt~\ref{sect:anzahl_schnittmuster} wurde bereits untersucht, wie
viele \emph{unterschiedliche} Schnittmuster die konstruktiven Sortiernetzwerke
\textsc{SN-Evolution-Cut} generiert werden können, charakterisiert. Die
Eingabe für \textsc{SN-Evolution-Cut} war jeweils das
\emph{Odd-Even-Mergesort}-Netzwerk mit der doppelten Leitungszahl.
-Abbildung~\ref{fig:23-ec-from-oes46} zeigt beispielhaft ein
-23-Sortiernetzwerk, das aus \oes{46} generiert wurde.
\begin{center}
\begin{tabular}{|r|r|r|r|r|}
\hline
Leitungen & Komparatoren & Schichten & Komparatoren & Schichten \\
-(Resultat) & \textsc{SN-EC} & \textsc{SN-EC} & \oes{n} & \oes{n} \\
+ & \textsc{SN-EC} & \textsc{SN-EC} & \oes{n} & \oes{n} \\
\hline
11 & 38 & 9 & 37 & 10 \\
12 & 43 & 9 & 41 & 10 \\
\hline
\end{tabular}
\end{center}
+Abbildung~\ref{fig:23-ec-from-oes46} zeigt beispielhaft ein
+23-Sortiernetzwerk, das aus \oes{46} generiert wurde. Bemerkenswert an diesem
+Sortiernetzwerk ist insbesondere, dass \textsc{SN-Evolution-Cut} mit der
+Eingabe \bs{46} ein besseres Ergebnis liefert als mit der Eingabe \oes{46}. In
+beiden Fällen wird ein Sortiernetzwerk zurückgegeben, das im Vergleich zu
+\bs{23} beziehungsweise \oes{23} eine Schicht einspart. Allerdings ist das
+Sortiernetzwerk auf Basis von \bs{46} (Abbildung~\ref{fig:23-ec-from-bs46})
+effizienter, da es nur 124~Komparatoren benötigt.
\begin{figure}
\begin{center}
jedoch, dass in dieser Konfiguration Sortiernetzwerke auftreten können, die
mehr Komparatoren besitzen als \emph{Odd-Even-Transpositionsort} -- \oet{16}
ist aus 120~Komparatoren aufgebaut, bei dem Lauf, der die Daten für
-Abbildung~\ref{fig:comparison-comparators} lieferte, traten auch jeweils ein
+Abbildung~\ref{fig:comparison-comparators} lieferte, trat auch jeweils ein
Sortiernetzwerk mit 121 und 124~Komparatoren auf. Da Sortiernetzwerke mit so
vielen Komparatoren im Verlauf des Experiments selbst nach über 100~Millionen
Iterationen nicht noch einmal erzeugt wurden, handelt es sich vermutlich um
% \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.
- \item \textsc{SN-Count-Markov} (ggf)
-\end{itemize}
-
\newpage
\section{Fazit und Ausblick}
-\todo{Ausformulieren}
-\begin{itemize}
-\item Mit \textsc{SN-Evolution} und \oem{n} kann man nicht besser werden als
- \oes{n}.
-\item Mit \textsc{SN-Evolution} und \bm{n} kann man besser werden als \bs{n}.
-\item Vermutlich kann man mit \textsc{SN-Evolution} und \bm{n} so gut werden
-wie \textsc{SN-Evolution-Cut}, wenn er mit \bs{2n} gestartet wird.
-\item Leider sind keine konstruktiven Methoden erkannt worden.
-\end{itemize}
+Dass sich mithilfe dem Entfernen von Leitungen aus bekannten Sortiernetzwerke
+interessante Ergebnisse erzielen lassen, zeige \textit{Moritz Mühlenthaler}
+bereits in~\cite{M2009}. Die in dieser Arbeit vorgestellten Methoden und
+Resultate machen deutlich, dass sich mit diesem Verfahren noch weitere
+interessante Beobachtungen machen lassen.
+
+Das \emph{Odd-Even-Mergesort}-Netzwerk wird sowohl von \textsc{SN-Evolution},
+\textsc{SN-Evolution-Cut} und \textsc{SN-Markov} erreicht. Wenn die Anzahl der
+Leitungen keine Zweierpotenz ist, kann gegebenenfalls ein schnelleres
+Sortiernetzwerk erzeugt werden. Einige Beispiele hierfür wurden in
+Abschnitt~\ref{sect:sn-evolution-cut:oes} aufgezeigt.
+
+Das \emph{bitone Mergesort}-Netzwerk kann in Bezug auf Effizienz von den
+vorgestellten Algorithmen übertroffen werden. Der Algorithmus
+\textsc{SN-Evolution-Cut} kann das Ergebnis von \textit{Mühlenthaler} und
+\textit{Wanka} (\cite{MW2010}) für ein 16-Sortiernetzwerk reproduzieren und
+für ein 32-Sortiernetzwerk sogar noch übertreffen. Der
+\textsc{SN-Evolution}-Algorithmus fand ein 16-Sortiernetzwerk, das gegenüber
+dem Ergebnis von \textsc{SN-Evolution-Cut} beziehungsweise~\cite{MW2010} einen
+weiteren Komparator einspart.
+
+Leider weisen die Sortiernetzwerke, die von den angegebenen Algorithmen
+zurückgegeben werden, keine Struktur auf, die sich zur Angabe einer
+Konstruktionsanweisung eigenen würde. Für das \emph{Pairwise-Sorting}- und das
+\emph{Odd-Even-Mergesort}-Netzwerk mit Zweierpotenzen als Leitungszahl wurden
+regelmäßige Schnittmuster angegeben, die Sortiernetzwerke ergeben, die so
+schnell und effizient sind wie die vergleichbaren \oes{n} und \ps{n}
+Netzwerke.
+
+Die Anzahl der \emph{unterschiedlichen} Schnitte von verschiedenen
+Sortiernetzwerken wurde experimentell bestimmt und gezeigt, dass es deutlich
+weniger \emph{unterschiedliche} als \emph{mögliche} Schnittmuster gibt. Das
+bedeutet im Umkehrschluss, dass die gewonnenen Sortiernetzwerke mit mehreren
+unterschiedlichen Schnittmustern erreicht werden können.
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.
+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{Ausblick: Das \textit{Pairwise-Sorting}-Netzwerk und \textsc{SN-Evolution}}
erwiesen.
Funktionen, die von Kommandozeilen-Programmen zur Verfügung gestellt werden,
-sind unter anderem das Erzeugen von Odd-Even-Mergesort-, bitonic Mergesort-
-und Pairwise-Sorting-Netzwerken, das Normalisieren von Sortiernetzwerken,
-Anwendung von Schnittmustern auf Sortiernetzwerke und Anwendung eines
-Komparatornetzwerks auf eine Eingabe-Permutation.
+sind unter anderem das Erzeugen des \emph{Odd-Even-Mergesort}-, \emph{bitonen
+Mergesort}- und \emph{Pairwise-Sorting}-Netzwerks, das Normalisieren von
+Sortiernetzwerken, Anwendung von Schnittmustern auf Sortiernetzwerke und
+Anwendung eines Komparatornetzwerks auf eine Eingabepermutation. Das
+Darstellen von Sortiernetzwerken wird ebenfalls angeboten, beispielsweise
+wurden die Sortiernetzwerke in dieser Arbeit mit dem Kommando \texttt{sn-tex}
+visualisiert.
\textit{libsortnetwork} kann unter der Web-Adresse
\url{http://octo.it/libsortnetwork/} unentgeltlich heruntergeladen werden.
projects / diplomarbeit.git / commitdiff