+ \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[\textsc{SN-Evolution-Cut}]{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:sn-evolution:bewertung}.
+
+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 ungleich 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.
+
+Die Eingabe für \textsc{SN-Evolution-Cut} ist ein $n$-Sortiernetzwerk und eine
+Zahl $k$, $1 \leqq k < n$, die angibt wie viele Leitungen entfernt werden
+sollen. Der Rückgabewert des \textsc{SN-Evolution-Cut}-Algorithmus ist ein
+\emph{$k$-Schnittmuster}. Wird das Schnittmuster auf das Sortiernetzwerk, mit
+dem der Algorithmus gestartet wurde, angewendet, entsteht ein möglichst
+schnelles und effizientes Sortiernetzwerk mit $m = n - k$ Leitungen. Da mit
+dem Eingabe-Netzwerk und dem zurückgegebenen $k$-Schnittmuster das
+$m$-Sortiernetzwerk eindeutig bestimmt ist, werden im Folgenden sowohl das
+$k$-Schnittmuster als auch das $m$-Sortiernetzwerk als Ausgabe von
+\textsc{SN-Evolution-Cut} bezeichnet.
+
+\subsection[Bitones Mergesort-Netzwerk]{Versuche mit dem bitonen Mergesort-Netzwerk}
+\label{sect:sn-evolution-cut:bs}
+
+Wenn der \textsc{SN-Evolution-Cut}-Algorithmus mit dem \emph{bitonen
+Mergesort}-Netzwerk \bs{n} gestartet wird und $k$~Leitungen entfernen soll,
+ergeben die gefundenen Schnittmuster in vielen Fällen effizientere Netzwerke
+als \bs{n-k}. Wird \textsc{SN-Evolution-Cut} beispielsweise mit \bs{22} und $k
+= 6$ gestartet, resultiert das gefundene Schnittmuster in einem
+Sortiernetzwerk mit 67~Komparatoren, 13~Komparatoren weniger als \bs{16}
+benötigt. Eines der Sortiernetzwerke, die auf diese Art und Weise generiert
+wurde, ist in Abbildung~\ref{fig:16-ec-from-bs22} zu sehen.
+
+\begin{figure}
+ \begin{center}
+ \input{images/16-ec-from-bs22.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 16~Leitungen und 67~Komparatoren in