+Bei welchen Parametern \textsc{SN-Evolution-Cut} effiziente
+19-Sortiernetzwerke findet, ist Tabelle~\ref{tbl:ec-ps-19} zu entnehmen. Für
+$n = 31$, $k = 12$ und $n = 32$, $k = 13$ werden 19-Sortiernetzwerke mit der
+selben Effizienz und Geschwindigkeit wie \oes{19} erzeugt. Das
+19-Sortiernetzwerk, das auf diese Art und Weise aus \ps{32} erzeugt wurde, ist
+in Abbildung~\ref{fig:19-ec-from-ps32} dargestellt.
+
+\begin{table}
+ \begin{center}
+ \rowcolors{2}{black!5}{}
+ \begin{tabular}{|r|r|r|}
+ \hline
+ $n$ & Komp. & Schichten \\
+ \hline
+ 20 & 97 & 15 \\
+ 21 & 96 & 15 \\
+ 22 & 96 & 15 \\
+ 23 & 97 & 14 \\
+ 24 & 96 & 14 \\
+ 25 & 93 & 14 \\
+ 26 & 92 & 14 \\
+ 27 & 94 & 14 \\
+ 28 & 94 & 14 \\
+ 29 & 92 & 14 \\
+ 30 & 92 & 14 \\
+ \rowcolor{green!10!white!95!black}
+ 31 & 91 & 14 \\
+ \rowcolor{green!10}
+ 32 & 91 & 14 \\
+ 33 & 101 & 15 \\
+ 34 & 104 & 15 \\
+ 35 & 106 & 15 \\
+ 36 & 107 & 15 \\
+ 37 & 106 & 15 \\
+ 38 & 102 & 15 \\
+ \hline
+ \ps{19} & 97 & 15 \\
+ \oes{19} & 91 & 14 \\
+ \hline
+ \end{tabular}
+ \end{center}
+ \caption{Anzahl der Komparatoren und Schichten von 19-Sortiernetzwerken, die
+ von \textsc{SN-Evolution-Cut} aus \ps{n}, $n = 20, \dots, 38$ erzeugt
+ wurden.}
+ \label{tbl:ec-ps-19}
+\end{table}
+
+\begin{figure}
+ \begin{center}
+ \input{images/19-ec-from-ps32.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 19~Leitungen und 91~Komparatoren in
+ 14~Schichten. Das Netzwerk wurde von dem Algorithmus
+ \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting}-Netzwerk
+ $\operatorname{PS}(32)$ erzeugt.}
+ \label{fig:19-ec-from-ps32}
+\end{figure}
+
+An den Daten in Tabelle~\ref{tbl:ec-ps-19} fällt auf, dass die Effizienz und
+Geschwindigkeit der Ergebnisse für $n > 32$ schlechter werden. Das
+\emph{Pairwise-Sorting}-Netzwerk ist Leitungszahlen, die Zweierpotenzen sind,
+besonders effizient und schnell. Um der Vermutung nachzugehen, dass der
+\textsc{SN-Evolution-Cut}-Algorithmus für $\ps{n = 2^d}$ besonders effiziente
+Schnittmuster findet, wurde \textsc{SN-Evolution-Cut} mit \ps{32} und $k = 1
+\dots 16$ gestartet. Die Ergebnisse sind in Tabelle~\ref{tbl:ec-ps-32}
+zusammengefasst.
+
+\begin{table}
+ \begin{center}
+ \rowcolors{2}{black!5}{}
+ \begin{tabular}{|r|r|r|}
+ \hline
+ $m$ & Komp. & Schichten \\
+ \hline
+ 16 & 69 & 11 \\
+ 17 & 77 & 13 \\
+ 18 & 89 & 13 \\
+ 19 & 91 & 14 \\
+ 20 & 97 & 14 \\
+ 21 & 107 & 15 \\
+ 22 & 114 & 15 \\
+ 23 & 122 & 15 \\
+ 24 & 127 & 15 \\
+ 25 & 138 & 15 \\
+ 26 & 146 & 15 \\
+ 27 & 155 & 15 \\
+ 28 & 161 & 15 \\
+ 29 & 171 & 15 \\
+ 30 & 178 & 15 \\
+ 31 & 186 & 15 \\
+ \hline
+ \end{tabular}
+ \end{center}
+ \caption{Anzahl der Komparatoren und Schichten von $m$-Sortiernetzwerken,
+ die von \textsc{SN-Evolution-Cut} nach 5.000.000 Iterationen aus \ps{32}
+ erzeugt wurden.}
+ \label{tbl:ec-ps-32}
+\end{table}
+
+% Geschwindigkeit
+
+Die Schnittmuster, die \textsc{SN-Evolution-Cut} für das
+\emph{Pairwise-Sorting}-Netzwerk berechnet, können zu schnelleren
+Sortiernetzwerken als \ps{m} führen. Beispielsweise konnte aus \ps{24} ein
+18-Sortiernetzwerk erzeugt werden, das mit 13~Schichten zwei parallele
+Schritte im Vergleich zu \ps{18} einspart. Eine Darstellung dieses
+Sortiernetzwerks befindet sich in Abbildung~\ref{fig:18-ec-from-ps24}. Für
+andere $m$ wurde die Geschwindigkeit des \emph{Pairwise-Sorting}-Netzwerks
+nicht übertroffen und im Fall von $m = 16$ wurde die Geschwindigkeit nicht
+einmal erreicht.
+
+\begin{table}
+ \begin{center}
+ \rowcolors{2}{black!5}{}
+ \begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
+ \hline
+ & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
+ \hline
+ 9 & 6 & & & & & & & & & & & & & & & \\
+ 10 & 6 & 10 & & & & & & & & & & & & & & \\
+ 11 & 6 & 9 & 10 & & & & & & & & & & & & & \\
+ 12 & 6 & 8 & 9 & 10 & & & & & & & & & & & & \\
+ 13 & 6 & 8 & 9 & 10 & 10 & & & & & & & & & & & \\
+ 14 & 6 & 8 & 9 & 10 & 10 & 10 & & & & & & & & & & \\
+ 15 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & & & & & & & & & \\
+ 16 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & & \\
+ 17 & 7 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 11 & & & & & & & \\
+ 18 & 7 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 11 & 15 & & & & & & \\
+ 19 & 7 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 11 & 15 & 15 & & & & & \\
+ 20 & 7 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 11 & 15 & 15 & 15 & & & & \\
+ 21 & 6 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 12 & 14 & 15 & 15 & 15 & & & \\
+ 22 & 6 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 12 & 14 & 14 & 15 & 15 & 15 & & \\
+ 23 & 6 & 9 & 9 & 10 & 10 & 10 & 11 & 11 & 11 & 13 & 14 & 14 & 15 & 15 & 15 & \\
+ 24 & 6 & 9 & 9 & 10 & 10 & 10 & 11 & 11 & 11 & 13 & 13 & 14 & 14 & 15 & 15 & 15 \\
+ \hline
+ \ps{m} & 6 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 15 & 15 & 15 & 15 & 15 & 15 & 15 \\
+ \hline
+ \end{tabular}
+ \end{center}
+ \caption{Anzahl der Schichten der Ergebnisse von
+ \textsc{SN-Evolution-Cut} mit verschiedenen Größen des
+ \emph{Pairwise-Sorting}-Netzwerks und unterschiedlichen Werten für~$k$.
+ Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \ps{n} an, jede
+ Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
+ Ausgabenetzwerks.}
+ \label{tbl:ec-ps-speed}
+\end{table}
+
+% Beispiel Geschwindigkeit
+
+\begin{figure}
+ \begin{center}
+ \input{images/18-ec-from-ps24.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 18~Leitungen und 89~Komparatoren in
+ 13~Schichten. Das Netzwerk wurde von dem Algorithmus
+ \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting}-Netzwerk
+ $\operatorname{PS}(24)$ erzeugt.}
+ \label{fig:18-ec-from-ps24}
+\end{figure}
+
+% 2-er Potenz
+
+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.
+
+Bei dem \emph{Pairwise-Sorting}-Netzwerk $\ps{n=2^d}$ ist das anders. Startet
+man \textsc{SN-Evolution-Cut} mit $\operatorname{PS}(32)$ und der Vorgabe,
+16~Leitungen zu entfernen, kann der Algorithmus ein Sortiernetzwerk
+zurückgeben, das die gleiche Anzahl Komparatoren und Schichten wie
+$\operatorname{PS}(16)$ und $\operatorname{OES}(16)$ hat. Eines dieser
+Sortiernetzwerke ist in Abbildung~\ref{fig:16-ec-from-ps32} dargestellt.
+Dieses Ergebnis demonstriert, dass sich die Ergebnisse in den gezeigten
+Tabellen oft durch zusätzliche Iterationen verbessern lassen.
+
+\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 \textsc{SN-Evolution-Cut} auf
+$\operatorname{PS}(16)$ angewendet wird: In diesem Fall kann ein
+8-Schnittmuster ausgegeben werden, das \emph{Odd-Even-Mergesort}-Netzwerk
+\oes{8} aus \ps{16} erzeugt.. 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}
+
+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