X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=c4ac16576f2e133b358bd7100d87b48476fdc336;hb=502386e80e6d483ad822488ee630e35f5b828827;hp=3299249f3f5881400181a5427fa7839e7814b38d;hpb=4ed102d387b0fb4f5bb54e6cab888c6f152629ea;p=diplomarbeit.git diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 3299249..c4ac165 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -36,6 +36,13 @@ \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)}} +\newcommand{\oet}[1]{\ensuremath{\operatorname{OET}(#1)}} + \newtheorem{definition}{Definition} \newtheorem{satz}{Satz} @@ -75,7 +82,7 @@ \maketitle \begin{abstract} Sortiernetzwerke werden eingeführt und einige bekannte Konstruktionen werden -vorgestellt (Off-Even-Transposition, Bitonic-Merge, Odd-Even-Merge, Pairwise). +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. @@ -92,6 +99,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. @@ -175,12 +183,12 @@ Definition handelt es sich bei dem \emph{Komparatornetzwerk} folglich gegebenes Komparatornetzwerk zu finden ist nach heutigem Kenntnisstand jedoch nicht \emph{effizient} möglich. -Beispielsweise sortiert das Komparatornetzwerk in -Abbildung~\ref{fig:09-e2-c24-allbut1} viele der 362.880 möglichen -Eingabepermutationen. Mit dem Gegenbeispiel $(3, 5, 2, 1, 0, 7, 4, 8, 6)$ -lässt sich jedoch leicht beweisen, dass das Komparatornetzwerk die -Sortiereigenschaft \emph{nicht} besitzt, da es in diesem Fall die Folge -$(1, 0, 2, 3, 4, 5, 6, 7, 8)$ ausgibt. +Beispielsweise sortiert das im Rahmen dieser Arbeit entdeckte +Komparatornetzwerk in Abbildung~\ref{fig:09-e2-c24-allbut1} viele der 362.880 +möglichen Eingabepermutationen. Mit dem Gegenbeispiel $(3, 5, 2, 1, 0, 7, 4, +8, 6)$ lässt sich jedoch leicht beweisen, dass das Komparatornetzwerk die +Sortiereigenschaft \emph{nicht} besitzt, da es in diesem Fall die Folge $(1, +0, 2, 3, 4, 5, 6, 7, 8)$ ausgibt. Insgesamt gibt es $n!$~Permutationen von $n$~Elementen. Wenn ein Komparatornetzwerk die Sortiereigenschaft besitzt, bildet es alle diese @@ -189,6 +197,7 @@ Permutationen auf die sortierte Reihenfolge ab. Allerdings wächst $n!$ Permutationen schon bei 16~Leitungen praktisch nicht mehr zu bewerkstelligen ist.\footnote{1.307.674.368.000 Permutationen} +\label{sect:0-1-prinzip} Glücklicherweise reicht es aus, alle möglichen 0-1-Folgen zu überprüfen, wie \textit{Donald~E. Knuth} in \cite{KNUTH} zeigt. Die Beweisidee ist folgende: Angenommen ein Komparatornetzwerk sortiert alle 0-1-Folgen und es gibt eine @@ -206,10 +215,19 @@ Die Eingabe kann mittels 1 & e_j > a_i \end{array} \right. \end{displaymath} -auf eine 0-1-Folge abgebildet werden, die entsprechen der Annahme von +auf eine 0-1-Folge abgebildet werden, die entsprechen der Annahme vom Komparatornetzwerk sortiert wird. Allerdings verändert diese Abbildung das -Verhalten jedes einzelnen Komparators nicht, so dass die Annahme auf einen -Widerspruch geführt wird. +Verhalten jedes einzelnen Komparators nicht: Wenn bei der Permutation eine +Zahl größer als $a_i$ und eine Zahl kleiner oder gleich $a_i$ verglichen +wurden, liegen jetzt entsprechend eine Null und eine Eins an, die genauso +vertauscht werden oder nicht, wie das bei der Permutation der Fall war. Liegen +zwei Nullen oder zwei Einsen an, entsprechen sie zwei Zahlen kleiner als $a_i$ +oder zwei Zahlen größer oder gleich $a_i$. Da im Fall der 0-1-Folge zwei +gleiche Zahlen am Komparator anliegen, dürfen wir davon ausgehen, dass sich +der Komparator so verhält, wie er sich bei der Permutation verhalten hat -- +ohne das Ergebnis zu beeinflussen. Entsprechend kommen an den Ausgängen $i-1$ +und $i$ eine Null und eine Eins in der falschen Reihenfolge an. Das steht im +Widerspruch zu der Annahme, dass alle 0-1-Folgen sortiert werden. Im Gegensatz zum Überprüfen aller möglichen Permutationen, was der Komplexitätsklasse @@ -311,12 +329,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} @@ -373,7 +434,7 @@ Schichten. Das Sortiernetzwerk basiert auf einem Komparatornetzwerk, welches zwei sortierte Listen zusammenfügen (englisch: \textit{to~merge}) kann. Dieser -\emph{„bitoner Mischer“} (englisch: \textit{bitonic merger}) genannte Baustein +\emph{„bitone Mischer“} (englisch: \textit{bitonic merger}) genannte Baustein verleiht dem Sortiernetzwerk seinen Namen. Da das Sortiernetzwerk rekursiv definiert ist, betrachten wir hier nur die @@ -382,20 +443,20 @@ Es ist jedoch möglich das Sortiernetzwerk für beliebige~$n$ zu erzeugen. \subsubsection{Der bitone Mischer}\label{sect:der_bitone_mischer} -Das \emph{bitone Mergesort-Netzwerk} basiert auf dem sogenannten \emph{bitonen -Mischer} $\operatorname{BM}(n)$, einem Kom\-parator-Netzwerk, das eine beliebige -\emph{bitone Folge} in eine sortierte Listen umordnen kann. Eine \emph{bitone -Folge} ist eine monoton steigende Folge gefolgt von einer monoton absteigenden -Folge, oder ein zyklischer Shift davon. Abbildung~\ref{fig:beispiel-biton} -zeigt die vier prinzipiellen Möglichkeiten die durch zyklische Shifts -entstehen können. Die wichtigsten Varianten für das \emph{bitone -Mergesort-Netzwerk} zeigen die Abbildungen~\ref{fig:beispiel-biton-0} -und~\ref{fig:beispiel-biton-1}. Sie erhält man, wenn man eine aufsteigend und -eine absteigend sortierte Liste aneinanderhängt. Bei den anderen beiden Formen -ist wichtig zu beachten, dass das letzte Element nicht größer -(Abbildung~\ref{fig:beispiel-biton-2}) bzw. kleiner -(Abbildung~\ref{fig:beispiel-biton-3}) als das erste Element der Folge sein -darf. +Das \emph{bitone Mergesort}-Netzwerk basiert auf dem sogenannten \emph{bitonen +Mischer} $\operatorname{BM}(n)$, einem Kom\-parator-Netzwerk, das eine +beliebige \emph{bitone Folge} in eine sortierte Listen umordnen kann. Eine +\emph{bitone Folge} ist eine monoton steigende Folge gefolgt von einer monoton +absteigenden Folge, oder ein zyklischer Shift davon. +Abbildung~\ref{fig:beispiel-biton} zeigt die vier prinzipiellen Möglichkeiten +die durch zyklische Shifts entstehen können. Die wichtigsten Varianten für das +\emph{bitone Mergesort}-Netzwerk zeigen die +Abbildungen~\ref{fig:beispiel-biton-0} und~\ref{fig:beispiel-biton-1}. Sie +erhält man, wenn man eine aufsteigend und eine absteigend sortierte Liste +aneinanderhängt. Bei den anderen beiden Formen ist wichtig zu beachten, dass +das letzte Element nicht größer (Abbildung~\ref{fig:beispiel-biton-2}) bzw. +kleiner (Abbildung~\ref{fig:beispiel-biton-3}) als das erste Element der Folge +sein darf. \begin{figure} \centering @@ -487,10 +548,9 @@ alle Komparatoren in die gleiche Richtung zeigen. \begin{center} \input{images/batcher-8.tex} \end{center} - \caption{$\operatorname{BS}(8)$, Batchers {\em bitones Mergesort-Netzwerk} - für acht Eingänge. Markiert sind die beiden Instanzen von - $\operatorname{BS}(4)$ (rot), die beiden bitonen - Mischer~$\operatorname{BM}(4)$ (blau) und die Komparatoren, die im letzten + \caption{\bs{8}, Batchers \emph{bitones Mergesort}-Netzwerk für acht + Eingänge. Markiert sind die beiden Instanzen von \bs{4} (rot), die beiden + bitonen Mischer~\bm{4} (blau) und die Komparatoren, die im letzten rekursiven Schritt hinzugefügt wurden (grün).} \label{fig:bitonic-08} \end{figure} @@ -507,15 +567,6 @@ $\frac{1}{4} n \log(n) \log(n+1) = \mathcal{O}\left(n (log (n))^2\right)$ 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} @@ -527,17 +578,17 @@ vorgestellt wurde, ähnlich: Auch dieses Sortiernetzwerk ist von beschrieben und initial analysiert worden. Eine weitere Gemeinsamkeit besteht darin, dass es ebenfalls rekursiv durch einen Mischer definiert ist. -\subsubsection{Der Odd-Even-Mischer}\label{sect:der_odd_even_mischer} +\subsubsection{Der \emph{Odd-Even}-Mischer}\label{sect:der_odd_even_mischer} -Der \emph{Odd-Even-Mischer} $\operatorname{OEM}(n,m)$ ist ein +Der \emph{Odd-Even}-Mischer $\operatorname{OEM}(n,m)$ ist ein Komperatornetzwerk, dass zwei sortierte Folgen mit $n$ beziehungsweise $m$ Elementen zu einer sortierten Ausgabefolge mit $N = n+m$~Elementen zusammenfügen kann. Dabei kommt es mit weniger Vergleichen aus als der \emph{bitone Mischer}, der im Abschnitt~\ref{sect:der_bitone_mischer} -vorgestellt wurde. Allerdings benötigt der \emph{Odd-Even-Mischer} unter +vorgestellt wurde. Allerdings benötigt der \emph{Odd-Even}-Mischer unter Umständen mehr Schichten als der \emph{bitone Mischer}.~\cite{KNUTH} -Der \emph{Odd-Even-Mischer} selbst ist ebenfalls rekursiv aufgebaut: Die +Der \emph{Odd-Even}-Mischer selbst ist ebenfalls rekursiv aufgebaut: Die Eingabe für den Mischer mit $N = n + m$ Leitungen besteht aus den beiden sortierten Folgen $U = \left(u_0, u_1, \ldots, u_{n-1}\right)$ und $V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die gesamte Eingabe sei @@ -571,7 +622,7 @@ geraden Indizes und je eine Liste der ungeraden Indizes. Die geraden Folgen $U_{\textrm{gerade}}$ und $V_{\textrm{gerade}}$ bzw. die ungeraden Folgen $U_{\textrm{ungerade}}$ und $V_{\textrm{ungerade}}$ werden -rekursiv von kleineren {\em Odd-Even-Mischern} zusammengefügt, so dass sich am +rekursiv von kleineren \emph{Odd-Even}-Mischern zusammengefügt, so dass sich am Ausgang der Mischer die Folgen \begin{eqnarray} W_{\textrm{gerade}} &=& \left(w_0, w_2, w_4, \ldots\right) \\ @@ -584,8 +635,8 @@ hinzugefügt, \begin{equation} w_{2i-1} \longleftrightarrow w_{2i}, \quad 1 \leqq i < \frac{N}{2} \end{equation} -die die Folge~$W$ sortieren. Den schematischen Aufbau des {\em -Odd-Even-Mischers} zeigt Abbildung~\ref{fig:oe-merge}. +die die Folge~$W$ sortieren. Den schematischen Aufbau des +\emph{Odd-Even}-Mischers zeigt Abbildung~\ref{fig:oe-merge}. Leider bricht die Rekursion nicht so schön ab, wie das beim {\em bitonen Mischer} der Fall gewesen ist. Insbesondere für ${n = m = 1}$ würde -- @@ -635,7 +686,7 @@ in Abbildung~\ref{fig:oe-post-recursive} dargestellt. \qquad \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 2$]{\input{images/oe-post-recursive-diff2.tex}} \caption{Die drei Situationen, die nach dem Verzahnen der Ausgaben der - kleineren {\em Odd-Even-Mischer} entstehen können. Ist die Differenz der + kleineren \emph{Odd-Even}-Mischer entstehen können. Ist die Differenz der Anzahl der Nullen gleich $0$ oder $1$, ist die Folge bereits sortiert. Im letzten Fall stellt einer der Komparatoren sicher, dass das Ergebnis sortiert ist.} @@ -686,7 +737,7 @@ benötigt werden. Das \emph{Odd-Even-Mergesort-Netzwerk} $\operatorname{OES}(n)$ besteht --~wie das \emph{bitone Mergesort-Netzwerk}~-- rekursiv aus kleineren Varianten von -sich selbst und einem abschließenden \emph{Odd-Even-Mischer}. Die +sich selbst und einem abschließenden \emph{Odd-Even}-Mischer. Die effizientesten Sortiernetzwerke in Bezug auf Komparator- und Schichtzahl entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht $\operatorname{OES}(n)$ aus @@ -703,7 +754,7 @@ Komparatornetzwerke definiert sind. \end{center} \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge. Markiert sind die Instanzen von $\operatorname{OES}(4)$ (rot), die beiden - \emph{Odd-Even-Mischer} $\operatorname{OEM}(4)$ für gerade und ungerade + \emph{Odd-Even}-Mischer $\operatorname{OEM}(4)$ für gerade und ungerade Leitungen (blau) und die im ersten Rekursionsschritt hinzugefügten Komparatoren zwischen benachbarten Leitungen (grün).} \label{fig:odd-even-mergesort-08} @@ -712,7 +763,7 @@ Komparatornetzwerke definiert sind. In Abbildung~\ref{fig:odd-even-mergesort-08} ist das konkrete Sortiernetzwerk $\operatorname{OES}(8)$ zu sehen. Rot markiert sind die beiden rekursiven Instanzen $\operatorname{OES}(4)$. Die blauen und der grüne Block stellen den -\emph{Odd-Even-Mischer} für acht Leitungen dar: Die beiden blauen Blöcke sind +\emph{Odd-Even}-Mischer für acht Leitungen dar: Die beiden blauen Blöcke sind die rekursiven Instanzen von $\operatorname{OEM}(4)$, der grüne Block markiert die Komparatoren, die in ersten Rekursionsschritt hinzugefügt werden. @@ -771,6 +822,7 @@ die Anzahl der Schichten als Bewertungskriterium verwendet, immer eine Komprimierung durchgeführt werden. \subsection{Normalisieren} +\label{sect:normalisieren} \begin{figure} \centering @@ -835,7 +887,7 @@ $\operatorname{OES}(9)$ benötigt beispielsweise 26~Komparatoren, die in in neun Schichten angeordnet sind. Es sind allerdings Sortiernetzwerke mit neun Eingängen bekannt, die lediglich 25~Komparatoren in sieben Schichten benötigen. Kombiniert man zwei dieser Netzwerke mit dem -\emph{Odd-Even-Mischer} erhält man ein Sortiernetzwerk mit 18~Eingängen, das +\emph{Odd-Even}-Mischer erhält man ein Sortiernetzwerk mit 18~Eingängen, das 80~Komparatoren in 11~Schichten benötigt -- $\operatorname{OES}(18)$ benötigt 82~Komparatoren in 13~Schichten. Damit ist das resultierende Netzwerk so schnell wie das Sortiernetzwerk mit 18~Eingängen, das \textit{Sherenaz~W. @@ -843,18 +895,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 @@ -864,12 +904,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} @@ -894,17 +928,20 @@ das {\em Odd-Even-Transpositionsort-Netzwerk}. \begin{figure} \centering - \subfigure[foo]{\input{images/oe-transposition-cut0.tex}\label{fig:oe-transposition-cut0}} - \subfigure[bar]{\input{images/oe-transposition-cut1.tex}\label{fig:oe-transposition-cut1}} - \subfigure[baz]{\input{images/oe-transposition-cut2.tex}\label{fig:oe-transposition-cut2}} - \subfigure[qux]{\input{images/oe-transposition-cut3.tex}\label{fig:oe-transposition-cut3}} + \subfigure[Auf der Leitung~4 wird $-\infty$ angelegt. Dadurch ist der Pfad + durch das Sortiernetzwerk eindeutig festgelegt.]{\input{images/oe-transposition-cut0.tex}\label{fig:oe-transposition-cut0}} + \subfigure[Komparatoren, die einen wechsel der Leitungen bewirken, werden + durch sich kreuzende Leitungen ersetzt.]{\input{images/oe-transposition-cut1.tex}\label{fig:oe-transposition-cut1}} + \subfigure[Leitung~4 wurde entfernt. Übrig bleibt ein Sortiernetzwerk mit + 7~Leitungen.]{\input{images/oe-transposition-cut2.tex}\label{fig:oe-transposition-cut2}} + \subfigure[Die Leitungen wurden wieder gerade eingezeichnet und die + Komparatoren regelmäßig angeordnet. Blau eingezeichnet ist \oet{7}.]{\input{images/oe-transposition-cut3.tex}\label{fig:oe-transposition-cut3}} \caption{Eine Leitung wird aus dem - \emph{Odd-Even-Transpositionsort}-Netzwerk $\operatorname{OET}(8)$ entfernt: - Auf der rot markierten Leitung wird $\infty$ angelegt. Da der Wert bei jedem - Komparator am unteren Ende herauskommt, ist der Pfad fest vorgegeben. Da die - restlichen Werte trotzdem noch richtig sortiert werden müssen, kann dieser - Pfad herausgetrennt werden. In der letzten Abbildung ist - $\operatorname{OET}(7)$ markiert.} + \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{8} entfernt: Auf der rot + markierten Leitung wird $-\infty$ angelegt. Da der Wert bei jedem Komparator + am unteren Ende herauskommt, ist der Pfad fest vorgegeben. Da die restlichen + Werte trotzdem noch richtig sortiert werden müssen, kann dieser Pfad + herausgetrennt werden. In der letzten Abbildung ist \oet{7} markiert.} \label{fig:oe-transposition-cut} \end{figure} @@ -927,19 +964,25 @@ auszuwerten -- über die verbleibenden Eingänge haben wir keine Aussage getroffen. Entsprechend müssen die verbleibenden Ausgänge eine sortierte Liste mit $(n-1)$~Elementen darstellen. -Wenn wir die Minimum- beziehungsweise Maximum-Leitung entfernen -(Abbildung~\ref{fig:oe-transposition-cut2}), bleibt das Sortiernetzwerk für -$(n-1)$~Leitungen übrig. Je nachdem, ob auf einer Leitung ein Minimum oder ein -Maximum angenommen wird, bezeichnen wir das eliminieren einer Leitung als -\emph{Minimum-Schnitt} beziehungsweise \emph{Maximum-Schnitt}. +Wenn man die Minimum- beziehungsweise Maximum-Leitung entfernt, wie in +Abbildung~\ref{fig:oe-transposition-cut2} dargestellt, bleibt das +Sortiernetzwerk für $(n-1)$~Leitungen übrig. Je nachdem, ob auf einer Leitung +ein Minimum oder ein Maximum angenommen wird, bezeichnen wir das eliminieren +einer Leitung als \emph{Minimum-Schnitt} beziehungsweise +\emph{Maximum-Schnitt}. Die letzte Abbildung, \ref{fig:oe-transposition-cut3}, zeigt das Sortiernetzwerk wieder mit den üblichen geraden Leitungen und die rot markierten Komparatoren wurden verschoben, so dass sich eine kompaktere Darstellung ergibt. Ausserdem ist das -{\em Odd-Even-Transpositionsort-Netzwerk} für sieben Werte markiert. Der -zusätzliche Komparator vor dem $\textrm{OET}(7)$ hat keinen Einfluss auf die -Ausgabe und kann entfernt werden. +\emph{Odd-Even-Transpositionsort}-Netzwerk für sieben Werte markiert. Der +zusätzliche Komparator vor dem \oet{7} hat keinen Einfluss auf die Ausgabe und +kann entfernt werden. + +Durch das Ersetzen von Komparatoren durch gekreuzte Leitungen werden häufig +\emph{Nicht-Standard-Sortiernetzwerke} erzeugt. Im Anschluss an einen +\emph{Schnitt} empfiehlt es sich deshalb, das Sortiernetzwerk zu +\emph{normalisieren}, wie in Abschnitt~\ref{sect:normalisieren} beschrieben. \subsubsection{Anzahl möglicher und unterschiedlicher Schnittmuster} \label{sect:anzahl_schnittmuster} @@ -947,8 +990,8 @@ Ausgabe und kann entfernt werden. Der Eliminierungsschritt kann iterativ angewandt werden, um aus einem Sortiernetzwerk mit $n$~Ein\-gängen Sortiernetzwerke mit $n-1$, $n-2$, $n-3$,~\dots Eingängen zu erzeugen. Insbesondere können auf diese Art und -Weise einen Sortiernetzwerke mit $2n$~Eingängen wieder auf Sortiernetzwerke -mit $n$~Eingängen reduziert werden. $k$~Minimum- und Maximum-Schnitte, die +Weise Sortiernetzwerke mit $2n$~Eingängen auf Sortiernetzwerke mit +$n$~Eingängen reduziert werden. $k$~Minimum- und Maximum-Schnitte, die nacheinander angewendet ein $n$-Sortiernetzwerk auf ein ${(n-k)}$-Sortiernetz\-werk reduzieren, bezeichnen wir als \emph{$k$-Schnittmuster}. @@ -963,7 +1006,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 @@ -971,14 +1014,15 @@ unterschiedlich. Legt man beispielsweise das Minimum auf die unterste Leitung und das Maximum auf die oberste Leitung eines Standard-Sortiernetzwerks, führen beide Reihenfolgen zum selben Ergebnis. -\textit{Moritz Mühlenthaler} zeigt in seiner Arbeit (\todo{Referenz}), dass es +\textit{Moritz Mühlenthaler} zeigt in seiner Arbeit~\cite{M2009}, dass es möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise Maximum -vorzubelegen. Dadurch wird die Anzahl der möglichen Schnittmuster reduziert, -die Menge der so erzeugbaren Sortiernetzwerke bleibt aber unverändert. Die -Anzahl der möglichen Schnittmuster setzt sich zusammen aus der Anzahl von -Möglichkeiten, $k$~Leitungen aus $n$~Leitungen auszuwählen, und die möglichen -Minimum-~/ Maximum-Muster. Damit ergibt sich folgende Formel für die Anzahl -der möglichen Schnittmuster: +vorzubelegen, ohne die Menge der erreichbaren Sortiernetzwerke einzuschränken. +Dadurch wird die Anzahl der möglichen Schnittmuster reduziert, die Menge der +so erzeugbaren Sortiernetzwerke bleibt aber unverändert. Die Anzahl der +möglichen Schnittmuster setzt sich zusammen aus der Anzahl von Möglichkeiten, +$k$~Leitungen aus $n$~Leitungen auszuwählen, und die möglichen Minimum-~/ +Maximum-Muster. Damit ergibt sich folgende Formel für die Anzahl der möglichen +Schnittmuster: \begin{displaymath} 2^k \cdot \left( \begin{array}{c} n \\ k \end{array} \right) = 2^{k} \cdot \frac{n!}{k! (n-k)!} @@ -1018,8 +1062,8 @@ sich die Resultate auch in der ersten Schicht nicht unterscheiden. 8-Schnittmuster aus $\operatorname{OES}(16)$, $\operatorname{BS}(16)$ und $\operatorname{PS}(16)$ hervorgegangen sind. Die Anzahl der unterschiedlichen Netzwerke nach $10^6$~Iterationen ist 3519 für das - \emph{Odd-Even-Mergesort-Netzwerk}, 4973 für das \emph{bitone - Mergesort-Netzwerk} und 18764 für das \emph{Pairwise-Sorting-Netzwerk}.} + \emph{Odd-Even-Mergesort}-Netzwerk, 4973 für das \emph{bitone + Mergesort}-Netzwerk und 18764 für das \emph{Pairwise-Sorting}-Netzwerk.} \label{fig:count-cuts-16} \end{figure} @@ -1027,13 +1071,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 @@ -1043,29 +1086,31 @@ 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 +\emph{Monte-Carlo-Methode}, die \textit{Rolf Wanka} in~\cite{W2006} für +schwierige Zählprobleme vorstellt. 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. @@ -1088,8 +1133,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} @@ -1110,9 +1155,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 @@ -1123,6 +1168,7 @@ die Anzahl der \emph{möglichen} Schnittmuster. \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 @@ -1194,21 +1240,21 @@ Algorithmus vorschnell in Richtung eines lokalen Optimums optimiert. Die in \textsc{SN-Evolution} implementierte Selektion lässt sich mithilfe von Pseudocode wie folgt beschreiben: \begin{verbatim} -Gütesumme := 0 -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) - Gütesumme := Gütesumme + reziproke Güte - - mit Wahrscheinlichkeit P + Gütesumme := 0 + Auswahl := (leer) + + für jedes Individuum in Population { - Auswahl := Individuum + reziproke Güte := 1.0 / Guete(Individuum) + Wahrscheinlichkeit P := reziproke Güte / (Gütesumme + reziproke Güte) + Gütesumme := Gütesumme + reziproke Güte + + mit Wahrscheinlichkeit P + { + Auswahl := Individuum + } } -} -gib Auswahl zurück + gib Auswahl zurück \end{verbatim} \subsection{Rekombination} @@ -1216,90 +1262,135 @@ gib Auswahl zurück Bei der Rekombination werden zwei Individuen --~hier Sortiernetzwerke~-- zu einer neuen Lösung kombiniert. Dazu verwenden wir einen Mischer, zum Beispiel den {\em bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) oder den -{\em Odd-Even-Mischer} (Abschnitt~\ref{sect:der_odd_even_mischer}), um die +\emph{Odd-Even}-Mischer (Abschnitt~\ref{sect:der_odd_even_mischer}), um die beiden Netzwerke zu einem Netzwerk mit $2n$~Leitungen zusammenzufügen. -Anschließend entfernen wir zufällig $n$~Leitungen wie in -Abschnitt~\ref{sect:leitungen_entfernen} beschrieben. +Anschließend werden zufällig $n$~Leitungen mit einem $n$-Schnittmuster wie in +Abschnitt~\ref{sect:leitungen_entfernen} beschrieben entfernt. Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft -erhält. +erhält. Entsprechend muss nicht aufwendig überprüft werden, ob das +Komparatornetzwerk die Sortiereigenschaft besitzt. Der Nachteil ist, dass +nicht alle Sortiernetzwerke auf diese Art und Weise erzeugt werden können. \subsection{Mutation} -Zu einem vollständigen evolutionären Algorithmus gehört außerdem eine Mutation +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. Nach einer Mutation müsste man überprüfen, ob das neue Komparatornetzwerk die Sortiereigenschaft noch besitzt. Nach heutigem Wissenstand ist diese Überprüfung nur mit exponentiellem Aufwand möglich, etwa durch das -Ausprobieren aller $2^n$~Bitmuster. +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 \emph{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} @@ -1315,11 +1406,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 \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 @@ -1334,7 +1425,7 @@ Mischer mit der Hälfte der Leitungen transformiert. Diese alternativen Mischer sparen im Vergleich zu den Mischern, die nach Batchers Methode konstruiert werden, Komparatoren ein. -Beispeilsweise geben \textit{Mühlenthaler} und \textit{Wanka} ein +Beispielsweise geben \textit{Mühlenthaler} und \textit{Wanka} ein Sortiernetzwerk mit 16~Eingängen an, das mithilfe der alternativen Mischer konstruiert wurde. Dieses Sortiernetzwerk benötigt 68~Komparatoren, 12~weniger als das bitone Mergesort-Netzwerk nach Batchers Methode. Gegenüber Batchers @@ -1397,7 +1488,7 @@ Netzwerks scheinen rein zufällig zu sein. \label{fig:32-ec-from-bs64} \end{figure} -Das Ergebnis von \textit{Mühlenthaler} von \textit{Wanka}, die den bitonen +Das Ergebnis von \textit{Mühlenthaler} und \textit{Wanka}, die den bitonen Mischer optimiert und anschließend aus diesen Mischern ein Sortiernetzwerk konstruiert haben, kann demnach auch erreicht werden, wenn $\operatorname{BS}(32)$ auf ein 16-Sortiernetzwerk reduziert wird. Bei anderen @@ -1454,7 +1545,7 @@ Anzahl an Komparatoren und Schichten hat wie $\operatorname{PS}(16)$ und $\operatorname{OES}(16)$. Eines dieser Sortiernetzwerke ist in Abbildung~\ref{fig:16-ec-from-ps32} dargestellt. -Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even-Mischer} nicht +Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even}-Mischer nicht einsetzt und auch nicht auf einem Mischer basiert, ist der $\operatorname{OEM}(8,8)$ im Sortiernetzwerk in Abbildung~\ref{fig:16-ec-from-ps32} eindeutig erkennbar (Schichten~7--10). In @@ -1462,14 +1553,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} @@ -1478,6 +1561,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} @@ -1488,21 +1593,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} @@ -1531,9 +1665,9 @@ selbst erzeugen kann. 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 -wurden jedoch bereits bis zu $2,6 \cdot 10^8$ unterschiedliche Schnittmuster -geschätzt. +Nachfolger zwar noch unter 20.000, bei den untersuchten +32-Sortier\-netz\-werken wurden jedoch bereits bis zu $2,6 \cdot 10^8$ +unterschiedliche Schnittmuster geschätzt. Der Algorithmus {\sc SN-Markov} legt auf diesem Nachfolger-Graph einen zufälligen Weg (englisch: \textit{random walk}) zurück. Er startet auf einem @@ -1543,94 +1677,256 @@ selbst und erhält so einen zufälligen Nachfolger. In Pseudocode lässt dich de Algorithmus wie folgt beschreiben: \begin{verbatim} -Netzwerk := Eingabe + Netzwerk := Eingabe + + für n Iterationen + { + Nachfolger := kombiniere (Netzwerk, Netzwerk) + Netzwerk := Nachfolger + } + + gib Netzwerk zurück +\end{verbatim} -für n Iterationen -{ - Nachfolger := kombiniere (Netzwerk, Netzwerk) - Netzwerk := Nachfolger -} +Die Graphen in Abbildung~\ref{fig:markov-comparators} zeigen die Anzahl der +Komparatoren der Sortiernetzwerke, die \textsc{SN-Markov} auf seinem +zufälligen Pfad durchläuft (rot). Für jeden Graphen wurde der +\textsc{SN-Markov}-Algorithmus auf einem entsprechenden +\emph{Odd-Even-Transporitionsort}-Netzwerk gestartet hat mindestens +1.000.000~Iterationen durchlaufen. In jedem Schritt wurde die Anzahl der +Komparatoren des Sortiernetzwerks bestimmt und ein entsprechender Zähler +erhöht. In Abbildung~\ref{fig:markov-comparators} ist die resultierende +prezenturale Verteilung zu sehen. + +Ebenfalls in die Graphen in Abbildung~\ref{fig:markov-comparators} +eingezeichnet ist eine \emph{Gamma-Verteilung} (grün), die die gemessenen +Daten gut annähert. Die Gamma-Verteilung verwendet einen Offset~$\delta$, der +um Eins kleiner als die kleinste erreichte Komparatorzahl gewählt wurde. +Beispielsweise war die kleinste erreichte Komparatorzahl bei +16-Sortiernetzwerken~63, entsprechend wurde der Offset $\delta = 63 - 1$ +gesetzt und die Gamma-Verteilung $g(x - 62)$ eingezeichnet. Die Parameter $k$ +und $\theta$, die eine Gamma-Verteilung charakterisieren, wurden mit einem +Fitting-Algorithmus bestimmt. Der konkrete Offset ist als Parameter~$\delta$ +unter den Graphen angegeben. -gib Netzwerk zurück -\end{verbatim} +\begin{figure} + \centering + \subfigure[12 Leitungen, $k = 8,267$, $\theta = 0,962$, $\delta = 40$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-12-pct.pdf}} + \subfigure[14 Leitungen, $k = 9,522$, $\theta = 0,867$, $\delta = 52$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-14-pct.pdf}} + \subfigure[16 Leitungen, $k = 17,939$, $\theta = 1,091$, $\delta = 62$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-16-pct.pdf}} + \subfigure[18 Leitungen, $k = 10,724$, $\theta = 0,766$, $\delta = 81$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-18-pct.pdf}} + \caption{Anzahl der Komparatoren von Sortiernetzwerken, + die von {\sc SN-Markov} durchlaufen wurden (rot). Ebenfalls eingezeichnet + ist jeweils eine \emph{Gamma-Verteilung} (grün), die eine gute Näherung der + gemessenen Daten darstellt.} + \label{fig:markov-comparators} +\end{figure} \begin{figure} \begin{center} - \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-cycles-16.pdf} + \includegraphics[viewport=0 0 425 262,width=15cm]{images/comparison-comparators-16.pdf} \end{center} - \caption{Zyklen, die beim \textit{Random Walk} des - \textsc{SN-Markov}-Algorithmus detektiert wurden. Auf der x-Achse sind die - Anzahl der Schritte, die \textsc{SN-Markov} zurückgelegt hat, auf der - y-Achse die Längen der gefundenen Zyklen aufgetragen. Das initiale - Start-Sortiernetzwerk war $\operatorname{OET}(16)$.} - \label{fig:markov-cycles-16} + \caption{Anzahl der Komparatoren, die 16-Sortiernetzwerke von + \textsc{SN-Markov} und \textsc{SN-Evolution} (mit dem + \emph{Odd-Even}-Mischer und dem \emph{bitonen Mischer}) besaßen.} + \label{fig:comparison-comparators} \end{figure} +Dass der \textsc{SN-Markov}-Algorithmus nicht schlechter ist als der +\textsc{SN-Evolution}-Algo\-rithmus, ist aus dem Graphen in +Abbildung~\ref{fig:comparison-comparators} ersichtlich. Analog zu dem Versuch +mit \textsc{SN-Markov}, wurde beim \textsc{SN-Evolution}-Algorithmus die +Anzahl der Komparatoren jedes neuen Individuums ermittelt und gespeichert. Als +Startnetzwerk diente bei beiden Algorithmen das +\emph{Odd-Even-Transpositionsort}-Netzwerk \oet{16}. Der Graph zeigt auf der +x-Achse die Anzahl der Komparatoren, auf der y-Achse die Häufigkeit, mit der +ein Sortiernetzwerk mit dieser Komparatorzahl durch die Rekombination erzeugt +wurde. Die Ergebnisse von \textsc{SN-Evolution} unterscheiden außerdem nach +dem verwendeten Mischer-Netzwerk -- \oem{32} beziehungsweise \bm{32}. + +Sowohl der \textsc{SN-Markov}-Algorithmus, der das +\emph{Odd-Even-Merge}-Netzwerk verwendet, als auch \textsc{SN-Evolution} mit +\oem{32} erreichen eine Komparatorzahl von~63 und finden Sortiernetzwerke, die +bezüglich Effizienz und Geschwindigkeit identisch zu \oes{16} sind. +Interessanterweise erzeugt \textsc{SN-Markov} derartige Netzwerke häufiger: +Während nur $0,000017 \%$ der Individuen von \textsc{SN-Evolution} mit +63~Komparatoren auskamen, ist die Rate bei \textsc{SN-Markov} mit $0,000335 +\%$ rund 20~mal höher. + +Erwartunggemäß sind die besten Netzwerke, die \textsc{SN-Evolution} mit dem +\emph{bitonen Mischer} findet, aus 67~Komparatoren aufgebaut. Überraschend ist +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 +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 +ein Phänomen, das mit der Initialisierung mit dem +\emph{Odd-Even-Transpositionsort}-Netzwerk zusammenhängt. + +%\begin{figure} +% \begin{center} +% \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-14-pct.pdf} +% \end{center} +% \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 14~Leitungen), +% die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die +% \emph{Gamma-Verteilung} $f(x - 52)$ mit $k = 9,522$ und $\theta = 0,867$.} +% \label{fig:markov-comparators-14} +%\end{figure} +% +%\begin{figure} +% \begin{center} +% \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-16-pct.pdf} +% \end{center} +% \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 16~Leitungen), +% die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die +% \emph{Gamma-Verteilung} $f(x - 62)$ mit $k = 17,939$ und $\theta = 1,091$.} +% \label{fig:markov-comparators-16} +%\end{figure} +% +%\begin{figure} +% \begin{center} +% \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-18-pct.pdf} +% \end{center} +% \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 18~Leitungen), +% die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die +% \emph{Gamma-Verteilung} $f(x - 81)$ mit $k = 10,724$ und $\theta = 0,766$.} +% \label{fig:markov-comparators-18} +%\end{figure} + +%\begin{figure} +% \begin{center} +% \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-cycles-16.pdf} +% \end{center} +% \caption{Zyklen, die beim \textit{Random Walk} des +% \textsc{SN-Markov}-Algorithmus detektiert wurden. Auf der x-Achse sind die +% Anzahl der Schritte, die \textsc{SN-Markov} zurückgelegt hat, auf der +% y-Achse die Längen der gefundenen Zyklen aufgetragen. Das initiale +% Start-Sortiernetzwerk war $\operatorname{OET}(16)$.} +% \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 Anzahl der Komparatoren und Anzahl der Schichten der durchlaufenen Netzwerke. (Abbildung~\ref{fig:markov-comparators-16}) + \item \textsc{SN-Count-Markov} (ggf) \end{itemize} -\begin{figure} - \begin{center} - \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-12-pct.pdf} - \end{center} - \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 12~Leitungen), - die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die - \emph{Gamma-Verteilung} $f(x - 40)$ mit $k = 8,267$ und $\theta = 0,962$.} - \label{fig:markov-comparators-12} -\end{figure} - -\begin{figure} - \begin{center} - \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-14-pct.pdf} - \end{center} - \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 14~Leitungen), - die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die - \emph{Gamma-Verteilung} $f(x - 52)$ mit $k = 9,522$ und $\theta = 0,867$.} - \label{fig:markov-comparators-14} -\end{figure} - -\begin{figure} - \begin{center} - \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-16-pct.pdf} - \end{center} - \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 16~Leitungen), - die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die - \emph{Gamma-Verteilung} $f(x - 62)$ mit $k = 17,939$ und $\theta = 1,091$.} - \label{fig:markov-comparators-16} -\end{figure} - -\begin{figure} - \begin{center} - \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-18-pct.pdf} - \end{center} - \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 18~Leitungen), - die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die - \emph{Gamma-Verteilung} $f(x - 81)$ mit $k = 10,724$ und $\theta = 0,766$.} - \label{fig:markov-comparators-18} -\end{figure} - \newpage -\section{Empirische Beobachtungen} +\section{Fazit und Ausblick} +\todo{Ausformulieren} \begin{itemize} -\item So schnell konvergiert der Algorithmus. -\item $\ldots$ +\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} -\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{Ausblick: Das \textit{Pairwise-Sorting}-Netzwerk und \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{Ausblick: 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}