X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=8307d467dacae9d70742039cff6d6ab347df97cb;hb=84dd1bb22090e19e9f2d0fc9b77af0dd12bc589f;hp=c0213f2c4b4596093891772c68de0885916bc83c;hpb=c145acd32aa61c8e213cd1a15ccf79bf30563a5e;p=diplomarbeit.git diff --git a/diplomarbeit.tex b/diplomarbeit.tex index c0213f2..8307d46 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -36,6 +36,12 @@ \newcommand{\todo}[1]{{\bf TODO:} #1} \newcommand{\qed}{\hfill $\Box$ \par \bigskip} +\newcommand{\oes}[1]{\ensuremath{\operatorname{OES}(#1)}} +\newcommand{\bs}[1]{\ensuremath{\operatorname{BS}(#1)}} +\newcommand{\ps}[1]{\ensuremath{\operatorname{PS}(#1)}} +\newcommand{\oem}[1]{\ensuremath{\operatorname{OEM}(#1)}} +\newcommand{\bm}[1]{\ensuremath{\operatorname{BM}(#1)}} + \newtheorem{definition}{Definition} \newtheorem{satz}{Satz} @@ -92,6 +98,7 @@ das hinbekomme bzw. Recht behalte.} \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. @@ -321,12 +328,55 @@ 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} Übersicht über bekannte konstruktive Sortiernetzwerke. +\todo{Einleitungssatz} + \subsection{Das Odd-Even-Transpositionsort-Netzwerk} \label{sect:odd_even_transpositionsort} @@ -853,18 +903,6 @@ Al-Haj Baddar} und \textit{Kenneth~E. Batcher} in ihrer Arbeit „An 11-Step 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 @@ -874,12 +912,6 @@ die Sortiereigenschaft. Die Sortiereigenschaft des resultierenden 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} @@ -973,7 +1005,7 @@ auch das Maximum angenommen werden. Wendet man das Verfahren iterativ an, um ein $n$-Sortiernetzwerk auf ein ${(n-k)}$-Sortiernetzwerk zu reduzieren, ergeben sich insgesamt \begin{equation}\label{eqn:anzahl_schnittmuster} - \prod_{i=n}^{1+n-k} 2i = 2^k \frac{n!}{(n-k)!} + \prod_{i=n}^{1+n-k} 2i = 2^k \cdot \frac{n!}{(n-k)!} \quad (n > m) \end{equation} \emph{mögliche} Schnittmuster. Diese Schnittmuster sind nicht alle @@ -1037,13 +1069,12 @@ Alleine durch Betrachten der ersten Schicht von Komparatoren konnte die Anzahl der \emph{unterschiedlichen} Schnittmuster auf höchstens $\frac{2}{3}$ der \emph{möglichen} Schnittmuster reduziert werden. Um die Anzahl der \emph{unterschiedlichen} Schnittmuster experimentell zu ermitteln, wurden je -eine Million zufällige 8-Schnittmuster auf die 16-Sortiernetzwerke -$\operatorname{OES}(16)$, $\operatorname{BS}(16)$ und $\operatorname{PS}(16)$ -angewandt. Anschließend wurde mithilfe einer Hashtabelle überprüft, ob das -resultierende Sortiernetzwerk schon von einem \emph{äquivalenten} -Schnittmuster erzeugt wurde. Falls das Sortiernetzwerk noch nicht in der -Hashtabelle enthalten war, wurde der Zähler für unterschiedliche Schnittmuster -erhöht und das Sortiernetzwerk eingefügt. +eine Million zufällige 8-Schnittmuster auf die 16-Sortiernetzwerke \oes{16}, +\bs{16} und \ps{16} angewandt. Anschließend wurde mithilfe einer Hashtabelle +überprüft, ob das resultierende Sortiernetzwerk schon von einem +\emph{äquivalenten} Schnittmuster erzeugt wurde. Falls das Sortiernetzwerk +noch nicht in der Hashtabelle enthalten war, wurde der Zähler für +unterschiedliche Schnittmuster erhöht und das Sortiernetzwerk eingefügt. Abbildung~\ref{fig:count-cuts-16} trägt die Anzahl der \emph{unterschiedlichen} Schnittmuster gegen die Anzahl der zufälligen @@ -1053,29 +1084,30 @@ Wert nach $1.000.000$~Iterationen allem Anschein nach dem Endwert schon sehr nahe ist. Die Anzahl der möglichen 8-Schnittmuster ist entsprechend der -Formel~\ref{eqn:anzahl_schnittmuster} 3.294.720. Diese möglichen Schnittmuster -führen aber nur zu wenigen \emph{unterschiedlichen} Sortiernetzwerken: 3519 -($\approx 0,1\%$) im Fall des \emph{Odd-Even-Mergesort-Netzwerks}, 4973 -($\approx 0,15\%$) beim \emph{bitonen Mergesort-Netzwerk} und 18764 ($\approx -0,57\%$) beim \emph{Pairwise-Sorting-Netzwerk}. Zwar ist es möglich, dass mehr -Iterationen die Anzahl der unterschiedlichen Schnittmuster noch wachsen lässt. -Die Graphen in Abbildung~\ref{fig:count-cuts-16} geben jedoch Grund zu der -Annahme, dass die Anzahl dieser zusätzlichen, unterschiedlichen Schnittmuster +Formel~\eqref{eqn:anzahl_schnittmuster} 3.294.720. Diese möglichen +Schnittmuster führen aber nur zu wenigen \emph{unterschiedlichen} +Sortiernetzwerken: 3519 ($\approx 0,1\%$) im Fall des +\emph{Odd-Even-Mergesort-Netzwerks}, 4973 ($\approx 0,15\%$) beim +\emph{bitonen Mergesort-Netzwerk} und 18764 ($\approx 0,57\%$) beim +\emph{Pairwise-Sorting-Netzwerk}. Zwar ist es möglich, dass mehr Iterationen +die Anzahl der unterschiedlichen Schnittmuster noch wachsen lässt. Die Graphen +in Abbildung~\ref{fig:count-cuts-16} geben jedoch Grund zu der Annahme, dass +die Anzahl dieser zusätzlichen, unterschiedlichen Schnittmuster vernachlässigbar klein ist. Bedingt durch die sehr große Anzahl möglicher Schnittmuster ist dieses Experiment für größere Sortiernetzwerke leider nicht sinnvoll durchführbar. -Die Hashtabelle benötigt mehr Arbeitsspeicher als in derzeitigen Rechnern -vorhanden ist, bevor ein entsprechender Graph den linearen Bereich für -„kleine“ x-Werte verlässt. +Die Hashtabelle würde mehr Arbeitsspeicher benötigen als in derzeitigen +Rechnern vorhanden ist, bevor ein entsprechender Graph den linearen Bereich +für „kleine“ x-Werte verlässt. Um die Anzahl der unterschiedlichen Schnittmuster trotzdem abschätzen zu können, kann man sich einer stochastischen Methode bedienen, der sogenannten \emph{Monte-Carlo-Methode}. Zunächst generiert man eine Menge~$S$ von $k$~unterschiedlichen Schnittmustern. Anschließend werden $n$~Schnittmuster -zufällig erzeugt und überprüft, ob sie sich in der Menge~$S$ enthalten sind. -Unter der Annahme, dass das Verhältnis der zufälligen Schnittmuster, die in -$S$ enthalten sind, und $n$ dem Verhältnis von $k$ und der Anzahl der +zufällig erzeugt und überprüft, ob sie in der Menge~$S$ enthalten sind. Unter +der Annahme, dass das Verhältnis der zufälligen Schnittmuster, die in $S$ +enthalten sind, und $n$ dem Verhältnis von $k$ und der Anzahl der unterschiedlichen Schnittmuster ingesamt entspricht, kann man die Anzahl der unterschiedlichen Schnittmuster abschätzen. @@ -1098,8 +1130,8 @@ zufällige Schnittmuster erzeugt und der Anteil der zufälligen Schnittmuster, die \emph{äquivalent} zu einem in~$S$ enthalten Schnittmuster sind, berechnet. Für $\operatorname{OES}(32)$ war dieser Anteil etwa $0,19 \%$, für $\operatorname{BS}(32)$ etwa $0,29 \%$. Das ergibt eine Abschätzung von $5,2 -\cdot 10^6$ unterschiedlichen Schnittmustern für $\operatorname{OES}(32)$ und -$3,4 \cdot 10^6$ für $\operatorname{BS}(32)$. +\cdot 10^6$ unterschiedlichen 16-Schnittmustern für $\operatorname{OES}(32)$ +und $3,4 \cdot 10^6$ für $\operatorname{BS}(32)$. \begin{figure} \begin{center} @@ -1120,9 +1152,9 @@ $\operatorname{BS}(32)$. In Anbetracht der Tatsache, dass die Anzahl der unterschiedlichen 8-Schnittmuster für $\operatorname{PS}(16)$ in Abbildung~\ref{fig:count-cuts-16} bereits mehr als dreimal größer war als die Anzahl für $\operatorname{OES}(16)$ beziehungsweise $\operatorname{BS}(16)$, -ist dieser Umstand wenig verwunderlich. In einem kombinierten Graphen hätte -man keine Details mehr erkennen können. Aufgrund der hohen Anzahl -unterschiedlicher Schnittmuster, wurde für das gleiche Experiment mit +ist dieser Umstand wenig verwunderlich. Entsprechend hätte man in einem +kombinierten Graphen keine Details mehr erkennen können. Aufgrund der hohen +Anzahl unterschiedlicher Schnittmuster, wurde für das gleiche Experiment mit $\operatorname{PS}(32)$ eine initiale Menge von 100.000 unterschiedilchen Schnittmustern erzeugt. Trotzdem wurden nach 1.000.000 Iterationen nur 385 Schnittmuster gefunden, die zu einem Schnittmuster in der Menge äquivalent @@ -1210,7 +1242,7 @@ Auswahl := (leer) 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 @@ -1238,7 +1270,7 @@ erhält. Zu einem vollständigen evolutionären Algorithmus gehört außerdem die Mutation --~eine zufällige Veränderung einer Lösung. Leider ist es nicht möglich ein -Sortiernetzwerk zufällig zu verändern aber trotzdem die Sortiereigenschaft zu +Sortiernetzwerk zufällig zu verändern und dabei die Sortiereigenschaft zu erhalten. Selbst das \emph{Hinzufügen} eines zufälligen Komparators kann diese Eigenschaft zerstören. @@ -1248,69 +1280,111 @@ Sortiereigenschaft noch besitzt. Nach heutigem Wissenstand ist diese Ausprobieren aller $2^n$~Bitmuster, wie in Abschnitt~\ref{sect:0-1-prinzip} beschrieben. -Um das Potenzial einer Mutation abzuschätzen habe ich in den evolutionären -Algorithmus eine Überprüfung eingebaut. Unmittelbar vor dem Einfügen in die -Population überprüft das Programm die Notwendigkeit jedes einzelnen -Komparators. Dazu wurde nacheinander jeder Komparator entfernt und überprüft, -ob das verbleibende Netzwerk die Sortiereigenschaft noch besitzt. +Um das Potenzial einer Mutation abzuschätzen wurde in \textsc{SN-Evolution} +eine Überprüfung eingebaut: Unmittelbar vor dem Einfügen in die Population +überprüft eine Funktion die Notwendigkeit jedes einzelnen Komparators. Dazu +wird nacheinander jeder Komparator entfernt und überprüft, ob das verbleibende +Netzwerk die Sortiereigenschaft noch besitzt. -\begin{itemize} -\item Güte von Sortiernetzwerken (Anzahl der Komparatoren, Anzahl der -Schichten, kobiniert) -\item Rekombination: Merge Anhängen und Leitungen entfernen. -\end{itemize} +Trotz des hohen Rechenaufwandes -- bei 16-Sortiernetzwerken sind gut +4~Millionen Tests notwendig, um alle Komparatoren zu überprüfen -- waren die +Ergebnisse ernüchternd: Nach circa 1~Million Iterationen mit +16-Sortiernetzwerken fand der so modifizierte Algorithmus keinen einzigen +Komparator, den er hätte entfernen können. -Ein Beispielnetzwerk, das von dem Algorithmus gefunden wird, zeigt -Abbildung~\ref{fig:evolutionary_08}. +\subsection{Güte} -\begin{figure} -\begin{center} -\input{images/evolutionary-08.tex} -\end{center} -\caption{Ein mit dem evolutionären Algorithmus erzeugtes Sortiernetzwerk mit -acht Eingängen. Es besteht aus 19~Komparatoren in 6~Schichten.} -\label{fig:evolutionary_08} -\end{figure} +Die Qualität der erreichten Sortiernetzwerke wurde mit eine Gütefunktion +beurteilt, die entsprechend dem im Abschnitt~\ref{sect:bewertung} +vorgestellten Muster definiert ist. Wie beschrieben müssen die Faktoren häufig +an die aktuelle Problemgröße angepasst werden, damit \textsc{SN-Evolution} +schnell gute Ergebnisse liefert. Als guter Standardansatz haben sich die +folgenden Werte herausgestellt: +\begin{eqnarray*} +w_{\mathrm{Basis}} &=& 0 \\ +w_{\mathrm{Komparatoren}} &=& 1 \\ +w_{\mathrm{Schichten}} &=& \left|S\right|_\mathrm{Leitungen} +\end{eqnarray*} -\begin{figure} -\begin{center} -\input{images/08-e2-1237993371.tex} -\end{center} -\caption{{\tt images/08-e2-1237993371.tex}: 19~Komparatoren in 6~Schichten} -\label{fig:08-e2-1237993371} -\end{figure} +\subsection{Versuche mit dem bitonen Mischer} \begin{figure} -\begin{center} -\input{images/09-e2-1237997073.tex} -\end{center} -\caption{{\tt images/09-e2-1237997073.tex}: 25~Komparatoren in 8~Schichten} -\label{fig:09-e2-1237997073} + \begin{center} + \input{images/16-e1-bitonic-1296542566.tex} + \end{center} + \caption{Sortiernetzwerk mit 16~Leitungen und 67~Komparatoren in + 10~Schichten. Das Netzwerk wurde von dem Algorithmus + \textsc{SN-Evolution} unter Verwendung des \emph{bitonen Mischers} + erzeugt.} + \label{fig:16-e1-bitonic-1296542566} \end{figure} -\begin{figure} -\begin{center} -\input{images/09-e2-1237999719.tex} -\end{center} -\caption{{\tt images/09-e2-1237999719.tex}: 25~Komparatoren in 7~Schichten} -\label{fig:09-e2-1237999719} -\end{figure} +Verwendet man den \emph{bitonen Mischer} in der Rekombinationsphase von +\textsc{SN-Evolution}, so erhält man Netzwerke wie das in +Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte: Der Algorithmus +wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk als triviale +Initiallösung gestartet. Das Ergebnis ist ein Netzwerk, das effizienter ist +als das bitone Mergesort-Netzwerk: $\operatorname{BS}(16)$ benötigt +80~Komparatoren, das Sortiernetzwerk in +Abbildung~\ref{fig:16-e1-bitonic-1296542566} benötigt lediglich~67. + +\subsection{Versuche mit dem Odd-Even-Mischer} \begin{figure} -\begin{center} -\input{images/10-e2-1239014566.tex} -\end{center} -\caption{{\tt images/10-e2-1239014566.tex}: 29~Komparatoren in 8~Schichten} -\label{fig:10-e2-1239014566} + \begin{center} + \input{images/16-e1-oddeven-1296543330.tex} + \end{center} + \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in + 10~Schichten. Das Netzwerk wurde von dem Algorithmus + \textsc{SN-Evolution} unter Verwendung des \emph{Odd-Even-Mischers} + erzeugt.} + \label{fig:16-e1-oddeven-1296543330} \end{figure} -\subsection{Güte} +Leider lies sich das Ergebnis des bitonen Mischers -- das von +\textsc{SN-Evolution} ausgegebene Netzwerk war effizienter als das rekursiv +aus dem verwendeten Mischer aufgebaute Sortiernetzwerk -- mit dem +\emph{Odd-Even-Mischer} nicht wiederholen. Zwar erreichen die +Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung des +\emph{Odd-Even-Mischers} findet, das \emph{Odd-Even-Mergesort}-Netzwerk +bezüglich Schnelligkeit und Effizienz, ein Beispiel hierfür ist in +Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen. Ein Netzwerk, das +$\operatorname{OES}(n)$ in mindestens einem Merkmal übertrifft, konnte jedoch +nicht beobachtet werden. -\begin{itemize} -\item So gut kann man mindestens werden {\em ($\rightarrow$ Bitonic-Mergesort, vermute ich)}. -\item Wie gut die Netzwerke werden, hängt stark vom verwendeten \em{Mischer} ab. -\item Ggf. Abschnitt „Shmoo-Äquivalenz“ kürzen und hier einbauen. -\end{itemize} +\todo{Ggf. Abschnitt „Shmoo-Äquivalenz“ kürzen und hier einbauen.} + +%\begin{figure} +%\begin{center} +%\input{images/08-e2-1237993371.tex} +%\end{center} +%\caption{{\tt images/08-e2-1237993371.tex}: 19~Komparatoren in 6~Schichten} +%\label{fig:08-e2-1237993371} +%\end{figure} +% +%\begin{figure} +%\begin{center} +%\input{images/09-e2-1237997073.tex} +%\end{center} +%\caption{{\tt images/09-e2-1237997073.tex}: 25~Komparatoren in 8~Schichten} +%\label{fig:09-e2-1237997073} +%\end{figure} +% +%\begin{figure} +%\begin{center} +%\input{images/09-e2-1237999719.tex} +%\end{center} +%\caption{{\tt images/09-e2-1237999719.tex}: 25~Komparatoren in 7~Schichten} +%\label{fig:09-e2-1237999719} +%\end{figure} +% +%\begin{figure} +%\begin{center} +%\input{images/10-e2-1239014566.tex} +%\end{center} +%\caption{{\tt images/10-e2-1239014566.tex}: 29~Komparatoren in 8~Schichten} +%\label{fig:10-e2-1239014566} +%\end{figure} %\input{shmoo-aequivalenz.tex} @@ -1326,11 +1400,11 @@ von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}. Mit diesem Algorithmus wurden zu einer Reihe von „interessanten“ Netzwerken möglichst gute Schnittmuster gesucht. -Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet die \emph{Schnittmuster} -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$. +Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet die \emph{Schnittmuster}, +die 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$. Die Mutation setzt entweder die Leitungs-Nummer eines Schnitts~$i$ zufällig auf einen neuen Wert $l$ mit $0 \leqq l \le n-i$ oder invertiert die @@ -1473,14 +1547,6 @@ den Schichten~1--6 erkennt man zwei unabhängige Sortiernetzerke, die strukturell identisch zu $\operatorname{PS}(8)$ sind -- lediglich die Schichten~1 und~2 sowie 4~und~5 sind vertauscht. -\begin{displaymath} -\textit{Eingang}_i = \left\{ \begin{array}{rl} - -\infty & \quad \textrm{falls } i \operatorname{mod} 8 \in \{0, 6\} \\ - \infty & \quad \textrm{falls } i \operatorname{mod} 8 \in \{2, 4\} \\ - ? & \quad \mathrm{sonst} - \end{array} \right. -\end{displaymath} - \begin{figure} \begin{center} \input{images/32-pairwise-cut-16-pairwise.tex} @@ -1489,6 +1555,28 @@ Schichten~1 und~2 sowie 4~und~5 sind vertauscht. \label{fig:ps16-from-ps32} \end{figure} +Für das \emph{Pairwise-Sorting-Netzwerk} ist es vergleichsweise einfach +regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk einen kleineres +schnelles und effizientes Sortiernetzwerk erzeugen. Beispielsweise führt das +einfache Schnittmuster +\begin{displaymath} +\textit{Eingang}_i = \left\{ \begin{array}{rl} + -\infty & \quad \textrm{falls } i < \frac{1}{4} n \\ + \infty & \quad \textrm{falls } i \geqq \frac{3}{4} n \\ + ? & \quad \mathrm{sonst} + \end{array} \right. +\end{displaymath} +für $\operatorname{PS}\left(n = 2^d\right)$ zum Sortiernetzwerk +$\operatorname{PS}\left(\frac{1}{2}n\right)$. Die Art und Weise, mit der +dieses Schnittmuster Komparatoren eliminiert und welche Komparatoren das +verbleibende Netzwerk ausmachen, ist in Abbildung~\ref{fig:ps16-from-ps32} +dargestellt. Die matt blauen und roten Leitungen und Komparatoren sind +diejenigen, die Aufgrund eines Minimums oder eines Maximums im resultierenden +Netzwerk nicht mehr enthalten sind. Da die Minima und Maxima bereits auf den +„richtigen“ Leitungen angelegt werden, müssen keine Leitungen vertauscht +werden und das Ergebnis ist bereits normalisiert. Daher ist das resultierende +Netzwerk in schwarz gut zu erkennen. + \begin{figure} \begin{center} \input{images/16-pairwise.tex} @@ -1499,21 +1587,50 @@ Schichten~1 und~2 sowie 4~und~5 sind vertauscht. \label{fig:16-pairwise} \end{figure} -Wendet man \textsc{SN-Evolution-Cut} auf $\operatorname{PS}(16)$ an, so kann -man $\operatorname{OES}(8)$ erhalten. +Ein Spezialfall ergibt sich, wenn man \textsc{SN-Evolution-Cut} auf +$\operatorname{PS}(16)$ anwendet: In diesem Fall kann man durch ein +8-Schnittmuster das \emph{Odd-Even-Mergesort}-Netzwerk \oes{8} erhalten. Für +größere Sortiernetzwerke ist dies hingegen nicht mehr möglich, beispielsweise +kann $\operatorname{PS}(32)$ nicht durch ein 16-Schnittmuster in \oes{16} +konvertiert werden. Die Verwandschaft von $\operatorname{PS}(n)$ und \oes{n} +untersucht \textit{Moritz Mühlenthaler} ausführlich in~\cite{M2009}. \subsection{Versuche mit dem Odd-Even-Mergesort-Netzwerk} -\todo{Schreibe noch etwas zum Odd-Even-Mergesort-Netzwerk.} +In Abschnitt~\ref{sect:anzahl_schnittmuster} wurde bereits untersucht, wie +viele \emph{unterschiedliche} Schnittmuster die konstruktiven Sortiernetzwerke +$\operatorname{OES}(32)$, $\operatorname{BS}(32)$ und $\operatorname{PS}(32)$ +besitzen. Eines der Ergebnisse war, dass von diesen Sortiernetzwerken das +\emph{Odd-Even-Mergesort}-Netzwerk die wenigsten unterschiedlichen +16-Schnittmuster besitzt -- nur etwa $5,2$~Millionen. Entsprechend ist es +wenig verwunderlich, dass \textsc{SN-Evolution-Cut} gestartet mit +$\operatorname{OES}(32)$ sehr schnell ein gutes 16-Schnittmuster findet. -\begin{itemize} - \item Beispiel: Moritz und Rolfs Optimierung für Bitonic-Sort. - \item Wie gut kann man durch wegschneiden werden? - \item Wieviele Schnitte ergeben das selbe Netzwerk? Oder andersrum: Wieviele - unterschiedliche Netzwerke kann ich erhalten? Wieviele Nachfolger hat ein - Netzwerk / Knoten in der Markov-Kette? - \item Abschnitt „Optimierung der Schnitte“ hier einbauen. -\end{itemize} +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 +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. + +\begin{figure} + \begin{center} + \input{images/16-ec-from-oes32-cut.tex} + \end{center} + \caption{Visualisierung eines 16-Schnittmusters, das auf + $\operatorname{OES}(32)$ angewendet wieder ein schnelles und effizientes + Sortiernetzwerk ergibt.} + \label{fig:16-ec-from-oes32-cut} +\end{figure} + +\begin{figure} + \begin{center} + \input{images/16-ec-from-oes32.tex} + \end{center} + \caption{16-Sortiernetzwerk mit 63~Komparatoren in 10~Schichten. + Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution-Cut} aus dem + \emph{Odd-Even-Mergesort-Netzwerk} $\operatorname{OES}(32)$ durch + 16~Schnitte erzeugt.} + \label{fig:16-ec-from-oes32} +\end{figure} \newpage \section{Der \textsc{SN-Markov}-Algorithmus} @@ -1577,7 +1694,7 @@ gib Netzwerk zurück \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. @@ -1626,22 +1743,106 @@ gib Netzwerk zurück \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$ +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} -So habe ich die ganzen Versuche durchgeführt. +Alle in dieser Arbeit beschriebenen Versuche wurden mit einer eigens +entwickelten C-Bibliothek, \textit{libsortnetwork}, und zugehörigen +Kommandozeilen-Programmen durchgeführt. Die Bibliothek wurde unter der +\textit{GNU Lesser General Public License} (LGPL) in der Version~2.1 +veröffentlicht; die Kommandozeilen-Programme, die in vielen Fällen lediglich +Funktionalität der Bibliothek auf der Kommandozeile zur Verfügung stellen, +stehen unter der \textit{GNU General Public License}, Version~2. Diese +Lizenzen räumen einem Benutzer weitreichende Rechte ein, unter anderem das +Programm beliebig zu verwenden, zu studieren, zu verändern sowie veränderte +und unveränderte Kopien zu veröffentlichen. + +Die Programmierschnittstelle (API) der Bibliothek orientiert sich an +Paradigmen der \textit{objektorientierten Programmierung}. Beispielsweise kann +mit der Funktion \texttt{sn\_network\_ create()} ein neues Zustands-Objekt +erzeugt werden, für das mehrere Manipulations-Methoden, zum Beispiel +\texttt{sn\_network\_comparator\_add()}, zur Verfügung stehen. Auf diese Art +und Weise kann die Bibliothek leicht erweitert werden, ohne dass bestehende +Programme angepasst werden müssen. + +Die meisten Kommandozeilen-Programmen lesen ein Komparatornetzwerk von der +Standard-Eingabe und schreiben ihr Ergebnis auf die Standard-Ausgabe. Um +Beispielsweise eine \emph{normalisierte} Variante des \emph{bitonen +Mergesort}-Netzwerks \bs{18} zu erzeugen, kann folgendes Kommando verwendet +werden: +\begin{verbatim} +$ sn-bitonicsort 18 | sn-normalize >sn-18 +\end{verbatim} +Dieses Prinzip, kleine Programme \emph{eine} Aufgabe erledigen zu lassen und +es einfach zu ermöglichen, Programme zu verketten, ist eines der +Grundprinzipien des UNIX-Be\-triebs\-sys\-tems. Es hat sich in den letzten +Jahrzehnten und beim Verfassen dieser Arbeit als sehr flexibel und mächtig +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. + +\textit{libsortnetwork} kann unter der Web-Adresse +\url{http://octo.it/libsortnetwork/} unentgeldlich heruntergeladen werden. \newpage \bibliography{references}