\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}
\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.
\newpage
\tableofcontents
-\newpage
+\newpage
\section{Motivation und Einleitung}
\subsection{Motivation}\label{sect:motivation}
\subsubsection{Sortiernetzwerke}\label{sect:einleitung_sortiernetzwerke}
-{\em Komparatoren} sind die Bausteine, die {\em Sortiernetzwerken} zugrunde
-liegen. Sie haben zwei Eingänge über die sie zwei Zahlen erhalten können.
-Ausserdem besitzt ein {\em Komparator} zwei Ausgänge, die im Gegensatz zu den
-Eingängen unterscheidbar sind: Die grö"sere der beiden Zahlen wird immer auf
-dem einen, die kleinere der beiden Zahlen immer auf dem anderen Ausgang
-ausgegeben.
+\emph{Komparatoren} sind die Bausteine, die \emph{Komparatornetzwerken}
+zugrunde liegen. Sie haben zwei Eingänge über die sie zwei Zahlen erhalten
+können und zwei Ausgänge, auf denen die Zahlen wieder ausgegeben werden. Dabei
+sind die Ausgänge im Gegensatz zu den Eingängen unterscheidbar, da die größere
+der beiden Zahlen wird immer auf dem einen, die kleinere der beiden Zahlen
+immer auf dem anderen Ausgang ausgegeben ausgegeben wird.
-Wenn man nun mehrere {\em Komparatoren} miteinander kombiniert, also die
-Ausgänge von Komparatoren mit dem Eingängen anderer Komparatoren verbindet,
+Kombiniert man mehrere \emph{Komparatoren} miteinander, das heißt, dass die
+Ausgänge eines Komparators mit Eingängen weiterer Komparatoren verbunden sind,
erhält man ein {\em Komparatornetzwerk}.
\begin{figure}
\end{figure}
Abbildung~\ref{fig:einfaches_komparatornetzwerk} zeigt ein einfaches
-Komparatornetzwerk aus fünf Komparatoren in der üblichen Darstellungsweise:
-Die horizontalen Linien stellen Leitungen von den Eingängen auf der linken
-Seite zu den Ausgängen auf er rechten Seite dar. Die vertikalen Pfeile
-symbolisieren die Komparatoren, die die Werte "`auf den Leitungen"'
-vergleichen und ggf. vertauschen. Nach einem Komparator befindet sich die
+\emph{Komparatornetzwerk} aus fünf Komparatoren. Insgesamt gibt es vier
+verschiedene Eingänge und vier Ausgänge. Die Ein- und Ausgänge werden durch
+eine horizontale Linie dargestellt und als \emph{Leitung} bezeichnet. Die
+\emph{Komparatoren} sind durch vertikale Pfeile dargestellt und verbinden je
+zwei verschiedene \emph{Leitungen} miteinander. Die Verbindungsstellen von
+\emph{Leitungen} und \emph{Komparatoren} sind zur besseren Übersichlichkeit
+durch schwarze Punkte symbolisiert.
+
+Auf der linken Seite befinden sich die Eingänge. Hier wird eine Zahlenfolge in
+das Netzwerk hineingegeben. Jeder Komparator vergleicht die Zahlen „auf“ den
+beiden Leitungen, die er verbindet. Nach einem Komparator befindet sich die
kleinere Zahl immer auf der Leitung, auf die der Pfeil zeigt, die größere Zahl
-befindet sich auf der Leitung auf der der Pfeil seinen Ursprung hat.
+befindet sich auf der Leitung, auf der der Pfeil seinen Ursprung hat.
Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
gleichzeitig angewandt werden. Das Beispiel in
Abbildung~\ref{fig:einfaches_komparatornetzwerk} verwendet diesen Umstand und
-vergleicht in einem ersten Schritt die zwei oberen und die zwei unteren
-Leitungen gleichzeitig. Eine Gruppe von Komparatoren, die gleichzeitig
-angewendet werden können, nennt man eine \emph{Schicht} des
-Komparatornetwerks. Die \emph{Verzögerung} eines Komparatornetzwerks ist
-gleichbedeutend mit der Anzahl der Schichten, in die sich die Komparatoren
-mindestens gruppieren lassen, da sie die Anzahl der benötigten parallelen
-Schritte darstellt.
-
-Komparatornetzwerke, die für jede beliebige Eingabepermutation eine
-Ausgabe erzeugen, die der Sortierung der Eingabe entspricht, heißen
-{\em Sortiernetzwerke}. Das in
+vergleicht die zwei oberen und die zwei unteren Leitungen gleichzeitig. Eine
+Gruppe von Komparatoren, die gleichzeitig angewendet werden können, nennt man
+eine \emph{Schicht} des Komparatornetwerks. Die \emph{Verzögerung} eines
+Komparatornetzwerks ist gleichbedeutend mit der Anzahl der Schichten, in die
+sich die Komparatoren mindestens gruppieren lassen, da sie die Anzahl der
+benötigten parallelen Schritte darstellt.
+
+\emph{Komparatornetzwerke}, die für \emph{jede} Eingabefolge eine Ausgabe
+erzeugen, die der Sortierung der Eingabe entspricht, heißen
+\emph{Sortiernetzwerke}. Das in
Abbildung~\ref{fig:einfaches_komparatornetzwerk} gezeigte Komparatornetzwerk
-ist kein Sotiernetzwerk: Die Eingabefolge ${(1, 2, 3, 4)}$ würde zur Ausgabe
-${(2, 1, 3, 4)}$ führen -- die bestehenden Sortierung wird also sogar
+ist \emph{kein} Sotiernetzwerk: Die Eingabefolge ${(1, 2, 3, 4)}$ führt zur
+Ausgabe ${(2, 1, 3, 4)}$ -- die bestehenden Sortierung wird also sogar
zerstört.
-Zu beweisen, dass ein gegebenes Komparatornetzwerk die Sortiereigenschaft
-{\em nicht} hat, ist mit einem gegebenen Gegenbeispiel einfach möglich.
-Dieses Gegenbeispiel zu finden ist allerdings aufwendig.
-
-\todo{Wie findet man die Gegenbeispiele? Die {\em Entscheidung}, ob ein
-Netzwerk sortiert, ist doch NP-vollständig, also müsste doch das Finden eines
-Gegenbeispiels im Allgemeinen auch exponentialle Laufzeit haben..?}
-\todo{Wenn die {\em Entscheidung}, ob ein Netzwerk sortiert, NP-vollständig
-ist, müsse man dann nicht einen Zeugen für die Sortiereigenschaft angeben
-können?}
-
-\todo{$0-1$-Prinzip}
-
-Um zu überprüfen, ob ein gegebenes Komparatornetzwerk die Sortiereigenschaft
-besetzt, müssen nicht alle $n!$ Permutationen von $n$~unterschiedlichen Zahlen
-ausprobieren. Stattdessen reicht es zu überprüfen, dass das Netzwerk alle
-$2^n$~0-1-Folgen sortiert.
-
-Sortiernetzwerke:
-\begin{itemize}
-\item Ein Komparator-Netzwerk ist $\ldots$
-\item Ein Komparator-Netzwerk ist ein Sortiernetzwerk, wenn $\ldots$
-\item Die Frage nach der Sortiereigenschaft ist NP-vollständig.
-\end{itemize}
+\begin{figure}
+ \begin{center}
+ \input{images/09-e2-c24-allbut1.tex}
+ \end{center}
+ \caption{Ein \emph{Komparatornetzwerk} mit neun Eingängen und
+ 24~Komparatoren, die in 8~Schichten angeordnet sind. Das Netzwerk sortiert
+ alle Eingaben, bei denen das Minimum nicht auf dem mittleren Eingang liegt.}
+ \label{fig:09-e2-c24-allbut1}
+\end{figure}
+Zu beweisen, dass ein gegebenes Komparatornetzwerk die Sortiereigenschaft {\em
+nicht} hat, ist mit einem gegebenen Gegenbeispiel einfach möglich. Das
+Komparatornetzwerk wird auf das Gegenbeispiel angewendet und anschließend wird
+überprüft, ob die Ausgabe sortiert ist. Ist sie es nicht heißt das, dass es
+mindestens eine Eingabefolge gibt, die nicht sortiert wird. Entsprechend der
+Definition handelt es sich bei dem \emph{Komparatornetzwerk} folglich
+\emph{nicht} um ein \emph{Sortiernetzwerk}. Ein solches Gegenbeispiel für ein
+gegebenes Komparatornetzwerk zu finden ist nach heutigem Kenntnisstand jedoch
+nicht \emph{effizient} möglich.
+
+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
+Permutationen auf die sortierte Reihenfolge ab. Allerdings wächst $n!$
+über-exponentiell schnell, so dass ein Ausprobieren aller möglichen
+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
+Permutation $E = (e_0, \dots, e_{n-1})$ beliebiger Zahlen, die nicht sortiert
+wird. Die Ausgabefolge sei $A = (a_0, \dots, a_{n-1})$. Sei $i$ eine Position
+in der Ausgabe, die die Sortierbedingung verletzt:
+\begin{displaymath}
+ a_0 \leqq a_1 \leqq \dots \leqq a_{i-1} > a_i \dots
+\end{displaymath}
+Die Eingabe kann mittels
+\begin{displaymath}
+ \hat{e}_j = \left\{
+ \begin{array}{cl}
+ 0 & e_j \leqq a_i \\
+ 1 & e_j > a_i
+ \end{array} \right.
+\end{displaymath}
+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: 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
+$\mathcal{O}\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ zuzuordnen ist,
+ist das Überprüfen aller 0-1-Folgen „nur“ mit dem Aufwand $\mathcal{O}(2^n)$
+verbunden. Entsprechend ist dieses Verfahren nicht \emph{effizient} -- ein
+schnelleres Verfahren ist bisher allerdings nicht bekannt. Um zu überprüfen,
+ob ein Komparatornetzwerk mit 16~Leitungen die Sortiereigenschaft besitzt,
+sind mit dieser Methode nur 65.536 Tests notwendig -- eine Zahl, die für
+aktuelle Prozessoren keine Herausforderung darstellt. Für die Überprüfung
+eines Komparatornetzwerks mit 32~Leitungen sind jedoch bereits etwa
+4,3~Millarden Tests notwendig, die einen Rechner durchaus mehrere Minuten
+beschäftigen.
\subsubsection{Evolutionäre Algorithmen}
Viele {\em kombinatorische Optimierungsprobleme} sind schwer zu lösen -- die
entsprechenden Entscheidungsprobleme liegen oft in der Komplexitätsklasse
-$NP$, sind also mit bekannten Verfahren nicht effizient exakt lösbar. Sollte
-sich herausstellen, dass diese Probleme nicht in der Komplexitätsklasse $P$
-liegen, wäre eine Konsequenz, dass es effiziente exakte Algorithmen für diese
-Probleme nicht geben kann. Falls sich hingegen herausstellt, dass diese
-Probleme in der Komplexitätsklasse~$P$ liegen, wird es mit großer
-Wahrscheinlichkeit noch einige Zeit dauern bis auch Algorithmen mit
-praktikablen Zeitkonstanten gefunden werden.
+\textit{NP}, das heißt das keine Verfahren bekannt sind, die das Problem
+effizient exakt lösbar. Sollte sich herausstellen, dass diese Probleme nicht
+in der Komplexitätsklasse~\textit{P} liegen, wäre eine Konsequenz, dass es
+effiziente exakte Algorithmen für diese Probleme nicht geben kann. Falls sich
+hingegen herausstellt, dass diese Probleme in der
+Komplexitätsklasse~\textit{P} liegen, wird es mit großer Wahrscheinlichkeit
+noch einige Zeit dauern, bis auch Algorithmen mit praktikablen Zeitkonstanten
+gefunden werden.
Aus diesem Grund besteht die Notwendigkeit einen Kompromiss einzugehen: Statt
-die bzw. eine der {\em optimalen} Lösungen als einzige Ausgabe des Algorithmus
-zuzulassen, wird eine "`möglichst gute"' Lösung ausgegeben. Viele dieser
-Optimierungsalgorithmen orientieren sich an Vorgängen in der Natur,
-beispielsweise immitieren die "`Ameisenalgorithmen"' das Verhalten von Ameisen
+die beziehungsweise eine der {\em optimalen} Lösungen als einzige Ausgabe des
+Algorithmus zuzulassen, wird eine "`möglichst gute"' Lösung ausgegeben. Viele
+dieser Optimierungsalgorithmen orientieren sich an Vorgängen in der Natur,
+beispielsweise imitieren die "`Ameisenalgorithmen"' das Verhalten von Ameisen
auf der Futtersuche um kurze Rundreisen auf Graphen zu berechnen.
Bei {\em Evolutionären Algorithmen} stand die Evolution pate. Die Grundidee
-ist es, bestehende Lösungen zu neuen, unter Umständen besseren Lösungen zu
+ist, bekannte Lösungen zu neuen -- unter Umständen besseren -- Lösungen zu
kombinieren. Dabei bedient man sich der in der Evolutionstheorie etablierten
-Nomenklatur, beispielsweise werden konkrete Lösungen für ein Problem häufig
-als {\em Individuum} bezeichnet.
+Nomenklatur, beispielsweise werden konkrete Lösungen für ein Problem als {\em
+Individuen} bezeichnet.
Die Vorgehensweise lässt sich abstrakt wie folgt beschreiben. Aus einer
-bestehenden Lösungsmenge, der {\em Population} werden zufällig Lösungen
+bestehenden Lösungsmenge, der {\em Population}, werden zufällig Lösungen
ausgesucht {\em (Selektion)} und zu einer neuen Lösung kombiniert ({\em
Rekombination}). Unter Umständen wird die neue Lösung noch zufällig
verändert {\em (Mutation)}, bevor sie in die bestehende Lösungsmenge
-integriert wird. Die Wahrscheinlichkeiten, beispielsweise bei der {\em
-Selektion}, sind dabei nicht zwangsläufig gleichverteilt -- üblicherweise
-werden bessere Lösungen bevorzugt. Zur Bewertung die die sogenannte {\em
+eingefügt wird. Die verwendeten Wahrscheinlichkeiten, beispielsweise bei der
+{\em Selektion}, sind dabei nicht zwangsläufig gleichverteilt -- üblicherweise
+werden bessere Lösungen bevorzugt. Zur Bewertung dient die sogenannte {\em
Gütefunktion}.
Nicht alle Probleme eignen sich für diese Strategie: Zum einen muss es möglich
sein, eine initiale Population zur Verfügung zu stellen, da diese als Basis
aller weiteren Operationen dient. Das ist häufig keine große Einschränkung, da
-es oft einfach ist {\em irgendeine} Lösung anzugeben. Zum anderen muss eine
-Methode für die Rekombination existieren. Das insbesondere dann problematisch
-wenn {\em Nebenbedingungen} eingehalten werden müssen.
-
-\begin{itemize}
-\item Unter einem "`Evolutionären Algorithmus"' versteht man $\ldots$
-\item Da die Sortiereigenschaft zu überprüfen NP-schwer ist, ist die
-Mutation \textit{(vermutlich)} nicht (effizient) möglich.
-\end{itemize}
+es oft einfach ist {\em irgendeine} Lösung anzugeben. Die angegebenen
+Algorithmen verwenden als einfache, initiale Lösung häufig das
+\emph{Odd-Even-Transpositionsort}-Netzwerk, das in
+Abschnitt~\ref{sect:odd_even_transpositionsort} beschrieben wird. Zum anderen
+muss eine Methode für die Rekombination existieren. Das ist insbesondere dann
+problematisch, wenn {\em Nebenbedingungen} eingehalten werden müssen.
+
+Beim Aussuchen von zufälligen Lösungen aus der Population, der
+\emph{Selektion}, werden gute Lösungen bevorzugt. Wie sehr diese Lösungen
+bevorzugt werden, hat einen starken Einfluss auf das Verhalten des
+Algorithmus. Werden gute Lösungen stark bevorzugt, konvergiert der Algorithmus
+schnell gegen ein (lokales) Optimum. Dieses \textit{Exploitation} (Englisch
+für „Ausnutzung“) genannte Verhalten sorgt dafür, dass sich der Algorithmus
+schnell auf eine Lösung festlegt und andere, möglicherweise bessere lokale
+Optima nicht mehr findet. Werden gute Lösungen hingegen nur wenig bevorzugt,
+erforscht der Algorithmus den Lösungsraum in viele Richtungen. Dieses
+\textit{Exploration} (Englisch für „Erforschung“) genannte Verhalten sorgt
+zwar dafür, dass der Algorithmus langsamer auf ein Optimum zusteuert, dafür
+findet er aber in der Regel bessere Lösungen.
+
+Die Parameter evolutionärer Algorithmen so einzustellen, dass sich ein guter
+Mittelweg zwischen den beiden Extremen einstellt, ist eine Aufgabe, die sich
+nur experimentell lösen lässt. Die genauen Parameter hängen nicht nur vom
+eigentlichen Algorithmus, sondern auch vom konkreten Problem ab, so dass sich
+beispielsweise bei der Optimierung von Sortiernetzwerken die Parameter
+zwischen verschiedenen Leitungszahlen stark unterscheiden.
+
+Die \textit{Exploration} kann von einem weiteren Mechanismus unterstützt
+werden, der ebenfalls der Evolutionslehre entliehen ist, der \emph{Mutation}.
+Dabei werden Lösungen zufällig verändert, so dass auch andere Lösungen „in der
+Nähe“ von direkten Nachfolgern erreicht werden können. Das hilft insbesondere
+bei der intensiven Suche in der Nähe eines lokalen Optimums aber auch beim
+„Ausbrechen“ und finden noch besserer Lösungen.
+
+Bei \emph{Sortiernetzwerken} ist eine \emph{Mutation} leider immer damit
+verbunden, dass anschließend die Sortiereigenschaft des resultierenden
+\emph{Komparatornetzwerks} wieder überprüft werden muss, da selbst das
+Hinzufügen eines zufälligen Komparators diese Eigenschaft zerstören kann. Beim
+Suchen möglichst effizienter Netzwerke ist natürlich das zufällige Entfernen
+von Komparatoren interessanter, was die Sortiereigenschaft sehr oft aufhebt.
+
+Die im Folgenden beschriebenen Algorithmen mutieren (verändern) daher nicht
+die \emph{Sortiernetzwerke} selbst, sondern verzichten auf Mutation oder
+mutieren lediglich Transformationen von Sortiernetzwerken, die die
+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.
+\newpage
\section{Bekannte konstruktive Sortiernetzwerke}
+\label{sect:konstruktive_netzwerke}
Übersicht über bekannte konstruktive Sortiernetzwerke.
Schichten, zum Beispiel $\mathcal{O}(\log n)$, angeordnet sind.
Das Interessante am OET-Netzwerk ist seine einfache Konstruktion. Einige der
-folgenden Algorithmen benötigen ein (einfaches) Sortiernetzwerk als
+folgenden Algorithmen benötigen ein möglichst einfaches Sortiernetzwerk als
Starteingabe, auf dessen Basis sie versuchen optimierte Sortiernetzwerke zu
finden. Häufig dient $\operatorname{OET}(n)$ als Eingabe für diese
Algorithmen.
Das \emph{bitone Mergesort}-Netzwerk ($\operatorname{BS}(n)$) ist ein
Sortiernetzwerk, das 1968 von \emph{Kenneth~E. Batcher} in~\cite{B1968}
veröffentlicht wurde. Es ist deutlich effizienter als das
-Odd-Even-Transporitionsort-Netzwerk -- sowohl in Bezug auf die Anzahl der
+Odd-Even-Transposi\-tionsort-Netzwerk -- sowohl in Bezug auf die Anzahl der
Komparatoren als auch bezüglich der benötigten Zeit, also der Anzahl der
Schichten.
verleiht dem Sortiernetzwerk seinen Namen.
Da das Sortiernetzwerk rekursiv definiert ist, betrachten wir hier nur die
-Instanzen des Netzwerks, deren Leitungszahl eine Zweierpotenz ist,
-$\operatorname{BS}(n = 2^t)$.
+Instanzen des Netzwerks, deren Leitungszahl $n = 2^t$ eine Zweierpotenz ist.
+Es ist jedoch möglich das Sortiernetzwerk für beliebige~$n$ zu erzeugen.
\subsubsection{Der bitone Mischer}\label{sect:der_bitone_mischer}
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
-Umständen mehr Schichten als der \emph{bitone Mischer}.\footnote{Knuth,
-“Bitonic Sorting”, Seite~230}
+Umständen mehr Schichten als der \emph{bitone Mischer}.~\cite{KNUTH}
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
\subsubsection{Das Odd-Even-Mergesort-Netzwerk}
-Das \emph{Odd-Even-Mergesort-Netzwerk} $\operatorname{OES}(n)$ besteht, --~wie
-das \emph{bitonen Mergesort-Netzwerk}~-- rekursiv aus kleineren Varianten von
+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
-effizientesten Sortiernetzwerke in Bezuf auf Komparator- und Schichtzahl
+effizientesten Sortiernetzwerke in Bezug auf Komparator- und Schichtzahl
entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht
$\operatorname{OES}(n)$ aus
$\operatorname{OES}\left(\left\lceil\frac{n}{2}\right\rceil\right)$,
die Komparatoren, die in ersten Rekursionsschritt hinzugefügt werden.
Im Allgemeinen ist die Anzahl der Komparatoren, die vom
-\emph{Odd-Even-Mergesort-Netzwerk} verwendet wird, $k(n)$, direkt aus der
+\emph{Odd-Even-Mergesort-Netz\-werk} verwendet wird, $k(n)$, direkt aus der
Definition beziehungsweise der Konstruktionsanleitung abzulesen:
\begin{displaymath}
k(n) = k\left(\left\lceil\frac{n}{2}\right\rceil\right)
$k(n)$ in $\mathcal{O}\left(n \left(\log (n)\right)^2\right)$ enthalten ist.
Für den wichtigen Spezialfall, dass $n = 2^t$ eine Zweierpotenz ist, kann die
-Anzahl der Komparatoren wieder explizit angegeben werden. \textit{K.~Batcher}
-zeigt in seiner Arbeit\footnote{\todo{Referenz!}}, dass in diesem Fall
+Anzahl der Komparatoren wieder explizit angegeben werden. \textit{Kenneth
+Batcher} zeigt in~\cite{B1968}, dass in diesem Fall
\begin{displaymath}
k(n = 2^t) = \frac{1}{4} n \left(\log (n)\right)^2 - \frac{1}{4}n\log(n) + n - 1
\end{displaymath}
%\item Pairwise sorting-network
%\end{itemize}
+\newpage
\section{Transformation von Sortiernetzwerken}
+\label{sect:tranformation}
\subsection{Komprimieren}
-\todo{Aus theoretischer Sicht eigentlich eine Trivialität. Rausschmeißen?}
-
Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
gleichzeitig ausgewertet werden, wie bereits in
-Abschnitt~\ref{sect:einleitung_sortiernetzwerke} beschrieben. Unter
-\emph{Komprimieren} wird eine (Neu-)Gruppierung in die kleinstmögliche Anzahl
-von \emph{Schichten} verstanden.
+Abschnitt~\ref{sect:einleitung_sortiernetzwerke} beschrieben. Durch manche
+Transformationen, insbesondere das Entfernen einer Leitung, das in
+Abschnitt~\ref{sect:leitungen_entfernen} beschrieben wird, kann es vorkommen,
+dass die Komparatoren eines Sortiernetzwerks nicht mehr in der
+kleinstmöglichen Anzahl von \emph{Schichten} angeordnet sind. Unter
+\emph{Komprimierung} wird eine (Neu-)Gruppierung der Komparatoren verstanden,
+die jeden Komparator so früh wie möglich ausführt. So entsteht die
+kleinstmögliche Anzahl von \emph{Schichten}, in die sich ein Sortiernetzwerk
+unterteilen lässt.
Diese Anzahl ist insbesondere beim automatisierten Bewerten von
-Komparatornetzwerken interessant. \dots
+Komparatornetzwerken interessant, wie in Abschnitt~\ref{sect:bewertung}
+beschrieben. Die Anzahl der Schichten kann künstlich vergrößert werden, indem
+Komparatoren später angewandt werden. Deshalb sollte vor einer Bewertung, die
+die Anzahl der Schichten als Bewertungskriterium verwendet, immer eine
+Komprimierung durchgeführt werden.
\subsection{Normalisieren}
Ein \emph{Standard-Sortiernetzwerk} oder \emph{normalisiertes Sortiernetzwerk}
ist ein Sortiernetzwerk, dessen Komparatoren alle in die selbe Richtung
zeigen. Jedes Sortiernetzwerk kann in eine normaliesierte Variante
-transformiert werden. Dazu gibt beispielsweise \emph{Knuth} (\todo{Verweis})
-einen Algorithmus an.
+transformiert werden. Dazu gibt beispielsweise \emph{Donald~E. Knuth}
+in~\cite{KNUTH} einen Algorithmus an.
Abbildung~\ref{fig:beispiel_normalisieren} zeigt das das
bitone Sortiernetzwerk in zwei Varianten. Abbildung~\ref{fig:bitonic-nonstd}
\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{Baddar} und
-\textit{Batcher} in ihrer Arbeit „An 11-Step Sorting Network for 18~Elements“
-vorstellen, benötigt aber 6~Komparatoren weniger.
+schnell wie das Sortiernetzwerk mit 18~Eingängen, das \textit{Sherenaz~W.
+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
%\item Nach dem Pairwise sorting-network Schema.
%\end{itemize}
-\subsection{Leitungen entfernen}\label{sect:leitungen_entfernen}
+\subsection{Leitungen entfernen}
+\label{sect:leitungen_entfernen}
Im vorherigen Abschnitt haben wir gesehen, dass es mithilfe von
\emph{Mischern} möglich ist, aus zwei Sortiernetzwerken mit je $n$~Eingängen
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 wir auf diese Art und
-Weise einen Sortiernetzwerk mit $2n$~Eingängen wieder auf ein Sortiernetzwerk
-mit $n$~Eingängen reduzieren. Das Anwenden mehrerer Minimum- und
-Maximum-Schnitte bezeichnen wir als \emph{Schnittmuster}.
+$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
+nacheinander angewendet ein $n$-Sortiernetzwerk auf ein
+${(n-k)}$-Sortiernetz\-werk reduzieren, bezeichnen wir als
+\emph{$k$-Schnittmuster}.
Zwei Schnittmuster heißen \emph{äquivalent} bezüglich~$S$, wenn ihre Anwendung
auf das Sortiernetzwerk~$S$ das selbe Ergebnis liefert. Ansonsten heißen die
Bei einem Sortiernetzwerk mit $n$~Eingängen gibt es $2n$~Möglichkeiten eine
Leitung zu entfernen: Auf jeder der $n$~Leitungen kann sowohl das Minimum als
auch das Maximum angenommen werden. Wendet man das Verfahren iterativ an, um
-ein $n$-Sortiernetzwerk auf ein $m$-Sortiernetzwerk zu reduzieren, ergeben
-sich insgesamt
-\begin{displaymath}
- \prod_{i=n}^{m+1} 2i = 2^{n-m} \frac{n!}{m!}
+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 \cdot \frac{n!}{(n-k)!}
\quad (n > m)
-\end{displaymath}
+\end{equation}
\emph{mögliche} Schnittmuster. Diese Schnittmuster sind nicht alle
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 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, $n-m$~Leitungen aus $n$ Leitungen auszuwählen,
-und die möglichen Minimum-~/ Maximum-Muster. Damit ergibt sich folgende
-Formel für die Anzahl der Schnittmuster:
+\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:
\begin{displaymath}
- 2^{n-m} \cdot \left( \begin{array}{c} n \\ n-m \end{array} \right)
- = 2^{n-m} \cdot \frac{n!}{(n-m)! m!}
- = 2^{n-m} \cdot \frac{n!}{m!} \cdot \frac{1}{(n-m)!}
- \quad (n > m)
+ 2^k \cdot \left( \begin{array}{c} n \\ k \end{array} \right)
+ = 2^{k} \cdot \frac{n!}{k! (n-k)!}
+ = 2^{k} \cdot \frac{n!}{(n-k)!} \cdot \frac{1}{k!}
+ \quad (1 \leqq k < n)
\end{displaymath}
Die Anzahl der möglichen Schnittmuster wird mit der Anzahl der zu entfernenden
Eingänge unterscheiden, wird anschließend der Komparator entfernt, so dass
sich die Resultate auch in der ersten Schicht nicht unterscheiden.
-\subsubsection{Der \textsc{SN-Evolution-Cut}-Algorithmus}
+\begin{figure}
+ \begin{center}
+ \includegraphics[viewport=0 0 425 262,width=15cm]{images/count-cuts-16.pdf}
+ \end{center}
+ \caption{Anzahl der \emph{unterschiedlichen} Sortiernetzwerke, die durch
+ 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}.}
+ \label{fig:count-cuts-16}
+\end{figure}
+
+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 \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
+Schnittmuster auf. Klar zu sehen ist, dass sich die Anzahl der erzeugten
+Sortiernetzwerke nach $500.000$~Iterationen nur noch gering verändert und der
+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~\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 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 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.
+
+\begin{figure}
+ \begin{center}
+ \includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-10000-1000000-32.pdf}
+ \end{center}
+ \caption{Abschnätzung der unterschiedlichen Schnittmuster mit der
+ \emph{Monte-Carlo-Methode} für $\operatorname{OES}(32)$ und
+ $\operatorname{BS}(32)$.}
+ \label{fig:collisions-10000-1000000-32}
+\end{figure}
+
+In Abbildung~\ref{fig:collisions-10000-1000000-32} ist das Ergebnis des
+Monte-Carlo-Algorithmus für 16-Schnittmuster zu sehen, die auf
+$\operatorname{OES}(32)$ und $\operatorname{BS}(32)$ angewandt wurden: Von
+jedem Sortiernetzwerk wurden zunächst eine Menge~$S$ von 10.000
+\emph{unterschiedlichen} Schnittmustern erzeugt. Anschließend wurden 1.000.000
+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 16-Schnittmustern für $\operatorname{OES}(32)$
+und $3,4 \cdot 10^6$ für $\operatorname{BS}(32)$.
+
+\begin{figure}
+ \begin{center}
+ \includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-100000-1000000-32-ps.pdf}
+ \end{center}
+ \caption{Abschnätzung der unterschiedlichen Schnittmuster mit der
+ \emph{Monte-Carlo-Methode} für $\operatorname{PS}(32)$. 385 von 1.000.000
+ zufälligen Schnittmustern waren äquivalent zu einem Schnittmuster in einer
+ Menge von 100.000. Daraus ergibt sich eine Schätzung von $2,6 \cdot 10^8$
+ unterschiedlichen Schnittmustern.}
+ \label{fig:collisions-100000-1000000-32-ps}
+\end{figure}
+
+Im vorherigen Abschnitt wurde das \emph{Pairwise-Sorting-Netzwerk}
+$\operatorname{PS}(32)$ nicht betrachtet, da es für dieses Netzwerk viel mehr
+unterschiedliche 16-Schnittmuster gibt als für $\operatorname{OES}(32)$ und
+$\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. 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
+sind. Daraus ergibt sich eine Abschätzung von $2,6 \cdot 10^8$
+unterschiedlichen Schnittmustern -- zwei Zehnerpotenzen mehr als bei den
+vorherigen Sortiernetzwerken, aber immernoch fünf Zehnerpotenzen kleiner als
+die Anzahl der \emph{möglichen} Schnittmuster.
+
+\newpage
+\section{Der \textsc{SN-Evolution}-Algorithmus}
+
+Der \textsc{SN-Evolution}-Algorithmus ist ein \emph{evolutionärer
+Algorithmus}, der die in den vorherigen Abschnitten beschriebenen Mischer
+(Abschnitt~\ref{sect:konstruktive_netzwerke}) und Schnittmuster
+(Abschnitt~\ref{sect:leitungen_entfernen}) verwendet, um „möglichst gute“
+Sortiernetzwerke zu erzeugen. Was ein „gutes“ Sortiernetzwerk ausmacht, wird
+in Abschnitt~\ref{sect:bewertung} behandelt.
+
+\subsection{Bewertungsfunktion}\label{sect:bewertung}
+
+Um Sortiernetzwerke überhaupt optimieren zu können, muss zunächst die
+{\em Güte} eines Netzwerkes definiert werden. Prinzipiell gibt es zwei Ziele,
+die bei Sortiernetzwerken verfolgt werden können:
+\begin{itemize}
+ \item Möglichst wenige Komparatoren („effizient“)
+ \item Möglichst wenige Schichten („schnell“)
+\end{itemize}
+
+Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das
+effizienteste bekannte Sortiernetzwerk für 16~Eingänge besteht aus
+60~Komparatoren in 10~Schichten. Das schnellste Netzwerk besteht aus
+61~Komparatoren in nur 9~Schichten.
+
+Eine Gütefunktion, die die beiden Ziele "`effizient"' und "`schnell"'
+berücksichtigen kann, hat die folgende allgemeine Form:
+\begin{equation}
+ \operatorname{Guete}(S) = w_{\mathrm{Basis}}
+ + w_{\mathrm{Komparatoren}} \cdot \left|S\right|_\mathrm{Komparatoren}
+ + w_{\mathrm{Schichten}} \cdot \left|S\right|_\mathrm{Schichten}
+\end{equation}
+Die Parameter $w_{\mathrm{Komparatoren}}$ und $w_{\mathrm{Schichten}}$ dienen
+dabei der Festlegung des Optimierungsziels. Wenn einer der beiden Parameter
+gleich Null ist, wird nur das jeweils andere Ziel verfolgt. Sind beide
+Parameter gleich Null, werden alle Netzwerke mit der gleich Güte bewertet --
+jegliche Ergebnisse sind dann rein zufälliger Natur.\footnote{Dass dies nicht
+so schlecht ist wie man intuitiv vermuten könnte, zeigt der
+\textsc{SN-Markov}-Algorithmus in Abschnitt~\ref{sect:markov}.}
+
+Da möglichst effiziente und schnelle Sortiernetzwerke gefunden werden sollen,
+ist ein kleiner Wert von $\operatorname{Guete}(S)$ besser als ein großer Wert.
+Das heißt, dass das Ziel von \textsc{SN-Evolution} ist,
+$\operatorname{Guete}(S)$ zu \emph{minimieren}.
+
+Mit dem Parameter $w_{\mathrm{Basis}}$ kann auf die Selektion Einfluss
+genommen werden. Ist er groß, wird der relative Unterschied der Güten
+verschiedener Netzwerke kleiner, was die {\em Exploration}, das Absuchen des
+gesamten Lösungsraums, begünstigt. Wählt man $w_{\mathrm{Basis}}$ hingegen
+klein -- in Abhängigkeit von den anderen beiden Parametern sind auch negative
+Werte möglich -- werden die relativen Unterschiede groß. Dadurch wird die {\em
+Exploitation}, das Finden (lokaler) Optima, bevorzugt.
+
+Diese Parameter haben einen großen Einfluss auf die Geschwindigkeit, mit der
+der \textsc{SN-Evolution}-Algorithmus konvergiert und ob er tatsächlich gute
+Lösungen findet oder sich in \emph{lokalen} Optima verrennt. Leider gibt es
+kein Patentrezept für die Wahl der Parameter, so dass für verschiedene
+Leitungszahlen und Mischer-Typen experimentiert werden muss.
+
+\subsection{Selektion}
+
+Die \emph{Selektion} sorgt dafür, dass bessere Individuen eine größere
+Wahrscheinlichkeit haben, zur nächsten Generation beizutragen. Diese
+Ungleichbehandlung von Individuen verschiedener Güte ist der Grund für das
+Streben des Algorithmus nach besseren Lösungen.
+
+Obwohl dieser Vorteil für gute Individuen intuitiv als sehr gering erscheint,
+ist es sehr häufig, dass die \emph{Exploitation} überhand gewinnt und der
+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
+ {
+ Auswahl := Individuum
+ }
+}
+gib Auswahl zurück
+\end{verbatim}
+
+\subsection{Rekombination}
+
+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
+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.
+
+Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft
+erhält.
+
+\subsection{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 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, wie in Abschnitt~\ref{sect:0-1-prinzip}
+beschrieben.
+
+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.
+
+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.
+
+\subsection{Güte}
+
+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*}
+
+\subsection{Versuche mit dem bitonen Mischer}
+
+\begin{figure}
+ \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}
+
+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/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}
+
+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 Güte von Sortiernetzwerken (Anzahl der Komparatoren, Anzahl der Schichten, kombiniert)
+\item Wie gut die Netzwerke werden, hängt stark vom verwendeten \emph{Mischer} ab.
+\item Ggf. Abschnitt „Shmoo-Äquivalenz“ kürzen und hier einbauen.
+\item Möglicherweise: Verwende den rekursiven Aufbau des \emph{Pairwise-Sorting}-Netzwerks um Sortiernetzwerke zu mergen.
+\end{itemize}
+
+%\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}
+
+\newpage
+\section{Der \textsc{SN-Evolution-Cut}-Algorithmus}
\label{sect:sn-evolution-cut}
Das Programm \textsc{SN-Evolution-Cut} implementiert einen evolutionären
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
Schnitt-Richtung.
-% bitones Mergesort-Netzwerk
+\subsection{Versuche mit dem bitonen Mergesort-Netzwerk}
In \cite{MW2010} zeigen \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka},
wie man einen bitonen Mischer, der nach Batchers Methode konstruiert wurde,
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
leicht invertieren lassen, werden der Fall, dass es mehr Minimumschnitte, und
der Fall, dass es mehr Maximumschnitte gibt, nicht unterschieden.
-
-
-% Odd-Even-Transpositionsort-Netzwerk
-
Dass die Ergebnisse von \textsc{SN-Evolution-Cut} keine erkennbare Struktur
haben, ist jedoch kein Eigenschaft des Algorithmus, sondern hängt insbesondere
von der Eingabe ab. Wird \textsc{SN-Evolution-Cut} beispielsweise mit dem
\label{fig:16-ec-from-ps32}
\end{figure}
-% Pairwise-Sorting-Netzwerk
+\subsection{Versuche mit dem Pairwise-Sorting-Netzwerk}
Anders verhält sich das \emph{Pairwise-Sorting-Netzwerk}
$\operatorname{PS}(n)$, das \textit{Ian Parberry} in seiner Arbeit „The
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}
\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}
\label{fig:16-pairwise}
\end{figure}
-Wendet man \textsc{SN-Evolution-Cut} auf $\operatorname{PS}(16)$ an, so kann
-man $\operatorname{OES}(8)$ erhalten.
-
-% Odd-Even-Mergesort-Netzwerk
-
-\todo{Schreibe noch etwas zum Odd-Even-Mergesort-Netzwerk.}
-
-\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}
-
-\section{Der \textsc{SN-Evolution}-Algorithmus}
-
-Um einen evolutionären Algorithmus für Sortiernetzwerke zu entwickeln, werden
-die vorgestellten Methoden kombiniert.
-
-\subsection{Bewertungsfunktion}\label{sect:bewertung}
-
-Um Sortiernetzwerke überhaupt optimieren zu können, muss zunächst die
-{\em Güte} eines Netzwerkes definiert werden. Prinzipiell gibt es zwei Ziele,
-die interessant sind:
-\begin{itemize}
- \item Möglichst wenige Komparatoren ("`klein"')
- \item Möglichst wenige Schichten ("`schnell"')
-\end{itemize}
-
-Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das
-kleinste bekannte Sortiernetzwerk für 16~Eingänge besteht aus 60~Komparatoren
-in 10~Schichten. Das schnellste Netzwerk besteht aus 61~Komparatoren in nur
-9~Schichten.
-
-Eine Gütefunktion, die die beiden Ziele "`klein"' und "`schnell"'
-berücksichtigen kann, hat die folgende allgemeine Form:
-\begin{equation}
- \operatorname{Guete}(S) = w_{\mathrm{Basis}}
- + w_{\mathrm{Komparatoren}} \cdot \left|S\right|_\mathrm{Komparatoren}
- + w_{\mathrm{Schichten}} \cdot \left|S\right|_\mathrm{Schichten}
-\end{equation}
-Die Parameter $w_{\mathrm{Komparatoren}}$ und $w_{\mathrm{Schichten}}$ dienen
-dabei der Festlegung des Optimierungsziels. Wenn einer der beiden Parameter
-gleich Null ist, wird nur das jeweils andere Ziel verfolgt. Sind beide
-Parameter gleich Null, werden alle Netzwerke mit der gleich Güte bewertet --
-jegliche Ergebnisse sind dann rein zufälliger Natur.
-
-Mit dem Parameter $w_{\mathrm{Basis}}$ kann auf die Selektion Einfluss
-genommen werden. Ist er groß, wird der relative Unterschied der Güten
-verschiedener Netzwerke kleiner, was die {\em Exploration}, das Absuchen des
-gesamten Lösungsraums, begünstigt. Wählt man $w_{\mathrm{Basis}}$ hingegen
-klein, in Abhängigkeit von den anderen beiden Parametern sind auch negative
-Werte möglich, werden die relativen Unterschiede groß. Dadurch wird die {\em
-Exploitation}, das Finden lokaler Optima, bevorzugt.
-
-\subsection{Selektion}
-
-...
-
-\subsection{Rekombination}
-
-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
-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.
-
-Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft
-erhält.
-
-\subsection{Mutation}
-
-Zu einem vollständigen evolutionären Algorithmus gehört außerdem eine 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
-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.
-
-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.
-
-\begin{itemize}
-\item Güte von Sortiernetzwerken (Anzahl der Komparatoren, Anzahl der
-Schichten, kobiniert)
-\item Rekombination: Merge Anhängen und Leitungen entfernen.
-\end{itemize}
-
-Ein Beispielnetzwerk, das von dem Algorithmus gefunden wird, zeigt
-Abbildung~\ref{fig:evolutionary_08}.
-
-\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}
-
-\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}
+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}
+
+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.
+
+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/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}
+ \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/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-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}
-\subsection{Güte}
-
-\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.
-\end{itemize}
-
+\newpage
\section{Der \textsc{SN-Markov}-Algorithmus}
+\label{sect:markov}
Der evolutionäre \textsc{SN-Evolution}-Algorithmus aus dem vorherigen
Abschnitt verwendete immer zwei zufällige Sortiernetzwerke („Individuen“) aus
hervorgehen können, heißen \emph{Nachfolger} von $S_0$.
Beim beschriebenen Vorgehen kann man die Sortiernetzwerke als Knoten in einem
-gerichteten Graphen betrachten. Zwei Knoten $V_0$ und $V_1$, die zwei
+(gerichteten) Graphen betrachten. Zwei Knoten $V_0$ und $V_1$, die zwei
Sortiernetzwerke $S_0$ und $S_1$ repräsentieren, sind genau dann mit einer
-Kante ${E_{0,1} = (V_0, V_1)}$ verbunden, wenn $S_1$ ein \emph{Nachfolger} von $S_0$
-ist, das heißt dass man $S_1$ durch die Rekombination von $S_0$ mit sich
+Kante ${E_{0,1} = (V_0, V_1)}$ verbunden, wenn $S_1$ ein \emph{Nachfolger} von
+$S_0$ ist, das heißt dass man $S_1$ durch die Rekombination von $S_0$ mit sich
selbst erzeugen kann.
-Wie in Abschnitt~\ref{sect:anzahl_schnittmuster} beschrieben ist die Anzahl
-(unterschiedlichen) Schnittmuster und damit die Anzahl der Nachfolger sehr
-groß. Wenn $S_0$ ein Sortiernetzwerk mit $n$~Leitungen ist, so hat $S_0$ bis
-zu
-\begin{displaymath}
- 2^n \cdot \left( \begin{array}{c} 2n \\ n \end{array} \right)
-\end{displaymath}
-Nachfolger.
+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.
-Der Algorithmus {\sc SN-Markov} legt auf diesem Graph einen zufälligen Weg
-(englisch: \textit{random walk}) zurück. Er startet auf einem gegebenen
-Sortiernetzwerk. Um von einem Sortiernetzwerk zum Nächsten zu gelangen
-rekombiniert er das aktuelle Sortiernetzwerk mit sich selbst und erhält so
-einen zufälligen Nachfolger.
+Der Algorithmus {\sc SN-Markov} legt auf diesem Nachfolger-Graph einen
+zufälligen Weg (englisch: \textit{random walk}) zurück. Er startet auf einem
+gegebenen Sortiernetzwerk. Um von einem Sortiernetzwerk zum Nächsten zu
+gelangen, rekombiniert der Algorithmus das aktuelle Sortiernetzwerk mit sich
+selbst und erhält so einen zufälligen Nachfolger. In Pseudocode lässt dich der
+Algorithmus wie folgt beschreiben:
+
+\begin{verbatim}
+Netzwerk := Eingabe
+
+für n Iterationen
+{
+ Nachfolger := kombiniere (Netzwerk, Netzwerk)
+ Netzwerk := Nachfolger
+}
+
+gib Netzwerk zurück
+\end{verbatim}
+
+\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}
-\begin{itemize}
- \item $n \leftarrow \mathrm{Input}$
- \item \texttt{while} \textit{true}
- \begin{itemize}
- \item $n \leftarrow \operatorname{recombine} (n, n)$
- \end{itemize}
-\end{itemize}
\begin{itemize}
\item Beste erreichte Netzwerke (gleich zu \emph{OE-Mergesort}).
\begin{figure}
\begin{center}
- \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-12-pct.pdf}
+ \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
\begin{figure}
\begin{center}
- \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-14-pct.pdf}
+ \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
\begin{figure}
\begin{center}
- \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-16-pct.pdf}
+ \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
\label{fig:markov-comparators-16}
\end{figure}
-%\input{shmoo-aequivalenz.tex}
-
-\section{Optimierung der Schnitte}
-
-\todo{In den Abschnitt "`Leitungen entfernen"' einbauen.}
-
-Abbildung~\ref{fig:32-ec-from-bs64} zeigt ein 32-Sortiernetzwerk, dass vom
-\textsc{SN-Evolution-Cut}-Algorithmus aus dem $BS(64)$-Netzwerk erzeugt wurde.
-Es besteht aus 206~Komparatoren in 15~Schichten -- 34~Komparatoren weniger als
-$BS(32)$ und zwei Komparatoren weniger als das Netzwerk, das nach Mühlenthaler
-und Wankas Methode konstruiert wird. Die Anzahl der Schichten ist bei allen
-Netzwerken gleich.
-
-\textbf{TODO:} $BS(128) \rightarrow n=64$: 584~Komparatoren in 21~Schichten
-möglich (nach ca. 600k Iterationen). Moritz und Rolf: $672-80=592$
-Komparatoren; $BS(64)$: 672~Komparatoren.
-
-Schnitt-Sequenz:
-MIN( 92)
-MAX( 80)
-MIN(100)
-MAX( 54)
-MAX(102)
-MAX( 53)
-MAX(105)
-MAX( 6)
-MAX( 99)
-MAX( 79)
-MAX( 26)
-MIN(111)
-MAX( 12)
-MIN( 22)
-MAX( 61)
-MAX( 72)
-MAX( 68)
-MIN( 80)
-MAX( 80)
-MAX( 99)
-MAX(105)
-MAX( 0)
-MIN( 8)
-MAX( 40)
-MAX( 74)
-MAX( 40)
-MAX( 40)
-MIN( 56)
-MAX( 27)
-MAX( 13)
-MAX( 1)
-MAX( 81)
-MAX( 17)
-MAX( 4)
-MIN( 36)
-MIN( 22)
-MAX( 13)
-MIN( 72)
-MAX( 24)
-MAX( 5)
-MIN( 10)
-MAX( 59)
-MIN( 37)
-MAX( 65)
-MAX( 46)
-MAX( 73)
-MAX( 58)
-MAX( 29)
-MAX( 65)
-MIN( 23)
-MAX( 56)
-MAX( 11)
-MIN( 75)
-MIN( 51)
-MIN( 46)
-MIN( 34)
-MAX( 32)
-MAX( 6)
-MAX( 37)
-MIN( 4)
-MIN( 28)
-MIN( 20)
-MAX( 33)
-MAX( 34)
-
-% images/32-ec-1277190372.tex
+\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}
\begin{itemize}
\item $\ldots$
\end{itemize}
+\newpage
\section{Ausblick}
Das würde mir noch einfallen$\ldots$
+\newpage
+\section{Implementierung}
+
+So habe ich die ganzen Versuche durchgeführt.
+
+\newpage
\bibliography{references}
\bibliographystyle{plain}
projects / diplomarbeit.git / blobdiff