+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 die \emph{Schnittmuster}
+als Individuen. Um zwei Individuen zu rekombinieren werden die ersten
+$r$~Schnitte des einen Schnittmusters verwendet und die letzten
+${c-r}$~Schnitte des zweiten Schmittmusters. $r$ ist eine Zufallsvariable mit
+$0 \leqq r \leqq c$.
+
+Die Mutation setzt entweder die Leitungs-Nummer eines Schnitts~$i$ zufällig
+auf einen neuen Wert $l$ mit $0 \leqq l \le n-i$ oder invertiert die
+Schnitt-Richtung.
+
+% bitones Mergesort-Netzwerk
+
+In \cite{MW2010} zeigen \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka},
+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.
+
+Beispeilsweise geben \textit{Mühlenthaler} und \textit{Wanka} ein
+Sortiernetzwerk mit 16~Eingängen an, das mithilfe der alternativen Mischer
+konstruiert wurde. Dieses Sortiernetzwerk benötigt 68~Komparatoren, 12~weniger
+als das bitone Mergesort-Netzwerk nach Batchers Methode. Gegenüber Batchers
+Methode sparen so konstruierte Sortiernetzwerke ${\frac{1}{4}n(\log n - 1)}$
+Komparatoren ein.
+
+\begin{figure}
+ \begin{center}
+ \input{images/16-ec-1277186619.tex}
+ \end{center}
+ \caption{{\tt images/16-ec-1277186619.tex}: 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-1277186619}
+\end{figure}
+
+Startet man {\sc SN-Evolution-Cut} mit dem 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
+Abbildung~\ref{fig:16-ec-1277186619} zu sehen.
+
+% Odd-Even-Transpositionsort-Netzwerk
+
+Betrachtet man das Sortiernetzwerk in Abbildung~\ref{fig:16-ec-1277186619}, so
+ist keine Ähnlichkeit zu $\operatorname{BS}(32)$ oder $\operatorname{BS}(16)$
+erkennbar -- insbesondere die ersten Schichten des Netzwerks scheinen rein
+zufällig zu sein. Dies 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.
+
+\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}
+
+% 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 an 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.
+
+Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even-Mischer} nicht
+einsetzt und auch nicht auf einem Mischer basiert, ist der
+$\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 Sortiernetzerke, die
+strukturell identisch zu $\operatorname{PS}(8)$ sind -- die Schichten~1 und~2
+sowie 4~und~5 sind vertauscht, was jeweils zum selben Ergebnis nach dem
+Schichtenpaar führt.
+
+\begin{displaymath}
+\textit{Eingang}_i = \left\{ \begin{array}{rl}
+ -\infty & \quad \textrm{falls } i \operatorname{mod} 8 \in \{0, 6\} \\
+ \infty & \quad \textrm{falls } i \operatorname{mod} 8 \in \{2, 4\} \\
+ ? & \quad \mathrm{sonst}
+ \end{array} \right.
+\end{displaymath}
+
+\begin{figure}
+ \begin{center}
+ \input{images/32-pairwise-cut-16-pairwise.tex}
+ \end{center}
+ \caption{PS(32) mit 16 Schnitten zu PS(16).}
+ \label{fig:ps16-from-ps32}
+\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}
+
+Wendet man \textsc{SN-Evolution-Cut} auf $\operatorname{PS}(16)$ an, so kann
+man $\operatorname{OES}(8)$ erhalten.
+
+% Odd-Even-Mergesort-Netzwerk
+
+\todo{Schreibe noch etwas zum Odd-Even-Mergesort-Netzwerk.}