\usepackage{listings}
\usepackage{graphicx}
\usepackage{url}
+\usepackage[table]{xcolor}
%\usepackage{longtable}
\usepackage{subfigure}
\usepackage{icomma}
\newcommand{\bm}[1]{\ensuremath{\operatorname{BM}\left(#1\right)}}
\newcommand{\oet}[1]{\ensuremath{\operatorname{OET}\left(#1\right)}}
+\newcommand{\gcell}{\cellcolor{green!10}}
+\newcommand{\Gcell}{\cellcolor{green!10!white!95!black}}
+
\newtheorem{definition}{Definition}
\newtheorem{satz}{Satz}
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)$
+$\Theta\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ zuzuordnen ist,
+ist das Überprüfen aller 0-1-Folgen „nur“ mit dem Aufwand $\Theta(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,
\begin{center}
\input{images/oe-transposition-8.tex}
\end{center}
- \caption{Das \emph{Odd-Even-Transpositionsort}-Netzwerk mit acht Eingängen.}
+ \caption{Das \emph{Odd-Even-Transpositionsort}-Netzwerk mit 8~Eingängen.}
\label{fig:odd-even-transposition-08}
\end{figure}
Das \emph{Odd-Even-Transpositionsort}-Netzwerk ist weder in Bezug auf die
Anzahl der Komparatoren noch in Bezug auf die Anzahl der Schichten, in denen
sich die Komparatoren anordnen lassen, effizient. Es benötigt ${\frac12 n
-(n-1)} = \mathcal{O}(n^2)$~Komparatoren, die in $n$~Schichten angeordnet sind.
+(n-1)} = \Theta(n^2)$~Komparatoren, die in $n$~Schichten angeordnet sind.
Die im Folgenden vorgestellten Sortiernetzwerke benötigen deutlich weniger Komparatoren,
($\Theta(n \log (n)^2)$), die in weniger Schichten,
($\Theta(\log (n)^2)$), angeordnet sind.
Da sich die Anzahl der Leitungen in jedem Rekursionsschritt halbiert, endet
die Rekursion nach $\log(n)$~Schritten. In jedem Rekursionsschritt werden
$\frac{n}{2}$~Komparatoren eingefügt, so dass der gesamte Mischer aus
-$\frac{1}{2} n \log(n) = \mathcal{O}\left(n \log(n)\right)$~Komparatoren
+$\frac{1}{2} n \log(n) = \Theta\left(n \log(n)\right)$~Komparatoren
besteht, die in $\log(n)$~Schichten angeordnet werden können.
\subsubsection{Das bitone Mergesort-Netzwerk}
\begin{center}
\input{images/batcher-8.tex}
\end{center}
- \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).}
+ \caption{\bs{8}, Batchers \emph{bitones Mergesort}-Netzwerk für 8~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}
\begin{center}
\input{images/oe-merge.tex}
\end{center}
- \caption{Schematischer Aufbau des \emph{Odd-Even-Merge}-Netzwerks. Im
- Vergleich zum bitonen Mischer für acht Leitungen kommt dieses Schema mit
- einem Komparator weniger aus. Der Effekt wird durch den rekursiven Aufbau
- verstärkt.}
+ \caption{Schematischer Aufbau des \emph{Odd-Even-Merge}-Netzwerks. Die
+ beiden Dreiecke symbolisieren die beiden sortierten Folgen $U$ und $V$,
+ die Blöcke darunter die rekursiven Mischer mit etwa der Hälfte der
+ Leitungen. Im Vergleich zum \emph{bitonen Mischer} für 8~Leitungen kommt
+ dieses Schema mit einem Komparator weniger aus. Der Effekt wird durch den
+ rekursiven Aufbau verstärkt.}
\label{fig:oe-merge}
\end{figure}
einzelnen Komparator.
\end{itemize}
-Mit dem {\em 0-1-Prinzip} lässt sich zeigen, sass die resultierende Folge
+Mit dem {\em 0-1-Prinzip} lässt sich zeigen, dass die resultierende Folge
sortiert ist. Da $U$ und $V$ sortiert sind, ist die Anzahl der Nullen in den
geraden Teilfolgen $U_{\textrm{gerade}}$, beziehungsweise
$V_{\textrm{gerade}}$ größer oder gleich der Anzahl der Nullen in den
\end{figure}
Da die Teilfolgen $U$ und $V$ in jedem Rekursionsschritt etwa halbiert werden,
-bricht die Rekursion nach $\mathcal{O}\left(\log (n) + \log (m)\right)$
+bricht die Rekursion nach $\Theta\left(\log (n) + \log (m)\right)$
Schritten ab. Die exakte Anzahl der benötigten Rekursionsschritte (und damit
Schichten im Mischer-Netzwerk), hängt von der längeren der beiden
Eingabefolgen ab und beträgt $1 + \lceil \log\left(\max(n, m)\right) \rceil$.
\end{displaymath}
Leider ist es schwierig, diese allgemeine Formel in einer geschlossenen Form
anzugeben. Aus der Anzahl der Rekursionsschritte ist jedoch leicht erkennbar,
-dass $K(n,m)$ in $\mathcal{O}(N \log (N))$ enthalten ist.
+dass $K(n,m)$ in $\Theta(N \log (N))$ enthalten ist.
Für den wichtigen Spezialfall, dass $n = m = 2^{t-1}$ beträgt, lässt sich die
Anzahl der Komparatoren im Vergleich zum \emph{bitonen Mischer} angeben: Der
\begin{center}
\input{images/oe-mergesort-8.tex}
\end{center}
- \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge. Markiert
+ \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für 8~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
Leitungen (blau) und die im ersten Rekursionsschritt hinzugefügten
In Abbildung~\ref{fig:odd-even-mergesort-08} ist das \oes{8}-Sortiernetzwerk
zu sehen. Rot markiert sind die beiden rekursiven Instanzen
$\operatorname{OES}(4)$. Die anderen Blöcke stellen den
-\emph{Odd-Even}-Mischer für acht Leitungen dar: die beiden blauen Blöcke sind
+\emph{Odd-Even}-Mischer für 8~Leitungen dar: die beiden blauen Blöcke sind
die rekursiven Instanzen von $\operatorname{OEM}(4)$, der grüne Block markiert
die Komparatoren, die im ersten Rekursionsschritt hinzugefügt werden.
zusammenfügen.
Beispielsweise kann die Ausgabe von zwei \emph{bitonen Mergesort-Netzwerken}
-$\operatorname{BS}(8)$ mit je acht Leitungen mit dem
+$\operatorname{BS}(8)$ mit je 8~Leitungen mit dem
\emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM(8,8)}$ zu einer sortierten
Gesamtfolge zusammengefügt werden. Das resultierende Sortiernetzwerk besitzt
73~Komparatoren (zum Vergleich: $\operatorname{BS}(16)$ benötigt
\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 bekannte 16-Sortiernetzwerk
-besteht aus 61~Komparatoren in nur 9~Schichten.
+\begin{figure}
+ \centering
+ \subfigure[16-Sortiernetzwerk aus 60~Komparatoren in 10~Schichten. Das Netzwerk wurde von \textit{M.~W. Green} konstruiert und 1969 in \todo{Referenz} veröffentlicht.]{\input{images/16-green.tex}\label{fig:16-green}}
+ \subfigure[16-Sortiernetzwerk aus 61~Komparatoren in 9~Schichten. Das Netzwerk wurde von \textit{D. Van~Voorhis} veröffentlicht.]{\input{images/16-voorhis.tex}\label{fig:16-voorhis}}
+ \caption{Das effizienteste und das schnellste Sortiernetzwerk für
+ 16~Leitungen, das derzeit bekannt ist.}
+ \label{fig:16-best-known}
+\end{figure}
+Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken.
+Beispielsweise besteht das \emph{effizienteste} bekannte Sortiernetzwerk für
+16~Eingänge aus 60~Komparatoren in 10~Schichten. Es ist in
+Abbildung~\ref{fig:16-green} dargestellt. Das \emph{schnellste} bekannte
+16-Sortiernetzwerk besteht aus 61~Komparatoren in nur 9~Schichten und ist in
+Abbildung~\ref{fig:16-voorhis} zu sehen.
Eine Gütefunktion, die die beiden Ziele "`effizient"' und "`schnell"'
berücksichtigen kann, hat die folgende allgemeine Form:
\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.
+Als \emph{Selektion} wird der Vorgang bezeichnet, der zwei Individuen zufällig
+aus der Population auswählt. Sie werden im folgenden Schritt miteinander
+rekombiniert. Die Auswahl der Individuen erfolgt zufällig, aber nicht
+gleichverteilt. So sorgt die \emph{Selektion} 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.
+passiert es häufig, dass die Ausnutzung \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:
+Die in \textsc{SN-Evolution} implementierte Selektion eines Individuums lässt
+sich mit Pseudocode wie folgt beschreiben:
\begin{verbatim}
Gütesumme := 0
Auswahl := (leer)
gib Auswahl zurück
\end{verbatim}
+Diese Auswahl wird zweimal ausgeführt, um zwei Individuen für die
+Rekombination zu erhalten. Das heißt, dass die Individuen bei
+\textsc{SN-Evolution} stochastisch unabhängig voneinander ausgewählt werden.
+
\subsection{Rekombination}
\label{sect:sn-evolution:rekombination}
\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 \emph{bitone Mergesort}-Netzwerk: \bs{16} benötigt 80~Komparatoren,
-das Sortiernetzwerk in Abbildung~\ref{fig:16-e1-bitonic-1296542566} benötigt
-lediglich~67. Die Effizienz des \emph{Odd-Even-Mergesort}-Netzwerks wurde
-leider mit keiner Leitungszahl erreicht.
+Wenn \textsc{SN-Evolution} mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk
+als Eingabe gestartet wird und in der Rekombinationsphase den \emph{bitonen
+Mischer} verwendet, gibt der Algorithmus Sortiernetzwerke wie das in
+Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte zurück.
+
+Viele der Sortiernetzwerke, die von \textsc{SN-Evolution} in dieser
+Konfiguration gefunden werden, sind effizienter als das \emph{bitone
+Mergesort}-Netzwerk \bs{n}, das ebenfalls auf dem \emph{bitonen
+Merge}-Netzwerk \bm{n} beruht. Das in
+Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte 16-Sortiernetzwerk
+benötigt 67~Komparatoren, 13~Komparatoren weniger als \bs{n}.
+
+Wenn die Gütefunktion so gewählt ist, dass sie schnelle Sortiernetzwerke
+bevorzugt, können Netzwerke zurückgegeben werden, die schneller als \bs{n}
+sind. Viele der schnellen Sortiernetzwerke sind außerdem effizienter als
+\bs{n}. Das Sortiernetzwerk mit $n = 23$ Leitungen benötigt mit
+134~Komparatoren jedoch einen Komparator mehr als \bs{23}. Die Daten von
+schnellen Sortiernetzwerken, die \textsc{SN-Evolution} mit dem \emph{bitonen
+Merge}-Netzwerk erzeugt hat, sind in Tabelle~\ref{tbl:sn-ev-bm-fast}
+aufgelistet.
+
+\begin{table}\label{tbl:sn-ev-bm-fast}
+\begin{center}
+\rowcolors{4}{black!5}{}
+\begin{tabular}{|r|r|r|r|r|}
+\hline
+Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}} & \multicolumn{2}{|l|}{\bs{n}} \\
+\cline{2-5}
+ ($n$) & Komp. & Schichten & Komp. & Schichten \\
+\hline
+ 8 & \gcell 20 & 6 & 24 & 6 \\
+ 9 & \Gcell 26 & 8 & 28 & 8 \\
+ 10 & \gcell 31 & \gcell 8 & 33 & 9 \\
+ 11 & \Gcell 37 & \Gcell 9 & 39 & 10 \\
+ 12 & \gcell 42 & \gcell 9 & 46 & 10 \\
+ 13 & \Gcell 48 & 10 & 53 & 10 \\
+ 14 & \gcell 54 & 10 & 61 & 10 \\
+ 15 & \Gcell 61 & 10 & 70 & 10 \\
+ 16 & \gcell 67 & 10 & 80 & 10 \\
+ 17 & \Gcell 76 & 12 & 85 & 12 \\
+ 18 & \gcell 87 & \gcell 12 & 91 & 13 \\
+ 19 & \Gcell 93 & \Gcell 13 & 98 & 14 \\
+ 20 & \gcell 104 & \gcell 13 & 106 & 14 \\
+ 21 & \Gcell 109 & \Gcell 14 & 114 & 15 \\
+ 22 & \gcell 118 & \gcell 14 & 123 & 15 \\
+ 23 & 134 & \Gcell 14 & \Gcell 133 & 15 \\
+ 24 & \gcell 133 & 15 & 144 & 15 \\
+\hline
+\end{tabular}
+\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus
+ unter Verwendung des \emph{bitonen Merge}-Netzwerks \bm{n}. Der Algorithmus
+ wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n} gestartet
+ und nach 2.500.000 Iterationen beendet. Die Bewertungsfunktion nutzte die
+ Konstanten $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = 1$,
+ $w_{\mathrm{Schichten}} = n$.}
+\end{center}
+\end{table}
\subsection[Odd-Even-Mischer]{Versuche mit dem Odd-Even-Mischer}
Sortiernetzwerke erzeugen kann, die effizienter als das rekursiv aus dem
\emph{bitonen Mischer} aufgebaute \emph{bitone Mergesort}-Netzwerk sind.
Dieses Ergebnis lies sich mit dem \emph{Odd-Even-Merge}-Netzwerk nicht
-wiederholen. Die Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung
-des \emph{Odd-Even}-Mischers findet, erreichen das
+erzielen. Die Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung des
+\emph{Odd-Even-Merge}-Netzwerks findet, erreichen das
\emph{Odd-Even-Mergesort}-Netzwerk bezüglich Effizienz, übertreffen es aber
nicht. Ein Beispiel für ein entsprechendes Sortiernetzwerk ist in
-Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen. Wenn $n$ keine
-Zweierpotenz ist, kann \textsc{SN-Evolution} unter Umständen Sortiernetzwerke
-ausgeben, die schneller als \oes{n} sind.
+Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen.
+
+Mit einer Gütefunktion, die schnelle Sortiernetzwerke bevorzugt, ist es auch
+mit dem \emph{Odd-Even}-Mischer möglich, dass \textsc{SN-Evolution}
+Sortiernetzwerke zurück gibt, die schneller als \oes{n} sind. Dies geschieht
+beispielsweise bei $n = 11$ und $n = 12$: für diese Leitungszahlen gibt
+\textsc{SN-Evolution} Sortiernetzwerke aus, die nur 9~Schicten benötigen.
+\oes{11} und \oes{12} benötigen jeweils 10~Schichten. Eine Auflistung der
+Ergebnisse von \textsc{SN-Evolution} mit dem \emph{Odd-Even}-Mischer befindet
+sich in Tabelle~\ref{tbl:sn-ev-oem-fast}.
%\begin{figure}
%\begin{center}
%\label{fig:10-e2-1239014566}
%\end{figure}
+\begin{table}\label{tbl:sn-ev-oem-fast}
+\begin{center}
+\rowcolors{4}{black!5}{}
+\begin{tabular}{|r|r|r|r|r|}
+\hline
+Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}} & \multicolumn{2}{|l|}{\oes{n}} \\
+\cline{2-5}
+ & Komp. & Schichten & Komp. & Schichten \\
+\hline
+ 8 & 19 & 6 & 19 & 6 \\
+ 9 & 26 & 8 & 26 & 8 \\
+ 10 & 31 & 9 & 31 & 9 \\
+ 11 & 38 & \Gcell 9 & \Gcell 37 & 10 \\
+ 12 & 43 & \gcell 9 & \gcell 41 & 10 \\
+ 13 & 48 & 10 & 48 & 10 \\
+ 14 & 53 & 10 & 53 & 10 \\
+ 15 & 59 & 10 & 59 & 10 \\
+ 16 & 63 & 10 & 63 & 10 \\
+ 17 & 74 & 12 & 74 & 12 \\
+ 18 & 82 & 13 & 82 & 13 \\
+ 19 & 93 & \Gcell 13 & \Gcell 91 & 14 \\
+ 20 & 97 & 14 & 97 & 14 \\
+ 21 & 108 & \Gcell 14 & \Gcell 107 & 15 \\
+ 22 & 117 & \gcell 14 & \gcell 114 & 15 \\
+ 23 & 129 & \Gcell 14 & \Gcell 122 & 15 \\
+ 24 & 128 & 15 & \gcell 127 & 15 \\
+\hline
+\end{tabular}
+\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus
+ unter Verwendung des \emph{Odd-Even-Merge}-Netzwerks \oem{n}. Der
+ Algorithmus wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n}
+ gestartet und nach 2.500.000 Iterationen beendet. Die Bewertungsfunktion
+ nutzte die Konstanten $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} =
+ 1$, $w_{\mathrm{Schichten}} = n$.}
+\end{center}
+\end{table}
+
+\subsection{Zufälliger Mischer}
+
+Die Ergebnisse der beiden vorhergehenden Abschnitte zeigen, dass für einige
+Leitungszahlen der \emph{bitone Mischer} und für andere Leitungszahlen der
+\emph{Odd-Even}-Mischer bessere Ergebnisse liefert. Beispielsweise hat das
+Netzwerk für $n = 18$ bei Verwendung des \emph{bitone Mischers} nur
+12~Schichten, bei Verwendung des \emph{Odd-Even}-Mischers hingegen nur
+82~Komparatoren. Daher liegt die Idee nahe, beide Mischer-Netzwerke zu nutzen,
+um das beste Ergebnis beider Konstruktionen zu erreichen.
+\textsc{SN-Evolution} kann zu diesem Zweck beim Zusammenfügen zweier
+Individuen zufällig zwischen dem \emph{bitonen Mischer} und dem
+\emph{Odd-Even}-Mischer wählen.
+
+Die Ergebnisse von \textsc{SN-Evolution} bei einer zufälligen Wahl des
+Mischers in der Rekombinationsphase sind in Tabelle~\ref{tbl:sn-ev-rnd-fast}
+zusammengefasst. Bei den Leitungszahlen 12, 19, 21, 22 und 23 hat der
+Algorithmus Netzwerke mit einer Effizienz erzeugt, die mit nur einem
+Mischertyp nicht erreicht wurde. Die Ergebnisse mit den Leitungszahlen 18 und
+20 erreichen die Geschwindigkeit der Netzwerke, die mit dem \emph{bitonen
+Mischer} generiert wurden, und verbessern gleichzeitig die Effizienz.
+
+\begin{table}\label{tbl:sn-ev-rnd-fast}
+\begin{center}
+\rowcolors{4}{black!5}{}
+\begin{tabular}{|r|r|r|r|r|r|r|}
+\hline
+Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}}
+ & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}}
+ & \multicolumn{2}{l|}{\textsc{SN-EV} mit Zufall} \\
+\cline{2-7}
+ ($n$) & Komp. & Schichten & Komp. & Schichten & Komp. & Schichten \\
+\hline
+ 8 & 20 & 6 & \gcell 19 & 6 & \gcell 19 & 6 \\
+ 9 & 26 & 8 & 26 & 8 & 26 & 8 \\
+ 10 & 31 & \gcell 8 & 31 & 9 & 31 & \gcell 8 \\
+ 11 & \Gcell 37 & 9 & 38 & 9 & \Gcell 37 & 9 \\
+ 12 & 42 & 9 & 43 & 9 & \gcell 41 & 9 \\
+ 13 & 48 & 10 & 48 & 10 & 48 & 10 \\
+ 14 & 54 & 10 & \gcell 53 & 10 & \gcell 53 & 10 \\
+ 15 & 61 & 10 & \Gcell 59 & 10 & \Gcell 59 & 10 \\
+ 16 & 67 & 10 & \gcell 63 & 10 & 64 & 10 \\
+ 17 & 76 & 12 & \Gcell 74 & 12 & \Gcell 74 & 12 \\
+ 18 & 87 & \gcell 12 & \gcell 82 & 13 & 83 & \gcell 12 \\
+ 19 & 93 & 13 & 93 & 13 & \Gcell 92 & 13 \\
+ 20 & 104 & \gcell 13 & \gcell 97 & 14 & 101 & \gcell 13 \\
+ 21 & 109 & 14 & 108 & 14 & \Gcell 107 & 14 \\
+ 22 & 118 & 14 & 117 & 14 & \gcell 116 & 14 \\
+ 23 & 134 & 14 & 129 & 14 & \Gcell 128 & 14 \\
+ 24 & 133 & 15 & \gcell 128 & 15 & 130 & 15 \\
+\hline
+\end{tabular}
+\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus
+ unter Verwendung der verschiedenen Mischer. Der Algorithmus wurde mit dem
+ \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n} gestartet und nach
+ 2.500.000 Iterationen beendet. Die Bewertungsfunktion nutzte die Konstanten
+ $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = 1$,
+ $w_{\mathrm{Schichten}} = n$.}
+\end{center}
+\end{table}
+
%\input{shmoo-aequivalenz.tex}
\newpage
+\section{Der \textsc{SN-Markov}-Algorithmus}
+\label{sect:markov}
+
+Der evolutionäre \textsc{SN-Evolution}-Algorithmus aus dem vorherigen
+Abschnitt verwendet immer zwei zufällige Sortiernetzwerke („Individuen“) aus
+einer Population. Da die beiden „Eltern“ zufällig und unabhängig voneinander
+ausgewählt werden, kann es vorkommen, dass das selbe Sortiernetzwerk zweimal
+verwendet und mit sich selbst kombiniert wird.
+
+Macht man diesen Spezialfall zum Regelfall, kombiniert das aktuelle Netzwerk
+\emph{immer} mit sich selbst und eliminiert anschließend die Hälfte aller
+Leitungen, lassen sich einige interessante Beobachtungen anstellen. Netzwerke,
+die aus einem Netzwerk $S_0$ durch die beschriebene Kombination von $S_0$ mit
+sich selbst und anschließendem Eliminieren der Hälfte der Leitungen 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
+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 $S_1$ durch die Rekombination von $S_0$ mit sich
+selbst erzeugt werden 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 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
+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 sich 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}
+
+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-Transpositionsort}-Netzwerk gestartet und 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
+prozentuale Verteilung zu sehen.
+
+Ebenfalls in die Graphen der 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.
+
+\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/comparison-comparators-16.pdf}
+ \end{center}
+ \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}
+
+Der Graph in Abbildung~\ref{fig:comparison-comparators} zeigt, dass der
+\textsc{SN-Markov}-Algorithmus nicht schlechter ist als der
+\textsc{SN-Evolution}-Algo\-rith\-mus. 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 sich außerdem je
+nach verwendetem 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.
+
+Erwartungsgemäß 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, trat auch jeweils ein
+Sortiernetzwerk mit 121 und 124~Komparatoren auf. Dass Sortiernetzwerke mit so
+vielen Komparatoren im Verlauf des Experiments selbst nach über 100~Millionen
+Iterationen nicht noch einmal erzeugt wurden, ist vermutlich ein Phänomen, das
+mit der Initialisierung durch das \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}
+
+\newpage
\section{Der \textsc{SN-Evolution-Cut}-Algorithmus}
\label{sect:sn-evolution-cut}
invertieren.
\subsection[Bitones Mergesort-Netzwerk]{Versuche mit dem bitonen Mergesort-Netzwerk}
+\label{sect:sn-evolution-cut:bs}
+
+\begin{figure}
+ \begin{center}
+ \input{images/16-ec-from-bs22.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 16~Leitungen und 67~Komparatoren in
+ 10~Schichten. Das Netzwerk wurde von dem Algorithmus
+ \textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort}-Netzwerk
+ $\operatorname{BS}(22)$ durch das 6-Schnittmuster $\operatorname{MIN}(4,
+ 10, 17)$, $\operatorname{MAX}(7, 15, 20)$ erzeugt.}
+ \label{fig:16-ec-from-bs22}
+\end{figure}
\textit{Moritz Mühlenthaler} und \textit{Rolf Wanka} zeigen in~\cite{MW2010},
wie man einen bitonen Mischer, der nach Batchers Methode konstruiert wurde,
haben, ist jedoch kein Eigenschaft des Algorithmus, sondern hängt insbesondere
von der Eingabe ab. Wird \textsc{SN-Evolution-Cut} beispielsweise mit dem
\emph{Odd-Even-Transpositionsort-Netzwerk} $\operatorname{OET}(n)$ und
-$m$~Schnitten gestartet, so ist das beste Ergebnis immer das
-$\operatorname{OET}(n-m)$-Netzwerk.
-
-\subsection[Pairwise-Sorting-Netzwerk]{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
-Pairwise Sorting Network“ \cite{P1992} definiert. Startet man
-\textsc{SN-Evolution-Cut} mit $\operatorname{PS}(32)$ und der Vorgabe,
-16~Leitungen zu entfernen, erhält man ein Sortiernetzwerk, das die gleiche
-Anzahl 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.
-
-\begin{figure}
- \begin{center}
- \input{images/16-ec-from-ps32.tex}
- \end{center}
- \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in
- 10~Schichten. Das Netzwerk wurde von dem Algorithmus
- \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting-Netzwerk}
- $\operatorname{PS}(32)$ durch 16~Schnitte erzeugt.}
- \label{fig:16-ec-from-ps32}
-\end{figure}
-
-Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even}-Mischer nicht
-einsetzt und auch nicht auf einem Mischer basiert, ist das
-\emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM}(8,8)$ im Sortiernetzwerk in
-Abbildung~\ref{fig:16-ec-from-ps32} eindeutig erkennbar (Schichten~7--10). In
-den Schichten~1--6 erkennt man zwei unabhängige Sortiernetzwerke, die
-strukturell sehr ähnlich zu $\operatorname{PS}(8)$ sind -- lediglich die
-Schichten~1 und~2 sowie 4~und~5 sind vertauscht.
-
-\begin{figure}
- \begin{center}
- \input{images/32-pairwise-cut-16-pairwise.tex}
- \end{center}
- \caption{Das \ps{32}-Netzwerk mit 8~Maximum- und 8~Minimumschnitten. Gut zu
- sehen sind die verbleibenden Komparatoren, die das \ps{16}-Netzwerk
- bilden.}
- \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 ein 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}
- \end{center}
- \caption{Das $\operatorname{PS}(16)$-Sortiernetzwerk mit 8~Schnitten
- ($\operatorname{MIN}(0, 2, 4, 6), \operatorname{MAX}(9, 11, 13, 15)$). Das
- resultierende 8-Sortiernetzwerk ist $\operatorname{OES}(8)$.}
- \label{fig:16-pairwise}
-\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 Verwandtschaft von $\operatorname{PS}(n)$ und \oes{n}
-untersucht \textit{Moritz Mühlenthaler} ausführlich in~\cite{M2009}.
+$k$~Schnitten gestartet, so ist das beste Ergebnis immer das
+$\operatorname{OET}(n-k)$-Netzwerk.
\subsection[Odd-Even-Mergesort-Netzwerk]{Versuche mit dem Odd-Even-Mergesort-Netzwerk}
\label{sect:sn-evolution-cut:oes}
\label{fig:23-ec-from-oes46}
\end{figure}
-\newpage
-\section{Der \textsc{SN-Markov}-Algorithmus}
-\label{sect:markov}
-
-Der evolutionäre \textsc{SN-Evolution}-Algorithmus aus dem vorherigen
-Abschnitt verwendet immer zwei zufällige Sortiernetzwerke („Individuen“) aus
-einer Population. Da die beiden „Eltern“ zufällig und unabhängig voneinander
-ausgewählt werden, kann es vorkommen, dass das selbe Sortiernetzwerk zweimal
-verwendet und mit sich selbst kombiniert wird.
-
-Macht man diesen Spezialfall zum Regelfall, kombiniert das aktuelle Netzwerk
-\emph{immer} mit sich selbst und eliminiert anschließend die Hälfte aller
-Leitungen, lassen sich einige interessante Beobachtungen anstellen. Netzwerke,
-die aus einem Netzwerk $S_0$ durch die beschriebene Kombination von $S_0$ mit
-sich selbst und anschließendem Eliminieren der Hälfte der Leitungen 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
-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 $S_1$ durch die Rekombination von $S_0$ mit sich
-selbst erzeugt werden 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 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
-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 sich der
-Algorithmus wie folgt beschreiben:
+\subsection[Pairwise-Sorting-Netzwerk]{Versuche mit dem Pairwise-Sorting-Netzwerk}
-\begin{verbatim}
- Netzwerk := Eingabe
-
- für n Iterationen
- {
- Nachfolger := kombiniere (Netzwerk, Netzwerk)
- Netzwerk := Nachfolger
- }
-
- gib Netzwerk zurück
-\end{verbatim}
+Die Ergebnisse, die \textsc{SN-Evolution-Cut} erzielte, wenn das gegebene
+Sortiernetzwerk das \emph{bitone Mergesort}-Netzwerk war
+(Abschnitt~\ref{sect:sn-evolution-cut:bs}), waren sehr wirr. Beispielsweise
+ist bei dem Netzwerk in Abbildung~\ref{fig:32-ec-from-bs64} nicht ersichtlich,
+wie und warum es jede beliebige Eingabe sortiert.
-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-Transpositionsort}-Netzwerk gestartet und 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
-prozentuale Verteilung zu sehen.
-
-Ebenfalls in die Graphen der 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.
+Das \emph{Pairwise-Sorting-Netzwerk} $\operatorname{PS}(n)$, das \textit{Ian
+Parberry} in seiner Arbeit „The Pairwise Sorting Network“ \cite{P1992}
+definiert, verhält sich anders. Startet man \textsc{SN-Evolution-Cut} mit
+$\operatorname{PS}(32)$ und der Vorgabe, 16~Leitungen zu entfernen, erhält man
+ein Sortiernetzwerk, das die gleiche Anzahl 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.
\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}
+ \begin{center}
+ \input{images/16-ec-from-ps32.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in
+ 10~Schichten. Das Netzwerk wurde von dem Algorithmus
+ \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting-Netzwerk}
+ $\operatorname{PS}(32)$ durch 16~Schnitte erzeugt.}
+ \label{fig:16-ec-from-ps32}
\end{figure}
+Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even}-Mischer nicht
+einsetzt und auch nicht auf einem Mischer basiert, ist das
+\emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM}(8,8)$ im Sortiernetzwerk in
+Abbildung~\ref{fig:16-ec-from-ps32} eindeutig erkennbar (Schichten~7--10). In
+den Schichten~1--6 erkennt man zwei unabhängige Sortiernetzwerke, die
+strukturell sehr ähnlich zu $\operatorname{PS}(8)$ sind -- lediglich die
+Schichten~1 und~2 sowie 4~und~5 sind vertauscht.
+
\begin{figure}
\begin{center}
- \includegraphics[viewport=0 0 425 262,width=15cm]{images/comparison-comparators-16.pdf}
+ \input{images/32-pairwise-cut-16-pairwise.tex}
\end{center}
- \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}
+ \caption{Das \ps{32}-Netzwerk mit 8~Maximum- und 8~Minimumschnitten. Gut zu
+ sehen sind die verbleibenden Komparatoren, die das \ps{16}-Netzwerk
+ bilden.}
+ \label{fig:ps16-from-ps32}
\end{figure}
-Der Graph in Abbildung~\ref{fig:comparison-comparators} zeigt, dass der
-\textsc{SN-Markov}-Algorithmus nicht schlechter ist als der
-\textsc{SN-Evolution}-Algo\-rith\-mus. 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 sich außerdem je
-nach verwendetem 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.
-
-Erwartungsgemäß 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, trat auch jeweils ein
-Sortiernetzwerk mit 121 und 124~Komparatoren auf. Dass Sortiernetzwerke mit so
-vielen Komparatoren im Verlauf des Experiments selbst nach über 100~Millionen
-Iterationen nicht noch einmal erzeugt wurden, ist vermutlich ein Phänomen, das
-mit der Initialisierung durch das \emph{Odd-Even-Transpositionsort}-Netzwerk
-zusammenhängt.
+Für das \emph{Pairwise-Sorting-Netzwerk} ist es vergleichsweise einfach
+regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk ein 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}
-% \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}
+ \input{images/16-pairwise.tex}
+ \end{center}
+ \caption{Das $\operatorname{PS}(16)$-Sortiernetzwerk mit 8~Schnitten
+ ($\operatorname{MIN}(0, 2, 4, 6), \operatorname{MAX}(9, 11, 13, 15)$). Das
+ resultierende 8-Sortiernetzwerk ist $\operatorname{OES}(8)$.}
+ \label{fig:16-pairwise}
+\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}
+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 Verwandtschaft von $\operatorname{PS}(n)$ und \oes{n}
+untersucht \textit{Moritz Mühlenthaler} ausführlich in~\cite{M2009}.
\newpage
\section{Fazit und Ausblick}
projects / diplomarbeit.git / blobdiff