[diplomarbeit.git] / diplomarbeit.tex

\documentclass[a4paper,11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage{ngerman}
\usepackage{fancyhdr}
\usepackage{geometry}
\usepackage{amsmath, bbm}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{listings}
\usepackage{graphicx}
\usepackage{url}
\usepackage[table]{xcolor}
%\usepackage{longtable}
\usepackage{subfigure}
\usepackage{icomma}

\usepackage{tikz}
\usetikzlibrary{arrows,shapes}

% Fuer mathtoolsset
\usepackage{mathtools}

\geometry{paper=a4paper,margin=30mm}

\pagestyle{fancy}
%\fancyhf{}
%\fancyhead[LO,LE]{"Ubung zu Computational Intelligence}
%\fancyhead[CO,CE]{2006-05-15}
%\fancyhead[RO,RE]{Florian Forster (2099894)}

\title{Evolutionäre Optimierung von Sortiernetzwerken}
\author{Florian Forster}
\date{\today}

\newcommand{\false}{\textsc{False}}
\newcommand{\true}{\textsc{True}}
\newcommand{\todo}[1]{{\bf TODO:} #1}
\newcommand{\qed}{\hfill $\Box$ \par \bigskip}

\newcommand{\oes}[1]{\ensuremath{\operatorname{OES}\left(#1\right)}}
\newcommand{\bs}[1]{\ensuremath{\operatorname{BS}\left(#1\right)}}
\newcommand{\ps}[1]{\ensuremath{\operatorname{PS}\left(#1\right)}}
\newcommand{\oem}[1]{\ensuremath{\operatorname{OEM}\left(#1\right)}}
\newcommand{\bm}[1]{\ensuremath{\operatorname{BM}\left(#1\right)}}
\newcommand{\oet}[1]{\ensuremath{\operatorname{OET}\left(#1\right)}}

\newcommand{\gcell}{\cellcolor{green!10}}
\newcommand{\Gcell}{\cellcolor{green!10!white!95!black}}

\newtheorem{definition}{Definition}
\newtheorem{satz}{Satz}

% Zeige Nummern nur bei referenzierten Gleichungen an.
\mathtoolsset{showonlyrefs=true}

\begin{document}

\tikzstyle{vertex}   = [circle,draw,thick,fill=black,minimum size=5,inner sep=0pt]
\tikzstyle{comp}     = [draw,thick,-]
\tikzstyle{compup}   = [draw,thick,->]
\tikzstyle{compdown} = [draw,thick,<-]
\tikzstyle{edge}     = [draw,thick,-]
\tikzstyle{diredge}  = [draw,thick,->]
\tikzstyle{prob}     = [font=\tiny]

\tikzstyle{edge minimum} = [edge,color=blue!20]
\tikzstyle{edge maximum} = [edge,color=red!20]
\tikzstyle{vertex active minimum} = [vertex,color=blue!50, fill=blue!50]
\tikzstyle{vertex active maximum} = [vertex,color=red!50, fill=red!50]
\tikzstyle{vertex active minimum maximum} = [vertex,color=violet!50, fill=violet!50]
\tikzstyle{vertex inactive minimum} = [vertex,color=blue!20, fill=blue!20]
\tikzstyle{vertex inactive maximum} = [vertex,color=red!20, fill=red!20]
\tikzstyle{vertex inactive minimum maximum} = [vertex,color=black!20, fill=black!20]
\tikzstyle{comp active minimum} = [comp]
\tikzstyle{comp active maximum} = [comp]
\tikzstyle{comp active minimum maximum} = [comp,color=black!20]
\tikzstyle{comp inactive minimum} = [comp,color=blue!20]
\tikzstyle{comp inactive maximum} = [comp,color=red!20]
\tikzstyle{comp inactive minimum maximum} = [comp,color=black!20]

\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]

\maketitle
\begin{abstract}
Sortiernetzwerke erweisen sich als sehr schwieriges Optimierungsproblem. Zwar
ist das Konzept leicht verständlich und schnell erklärt, effiziente und
schnelle Sortiernetzwerke zu finden oder zu konstruieren bleibt aber eine
Herausforderung.

Diese Arbeit verwendet „Schnitte“ oder „Leitungselimination“ und
Mischer-Netz\-werke, um evolutionäre Algorithmen anzugeben, deren Individuen
die Menge der gültigen Sortiernetzwerke nie verlassen. Bisherige Ansätze
bewegten sich in der Regel in der Menge aller Komparatornetzwerke und suchten
dort nach Sortiernetzwerken. Nach dem Vorstellen der zwei Algorithmen
\textsc{SN-Evolution} und \textsc{SN-Evolution-Cut} sowie einiger Ergebnisse,
die mit diesen Algorithmen erzielt werden konnten, wird -- basierend auf dem
evolutionären Algorithmus \textsc{SN-Evolution} -- eine Markov-Kette für
Sortiernetzwerke angegeben.
\end{abstract}
\newpage

\tableofcontents

\newpage
\section{Motivation und Einleitung}

\subsection{Motivation}\label{sect:motivation}

\emph{Sortiernetzwerke} sind ein theoretisches Konstrukt, dass auch von
Personen ohne Zugang zum Thema, beziehungsweise der theoretischen Informatik,
schnell verstanden werden kann. Eine Einführung wird in
Abschnitt~\ref{sect:einleitung_sortiernetzwerke} gegeben. Nichtsdestotrotz ist
das Finden von Sortiernetzwerken sowie das Beweisen, dass ein
Komparatornetzwerk jede beliebige Eingabe sortiert, im Allgemeinen sehr
schwierig und nach heutigem Kenntnisstand nur mit exponentiellem Aufwand zu
bewältigen.

Einfacher ist der Korrektheitsbeweis bei konstruktiven Verfahren, da hier die
Konstruktionsvorschrift genutzt werden kann, um die Korrektheit für beliebige
Eingabegrößen zu beweisen. Im Abschnitt~\ref{sect:konstruktive_netzwerke}
geschieht dies beispielsweise für zwei von \emph{Kenneth~E. Batcher} 1968
gefundene Konstruktionsvorschriften.

Um effiziente und schnelle Sortiernetzwerke zu finden, wurden schon wiederholt
Computer und automatische Suchverfahren eingesetzt. Bisherige Ansätze
versuchen meist in der Menge aller Komparatornetzwerke jene zu finden, die
die Sortiereigenschaft besitzen und aus wenigen Komparatoren bestehen. Die
Eigenschaft, jede Eingabepermutation zu sortieren, ist also ein
Optimierungsziel und nicht durch das Vorgehen gewährleistet. Dafür können
theoretisch alle Sortiernetzwerke durch diese Algorithmen gefunden werden --
genügend Laufzeit vorausgesetzt.

In dieser Arbeit werden Methoden verwendet, die die Menge der Sortiernetzwerke
nie verlassen, dafür aber auch nicht alle existierenden Sortiernetzwerke
erzeugen können. So muss für ein gefundenes Komparatornetzwerk nicht mehr
nachgewiesen werden, dass es jede beliebige Eingabe sortiert, weil diese
Eigenschaft durch das Verfahren sichergestellt ist.

\subsection{Einleitung}\label{sect:einleitung}

\subsubsection{Sortiernetzwerke}\label{sect:einleitung_sortiernetzwerke}

\emph{Komparatoren} sind die Bausteine, die \emph{Komparatornetzwerken}
zugrunde liegen. Sie haben zwei Eingänge über die sie zwei Zahlen erhalten
können und zwei Ausgänge, auf denen die Zahlen wieder ausgegeben werden. Dabei
sind die Ausgänge im Gegensatz zu den Eingängen unterscheidbar, da die größere
der beiden Zahlen immer auf dem einen, die kleinere der beiden Zahlen
immer auf dem anderen Ausgang ausgegeben wird.

Kombiniert man mehrere \emph{Komparatoren} in der Form miteinander, dass die
Ausgänge eines Komparators mit Eingängen weiterer Komparatoren verbunden sind,
erhält man ein {\em Komparatornetzwerk}.

\begin{figure}
  \begin{center}
    \input{images/einfaches_komparatornetzwerk.tex}
  \end{center}
  \caption{Einfaches Komparatornetzwerk mit 4~Ein- beziehungsweise Ausgängen,
    bestehend aus 5~Komparatoren.}
  \label{fig:einfaches_komparatornetzwerk}
\end{figure}

Abbildung~\ref{fig:einfaches_komparatornetzwerk} zeigt ein einfaches
\emph{Komparatornetzwerk} aus fünf Komparatoren. Insgesamt gibt es vier
verschiedene Eingänge und vier Ausgänge. Die Ein- und Ausgänge werden durch
eine horizontale Linie dargestellt und als \emph{Leitung} bezeichnet. Die
\emph{Komparatoren} sind durch vertikale Pfeile dargestellt und verbinden je
zwei verschiedene \emph{Leitungen} miteinander. Die Verbindungsstellen von
\emph{Leitungen} und \emph{Komparatoren} sind zur besseren Übersichtlichkeit
durch schwarze Punkte symbolisiert.

Auf der linken Seite befinden sich die Eingänge. Hier wird eine Zahlenfolge in
das Netzwerk hinein gegeben. Jeder Komparator vergleicht die Zahlen „auf“ den
beiden Leitungen, die er verbindet. Nach einem Komparator befindet sich die
kleinere Zahl immer auf der Leitung, auf die der Pfeil zeigt, die größere Zahl
befindet sich auf der Leitung, auf der der Pfeil seinen Ursprung hat. Wenn in
einem Komparatornetzwerk alle Komparatoren in die gleiche Richtung zeigen --
die Konvention in dieser Arbeit ist, dass das Minimum auf der unteren Leitung
ausgegeben wird -- werden die Pfeile durch einfache Linien ersetzt. Zu diesen
sogenannten \emph{Standard-Netzwerken} siehe auch
Abschnitt~\ref{sect:normalisieren}.

Komparatoren, die \emph{unterschiedliche} Leitungen miteinander vergleichen,
können gleichzeitig angewendet werden. Das Beispiel in
Abbildung~\ref{fig:einfaches_komparatornetzwerk} verwendet diesen Umstand und
vergleicht die zwei oberen und die zwei unteren Leitungen gleichzeitig. Eine
Gruppe von Komparatoren, die gleichzeitig angewendet werden können, nennt man
eine \emph{Schicht} des Komparatornetzwerks. Die \emph{Geschwindigkeit} eines
Komparatornetzwerks ist gleichbedeutend mit der Anzahl der Schichten, in die
sich die Komparatoren mindestens gruppieren lassen, da sie die Anzahl der
benötigten parallelen Schritte darstellt.

\emph{Komparatornetzwerke}, die für \emph{jede} Eingabefolge eine Ausgabe
erzeugen, die der Sortierung der Eingabe entspricht, heißen
\emph{Sortiernetzwerke}. Das in
Abbildung~\ref{fig:einfaches_komparatornetzwerk} gezeigte Komparatornetzwerk
ist \emph{kein} Sortiernetzwerk: Die Eingabefolge ${(1, 2, 3, 4)}$ führt zur
Ausgabe ${(2, 1, 3, 4)}$ -- die bestehenden Sortierung wird also sogar
zerstört.

\begin{figure}
  \begin{center}
    \input{images/09-e2-c24-allbut1.tex}
  \end{center}
  \caption{Ein \emph{Komparatornetzwerk} mit 9~Eingängen und 24~Komparatoren,
  die in 8~Schichten angeordnet sind. Das Netzwerk sortiert alle Eingaben, bei
  denen das Minimum nicht auf dem mittleren Eingang liegt.}
  \label{fig:09-e2-c24-allbut1}
\end{figure}
Zu beweisen, dass ein gegebenes Komparatornetzwerk die Sortiereigenschaft {\em
nicht} hat, ist mit einem gegebenen Gegenbeispiel einfach möglich. Das
Komparatornetzwerk wird auf das Gegenbeispiel angewendet und anschließend wird
überprüft, ob die Ausgabe sortiert ist. Ist sie es nicht, heißt das, dass es
mindestens eine Eingabefolge gibt, die nicht sortiert wird. Entsprechend der
Definition handelt es sich bei dem \emph{Komparatornetzwerk} folglich
\emph{nicht} um ein \emph{Sortiernetzwerk}. Ein solches Gegenbeispiel für ein
gegebenes Komparatornetzwerk zu finden ist nach heutigem Kenntnisstand jedoch
nicht \emph{effizient}\footnote{In diesem Zusammenhang heißt \emph{effizient},
dass keine Algorithmen bekannt sind, die eine polynomielle Laufzeit (in
Abhängigkeit von der Eingabelänge) haben.} möglich.

Beispielsweise sortiert das im Rahmen dieser Arbeit entdeckte
Komparatornetzwerk in Abbildung~\ref{fig:09-e2-c24-allbut1} viele der 362.880
möglichen Eingabepermutationen. Mit dem Gegenbeispiel $(3, 5, 2, 1, 0, 7, 4,
8, 6)$ lässt sich jedoch leicht beweisen, dass das Komparatornetzwerk die
Sortiereigenschaft \emph{nicht} besitzt, da es in diesem Fall die Folge $(1,
0, 2, 3, 4, 5, 6, 7, 8)$ ausgibt.

Insgesamt gibt es $n!$~Permutationen von $n$~Elementen. Wenn ein
Komparatornetzwerk die Sortiereigenschaft besitzt, bildet es alle diese
Permutationen auf die sortierte Reihenfolge ab. Allerdings wächst $n!$
so schnell, dass ein Ausprobieren aller möglichen Permutationen schon bei
16~Leitungen praktisch nicht mehr zu bewerkstelligen
ist.\footnote{1.307.674.368.000 Permutationen}

\label{sect:0-1-prinzip}
Glücklicherweise reicht es aus, alle möglichen 0-1-Folgen zu überprüfen, wie
\textit{Donald~E. Knuth} in \cite{KNUTH} zeigt. Die Beweisidee ist folgende:
Angenommen ein Komparatornetzwerk sortiert alle 0-1-Folgen und es gibt eine
Permutation $E = (e_0, \dots, e_{n-1})$ beliebiger Zahlen, die nicht sortiert
wird. Die Ausgabefolge sei $A = (a_0, \dots, a_{n-1})$. Sei $i$ eine Position
in der Ausgabe, die die Sortierbedingung verletzt:
\begin{displaymath}
  a_0 \leqq a_1 \leqq \dots \leqq a_{i-1} > a_i \dots
\end{displaymath}
Die Eingabe kann mittels
\begin{displaymath}
  \hat{e}_j = \left\{
    \begin{array}{cl}
      0 & e_j \leqq a_i \\
      1 & e_j > a_i
    \end{array} \right.
\end{displaymath}
auf eine 0-1-Folge abgebildet werden, die entsprechend der Annahme vom
Komparatornetzwerk sortiert wird. Allerdings verändert diese Abbildung das
Verhalten jedes einzelnen Komparators nicht: Wenn bei der Permutation eine
Zahl größer als $a_i$ und eine Zahl kleiner oder gleich $a_i$ verglichen
wurden, liegen jetzt entsprechend eine Null und eine Eins an, die genauso
vertauscht werden oder nicht, wie das bei der Permutation der Fall war. Liegen
zwei Nullen oder zwei Einsen an, entsprechen sie zwei Zahlen kleiner als
$a_i$, beziehungsweise zwei Zahlen größer oder gleich $a_i$. Da im Fall der
0-1-Folge zwei gleiche Zahlen am Komparator anliegen, dürfen wir davon
ausgehen, dass sich der Komparator so verhält, wie er sich bei der Permutation
verhalten hat -- ohne das Ergebnis zu beeinflussen. Entsprechend müssen an den
Ausgängen $i-1$ und $i$ eine Null und eine Eins in der falschen Reihenfolge
ankommen. Das steht im Widerspruch zu der Annahme, dass alle 0-1-Folgen
sortiert werden.

Im Gegensatz zum Überprüfen aller möglichen Permutationen, was mit dem Aufwand
$\Theta\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ verbunden ist, besitzt
das Überprüfen aller 0-1-Folgen „nur“ den Aufwand $\Theta(2^n)$. Entsprechend
ist dieses Verfahren nicht \emph{effizient} -- ein schnelleres Verfahren ist
bisher allerdings nicht bekannt.

Um zu überprüfen, ob ein Komparatornetzwerk mit 16~Leitungen die
Sortiereigenschaft besitzt, sind mit dieser Methode nur 65.536 Tests notwendig
-- eine Zahl, die für aktuelle Prozessoren keine Herausforderung darstellt.
Für die Überprüfung eines Komparatornetzwerks mit 32~Leitungen sind jedoch
bereits etwa 4,3~Milliarden Tests notwendig, die einen Rechner durchaus
mehrere Minuten beschäftigen. Das ist deshalb problematisch, weil die im
Folgenden vorgestellten \emph{Evolutionären Algorithmen} eine entsprechende
Überprüfung in jeder Iteration durchführen müssten. Wenn die Überprüfung eines
Zwischenergebnisses fünf Minuten in Anspruch nimmt, sind für eine Million
Iterationen fast zehn Jahre Rechenzeit notwendig. Selbst wenn die Berechnung
auf 1000~Computern mit je 4~Prozessoren verteilt wird, werden über 20~Stunden
für einen Lauf benötigt.

\subsubsection{Evolutionäre Algorithmen}

Viele {\em kombinatorische Optimierungsprobleme} sind schwer zu lösen -- die
entsprechenden Entscheidungsprobleme liegen oft in der Komplexitätsklasse
$\mathcal{NP}$-vollständig. Das heißt, dass keine Verfahren bekannt sind, die
diese Probleme effizient exakt lösen. Sollte sich herausstellen, dass diese
Probleme außerhalb der Komplexitätsklasse~$\mathcal{P}$ liegen, wäre eine
Konsequenz, dass es für diese Probleme keine effizienten exakten Algorithmen
gibt. Stellt sich hingegen heraus, dass diese Probleme neben
$\mathcal{NP}$-vollständig auch in der Komplexitätsklasse~\textit{P} liegen,
gibt es effiziente Algorithmen. Es ist jedoch wahrscheinlich, dass die
Zeitkonstanten solcher Algorithmen sehr groß wären, so dass der praktische
Nutzen fraglich bleibt.

Aus diesem Grund besteht die Notwendigkeit, einen Kompromiss einzugehen: Statt
die \emph{optimale Lösung}, beziehungsweise eine der \emph{optimalen Lösungen}
als einzige Ausgabe des Algorithmus zuzulassen, wird eine "`möglichst gute"'
Lösung ausgegeben. Dafür verringert sich die Laufzeit des Algorithmus. Viele
dieser Optimierungsalgorithmen orientieren sich an Vorgängen in der Natur.
Beispielsweise imitieren die „Ameisenalgorithmen“ das Verhalten von Ameisen
auf der Futtersuche, um kurze Rundreisen auf Graphen zu berechnen.

Bei {\em Evolutionären Algorithmen} stand die Evolution Pate. Die Grundidee
ist, bekannte Lösungen zu neuen -- unter Umständen besseren -- Lösungen zu
kombinieren. Dabei bedient man sich der in der Evolutionstheorie etablierten
Nomenklatur, beispielsweise werden konkrete Lösungen für ein Problem als {\em
Individuen} bezeichnet.

Die Vorgehensweise lässt sich abstrakt wie folgt beschreiben: Aus einer
bestehenden Lösungsmenge, der {\em Population}, werden zufällig Lösungen
ausgesucht {\em (Selektion)} und zu einer neuen Lösung kombiniert ({\em
Rekombination}). Unter Umständen wird die neue Lösung noch zufällig
verändert {\em (Mutation)}, bevor sie in die bestehende Lösungsmenge
eingefügt wird. Die verwendeten Wahrscheinlichkeiten, beispielsweise bei der
{\em Selektion}, sind dabei nicht zwangsläufig gleichverteilt -- üblicherweise
werden bessere Lösungen bevorzugt. Zur Bewertung dient die sogenannte {\em
Gütefunktion}.

Nicht alle Probleme eignen sich für diese Strategie. Zum einen muss es möglich
sein, eine initiale Population zur Verfügung zu stellen, da diese als Basis
aller weiteren Operationen dient. Das ist häufig keine große Einschränkung, da
es oft einfach ist, {\em irgendeine} Lösung anzugeben. Die angegebenen
Algorithmen verwenden als einfache initiale Lösung häufig das
\emph{Odd-Even-Transpositionsort}-Netzwerk, das in
Abschnitt~\ref{sect:odd_even_transpositionsort} beschrieben wird. Zum anderen
muss eine Methode für die Rekombination existieren. Das ist insbesondere dann
problematisch, wenn {\em Nebenbedingungen} eingehalten werden müssen. Die in
dieser Arbeit verwendeten Rekombinationsmethoden sind so gewählt, dass die
Nebenbedingungen nicht verletzt werden.

Beim Aussuchen von zufälligen Lösungen aus der Population, der
\emph{Selektion}, werden gute Lösungen bevorzugt. Wie sehr diese Lösungen
bevorzugt werden, hat einen starken Einfluss auf das Verhalten des
Algorithmus. Werden gute Lösungen stark bevorzugt, konvergiert der Algorithmus
schnell gegen ein (lokales) Optimum. Dieses \textit{Exploitation} (Englisch
für „Ausnutzung“) genannte Verhalten sorgt dafür, dass sich der Algorithmus
schnell auf eine Lösung festlegt und andere, möglicherweise bessere lokale
Optima nicht mehr findet. Werden gute Lösungen hingegen nur wenig bevorzugt,
erforscht der Algorithmus den Lösungsraum in viele Richtungen. Dieses
\textit{Exploration} (Englisch für „Erforschung“) genannte Verhalten sorgt
zwar dafür, dass der Algorithmus langsamer auf ein Optimum zusteuert, dafür
findet er aber in der Regel bessere Lösungen.

Die Parameter evolutionärer Algorithmen so einzustellen, dass sich ein guter
Mittelweg zwischen den beiden Extremen einstellt, ist eine Aufgabe, die sich
nur experimentell lösen lässt. Die genauen Parameter hängen nicht nur vom
eigentlichen Algorithmus, sondern auch vom konkreten Problem ab, so dass sich
beispielsweise bei der Optimierung von Sortiernetzwerken die Parameter
zwischen verschiedenen Leitungszahlen stark unterscheiden.

Die Erforschung (\textit{Exploration}) kann von einem weiteren Mechanismus
unterstützt werden, der ebenfalls der Evolutionslehre entliehen ist, der
\emph{Mutation}. Dabei werden Lösungen zufällig verändert, so dass auch andere
Lösungen „in der Nähe“ von direkten Nachfolgern erreicht werden können. Das
hilft insbesondere bei der intensiven Suche in der Nähe eines lokalen Optimums
aber auch beim „Ausbrechen“ aus lokalen Optima und finden noch besserer
Lösungen.

Bei \emph{Sortiernetzwerken} ist eine \emph{Mutation} leider immer damit
verbunden, dass anschließend die Sortiereigenschaft des resultierenden
\emph{Komparatornetzwerks} wieder überprüft werden muss, da selbst das
Hinzufügen eines zufälligen Komparators diese Eigenschaft zer\-stö\-ren kann.
Beim Suchen möglichst effizienter Netzwerke ist das zufällige Entfernen von
Komparatoren interessanter, was die Sortiereigenschaft fast immer aufhebt.

Die im Folgenden beschriebenen Algorithmen mutieren (verändern) daher nicht
die \emph{Sortiernetzwerke} selbst, sondern verzichten entweder ganz auf
Mutation oder mutieren lediglich Transformationen von Sortiernetzwerken, die
die Sortiereigenschaft erhalten. Transformationen von Sortiernetzwerken werden
in 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{H1990} 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{H1990}. Diese \emph{Parasiten} genannten Eingaben wurden
daran gemessen, bei wie vielen 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~\cite{J1995}. Dabei handelt es sich nicht um
einen der \emph{Evolutionären Algorithmen}, 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, wie viele 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[Konstruktionsverfahren]{Konstruktionsverfahren für Sortiernetzwerke}
\label{sect:konstruktive_netzwerke}

Die bekannten Konstruktionsverfahren für Sortiernetzwerke, insbesondere ein
häufig verwendeter Baustein, sogenannte \emph{Mischer}\footnote{Eine
Fehlübersetzung aus dem Englischen, von \textit{to~merge} (Deutsch:
zusammenfügen). Da der Begriff des "`mischens"' beziehungsweise der
"`Mischer"' in der Literatur sehr weit verbreitet ist, werden diese Begriffe
in dieser Arbeit trotzdem verwendet.}, bilden die Grundlage für die
beschriebenen evolutionären Algorithmen beziehungsweise dienen als initiale
Eingabe. Im Folgenden werden daher vier Konstruktionsverfahren vorgestellt.

\todo{Drei oder vier Verfahren? Sprich: Mit oder ohne Pairwise Sorting.}

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

Das Sortiernetzwerk {\em Odd-Even-Transpositionsort} (OET) ist eines der
einfachsten Sortiernetzwerke. Es besteht aus $n$~{\em Schichten}, die jede
"`Leitung"' abwechselnd mit den benachbarten Leitungen verbindet.
Abbildung~\ref{fig:odd-even-transposition-08} zeigt das OET-Netzwerk für
${n = 8}$ Leitungen.

\begin{figure}
  \begin{center}
    \input{images/oe-transposition-8.tex}
  \end{center}
  \caption{Das \emph{Odd-Even-Transpositionsort}-Netzwerk mit 8~Eingängen.}
  \label{fig:odd-even-transposition-08}
\end{figure}

Dass das \emph{Odd-Even-Transpositionsort}-Netzwerk tatsächlich jede beliebige
Eingabe sortiert, ist nicht offensichtlich. Leicht zu sehen ist jedoch, dass
sowohl das Minimum als auch das Maximum durch das im Netzwerk enthaltene
Treppenmuster auf die unterste beziehungsweise oberste Leitung gelangt.

Die Sortiereigenschaft größerer OET-Netzwerke lässt sich rekursiv beweisen,
indem man $\operatorname{OET}(n)$ auf $\operatorname{OET}(n-1)$ durch
Herausschneiden einer Leitung reduziert. In
Abschnitt~\ref{sect:leitungen_entfernen} wird das Vorgehen im Detail
beschrieben, Abbildung~\ref{fig:oe-transposition-cut} zeigt das
Herausschneiden einer Leitung aus $\operatorname{OET}(8)$. Die Rekursion endet
beim \emph{Odd-Even-Transpositionsort}-Netzwerk mit drei Eingängen, bei dem
das Minimum auf der untersten, das Maximum auf der obersten und der mittlere
Wert auf der mittleren Leitung landet. Folglich ist die Ausgabe bei
$\operatorname{OET}(3)$ sortiert.

Das \emph{Odd-Even-Transpositionsort}-Netzwerk ist weder in Bezug auf die
Anzahl der Komparatoren noch in Bezug auf die Anzahl der Schichten, in denen
sich die Komparatoren anordnen lassen, effizient. Es benötigt ${\frac12 n
(n-1)} = \Theta(n^2)$~Komparatoren, die in $n$~Schichten angeordnet sind.
Die im Folgenden vorgestellten Sortiernetzwerke benötigen deutlich weniger Komparatoren,
($\Theta(n \log (n)^2)$), die in weniger Schichten,
($\Theta(\log (n)^2)$), angeordnet sind.

Das Interessante am OET-Netzwerk ist seine einfache Konstruktion. Einige der
folgenden Algorithmen benötigen ein möglichst einfaches Sortiernetzwerk als
Starteingabe, auf dessen Basis sie versuchen optimierte Sortiernetzwerke zu
finden. Häufig dient $\operatorname{OET}(n)$ als Eingabe für diese
Algorithmen.

Außerdem bedienen sich die Algorithmen der Technik des Herausschneidens einer,
beziehungsweise mehrerer Leitungen, um die Anzahl der Leitungen eines
Sortiernetzwerks zu reduzieren. Die Technik wird in Detail im
Abschnitt~\ref{sect:leitungen_entfernen} beschrieben.

\subsection{Das bitone Mergesort-Netzwerk}

Das \emph{bitone Mergesort}-Netzwerk ($\operatorname{BS}(n)$) ist ein
Sortiernetzwerk, das 1968 von \emph{Kenneth~E. Batcher} in~\cite{B1968}
veröffentlicht wurde. Es ist deutlich effizienter als das
Odd-Even-Transposi\-tionsort-Netzwerk -- sowohl in Bezug auf die Anzahl der
Komparatoren als auch der benötigten Zeit, also der Anzahl der Schichten.

Das Sortiernetzwerk basiert auf einem Komparatornetzwerk, welches zwei
sortierte Listen zusammenfügen (Englisch: \textit{to~merge}) kann. Dieser
\emph{„bitone Mischer“} (Englisch: \textit{bitonic merger}) genannte Baustein
verleiht dem Sortiernetzwerk seinen Namen.

Da das Sortiernetzwerk rekursiv definiert ist, betrachten wir hier nur die
Instanzen des Netzwerks, deren Leitungszahl $n = 2^d$ eine Zweierpotenz ist.
Es ist jedoch möglich, das Sortiernetzwerk für beliebige~$n$ zu erzeugen.

\subsubsection{Der bitone Mischer}\label{sect:der_bitone_mischer}

Das \emph{bitone Mergesort}-Netzwerk basiert auf dem sogenannten \emph{bitonen
Mischer} $\operatorname{BM}(n)$, einem Kom\-parator-Netzwerk, das eine
beliebige \emph{bitone Folge} in eine sortierte Liste umordnen kann. Eine
\emph{bitone Folge} ist eine monoton steigende Folge, gefolgt von einer
monoton absteigenden Folge, oder ein zyklischer Shift davon.
Abbildung~\ref{fig:beispiel-biton} zeigt die vier prinzipiellen Möglichkeiten,
die durch zyklische Shifts entstehen können. Die wichtigsten Varianten für das
\emph{bitone Mergesort}-Netzwerk zeigen die
Abbildungen~\ref{fig:beispiel-biton-0} und~\ref{fig:beispiel-biton-1}. Sie
erhält man, wenn man eine aufsteigend und eine absteigend sortierte Liste
aneinanderhängt. Bei den anderen beiden Formen ist wichtig zu beachten, dass
das letzte Element nicht größer (Abbildung~\ref{fig:beispiel-biton-2}) beziehungsweise
kleiner (Abbildung~\ref{fig:beispiel-biton-3}) als das erste Element der Folge
sein darf.

\begin{figure}
  \centering
  \subfigure[aufsteigend, absteigend]{\input{images/beispiel-biton-0.tex}\label{fig:beispiel-biton-0}}
  \subfigure[absteigend, aufsteigend]{\input{images/beispiel-biton-1.tex}\label{fig:beispiel-biton-1}}
  \subfigure[aufsteigend, absteigend, aufsteigend]{\input{images/beispiel-biton-2.tex}\label{fig:beispiel-biton-2}}
  \subfigure[absteigend, aufsteigend, absteigend]{\input{images/beispiel-biton-3.tex}\label{fig:beispiel-biton-3}}
  \caption{Beispiele bitoner Folgen.}
  \label{fig:beispiel-biton}
\end{figure}

\begin{figure}
  \centering
  \subfigure[normal]{\input{images/bitonic-merge.tex}\label{fig:bitonic-merge-normal}}
  \qquad
  \subfigure[trichter]{\input{images/bitonic-merge-trichter.tex}\label{fig:bitonic-merge-tricheter}}
  \caption{Schematischer Aufbau des bitonen Mischers: Jedes Element der
  aufsteigenden Folge $u_0, u_1, \ldots$ wird mit dem entsprechenden Element
  der absteigend sortierten Folge $v_0, v_1, \ldots$ verglichen. Die beiden
  resultierenden Teilfolgen sind wiederum biton.}
  \label{fig:bitonic-merge-schema}
\end{figure}

Der Mischer funktioniert folgendermaßen: Gegeben sind zwei Folgen mit je
${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}
\end{eqnarray}
Im ersten Schritt werden nun jeweils die Elemente an den gleichen relativen
Positionen verglichen und ggf. vertauscht:
\begin{equation}
u_i \longleftrightarrow v_i, \quad 0 \leqq i < m
\end{equation}
Sei $j \in \{0 \ldots m\}$ der Index der ersten Elemente $u_j$ und $v_j$, die
durch den gemeinsamen Komparator vertauscht werden. Unter der Annahme, dass
Elemente nur vertauscht werden wenn, sie ungleich sind, muss ${u_j > v_j}$
gelten. Mit $u_j \leqq u_{j+1}$ und $v_j \geqq v_{j+1}$ folgt daraus $u_{j+1}
> v_{j+1}$. Es werden also alle Elemente $u_k$ und $v_k$ mit $k \geqq j$
vertauscht. $j = m$ bezeichnet den Fall, in dem das größte Element der
"`linken"' Folge $u_{m-1}$ kleiner ist als das kleinste Element der
"`rechten"' Folge $v_{m-1}$. Daraus folgt, dass sich das Resultat in zwei
bitone Folgen aufteilen lässt: Eine aufsteigende~/ absteigende Folge und eine
absteigende~/ aufsteigende Folge. Abbildung~\ref{fig:bitonic-merge-normal}
zeigt die Situationen vor und nach diesem Schritt des Mischers schematisch.

Um die Folge vollständig zu sortieren, müssen anschließend die beiden
resultierenden bitonen Folgen sortiert werden. Die geschieht ebenfalls
mithilfe des bitonen Mischers, mit zwei Instanzen von
$\operatorname{BM}(\frac{n}{2})$. Diese rekursive Definition endet mit dem
bitonen Mischer mit zwei Leitungen, $\operatorname{BM}(2)$, der als
Komparator-Netzwerk mit einem Komparator zwischen den beiden Leitungen
definiert ist.

Der bitone Mischer kann auch zwei aufsteigende Folgen sortieren. Dazu ist
lediglich eine etwas modifizierte Vergleichs-Kaskade im ersten Schritt
notwendig. Die folgenden, kleineren Mischer erhalten als Eingabe wieder eine
„echte“ bitone Folge. Abbildung~\ref{fig:bitonic-merge-tricheter} zeigt das
Schema des bitonen Mischers für zwei aufsteigend sortierte Folgen. Durch das
Umdrehen einer Folge verändert sich das Muster der Komparatoren ein wenig:
Statt an eine Treppe erinnert das Muster nun an einen Trichter.

Da sich die Anzahl der Leitungen in jedem Rekursionsschritt halbiert, endet
die Rekursion nach $\log(n)$~Schritten. In jedem Rekursionsschritt werden
$\frac{n}{2}$~Komparatoren eingefügt, so dass der gesamte Mischer aus
$\frac{1}{2} n \log(n) = \Theta\left(n \log(n)\right)$~Komparatoren
besteht, die in $\log(n)$~Schichten angeordnet werden können.

\subsubsection{Das bitone Mergesort-Netzwerk}

Ebenso wie der bitone Mischer $\operatorname{BM}(n)$ ist auch das \emph{bitone
Mergesort-Netzwerk} $\operatorname{BS}(n)$ rekursiv definiert. Es setzt sich
zusammen aus zwei Instanzen des bitonen Mergesort-Netzwerks halber Größe
$\bs{\frac{n}{2}}$ für je die Hälfte der Eingänge, sowie dem bitonen Mischer
für $n$~Leitungen $\operatorname{BM}(n)$. Das Rekursionsende ist das bitone
Mergesort-Netzwerk mit nur einer Leitung $\operatorname{BS}(1)$, welches als
leeres Komparatornetzwerk definiert ist. Entsprechend sind die
Komparatornetzwerke $\operatorname{BM}(2)$ und $\operatorname{BS}(2)$
identisch.

Bei der Konstruktion kommt die trichterförmige Anordnung der Komparatoren
(Abbildung~\ref{fig:bitonic-merge-tricheter}) gelegen, weil so die beiden
rekursiven Sortiernetzwerke in die gleiche Richtung sortieren können und so
alle Komparatoren in die gleiche Richtung zeigen.

\begin{figure}
  \begin{center}
  \input{images/batcher-8.tex}
  \end{center}
  \caption{\bs{8}, Batchers \emph{bitones Mergesort}-Netzwerk für 8~Eingänge.
    Markiert sind die beiden Instanzen von \bs{4} (rot), die beiden bitonen
    Mischer~\bm{4} (blau) und die Komparatoren, die im letzten rekursiven
    Schritt hinzugefügt wurden (grün).}
  \label{fig:bitonic-08}
\end{figure}

Das Sortiernetzwerk~$\operatorname{BS}(8)$ ist in
Abbildung~\ref{fig:bitonic-08} zu sehen. Eingezeichnet sind ebenfalls die
beiden Instanzen des Netzwerks~$\operatorname{BS}(4)$ (rot) sowie der bitone
Mischer~$\operatorname{BM}(8)$ (blau). Die trichterförmige Komparator-Kaskade,
die die bitone Eingabefolge in zwei bitone Ausgabefolgen transformiert, ist
grün hinterlegt.

Das \emph{bitone Mergesort}-Netzwerk mit einer Leitungszahl $n = 2^d$, die
eine Zweierpotenz ist, besteht aus $\frac{1}{4} n \log(n) \log(n+1) =
\Theta\left(n (log (n))^2\right)$ Komparatoren, die in $\frac{1}{2}
\log(n) \log(n+1) = \Theta(\log(n)^2)$ Schichten angeordnet sind.

\subsection{Das Odd-Even-Mergesort-Netzwerk}

Obwohl der Name ähnlich klingt, haben das \emph{Odd-Even-Mergesort}-Netzwerk
(OES) und das \emph{Odd-Even-Transpositionsort}-Netzwerk (siehe
Abschnitt~\ref{sect:odd_even_transpositionsort}) wenig gemein. Vielmehr ist
OES dem \emph{bitonen Mergesort}-Netzwerk, das im vorherigen Abschnitt
vorgestellt wurde, ähnlich: Auch dieses Sortiernetzwerk ist von
\textit{Kenneth~E. Batcher} gefunden worden und ist ebenfalls in~\cite{B1968}
beschrieben und initial analysiert worden. Eine weitere Gemeinsamkeit besteht
darin, dass es ebenfalls rekursiv durch einen Mischer definiert ist.

\subsubsection{Der \emph{Odd-Even}-Mischer}\label{sect:der_odd_even_mischer}

Der \emph{Odd-Even}-Mischer $\operatorname{OEM}(n,m)$ ist ein
Komparatornetzwerk, das zwei sortierte Folgen mit $n$ beziehungsweise $m$
Elementen zu einer sortierten Ausgabefolge mit $N = n+m$~Elementen
zusammenfügen kann. Dabei kommt es mit weniger Vergleichen aus als der
\emph{bitone Mischer}, der im Abschnitt~\ref{sect:der_bitone_mischer}
vorgestellt wurde. Im allgemeinen Fall, wenn die Anzahl der Leitungen keine
Zweierpotenz ist, kann das \emph{bitonic-Merge}-Netzwerk schneller sein 
als das \emph{Odd-Even-Merge}-Netzwerk.~\cite{KNUTH}

Der \emph{Odd-Even}-Mischer selbst ist ebenfalls rekursiv aufgebaut: Die
Eingabe für den Mischer mit $N = n + m$ Leitungen besteht aus den beiden
sortierten Folgen $U = \left(u_0, u_1, \ldots, u_{n-1}\right)$ und
$V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die gesamte Eingabe sei
$W = \left(w_0, w_1, \ldots, w_{N-1}\right)$ mit:
\begin{equation}
w_i = \left\{ \begin{array}{ll}
        u_i,     & i < n \\
        v_{i-n}, & i \geqq n
      \end{array} \right.,
      \quad 0 \leqq i < N
\end{equation}

\begin{figure}
  \begin{center}
  \input{images/oe-merge.tex}
  \end{center}
  \caption{Schematischer Aufbau des \emph{Odd-Even-Merge}-Netzwerks. Die
    beiden Dreiecke symbolisieren die beiden sortierten Folgen $U$ und $V$,
    die Blöcke darunter die rekursiven Mischer mit etwa der Hälfte der
    Leitungen. Im Vergleich zum \emph{bitonen Mischer} für 8~Leitungen kommt
    dieses Schema mit einem Komparator weniger aus. Der Effekt wird durch den
    rekursiven Aufbau verstärkt.}
  \label{fig:oe-merge}
\end{figure}

Diese werden in insgesamt vier sortierte Folgen aufgeteilt, je eine Liste der
geraden Indizes und je eine Liste der ungeraden Indizes.
\begin{eqnarray}
  U_{\textrm{gerade}}   &=& \left(u_0, u_2, u_4, \ldots\right) \\
  U_{\textrm{ungerade}} &=& \left(u_1, u_3, u_5, \ldots\right) \\
  V_{\textrm{gerade}}   &=& \left(v_0, v_2, u_4, \ldots\right) \\
  V_{\textrm{ungerade}} &=& \left(v_1, v_3, u_5, \ldots\right)
\end{eqnarray}

Die geraden Folgen $U_{\textrm{gerade}}$ und $V_{\textrm{gerade}}$,
beziehungsweise die ungeraden Folgen $U_{\textrm{ungerade}}$ und
$V_{\textrm{ungerade}}$ werden rekursiv von kleineren \emph{Odd-Even}-Mischern
zusammengefügt, so dass sich am Ausgang der Mischer die Folgen
\begin{eqnarray}
  W_{\textrm{gerade}}   &=& \left(w_0, w_2, w_4, \ldots\right) \\
  W_{\textrm{ungerade}} &=& \left(w_1, w_3, w_5, \ldots\right)
\end{eqnarray}
ergeben.

Anschließend werden die Komparatoren zwischen benachbarten Leitungen
hinzugefügt,
\begin{equation}
  w_{2i-1} \longleftrightarrow w_{2i}, \quad 1 \leqq i < \frac{N}{2}
\end{equation}
die die Folge~$W$ sortieren. Den schematischen Aufbau des
\emph{Odd-Even}-Mischers zeigt Abbildung~\ref{fig:oe-merge}.

Leider bricht die Rekursion nicht so schön ab, wie das beim {\em bitonen
Mischer} der Fall gewesen ist. Insbesondere für ${n = m = 1}$ würde --
entsprechend der Konstruktionsvorschrift -- ein leeres Netzwerk entstehen, was
offensichtlich nicht korrekt wäre. Die Abbruchbedingungen für den rekursiven
Aufbau lauten:
\begin{itemize}
  \item Falls ${n = 0}$ oder ${m = 0}$: Das Netzwerk ist leer.
  \item Falls ${n = 1}$ und ${m = 1}$: Das Netzwerk besteht aus einem
  einzelnen Komparator.
\end{itemize}

Mit dem {\em 0-1-Prinzip} lässt sich zeigen, dass die resultierende Folge
sortiert ist. Da $U$ und $V$ sortiert sind, ist die Anzahl der Nullen in den
geraden Teilfolgen $U_{\textrm{gerade}}$, beziehungsweise
$V_{\textrm{gerade}}$ größer oder gleich der Anzahl der Nullen in den
ungeraden Teilfolgen $U_{\textrm{ungerade}}$ beziehungsweise
$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}
  \left|W_{\textrm{gerade}}\right|_0
  &=& \left|U_{\textrm{gerade}}\right|_0
    + \left|V_{\textrm{gerade}}\right|_0
   =  \left\lceil \frac{1}{2} \left|U\right|_0 \right\rceil
   +  \left\lceil \frac{1}{2} \left|V\right|_0 \right\rceil \\
  \left|W_{\textrm{ungerade}}\right|_0
  &=& \left|U_{\textrm{ungerade}}\right|_0
    + \left|V_{\textrm{ungerade}}\right|_0
   =  \left\lfloor \frac{1}{2} \left|U\right|_0 \right\rfloor
   +  \left\lfloor \frac{1}{2} \left|V\right|_0 \right\rfloor
\end{eqnarray}
Daraus folgt, dass $W_{\textrm{gerade}}$ $0$, $1$ oder $2$ Nullen mehr enthält
als $W_{\textrm{ungerade}}$. In den ersten beiden Fällen ist die "`verzahnte"'
Ausgabe der beiden kleineren Mischer bereits sortiert. Nur im letzten Fall,
wenn $W_{\textrm{gerade}}$ zwei Nullen mehr enthält als
$W_{\textrm{ungerade}}$, muss genau eine Vertauschung stattfinden, um die
Ausgabe zu sortieren. Diese wird von den Komparatoren ausgeführt, die
benachbarte Leitungen miteinander vergleichen. Die jeweiligen Situationen sind
in Abbildung~\ref{fig:oe-post-recursive} dargestellt.

\begin{figure}
  \centering
  \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 0$]{\input{images/oe-post-recursive-diff0.tex}}
  \qquad
  \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 1$]{\input{images/oe-post-recursive-diff1.tex}}
  \qquad
  \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 2$]{\input{images/oe-post-recursive-diff2.tex}}
  \caption{Die drei Situationen, die nach dem Verzahnen der Ausgaben der
  kleineren \emph{Odd-Even}-Mischer entstehen können. Ist die Differenz der
  Anzahl der Nullen gleich $0$ oder $1$, ist die Folge bereits sortiert. Im
  letzten Fall stellt einer der Komparatoren sicher, dass das Ergebnis
  sortiert ist.}
  \label{fig:oe-post-recursive}
\end{figure}

Da die Teilfolgen $U$ und $V$ in jedem Rekursionsschritt etwa halbiert werden,
bricht die Rekursion nach $\Theta\left(\log (n) + \log (m)\right)$
Schritten ab. Die exakte Anzahl der benötigten Rekursionsschritte (und damit
Schichten im Mischer-Netzwerk), hängt von der längeren der beiden
Eingabefolgen ab und beträgt $1 + \lceil \log\left(\max(n, m)\right) \rceil$.

Die Anzahl der Komparatoren $K(n,m)$, die $\operatorname{OEM}(n,m)$ im
allgemeinen Fall verwendet, hängt gemäß der rekursiven Definition von der
Länge der Eingabefolgen, $n$ und $m$ ab:
\begin{displaymath}
  K(n,m) = \left\{ \begin{array}{ll}
    nm, & \mathrm{falls} \quad nm \leqq 1 \\
    K\left(\left\lceil \frac{n}{2} \right\rceil, \left\lceil \frac{m}{2} \right\rceil\right)
    + K\left(\left\lfloor \frac{n}{2} \right\rfloor, \left\lfloor \frac{m}{2} \right\rfloor\right)
    + \left\lfloor \frac{1}{2} (m + n - 1) \right\rfloor & \mathrm{falls} \quad nm > 1
  \end{array} \right.
\end{displaymath}
Leider ist es schwierig, diese allgemeine Formel in einer geschlossenen Form
anzugeben. Aus der Anzahl der Rekursionsschritte ist jedoch leicht erkennbar,
dass $K(n,m)$ in $\Theta(N \log (N))$ enthalten ist.

Für den wichtigen Spezialfall, dass $n = m = 2^{d-1}$ beträgt, lässt sich die
Anzahl der Komparatoren im Vergleich zum \emph{bitonen Mischer} angeben: Der
erste Rekursionsschritt der OEM-Konstruktion fügt
$\left\lfloor \frac{1}{2} (m + n - 1) \right\rfloor = \frac{N}{2} - 1$
Komparatoren ein -- einen Komparator weniger als der \emph{bitone Mischer} in
diesem Schritt. Das selbe gilt für die rekursiv verwendeten kleineren Mischer
$\operatorname{OEM}(\frac{n}{2}, \frac{n}{2})$ und so weiter bis
einschließlich $\operatorname{OEM}(2, 2)$, von denen es $2, 4, \dots,
\frac{N}{4} = 2^{\log(N)-2}$ Instanzen gibt. Insgesamt werden
\begin{displaymath}
  \sum_{i=0}^{\log(N)-2} 2^i = 2^{\log(N) - 1} - 1 = \frac{N}{2} - 1 = n - 1
\end{displaymath}
Komparatoren eingespart. Damit ergibt sich
\begin{displaymath}
  K\left(n = 2^{d-1}, n = 2^{d-1}\right) = \frac{1}{2} N \log(N) - \frac{N}{2} + 1
\end{displaymath}
für die Anzahl der Komparatoren, die von $\operatorname{OEM}(N = 2^d)$
benötigt werden.

\subsubsection{Das Odd-Even-Mergesort-Netzwerk}

Das \emph{Odd-Even-Mergesort}-Netzwerk $\operatorname{OES}(n)$ besteht, wie
das \emph{bitone Mergesort}-Netzwerk, rekursiv aus kleineren Varianten von
sich selbst und einem abschließenden \emph{Odd-Even}-Mischer. Die
effizientesten Sortiernetzwerke in Bezug auf Komparator- und Schichtzahl
entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht
\oes{n} aus $\oes{\left\lceil\frac{n}{2}\right\rceil}$,
$\oes{\left\lfloor\frac{n}{2}\right\rfloor}$ und
$\oem{\left\lceil\frac{n}{2}\right\rceil, \left\lfloor\frac{n}{2}\right\rfloor}$.
Die Rekursion endet mit $\operatorname{OES}(1)$ und $\operatorname{OES}(0)$,
die als leere Komparatornetzwerke definiert sind.

\begin{figure}
  \begin{center}
  \input{images/oe-mergesort-8.tex}
  \end{center}
  \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für 8~Eingänge. Markiert
  sind die Instanzen von $\operatorname{OES}(4)$ (rot), die beiden
  \emph{Odd-Even}-Mischer $\operatorname{OEM}(4)$ für gerade und ungerade
  Leitungen (blau) und die im ersten Rekursionsschritt hinzugefügten
  Komparatoren zwischen benachbarten Leitungen (grün).}
  \label{fig:odd-even-mergesort-08}
\end{figure}

In Abbildung~\ref{fig:odd-even-mergesort-08} ist das \oes{8}-Sortiernetzwerk
zu sehen. Rot markiert sind die beiden rekursiven Instanzen
$\operatorname{OES}(4)$. Die anderen Blöcke stellen den
\emph{Odd-Even}-Mischer für 8~Leitungen dar: die beiden blauen Blöcke sind
die rekursiven Instanzen von $\operatorname{OEM}(4)$, der grüne Block markiert
die Komparatoren, die im ersten Rekursionsschritt hinzugefügt werden.

Im Allgemeinen ist die Anzahl der Komparatoren, die vom
\emph{Odd-Even-Mergesort-Netz\-werk} verwendet wird, $k(n)$, direkt aus der
Definition, beziehungsweise der Konstruktionsanleitung abzulesen:
\begin{displaymath}
  k(n) = k\left(\left\lceil\frac{n}{2}\right\rceil\right)
       + k\left(\left\lfloor\frac{n}{2}\right\rfloor\right)
       + K\left(\left\lceil\frac{n}{2}\right\rceil, \left\lfloor\frac{n}{2}\right\rfloor\right)
\end{displaymath}
Da es schwierig ist für $K(n,m)$ eine geschlossene Form anzugeben, ist eine
geschlossene Darstellung von $k(n)$ ebenfalls nicht ohne weiteres möglich. Es
ist allerdings bekannt, dass $k(n)$ in $\Theta\left(n \left(\log
(n)\right)^2\right)$ enthalten ist.

Für den wichtigen Spezialfall, dass $n = 2^d$ eine Zweierpotenz ist, kann die
Anzahl der Komparatoren wieder explizit angegeben werden. \textit{Kenneth
Batcher} zeigt in~\cite{B1968}, dass in diesem Fall
\begin{displaymath}
  k(n = 2^d) = \frac{1}{4} n \left(\log (n)\right)^2 - \frac{1}{4}n\log(n) + n - 1
\end{displaymath}
gilt.

% gnuplot:
% oem(n,m) = ((n*m) <= 1) ? (n*m) : oem(ceil(.5*n), ceil(.5*m)) + oem(floor(.5*n), floor(.5*m)) + floor(.5*(n+m-1.0))
% oem1(n) = oem(ceil(.5*n),floor(.5*n))
% oes(n) = (n <= 1.0) ? 0 : oes(ceil(0.5*n)) + oes(floor(0.5*n)) + oem1(n)

%\begin{itemize}
%\item Pairwise sorting-network
%\end{itemize}

\subsection{Das Pairwise-Sorting-Netzwerk}

Das \emph{Pairwise-Sorting}-Netzwerk \ps{n} ist eine Konstruktionsvorschrift
für Sortiernetzwerke, die 1992 von \textit{Ian Parberry} in seiner Arbeit „The
Pairwise Sorting Network“ \cite{P1992} definiert wurde. Wenn die Anzahl der
Leitungen $n = 2^d$ eine Zweierpotenz ist, hat das
\emph{Pairwise-Sorting}-Netzwerk die selbe Effizienz und Geschwindigkeit wie
das \emph{Odd-Even-Mergesort}-Netzwerk.

\newpage
\section{Transformation von Sortiernetzwerken}
\label{sect:tranformation}

\subsection{Komprimieren}

Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
gleichzeitig ausgewertet werden, wie bereits in
Abschnitt~\ref{sect:einleitung_sortiernetzwerke} beschrieben. Durch manche
Transformationen, insbesondere das Entfernen einer Leitung wie in
Abschnitt~\ref{sect:leitungen_entfernen} beschrieben, kann es vorkommen, dass
die Komparatoren eines Sortiernetzwerks nicht mehr in der kleinstmöglichen
Anzahl von \emph{Schichten} angeordnet sind. Unter \emph{Komprimierung} wird
eine (Neu-)Gruppierung der Komparatoren verstanden, die jeden Komparator so
früh wie möglich ausführt. So entsteht die kleinstmögliche Anzahl von
\emph{Schichten}, in die sich ein Sortiernetzwerk unterteilen lässt.

Diese Anzahl ist insbesondere beim automatisierten Bewerten von
Komparatornetzwerken interessant, wie in Abschnitt~\ref{sect:sn-evolution:bewertung}
beschrieben. Die Anzahl der Schichten kann künstlich vergrößert werden, indem
Komparatoren später angewendet werden. Deshalb sollte vor einer Bewertung, die
die Anzahl der Schichten als Bewertungskriterium verwendet, immer eine
Komprimierung durchgeführt werden.

\subsection{Normalisieren}
\label{sect: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.\footnote{Die Konvention in dieser Arbeit ist, dass in diesem Fall alle
Pfeile nach unten zeigen. Das Minimum wird auf der untersten, das Maximum auf
der obersten Leitung ausgegeben.} Jedes Sortiernetzwerk kann in eine
normaliesierte Variante transformiert werden. Dazu gibt beispielsweise
\emph{Donald~E. Knuth} in~\cite{KNUTH} einen Algorithmus an.

Abbildung~\ref{fig:beispiel_normalisieren} stellt das \emph{bitone
Mergesort}-Netzwerk in zwei Varianten dar. 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 untere 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 selbe
Richtung. Statt dem typischen „Treppenmuster“ sind abwechselnd das Treppen-
und das Trichtermuster zu sehen.

\subsection{Zwei Netzwerke kombinieren}

Um Sortiernetzwerke als \emph{Individuen} evolutionärer Algorithmen verwenden
zu können, muss es möglich sein, zwei Sortiernetzwerke zu einem neuen
Sortiernetzwerk zusammenzufassen.

Diese Technik wurde in den vorangegangen Abschnitten bereits verwendet,
beispielsweise um zwei \emph{bitone Mergesort}-Netzwerke mit jeweils der
halben Leitungszahl, $\operatorname{BS}\left(\frac{n}{2}\right)$, zu einem
einzigen Sortiernetzwerk $\operatorname{BS}(n)$ zu kombinieren. Auch das
\emph{Odd-Even-Mergesort}-Netzwerk $\operatorname{OES}(n)$ wurde auf diese Art
und Weise rekursiv aufgebaut.

Die vorgestellten \emph{Mischer} erwarten als Eingabe zwei bereits sortierte
Folgen. \emph{Wie} diese Folgen sortiert wurden ist unerheblich. Entsprechend
können wir beliebige Sortiernetzwerke einsetzen, um die beiden Eingabefolgen
zu sortieren und die Ausgaben mit einem der beschriebenen Mischer
zusammenfügen.

Beispielsweise kann die Ausgabe von zwei \emph{bitonen Mergesort-Netzwerken}
$\operatorname{BS}(8)$ mit je 8~Leitungen mit dem
\emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM(8,8)}$ zu einer sortierten
Gesamtfolge zusammengefügt werden. Das resultierende Sortiernetzwerk besitzt
73~Komparatoren (zum Vergleich: $\operatorname{BS}(16)$ benötigt
80~Komparatoren, $\operatorname{OES}(16)$ nur 63).

Verbesserungen der Effizienz (die Anzahl der benötigten Komparatoren),
beziehungsweise der Geschwindigkeit (die Anzahl der Schichten) eines „kleinen“
Sortiernetzwerks, übertragen sich direkt auf das resultierende Gesamtnetzwerk.
Das \emph{Odd-Even-Mergesort}-Netzwerk $\operatorname{OES}(9)$ benötigt
beispielsweise 26~Komparatoren, die in 9~Schichten angeordnet sind. Es sind
allerdings Sortiernetzwerke mit 9~Eingängen bekannt, die lediglich
25~Komparatoren in 7~Schichten benötigen. Wenn zwei dieser Netzwerke mit dem
\emph{Odd-Even}-Mischer kombiniert werden, entsteht ein 18-Sortiernetzwerk,
das aus 80~Komparatoren in 11~Schichten besteht. Damit ist das resultierende
Netzwerk genauso schnell wie das Sortiernetzwerk mit 18~Eingängen, das
\textit{Sherenaz~W. 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. $\operatorname{OES}(18)$ benötigt
82~Komparatoren in 13~Schichten.

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
Aneinanderreihung der Art „die ersten $x$~Schichten des einen, dann die
letzten $y$~Schichten des anderen Sortiernetzwerks“ zerstören im Allgemeinen
die Sortiereigenschaft. Die Sortiereigenschaft des resultierenden
Komparatornetzwerks müsste überprüft werden, was nach heutigem Wissensstand
nur mit exponentiellem Aufwand möglich ist.

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

Im vorherigen Abschnitt wurde gezeigt, dass es mithilfe von \emph{Mischern}
möglich ist, aus zwei Sortiernetzwerken mit je $n$~Eingängen
ein neues Sortiernetzwerk mit $2n$~Eingängen zu erzeugen. Für einen
beabsichtigen \emph{evolutionären Algorithmus} ist es jedoch notwendig, dass
sich die Anzahl der Eingänge nicht verändert. Es soll wieder ein
Sortiernetzwerk mit $n$~Eingängen entstehen.

Man kann ein gegebenes Sortiernetzwerk mit $n$~Eingängen auf ein
Sortiernetzwerk mit ${n-1}$~Leitungen verkleinern, indem man eine Leitung
„eliminiert“. Dazu wird angenommen, dass das Minimum oder das Maximum an einem
bestimmten Eingang anliegt. Der Weg, den das Minimum beziehungsweise das
Maximum durch das Sortiernetzwerk nimmt, ist eindeutig bestimmt und endet an
einem der „Ränder“, also auf der Leitung mit dem höchsten oder dem niedrigsten
Index. Insbesondere ist bekannt, welche Komparatoren „berührt“ werden und
welche dafür sorgen, dass der Wert die Leitung wechselt, da das Minimum jeden
Vergleich „verliert“ und das Maximum jeden Vergleich „gewinnt“. Die
Abbildung~\ref{fig:oe-transposition-cut0} zeigt den Weg eines Maximums durch
das \emph{Odd-Even-Transpositionsort}-Netzwerk.

Im ersten Schritt wird eine Leitung ausgewählt und Maximum oder Minimum auf
dieser Leitung angenommen. Dadurch ist der Weg durch das Sortiernetzwerk
eindeutig festgelegt.

\begin{figure}
  \centering
  \subfigure[Auf der Leitung~4 wird $-\infty$ angelegt. Dadurch ist der Pfad
  durch das Sortiernetzwerk eindeutig festgelegt.]{\input{images/oe-transposition-cut0.tex}\label{fig:oe-transposition-cut0}}
  \subfigure[Komparatoren, die einen Wechsel der Leitungen bewirken, werden
  durch sich kreuzende Leitungen ersetzt.]{\input{images/oe-transposition-cut1.tex}\label{fig:oe-transposition-cut1}}
  \subfigure[Leitung~4 wurde entfernt. Übrig bleibt ein Sortiernetzwerk mit
  7~Leitungen.]{\input{images/oe-transposition-cut2.tex}\label{fig:oe-transposition-cut2}}
  \subfigure[Die Leitungen wurden wieder gerade eingezeichnet und die
  Komparatoren regelmäßig angeordnet. Blau eingezeichnet ist \oet{7}.]{\input{images/oe-transposition-cut3.tex}\label{fig:oe-transposition-cut3}}
  \caption{Eine Leitung wird aus dem
  \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{8} entfernt: Auf der rot
  markierten Leitung wird $-\infty$ angelegt. Da der Wert bei jedem Komparator
  nach unten weiter gegeben wird, ist der Pfad fest vorgegeben. Da die
  restlichen Werte trotzdem noch richtig sortiert werden müssen, kann dieser
  Pfad heraus getrennt werden. In der letzten Abbildung ist \oet{7} markiert.}
  \label{fig:oe-transposition-cut}
\end{figure}

Im nächsten Schritt werden alle beteiligten Komparatoren gelöscht,
beziehungsweise 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 ist eine Leitung, auf der das Minimum beziehungsweise
das Maximum angenommen wird, die an unterster oder oberster Stelle endet und
die keine Komparatoren mehr berührt
(Abbildung~\ref{fig:oe-transposition-cut1}).

Die Werte auf den verbleibenden $(n-1)$~Leitungen müssen vom restlichen
Komparatornetzwerk immer noch sortiert werden: Es wurde lediglich die
\emph{Position}  des Minimums oder des Maximums in der Eingabe angenommen. Ein
Sortiernetzwerk muss die Eingabe sortieren, unabhängig davon auf welcher
Leitung das Minimum oder das Maximum liegt. Das Sortiernetzwerk unter diese
Annahme auszuwerten -- über die verbleibenden Eingänge wurde keine Aussage
getroffen. Entsprechend müssen die verbleibenden Ausgänge eine sortierte Liste
mit $(n-1)$~Elementen darstellen.

Wird die Minimum- beziehungsweise Maximum-Leitung entfernt, wie in
Abbildung~\ref{fig:oe-transposition-cut2} dargestellt, bleibt das
Sortiernetzwerk für $(n-1)$~Leitungen übrig. Je nachdem, ob auf einer Leitung
ein Minimum oder ein Maximum angenommen wird, wird das eliminieren einer
Leitung auf diese Art und Weise als \emph{Minimum-Schnitt}, beziehungsweise
\emph{Maximum-Schnitt} bezeichnet.

Die letzte Abbildung, \ref{fig:oe-transposition-cut3}, zeigt das
Sortiernetzwerk wieder mit den üblichen geraden Leitungen und die rot
markierten Komparatoren sind verschoben, so dass sich eine kompaktere
Darstellung ergibt. Außerdem ist das
\emph{Odd-Even-Transpositionsort}-Netzwerk für sieben Werte markiert. Der
zusätzliche Komparator vor dem \oet{7} hat keinen Einfluss auf die Ausgabe und
kann entfernt werden.

Durch das Ersetzen von Komparatoren durch gekreuzte Leitungen werden häufig
\emph{Nicht-Standard-Sortiernetzwerke} erzeugt. Im Anschluss an einen
\emph{Schnitt} empfiehlt es sich deshalb, das Sortiernetzwerk zu
\emph{normalisieren}, wie in Abschnitt~\ref{sect:normalisieren} beschrieben.

\subsubsection{Anzahl möglicher und unterschiedlicher Schnittmuster}
\label{sect:anzahl_schnittmuster}

Der Eliminierungsschritt kann iterativ angewendet 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 auf diese Art und
Weise Sortiernetzwerke mit $2n$~Eingängen auf Sortiernetzwerke mit
$n$~Eingängen reduziert werden. Als \emph{$k$-Schnittmuster} bezeichnet man
die $k$~Minimum- und Maximum-Schnitte, die nacheinander angewendet ein
$n$-Sortiernetzwerk auf ein ${(n-k)}$-Sortiernetz\-werk reduzieren.

Zwei Schnittmuster heißen \emph{äquivalent} bezüglich~$S$, wenn ihre Anwendung
auf das Sortiernetzwerk~$S$ das selbe Ergebnis liefert. Ansonsten heißen die
Schnittmuster \emph{unterschiedlich} bezüglich~$S$. 

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 ${(n-k)}$-Sortiernetzwerk zu reduzieren,
ergeben sich insgesamt
\begin{displaymath}
  \prod_{i=n}^{1+n-k} 2i = 2^k \cdot \frac{n!}{(n-k)!}
  \quad (n > m)
\end{displaymath}
\emph{mögliche} Schnittmuster. Diese Schnittmuster sind nicht alle
unterschiedlich. Wird beispielsweise das Minimum auf der untersten Leitung
und das Maximum auf der obersten Leitung eines Standard-Sortiernetzwerks
angenommen, führen beide möglichen Schnitt-Reihenfolgen zum selben Ergebnis.

\textit{Moritz Mühlenthaler} zeigt in seiner Arbeit~\cite{M2009}, dass es
möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise Maximum
vorzubelegen, ohne die Menge der erreichbaren Sortiernetzwerke einzuschränken.
Dadurch wird die Anzahl der möglichen Schnittmuster reduziert, die Menge der
so erzeugbaren Sortiernetzwerke bleibt aber unverändert. Die Anzahl der
möglichen Schnittmuster setzt sich zusammen aus der Anzahl von Möglichkeiten,
$k$~Leitungen aus $n$~Leitungen auszuwählen, und die möglichen Minimum-~/
Maximum-Muster. Damit ergibt sich folgende Formel für die Anzahl der möglichen
Schnittmuster:
\begin{equation}\label{eqn:anzahl_schnittmuster}
  2^k \cdot \left( \begin{array}{c} n \\ k \end{array} \right)
  = 2^{k} \cdot \frac{n!}{k! (n-k)!}
  = 2^{k} \cdot \frac{n!}{(n-k)!} \cdot \frac{1}{k!}
  \quad (1 \leqq k < n)
\end{equation}

Die Anzahl der möglichen Schnittmuster wird mit der Anzahl der zu entfernenden
Leitungen sehr schnell sehr groß. Um ein Sortiernetzwerk mit 32~Eingängen auf
ein Sortiernetzwerk mit 16~Eingängen zu reduzieren, ist ein Schnittmuster mit
16~Schnitten notwendig, für das 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.

Die Anzahl der \emph{unterschiedlichen} Schnittmuster ist allerdings kleiner
als die Anzahl der \emph{möglichen} Schnittmuster. Für jeden Komparator auf
der ersten Stufe gibt es neun verschiedene Eingangskonfigurationen: Für beide
Eingänge gibt es drei mögliche Eingangswerte, Minimum, Maximum und
unspezifiziert. Es gibt drei Konfigurationen, bei denen an beiden Eingängen
der gleiche Wert angelegt wird, und sechs Konfigurationen, bei denen sich die
Werte unterscheiden.

Bei diesen letzten sechs Konfigurationen werden je zwei auf das selbe
Ausgangsmuster abgebildet, weil die Position des Minimums beziehungsweise des
Maximums durch den Komparator vorgegeben wird. Das heißt, dass die neun
unterschiedlichen Eingangsmuster nur sechs unterschiedliche Ausgangsmuster
erzeugen. In der zweiten und allen folgenden Schichten kann man diesen
Unterschied nicht mehr erkennen. In allen sechs Fällen, in denen sich die
Eingänge unterscheiden, wird anschließend der Komparator entfernt, so dass
sich die Resultate auch in der ersten Schicht nicht unterscheiden.

\begin{figure}
  \begin{center}
    \includegraphics[viewport=0 0 425 262,width=15cm]{images/count-cuts-16.pdf}
  \end{center}
  \caption{Anzahl der \emph{unterschiedlichen} Sortiernetzwerke, die durch
  8-Schnittmuster aus $\operatorname{OES}(16)$, $\operatorname{BS}(16)$ und
  $\operatorname{PS}(16)$ hervorgegangen sind. Die Anzahl der
  unterschiedlichen Netzwerke nach $10^6$~Iterationen ist 3519 für das
  \emph{Odd-Even-Mergesort}-Netzwerk, 4973 für das \emph{bitone
  Mergesort}-Netzwerk und 18764 für das \emph{Pairwise-Sorting}-Netzwerk.}
  \label{fig:count-cuts-16}
\end{figure}

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
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
Schnittmuster auf. Klar zu sehen ist, dass sich die Anzahl der erzeugten
Sortiernetzwerke nach $500.000$~Iterationen nur noch gering verändert und der
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
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 nicht sinnvoll durchführbar. 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}, die \textit{Rolf Wanka} in~\cite{W2006} für
schwierige Zählprobleme vorstellt. Zunächst generiert man eine Menge~$S$ von
$k$~unterschiedlichen Schnittmustern. Anschließend werden $n$~Schnittmuster
zufällig erzeugt und überprüft, ob sie in der Menge~$S$ enthalten sind. Unter
der Annahme, dass auf diese Art und Weise Sortiernetzwerke zufällig und
gleichverteilt erzeugt werden, entspricht das Verhältnis der zufälligen
Schnittmuster, die in $S$ enthalten sind, und $n$ gleich dem Verhältnis von
$k$ und der Anzahl der unterschiedlichen Schnittmuster insgesamt. Damit kann
die Anzahl der unterschiedlichen Schnittmuster abgeschätzt werden.

\begin{figure}
  \begin{center}
    \includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-10000-1000000-32.pdf}
  \end{center}
  \caption{Abschätzung der unterschiedlichen Schnittmuster mit der
  \emph{Monte-Carlo-Methode} für $\operatorname{OES}(32)$ und
  $\operatorname{BS}(32)$.}
  \label{fig:collisions-10000-1000000-32}
\end{figure}

In Abbildung~\ref{fig:collisions-10000-1000000-32} ist das Ergebnis des
Monte-Carlo-Algorithmus für 16-Schnittmuster zu sehen, die auf
$\operatorname{OES}(32)$ und $\operatorname{BS}(32)$ angewandt wurden: Von
jedem Sortiernetzwerk wurden zunächst eine Menge~$S$ von 10.000
\emph{unterschiedlichen} Schnittmustern erzeugt. Anschließend wurden 1.000.000
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
\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}
    \includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-100000-1000000-32-ps.pdf}
  \end{center}
  \caption{Abschätzung der unterschiedlichen Schnittmuster mit der
  \emph{Monte-Carlo-Methode} für $\operatorname{PS}(32)$. 385 von 1.000.000
  zufälligen Schnittmustern waren äquivalent zu einem Schnittmuster in einer
  Menge von 100.000. Daraus ergibt sich eine Schätzung von $2,6 \cdot 10^8$
  unterschiedlichen Schnittmustern.}
  \label{fig:collisions-100000-1000000-32-ps}
\end{figure}

Im vorherigen Abschnitt wurde das \emph{Pairwise-Sorting}-Netzwerk
$\operatorname{PS}(32)$ nicht betrachtet, da es für dieses Netzwerk viel mehr
unterschiedliche 16-Schnittmuster gibt als für $\operatorname{OES}(32)$ und
$\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)$,
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 unterschiedlichen
Schnittmustern erzeugt. Trotzdem wurden nach 1.000.000 Iterationen nur 385
Schnittmuster gefunden, die zu einem Schnittmuster in der Menge äquivalent
waren. Daraus ergibt sich eine Abschätzung von $2,6 \cdot 10^8$
unterschiedlichen Schnittmustern -- zwei Zehnerpotenzen mehr als bei den
vorherigen Sortiernetzwerken, aber immer noch fünf Zehnerpotenzen kleiner als
die Anzahl der \emph{möglichen} Schnittmuster.

\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
(Abschnitt~\ref{sect:konstruktive_netzwerke}) und Schnittmuster
(Abschnitt~\ref{sect:leitungen_entfernen}) verwendet, um „möglichst gute“
Sortiernetzwerke zu erzeugen. Was ein „gutes“ Sortiernetzwerk ausmacht, wird
in Abschnitt~\ref{sect:sn-evolution:bewertung} behandelt. Informationen zur Implementierung
von \textsc{SN-Evolution} befinden sich in
Abschnitt~\ref{sect:implementierung}.

\subsection{Bewertungsfunktion}\label{sect:sn-evolution:bewertung}

Um Sortiernetzwerke überhaupt optimieren zu können, muss zunächst die
{\em Güte} eines Netzwerks definiert werden. Prinzipiell gibt es zwei Ziele,
die bei Sortiernetzwerken verfolgt werden können:
\begin{itemize}
  \item Möglichst wenige Komparatoren („effizient“)
  \item Möglichst wenige Schichten („schnell“)
\end{itemize}

\begin{figure}
  \centering
  \subfigure[16-Sortiernetzwerk aus 60~Komparatoren in 10~Schichten. Das Netzwerk wurde von \textit{M.~W. Green} konstruiert und 1969 in \todo{Referenz} veröffentlicht.]{\input{images/16-green.tex}\label{fig:16-green}}
  \subfigure[16-Sortiernetzwerk aus 61~Komparatoren in 9~Schichten. Das Netzwerk wurde von \textit{D. Van~Voorhis} veröffentlicht.]{\input{images/16-voorhis.tex}\label{fig:16-voorhis}}
  \caption{Das effizienteste und das schnellste Sortiernetzwerk für
  16~Leitungen, das derzeit bekannt ist.}
  \label{fig:16-best-known}
\end{figure}
Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken.
Beispielsweise besteht das \emph{effizienteste} bekannte Sortiernetzwerk für
16~Eingänge aus 60~Komparatoren in 10~Schichten. Es ist in
Abbildung~\ref{fig:16-green} dargestellt. Das \emph{schnellste} bekannte
16-Sortiernetzwerk besteht aus 61~Komparatoren in nur 9~Schichten und ist in
Abbildung~\ref{fig:16-voorhis} zu sehen.

\textsc{SN-Evolution} verwendet eine Gütefunktion, die die beiden Ziele
"`effizient"' und "`schnell"' berücksichtigen kann. Sie hat die folgende
generelle Form:
\begin{equation}
  \operatorname{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.\footnote{Dass dies nicht
so schlecht ist wie man intuitiv vermuten könnte, zeigt der
\textsc{SN-Markov}-Algorithmus in Abschnitt~\ref{sect:markov}.}

Da möglichst effiziente und schnelle Sortiernetzwerke gefunden werden sollen,
ist ein kleiner Wert von $\operatorname{Guete}(S)$ besser als ein großer Wert.
Das heißt, dass das Ziel von \textsc{SN-Evolution} ist,
$\operatorname{Guete}(S)$ zu \emph{minimieren}.

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 Streben zu (lokalen) Optima, verstärkt.

Diese Parameter haben einen großen Einfluss auf die Geschwindigkeit, mit der
der \textsc{SN-Evolution}-Algorithmus konvergiert und ob er tatsächlich gute
Lösungen findet oder sich in \emph{lokalen} Optima "`verfängt"'. Leider gibt
es kein Patentrezept für die Wahl der Parameter, so dass für verschiedene
Leitungszahlen und Mischer-Typen experimentiert werden muss.

Als guter Standardansatz für \textsc{SN-Evolution} haben sich die folgenden
Werte herausgestellt:
\begin{eqnarray*}
  w_{\mathrm{Basis}}        &=& 0 \\
  w_{\mathrm{Komparatoren}} &=& 1 \\
  w_{\mathrm{Schichten}}    &=& \left|S\right|_\mathrm{Leitungen}
\end{eqnarray*}
Sofern nicht anders angegeben, werden diese Werte im Folgenden zur Bewertung
von Sortiernetzwerken verwendet. Die Bewertungsfunktion bevorzugt mit diesen
Konstanten \emph{schnelle} Sortiernetzwerke, da das Einsparen einer Schicht
ein höheres Gewicht als das Einsparen von Komparatoren hat.

Wenn der \textsc{SN-Evolution}-Algorithmus nach \emph{effizienten}
Sortiernetzwerken suchen soll, werden alternative Werte für die Konstanten der
Bewertungsfunktion verwendet. Die Werte
\begin{eqnarray*}
  w_{\mathrm{Basis}}        &=& 0 \\
  w_{\mathrm{Komparatoren}} &=& 2 \\
  w_{\mathrm{Schichten}}    &=& 1
\end{eqnarray*}
geben dem Einsparen eines Komparators ein höheres Gewicht als dem Einsparen
einer Schicht. \todo{Fehler hier noch was?}

\subsection{Selektion}

Als \emph{Selektion} wird der Vorgang bezeichnet, der zwei Individuen zufällig
aus der Population auswählt. Sie werden im folgenden Schritt miteinander
rekombiniert. Die Auswahl der Individuen erfolgt zufällig, aber nicht
gleichverteilt. So sorgt die \emph{Selektion} dafür, dass bessere Individuen
eine größere Wahrscheinlichkeit haben zur nächsten Generation beizutragen.
Diese Ungleichbehandlung von Individuen verschiedener Güte ist der Grund für
das Streben des Algorithmus nach besseren Lösungen.

Obwohl dieser Vorteil für gute Individuen intuitiv als sehr gering erscheint,
passiert es häufig, dass die Ausnutzung \emph{(Exploitation)} überhand gewinnt
und der Algorithmus vorschnell in Richtung eines lokalen Optimums optimiert.

Die in \textsc{SN-Evolution} implementierte Selektion eines Individuums lässt
sich mit Pseudocode wie folgt beschreiben:
\begin{verbatim}
  Gütesumme := 0
  Auswahl := (leer)
  
  für jedes Individuum in Population
  {
    reziproke Güte := 1.0 / Guete(Individuum)
    Wahrscheinlichkeit P := reziproke Güte / (Gütesumme + reziproke Güte)
    Gütesumme := Gütesumme + reziproke Güte
  
    mit Wahrscheinlichkeit P
    {
      Auswahl := Individuum
    }
  }
  gib Auswahl zurück
\end{verbatim}

Diese Auswahl wird zweimal ausgeführt, um zwei Individuen für die
Rekombination zu erhalten. Das heißt, dass die Individuen bei
\textsc{SN-Evolution} stochastisch unabhängig voneinander ausgewählt werden.

\subsection{Rekombination}
\label{sect:sn-evolution:rekombination}

Bei der Rekombination werden zwei Individuen --~hier Sortiernetzwerke~-- zu
einer neuen Lösung kombiniert. Geeignete Mischer, um die beiden Netzwerke zu
einem Netzwerk mit $2n$~Leitungen zusammenzufügen, sind zum Beispiel der {\em
bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) und der
\emph{Odd-Even}-Mischer (Abschnitt~\ref{sect:der_odd_even_mischer}),
Anschließend werden $n$~Leitungen mit einem zufälligen $n$-Schnittmuster wie
in Abschnitt~\ref{sect:leitungen_entfernen} beschrieben entfernt.

Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft
erhält. Entsprechend muss nicht aufwendig überprüft werden, ob das
Komparatornetzwerk die Sortiereigenschaft besitzt. Der Nachteil ist, dass
nicht alle Sortiernetzwerke auf diese Art und Weise erzeugt werden können.

\subsection{Mutation}

Zu einem vollständigen evolutionären Algorithmus gehört außerdem die Mutation
--~eine zufällige Veränderung einer Lösung. Leider ist es nicht möglich ein
Sortiernetzwerk zufällig zu verändern und dabei 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, wie in Abschnitt~\ref{sect:0-1-prinzip}
beschrieben.

Um das Potenzial einer Mutation abzuschätzen wurde in \textsc{SN-Evolution}
eine Überprüfung eingebaut: Unmittelbar vor dem Einfügen in die Population
überprüft eine Funktion die Notwendigkeit jedes einzelnen Komparators. Dazu
wird nacheinander jeder Komparator entfernt und überprüft, ob das verbleibende
Netzwerk die Sortiereigenschaft noch besitzt. Trotz des hohen Rechenaufwands
-- bei 16-Sortiernetzwerken sind gut 4~Millionen Tests notwendig, um alle
Komparatoren zu überprüfen -- waren die Ergebnisse ernüchternd: Nach circa
1~Million Iterationen mit 16-Sortiernetzwerken fand der so modifizierte
Algorithmus keinen einzigen Komparator, den er hätte entfernen können. Daher
wurde beim \textsc{SN-Evolution}-Algorithmus auf eine Mutation verzichtet.

\subsection[Bitoner Mischer]{Versuche mit dem bitonen Mischer}

Wenn \textsc{SN-Evolution} mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk
als Eingabe gestartet wird und in der Rekombinationsphase den \emph{bitonen
Mischer} verwendet, gibt der Algorithmus \emph{effiziente} und in einigen
Fällen \emph{schnelle} Sortiernetzwerke aus. Die Ergebnisse des
\textsc{SN-Evolution}-Algorithmus unter Verwendung des \emph{bitonen Mischers}
sind in Tabelle~\ref{tbl:sn-ev-bm-fast} zusammengefasst.

\begin{table}\label{tbl:sn-ev-bm-fast}
\begin{center}
\rowcolors{4}{black!5}{}
\begin{tabular}{|r|r|r|r|r|}
\hline
Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}} & \multicolumn{2}{|l|}{\bs{n}} \\
\cline{2-5}
    ($n$) & Komp. & Schichten & Komp. & Schichten \\
\hline
        8 & \gcell  20 &         6 &  24 &  6 \\
        9 & \Gcell  26 &         8 &  28 &  8 \\
       10 & \gcell  31 & \gcell  8 &  33 &  9 \\
       11 & \Gcell  37 & \Gcell  9 &  39 & 10 \\
       12 & \gcell  42 & \gcell  9 &  46 & 10 \\
       13 & \Gcell  48 &        10 &  53 & 10 \\
       14 & \gcell  54 &        10 &  61 & 10 \\
       15 & \Gcell  61 &        10 &  70 & 10 \\
       16 & \gcell  67 &        10 &  80 & 10 \\
       17 & \Gcell  76 &        12 &  85 & 12 \\
       18 & \gcell  87 & \gcell 12 &  91 & 13 \\
       19 & \Gcell  93 & \Gcell 13 &  98 & 14 \\
       20 & \gcell 104 & \gcell 13 & 106 & 14 \\
       21 & \Gcell 109 & \Gcell 14 & 114 & 15 \\
       22 & \gcell 118 & \gcell 14 & 123 & 15 \\
       23 & \Gcell 129 & \Gcell 14 & 133 & 15 \\
       24 & \gcell 133 &        15 & 144 & 15 \\
\hline
\end{tabular}
\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus
  unter Verwendung des \emph{bitonen Merge}-Netzwerks \bm{n}. Der Algorithmus
  wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n} gestartet
  und nach 2.500.000 Iterationen beendet. Die Bewertungsfunktion nutzte die
  Konstanten $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = 1$,
  $w_{\mathrm{Schichten}} = n$.}
\end{center}
\end{table}

Alle Sortiernetzwerke, die von \textsc{SN-Evolution} in dieser Konfiguration
gefunden wurden, waren \emph{effizienter} als das \emph{bitone
Mergesort}-Netzwerk \bs{n}, das ebenfalls auf dem \emph{bitonen
Merge}-Netzwerk \bm{n} beruht. Zum Beispiel benötigt das in
Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte 16-Sortiernetzwerk
67~Komparatoren, 13~Komparatoren weniger als \bs{n}.

\begin{figure}
  \begin{center}
    \input{images/16-e1-bitonic-1296542566.tex}
  \end{center}
  \caption{Sortiernetzwerk mit 16~Leitungen und 67~Komparatoren in
    10~Schichten. Das Netzwerk wurde von dem Algorithmus
    \textsc{SN-Evolution} unter Verwendung des \emph{bitonen Mischers}
    erzeugt.}
  \label{fig:16-e1-bitonic-1296542566}
\end{figure}

Wenn die Gütefunktion so gewählt ist, dass sie schnelle Sortiernetzwerke
bevorzugt, werden in einigen Fällen Netzwerke zurückgegeben, die
\emph{schneller} und \emph{effizienter} als \bs{n} sind. Das
19-Sortiernetzwerk in Abbildung~\ref{fig:19-e1-bm-fast} besitzt beispielsweise
nur 13~Schichten und benötigt damit einen parallelen Schritt weniger als
\bs{19}.

\begin{figure}
  \begin{center}
    \input{images/19-e1-bm-fast.tex}
  \end{center}
  \caption{Sortiernetzwerk mit 19~Leitungen und 93~Komparatoren in
    13~Schichten. Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution}
    unter Verwendung des \emph{bitonen Mischers} erzeugt.}
  \label{fig:19-e1-bm-fast}
\end{figure}

\subsection[Odd-Even-Mischer]{Versuche mit dem Odd-Even-Mischer}

Die folgenden Ergebnisse wurden erzielt, indem \textsc{SN-Evolution} mit dem
\emph{Odd-Even-Transpositionsort}-Netzwerk als Eingabe gestartet wurde und in
der Rekombinationsphase das \emph{Odd-Even-Merge}-Netzwerk verwendete. So
erzeugt der Algorithmus entweder Sortiernetzwerke, die genauso schnell und
effizient wie das \oes{n}-Netzwerk, oder Sortiernetzwerke, die schneller aber
weniger effizient als das \oes{n}-Netzwerk sind. Die Ergebnisse von
\textsc{SN-Evolution} mit dem \emph{Odd-Even}-Mischer sind in
Tabelle~\ref{tbl:sn-ev-oem-fast} zusammengefasst.

\begin{table}\label{tbl:sn-ev-oem-fast}
\begin{center}
\rowcolors{4}{black!5}{}
\begin{tabular}{|r|r|r|r|r|}
\hline
Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}} & \multicolumn{2}{|l|}{\oes{n}} \\
\cline{2-5}
          & Komp. & Schichten & Komp. & Schichten \\
\hline
        8 &   19 &         6 &         19 &         6 \\
        9 &   26 &         8 &         26 &         8 \\
       10 &   31 &         9 &         31 &         9 \\
       11 &   38 & \Gcell  9 & \Gcell  37 &        10 \\
       12 &   43 & \gcell  9 & \gcell  41 &        10 \\
       13 &   48 &        10 &         48 &        10 \\
       14 &   53 &        10 &         53 &        10 \\
       15 &   59 &        10 &         59 &        10 \\
       16 &   63 &        10 &         63 &        10 \\
       17 &   74 &        12 &         74 &        12 \\
       18 &   82 &        13 &         82 &        13 \\
       19 &   93 & \Gcell 13 & \Gcell  91 &        14 \\
       20 &   97 &        14 &         97 &        14 \\
       21 &  108 & \Gcell 14 & \Gcell 107 &        15 \\
       22 &  117 & \gcell 14 & \gcell 114 &        15 \\
       23 &  129 & \Gcell 14 & \Gcell 122 &        15 \\
       24 &  128 &        15 & \gcell 127 &        15 \\
\hline
\end{tabular}
\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus
  unter Verwendung des \emph{Odd-Even-Merge}-Netzwerks \oem{n}. Der
  Algorithmus wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n}
  gestartet und nach 2.500.000 Iterationen beendet. Die Bewertungsfunktion
  nutzte die Konstanten $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} =
  1$, $w_{\mathrm{Schichten}} = n$.}
\end{center}
\end{table}

Im vorherigen Abschnitt wurde gezeigt, dass der
\textsc{SN-Evolution}-Algorithmus unter Verwendung des \emph{bitonen Mischers}
Sortiernetzwerke erzeugen kann, die effizienter als das rekursiv aus dem
\emph{bitonen Mischer} aufgebaute \emph{bitone Mergesort}-Netzwerk sind.
Dieses Ergebnis lies sich mit dem \emph{Odd-Even-Merge}-Netzwerk nicht
erzielen. Die Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung des
\emph{Odd-Even-Merge}-Netzwerks findet, erreichen das
\emph{Odd-Even-Mergesort}-Netzwerk bezüglich Effizienz, übertreffen es aber
nicht. Ein Beispiel für ein entsprechendes Sortiernetzwerk ist in
Abbildung~\ref{fig:16-e1-oem-fast} dargestellt.

\begin{figure}
  \begin{center}
    \input{images/16-e1-oem-fast.tex}
  \end{center}
  \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in
    10~Schichten. Das Netzwerk wurde von dem Algorithmus
    \textsc{SN-Evolution} unter Verwendung des \emph{Odd-Even}-Mischers
    erzeugt.}
  \label{fig:16-e1-oem-fast}
\end{figure}

Mit einer Gütefunktion, die schnelle Sortiernetzwerke bevorzugt, ist es auch
mit dem \emph{Odd-Even}-Mischer möglich, dass \textsc{SN-Evolution}
Sortiernetzwerke zurück gibt, die schneller als \oes{n} sind. Beispielsweise
benötigt das 19-Sortiernetzwerk, das in Abbildung~\ref{fig:19-e1-oem-fast}
dargestellt ist, nur 13~Schichten, während \oes{19} 14~Schichten benötigt.

\begin{figure}
  \begin{center}
    \input{images/19-e1-oem-fast.tex}
  \end{center}
  \caption{Sortiernetzwerk mit 19~Leitungen und 93~Komparatoren in
    13~Schichten. Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution}
    unter Verwendung des \emph{Odd-Even}-Mischers erzeugt.}
  \label{fig:19-e1-oem-fast}
\end{figure}

%\begin{figure}
%\begin{center}
%\input{images/08-e2-1237993371.tex}
%\end{center}
%\caption{{\tt images/08-e2-1237993371.tex}: 19~Komparatoren in 6~Schichten}
%\label{fig:08-e2-1237993371}
%\end{figure}
%
%\begin{figure}
%\begin{center}
%\input{images/09-e2-1237997073.tex}
%\end{center}
%\caption{{\tt images/09-e2-1237997073.tex}: 25~Komparatoren in 8~Schichten}
%\label{fig:09-e2-1237997073}
%\end{figure}
%
%\begin{figure}
%\begin{center}
%\input{images/09-e2-1237999719.tex}
%\end{center}
%\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}

\subsection{Zufälliger Mischer}

Die Ergebnisse der beiden vorhergehenden Abschnitte zeigen, dass für einige
Leitungszahlen der \emph{bitone Mischer} und für andere Leitungszahlen der
\emph{Odd-Even}-Mischer bessere Ergebnisse liefert. Beispielsweise hat das
Netzwerk für $n = 18$ bei Verwendung des \emph{bitone Mischers} nur
12~Schichten, bei Verwendung des \emph{Odd-Even}-Mischers hingegen nur
82~Komparatoren. Daher liegt die Idee nahe, beide Mischer-Netzwerke zu nutzen,
um das beste Ergebnis beider Konstruktionen zu erreichen.
\textsc{SN-Evolution} kann zu diesem Zweck beim Zusammenfügen zweier
Individuen zufällig zwischen dem \emph{bitonen Mischer} und dem
\emph{Odd-Even}-Mischer wählen.

Die Ergebnisse von \textsc{SN-Evolution} bei einer zufälligen Wahl des
Mischers in der Rekombinationsphase sind in Tabelle~\ref{tbl:sn-ev-rnd-fast}
zusammengefasst. Bei den Leitungszahlen 12, 19, 21, 22 und 23 hat der
Algorithmus Netzwerke mit einer Effizienz erzeugt, die mit nur einem
Mischertyp nicht erreicht wurde. Die Ergebnisse mit den Leitungszahlen 18 und
20 erreichen die Geschwindigkeit der Netzwerke, die mit dem \emph{bitonen
Mischer} generiert wurden, und verbessern gleichzeitig die Effizienz.

\begin{table}\label{tbl:sn-ev-rnd-fast}
\begin{center}
\rowcolors{4}{black!5}{}
\begin{tabular}{|r|r|r|r|r|r|r|}
\hline
Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}}
          & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}}
          & \multicolumn{2}{l|}{\textsc{SN-EV} mit Zufall} \\
\cline{2-7}
    ($n$) & Komp. & Schichten & Komp. & Schichten & Komp. & Schichten \\
\hline
        8 &         20 &         6 & \gcell  19 &         6 & \gcell  19 &         6 \\
        9 &         26 &         8 &         26 &         8 &         26 &         8 \\
       10 &         31 & \gcell  8 &         31 &         9 &         31 & \gcell  8 \\
       11 & \Gcell  37 &         9 &         38 &         9 & \Gcell  37 &         9 \\
       12 &         42 &         9 &         43 &         9 & \gcell  41 &         9 \\
       13 &         48 &        10 &         48 &        10 &         48 &        10 \\
       14 &         54 &        10 & \gcell  53 &        10 & \gcell  53 &        10 \\
       15 &         61 &        10 & \Gcell  59 &        10 & \Gcell  59 &        10 \\
       16 &         67 &        10 & \gcell  63 &        10 &         64 &        10 \\
       17 &         76 &        12 & \Gcell  74 &        12 & \Gcell  74 &        12 \\
       18 &         87 & \gcell 12 & \gcell  82 &        13 &         83 & \gcell 12 \\
       19 &         93 &        13 &         93 &        13 & \Gcell  92 &        13 \\
       20 &        104 & \gcell 13 & \gcell  97 &        14 &        101 & \gcell 13 \\
       21 &        109 &        14 &        108 &        14 & \Gcell 107 &        14 \\
       22 &        118 &        14 &        117 &        14 & \gcell 116 &        14 \\
       23 &        129 &        14 &        129 &        14 & \Gcell 128 &        14 \\
       24 &        133 &        15 & \gcell 128 &        15 &        130 &        15 \\
\hline
\end{tabular}
\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus
  unter Verwendung der verschiedenen Mischer. Der Algorithmus wurde mit dem
  \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n} gestartet und nach
  2.500.000 Iterationen beendet. Die Bewertungsfunktion nutzte die Konstanten
  $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = 1$,
  $w_{\mathrm{Schichten}} = n$.}
\end{center}
\end{table}

%\input{shmoo-aequivalenz.tex}

\newpage
\section{Der \textsc{SN-Markov}-Algorithmus}
\label{sect:markov}

Der evolutionäre \textsc{SN-Evolution}-Algorithmus aus dem vorherigen
Abschnitt verwendet immer zwei zufällige Sortiernetzwerke („Individuen“) aus
einer Population. Da die beiden „Eltern“ zufällig und unabhängig voneinander
ausgewählt werden, kann es vorkommen, dass das selbe Sortiernetzwerk zweimal
verwendet und mit sich selbst kombiniert wird.

Macht man diesen Spezialfall zum Regelfall, kombiniert das aktuelle Netzwerk
\emph{immer} mit sich selbst und eliminiert anschließend die Hälfte aller
Leitungen, lassen sich einige interessante Beobachtungen anstellen. Netzwerke,
die aus einem Netzwerk $S_0$ durch die beschriebene Kombination von $S_0$ mit
sich selbst und anschließendem Eliminieren der Hälfte der Leitungen hervorgehen
können, heißen \emph{Nachfolger} von $S_0$.

Beim beschriebenen Vorgehen kann man die Sortiernetzwerke als Knoten in einem
(gerichteten) Graphen betrachten. Zwei Knoten $V_0$ und $V_1$, die zwei
Sortiernetzwerke $S_0$ und $S_1$ repräsentieren, sind genau dann mit einer
Kante ${E_{0,1} = (V_0, V_1)}$ verbunden, wenn $S_1$ ein \emph{Nachfolger} von
$S_0$ ist, das heißt, dass $S_1$ durch die Rekombination von $S_0$ mit sich
selbst erzeugt werden kann.

Wie in Abschnitt~\ref{sect:anzahl_schnittmuster} beschrieben, ist die Anzahl
der \emph{unterschiedlichen} Schnittmuster und damit die Anzahl der Nachfolger
sehr groß. Bei den untersuchten 16-Sortiernetzwerken lag die Anzahl der
Nachfolger zwar noch unter 20.000, bei den untersuchten
32-Sortier\-netz\-werken wurden jedoch bereits bis zu $2,6 \cdot 10^8$
unterschiedliche Schnittmuster geschätzt.

Der Algorithmus {\sc SN-Markov} legt auf diesem Nachfolger-Graph einen
zufälligen Weg (englisch: \textit{random walk}) zurück. Er startet auf einem
gegebenen Sortiernetzwerk. Um von einem Sortiernetzwerk zum Nächsten zu
gelangen, rekombiniert der Algorithmus das aktuelle Sortiernetzwerk mit sich
selbst und erhält so einen zufälligen Nachfolger. In Pseudocode lässt sich der
Algorithmus wie folgt beschreiben:

\begin{verbatim}
  Netzwerk := Eingabe
  
  für n Iterationen
  {
    Nachfolger := kombiniere (Netzwerk, Netzwerk)
    Netzwerk   := Nachfolger
  }
  
  gib Netzwerk zurück
\end{verbatim}

Die Graphen in Abbildung~\ref{fig:markov-comparators} zeigen die Anzahl der
Komparatoren der Sortiernetzwerke, die \textsc{SN-Markov} auf seinem
zufälligen Pfad durchläuft (rot). Für jeden Graphen wurde der
\textsc{SN-Markov}-Algorithmus auf einem entsprechenden
\emph{Odd-Even-Transpositionsort}-Netzwerk gestartet und hat mindestens
1.000.000~Iterationen durchlaufen. In jedem Schritt wurde die Anzahl der
Komparatoren des Sortiernetzwerks bestimmt und ein entsprechender Zähler
erhöht. In Abbildung~\ref{fig:markov-comparators} ist die resultierende
prozentuale Verteilung zu sehen.

Ebenfalls in die Graphen der Abbildung~\ref{fig:markov-comparators}
eingezeichnet ist eine \emph{Gamma-Verteilung} (grün), die die gemessenen
Daten gut annähert. Die Gamma-Verteilung verwendet einen Offset~$\delta$, der
um Eins kleiner als die kleinste erreichte Komparatorzahl gewählt wurde.
Beispielsweise war die kleinste erreichte Komparatorzahl bei
16-Sortiernetzwerken~63, entsprechend wurde der Offset $\delta = 63 - 1$
gesetzt und die Gamma-Verteilung $g(x - 62)$ eingezeichnet. Die Parameter $k$
und $\theta$, die eine Gamma-Verteilung charakterisieren, wurden mit einem
Fitting-Algorithmus bestimmt. Der konkrete Offset ist als Parameter~$\delta$
unter den Graphen angegeben.

\begin{figure}
  \centering
  \subfigure[12 Leitungen, $k = 8,267$, $\theta = 0,962$, $\delta = 40$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-12-pct.pdf}}
  \subfigure[14 Leitungen, $k = 9,522$, $\theta = 0,867$, $\delta = 52$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-14-pct.pdf}}
  \subfigure[16 Leitungen, $k = 17,939$, $\theta = 1,091$, $\delta = 62$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-16-pct.pdf}}
  \subfigure[18 Leitungen, $k = 10,724$, $\theta = 0,766$, $\delta = 81$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-18-pct.pdf}}
  \caption{Anzahl der Komparatoren von Sortiernetzwerken,
  die von {\sc SN-Markov} durchlaufen wurden (rot). Ebenfalls eingezeichnet
  ist jeweils eine \emph{Gamma-Verteilung} (grün), die eine gute Näherung der
  gemessenen Daten darstellt.}
  \label{fig:markov-comparators}
\end{figure}

\begin{figure}
  \begin{center}
    \includegraphics[viewport=0 0 425 262,width=15cm]{images/comparison-comparators-16.pdf}
  \end{center}
  \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
    10~Schichten. Das Netzwerk wurde von dem Algorithmus
    \textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort}-Netzwerk
    $\operatorname{BS}(22)$ durch das 6-Schnittmuster $\operatorname{MIN}(4,
    10, 17)$, $\operatorname{MAX}(7, 15, 20)$ erzeugt.}
  \label{fig:16-ec-from-bs22}
\end{figure}

Eine Übersicht über die Effizienz der Ergebnisse, die mit dem \emph{bitonen
Mergesort}-Netzwerk als Eingabe für \textsc{SN-Evolution-Cut} erzielt wurden,
gibt Tabelle~\ref{tbl:ec-bs-efficiency}. \textsc{SN-E\-vo\-lu\-tion-Cut} wurde
mit \bs{n}, $n = 9 \dots 24$ und $k = 1 \dots (n-8)$ gestartet. Die Konstanten
der Bewertungsfunktion waren $w_{\mathrm{Basis}} = 0$,
$w_{\mathrm{Komparatoren}} = 1$ und $w_{\mathrm{Schichten}} = n$. In jeder
Zeile befinden sich die Ergebnisse für ein Eingabenetzwerk, in den Spalten
befinden sich die Ergebnisse für eine Leitungszahl $m=n-k$ des
Ausgabenetzwerks. In den Zellen stehen jeweils die Anzahl der Komparatoren des
resultierenden Netzwerks. Die letzte Zeile enthält die Anzahl der
Komparatoren, die \bs{m} benötigt, um die Ergebnisse besser einordnen zu
können.

\begin{table}
  \begin{center}
    \rowcolors{2}{black!5}{}
    \begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
    \hline
       &  8 &  9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 &  20 &  21 &  22 &  23 \\
    \hline
    9  & 21 &    &    &    &    &    &    &    &    &    &    &    &     &     &     &     \\
    10 & 20 & 27 &    &    &    &    &    &    &    &    &    &    &     &     &     &     \\
    11 & 20 & 27 & 32 &    &    &    &    &    &    &    &    &    &     &     &     &     \\
    12 & 20 & 26 & 32 & 39 &    &    &    &    &    &    &    &    &     &     &     &     \\
    13 & 20 & 26 & 32 & 39 & 45 &    &    &    &    &    &    &    &     &     &     &     \\
    14 & 20 & 26 & 32 & 39 & 45 & 53 &    &    &    &    &    &    &     &     &     &     \\
    15 & 20 & 26 & 32 & 39 & 45 & 53 & 61 &    &    &    &    &    &     &     &     &     \\
    16 & 20 & 26 & 32 & 39 & 45 & 53 & 61 & 70 &    &    &    &    &     &     &     &     \\
    17 & 20 & 26 & 32 & 37 & 43 & 50 & 57 & 65 & 74 &    &    &    &     &     &     &     \\
    18 & 20 & 26 & 31 & 37 & 43 & 49 & 56 & 63 & 71 & 82 &    &    &     &     &     &     \\
    19 & 20 & 26 & 31 & 37 & 43 & 48 & 55 & 62 & 70 & 79 & 88 &    &     &     &     &     \\
    20 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 86 & 95 &     &     &     &     \\
    21 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 85 & 94 & 103 &     &     &     \\
    22 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 67 & 77 & 84 & 93 & 102 & 112 &     &     \\
    23 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 &     \\
    24 & 20 & 26 & 32 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 & 133 \\
    \hline
\bs{m} & 24 & 28 & 33 & 39 & 46 & 53 & 61 & 70 & 80 & 85 & 91 & 98 & 106 & 114 & 123 & 133 \\
    \hline
    \end{tabular}
  \end{center}
  \caption{Anzahl der Komparatoren der Ergebnisse von
    \textsc{SN-Evolution-Cut} mit verschiedenen Größen des \emph{bitonen
    Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. Jede Zeile gibt
    die Ergebnisse für ein Eingabenetzwerk \bs{n} an, jede Spalte enthält die
    Ergebnisse für $m=n-k$, die Anzahl der Leitungen des Ausgabenetzwerks.}
  \label{tbl:ec-bs-efficiency}
\end{table}

Zu sehen ist, dass jedes einzelne Ergebnis von \textsc{SN-Evolution-Cut}
mindestens so effizient wie das \emph{bitone Mergesort}-Netzwerk mit der
gleichen Leitungszahl ist. Außerdem enthält jede Spalte (mit Ausnahme von
$m=23$) ein Ergebnis, das effizienter als \bs{m} ist.

In zahlreichen Fällen reicht das Entfernen einer einzigen Leitung aus, um ein
effizientes Ergebnis zu erzielen. Das Ergebnis, das \textsc{SN-Evolution-Cut}
gestartet mit \bs{20} und $k = 1$ erreicht, benötigt mit 95~Komparatoren
3~weniger als \bs{19}.

Bei anderen Größen ergeben erst größere~$k$ effiziente Sortiernetzwerke,
beispielsweise bei $m = 10$: erst für $n = 18$, $k = 8$ wird ein
Sortiernetzwerk mit 31~Komparatoren gefunden.

\begin{figure}
  \centering
  \subfigure[10-Sortiernetzwerk aus 31~Komparatoren in 8~Schichten. Das
  Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{19} erzeugt.]{\input{images/10-ec-from-bs19-fast.tex}\label{fig:10-ec-from-bs19-fast}}
  \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 9~Schichten. Das
  Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{18} erzeugt.]{\input{images/11-ec-from-bs18-fast.tex}\label{fig:11-ec-from-bs18-fast}}
  \subfigure[12-Sortiernetzwerk aus 42~Komparatoren in 9~Schichten. Das
  Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{22} erzeugt.]{\input{images/12-ec-from-bs22-fast.tex}\label{fig:12-ec-from-bs22-fast}}
  \subfigure[19-Sortiernetzwerk aus 92~Komparatoren in 13~Schichten. Das
  Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{37} erzeugt.]{\input{images/19-ec-from-bs37-fast.tex}\label{fig:19-ec-from-bs37-fast}}
  \caption{Für einige Ziel-Leitungszahlen, unter anderem $m \in \{10, 11,
  12, 19\}$, kann der \textsc{SN-Evolution-Cut}-Algorithmus Sortiernetzwerke
  erzeugen, die \emph{schneller} und \emph{effizienter} als \bs{m} sind.}
  \label{fig:ec-bs-fast_networks}
\end{figure}

Bei einigen Werten für die Ziel-Leitungsanzahl $m$ kann der
\textsc{SN-Evolution-Cut}-Algorithmus Ergebnisse erzielen, die schneller als
das entsprechende \emph{bitone Mergesort}-Netzwerk \bs{m} sind. In
Tabelle~\ref{tbl:ec-bs-speed} ist die Anzahl der Schichten, die die Ergebnisse
von \textsc{SN-Evolution-Cut} benötigen, um die Eingabe zu sortieren,
aufgelistet. Jede Zeile enthält die Ergebnisse für ein Eingabenetzwerk \bs{n},
jede Spalte enthält die Ergebnisse für eine Ziel-Leitungszahl $m = n-k$. Die
Zellen enthalten die Anzahl der Schichten des jeweiligen Ergebnis-Netzwerks.

\begin{table}
  \begin{center}
    \rowcolors{2}{black!5}{}
\begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
\hline
    &   8 &   9 &  10 &  11 &  12 &  13 &  14 &  15 &  16 &  17 &  18 &  19 &  20 &  21 &  22 &  23 \\
\hline
  9 &   6 &     &     &     &     &     &     &     &     &     &     &     &     &     &     &     \\
 10 &   6 &   8 &     &     &     &     &     &     &     &     &     &     &     &     &     &     \\
 11 &   6 &   8 &   9 &     &     &     &     &     &     &     &     &     &     &     &     &     \\
 12 &   6 &   8 &   9 &  10 &     &     &     &     &     &     &     &     &     &     &     &     \\
 13 &   6 &   8 &   9 &  10 &  10 &     &     &     &     &     &     &     &     &     &     &     \\
 14 &   6 &   8 &   9 &  10 &  10 &  10 &     &     &     &     &     &     &     &     &     &     \\
 15 &   6 &   8 &   9 &  10 &  10 &  10 &  10 &     &     &     &     &     &     &     &     &     \\
 16 &   6 &   8 &   9 &  10 &  10 &  10 &  10 &  10 &     &     &     &     &     &     &     &     \\
 17 &   6 &   8 &   8 &   9 &  10 &  10 &  10 &  10 &  10 &     &     &     &     &     &     &     \\
 18 &   6 &   8 &   8 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &     &     &     &     &     &     \\
 19 &   6 &   8 &   8 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &     &     &     &     &     \\
 20 &   6 &   8 &   8 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &     &     &     &     \\
 21 &   6 &   8 &   8 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &  14 &     &     &     \\
 22 &   6 &   8 &   8 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &  14 &  15 &     &     \\
 23 &   6 &   8 &   8 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &  14 &  15 &  15 &     \\
 24 &   6 &   8 &   8 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &  14 &  15 &  15 &  15 \\
\hline
\bs{m}& 6 &   8 &   9 &  10 &  10 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &  14 &  15 &  15 &  15 \\
\hline
\end{tabular}
  \end{center}
  \caption{Anzahl der Schichten der Ergebnisse von
    \textsc{SN-Evolution-Cut} mit verschiedenen Größen des \emph{bitonen
    Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. Jede Zeile gibt
    die Ergebnisse für ein Eingabenetzwerk \bs{n} an, jede Spalte enthält die
    Ergebnisse für $m=n-k$, die Anzahl der Leitungen des Ausgabenetzwerks.}
  \label{tbl:ec-bs-speed}
\end{table}

Für die Ziel-Leitungszahlen 9, 10 und 11 wurden Schnittmuster gefunden, die
schnelle Sortiernetzwerke erzeugen. Beispiele für schnelle Sortiernetzwerke,
die mit den von \textsc{SN-Evolution-Cut} ausgegebenen Schnittmustern erzeugt
werden können, sind in Abbildung~\ref{fig:ec-bs-fast_networks} dargestellt.

Bei der Betrachtung der Effizienz wurde festgestellt, dass oft schon das
Entfernen einer einzigen Leitung zu eines effizienteren Ergebnis als \bs{m}
führt. Bei der Geschwindigkeit ist die Anzahl der Leitungen, die entfernt
werden müssen, um schnellere Netzwerke zu erzielen, größer. Um eine Schicht
einzusparen waren bei $m = 10$ und $m = 11$ $k = 6$ Schnitte notwendig. Bei $m
= 9$ war sogar ein 7-Schnittmuster notwendig, um die Anzahl der Schichten zu
reduzieren. Für schnelle \emph{und} effiziente Netzwerke musste $k$ teilweise
noch größer gewählt werden.

Die Effizienz und Geschwindigkeit der Sortiernetzwerke, die von
\textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort}-Netzwerk erzeugten
werden, ist für $m = 19$ und $n = 20 \dots 38$ ($k = 1 \dots 19$) in
Tabelle~\ref{tbl:ec-bs-19} aufgelistet. Erst, wenn $k \geqq 6$ ist, wird im
Vergleich zu \bs{19} eine Schicht eingespart. Für $n = 36$ ($k = 17$) und $n =
37$ ($k = 18$) werden Sortiernetzwerke ausgegeben, die schneller als \bs{19}
und \oes{19} sind und nur einen Komparator mehr als \oes{19} benötigen. Ein
Beispiel für ein solches Netzwerk ist in
Abbildung~\ref{fig:19-ec-from-bs37-fast} zu sehen.

\begin{table}
  \begin{center}
    \rowcolors{2}{black!5}{}
    \begin{tabular}{|r|r|r|}
    \hline
    $n$ & Komp. & Schichten \\
    \hline
          20 & 95 & 14 \\
          21 & 94 & 14 \\
          22 & 93 & 14 \\
          23 & 93 & 14 \\
          24 & 93 & 14 \\
          25 & 96 & 13 \\
          26 & 96 & 13 \\
          27 & 96 & 13 \\
          28 & 96 & 13 \\
          29 & 95 & 13 \\
          30 & 96 & 13 \\
          31 & 95 & 13 \\
          32 & 96 & 13 \\
          33 & 93 & 13 \\
          34 & 94 & 13 \\
          35 & 93 & 13 \\
          \rowcolor{green!10}
          36 & 92 & 13 \\
          \rowcolor{green!10!white!95!black}
          37 & 92 & 13 \\
          38 & 93 & 13 \\
    \hline
    \bs{19}  & 98 & 14 \\
    \oes{19} & 91 & 14 \\
    \hline
    \end{tabular}
  \end{center}
  \caption{Anzahl der Komparatoren und Schichten von 19-Sortiernetzwerken, die
    von \textsc{SN-Evolution-Cut} aus \bs{n}, $n = 20, \dots, 38$ erzeugt
    wurden. Für $k \geqq 6$ ergeben sich Sortiernetzwerke, die schneller als
    \bs{19} sind. Mit $k \in \{14, 16, 19\}$ erreichen die Ergebnisse mit
    13~Schichten die Effizienz der vorherigen
    Ergebnisse mit 14~Schichten, mit $k = 17$ und $k = 18$ wird diese
    Effizienz noch übertroffen. Ein 19-Sortiernetzwerk, das aus \bs{37}
    auf diese Art erzeugt wurde, ist in
    Abbildung~\ref{fig:19-ec-from-bs37-fast} dargestellt.}
  \label{tbl:ec-bs-19}
\end{table}

\textit{Moritz Mühlenthaler} und \textit{Rolf Wanka} zeigen in~\cite{MW2010},
wie ein \emph{bitoner Mischer} $\bm{n = 2^d}$, der nach Batchers Methode
konstruiert wurde, durch systematisches Entfernen von Leitungen in einen
ebenfalls bitonen Mischer mit der Hälfte der Leitungen transformiert werden
kann, so dass dieser alternative Mischer im Vergleich zu $\bm{\frac{n}{2} =
2^{d-1}}$ Komparatoren einspart.

Basierend auf diesen alternativen Mischern geben \textit{Mühlenthaler} und
\textit{Wanka} eine Konstruktionsvorschrift für Sortiernetzwerke an, die
gegenüber \bs{n} ${\frac{1}{4}n(\log n - 1)}$ Komparatoren einspart.
Beispielsweise wird ein 16-Sortiernetzwerk angegeben, das nur 68~Komparatoren
benötigt. Dieses Netzwerk ist in Abbildung~\ref{fig:16-muehlenthaler}
dargestellt.

\begin{figure}
  \begin{center}
    \input{images/16-muehlenthaler.tex}
  \end{center}
  \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in
    10~Schichten. Das Netzwerk wurde 2010 von \textit{Mühlenthaler} und
    \textit{Wanka} aus optimierten bitonen Mischern konstruiert und
    in~\cite{MW2010} veröffentlicht.}
  \label{fig:16-muehlenthaler}
\end{figure}

\begin{figure}
  \begin{center}
    \input{images/16-ec-from-bs32.tex}
  \end{center}
  \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in
    10~Schichten. Das Netzwerk wurde von dem Algorithmus
    \textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort-Netzwerk}
    $\operatorname{BS}(32)$ durch 16~Schnitte erzeugt.}
  \label{fig:16-ec-from-bs32}
\end{figure}

\begin{figure}
  \begin{center}
    \input{images/16-ec-from-bs32-normalized.tex}
  \end{center}
  \caption{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-from-bs32-normalized}
\end{figure}

Startet man {\sc SN-Evolution-Cut} mit dem \emph{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 den
Abbildungen~\ref{fig:16-ec-from-bs32} und~\ref{fig:16-ec-from-bs32-normalized}
zu sehen. Abbildung~\ref{fig:16-ec-from-bs32} zeigt $\operatorname{BS}(32)$
und das Schnittmuster ${\operatorname{MIN}(0, 5, 9, 11, 15, 17, 20, 22, 26,
29, 30)}$, ${\operatorname{MAX}(2, 4, 13, 19, 24)}$, das durch
\textsc{SN-Evolution-Cut} gefunden wurde.
Abbildung~\ref{fig:16-ec-from-bs32-normalized} zeigt das 16-Sortiernetzwerk
nachdem das Schnittmuster angewendet und das Netzwerk normalisiert wurde.
% Eine Ähnlichkeit zu $\operatorname{BS}(32)$ oder $\operatorname{BS}(16)$ ist
% in diesem Netzwerk nicht mehr erkennbar -- insbesondere die ersten Schichten
% des Netzwerks scheinen rein zufällig zu sein.

\begin{figure}
  % 0:MAX 1:MAX 4:MIN 6:MAX 9:MAX 11:MAX 14:MIN 15:MAX 18:MAX 19:MAX 21:MAX
  % 23:MIN 24:MAX 25:MAX 30:MIN 31:MIN 32:MAX 34:MAX 36:MIN 37:MAX 40:MAX
  % 43:MAX 46:MIN 47:MAX 48:MAX 49:MAX 54:MIN 55:MAX 56:MAX 58:MIN 60:MAX
  % 63:MAX
  \begin{center}
    \input{images/32-ec-from-bs64.tex}
  \end{center}
  \caption{Sortiernetzwerk mit 32~Leitungen und 206~Komparatoren in
    15~Schichten. Das Netzwerk wurde von dem Algorithmus
    \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk
    $\operatorname{BS}(64)$ durch 32~Schnitte erzeugt. Das zugehörige
    Schnittmuster ist
    $\operatorname{MIN}(4, 14, 23, 30, 31, 36, 46, 54, 58)$,
    $\operatorname{MAX}(0, 1, 6, 9, 11, 15, 18, 19, 21, 24, 25, 32, 34, 37,
    40, 43, 47, 48, 49, 55, 56, 60, 63)$.}
  \label{fig:32-ec-from-bs64}
\end{figure}

Wenn \textsc{SN-Evolution-Cut} mit dem \bs{64}-Netzwerk und $k = 32$ gestartet
wird, findet der Algorithmus 32-Sortiernetzwerke, die effizienter sind als
32-Sortiernetzwerke, die nach \textit{Mühlenthalers} und \textit{Wankas}
Methode konstruiert werden. Ein von \textsc{SN-Evolution-Cut} aus \bs{64}
generiertes 32-Sortiernetzwerk ist in Abbildung~\ref{fig:32-ec-from-bs64}
dargestellt. Das \emph{bitone Mergesort}-Netzwerk \bs{32} benötigt
240~Komparatoren, ein aus den optimierten Mischern aufgebautes Netzwerk
verbessert die Effizienz auf 208~Komparatoren. Das Ergebnis von
\textsc{SN-Evolution-Cut} kommt mit nur 206~Komparatoren aus. Die
Geschwindigkeit aller genannten Sortiernetzwerke ist mit 15 parallelen
Schritten identisch.

Wenn die Leitungszahl des Eingabenetzwerks keine Zweierpotenz ist, kann
\textsc{SN-Evo\-lu\-tion-Cut} auch 16-Sortiernetzwerke erzeugen, die diese
Effizienz unterbieten. Das geht aus den Daten in
Tabelle~\ref{tbl:ec-bs-efficiency} hervor. Ein 16-Sortiernetzwerk mit
67~Komparatoren, das von \textsc{SN-Evolution-Cut} generiert wurde, ist in
Abbildung~\ref{fig:16-ec-from-bs22} dargestellt.

Leider sind die Schnittmuster, die \textsc{SN-Evolution-Cut} ausgibt, sehr
unregelmäßig. Bisher ist es nicht gelungen eine Konstruktionsanweisung für
gute Schnittmuster anzugeben.

Entscheidend für das Ergebnis eines Schnittmusters scheint beim \emph{bitonen
Mergesort}-Netzwerk die Aufteilung der Minimum- und Maximumschnitte zu sein.
Von Hundert 16-Schnittmustern für $\operatorname{BS}(32)$, die in
Sortiernetzwerken mit 68~Komparatoren in 10~Schichten resultieren, hatten 73
ein Verhältnis von $5/11$, 13 hatten ein Verhältnis von $4/12$ und 14 hatten
ein Verhältnis von $3/13$ Minimum- beziehungsweise Maximumschnitten. Da sich
die Schnittmuster aufgrund der Symmetrie des \emph{bitonen
Mergesort}-Netzwerks leicht invertieren lassen, ist eine Fallunterscheidung --
mehr Minimum- oder mehr Maximumschnitte -- nicht notwendig.

Dass die Sortiernetzwerke, die mit den Schnittmustern von
\textsc{SN-Evolution-Cut} entstehen, keine erkennbare Struktur haben, 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
$k$~Schnitten gestartet, so ist das beste Ergebnis immer das
$\operatorname{OET}(n-k)$-Netzwerk. 

\subsection[Odd-Even-Mergesort-Netzwerk]{Versuche mit dem Odd-Even-Mergesort-Netzwerk}
\label{sect:sn-evolution-cut:oes}

Wird \textsc{SN-Evolution-Cut} mit dem \emph{Odd-Even-Mergesort}-Netzwerk
\oes{n} gestartet, gibt der Algorithmus meist Sortiernetzwerke zurück, die
genauso effizient und schnell wie das entsprechende
\emph{Odd-Even-Mergesort}-Netzwerk \oes{m} sind. Die Effizienz der
Sortiernetzwerke, die mit Schnittmustern von \textsc{SN-Evolution-Cut} aus
\oes{n} entstehen können, zeigt Tabelle~\ref{tbl:ec-oes-efficiency}
tabellarisch.

\begin{table}
  \begin{center}
    \rowcolors{2}{black!5}{}
\begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
\hline
    &   8 &   9 &  10 &  11 &  12 &  13 &  14 &  15 &  16 &  17 &  18 &  19 &  20 &  21 &  22 &  23 \\
\hline
  9 &  19 &     &     &     &     &     &     &     &     &     &     &     &     &     &     &     \\
 10 &  19 &  26 &     &     &     &     &     &     &     &     &     &     &     &     &     &     \\
 11 &  19 &  26 &  31 &     &     &     &     &     &     &     &     &     &     &     &     &     \\
 12 &  19 &  26 &  31 &  37 &     &     &     &     &     &     &     &     &     &     &     &     \\
 13 &  19 &  26 &  31 &  37 &  41 &     &     &     &     &     &     &     &     &     &     &     \\
 14 &  19 &  26 &  31 &  37 &  41 &  48 &     &     &     &     &     &     &     &     &     &     \\
 15 &  19 &  26 &  31 &  37 &  41 &  48 &  53 &     &     &     &     &     &     &     &     &     \\
 16 &  19 &  26 &  31 &  37 &  41 &  48 &  53 &  59 &     &     &     &     &     &     &     &     \\
 17 &  19 &  26 &  31 &  38 &  41 &  48 &  53 &  59 &  63 &     &     &     &     &     &     &     \\
 18 &  19 &  26 &  31 &  38 &  43 &  48 &  53 &  59 &  63 &  74 &     &     &     &     &     &     \\
 19 &  19 &  26 &  31 &  38 &  43 &  48 &  53 &  59 &  63 &  74 &  82 &     &     &     &     &     \\
 20 &  19 &  26 &  31 &  38 &  43 &  48 &  53 &  59 &  63 &  74 &  82 &  91 &     &     &     &     \\
 21 &  19 &  26 &  31 &  38 &  43 &  48 &  53 &  59 &  63 &  74 &  82 &  91 &  97 &     &     &     \\
 22 &  19 &  26 &  31 &  38 &  43 &  48 &  53 &  59 &  63 &  74 &  82 &  91 &  97 & 107 &     &     \\
 23 &  19 &  26 &  31 &  38 &  43 &  48 &  53 &  59 &  63 &  74 &  82 &  91 &  97 & 107 & 114 &     \\
 24 &  19 &  26 &  31 &  38 &  43 &  48 &  53 &  59 &  63 &  74 &  82 &  91 &  97 & 107 & 114 & 122 \\
\hline
\end{tabular}
  \end{center}
  \caption{Anzahl der Komparatoren der Ergebnisse von
    \textsc{SN-Evolution-Cut} mit verschiedenen Größen des
    \emph{Odd-Even-Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$.
    Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \oes{n} an, jede
    Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
    Ausgabenetzwerks.}
  \label{tbl:ec-oes-efficiency}
\end{table}

\begin{figure}
  \centering
  \subfigure[11-Sortiernetzwerk aus 38~Komparatoren in 9~Schichten. Das
  Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \oes{17} erzeugt.]{\input{images/11-ec-from-oes17-fast.tex}\label{fig:11-ec-from-oes17-fast}}
  \subfigure[12-Sortiernetzwerk aus 43~Komparatoren in 9~Schichten. Das
  Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \oes{18} erzeugt.]{\input{images/12-ec-from-oes18-fast.tex}\label{fig:12-ec-from-oes18-fast}}
  \caption{Für einige Ziel-Leitungszahlen, unter anderem $m = 10$ und $m =
  11$, kann der \textsc{SN-Evolution-Cut}-Algorithmus Sortiernetzwerke
  erzeugen, die \emph{schneller} aber weniger \emph{effizient} als \oes{m}
  sind.}
  \label{fig:ec-oes-fast_networks}
\end{figure}

Die Bewertungsfunktion, die \textsc{SN-Evolution-Cut} verwendet, bevorzugt
schnelle Sortiernetzwerke. Dadurch kann es vorkommen, dass ein
$m$-Sortiernetzwerk, das durch ein von \textsc{SN-Evolution-Cut} ausgegebenes
Schnittmuster entsteht, schneller als \oes{m} ist. Diese Geschwindigkeit
war allerdings in allen beobachteten Fällen nur dann möglich, wenn
zusätzliche Komparatoren in Kauf genommen wurden. In den
Tabellen~\ref{tbl:ec-oes-efficiency} und~\ref{tbl:ec-oes-speed} ist dieser
Fall für $m = 11$ und $k \geqq 6$, beziehungsweise $m = 12$ und $k \geqq 6$ zu
beobachten. Die entsprechenden schnellen Sortiernetzwerke sind in
Abbildung~\ref{fig:ec-oes-fast_networks} dargestellt.

Wie beim \emph{bitonen Mergesort}-Netzwerk reicht auch beim
\emph{Odd-Even-Mergesort}-Netzwerk ein einziger Schnitt nicht aus, um die
Geschwindigkeit gegenüber \oes{m} zu verbessern. Bei $m = 11$ und $m = 12$ war
jeweils mindestens ein 6-Schnittmuster notwendig, um eine höhere
Geschwindigkeit zu erreichen.

In Tabelle~\ref{tbl:ec-oes-19} sind die Ergebnisse von
\textsc{SN-Evolution-Cut} für \oes{n}, $n = 20$ und $m = 19$ ($k = 1 \dots
19$) aufgelistet. Mit $k = 10$ wird das erste mal ein schnelles
19-Sortiernetzwerk mit 13~Schichten ausgegeben. Mit $k \geqq 11$ sind die
resultierenden Netzwerke mit 93~Komparatoren effizienter als das Ergebnis mit
$k = 10$, das 95~Komparatoren benötigt. Das Ergebnis, das auf Basis des
\emph{bitonen Mergesort}-Netzwerks erreicht wurde (92~Komparatoren in
13~Schichten, siehe Tabelle~\ref{tbl:ec-bs-19}), wird nicht erreicht.

\begin{table}
  \begin{center}
    \rowcolors{2}{black!5}{}
\begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
\hline
    &   8 &   9 &  10 &  11 &  12 &  13 &  14 &  15 &  16 &  17 &  18 &  19 &  20 &  21 &  22 &  23 \\
\hline
  9 &   6 &     &     &     &     &     &     &     &     &     &     &     &     &     &     &     \\
 10 &   6 &   8 &     &     &     &     &     &     &     &     &     &     &     &     &     &     \\
 11 &   6 &   8 &   9 &     &     &     &     &     &     &     &     &     &     &     &     &     \\
 12 &   6 &   8 &   9 &  10 &     &     &     &     &     &     &     &     &     &     &     &     \\
 13 &   6 &   8 &   9 &  10 &  10 &     &     &     &     &     &     &     &     &     &     &     \\
 14 &   6 &   8 &   9 &  10 &  10 &  10 &     &     &     &     &     &     &     &     &     &     \\
 15 &   6 &   8 &   9 &  10 &  10 &  10 &  10 &     &     &     &     &     &     &     &     &     \\
 16 &   6 &   8 &   9 &  10 &  10 &  10 &  10 &  10 &     &     &     &     &     &     &     &     \\
 17 &   6 &   8 &   9 &   9 &  10 &  10 &  10 &  10 &  10 &     &     &     &     &     &     &     \\
 18 &   6 &   8 &   9 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &     &     &     &     &     &     \\
 19 &   6 &   8 &   9 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &     &     &     &     &     \\
 20 &   6 &   8 &   9 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &     &     &     &     \\
 21 &   6 &   8 &   9 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &  14 &     &     &     \\
 22 &   6 &   8 &   9 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &  14 &  15 &     &     \\
 23 &   6 &   8 &   9 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &  14 &  15 &  15 &     \\
 24 &   6 &   8 &   9 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &  14 &  15 &  15 &  15 \\
\hline
\oes{m}& 6 &  8 &   9 &  10 &  10 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &  14 &  15 &  15 &  15 \\
\hline
\end{tabular}
  \end{center}
  \caption{Anzahl der Schichten der Ergebnisse von
    \textsc{SN-Evolution-Cut} mit verschiedenen Größen des
    \emph{Odd-Even-Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$.
    Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \oes{n} an, jede
    Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
    Ausgabenetzwerks.}
  \label{tbl:ec-oes-speed}
\end{table}

\begin{table}
  \begin{center}
    \rowcolors{2}{black!5}{}
    \begin{tabular}{|r|r|r|}
      \hline
      $n$ & Komp. & Schichten \\
      \hline
      20  &  91 & 14 \\
      21  &  91 & 14 \\
      22  &  91 & 14 \\
      23  &  91 & 14 \\
      24  &  91 & 14 \\
      25  &  91 & 14 \\
      26  &  91 & 14 \\
      27  &  91 & 14 \\
      28  &  91 & 14 \\
      29  &  95 & 13 \\
      30  &  93 & 13 \\
      31  &  93 & 13 \\
      32  &  93 & 13 \\
      33  &  93 & 13 \\
      34  &  93 & 13 \\
      35  &  93 & 13 \\
      36  &  93 & 13 \\
      37  &  93 & 13 \\
      38  &  93 & 13 \\
      \hline
 \bs{19}  &  98 & 14 \\
 \oes{19} &  91 & 14 \\
      \hline
    \end{tabular}
  \end{center}
  \caption{Komparatoren und Schichten von Sortiernetzwerken, die von
    \textsc{SN-Evolution-Cut} mit \oes{n} und $k = n - 19$ ermittelt wurden. Erst mit $k = 10$
    ist es möglich gegenüber \oes{19} eine Schicht einzusparen. Dafür ist die
    Effizienz von 91~Komparatoren nicht mehr erreichbar.}
  \label{tbl:ec-oes-19}
\end{table}

In Abschnitt~\ref{sect:anzahl_schnittmuster} wurde bereits untersucht, wie
viele \emph{unterschiedliche} 16-Schnittmuster die konstruierten
Sortiernetzwerke $\operatorname{OES}(32)$, $\operatorname{BS}(32)$ und
$\operatorname{PS}(32)$ besitzen. Eines der Ergebnisse war, dass von diesen
Sortiernetzwerken das \emph{Odd-Even-Mergesort}-Netzwerk die wenigsten
unterschiedlichen 16-Schnittmuster besitzt -- nur etwa $5,2$~Millionen.
Entsprechend ist es wenig verwunderlich, dass \textsc{SN-Evolution-Cut}
gestartet mit $\operatorname{OES}(32)$ sehr schnell\footnote{Ein
entsprechendes Ergebnis wird meist nach 20.000 bis 100.000 Iterationen
geliefert. Bei dieser Problemgröße erreicht die Implementierung (siehe
Abschnitt~\ref{sect:implementierung}) etwa 20.000 Iterationen pro Sekunde auf
derzeitigen Computern.} ein gutes 16-Schnittmuster findet.

Eines der 16-Schnittmuster für \oes{32}, die ein Sortiernetzwerk erzeugen, das
bezüglich Effizienz und Geschwindigkeit identisch ist zu \oes{16}, ist
$\operatorname{MIN}(1, 6, 11, 14, 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.

\begin{figure}
  \begin{center}
    \input{images/16-ec-from-oes32-cut.tex}
  \end{center}
  \caption{Visualisierung eines 16-Schnittmusters, das auf
  $\operatorname{OES}(32)$ angewendet ein Sortiernetzwerk ergibt, das
  bezüglich Geschwindigkeit und Effizienz identisch zu \oes{16} ist. Das
  resultierende Sortiernetzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32}
  dargestellt.}
  \label{fig:16-ec-from-oes32-cut}
\end{figure}

\begin{figure}
  \begin{center}
    \input{images/16-ec-from-oes32.tex}
  \end{center}
  \caption{16-Sortiernetzwerk mit 63~Komparatoren in 10~Schichten. 
    Das Netzwerk wurde aus dem \emph{Odd-Even-Mergesort}-Netzwerk \oes{32} mit
    einem 16-Schnittmuster erzeugt, das von \textsc{SN-Evolution-Cut}
    berechnet wurde. Das Schnittmuster ist in
    Abbildung~\ref{fig:16-ec-from-oes32-cut} dargestellt.}
  \label{fig:16-ec-from-oes32}
\end{figure}

Bei diesem Schnittmuster fällt auf, dass es für jeweils vier Eingänge (0--3,
4--7, \dots, 28--31) einen Minimum- und einen Maximumschnitt gibt. Aus dieser
Beobachtung kann man das regelmäßige Schnittmuster
\begin{displaymath}
\textit{Eingang}_i = \left\{ \begin{array}{rl}
   \infty & \quad \textrm{falls } i \bmod 4 = 0 \\
  -\infty & \quad \textrm{falls } i \bmod 4 = 3 \\
        ? & \quad \mathrm{sonst}
  \end{array} \right.
\end{displaymath}
ableiten. Es entfernt die Hälfte der Leitungen, vorausgesetzt die Anzahl der
Leitungen ist durch Vier teilbar. Das Schnittmuster erzeugt effiziente
Netzwerke, wenn die Anzahl der Leitungen $n = 2^d$ eine Zweierpotenz ist. Ein
32-Sortiernetzwerk, das mit diesem Schnittmuster aus \oes{64} erzeugt wurde,
ist in Abbildung~\ref{fig:32-ec-from-oes64} zu sehen.

\begin{figure}
  \begin{center}
    \input{images/32-ec-from-oes64.tex}
  \end{center}
  \caption{32-Sortiernetzwerk mit 191~Komparatoren in 15~Schichten. 
    Das Netzwerk wurde mit einem regelmäßigen Schnittmuster aus dem
    \emph{Odd-Even-Mergesort}-Netzwerk \oes{64} erzeugt.}
  \label{fig:32-ec-from-oes64}
\end{figure}

Wenn die Anzahl der Leitungen keine Zweierpotenz ist, erreichen die so
erzeugten Sortiernetzwerke die Effizienz des
\emph{Odd-Even-Mergesort}-Netzwerks nicht. Wendet man das Schnittmuster
beispielsweise auf \oes{24} an, so erhält man ein Sortiernetzwerk mit
43~Komparatoren -- \oes{12} kommt mit 41~Komparatoren aus. Die Geschwindigkeit
beider Sortiernetzwerke ist mit 10~Schichten identisch.

Startet man hingegen den \textsc{SN-Evolution-Cut}-Algorithmus mit \oes{24}
und dem Ziel, ein gutes 12-Schnittmuster zu finden, hängt die Ausgabe von der
verwendeten Gütefunktion ab. Werden effiziente Netzwerke bevorzugt, findet der
Algorithmus Schnittmuster wie $\operatorname{MIN}(6, 7, 8, 9, 16, 17, 20,
22)$, $\operatorname{MAX}(2, 4, 12, 14)$, dessen Ergebnis in
Abbildung~\ref{fig:12-ec-from-oes24-efficient} zu sehen ist. Das resultierende
Sortiernetzwerk besteht aus 41~Komparatoren, die in 10~Schichten angeordnet
werden können. Damit ist das Netzwerk bezüglich Effizienz und Geschwindigkeit
gleichauf mit \oes{12}. Werden hingegen schnelle Sortiernetzwerke bevorzugt,
werden stattdessen Schnittmuster wie $\operatorname{MIN}(6, 7, 11, 12, 15,
16)$, $\operatorname{MAX}(1, 3, 10, 17, 20, 23)$ ausgegeben. Das Ergebnis
dieses Schnittmusters ist in Abbildung~\ref{fig:12-ec-from-oes24-fast} zu
sehen. Das Sortiernetzwerk besteht aus 43~Komparatoren, die in 9~Schichten
angeordnet sind. Das resultierende Netzwerk zwar nicht so effizient wie
\oes{12}, dafür aber schneller als \oes{12} und \bs{12}.

\begin{figure}
  \centering
  \subfigure[Effizientes 12-Sortiernetzwerk aus 41~Komparatoren in
  10~Schichten, das von \textsc{SN-Evolution-Cut} aus dem
  \emph{Odd-Even-Mergesort}-Netzwerk generiert
  wurde.]{\input{images/12-ec-from-oes24-efficient.tex}\label{fig:12-ec-from-oes24-efficient}}
  \subfigure[Schnelles 12-Sortiernetzwerk aus 43~Komparatoren in 9~Schichten,
  das von \textsc{SN-Evolution-Cut} aus dem \emph{Odd-Even-Mergesort}-Netzwerk
  generiert
  wurde.]{\input{images/12-ec-from-oes24-fast.tex}\label{fig:12-ec-from-oes24-fast}}
  \caption{Startet man \textsc{SN-Evolution-Cut} mit \oes{24}, hängt das
  Ergebnis von der Bewertungsfunktion ab.}
  \label{fig:12-ec-from-oes24}
\end{figure}

Das \oes{24}-Sortiernetzwerk ist kein Einzelfall: \textsc{SN-Evolution-Cut}
findet Sortiernetzwerke, die schneller sind als das entsprechende
\emph{Odd-Even-Mergesort}-Netzwerk, unter anderem für das Sortiernetzwerke mit
22, 24, 38, 40, 42, 44 und 46 Leitungen. In der folgenden Tabelle sind einige
schnelle Netzwerke, die von \textsc{SN-Evolution-Cut} generiert werden können,
charakterisiert. Die Eingabe für \textsc{SN-Evolution-Cut} war jeweils das
\emph{Odd-Even-Mergesort}-Netzwerk mit der doppelten Leitungszahl.
\begin{center}
\begin{tabular}{|r|r|r|r|r|}
\hline
Leitungen  & Komparatoren   & Schichten      & Komparatoren & Schichten \\
           & \textsc{SN-EC} & \textsc{SN-EC} &      \oes{n} &   \oes{n} \\
\hline
11 &  38 &  9 &  37 & 10 \\
12 &  43 &  9 &  41 & 10 \\
19 &  93 & 13 &  91 & 14 \\
20 & 101 & 13 &  97 & 14 \\
21 & 108 & 14 & 107 & 15 \\
22 & 116 & 14 & 114 & 15 \\
23 & 125 & 14 & 122 & 15 \\
\hline
\end{tabular}
\end{center}
Abbildung~\ref{fig:23-ec-from-oes46} zeigt beispielhaft ein
23-Sortiernetzwerk, das aus \oes{46} generiert wurde. Bemerkenswert an diesem
Sortiernetzwerk ist insbesondere, dass \textsc{SN-Evolution-Cut} mit der
Eingabe \bs{46} ein besseres Ergebnis liefert als mit der Eingabe \oes{46}. In
beiden Fällen wird ein Sortiernetzwerk zurückgegeben, das im Vergleich zu
\bs{23} beziehungsweise \oes{23} eine Schicht einspart.

\begin{figure}
  \begin{center}
    \input{images/23-ec-from-oes46-fast.tex}
  \end{center}
  \caption{23-Sortiernetzwerk mit 125~Komparatoren in 14~Schichten. 
    Das Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \oes{46} mit dem
    Schnittmuster $\operatorname{MIN}(6, 7, 9, 17, 19, 22, 29, 30, 32, 34, 38,
    44)$, $\operatorname{MAX}(4, 5, 11, 16, 18, 25, 31, 36, 39, 42, 45)$
    erzeugt.}
  \label{fig:23-ec-from-oes46}
\end{figure}

\subsection[Pairwise-Sorting-Netzwerk]{Versuche mit dem Pairwise-Sorting-Netzwerk}

Die Ergebnisse, die \textsc{SN-Evolution-Cut} erzielte, wenn das gegebene
Sortiernetzwerk das \emph{bitone Mergesort}-Netzwerk war
(Abschnitt~\ref{sect:sn-evolution-cut:bs}), waren sehr wirr. Beispielsweise
ist bei dem Netzwerk in Abbildung~\ref{fig:32-ec-from-bs64} nicht ersichtlich,
wie und warum es jede beliebige Eingabe sortiert.

\begin{table}
  \begin{center}
    \rowcolors{2}{black!5}{}
\begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
\hline
    &   8 &   9 &  10 &  11 &  12 &  13 &  14 &  15 &  16 &  17 &  18 &  19 &  20 &  21 &  22 &  23 \\
\hline
  9 &  20 &     &     &     &     &     &     &     &     &     &     &     &     &     &     &     \\
 10 &  20 &  27 &     &     &     &     &     &     &     &     &     &     &     &     &     &     \\
 11 &  20 &  28 &  32 &     &     &     &     &     &     &     &     &     &     &     &     &     \\
 12 &  20 &  28 &  32 &  38 &     &     &     &     &     &     &     &     &     &     &     &     \\
 13 &  19 &  27 &  31 &  37 &  41 &     &     &     &     &     &     &     &     &     &     &     \\
 14 &  19 &  27 &  31 &  37 &  41 &  48 &     &     &     &     &     &     &     &     &     &     \\
 15 &  19 &  27 &  31 &  37 &  41 &  48 &  53 &     &     &     &     &     &     &     &     &     \\
 16 &  19 &  27 &  31 &  37 &  41 &  48 &  53 &  59 &     &     &     &     &     &     &     &     \\
 17 &  21 &  29 &  32 &  39 &  43 &  51 &  57 &  64 &  68 &     &     &     &     &     &     &     \\
 18 &  22 &  29 &  32 &  39 &  43 &  52 &  58 &  65 &  69 &  80 &     &     &     &     &     &     \\
 19 &  23 &  29 &  32 &  39 &  43 &  52 &  58 &  65 &  69 &  80 &  88 &     &     &     &     &     \\
 20 &  23 &  29 &  32 &  39 &  43 &  52 &  58 &  65 &  69 &  80 &  88 &  97 &     &     &     &     \\
 21 &  20 &  30 &  34 &  38 &  44 &  51 &  57 &  64 &  74 &  82 &  87 &  96 & 102 &     &     &     \\
 22 &  20 &  30 &  34 &  38 &  46 &  51 &  57 &  64 &  72 &  82 &  89 &  96 & 102 & 112 &     &     \\
 23 &  20 &  27 &  34 &  38 &  42 &  51 &  57 &  66 &  72 &  83 &  89 &  97 & 102 & 112 & 119 &     \\
 24 &  20 &  27 &  34 &  38 &  42 &  51 &  57 &  64 &  72 &  82 &  89 &  96 & 102 & 112 & 119 & 127 \\
\hline
\ps{m}&19 &  27 &  32 &  38 &  42 &  48 &  53 &  59 &  63 &  79 &  88 &  97 & 103 & 112 & 119 & 127 \\
\hline
\end{tabular}
  \end{center}
  \caption{Anzahl der Komparatoren der Ergebnisse von
    \textsc{SN-Evolution-Cut} mit verschiedenen Größen des
    \emph{Pairwise-Sorting}-Netzwerks und unterschiedlichen Werten für~$k$.
    Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \ps{n} an, jede
    Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
    Ausgabenetzwerks.}
  \label{tbl:ec-ps-speed}
\end{table}

Das \emph{Pairwise-Sorting-Netzwerk} $\operatorname{PS}(n)$, das \textit{Ian
Parberry} in seiner Arbeit „The Pairwise Sorting Network“ \cite{P1992}
definiert, verhält sich anders. Startet man \textsc{SN-Evolution-Cut} mit
$\operatorname{PS}(32)$ und der Vorgabe, 16~Leitungen zu entfernen, erhält man
ein Sortiernetzwerk, das die gleiche Anzahl 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.

\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}

Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even}-Mischer nicht
einsetzt und auch nicht auf einem Mischer basiert, ist das
\emph{Odd-Even-Merge}-Netzwerk $\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 Sortiernetzwerke, die
strukturell sehr ähnlich zu $\operatorname{PS}(8)$ sind -- lediglich die
Schichten~1 und~2 sowie 4~und~5 sind vertauscht.

\begin{figure}
  \begin{center}
    \input{images/32-pairwise-cut-16-pairwise.tex}
  \end{center}
  \caption{Das \ps{32}-Netzwerk mit 8~Maximum- und 8~Minimumschnitten. Gut zu
    sehen sind die verbleibenden Komparatoren, die das \ps{16}-Netzwerk
    bilden.}
  \label{fig:ps16-from-ps32}
\end{figure}

Für das \emph{Pairwise-Sorting-Netzwerk} ist es vergleichsweise einfach
regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk ein kleineres
schnelles und effizientes Sortiernetzwerk erzeugen. Beispielsweise führt das
einfache Schnittmuster
\begin{displaymath}
\textit{Eingang}_i = \left\{ \begin{array}{rl}
  -\infty & \quad \textrm{falls } i < \frac{1}{4} n \\
   \infty & \quad \textrm{falls } i \geqq \frac{3}{4} n \\
        ? & \quad \mathrm{sonst}
  \end{array} \right.
\end{displaymath}
für $\operatorname{PS}\left(n = 2^d\right)$ zum Sortiernetzwerk
$\operatorname{PS}\left(\frac{1}{2}n\right)$. Die Art und Weise, mit der
dieses Schnittmuster Komparatoren eliminiert und welche Komparatoren das
verbleibende Netzwerk ausmachen, ist in Abbildung~\ref{fig:ps16-from-ps32}
dargestellt. Die matt blauen und roten Leitungen und Komparatoren sind
diejenigen, die Aufgrund eines Minimums oder eines Maximums im resultierenden
Netzwerk nicht mehr enthalten sind. Da die Minima und Maxima bereits auf den
„richtigen“ Leitungen angelegt werden, müssen keine Leitungen vertauscht
werden und das Ergebnis ist bereits normalisiert. Daher ist das resultierende
Netzwerk in schwarz gut zu erkennen.

\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}

Ein Spezialfall ergibt sich, wenn man \textsc{SN-Evolution-Cut} auf
$\operatorname{PS}(16)$ anwendet: In diesem Fall kann man durch ein
8-Schnittmuster das \emph{Odd-Even-Mergesort}-Netzwerk \oes{8} erhalten. Für
größere Sortiernetzwerke ist dies hingegen nicht mehr möglich, beispielsweise
kann $\operatorname{PS}(32)$ nicht durch ein 16-Schnittmuster in \oes{16}
konvertiert werden. Die Verwandtschaft von $\operatorname{PS}(n)$ und \oes{n}
untersucht \textit{Moritz Mühlenthaler} ausführlich in~\cite{M2009}.

\newpage
\section{Fazit und Ausblick}

Mit dem Entfernen von Leitungen aus bekannten Sortiernetzwerken lassen sich
interessante Ergebnisse erzielen. Dies zeigte \textit{Moritz Mühlenthaler}
bereits in~\cite{M2009}. Die in dieser Arbeit vorgestellten Methoden und
Resultate machen deutlich, dass sich mit diesem Verfahren noch weitere
interessante Beobachtungen machen lassen.

Das \emph{Odd-Even-Mergesort}-Netzwerk wird sowohl von \textsc{SN-Evolution},
\textsc{SN-Evolution-Cut} und \textsc{SN-Markov} erreicht. Wenn die Anzahl der
Leitungen keine Zweierpotenz ist, kann gegebenenfalls ein schnelleres
Sortiernetzwerk erzeugt werden. Einige Beispiele hierfür wurden in
Abschnitt~\ref{sect:sn-evolution-cut:oes} aufgezeigt.

Das \emph{bitone Mergesort}-Netzwerk kann in Bezug auf Effizienz von den
vorgestellten Algorithmen übertroffen werden. Der Algorithmus
\textsc{SN-Evolution-Cut} kann das Ergebnis von \textit{Mühlenthaler} und
\textit{Wanka} (\cite{MW2010}) für ein 16-Sortiernetzwerk reproduzieren und
für ein 32-Sortiernetzwerk sogar noch übertreffen. Der
\textsc{SN-Evolution}-Algorithmus fand 16-Sortiernetzwerke, die gegenüber dem
Ergebnis von \textsc{SN-Evolution-Cut} beziehungsweise~\cite{MW2010} einen
weiteren Komparator einsparen.

Leider weisen die Sortiernetzwerke, die von den angegebenen Algorithmen
zurückgegeben werden, keine Struktur auf, die sich zur Angabe einer
Konstruktionsanweisung eigenen würde. Für das \emph{Pairwise-Sorting}- und das
\emph{Odd-Even-Mergesort}-Netzwerk mit Zweierpotenzen als Leitungszahl wurden
regelmäßige Schnittmuster angegeben. Diese ergeben Sortiernetzwerke, die so
schnell und effizient sind wie die vergleichbaren \oes{n} und \ps{n}
Netzwerke.

Die Anzahl der \emph{unterschiedlichen} Schnitte von verschiedenen
Sortiernetzwerken wurde experimentell bestimmt und gezeigt, dass es deutlich
weniger \emph{unterschiedliche} als \emph{mögliche} Schnittmuster gibt. Das
bedeutet im Umkehrschluss, dass die gewonnenen Sortiernetzwerke mit mehreren
Schnittmustern erreicht werden können.

Die Möglichkeiten der Optimierung von Sortiernetzwerken mit
\emph{Evolutionären Algorithmen} 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{Ausblick: Das \textit{Pairwise-Sorting}-Netzwerk und \textsc{SN-Evolution}}

Die aktuelle Implementierung von \textsc{SN-Evolution}
(Abschnitte~\ref{sect:sn-evolution}
beziehungsweise~\ref{sect:implementierung}) 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
Ausgabe sorgen. Anstelle von $\ps{\frac{n}{2}}$ können beliebige
Sortiernetzwerke mit $\frac{n}{2}$~Leitungen verwendet werden.

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{unterschiedliche} Schnittmuster gibt
(Abschnitt~\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{Ausblick: 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{H1990} beschreibt, könnte man versuchen, die Algorithmen
\textsc{SN-Evolution} und \textsc{SN-Evolution-Cut} 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ächsten 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}
\label{sect:implementierung}

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{42} zu erzeugen, kann folgendes Kommando verwendet
werden:
\begin{verbatim}
  $ sn-bitonicsort 42 | sn-normalize >sn-42
\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 des \emph{Odd-Even-Mergesort}-, \emph{bitonen
Mergesort}- und \emph{Pairwise-Sorting}-Netzwerks, das Normalisieren von
Sortiernetzwerken, Anwendung von Schnittmustern auf Sortiernetzwerke und
Anwendung eines Komparatornetzwerks auf eine Eingabepermutation. Das
Darstellen von Sortiernetzwerken wird ebenfalls angeboten, beispielsweise
wurden die Sortiernetzwerke in dieser Arbeit mit dem Kommando \texttt{sn-tex}
visualisiert.

\textit{libsortnetwork} kann unter der Web-Adresse
\url{http://octo.it/libsortnetwork/} unentgeltlich heruntergeladen werden.

\newpage
\bibliography{references}
\bibliographystyle{plain}

%\listoffigures

\end{document}

% vim: set shiftwidth=2 softtabstop=2 tabstop=8 fdm=marker tw=78 spelllang=de :