Label "sect:sn-evolution".

[diplomarbeit.git] / diplomarbeit.tex

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index a7f0bf9..c3bc372 100644 (file)
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -98,6 +98,7 @@ das hinbekomme bzw. Recht behalte.}
 
 \subsection{Motivation}\label{sect:motivation}
 
 
 \subsection{Motivation}\label{sect:motivation}
 

+\todo{Schreibe noch etwas zu …}

 \begin{itemize}
 \item Sortiernetzwerke sind toll, weil $\ldots$
 \item Sortiernetzwerke sind einfach erklärt, aber trotzdem kompliziert.
 \begin{itemize}
 \item Sortiernetzwerke sind toll, weil $\ldots$
 \item Sortiernetzwerke sind einfach erklärt, aber trotzdem kompliziert.


@@ -327,12 +328,55 @@ Sortiereigenschaft erhält. Transformationen von Sortiernetzwerken werden in
 Abschnitt~\ref{sect:tranformation} beschrieben, ein Algorithmus, der Mutation
 einsetzt, wird in Abschnitt~\ref{sect:sn-evolution-cut} vorgestellt.
 
 Abschnitt~\ref{sect:tranformation} beschrieben, ein Algorithmus, der Mutation
 einsetzt, wird in Abschnitt~\ref{sect:sn-evolution-cut} vorgestellt.
 

+
+\begin{figure}
+  \begin{center}
+    \input{images/16-hillis.tex}
+  \end{center}
+  \caption{Das 16-Sortiernetzwerk, das \textit{Hillis} in~\cite{H1992} angibt.
+  Es besteht aus 61~Komparatoren in 11~Schichten.}
+  \label{fig:16-hillis}
+\end{figure}
+Evolutionäre Algorithmen wurden bereits mehrfach eingesetzt, um
+Sortiernetzwerke zu untersuchen. \textit{W.~Daniel Hillis} verwendete
+\emph{Co-Evolution} um neben Komparatornetzwerken auch „schwierige Eingaben“
+zu optimieren~\cite{H1992}. Diese \emph{Parasiten} genannten Eingaben wurden
+daran gemessen, bei wievielen Komparatornetzwerken sie beweisen konnten, dass
+sie keine Sortiernetzwerke sind. So mussten bei neuen Individuen~/
+Komparatornetzwerken nicht alle 0-1-Folgen, sondern nur erfolgreiche
+Parasiten~/ schwierige Eingaben überprüft werden. Auf diese Art und Weise
+gelang es \textit{Hillis} ein 16-Sortiernetzwerk mit 61~Komparatoren
+anzugeben, das in Abbildung~\ref{fig:16-hillis} zu sehen ist.
+
+\begin{figure}
+  \centering
+  \subfigure{\input{images/13-juille-0.tex}}
+  \subfigure{\input{images/13-juille-1.tex}}
+  \caption{13-Sortiernetzwerke, die von \textit{Hugues Juillé} mithilfe des
+  END-Algorithmus gefunden wurden. Sie bestehen jeweils aus 45~Komparatoren in
+  10~Schichten.}
+  \label{fig:13-juille}
+\end{figure}
+\textit{Hugues Juillé} entwickelte ein Verfahren, das er \emph{Evolving
+Non-Determinism} (END) nannte. Dabei handelt es sich nicht um einen
+\emph{Evolutionären Algorithmus}, wie sie hier vorgestellt wurden, sondern um
+eine verteilte, probabilistische Breitensuche, die an die \emph{Strahlsuche}
+(englisch: \textit{beam search}), ein Verfahren der Künstlichen Intelligenz,
+angelehnt ist. Die aufwendigste Operation bei diesem Ansatz ist die
+Bewertungsfunktion, die abschätzt, wieviele Komparatoren zu einem
+Komparatornetzwerk hinzugefügt werden müssen, um ein Sortiernetzwerk zu
+erhalten. Mit diesem Ansatz gelang es \textit{Juillé} zwei 13-Sortiernetzwerke
+anzugeben, die mit 45~Komparatoren effizienter sind als alle bis dahin
+Bekannten (Abbildung~\ref{fig:13-juille}).
+

 \newpage
 \section{Bekannte konstruktive Sortiernetzwerke}
 \label{sect:konstruktive_netzwerke}
 
 Übersicht über bekannte konstruktive Sortiernetzwerke.
 
 \newpage
 \section{Bekannte konstruktive Sortiernetzwerke}
 \label{sect:konstruktive_netzwerke}
 
 Übersicht über bekannte konstruktive Sortiernetzwerke.
 

+\todo{Einleitungssatz}
+

 \subsection{Das Odd-Even-Transpositionsort-Netzwerk}
 \label{sect:odd_even_transpositionsort}
 
 \subsection{Das Odd-Even-Transpositionsort-Netzwerk}
 \label{sect:odd_even_transpositionsort}
 


@@ -859,18 +903,6 @@ Al-Haj Baddar} und \textit{Kenneth~E. Batcher} in ihrer Arbeit „An 11-Step
 Sorting Network for 18~Elements“~\cite{BB2009} vorstellen, benötigt aber
 6~Komparatoren weniger.
 
 Sorting Network for 18~Elements“~\cite{BB2009} vorstellen, benötigt aber
 6~Komparatoren weniger.
 

-% 9   9
-% 9  18
-% 9  27
-% 9  36
-% 9  45
-% 8  53
-% 8  61
-% 7  68
-% 7  75
-% 6  81
-% 5  86
-

 Das Zusammenfassen von zwei Sortiernetzwerken durch Hintereinanderausführung
 ist nicht sinnvoll: Da die Ausgabe des ersten Sortiernetzwerks bereits
 sortiert ist, ist das zweite Sortiernetzwerk überflüssig. Eine
 Das Zusammenfassen von zwei Sortiernetzwerken durch Hintereinanderausführung
 ist nicht sinnvoll: Da die Ausgabe des ersten Sortiernetzwerks bereits
 sortiert ist, ist das zweite Sortiernetzwerk überflüssig. Eine


@@ -880,12 +912,6 @@ die Sortiereigenschaft. Die Sortiereigenschaft des resultierenden
 Komparatornetzwerks müsste überprüft werden, was nach heutigem Wissensstand
 nur mit exponentiellem Aufwand möglich ist.
 
 Komparatornetzwerks müsste überprüft werden, was nach heutigem Wissensstand
 nur mit exponentiellem Aufwand möglich ist.
 

-%\begin{itemize}
-%\item Mit dem Bitonic-Merge
-%\item Mit dem Odd-Even-Merge
-%\item Nach dem Pairwise sorting-network Schema.
-%\end{itemize}
-

 \subsection{Leitungen entfernen}
 \label{sect:leitungen_entfernen}
 
 \subsection{Leitungen entfernen}
 \label{sect:leitungen_entfernen}
 


@@ -979,7 +1005,7 @@ auch das Maximum angenommen werden. Wendet man das Verfahren iterativ an, um
 ein $n$-Sortiernetzwerk auf ein ${(n-k)}$-Sortiernetzwerk zu reduzieren,
 ergeben sich insgesamt
 \begin{equation}\label{eqn:anzahl_schnittmuster}
 ein $n$-Sortiernetzwerk auf ein ${(n-k)}$-Sortiernetzwerk zu reduzieren,
 ergeben sich insgesamt
 \begin{equation}\label{eqn:anzahl_schnittmuster}

-  \prod_{i=n}^{1+n-k} 2i = 2^k \frac{n!}{(n-k)!}
+  \prod_{i=n}^{1+n-k} 2i = 2^k \cdot \frac{n!}{(n-k)!}

   \quad (n > m)
 \end{equation}
 \emph{mögliche} Schnittmuster. Diese Schnittmuster sind nicht alle
   \quad (n > m)
 \end{equation}
 \emph{mögliche} Schnittmuster. Diese Schnittmuster sind nicht alle


@@ -1043,13 +1069,12 @@ Alleine durch Betrachten der ersten Schicht von Komparatoren konnte die Anzahl
 der \emph{unterschiedlichen} Schnittmuster auf höchstens $\frac{2}{3}$ der
 \emph{möglichen} Schnittmuster reduziert werden. Um die Anzahl der
 \emph{unterschiedlichen} Schnittmuster experimentell zu ermitteln, wurden je
 der \emph{unterschiedlichen} Schnittmuster auf höchstens $\frac{2}{3}$ der
 \emph{möglichen} Schnittmuster reduziert werden. Um die Anzahl der
 \emph{unterschiedlichen} Schnittmuster experimentell zu ermitteln, wurden je

-eine Million zufällige 8-Schnittmuster auf die 16-Sortiernetzwerke
-$\operatorname{OES}(16)$, $\operatorname{BS}(16)$ und $\operatorname{PS}(16)$
-angewandt. Anschließend wurde mithilfe einer Hashtabelle überprüft, ob das
-resultierende Sortiernetzwerk schon von einem \emph{äquivalenten}
-Schnittmuster erzeugt wurde. Falls das Sortiernetzwerk noch nicht in der
-Hashtabelle enthalten war, wurde der Zähler für unterschiedliche Schnittmuster
-erhöht und das Sortiernetzwerk eingefügt.
+eine Million zufällige 8-Schnittmuster auf die 16-Sortiernetzwerke \oes{16},
+\bs{16} und \ps{16} angewandt. Anschließend wurde mithilfe einer Hashtabelle
+überprüft, ob das resultierende Sortiernetzwerk schon von einem
+\emph{äquivalenten} Schnittmuster erzeugt wurde. Falls das Sortiernetzwerk
+noch nicht in der Hashtabelle enthalten war, wurde der Zähler für
+unterschiedliche Schnittmuster erhöht und das Sortiernetzwerk eingefügt.

 
 Abbildung~\ref{fig:count-cuts-16} trägt die Anzahl der
 \emph{unterschiedlichen} Schnittmuster gegen die Anzahl der zufälligen
 
 Abbildung~\ref{fig:count-cuts-16} trägt die Anzahl der
 \emph{unterschiedlichen} Schnittmuster gegen die Anzahl der zufälligen


@@ -1059,29 +1084,30 @@ Wert nach $1.000.000$~Iterationen allem Anschein nach dem Endwert schon sehr
 nahe ist.
 
 Die Anzahl der möglichen 8-Schnittmuster ist entsprechend der
 nahe ist.
 
 Die Anzahl der möglichen 8-Schnittmuster ist entsprechend der

-Formel~\ref{eqn:anzahl_schnittmuster} 3.294.720. Diese möglichen Schnittmuster
-führen aber nur zu wenigen \emph{unterschiedlichen} Sortiernetzwerken: 3519
-($\approx 0,1\%$) im Fall des \emph{Odd-Even-Mergesort-Netzwerks}, 4973
-($\approx 0,15\%$) beim \emph{bitonen Mergesort-Netzwerk} und 18764 ($\approx
-0,57\%$) beim \emph{Pairwise-Sorting-Netzwerk}. Zwar ist es möglich, dass mehr
-Iterationen die Anzahl der unterschiedlichen Schnittmuster noch wachsen lässt.
-Die Graphen in Abbildung~\ref{fig:count-cuts-16} geben jedoch Grund zu der
-Annahme, dass die Anzahl dieser zusätzlichen, unterschiedlichen Schnittmuster
+Formel~\eqref{eqn:anzahl_schnittmuster} 3.294.720. Diese möglichen
+Schnittmuster führen aber nur zu wenigen \emph{unterschiedlichen}
+Sortiernetzwerken: 3519 ($\approx 0,1\%$) im Fall des
+\emph{Odd-Even-Mergesort-Netzwerks}, 4973 ($\approx 0,15\%$) beim
+\emph{bitonen Mergesort-Netzwerk} und 18764 ($\approx 0,57\%$) beim
+\emph{Pairwise-Sorting-Netzwerk}. Zwar ist es möglich, dass mehr Iterationen
+die Anzahl der unterschiedlichen Schnittmuster noch wachsen lässt. Die Graphen
+in Abbildung~\ref{fig:count-cuts-16} geben jedoch Grund zu der Annahme, dass
+die Anzahl dieser zusätzlichen, unterschiedlichen Schnittmuster

 vernachlässigbar klein ist.
 
 Bedingt durch die sehr große Anzahl möglicher Schnittmuster ist dieses
 Experiment für größere Sortiernetzwerke leider nicht sinnvoll durchführbar.
 vernachlässigbar klein ist.
 
 Bedingt durch die sehr große Anzahl möglicher Schnittmuster ist dieses
 Experiment für größere Sortiernetzwerke leider nicht sinnvoll durchführbar.

-Die Hashtabelle benötigt mehr Arbeitsspeicher als in derzeitigen Rechnern
-vorhanden ist, bevor ein entsprechender Graph den linearen Bereich für
-„kleine“ x-Werte verlässt.
+Die Hashtabelle würde mehr Arbeitsspeicher benötigen als in derzeitigen
+Rechnern vorhanden ist, bevor ein entsprechender Graph den linearen Bereich
+für „kleine“ x-Werte verlässt.

 
 Um die Anzahl der unterschiedlichen Schnittmuster trotzdem abschätzen zu
 können, kann man sich einer stochastischen Methode bedienen, der sogenannten
 \emph{Monte-Carlo-Methode}. Zunächst generiert man eine Menge~$S$ von
 $k$~unterschiedlichen Schnittmustern. Anschließend werden $n$~Schnittmuster
 
 Um die Anzahl der unterschiedlichen Schnittmuster trotzdem abschätzen zu
 können, kann man sich einer stochastischen Methode bedienen, der sogenannten
 \emph{Monte-Carlo-Methode}. Zunächst generiert man eine Menge~$S$ von
 $k$~unterschiedlichen Schnittmustern. Anschließend werden $n$~Schnittmuster

-zufällig erzeugt und überprüft, ob sie sich in der Menge~$S$ enthalten sind.
-Unter der Annahme, dass das Verhältnis der zufälligen Schnittmuster, die in
-$S$ enthalten sind, und $n$ dem Verhältnis von $k$ und der Anzahl der
+zufällig erzeugt und überprüft, ob sie in der Menge~$S$ enthalten sind. Unter
+der Annahme, dass das Verhältnis der zufälligen Schnittmuster, die in $S$
+enthalten sind, und $n$ dem Verhältnis von $k$ und der Anzahl der

 unterschiedlichen Schnittmuster ingesamt entspricht, kann man die Anzahl der
 unterschiedlichen Schnittmuster abschätzen.
 
 unterschiedlichen Schnittmuster ingesamt entspricht, kann man die Anzahl der
 unterschiedlichen Schnittmuster abschätzen.
 


@@ -1104,8 +1130,8 @@ zufällige Schnittmuster erzeugt und der Anteil der zufälligen Schnittmuster,
 die \emph{äquivalent} zu einem in~$S$ enthalten Schnittmuster sind, berechnet.
 Für $\operatorname{OES}(32)$ war dieser Anteil etwa $0,19 \%$, für
 $\operatorname{BS}(32)$ etwa $0,29 \%$. Das ergibt eine Abschätzung von $5,2
 die \emph{äquivalent} zu einem in~$S$ enthalten Schnittmuster sind, berechnet.
 Für $\operatorname{OES}(32)$ war dieser Anteil etwa $0,19 \%$, für
 $\operatorname{BS}(32)$ etwa $0,29 \%$. Das ergibt eine Abschätzung von $5,2

-\cdot 10^6$ unterschiedlichen Schnittmustern für $\operatorname{OES}(32)$ und
-$3,4 \cdot 10^6$ für $\operatorname{BS}(32)$.
+\cdot 10^6$ unterschiedlichen 16-Schnittmustern für $\operatorname{OES}(32)$
+und $3,4 \cdot 10^6$ für $\operatorname{BS}(32)$.

 
 \begin{figure}
   \begin{center}
 
 \begin{figure}
   \begin{center}


@@ -1126,9 +1152,9 @@ $\operatorname{BS}(32)$. In Anbetracht der Tatsache, dass die Anzahl der
 unterschiedlichen 8-Schnittmuster für $\operatorname{PS}(16)$ in
 Abbildung~\ref{fig:count-cuts-16} bereits mehr als dreimal größer war als die
 Anzahl für $\operatorname{OES}(16)$ beziehungsweise $\operatorname{BS}(16)$,
 unterschiedlichen 8-Schnittmuster für $\operatorname{PS}(16)$ in
 Abbildung~\ref{fig:count-cuts-16} bereits mehr als dreimal größer war als die
 Anzahl für $\operatorname{OES}(16)$ beziehungsweise $\operatorname{BS}(16)$,

-ist dieser Umstand wenig verwunderlich. In einem kombinierten Graphen hätte
-man keine Details mehr erkennen können. Aufgrund der hohen Anzahl
-unterschiedlicher Schnittmuster, wurde für das gleiche Experiment mit
+ist dieser Umstand wenig verwunderlich. Entsprechend hätte man in einem
+kombinierten Graphen keine Details mehr erkennen können. Aufgrund der hohen
+Anzahl unterschiedlicher Schnittmuster, wurde für das gleiche Experiment mit

 $\operatorname{PS}(32)$ eine initiale Menge von 100.000 unterschiedilchen
 Schnittmustern erzeugt. Trotzdem wurden nach 1.000.000 Iterationen nur 385
 Schnittmuster gefunden, die zu einem Schnittmuster in der Menge äquivalent
 $\operatorname{PS}(32)$ eine initiale Menge von 100.000 unterschiedilchen
 Schnittmustern erzeugt. Trotzdem wurden nach 1.000.000 Iterationen nur 385
 Schnittmuster gefunden, die zu einem Schnittmuster in der Menge äquivalent


@@ -1139,6 +1165,7 @@ die Anzahl der \emph{möglichen} Schnittmuster.
 
 \newpage
 \section{Der \textsc{SN-Evolution}-Algorithmus}
 
 \newpage
 \section{Der \textsc{SN-Evolution}-Algorithmus}

+\label{sect:sn-evolution}

 
 Der \textsc{SN-Evolution}-Algorithmus ist ein \emph{evolutionärer
 Algorithmus}, der die in den vorherigen Abschnitten beschriebenen Mischer
 
 Der \textsc{SN-Evolution}-Algorithmus ist ein \emph{evolutionärer
 Algorithmus}, der die in den vorherigen Abschnitten beschriebenen Mischer


@@ -1216,7 +1243,7 @@ Auswahl := (leer)
 für jedes Individuum in Population
 {
   reziproke Güte := 1.0 / Guete(Individuum)
 für jedes Individuum in Population
 {
   reziproke Güte := 1.0 / Guete(Individuum)

-  Wahrscheinlichkeit P := reziproke Güte / (reziproke Güte + Gütesumme)
+  Wahrscheinlichkeit P := reziproke Güte / (Gütesumme + reziproke Güte)

   Gütesumme := Gütesumme + reziproke Güte
 
   mit Wahrscheinlichkeit P
   Gütesumme := Gütesumme + reziproke Güte
 
   mit Wahrscheinlichkeit P


@@ -1326,12 +1353,7 @@ Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen. Ein Netzwerk, das
 $\operatorname{OES}(n)$ in mindestens einem Merkmal übertrifft, konnte jedoch
 nicht beobachtet werden.
 
 $\operatorname{OES}(n)$ in mindestens einem Merkmal übertrifft, konnte jedoch
 nicht beobachtet werden.
 

-\begin{itemize}
-\item Güte von Sortiernetzwerken (Anzahl der Komparatoren, Anzahl der Schichten, kombiniert)
-\item Wie gut die Netzwerke werden, hängt stark vom verwendeten \emph{Mischer} ab.
-\item Ggf. Abschnitt „Shmoo-Äquivalenz“ kürzen und hier einbauen.
-\item Möglicherweise: Verwende den rekursiven Aufbau des \emph{Pairwise-Sorting}-Netzwerks um Sortiernetzwerke zu mergen.
-\end{itemize}
+\todo{Ggf. Abschnitt „Shmoo-Äquivalenz“ kürzen und hier einbauen.}

 
 %\begin{figure}
 %\begin{center}
 
 %\begin{figure}
 %\begin{center}


@@ -1379,11 +1401,11 @@ von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}. Mit diesem
 Algorithmus wurden zu einer Reihe von „interessanten“ Netzwerken möglichst
 gute Schnittmuster gesucht.
 
 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$.
+Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet die \emph{Schnittmuster},
+die in Abschnitt~\ref{sect:anzahl_schnittmuster} definiert wurden, 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
 
 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


@@ -1586,7 +1608,7 @@ wenig verwunderlich, dass \textsc{SN-Evolution-Cut} gestartet mit
 $\operatorname{OES}(32)$ sehr schnell ein gutes 16-Schnittmuster findet.
 
 Eines der eher zufälligen Schnittmuster ist $\operatorname{MIN}(1, 6, 11, 14,
 $\operatorname{OES}(32)$ sehr schnell ein gutes 16-Schnittmuster findet.
 
 Eines der eher zufälligen Schnittmuster ist $\operatorname{MIN}(1, 6, 11, 14,

-17, 23, 26, 29)$, $\operatorname{MAX}(2, 7, 8, 13, 18, 21, 27, 31)$. Das
+17, 23, 26, 29)$, $\operatorname{MAX}(2, 7, 8,$ $13, 18, 21, 27, 31)$. Das

 Schnittmuster ist in Abbildung~\ref{fig:16-ec-from-oes32-cut} veranschaulicht,
 das resultierende Netzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32} zu sehen.
 
 Schnittmuster ist in Abbildung~\ref{fig:16-ec-from-oes32-cut} veranschaulicht,
 das resultierende Netzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32} zu sehen.
 


@@ -1673,7 +1695,7 @@ gib Netzwerk zurück
   \label{fig:markov-cycles-16}
 \end{figure}
 
   \label{fig:markov-cycles-16}
 \end{figure}
 

-
+\todo{Schreibe noch etwas zu …}

 \begin{itemize}
   \item Beste erreichte Netzwerke (gleich zu \emph{OE-Mergesort}).
   \item Anzahl der erreichbaren Sortiernetzwerke.
 \begin{itemize}
   \item Beste erreichte Netzwerke (gleich zu \emph{OE-Mergesort}).
   \item Anzahl der erreichbaren Sortiernetzwerke.


@@ -1722,22 +1744,106 @@ gib Netzwerk zurück
 \end{figure}
 
 \newpage
 \end{figure}
 
 \newpage

-\section{Empirische Beobachtungen}
-
-\begin{itemize}
-\item So schnell konvergiert der Algorithmus.
-\item $\ldots$
-\end{itemize}
-
-\newpage

 \section{Ausblick}
 
 \section{Ausblick}
 

-Das würde mir noch einfallen$\ldots$
+Die Möglichkeiten, die Evolutionäre Algorithmen bei der Optimierung von
+Sortiernetzwerken bieten, 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{Verwendung des Pairwise-Sorting-Netzwerk in \textsc{SN-Evolution}}
+
+Die aktuelle Implementierung von \textsc{SN-Evolution}
+(Abschnitt~\ref{sect:sn-evolution}) 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
+Ausgaben sorgen. Anstelle von $\ps{\frac{n}{2}}$ kann man natürlich beliebige
+Sortiernetzwerke mit $\frac{n}{2}$~Leitungen verwenden.
+
+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{unterscheidliche} Schnittmuster gibt
+(Abbschnitt~\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{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{H1992} beschreibt, könnte man die Algorithmen \textsc{SN-Evolution}
+und \textsc{SN-Evolution-Cut} versuchen 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ächten 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}
 
 
 \newpage
 \section{Implementierung}
 

-So habe ich die ganzen Versuche durchgeführt.
+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{18} zu erzeugen, kann folgendes Kommando verwendet
+werden:
+\begin{verbatim}
+$ sn-bitonicsort 18 | sn-normalize >sn-18
+\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 von Odd-Even-Mergesort-, bitonic Mergesort-
+und Pairwise-Sorting-Netzwerken, das Normalisieren von Sortiernetzwerken,
+Anwendung von Schnittmustern auf Sortiernetzwerke und Anwendung eines
+Komparatornetzwerks auf eine Eingabe-Permutation.
+
+\textit{libsortnetwork} kann unter der Web-Adresse
+\url{http://octo.it/libsortnetwork/} unentgeldlich heruntergeladen werden.

 
 \newpage
 \bibliography{references}
 
 \newpage
 \bibliography{references}