+\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}, die \textit{Rolf Wanka} in~\cite{W2006} für
+schwierige Zählprobleme vorstellt. Zunächst generiert man eine Menge~$S$ von
+$k$~unterschiedlichen Schnittmustern. Anschließend werden $n$~Schnittmuster
+zufällig erzeugt und überprüft, ob sie in der Menge~$S$ enthalten sind. Unter
+der Annahme, dass auf diese Art und Weise Sortiernetzwerke zufällig und
+gleichverteilt erzeugt werden, entspricht das Verhältnis der zufälligen
+Schnittmuster, die in $S$ enthalten sind, und $n$ gleich dem Verhältnis von
+$k$ und der Anzahl der unterschiedlichen Schnittmuster insgesamt. Damit kann
+die Anzahl der unterschiedlichen Schnittmuster abgeschätzt werden.
+
+\begin{figure}
+ \begin{center}
+ \includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-10000-1000000-32.pdf}
+ \end{center}
+ \caption{Abschä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{Abschä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 unterschiedlichen
+Schnittmustern erzeugt. Trotzdem wurden nach 1.000.000 Iterationen nur 385
+Schnittmuster gefunden, die zu einem Schnittmuster in der Menge äquivalent
+waren. Daraus ergibt sich eine Abschätzung von $2,6 \cdot 10^8$
+unterschiedlichen Schnittmustern -- zwei Zehnerpotenzen mehr als bei den
+vorherigen Sortiernetzwerken, aber immer noch fünf Zehnerpotenzen kleiner als
+die Anzahl der \emph{möglichen} Schnittmuster.
+
+\newpage
+\section{Der \textsc{SN-Evolution}-Algorithmus}
+\label{sect:sn-evolution}
+
+Der \textsc{SN-Evolution}-Algorithmus ist ein \emph{evolutionärer
+Algorithmus}, der die in den vorherigen Abschnitten beschriebenen Mischer
+(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 Netzwerks 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 bekannte 16-Sortiernetzwerk
+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.
+
+Als guter Standardansatz für \textsc{SN-Evolution} 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{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 / (Gütesumme + reziproke Güte)
+ Gütesumme := Gütesumme + reziproke Güte
+
+ mit Wahrscheinlichkeit P
+ {
+ Auswahl := Individuum
+ }
+ }
+ gib Auswahl zurück
+\end{verbatim}
+
+\subsection{Rekombination}
+\label{sect:sn-evolution: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
+\emph{Odd-Even}-Mischer (Abschnitt~\ref{sect:der_odd_even_mischer}), um die
+beiden Netzwerke zu einem Netzwerk mit $2n$~Leitungen zusammenzufügen.
+Anschließend werden zufällig $n$~Leitungen mit einem $n$-Schnittmuster wie in
+Abschnitt~\ref{sect:leitungen_entfernen} beschrieben entfernt.
+
+Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft
+erhält. Entsprechend muss nicht aufwendig überprüft werden, ob das
+Komparatornetzwerk die Sortiereigenschaft besitzt. Der Nachteil ist, dass
+nicht alle Sortiernetzwerke auf diese Art und Weise erzeugt werden können.
+
+\subsection{Mutation}
+
+Zu einem vollständigen evolutionären Algorithmus gehört außerdem 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 Rechenaufwands
+-- 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. Daher
+wurde beim \textsc{SN-Evolution}-Algorithmus auf eine Mutation verzichtet.
+
+\subsection[Bitoner Mischer]{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 \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.
+
+\subsection[Odd-Even-Mischer]{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 -- die von
+\textsc{SN-Evolution} ausgegebenen Netzwerke waren effizienter als das
+rekursiv aus dem verwendeten Mischer aufgebaute Sortiernetzwerk -- mit dem
+\emph{Odd-Even-Merge}-Netzwerk 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 Geschwindigkeit und Effizienz, ein Beispiel hierfür ist in
+Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen. Sortiernetzwerkde, die
+effizienter als $\operatorname{OES}(n)$ sind, konnten leider nicht beobachtet
+werden. Wenn $n$ keine Zweietpotenz ist, kann \textsc{SN-Evolution} unter
+Umständen Sortiernetzwerke ausgeben, die schneller als \oes{n} sind.
+
+%\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, der zu einem gegebenen Sortiernetzwerk und einer gewünschten
+Leitungszahl ein Schnittmuster sucht, dass ein Sortiernetzwerk mit einer
+möglichst geringen Anzahl von Komparatoren und Schichten ergibt. Zur Bewertung
+von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}. Mit diesem
+Algorithmus wurden zu einer Reihe von „interessanten“ Netzwerken möglichst
+gute Schnittmuster gesucht.
+
+Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet \emph{Schnittmuster}, die
+in Abschnitt~\ref{sect:anzahl_schnittmuster} definiert wurden, als Individuen.
+Ein Individuum besteht aus einer Liste von $n$~Zahlen, die entweder 1, $-1$
+oder 0 sind. Dieser Werte entsprechen Maximum, Minimum und unbelegt. Bei einem
+$k$-Schnittmuster sind genau $k$ Zahlen nicht Null.
+
+Um zwei Individuen zu rekombinieren werden die ersten $r$~Werte des einen
+Schnittmusters und die letzten ${n-r}$~Schnitte des zweiten Schnittmusters
+verwendet. $r$ ist eine Zufallsvariable mit $0 \leqq r \leqq n$. Anschließend
+werden zufällig Werte auf Null beziehungsweise 1 oder $-1$ gesetzt, um die
+Anzahl der Schnitte zu korrigieren.
+
+Die Mutation vertauscht entweder die Werte von zwei zufälligen Positionen oder
+multipliziert den Wert einer Leitung mit $-1$, um die Schnittrichtung zu
+invertieren.
+
+\subsection[Bitones Mergesort-Netzwerk]{Versuche mit dem bitonen Mergesort-Netzwerk}
+
+\textit{Moritz Mühlenthaler} und \textit{Rolf Wanka} zeigen in~\cite{MW2010},
+wie man einen bitonen Mischer, der nach Batchers Methode konstruiert wurde,
+durch systematisches Entfernen von Leitungen in einen ebenfalls bitonen
+Mischer mit der Hälfte der Leitungen transformiert. Diese alternativen Mischer
+sparen im Vergleich zu den Mischern, die nach Batchers Methode konstruiert
+werden, Komparatoren ein.
+
+Beispielsweise geben \textit{Mühlenthaler} und \textit{Wanka} ein
+Sortiernetzwerk mit 16~Eingängen an, das mithilfe der alternativen Mischer
+konstruiert wurde. Dieses Sortiernetzwerk be\-nö\-tigt 68~Komparatoren,
+12~weniger als das \emph{bitone Mergesort}-Netzwerk nach Batchers Methode.
+Gegenüber Batchers Methode sparen so konstruierte Sortiernetzwerke
+${\frac{1}{4}n(\log n - 1)}$ Komparatoren ein.
+
+\begin{figure}
+ \begin{center}
+ \input{images/16-ec-from-bs32.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in
+ 10~Schichten. Das Netzwerk wurde von dem Algorithmus
+ \textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort-Netzwerk}
+ $\operatorname{BS}(32)$ durch 16~Schnitte erzeugt.}
+ \label{fig:16-ec-from-bs32}
+\end{figure}
+
+\begin{figure}
+ \begin{center}
+ \input{images/16-ec-from-bs32-normalized.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in
+ 10~Schichten. Das Netzwerk wurde von dem Algorithmus
+ \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk
+ $\operatorname{BS}(32)$ durch 16~Schnitte erzeugt.}
+ \label{fig:16-ec-from-bs32-normalized}
+\end{figure}
+
+Startet man {\sc SN-Evolution-Cut} mit dem \emph{bitonen Mergesort}-Netzwerk
+$\operatorname{BS}(32)$ und der Vorgabe 16~Leitungen zu entfernen, liefert der
+Algorithmus Sortiernetzwerke, die ebenfalls aus 68~Komparatoren bestehen. Ein
+16-Sortiernetzwerk, das auf diese Weise generiert wurde, ist in den
+Abbildungen~\ref{fig:16-ec-from-bs32} und~\ref{fig:16-ec-from-bs32-normalized}
+zu sehen. Abbildung~\ref{fig:16-ec-from-bs32} zeigt $\operatorname{BS}(32)$
+und das Schnittmuster ${\operatorname{MIN}(0, 5, 9, 11, 15, 17, 20, 22, 26,
+29, 30)}$, ${\operatorname{MAX}(2, 4, 13, 19, 24)}$, das durch
+\textsc{SN-Evolution-Cut} gefunden wurde.
+Abbildung~\ref{fig:16-ec-from-bs32-normalized} zeigt das 16-Sortiernetzwerk
+nachdem das Schnittmuster angewandt und das Netzwerk normalisiert wurde. Eine
+Ähnlichkeit zu $\operatorname{BS}(32)$ oder $\operatorname{BS}(16)$ ist in
+diesem Netzwerk nicht mehr erkennbar -- insbesondere die ersten Schichten des
+Netzwerks scheinen rein zufällig zu sein.
+
+\begin{figure}
+ % 0:MAX 1:MAX 4:MIN 6:MAX 9:MAX 11:MAX 14:MIN 15:MAX 18:MAX 19:MAX 21:MAX
+ % 23:MIN 24:MAX 25:MAX 30:MIN 31:MIN 32:MAX 34:MAX 36:MIN 37:MAX 40:MAX
+ % 43:MAX 46:MIN 47:MAX 48:MAX 49:MAX 54:MIN 55:MAX 56:MAX 58:MIN 60:MAX
+ % 63:MAX
+ \begin{center}
+ \input{images/32-ec-from-bs64.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 32~Leitungen und 206~Komparatoren in
+ 15~Schichten. Das Netzwerk wurde von dem Algorithmus
+ \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk
+ $\operatorname{BS}(64)$ durch 32~Schnitte erzeugt. Das zugehörige
+ Schnittmuster ist
+ $\operatorname{MIN}(4, 14, 23, 30, 31, 36, 46, 54, 58)$,
+ $\operatorname{MAX}(0, 1, 6, 9, 11, 15, 18, 19, 21, 24, 25, 32, 34, 37,
+ 40, 43, 47, 48, 49, 55, 56, 60, 63)$.}
+ \label{fig:32-ec-from-bs64}
+\end{figure}
+
+Das Ergebnis von \textit{Mühlenthaler} und \textit{Wanka}, die den bitonen
+Mischer optimiert und anschließend aus diesen Mischern ein Sortiernetzwerk
+konstruiert haben, kann demnach auch erreicht werden, wenn
+$\operatorname{BS}(32)$ auf ein 16-Sortiernetzwerk reduziert wird. Bei anderen
+Größen, beispielsweise wenn man $\operatorname{BS}(64)$ auf ein
+32-Sortiernetzwerk reduziert, kann das Ergebnis sogar noch übertroffen werden,
+wie in Abbildung~\ref{fig:32-ec-from-bs64} zu sehen: Ein nach Batchers Methode
+konstruiertes Sortiernetzwerk benötigt 240~Komparatoren, ein aus den
+optimierten Mischern aufgebautes Netzwerk verbessert die Kosten auf
+208~Komparatoren. Das in Abbildung~\ref{fig:32-ec-from-bs64} dargestellte
+Sortiernetzwerk benötigt lediglich 206~Komparatoren. Die Komparatoren aller
+dieser Netzwerke können in 15~Schichten angeordnet werden, so dass die
+Geschwindigkeit dieser Sortiernetzwerke gleich ist.
+
+Leider sind die Schnittmuster, die \textsc{SN-Evolution-Cut} ausgibt, sehr
+unregelmäßig. Bisher ist es nicht gelungen eine Konstruktionsanweisung für
+gute Schnittmuster anzugeben.
+
+Entscheidend für das Ergebnis eines Schnittmusters scheint beim \emph{bitonen
+Mergesort}-Netzwerk die Aufteilung der Minimum- und Maximumschnitte zu sein.
+Von Hundert 16-Schnittmustern für $\operatorname{BS}(32)$, die in
+Sortiernetzwerken mit 68~Komparatoren in 10~Schichten resultieren, hatten 73
+ein Verhältnis von $5/11$, 13 hatten ein Verhältnis von $4/12$ und 14 hatten
+ein Verhältnis von $3/13$ Minimum- beziehungsweise Maximumschnitten. Da sich
+die Schnittmuster aufgrund der Symmetrie des bitonen Mergesort-Netzwerks
+leicht invertieren lassen, werden der Fall, dass es mehr Minimumschnitte, und
+der Fall, dass es mehr Maximumschnitte gibt, nicht unterschieden.
+
+\begin{figure}
+ \centering
+ \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 9~Schichten. Das
+ Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{22} erzeugt.]{\input{images/11-ec-from-bs22-fast.tex}\label{fig:11-ec-from-bs22-fast}}
+ \subfigure[12-Sortiernetzwerk aus 42~Komparatoren in 9~Schichten. Das
+ Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{24} erzeugt.]{\input{images/12-ec-from-bs24-fast.tex}\label{fig:12-ec-from-bs24-fast}}
+ \caption{Startet man \textsc{SN-Evolution-Cut} mit \bs{22} und \bs{24}, kann
+ der Algorithmus schnelle Sortiernetzwerke ausgeben.}
+ \label{fig:11-12-ec-from-bs22-bs24}
+\end{figure}
+
+Verwendet man als Eingabe für \textsc{SN-Evolution-Cut} Instanzen des
+\emph{bitonen Mergesort}-Netzwerks, deren Leitungszahl keine Zweierpotenz ist,
+können Sortiernetzwerke zurückgegeben werden, die sowohl schneller als auch
+effizienter als das entsprechende \emph{bitone Mergesort}-Netzwerk sind. Die
+folgende Tabelle listet einige interessante Fälle auf. Die Eingabe für
+\textsc{SN-Evolution-Cut} war jeweils das \emph{bitone Mergesort}-Netzwerk mit
+der doppelten Leitungszahl. Die Abbildungen~\ref{fig:11-12-ec-from-bs22-bs24}
+und~\ref{fig:23-ec-from-bs46} zeigen beispielhaft ein 11-, 12- und
+23-Sortiernetzwerk, die aus \bs{22}, \bs{24} und \bs{46} generiert wurden.
+
+\begin{center}
+\begin{tabular}{|r|r|r|r|r|}
+\hline
+Leitungen & Komparatoren & Schichten & Komparatoren & Schichten \\
+ & \textsc{SN-EC} & \textsc{SN-EC} & \bs{n} &
+ \bs{n} \\
+\hline
+11 & 37 & 9 & 39 & 10 \\
+12 & 42 & 9 & 46 & 10 \\
+19 & 93 & 13 & 98 & 14 \\
+20 & 102 & 13 & 106 & 14 \\
+% 20: # sn-cut 2:MAX 3:MIN 4:MIN 9:MIN 10:MIN 13:MIN 14:MIN 15:MIN 19:MIN 20:MAX 24:MAX 26:MIN 27:MAX 29:MIN 31:MAX 33:MIN 34:MAX 35:MIN 37:MIN 39:MAX
+21 & 109 & 14 & 114 & 15 \\
+22 & 116 & 14 & 123 & 15 \\
+23 & 124 & 14 & 133 & 15 \\
+\hline
+\end{tabular}
+\end{center}
+
+\begin{figure}
+ \begin{center}
+ \input{images/23-ec-from-bs46-fast.tex}
+ \end{center}
+ \caption{23-Sortiernetzwerk mit 124~Komparatoren in 14~Schichten. Das
+ Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{46} mit dem
+ Schnittmuster $\operatorname{MIN}(2, 4, 9, 12, 20, 22, 28, 30, 32, 33, 37,
+ 38, 41)$, $\operatorname{MAX}(1, 5, 16, 19, 21, 24, 25, 35, 36, 43)$
+ erzeugt.}
+ \label{fig:23-ec-from-bs46}
+\end{figure}
+
+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
+\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, dass 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 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}
+ \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}.
+
+\subsection[Odd-Even-Mergesort-Netzwerk]{Versuche mit dem Odd-Even-Mergesort-Netzwerk}
+\label{sect:sn-evolution-cut:oes}
+
+In Abschnitt~\ref{sect:anzahl_schnittmuster} wurde bereits untersucht, wie
+viele \emph{unterschiedliche} Schnittmuster die konstruktiven Sortiernetzwerke
+$\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\footnote{Auf dem Computer, auf dem diese
+Arbeit geschrieben wurde, dauerte es in den meisten Fällen weniger als eine
+Sekunde bis ein entsprechendes Schnittmuster gefunden wurde.} ein gutes
+16-Schnittmuster findet.
+
+Eines der 16-Schnittmuster für \oes{32}, die ein Sortiernetzwerk erzeugen, das
+bezüglich Effizienz und Geschwindigkeit identisch ist zu \oes{16}, ist
+$\operatorname{MIN}(1, 6, 11, 14, 17, 23, 26, 29)$, $\operatorname{MAX}(2, 7,
+8,$ $13, 18, 21, 27, 31)$. Das Schnittmuster ist in
+Abbildung~\ref{fig:16-ec-from-oes32-cut} veranschaulicht, das resultierende
+Netzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32} zu sehen.
+
+\begin{figure}
+ \begin{center}
+ \input{images/16-ec-from-oes32-cut.tex}
+ \end{center}
+ \caption{Visualisierung eines 16-Schnittmusters, das auf
+ $\operatorname{OES}(32)$ angewendet wieder ein schnelles und effizientes
+ Sortiernetzwerk ergibt.}
+ \label{fig:16-ec-from-oes32-cut}
+\end{figure}
+
+\begin{figure}
+ \begin{center}
+ \input{images/16-ec-from-oes32.tex}
+ \end{center}
+ \caption{16-Sortiernetzwerk mit 63~Komparatoren in 10~Schichten.
+ Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution-Cut} aus dem
+ \emph{Odd-Even-Mergesort}-Netzwerk $\operatorname{OES}(32)$ durch
+ 16~Schnitte erzeugt.}
+ \label{fig:16-ec-from-oes32}
+\end{figure}
+
+Bei diesem Schnittmuster fällt auf, dass es für jeweils vier Eingänge (0--3,
+4--7, \dots, 28--31) einen Minimum- und einen Maximumschnitt gibt. Aus dieser
+Beobachtung kann man das regelmäßige Schnittmuster
+\begin{displaymath}
+\textit{Eingang}_i = \left\{ \begin{array}{rl}
+ \infty & \quad \textrm{falls } i \bmod 4 = 0 \\
+ -\infty & \quad \textrm{falls } i \bmod 4 = 3 \\
+ ? & \quad \mathrm{sonst}
+ \end{array} \right.
+\end{displaymath}
+ableiten. Es entfernt die Hälfte der Leitungen, vorausgesetzt die Anzahl der
+Leitungen ist durch Vier teilbar. Das Schnittmuster erzeugt effiziente
+Netzwerke, wenn die Anzahl der Leitungen $n = 2^d$ eine Zweierpotenz ist. Ein
+32-Sortiernetzwerk, das mit diesem Schnittmuster aus \oes{64} erzeugt wurde,
+ist in Abbildung~\ref{fig:32-ec-from-oes64} zu sehen.
+
+\begin{figure}
+ \begin{center}
+ \input{images/32-ec-from-oes64.tex}
+ \end{center}
+ \caption{32-Sortiernetzwerk mit 191~Komparatoren in 15~Schichten.
+ Das Netzwerk wurde mit einem regelmäßigen Schnittmuster aus dem
+ \emph{Odd-Even-Mergesort}-Netzwerk \oes{64} erzeugt.}
+ \label{fig:32-ec-from-oes64}
+\end{figure}
+
+Wenn die Anzahl der Leitungen keine Zweierpotenz ist, erreichen die so
+erzeugten Sortiernetzwerke die Effizienz des
+\emph{Odd-Even-Mergesort}-Netzwerks nicht. Wendet man das Schnittmuster
+beispielsweise auf \oes{24} an, so erhält man ein Sortiernetzwerk mit
+43~Komparatoren -- \oes{12} kommt mit 41~Komparatoren aus. Die Geschwindigkeit
+beider Sortiernetzwerke ist mit 10~Schichten identisch.
+
+Startet man hingegen den \textsc{SN-Evolution-Cut}-Algorithmus mit \oes{24}
+und dem Ziel, ein gutes 12-Schnittmuster zu finden, hängt die Ausgabe von der
+verwendeten Gütefunktion ab. Werden effiziente Netzwerke bevorzugt, findet der
+Algorithmus Schnittmuster wie $\operatorname{MIN}(6, 7, 8, 9, 16, 17, 20,
+22)$, $\operatorname{MAX}(2, 4, 12, 14)$, dessen Ergebnis in
+Abbildung~\ref{fig:12-ec-from-oes24-efficient} zu sehen ist. Das resultierende
+Sortiernetzwerk besteht aus 41~Komparatoren, die in 10~Schichten angeordnet
+werden können. Damit ist das Netzwerk bezüglich Effizienz und Geschwindigkeit
+gleichauf mit \oes{12}. Werden hingegen schnelle Sortiernetzwerke bevorzugt,
+werden stattdessen Schnittmuster wie $\operatorname{MIN}(6, 7, 11, 12, 15,
+16)$, $\operatorname{MAX}(1, 3, 10, 17, 20, 23)$ ausgegeben. Das Ergebnis
+dieses Schnittmusters ist in Abbildung~\ref{fig:12-ec-from-oes24-fast} zu
+sehen. Das Sortiernetzwerk besteht aus 43~Komparatoren, die in 9~Schichten
+angeordnet sind. Das heißt, dass das resultierende Netzwerk zwar nicht so
+effizient wie \oes{12}, dafür aber schneller als \oes{12} und \bs{12} ist.
+
+\begin{figure}
+ \centering
+ \subfigure[Effizientes 12-Sortiernetzwerk aus 41~Komparatoren in
+ 10~Schichten, das von \textsc{SN-Evolution-Cut} aus dem
+ \emph{Odd-Even-Mergesort}-Netzwerk generiert
+ wurde.]{\input{images/12-ec-from-oes24-efficient.tex}\label{fig:12-ec-from-oes24-efficient}}
+ \subfigure[Schnelles 12-Sortiernetzwerk aus 43~Komparatoren in 9~Schichten,
+ das von \textsc{SN-Evolution-Cut} aus dem \emph{Odd-Even-Mergesort}-Netzwerk
+ generiert
+ wurde.]{\input{images/12-ec-from-oes24-fast.tex}\label{fig:12-ec-from-oes24-fast}}
+ \caption{Startet man \textsc{SN-Evolution-Cut} mit \oes{24}, hängt das
+ Ergebnis von der Bewertungsfunktion ab.}
+ \label{fig:12-ec-from-oes24}
+\end{figure}
+
+Das \oes{24}-Sortiernetzwerk ist kein Einzelfall: \textsc{SN-Evolution-Cut}
+findet Sortiernetzwerke, die schneller sind als das entsprechende
+\emph{Odd-Even-Mergesort}-Netzwerk, unter anderem für das Sortiernetzwerke mit
+22, 24, 38, 40, 42, 44 und 46 Leitungen. In der folgenden Tabelle sind einige
+schnelle Netzwerke, die von \textsc{SN-Evolution-Cut} generiert werden können,
+charakterisiert. Die Eingabe für \textsc{SN-Evolution-Cut} war jeweils das
+\emph{Odd-Even-Mergesort}-Netzwerk mit der doppelten Leitungszahl.
+\begin{center}
+\begin{tabular}{|r|r|r|r|r|}
+\hline
+Leitungen & Komparatoren & Schichten & Komparatoren & Schichten \\
+ & \textsc{SN-EC} & \textsc{SN-EC} & \oes{n} & \oes{n} \\
+\hline
+11 & 38 & 9 & 37 & 10 \\
+12 & 43 & 9 & 41 & 10 \\
+19 & 93 & 13 & 91 & 14 \\
+20 & 101 & 13 & 97 & 14 \\
+21 & 108 & 14 & 107 & 15 \\
+22 & 116 & 14 & 114 & 15 \\
+23 & 125 & 14 & 122 & 15 \\
+\hline
+\end{tabular}
+\end{center}
+Abbildung~\ref{fig:23-ec-from-oes46} zeigt beispielhaft ein
+23-Sortiernetzwerk, das aus \oes{46} generiert wurde. Bemerkenswert an diesem
+Sortiernetzwerk ist insbesondere, dass \textsc{SN-Evolution-Cut} mit der
+Eingabe \bs{46} ein besseres Ergebnis liefert als mit der Eingabe \oes{46}. In
+beiden Fällen wird ein Sortiernetzwerk zurückgegeben, das im Vergleich zu
+\bs{23} beziehungsweise \oes{23} eine Schicht einspart. Allerdings ist das
+Sortiernetzwerk auf Basis von \bs{46} (Abbildung~\ref{fig:23-ec-from-bs46})
+effizienter, da es nur 124~Komparatoren benötigt.
+
+\begin{figure}
+ \begin{center}
+ \input{images/23-ec-from-oes46-fast.tex}
+ \end{center}
+ \caption{23-Sortiernetzwerk mit 125~Komparatoren in 14~Schichten.
+ Das Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \oes{46} mit dem
+ Schnittmuster $\operatorname{MIN}(6, 7, 9, 17, 19, 22, 29, 30, 32, 34, 38,
+ 44)$, $\operatorname{MAX}(4, 5, 11, 16, 18, 25, 31, 36, 39, 42, 45)$
+ erzeugt.}
+ \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:
+
+\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{Fazit und Ausblick}
+
+Mit dem Entfernen von Leitungen aus bekannten Sortiernetzwerken lassen sich
+interessante Ergebnisse erzielen. Dies zeigte \textit{Moritz Mühlenthaler}
+bereits in~\cite{M2009}. Die in dieser Arbeit vorgestellten Methoden und
+Resultate machen deutlich, dass sich mit diesem Verfahren noch weitere
+interessante Beobachtungen machen lassen.
+
+Das \emph{Odd-Even-Mergesort}-Netzwerk wird sowohl von \textsc{SN-Evolution},
+\textsc{SN-Evolution-Cut} und \textsc{SN-Markov} erreicht. Wenn die Anzahl der
+Leitungen keine Zweierpotenz ist, kann gegebenenfalls ein schnelleres
+Sortiernetzwerk erzeugt werden. Einige Beispiele hierfür wurden in
+Abschnitt~\ref{sect:sn-evolution-cut:oes} aufgezeigt.
+
+Das \emph{bitone Mergesort}-Netzwerk kann in Bezug auf Effizienz von den
+vorgestellten Algorithmen übertroffen werden. Der Algorithmus
+\textsc{SN-Evolution-Cut} kann das Ergebnis von \textit{Mühlenthaler} und
+\textit{Wanka} (\cite{MW2010}) für ein 16-Sortiernetzwerk reproduzieren und
+für ein 32-Sortiernetzwerk sogar noch übertreffen. Der
+\textsc{SN-Evolution}-Algorithmus fand 16-Sortiernetzwerke, die gegenüber dem
+Ergebnis von \textsc{SN-Evolution-Cut} beziehungsweise~\cite{MW2010} einen
+weiteren Komparator einsparen.
+
+Leider weisen die Sortiernetzwerke, die von den angegebenen Algorithmen
+zurückgegeben werden, keine Struktur auf, die sich zur Angabe einer
+Konstruktionsanweisung eigenen würde. Für das \emph{Pairwise-Sorting}- und das
+\emph{Odd-Even-Mergesort}-Netzwerk mit Zweierpotenzen als Leitungszahl wurden
+regelmäßige Schnittmuster angegeben. Diese ergeben Sortiernetzwerke, die so
+schnell und effizient sind wie die vergleichbaren \oes{n} und \ps{n}
+Netzwerke.
+
+Die Anzahl der \emph{unterschiedlichen} Schnitte von verschiedenen
+Sortiernetzwerken wurde experimentell bestimmt und gezeigt, dass es deutlich
+weniger \emph{unterschiedliche} als \emph{mögliche} Schnittmuster gibt. Das
+bedeutet im Umkehrschluss, dass die gewonnenen Sortiernetzwerke mit mehreren
+Schnittmustern erreicht werden können.
+
+Die Möglichkeiten der Optimierung von Sortiernetzwerken mit
+\emph{Evolutionären Algorithmen} sind durch die in dieser Arbeit vorgestellten
+Herangehensweisen bei weitem nicht erschöpft. Im Folgenden werden Ansätze
+umrissen, mit denen an die Untersuchungen in dieser Arbeit nahtlos angeknüpft
+werden könnte.
+
+\subsection{Ausblick: Das \textit{Pairwise-Sorting}-Netzwerk und \textsc{SN-Evolution}}
+
+Die aktuelle Implementierung von \textsc{SN-Evolution}
+(Abschnitte~\ref{sect:sn-evolution}
+beziehungsweise~\ref{sect:implementierung}) kann sowohl den \emph{bitonen
+Mischer} als auch den \emph{Odd-Even}-Mischer verwenden, um zwei Individuen zu
+rekombinieren. Das \emph{Pairwise-Sorting}-Netzwerk verwendet zwar keinen
+Mischer, es ist aber ebenfalls rekursiv über kleinere Versionen von sich
+selbst definiert. Das heißt, dass \ps{n} aus zwei Instanzen von
+$\ps{\frac{n}{2}}$ und zusätzlichen Komparatoren besteht, die die Eingabe für
+die kleineren Sortiernetzwerke vorbereiten und anschließend für eine sortierte
+Ausgabe sorgen. Anstelle von $\ps{\frac{n}{2}}$ können beliebige
+Sortiernetzwerke mit $\frac{n}{2}$~Leitungen verwendet werden.
+
+Dies ließe sich für \textsc{SN-Evolution} nutzen, um zwei Individuen zu
+rekombinieren. Da es für das \emph{Pairwise-Sorting}-Netzwerk sehr viele
+\emph{unterschiedliche} Schnittmuster gibt
+(Abschnitt~\ref{sect:anzahl_schnittmuster}), ist es möglich, dass die
+Verwendung dieser Rekombinationsmethode neue Ergebnisse ermöglicht. Leider
+wird die Aussicht auf Erfolg durch die Tatsache geschmälert, dass keine
+$n$-Schnittmuster für \ps{2n} gefunden werden konnten, die zu besseren
+$n$-Sortiernetzwerken als \ps{n} führen.
+
+\subsection{Ausblick: Kooperation von \textsc{SN-Evolution} und \textsc{SN-Evolution-Cut}}
+
+Ähnlich zu der parasitären \emph{Co-Evolution}, die \textit{W.~Daniel Hillis}
+in~\cite{H1990} beschreibt, könnte man versuchen, die Algorithmen
+\textsc{SN-Evolution} und \textsc{SN-Evolution-Cut} zu kombinieren. Nach dem
+Zusammenfügen von zwei $n$-Sortiernetzwerken könnte der Algorithmus
+\textsc{SN-Evolution-Cut} beispielsweise einen möglichst guten Schnitt für
+\emph{dieses} Netzwerk ermitteln. Da sich die Lösungen, die Evolutionäre
+Algorithmen in ihre Population aufnehmen, in den ersten Schritten rasch
+verbessern, könnten selbst weniger Iterationen von \textsc{SN-Evolution-Cut}
+die Zwischenlösungen von \textsc{SN-Evolution} deutlich verbessern.
+
+Alternativ könnte man -- analog zur Herangehensweise von \textit{Hillis} --
+eine zweite Population von Schnittmustern evolvieren, die für die
+Sortiernetzwerke in der Population von \textsc{SN-Evolution} besonders gut
+funktionieren. In jeder Iteration wendet man alle oder eine zufällige Menge
+Schnittmuster auf das zusammengeführte Netzwerk an und gibt dem besten
+Ergebnis den Zuschlag. Anschließend erfährt das entsprechende Schnittmuster
+eine Aufwertung, so dass es wahrscheinlicher wird, dass \emph{dieses}
+Schnittmuster zur nächsten Generation beiträgt. Im Gegensatz zum Ansatz der
+parasitären Eingaben entsteht eine \emph{Synergie} zweier Populationen, die
+das Gesamtergebnis oder zumindest die Konvergenzgeschwindigkeit verbessern
+könnte.
+
+\newpage
+\section{Implementierung}
+\label{sect:implementierung}
+
+Alle in dieser Arbeit beschriebenen Versuche wurden mit einer eigens
+entwickelten C-Bibliothek, \textit{libsortnetwork}, und zugehörigen
+Kommandozeilen-Programmen durchgeführt. Die Bibliothek wurde unter der
+\textit{GNU Lesser General Public License} (LGPL) in der Version~2.1
+veröffentlicht; die Kommandozeilen-Programme, die in vielen Fällen lediglich
+Funktionalität der Bibliothek auf der Kommandozeile zur Verfügung stellen,
+stehen unter der \textit{GNU General Public License}, Version~2. Diese
+Lizenzen räumen einem Benutzer weitreichende Rechte ein, unter anderem das
+Programm beliebig zu verwenden, zu studieren, zu verändern sowie veränderte
+und unveränderte Kopien zu veröffentlichen.
+
+Die Programmierschnittstelle (API) der Bibliothek orientiert sich an
+Paradigmen der \textit{objektorientierten Programmierung}. Beispielsweise kann
+mit der Funktion \texttt{sn\_network\_ create()} ein neues Zustands-Objekt
+erzeugt werden, für das mehrere Manipulations-Methoden, zum Beispiel
+\texttt{sn\_network\_comparator\_add()}, zur Verfügung stehen. Auf diese Art
+und Weise kann die Bibliothek leicht erweitert werden, ohne dass bestehende
+Programme angepasst werden müssen.
+
+Die meisten Kommandozeilen-Programmen lesen ein Komparatornetzwerk von der
+Standard-Eingabe und schreiben ihr Ergebnis auf die Standard-Ausgabe. Um
+Beispielsweise eine \emph{normalisierte} Variante des \emph{bitonen
+Mergesort}-Netzwerks \bs{42} zu erzeugen, kann folgendes Kommando verwendet
+werden:
+\begin{verbatim}
+ $ sn-bitonicsort 42 | sn-normalize >sn-42
+\end{verbatim}
+Dieses Prinzip, kleine Programme \emph{eine} Aufgabe erledigen zu lassen und
+es einfach zu ermöglichen, Programme zu verketten, ist eines der
+Grundprinzipien des UNIX-Be\-triebs\-sys\-tems. Es hat sich in den letzten
+Jahrzehnten und beim Verfassen dieser Arbeit als sehr flexibel und mächtig
+erwiesen.
+
+Funktionen, die von Kommandozeilen-Programmen zur Verfügung gestellt werden,
+sind unter anderem das Erzeugen des \emph{Odd-Even-Mergesort}-, \emph{bitonen
+Mergesort}- und \emph{Pairwise-Sorting}-Netzwerks, das Normalisieren von
+Sortiernetzwerken, Anwendung von Schnittmustern auf Sortiernetzwerke und
+Anwendung eines Komparatornetzwerks auf eine Eingabepermutation. Das
+Darstellen von Sortiernetzwerken wird ebenfalls angeboten, beispielsweise
+wurden die Sortiernetzwerke in dieser Arbeit mit dem Kommando \texttt{sn-tex}
+visualisiert.
+
+\textit{libsortnetwork} kann unter der Web-Adresse
+\url{http://octo.it/libsortnetwork/} unentgeltlich heruntergeladen werden.
+
+\newpage
+\bibliography{references}
+\bibliographystyle{plain}