+Der Eliminierungsschritt kann iterativ angewandt werden, um aus einem
+Sortiernetzwerk mit $n$~Ein\-gängen Sortiernetzwerke mit $n-1$, $n-2$,
+$n-3$,~\dots Eingängen zu erzeugen. Insbesondere können wir auf diese Art und
+Weise einen Sortiernetzwerk mit $2n$~Eingängen wieder auf ein Sortiernetzwerk
+mit $n$~Eingängen reduzieren.
+
+\subsubsection{Der \textsc{SN-Evolution-Cut}-Algorithmus}
+
+Bei einem Sortiernetzwerk mit $n$~Eingängen gibt es $2n$~Möglichkeiten eine
+Leitung zu entfernen: Auf jeder der $n$~Leitungen kann sowohl das Minimum als
+auch das Maximum angenommen werden. Wendet man das Verfahren iterativ an, um
+ein $n$-Sortiernetzwerk auf ein $m$-Sortiernetzwerk zu reduzieren, ergeben
+sich insgesamt
+\begin{displaymath}
+ \prod_{i=n}^{m+1} 2i = 2^{n-m} \frac{n!}{m!}
+ \quad (n > m)
+\end{displaymath}
+Möglichkeiten. Diese Möglichkeiten sind nicht alle unterschiedlich. Legt man
+beispielsweise das Minimum auf die unterste Leitung und das Maximum auf die
+oberste Leitung eines Standard-Sortiernetzwerks, führen beide Reihenfolgen zum
+selben Ergebnis.
+
+\textit{Moritz Mühlenthaler} zeigt in seiner Arbeit (\todo{Referenz}), dass
+es möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise
+Maximum vorzubelegen. Dadurch wird die Anzahl der möglichen Schnitte
+reduziert, die Menge der erreichbaren Sortiernetzwerke bleibt aber
+unverändert. Die Anzahl der möglichen „Schnittmuster“ setzt sich zusammen aus
+der Anzahl von Möglichkeiten, $n-m$~Leitungen aus $n$ Leitungen auszuwählen,
+und die möglichen Minimum-~/ Maximum-Muster. Damit ergibt sich folgende
+Formel:
+\begin{displaymath}
+ 2^{n-m} \cdot \left( \begin{array}{c} n \\ n-m \end{array} \right)
+ = 2^{n-m} \cdot \frac{n!}{(n-m)! m!}
+ = 2^{n-m} \cdot \frac{n!}{m!} \cdot \frac{1}{(n-m)!}
+ \quad (n > m)
+\end{displaymath}
+
+Die Anzahl der möglichen Schnitte wird mit der Anzahl der zu entfernenden
+Leitungen sehr schnell sehr groß. Um ein Sortiernetzwerk mit 32~Eingängen auf
+ein Sortiernetzwerk mit 16~Ein\-gängen zu reduzieren sind 16~Schnitte notwendig,
+für die es bereits etwa ${3,939 \cdot 10^{13}}$ Möglichkeiten gibt. Ein
+Ausprobieren aller Möglichkeiten ist für große Netzwerke nicht oder nur unter
+erheblichem Ressourcenaufwand möglich.
+
+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 die
+\emph{Schnitt-Sequenzen} als Individuen. Eine \emph{Schnitt-Sequenz} ist eine
+Liste mit $c$~Schnitten, die jeweils durch die Start-Leitung und die Richtung
+\textit{Min} beziehungsweise \textit{Max} gegeben ist. Der Algorithmus wendet
+jeden Schnitt einzeln an, so dass eine Leitungsnummer mehrfach in einer
+Schnittsequenz vorkommen kann. Die höchste zulässige Leitungsnummer ist
+abhängig von der Position des Schnitts in der Sequenz. Der Schnitt an
+Position~$i$ darf höchstens die Leitungsnummer~${n-i-1}$
+enthalten.\footnote{Die niedrigste Leitungsnummer ist $0$, die höchste
+Leitungsnummer eines $n$-Sortiernetzwerks ist $n-1$.}
+
+Um zwei Individuen zu rekombinieren werden die ersten $r$~Schnitte der einen
+Schnitt-Sequenz verwendet und die letzten ${c-r}$~Schnitte der zweiten
+Sequenz. $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.
+
+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.
+
+\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}
+
+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 Eingaben. 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.
+
+Anders verhält sich das \emph{Pairwise-Sorting-Netzwerk}
+$\operatorname{PS}(n)$, das \textit{Ian Parberry} in seiner Arbeit „The
+Pairwise Sorting Network“ 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)$. Der Algorithmus gibt
+auch nach zahlreichen Versuchen nur eines von zwei Sortiernetzwerken zurück,
+die beide sehr symmetrisch sind und eine saubere Struktur aufweisen. Eines der
+beiden Sortiernetzwerke ist in Abbildung~\ref{fig:16-ec-from-ps32}
+dargestellt, das andere Sortiernetzwerk unterscheidet sich lediglich dadurch,
+dass die zweite und dritte Schicht vertauscht sind.
+
+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.
+
+Wendet man \textsc{SN-Evolution-Cut} auf $\operatorname{PS}(16)$ an, so kann
+man $\operatorname{OES}(8)$ erhalten.
+