X-Git-Url: https://git.verplant.org/?a=blobdiff_plain;f=diplomarbeit.tex;h=49905bd38753e2f7aa1f45ac038b508bc9b642a8;hb=4fd9c8479d2030c7bc9c43d850b3f164d6bd6caf;hp=7652e83afea7f206cd21e86796a77da738e5cbbd;hpb=722308a3028582c1c3f88a17e3d21cb718f4084b;p=diplomarbeit.git

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index 7652e83..49905bd 100644
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -55,7 +55,7 @@
 \tikzstyle{red box}   = [draw,-,color=red, top color=red!2,bottom color=red!10]
 \tikzstyle{blue box}  = [draw,-,color=blue,top color=blue!2,bottom color=blue!10]
 \tikzstyle{green box} = [draw,-,color=teal,top color=teal!2,bottom color=teal!10]
-\tikzstyle{gray box}   = [draw,-,color=black, top color=black!2,bottom color=black!10]
+\tikzstyle{gray box}  = [draw,-,color=black, top color=black!2,bottom color=black!10]
 
 \maketitle
 \begin{abstract}
@@ -265,9 +265,9 @@ darf.
 \end{figure}
 
 Der Mischer funktioniert folgendermaßen: Gegeben sind zwei Folgen mit je
-${m = \frac{n}{2}}$~Elementen, ${u_0, u_1, \ldots, u_{m-1}}$ und
-${v_0, v_1, \ldots, v_{m-1}}$. Die Folge der $u_i$ sei aufsteigend sortiert,
-die Folge der $v_i$ sei absteigend sortiert:
+${m = \frac{n}{2}}$ Elementen, $U = \left(u_0, u_1, \ldots, u_{m-1}\right)$ und
+$V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die Folge $U$ sei aufsteigend
+sortiert, die Folge $V$ sei absteigend sortiert:
 \begin{eqnarray}
  u_0 \leqq u_1 \leqq &\ldots& \leqq u_{m-1} \\
  v_0 \geqq v_1 \geqq &\ldots& \geqq v_{m-1}
@@ -299,13 +299,15 @@ Muster nun an einen Trichter.
 \subsubsection{Batcher's Bitonic-Mergesort-Netzwerk}
 
 Das Sortiernetzwerk $S(n)$ mit $n$~Eingängen besteht aus zwei Instanzen von
-$S(\frac{n}{2})$, dem Netzwerk mit $\frac{n}{2}$~Eingängen, und dem bitonen
-Mischer $M(n)$. Die Rekursion bricht bei ${n = 1}$~ab -- eine einelementige
+$S(\frac{n}{2})$, dem Netzwerk mit $\frac{n}{2}$~Eingängen und dem bitonen
+Mischer~$M(n)$. Die Rekursion bricht bei ${n = 1}$~ab --~eine einelementige
 Liste ist immer sortiert.
 Das konkrete Netzwerk~$S(8)$ ist in Abbildung~\ref{fig:batcher_08} zu sehen.
 Eingezeichnet sind ebenfalls die beiden Instanzen des Netzwerks~$S(4)$ (rot)
 sowie der bitone Mischer~$M(8)$ (blau).
 
+
+
 %\begin{figure}
 %\begin{center}
 %\includegraphics[viewport=115 491 372 782,width=7.5cm]{images/sn-rekursiver-aufbau.pdf}
@@ -334,7 +336,7 @@ Abschnitt~\ref{sect:odd_even_transpositionsort}) wenig gemein. Auch dieses
 Netzwerk ist von K.~Batcher gefunden worden und wird rekursiv durch einen
 "`Mischer"' definiert.
 
-\subsubsection{Der Odd-Even-Mischer}
+\subsubsection{Der Odd-Even-Mischer}\label{sect:der_odd_even_mischer}
 
 Der {\em Odd-Even-Mischer} ist ein Komperatornetzwerk, dass zwei sortierte
 Folgen zu einer sortierten Ausgabe zusammenfügen kann. Dabei kommt es mit
@@ -407,7 +409,7 @@ Dass die resultierende Folge sortiert ist, lässt sich mit dem
 Da $U$ und $V$ sortiert sind, ist die Anzahl der Nullen in den geraden
 Teilfolgen, $U_{\textrm{gerade}}$ bzw. $V_{\textrm{gerade}}$, größer oder
 gleich der Anzahl der Nullen in den ungeraden Teilfolgen
-$U_{\textrm{ungerade}}$ bzw. $V_{\textrm{ungerade}}$ -- die Einsen verhalten
+$U_{\textrm{ungerade}}$ bzw. $V_{\textrm{ungerade}}$ --~die Einsen verhalten
 sich entsprechend umgekehrt. Das trifft demnach auch auf die Folgen
 $W_{\textrm{gerade}}$ und $W_{\textrm{ungerade}}$ entsprechend zu:
 \begin{eqnarray}
@@ -447,9 +449,9 @@ Abbildung~\ref{fig:oe-post-recursive} dargestellt.
 
 \subsubsection{Das Odd-Even-Mergesort-Netzwerk}
 
-Auch beim {\em Odd-Even-Mergesort-Netzwerk} -- wie beim {\em bitonen
-Mergesort-Netzwerk} -- entsteht das Sortiernetzwerk aus dem {\em
-Odd-Even-Mischer} durch resursives Anwenden auf einen Teil der Eingabe
+Auch beim \emph{Odd-Even-Mergesort-Netzwerk} --~wie beim \emph{bitonen
+Mergesort-Netzwerk}~-- entsteht das Sortiernetzwerk aus dem {\em
+Odd-Even-Mischer} durch rekursives Anwenden auf einen Teil der Eingabe
 (üblicherweise die Hälfte der Leitungen) und anschließendes zusammenfügen.
 Abbildung~\ref{fig:odd_even_mergesort_08} zeigt das Netzwerk für $8$~Eingänge.
 
@@ -457,7 +459,7 @@ Abbildung~\ref{fig:odd_even_mergesort_08} zeigt das Netzwerk für $8$~Eingänge.
 \begin{center}
 \input{images/oe-mergesort-8.tex}
 \end{center}
-\caption{Das {\em Odd-Even-Mergesort} Netzwerk für acht Eingänge.}
+\caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge.}
 \label{fig:odd_even_mergesort_08}
 \end{figure}
 
@@ -470,10 +472,49 @@ Abbildung~\ref{fig:odd_even_mergesort_08} zeigt das Netzwerk für $8$~Eingänge.
 
 \section{Transformation von Sortiernetzwerken}
 
-\begin{itemize}
-\item Komprimieren (Alle Komparatoren so früh wie möglich anwenden).
-\item Normalisieren (Transformation zu Standard-Sortiernetzwerken).
-\end{itemize}
+\subsection{Komprimieren}
+
+\todo{Aus theoretischer Sicht eigentlich eine Trivialität. Rausschmeißen?}
+
+Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
+gleichzeitig ausgewertet werden, wie bereits in
+Abschnitt~\ref{sect:einleitung_sortiernetzwerke} beschrieben. Unter
+\emph{Komprimieren} wird eine (Neu-)Gruppierung in die kleinstmögliche Anzahl
+von \emph{Schichten} verstanden.
+
+Diese Anzahl ist insbesondere beim automatisierten Bewerten von
+Komparatornetzwerken interessant. \dots
+
+\subsection{Normalisieren}
+
+\begin{figure}
+  \centering
+  \subfigure[$S(8)$ (nach Konstruktion)]{\input{images/batcher-8-nonstd.tex}\label{fig:bitonic-nonstd}}
+  \subfigure[$S(8)$ (normalisiert)]{\input{images/batcher-8-std.tex}\label{fig:bitonic-std}}
+  \caption{Jedes Sortiernetzwerk kann in ein Standard-Sortiernetzwerk
+  transformiert werden. Gezeigt ist das bitone Sortiernetzwerk nach der
+  intuitiven Konstruktion und die normalisierte Variante.}
+  \label{fig:beispiel_normalisieren}
+\end{figure}
+
+Ein \emph{Standard-Sortiernetzwerk} oder \emph{normalisiertes Sortiernetzwerk}
+ist ein Sortiernetzwerk, dessen Komparatoren alle in die selbe Richtung
+zeigen. Jedes Sortiernetzwerk kann in eine normaliesierte Variante
+transformiert werden. Dazu gibt beispielsweise \emph{Knuth} (\todo{Verweis})
+einen Algorithmus an.
+
+Abbildung~\ref{fig:beispiel_normalisieren} zeigt das das
+bitone Sortiernetzwerk in zwei Varianten. Abbildung~\ref{fig:bitonic-nonstd}
+zeigt das Netzwerk nach der Konstruktionsvorschrift, siehe auch
+Abbildung~\ref{fig:bitonic-merge-normal}: In den ersten drei Schichten werden
+die unter und die obere Hälfte gegenläufig sortiert. Das heißt dass nach drei
+Schritten die eine Hälfte auf- und die andere Hälfte absteigend sortiert ist. 
+In den Schichten~4 bis~6 folgt der bitone Mischer entsprechend der rekursiven
+Definition.
+
+In Abbildung~\ref{fig:bitonic-std} ist die normalisierte Version des bitonen
+Mergesort-Netzwerks zu sehen. Alle Komparatoren zeigen hier in die gleiche
+Richtung.
 
 \subsection{Zwei Netzwerke kombinieren}
 
@@ -483,7 +524,25 @@ Abbildung~\ref{fig:odd_even_mergesort_08} zeigt das Netzwerk für $8$~Eingänge.
 \item Nach dem Pairwise sorting-network Schema.
 \end{itemize}
 
-\subsection{Leitungen entfernen}
+\subsection{Leitungen entfernen}\label{sect:leitungen_entfernen}
+
+Man kann ein gegebenes Sortiernetzwerk mit $n$~Eingängen auf ein
+Sortiernetzwerk mit $(n-1)$~Leitungen verkleinern, indem man eine Leitung
+entfernt. Zunächst wird angenommen, dass das Minimum oder das Maximum an einem
+der Eingänge anliegt. Der Weg durch das Netzwerk zum entsprechenden Ausgang
+ist dadurch fest vorgegeben, insbesondere welche Komparatoren dafür sorgen,
+dass die Leitung gewechselt wird und welche nicht.
+Abbildung~\ref{fig:oe-transposition-cut0} zeigt den Weg eines Maximums durch
+das {\em Odd-Even-Transpositionsort-Netzwerk}.
+
+Im nächsten Schritt werden alle beteiligten Komparatoren gelöscht bzw.
+ersetzt: Komparatoren, die {\em nicht} zu einem Wechsel der Leitung geführt
+haben, werden ersatzlos gelöscht. Diese Komparatoren sind in
+Abbildung~\ref{fig:oe-transposition-cut0} grün markiert. Die Komparatoren, die
+zum Wechsel der Leitung geführt haben, werden durch sich kreuzende Leitungen
+ersetzt. Das Resultat zeigt Abbildung~\ref{fig:oe-transposition-cut1}. Wenn
+man die Maximum-Leitung entfernt (Abbildung~\ref{fig:oe-transposition-cut2}),
+erhält man ein Sortiernetzwerk für $(n-1)$~Leitungen.
 
 \begin{figure}
   \centering
@@ -499,6 +558,14 @@ Abbildung~\ref{fig:odd_even_mergesort_08} zeigt das Netzwerk für $8$~Eingänge.
   letzten Abbildung ist $\textrm{OET}(7)$ markiert.}
 \end{figure}
 
+Die letzte Abbildung, \ref{fig:oe-transposition-cut3}, zeigt das
+Sortiernetzwerk wieder mit den üblichen geraden Leitungen und die rot
+markierten Komparatoren wurden verschoben, so dass sich eine kompaktere
+Darstellung ergibt. Ausserdem ist das
+{\em Odd-Even-Transpositionsort-Netzwerk} für sieben Werte markiert. Der
+zusätzliche Komparator vor dem $\textrm{OET}(7)$ hat keinen Einfluss auf die
+Ausgabe und kann entfernt werden.
+
 \begin{itemize}
 \item Min-Richtung
 \item Max-Richtung
@@ -506,6 +573,81 @@ Abbildung~\ref{fig:odd_even_mergesort_08} zeigt das Netzwerk für $8$~Eingänge.
 
 \section{Der evolutionäre Ansatz}
 
+Um einen evolutionären Algorithmus für Sortiernetzwerke zu entwickeln, werden
+die vorgestellten Methoden kombiniert.
+
+\subsection{Bewertungsfunktion}
+
+Um Sortiernetzwerke überhaupt optimieren zu können, muss zunächst die
+{\em Güte} eines Netzwerkes definiert werden. Prinzipiell gibt es zwei Ziele,
+die interessant sind:
+\begin{itemize}
+  \item Möglichst wenige Komparatoren ("`klein"')
+  \item Möglichst wenige Schichten ("`schnell"')
+\end{itemize}
+
+Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das
+kleinste bekannte Sortiernetzwerk für 16~Eingänge besteht aus 60~Komparatoren
+in 10~Schichten. Das schnellste Netzwerk besteht aus 61~Komparatoren in nur
+9~Schichten.
+
+Eine Gütefunktion, die die beiden Ziele "`klein"' und "`schnell"'
+berücksichtigen kann, hat die folgende allgemeine Form:
+\begin{equation}
+  \mathit{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.
+
+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.
+
+\subsection{Selektion}
+
+...
+
+\subsection{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
+{\em Odd-Even-Mischer} (Abschnitt~\ref{sect:der_odd_even_mischer}), um die
+beiden Netzwerke zu einem Netzwerk mit $2n$~Leitungen zusammenzufügen.
+Anschließend entfernen wir zufällig $n$~Leitungen wie in
+Abschnitt~\ref{sect:leitungen_entfernen} beschrieben.
+
+Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft
+erhält.
+
+\subsection{Mutation}
+
+Zu einem vollständigen evolutionären Algorithmus gehört außerdem eine Mutation
+--~eine zufällige Veränderung einer Lösung. Leider ist es nicht möglich ein
+Sortiernetzwerk zufällig zu verändern aber trotzdem 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.
+
+Um das Potenzial einer Mutation abzuschätzen habe ich in den evolutionären
+Algorithmus eine Überprüfung eingebaut. Unmittelbar vor dem Einfügen in die
+Population überprüft das Programm die Notwendigkeit jedes einzelnen
+Komparators. Dazu wurde nacheinander jeder Komparator entfernt und überprüft,
+ob das verbleibende Netzwerk die Sortiereigenschaft noch besitzt.
+
 \begin{itemize}
 \item Güte von Sortiernetzwerken (Anzahl der Komparatoren, Anzahl der
 Schichten, kobiniert)
@@ -528,7 +670,7 @@ acht Eingängen. Es besteht aus 19~Komparatoren in 6~Schichten.}
 \begin{center}
 \input{images/08-e2-1237993371.tex}
 \end{center}
-\caption{\tt images/08-e2-1237993371.tex}
+\caption{{\tt images/08-e2-1237993371.tex}: 19~Komparatoren in 6~Schichten}
 \label{fig:08-e2-1237993371}
 \end{figure}
 
@@ -536,7 +678,7 @@ acht Eingängen. Es besteht aus 19~Komparatoren in 6~Schichten.}
 \begin{center}
 \input{images/09-e2-1237997073.tex}
 \end{center}
-\caption{\tt images/09-e2-1237997073.tex}
+\caption{{\tt images/09-e2-1237997073.tex}: 25~Komparatoren in 8~Schichten}
 \label{fig:09-e2-1237997073}
 \end{figure}
 
@@ -544,15 +686,256 @@ acht Eingängen. Es besteht aus 19~Komparatoren in 6~Schichten.}
 \begin{center}
 \input{images/09-e2-1237999719.tex}
 \end{center}
-\caption{\tt images/09-e2-1237999719.tex}
+\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}
+
+% ============
+
+\section{Shmoo-Äquivalenz}
+
+Die folgenden 16-Eingang-Sortiernetzwerke wurden alle mit dem
+\emph{Algorithmus~1} gefunden. Sie haben alle 63~Komparatoren in 10~Schichten,
+jeweils die selbe Anzahl wie Odd-Even-Mergesort.
+
+Um wiederkehrende Muster in den hinteren Schichten der erzeugten
+Sortiernetzwerke besser untersuchen zu können, wurden die erzeugten Netzwerke
+in Gruppen aufgeteilt. Zwei Netzwerke befinden sich dann in der selben
+Gruppen, wenn die Nullen bzw. Einsen, die auf einer Leitung vorkommen können,
+nach der 5.~Schicht (Schicht~4, da bei Null mit dem Zählen begonnen wird)
+nicht mehr ändert. Das heißt, dass die Schichten 0--4 unterschiedlich
+aufgebaut sind, aber den selben Effekt erziehlen. Die Schichten 5--9 sind
+hingegen innerhalb einer Gruppe austauschbar und oft (immer?) identisch.
+
+Die Anzahl der Netzwerke in den jeweiligen Gruppen ist unterschiedlich. Zur
+Zeit sind in den Gruppen so viele Netzwerke:\\
+\begin{tabular}{|l|r|r|} \hline
+Gruppe~0 & 21 & $50,0\%$ \\
+Gruppe~1 & 10  & $23,8\%$ \\
+Gruppe~2 & 6  & $14,3\%$ \\
+Gruppe~3 & 3  & $7,1\%$ \\
+Gruppe~4 & 2  & $4,8\%$ \\ \hline
+\end{tabular}
+
+Die hinteren Schichten zwischen den Gruppen~1 und~3 schauen so aus, als wären
+sie nur gespiegelt. Warum kommt Gruppe~1 aber viel häufiger vor? Ggf. eine
+Konsequenz aus dem Normieren?
+
+Dito für die Gruppen~2 und~4. Warum ist die eine häufiger?
+
+Ist Gruppe~0 symmetrisch bzgl. der Leitungen?
+
+% Gruppe 0
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group0/16-e1-1258009316.tex}
+\end{center}
+\caption{{\tt images/16-e1/group0/16-e1-1258009316.tex}: 63~Komparatoren in
+10~Schichten.}
+\label{fig:16-e1-1258009316}
+\end{figure}
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group0/16-e1-1258010866.tex}
+\end{center}
+\caption{{\tt images/16-e1/group0/16-e1-1258010866.tex}: 63~Komparatoren in
+10~Schichten.}
+\label{fig:16-e1-1258010866}
+\end{figure}
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group0/16-e1-1258011861.tex}
+\end{center}
+\caption{{\tt images/16-e1/group0/16-e1-1258011861.tex}: 63~Komparatoren in
+10~Schichten.}
+\label{fig:16-e1-1258011861}
+\end{figure}
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group0/16-e1-1259060992.tex}
+\end{center}
+\caption{{\tt images/16-e1/group0/16-e1-1259060992.tex}: 63~Komparatoren in
+10~Schichten.}
+\label{fig:16-e1-1259060992}
+\end{figure}
+
+%\begin{figure}
+%\begin{center}
+%\input{images/16-e1/group0/16-e1-1259061148.tex}
+%\end{center}
+%\caption{{\tt images/16-e1/group0/16-e1-1259061148.tex}: 63~Komparatoren in
+%10~Schichten.}
+%\label{fig:16-e1-1259061148}
+%\end{figure}
+
+% Gruppe 1
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group1/16-e1-1258009982.tex}
+\end{center}
+\caption{{\tt images/16-e1/group1/16-e1-1258009982.tex}: 63~Komparatoren in 10~Schichten.
+Schichten 4--9 identisch zu 16-e1-1258030047 (Gruppe~1).}
+\label{fig:16-e1-1258009982}
+\end{figure}
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group1/16-e1-1258010023.tex}
+\end{center}
+\caption{{\tt images/16-e1/group1/16-e1-1258010023.tex}: 63~Komparatoren in
+10~Schichten.}
+\label{fig:16-e1-1258010023}
+\end{figure}
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group1/16-e1-1258029734.tex}
+\end{center}
+\caption{{\tt images/16-e1/group1/16-e1-1258029734.tex}: 63~Komparatoren in
+10~Schichten.}
+\label{fig:16-e1-1258029734}
+\end{figure}
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group1/16-e1-1258030047.tex}
+\end{center}
+\caption{{\tt images/16-e1/group1/16-e1-1258030047.tex}: 63~Komparatoren in
+10~Schichten.}
+\label{fig:16-e1-1258030047}
+\end{figure}
+
+%\begin{figure}
+%\begin{center}
+%\input{images/16-e1/group1/16-e1-1258034768.tex}
+%\end{center}
+%\caption{{\tt images/16-e1/group1/16-e1-1258034768.tex}: 63~Komparatoren in
+%10~Schichten.}
+%\label{fig:16-e1-1258034768}
+%\end{figure}
+
+% Gruppe 2
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group2/16-e1-1258029063.tex}
+\end{center}
+\caption{{\tt images/16-e1/group2/16-e1-1258029063.tex}: 63~Komparatoren in
+10~Schichten.}
+\label{fig:16-e1-1258029063}
+\end{figure}
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group2/16-e1-1258034821.tex}
+\end{center}
+\caption{{\tt images/16-e1/group2/16-e1-1258034821.tex}: 63~Komparatoren in
+10~Schichten.}
+\label{fig:16-e1-1258034821}
+\end{figure}
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group2/16-e1-1259054993.tex}
+\end{center}
+\caption{{\tt images/16-e1/group2/16-e1-1259054993.tex}: 63~Komparatoren in
+10~Schichten.}
+\label{fig:16-e1-1259054993}
+\end{figure}
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group2/16-e1-1259058588.tex}
+\end{center}
+\caption{{\tt images/16-e1/group2/16-e1-1259058588.tex}: 63~Komparatoren in
+10~Schichten.}
+\label{fig:16-e1-1259058588}
+\end{figure}
+
+%\begin{figure}
+%\begin{center}
+%\input{images/16-e1/group2/16-e1-1259063485.tex}
+%\end{center}
+%\caption{{\tt images/16-e1/group2/16-e1-1259063485.tex}: 63~Komparatoren in
+%10~Schichten.}
+%\label{fig:16-e1-1259063485}
+%\end{figure}
+
+%\begin{figure}
+%\begin{center}
+%\input{images/16-e1/group2/16-e1-1259063618.tex}
+%\end{center}
+%\caption{{\tt images/16-e1/group2/16-e1-1259063618.tex}: 63~Komparatoren in
+%10~Schichten.}
+%\label{fig:16-e1-1259063618}
+%\end{figure}
+
+% Gruppe 3
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group3/16-e1-1258012027.tex}
+\end{center}
+\caption{{\tt images/16-e1/group3/16-e1-1258012027.tex}: 63~Komparatoren in
+10~Schichten.}
+\label{fig:16-e1-1258012027}
+\end{figure}
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group3/16-e1-1258037039.tex}
+\end{center}
+\caption{{\tt images/16-e1/group3/16-e1-1258037039.tex}: 63~Komparatoren in
+10~Schichten.}
+\label{fig:16-e1-1258037039}
+\end{figure}
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group3/16-e1-1259065042.tex}
+\end{center}
+\caption{{\tt images/16-e1/group3/16-e1-1259065042.tex}: 63~Komparatoren in
+10~Schichten.}
+\label{fig:16-e1-1259065042}
+\end{figure}
+
+% Gruppe 4
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group4/16-e1-1259060520.tex}
+\end{center}
+\caption{{\tt images/16-e1/group4/16-e1-1259060520.tex}: 63~Komparatoren in 10~Schichten.
+(Gruppe~4).}
+\label{fig:16-e1-1259060520}
+\end{figure}
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group4/16-e1-1259067171.tex}
+\end{center}
+\caption{{\tt images/16-e1/group4/16-e1-1259067171.tex}: 63~Komparatoren in 10~Schichten.
+(Gruppe~4).}
+\label{fig:16-e1-1259067171}
+\end{figure}
+
 \subsection{Güte}
 
 \begin{itemize}
-\item So gut kann man mindestens werden \em{($\rightarrow$ Bitonic-Mergesort,
-vermute ich)}.
+\item So gut kann man mindestens werden {\em ($\rightarrow$ Bitonic-Mergesort, vermute ich)}.
 \item Wie gut die Netzwerke werden, hängt stark vom verwendeten \em{Mischer} ab.
 \end{itemize}
 
@@ -564,6 +947,152 @@ vermute ich)}.
 \item Anzahl der erreichbaren Sortiernetzwerke.
 \end{itemize}
 
+\section{Optimierung der Schnitte}
+
+Der \emph{evolution-cut}-Algorithmus nimmt ein gegebenes Sortiernetzwerk mit
+$n$~Leitungen und sucht die beste Sequenz von $c$~Min- und Max-Schnitten um
+ein ${(n-c)}$-Sortiernetzwerk zu erhalten.
+
+Bei diesem Algorithmus werden die \emph{Schnitt-Sequenzen} als Individuen
+verwendet. 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.
+
+\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
+  \emph{evolution-cut} aus dem Bitonic-Mergesort-Netzwerk $M(32)$ durch
+  16~Schnitte erzeugt.}
+\label{fig:16-ec-1277186619}
+\end{figure}
+
+Wendet man den \emph{evolution-cut}-Algorithmus auf das
+Bitonic-Mergesort-Netzwerk $M(n)$ an und setzt die Anzahl der Schnitte~$c$ auf
+$\frac{n}{2}$, so erhält man Sortiernetzwerke, die weniger Komparatoren
+benötigen als $M(\frac{n}{2})$.
+
+Das Sortiernetzwerk in Abbildung~\ref{fig:16-ec-1277186619} ist entstanden,
+indem der Algorithmus \emph{evolution-cut} auf das $M(32)$-Sortiernetzwerk
+angewendet wurde. Der Algorithmus fand eine Schnitt-Sequenz aus 16~Schnitten,
+die ein Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in 10~Schichten
+erzeugt. Das $M(16)$-Sortiernetzwerk besteht aus 80~Komparatoren in
+10~Schichten.
+
+Dieses Ergebnis deckt sich mit dem Sortiernetzwerk, dass
+\emph{Moritz Mühlenthaler} und \emph{Rolf Wanka} in ihrer Veröffentlichung
+„Improving Bitonic Sorting by Wire Elimination“ vorstellen. Sie verwenden
+Schnitte, um Komparatoren beim bitonen $(n,n)$-Mischer enizusparen. Ein
+sukzessive aus optimieren Mischern aufgebautes Sortiernetzwerk spart
+--~verglichen mit dem Bitonic-Mergesort-Netzwerk~-- $\frac{1}{4}n(\log n - 1)$
+Komparatoren ein. Bei einem Sortiernetzwerk mit 16~Leitungen also
+12~Komparatoren -- 68 statt 80.
+
+\begin{figure}
+\begin{center}
+\input{images/32-ec-1277190372.tex}
+\end{center}
+\caption{{\tt images/32-ec-1277190372.tex}: Sortiernetzwerk mit 32~Leitungen
+  und 206~Komparatoren in 15~Schichten. Das Netzwerk wurde von dem Algorithmus
+  \emph{evolution-cut} aus dem Bitonic-Mergesort-Netzwerk $M(64)$ durch
+  32~Schnitte erzeugt.}
+\label{fig:32-ec-1277190372}
+\end{figure}
+
+Abbildung~\ref{fig:32-ec-1277190372} zeigt ein 32-Sortiernetzwerk, dass vom
+\emph{evolution-cut}-Algorithmus aus dem $M(64)$-Netzwerk erzeugt wurde. Es
+besteht aus 206~Komparatoren in 15~Schichten -- 34~Komparatoren weniger als
+$M(32)$ und zwei Komparatoren weniger als das Netzwerk, das nach Mühlenthaler
+und Wankas Methode konstruiert wird. Die Anzahl der Schichten ist bei allen
+Netzwerken gleich.
+
+\textbf{TODO:} $M(128) \rightarrow n=64$: 584~Komparatoren in 21~Schichten
+möglich (nach ca. 600k Iterationen). Moritz und Rolf: $672-80=592$
+Komparatoren; $M(64)$: 672~Komparatoren.
+
+Schnitt-Sequenz:
+MIN( 92)
+MAX( 80)
+MIN(100)
+MAX( 54)
+MAX(102)
+MAX( 53)
+MAX(105)
+MAX(  6)
+MAX( 99)
+MAX( 79)
+MAX( 26)
+MIN(111)
+MAX( 12)
+MIN( 22)
+MAX( 61)
+MAX( 72)
+MAX( 68)
+MIN( 80)
+MAX( 80)
+MAX( 99)
+MAX(105)
+MAX(  0)
+MIN(  8)
+MAX( 40)
+MAX( 74)
+MAX( 40)
+MAX( 40)
+MIN( 56)
+MAX( 27)
+MAX( 13)
+MAX(  1)
+MAX( 81)
+MAX( 17)
+MAX(  4)
+MIN( 36)
+MIN( 22)
+MAX( 13)
+MIN( 72)
+MAX( 24)
+MAX(  5)
+MIN( 10)
+MAX( 59)
+MIN( 37)
+MAX( 65)
+MAX( 46)
+MAX( 73)
+MAX( 58)
+MAX( 29)
+MAX( 65)
+MIN( 23)
+MAX( 56)
+MAX( 11)
+MIN( 75)
+MIN( 51)
+MIN( 46)
+MIN( 34)
+MAX( 32)
+MAX(  6)
+MAX( 37)
+MIN(  4)
+MIN( 28)
+MIN( 20)
+MAX( 33)
+MAX( 34)
+
+% images/32-ec-1277190372.tex
+
 \section{Empirische Beobachtungen}
 
 \begin{itemize}