Sortier- und Mergenetzwerke konsequenter benannt.

[diplomarbeit.git] / diplomarbeit.tex

\documentclass[a4paper,10pt]{article}
\usepackage[utf8]{inputenc}
\usepackage{ngerman}
\usepackage{fancyhdr}
\usepackage{geometry}
\usepackage{amsmath, bbm}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{listings}
\usepackage{graphicx}
\usepackage{url}
%\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}

\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{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 werden eingeführt und einige bekannte Konstruktionen werden
vorgestellt (Off-Even-Transposition, Bitonic-Merge, Odd-Even-Merge, Pairwise).
Transformationsmöglichkeiten für Sortiernetzwerke werden besprochen.
Evolutionäre Algorithmen werden beschrieben und ein evolutionärer
Algorithmus für die Optimierung von Sortiernetzwerken wird angegeben.
Die mindestens von diesem Algorithmus erreichte Güte wird angegeben und die
Transformation zu einer Markov-Kette wird gezeigt. {\em Natürlich: So fern ich
das hinbekomme bzw. Recht behalte.}
\end{abstract}
\newpage

\tableofcontents
\newpage

\section{Motivation und Einleitung}

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

\begin{itemize}
\item Sortiernetzwerke sind toll, weil $\ldots$
\item Sortiernetzwerke sind einfach erklärt, aber trotzdem kompliziert.
\item Bisher noch kein evolutionärer Algorithmus zur automatischen
  Optimierung von Sortiernetzwerken bekannt. \textit{(Glaube ich zumindest.)}
\end{itemize}

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

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

{\em Komparatoren} sind die Bausteine, die {\em Sortiernetzwerken} zugrunde
liegen. Sie haben zwei Eingänge über die sie zwei Zahlen erhalten können.
Ausserdem besitzt ein {\em Komparator} zwei Ausgänge, die im Gegensatz zu den
Eingängen unterscheidbar sind: Die grö"sere der beiden Zahlen wird immer auf
dem einen, die kleinere der beiden Zahlen immer auf dem anderen Ausgang
ausgegeben.

Wenn man nun mehrere {\em Komparatoren} miteinander kombiniert, also die
Ausgänge von Komparatoren mit dem Eingängen anderer Komparatoren verbindet,
erhält man ein {\em Komparatornetzwerk}.

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

Abbildung~\ref{fig:einfaches_komparatornetzwerk} zeigt ein einfaches
Komparatornetzwerk aus fünf Komparatoren in der üblichen Darstellungsweise:
Die horizontalen Linien stellen Leitungen von den Eingängen auf der linken
Seite zu den Ausgängen auf er rechten Seite dar. Die vertikalen Pfeile
symbolisieren die Komparatoren, die die Werte "`auf den Leitungen"'
vergleichen und ggf. vertauschen. 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.

Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
gleichzeitig angewandt werden. Das Beispiel in
Abbildung~\ref{fig:einfaches_komparatornetzwerk} verwendet diesen Umstand und
vergleicht in einem ersten Schritt 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
Komparatornetwerks. Die \emph{Verzögerung} 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.

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

Zu beweisen, dass ein gegebenes Komparatornetzwerk die Sortiereigenschaft
{\em nicht} hat, ist mit einem gegebenen Gegenbeispiel einfach möglich.
Dieses Gegenbeispiel zu finden ist allerdings aufwendig.

\todo{Wie findet man die Gegenbeispiele? Die {\em Entscheidung}, ob ein
Netzwerk sortiert, ist doch NP-vollständig, also müsste doch das Finden eines
Gegenbeispiels im Allgemeinen auch exponentialle Laufzeit haben..?}
\todo{Wenn die {\em Entscheidung}, ob ein Netzwerk sortiert, NP-vollständig
ist, müsse man dann nicht einen Zeugen für die Sortiereigenschaft angeben
können?}

\todo{$0-1$-Prinzip}

Um zu überprüfen, ob ein gegebenes Komparatornetzwerk die Sortiereigenschaft
besetzt, müssen nicht alle $n!$ Permutationen von $n$~unterschiedlichen Zahlen
ausprobieren. Stattdessen reicht es zu überprüfen, dass das Netzwerk alle
$2^n$~0-1-Folgen sortiert.

Sortiernetzwerke:
\begin{itemize}
\item Ein Komparator-Netzwerk ist $\ldots$
\item Ein Komparator-Netzwerk ist ein Sortiernetzwerk, wenn $\ldots$
\item Die Frage nach der Sortiereigenschaft ist NP-vollständig.
\end{itemize}

\subsubsection{Evolutionäre Algorithmen}

Viele {\em kombinatorische Optimierungsprobleme} sind schwer zu lösen -- die
entsprechenden Entscheidungsprobleme liegen oft in der Komplexitätsklasse
$NP$, sind also mit bekannten Verfahren nicht effizient exakt lösbar. Sollte
sich herausstellen, dass diese Probleme nicht in der Komplexitätsklasse $P$
liegen, wäre eine Konsequenz, dass es effiziente exakte Algorithmen für diese
Probleme nicht geben kann. Falls sich hingegen herausstellt, dass diese
Probleme in der Komplexitätsklasse~$P$ liegen, wird es mit großer
Wahrscheinlichkeit noch einige Zeit dauern bis auch Algorithmen mit
praktikablen Zeitkonstanten gefunden werden.

Aus diesem Grund besteht die Notwendigkeit einen Kompromiss einzugehen: Statt
die bzw. eine der {\em optimalen} Lösungen als einzige Ausgabe des Algorithmus
zuzulassen, wird eine "`möglichst gute"' Lösung ausgegeben. Viele dieser
Optimierungsalgorithmen orientieren sich an Vorgängen in der Natur,
beispielsweise immitieren 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 es, bestehende 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 häufig
als {\em Individuum} 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
integriert wird. Die Wahrscheinlichkeiten, beispielsweise bei der {\em
Selektion}, sind dabei nicht zwangsläufig gleichverteilt -- üblicherweise
werden bessere Lösungen bevorzugt. Zur Bewertung die 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. Zum anderen muss eine
Methode für die Rekombination existieren. Das insbesondere dann problematisch
wenn {\em Nebenbedingungen} eingehalten werden müssen.

\begin{itemize}
\item Unter einem "`Evolutionären Algorithmus"' versteht man $\ldots$
\item Da die Sortiereigenschaft zu überprüfen NP-schwer ist, ist die
Mutation \textit{(vermutlich)} nicht (effizient) möglich.
\end{itemize}

\section{Bekannte konstruktive Sortiernetzwerke}

Übersicht über bekannte konstruktive Sortiernetzwerke.

\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 acht Eingängen.}
  \label{fig:odd-even-transposition-08}
\end{figure}

Dass das Odd-Even-Transporitionsort-Netzwerk tatsächlich jede beliegibe
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. Beim
Odd-Even-Transporitionsort-Netzwerk mit drei Eingängen,
$\operatorname{OET}(3)$, ist die Ausgabe folglich sortiert.

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)$.

Das Odd-Even-Transporitionsort-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)} = \mathcal{O}(n^2)$~Komparatoren, die in $n$~Schichten
angeordnet sind. Andere Sortiernetzwerke benötigen deutlich weniger
Komparatoren, beispielsweise $\mathcal{O}(n (\log n)^2)$, die in weniger
Schichten, zum Beispiel $\mathcal{O}(\log n)$, angeordnet sind.

Das Interessante am OET-Netzwerk ist seine einfache Konstruktion. Einige der
folgenden Algorithmen benötigen ein (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.

\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-Transporitionsort-Netzwerk -- sowohl in Bezug auf die Anzahl der
Komparatoren als auch bezüglich 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{„bitoner 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 eine Zweierpotenz ist,
$\operatorname{BS}(n = 2^t)$.

\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 Listen 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}) bzw. 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 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.

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 bitonen 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 Foglen. 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) = \mathcal{O}\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,
$\operatorname{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{$\operatorname{BS}(8)$, Batchers {\em bitones Mergesort-Netzwerk}
  für acht Eingänge. Markiert sind die beiden Instanzen von
  $\operatorname{BS}(4)$ (rot), die beiden bitonen
  Mischer~$\operatorname{BM}(4)$ (blau) und die Komparatoren, die im letzten
  rekursiven Schritt hinzugefügt wurden (grün).}
  \label{fig:bitonic-08}
\end{figure}

Das konkrete Netzwerk~$\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} $\operatorname{BS}(8)$ besteht aus
$\frac{1}{4} n \log(n) \log(n+1) = \mathcal{O}\left(n (log (n))^2\right)$
Komparatoren, die in $\frac{1}{2} \log(n) \log(n+1) = \mathcal{O}(\log(n))$
Schichten angeordnet sind.

%\begin{figure}
%\begin{center}
%\includegraphics[viewport=115 491 372 782,width=7.5cm]{images/sn-rekursiver-aufbau.pdf}
%\end{center}
%\caption{Rekursiver Aufbau von $S(n)$: Es besteht aus zwei Instanzen von
%$S(n/2)$ und dem Mischer $M(n)$.}
%\label{fig:bms_rekursiver_aufbau}
%\end{figure}

\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{K.~Batcher} gefunden worden und wird rekursiv durch einen Mischer
definiert.

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

Der \emph{Odd-Even-Mischer} $\operatorname{OEM}(n,m)$ ist ein
Komperatornetzwerk, dass 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. Allerdings benötigt der \emph{Odd-Even-Mischer} unter
Umständen mehr Schichten als der \emph{bitone Mischer}.\footnote{Knuth,
“Bitonic Sorting”, Seite~230}

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 {\em Odd-Even} Mischers. Im Vergleich zum
  bitonen Mischer für Acht kommt dieses Schema mit einem Komparator weniger
  aus. Der Effekt wird duch den rekursiven Aufbau noch 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}}$ bzw. die
ungeraden Folgen $U_{\textrm{ungerade}}$ und $V_{\textrm{ungerade}}$ werden
rekursiv von kleineren {\em 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 {\em
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}

Dass die resultierende Folge sortiert ist, lässt sich mit dem
{\em 0-1-Prinzip} zeigen:
Da $U$ und $V$ sortiert sind, ist die Anzahl der Nullen in den geraden
Teilfolgen, $U_{\textrm{gerade}}$ bzw. $V_{\textrm{gerade}}$, größer oder
gleich der Anzahl der Nullen in den ungeraden Teilfolgen
$U_{\textrm{ungerade}}$ bzw. $V_{\textrm{ungerade}}$ --~die Einsen verhalten
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ählt als
$W_{\textrm{ungerade}}$, muss genau eine Vertauschung stattfinden, um die
Ausgabe zu sortieren. Diese wird von den Komparatoren, die benachbarte
Leitungen miteinander vergleichen, ausgeführt. 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 {\em 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 $\mathcal{O}\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, ist Gemäß der rekursiven Definition in
Abhängigkeit der Länge der Eingabefolgen, $n$ und $m$:
\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 $\mathcal{O}(N \log (N))$ enthalten ist.

Für den wichtigen Spezialfall, dass $n = m = 2^{t-1}$, 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^{t-1}, n = 2^{t-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^t)$
benötigt werden.

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

Das \emph{Odd-Even-Mergesort-Netzwerk} $\operatorname{OES}(n)$ besteht, --~wie
das \emph{bitonen Mergesort-Netzwerk}~-- rekursiv aus kleineren Varianten von
sich selbst und einem abschließenden \emph{Odd-Even-Mischer}. Die
effizientesten Sortiernetzwerke in Bezuf auf Komparator- und Schichtzahl
entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht
$\operatorname{OES}(n)$ aus
$\operatorname{OES}\left(\left\lceil\frac{n}{2}\right\rceil\right)$,
$\operatorname{OES}\left(\left\lfloor\frac{n}{2}\right\rfloor\right)$
und $\operatorname{OEM}\left(\left\lceil\frac{n}{2}\right\rceil,
\left\lfloor\frac{n}{2}\right\rfloor\right)$. 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 acht 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 konkrete Sortiernetzwerk
$\operatorname{OES}(8)$ zu sehen. Rot markiert sind die beiden rekursiven
Instanzen $\operatorname{OES}(4)$. Die blauen und der grüne Block stellen den
\emph{Odd-Even-Mischer} für acht Leitungen dar: Die beiden blauen Blöcke sind
die rekursiven Instanzen von $\operatorname{OEM}(4)$, der grüne Block markiert
die Komparatoren, die in ersten Rekursionsschritt hinzugefügt werden.

Im Allgemeinen ist die Anzahl der Komparatoren, die vom
\emph{Odd-Even-Mergesort-Netzwerk} 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}
Eine geschlossene Form dieser Formel ist schon alleine deshalb schwierig, weil
sie für $K(n,m)$ schwierig anzugeben ist. Es ist allerdings bekannt, dass
$k(n)$ in $\mathcal{O}\left(n \left(\log (n)\right)^2\right)$ enthalten ist.

Für den wichtigen Spezialfall, dass $n = 2^t$ eine Zweierpotenz ist, kann die
Anzahl der Komparatoren wieder explizit angegeben werden. \textit{K.~Batcher}
zeigt in seiner Arbeit\footnote{\todo{Referenz!}}, dass in diesem Fall
\begin{displaymath}
  k(n = 2^t) = \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}

\section{Transformation von Sortiernetzwerken}

\subsection{Komprimieren}

\todo{Aus theoretischer Sicht eigentlich eine Trivialität. Rausschmeißen?}

Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
gleichzeitig ausgewertet werden, wie bereits in
Abschnitt~\ref{sect:einleitung_sortiernetzwerke} beschrieben. Unter
\emph{Komprimieren} wird eine (Neu-)Gruppierung in die kleinstmögliche Anzahl
von \emph{Schichten} verstanden.

Diese Anzahl ist insbesondere beim automatisierten Bewerten von
Komparatornetzwerken interessant. \dots

\subsection{Normalisieren}

\begin{figure}
  \centering
  \subfigure[$S(8)$ (nach Konstruktion)]{\input{images/batcher-8-nonstd.tex}\label{fig:bitonic-nonstd}}
  \subfigure[$S(8)$ (normalisiert)]{\input{images/batcher-8-std.tex}\label{fig:bitonic-std}}
  \caption{Jedes Sortiernetzwerk kann in ein Standard-Sortiernetzwerk
  transformiert werden. Gezeigt ist das bitone Sortiernetzwerk nach der
  intuitiven Konstruktion und die normalisierte Variante.}
  \label{fig:beispiel_normalisieren}
\end{figure}

Ein \emph{Standard-Sortiernetzwerk} oder \emph{normalisiertes Sortiernetzwerk}
ist ein Sortiernetzwerk, dessen Komparatoren alle in die selbe Richtung
zeigen. Jedes Sortiernetzwerk kann in eine normaliesierte Variante
transformiert werden. Dazu gibt beispielsweise \emph{Knuth} (\todo{Verweis})
einen Algorithmus an.

Abbildung~\ref{fig:beispiel_normalisieren} zeigt das das
bitone Sortiernetzwerk in zwei Varianten. Abbildung~\ref{fig:bitonic-nonstd}
zeigt das Netzwerk nach der Konstruktionsvorschrift, siehe auch
Abbildung~\ref{fig:bitonic-merge-normal}: In den ersten drei Schichten werden
die unter und die obere Hälfte gegenläufig sortiert. Das heißt dass nach drei
Schritten die eine Hälfte auf- und die andere Hälfte absteigend sortiert ist. 
In den Schichten~4 bis~6 folgt der bitone Mischer entsprechend der rekursiven
Definition.

In Abbildung~\ref{fig:bitonic-std} ist die normalisierte Version des bitonen
Mergesort-Netzwerks zu sehen. Alle Komparatoren zeigen hier in die gleiche
Richtung. 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.

Wir haben diese Technik 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 man die Ausgabe von zwei \emph{bitonen
Mergesort-Netzwerken} $\operatorname{BS}(8)$ mit je acht Leitungen mit dem
\emph{Odd-Even-Merge} $\operatorname{OEM(8,8)}$ zu einer sortierten
Gesamtfolge zusammenfügen. Das resultierende Sortiernetzwerk besitzt
73~Komparatoren (zum Vergleich: $\operatorname{BS}(16)$ benötigt
80~Komparatoren, $\operatorname{OES}(16)$ nur 63).

Verbesserungen in der Anzahl der benötigten Komparatoren beziehungsweise 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 in
neun Schichten angeordnet sind. Es sind allerdings Sortiernetzwerke mit neun
Eingängen bekannt, die lediglich 25~Komparatoren in sieben Schichten
benötigen. Kombiniert man zwei dieser Netzwerke mit dem
\emph{Odd-Even-Mischer} erhält man ein Sortiernetzwerk mit 18~Eingängen, das
80~Komparatoren in 11~Schichten benötigt -- $\operatorname{OES}(18)$ benötigt
82~Komparatoren in 13~Schichten. Damit ist das resultierende Netzwerk so
schnell wie das Sortiernetzwerk mit 18~Eingängen, das \textit{Baddar} und
\textit{Batcher} in ihrer Arbeit „An 11-Step Sorting Network for 18~Elements“
vorstellen, benötigt aber 6~Komparatoren weniger.

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

Das Zusammenfassen von zwei Sortiernetzwerken durch Hintereinanderausführung
ist nicht sinnvoll: Da die Ausgabe des ersten Sortiernetzwerks bereits
sortiert ist, ist das zweite Sortiernetzwerk überflüssig. Eine
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.

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

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

Im vorherigen Abschnitt haben wir gesehen, 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. Das heißt, dass wir wieder ein
Sortiernetzwerk mit $n$~Eingängen erhalten müssen.

Man kann ein gegebenes Sortiernetzwerk mit $n$~Eingängen auf ein
Sortiernetzwerk mit ${n-1}$~Leitungen verkleinern, indem man eine Leitung
„eliminiert“. Dazu nehmen wir an, dass das Minimum oder das Maximum an einem
bestimmten Eingang anliegt. Der Weg, den das Minimum beziehungsweise das Maxim
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 gewechselt, 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 {\em Odd-Even-Transpositionsort-Netzwerk}.

\begin{figure}
  \centering
  \subfigure[foo]{\input{images/oe-transposition-cut0.tex}\label{fig:oe-transposition-cut0}}
  \subfigure[bar]{\input{images/oe-transposition-cut1.tex}\label{fig:oe-transposition-cut1}}
  \subfigure[baz]{\input{images/oe-transposition-cut2.tex}\label{fig:oe-transposition-cut2}}
  \subfigure[qux]{\input{images/oe-transposition-cut3.tex}\label{fig:oe-transposition-cut3}}
  \caption{Eine Leitung wird aus dem
  \emph{Odd-Even-Transpositionsort}-Netzwerk $\operatorname{OET}(8)$ entfernt:
  Auf der rot markierten Leitung wird $\infty$ angelegt. Da der Wert bei jedem
  Komparator am unteren Ende herauskommt, ist der Pfad fest vorgegeben. Da die
  restlichen Werte trotzdem noch richtig sortiert werden müssen, kann dieser
  Pfad herausgetrennt werden. In der letzten Abbildung ist
  $\operatorname{OET}(7)$ markiert.}
  \label{fig:oe-transposition-cut}
\end{figure}

Im nächsten Schritt werden alle beteiligten Komparatoren gelöscht bzw.
ersetzt: Komparatoren, die {\em nicht} zu einem Wechsel der Leitung geführt
haben, werden ersatzlos gelöscht. Diese Komparatoren sind in
Abbildung~\ref{fig:oe-transposition-cut0} grün markiert. Die Komparatoren, die
zum Wechsel der Leitung geführt haben, werden durch sich kreuzende Leitungen
ersetzt. Das Resultat ist eine Leitung, auf der das Minimum beziehungsweise
das Maximum angenommen wird, die an unterster oder oberster Stelle endet und
auf 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 immernoch sortiert werden: Wir haben lediglich die Position
des Minimums oder des Maximums angenommen. Ein Sortiernetzwerk muss die
Eingabe sortieren, egal auf welcher Leitung das Minimum~/ das Maximum liegt.
Wir haben lediglich angefangen, das Sortiernetzwerk unter diese Annahme
auszuwerten -- über die verbleibenden Eingänge haben wir keine Aussage
getroffen. Entsprechend müssen die verbleibenden Ausgänge eine sortierte Liste
mit $(n-1)$~Elementen darstellen.

Wenn wir die Minimum- beziehungsweise Maximum-Leitung entfernen
(Abbildung~\ref{fig:oe-transposition-cut2}), bleibt das Sortiernetzwerk für
$(n-1)$~Leitungen übrig. Je nachdem, ob auf einer Leitung ein Minimum oder ein
Maximum angenommen wird, bezeichnen wir das eliminieren einer Leitung als
\emph{Minimum-Schnitt} beziehungsweise \emph{Maximum-Schnitt}.

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

Der Eliminierungsschritt kann iterativ angewandt werden, um aus einem
Sortiernetzwerk mit $n$~Ein\-gängen Sortiernetzwerke mit $n-1$, $n-2$,
$n-3$,~\dots Eingängen zu erzeugen. Insbesondere können wir auf diese Art und
Weise einen Sortiernetzwerk mit $2n$~Eingängen wieder auf ein Sortiernetzwerk
mit $n$~Eingängen reduzieren.

\subsubsection{Der \textsc{SN-Evolution-Cut}-Algorithmus}

Bei einem Sortiernetzwerk mit $n$~Eingängen gibt es $2n$~Möglichkeiten eine
Leitung zu entfernen: Auf jeder der $n$~Leitungen kann sowohl das Minimum als
auch das Maximum angenommen werden. Wendet man das Verfahren iterativ an, um
ein $n$-Sortiernetzwerk auf ein $m$-Sortiernetzwerk zu reduzieren, ergeben
sich insgesamt
\begin{displaymath}
  \prod_{i=n}^{m+1} 2i = 2^{n-m} \frac{n!}{m!}
  \quad (n > m)
\end{displaymath}
Möglichkeiten. Diese Möglichkeiten sind nicht alle unterschiedlich. Legt man
beispielsweise das Minimum auf die unterste Leitung und das Maximum auf die
oberste Leitung eines Standard-Sortiernetzwerks, führen beide Reihenfolgen zum
selben Ergebnis.

\textit{Moritz Mühlenthaler} zeigt in seiner Arbeit (\todo{Referenz}), dass
es möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise
Maximum vorzubelegen. Dadurch wird die Anzahl der möglichen Schnitte
reduziert, die Menge der erreichbaren Sortiernetzwerke bleibt aber
unverändert. Die Anzahl der möglichen „Schnittmuster“ setzt sich zusammen aus
der Anzahl von Möglichkeiten, $n-m$~Leitungen aus $n$ Leitungen auszuwählen,
und die möglichen Minimum-~/ Maximum-Muster. Damit ergibt sich folgende
Formel:
\begin{displaymath}
  2^{n-m} \cdot \left( \begin{array}{c} n \\ n-m \end{array} \right)
  = 2^{n-m} \cdot \frac{n!}{(n-m)! m!}
  = 2^{n-m} \cdot \frac{n!}{m!} \cdot \frac{1}{(n-m)!}
  \quad (n > m)
\end{displaymath}

Die Anzahl der möglichen Schnitte wird mit der Anzahl der zu entfernenden
Leitungen sehr schnell sehr groß. Um ein Sortiernetzwerk mit 32~Eingängen auf
ein Sortiernetzwerk mit 16~Ein\-gängen zu reduzieren sind 16~Schnitte notwendig,
für die es bereits etwa ${3,939 \cdot 10^{13}}$ Möglichkeiten gibt. Ein
Ausprobieren aller Möglichkeiten ist für große Netzwerke nicht oder nur unter
erheblichem Ressourcenaufwand möglich.

Das Programm \textsc{SN-Evolution-Cut} implementiert einen evolutionären
Algorithmus, der zu einem gegebenen Sortiernetzwerk und einer gewünschten
Leitungszahl ein Schnittmuster sucht, dass ein Sortiernetzwerk mit einer
möglichst geringen Anzahl von Komparatoren und Schichten ergibt. Zur Bewertung
von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}. Mit diesem
Algorithmus wurden zu einer Reihe von „interessanten“ Netzwerken möglichst
gute Schnittmuster gesucht.

Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet die
\emph{Schnitt-Sequenzen} als Individuen. Eine \emph{Schnitt-Sequenz} ist eine
Liste mit $c$~Schnitten, die jeweils durch die Start-Leitung und die Richtung
\textit{Min} beziehungsweise \textit{Max} gegeben ist. Der Algorithmus wendet
jeden Schnitt einzeln an, so dass eine Leitungsnummer mehrfach in einer
Schnittsequenz vorkommen kann. Die höchste zulässige Leitungsnummer ist
abhängig von der Position des Schnitts in der Sequenz. Der Schnitt an
Position~$i$ darf höchstens die Leitungsnummer~${n-i-1}$
enthalten.\footnote{Die niedrigste Leitungsnummer ist $0$, die höchste
Leitungsnummer eines $n$-Sortiernetzwerks ist $n-1$.}

Um zwei Individuen zu rekombinieren werden die ersten $r$~Schnitte der einen
Schnitt-Sequenz verwendet und die letzten ${c-r}$~Schnitte der zweiten
Sequenz. $r$ ist eine Zufallsvariable mit $0 \leqq r \leqq c$.

Die Mutation setzt entweder die Leitungs-Nummer eines Schnitts~$i$ zufällig
auf einen neuen Wert $l$ mit $0 \leqq l \le n-i$ oder invertiert die
Schnitt-Richtung.

In ihrer Arbeit \textit{“Improving Bitonic Sorting by Wire Elimination”}
zeigen \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka}, wie man einen
bitonen Mischer, der nach Batchers Methode konstruiert wurde, durch
systematisches Entfernen von Leitungen in einen ebenfalls bitonen Mischer mit
der Hälfte der Leitungen transformiert. Diese alternativen Mischer sparen im
Vergleich zu den Mischern, die nach Batchers Methode konstruiert werden,
Komparatoren ein.

Beispeilsweise geben \textit{Mühlenthaler} und \textit{Wanka} ein
Sortiernetzwerk mit 16~Eingängen an, das mithilfe der alternativen Mischer
konstruiert wurde. Dieses Sortiernetzwerk benötigt 68~Komparatoren, 12~weniger
als das bitone Mergesort-Netzwerk nach Batchers Methode. Gegenüber Batchers
Methode sparen so konstruierte Sortiernetzwerke ${\frac{1}{4}n(\log n - 1)}$
Komparatoren ein.

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

Startet man {\sc SN-Evolution-Cut} mit dem bitonen Mergesort-Netzwerk
$\operatorname{BS}(32)$ und der Vorgabe 16~Leitungen zu entfernen, liefert der
Algorithmus Sortiernetzwerke, die ebenfalls aus 68~Komparatoren bestehen. Ein
16-Sortiernetzwerk, das auf diese Weise generiert wurde, ist in
Abbildung~\ref{fig:16-ec-1277186619} zu sehen.

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

Betrachtet man das Sortiernetzwerk in Abbildung~\ref{fig:16-ec-1277186619}, so
ist keine Ähnlichkeit zu $\operatorname{BS}(32)$ oder $\operatorname{BS}(16)$
erkennbar -- insbesondere die ersten Schichten des Netzwerks scheinen rein
zufällig zu sein. Dies ist jedoch kein Eigenschaft des Algorithmus, sondern
hängt insbesondere von der Eingaben. Wird \textsc{SN-Evolution-Cut}
beispielsweise mit dem \emph{Odd-Even-Transpositionsort-Netzwerk}
$\operatorname{OET}(n)$ und $m$~Schnitten gestartet, so ist das beste Ergebnis
immer das $\operatorname{OET}(n-m)$-Netzwerk. 

Anders verhält sich das \emph{Pairwise-Sorting-Netzwerk}
$\operatorname{PS}(n)$, das \textit{Ian Parberry} in seiner Arbeit „The
Pairwise Sorting Network“ definiert. Startet man \textsc{SN-Evolution-Cut} mit
$\operatorname{PS}(32)$ und der Vorgabe, 16~Leitungen zu entfernen, erhält man
ein Sortiernetzwerk, dass die gleiche Anzahl an Komparatoren und Schichten hat
wie $\operatorname{PS}(16)$ und $\operatorname{OES}(16)$. Der Algorithmus gibt
auch nach zahlreichen Versuchen nur eines von zwei Sortiernetzwerken zurück,
die beide sehr symmetrisch sind und eine saubere Struktur aufweisen. Eines der
beiden Sortiernetzwerke ist in Abbildung~\ref{fig:16-ec-from-ps32}
dargestellt, das andere Sortiernetzwerk unterscheidet sich lediglich dadurch,
dass die zweite und dritte Schicht vertauscht sind.

Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even-Mischer} nicht
einsetzt und auch nicht auf einem Mischer basiert, ist der
$\operatorname{OEM}(8,8)$ im Sortiernetzwerk in
Abbildung~\ref{fig:16-ec-from-ps32} eindeutig erkennbar (Schichten~7--10). In
den Schichten~1--6 erkennt man zwei unabhängige Sortiernetzerke, die
strukturell identisch zu $\operatorname{PS}(8)$ sind -- die Schichten~1 und~2
sowie 4~und~5 sind vertauscht, was jeweils zum selben Ergebnis nach dem
Schichtenpaar führt.

Wendet man \textsc{SN-Evolution-Cut} auf $\operatorname{PS}(16)$ an, so kann
man $\operatorname{OES}(8)$ erhalten.

\begin{itemize}
  \item Beispiel: Moritz und Rolfs Optimierung für Bitonic-Sort.
  \item Wie gut kann man durch wegschneiden werden?
  \item Wieviele Schnitte ergeben das selbe Netzwerk?
  \item Abschnitt „Optimierung der Schnitte“ hier einbauen.
\end{itemize}

\section{Der \textsc{SN-Evolution}-Algorithmus}

Um einen evolutionären Algorithmus für Sortiernetzwerke zu entwickeln, werden
die vorgestellten Methoden kombiniert.

\subsection{Bewertungsfunktion}\label{sect:bewertung}

Um Sortiernetzwerke überhaupt optimieren zu können, muss zunächst die
{\em Güte} eines Netzwerkes definiert werden. Prinzipiell gibt es zwei Ziele,
die interessant sind:
\begin{itemize}
  \item Möglichst wenige Komparatoren ("`klein"')
  \item Möglichst wenige Schichten ("`schnell"')
\end{itemize}

Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das
kleinste bekannte Sortiernetzwerk für 16~Eingänge besteht aus 60~Komparatoren
in 10~Schichten. Das schnellste Netzwerk besteht aus 61~Komparatoren in nur
9~Schichten.

Eine Gütefunktion, die die beiden Ziele "`klein"' und "`schnell"'
berücksichtigen kann, hat die folgende allgemeine Form:
\begin{equation}
  \mathit{Guete}(S) = w_{\mathrm{Basis}}
                    + w_{\mathrm{Komparatoren}} \cdot \left|S\right|_\mathrm{Komparatoren}
                    + w_{\mathrm{Schichten}} \cdot \left|S\right|_\mathrm{Schichten}
\end{equation}
Die Parameter $w_{\mathrm{Komparatoren}}$ und $w_{\mathrm{Schichten}}$ dienen
dabei der Festlegung des Optimierungsziels. Wenn einer der beiden Parameter
gleich Null ist, wird nur das jeweils andere Ziel verfolgt. Sind beide
Parameter gleich Null, werden alle Netzwerke mit der gleich Güte bewertet --
jegliche Ergebnisse sind dann rein zufälliger Natur.

Mit dem Parameter $w_{\mathrm{Basis}}$ kann auf die Selektion Einfluss
genommen werden. Ist er groß, wird der relative Unterschied der Güten
verschiedener Netzwerke kleiner, was die {\em Exploration}, das Absuchen des
gesamten Lösungsraums, begünstigt. Wählt man $w_{\mathrm{Basis}}$ hingegen
klein, in Abhängigkeit von den anderen beiden Parametern sind auch negative
Werte möglich, werden die relativen Unterschiede groß. Dadurch wird die {\em
Exploitation}, das Finden lokaler Optima, bevorzugt.

\subsection{Selektion}

...

\subsection{Rekombination}

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

Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft
erhält.

\subsection{Mutation}

Zu einem vollständigen evolutionären Algorithmus gehört außerdem eine Mutation
--~eine zufällige Veränderung einer Lösung. Leider ist es nicht möglich ein
Sortiernetzwerk zufällig zu verändern aber trotzdem die Sortiereigenschaft zu
erhalten. Selbst das \emph{Hinzufügen} eines zufälligen Komparators kann diese
Eigenschaft zerstören.

Nach einer Mutation müsste man überprüfen, ob das neue Komparatornetzwerk die
Sortiereigenschaft noch besitzt. Nach heutigem Wissenstand ist diese
Überprüfung nur mit exponentiellem Aufwand möglich, etwa durch das
Ausprobieren aller $2^n$~Bitmuster.

Um das Potenzial einer Mutation abzuschätzen habe ich in den evolutionären
Algorithmus eine Überprüfung eingebaut. Unmittelbar vor dem Einfügen in die
Population überprüft das Programm die Notwendigkeit jedes einzelnen
Komparators. Dazu wurde nacheinander jeder Komparator entfernt und überprüft,
ob das verbleibende Netzwerk die Sortiereigenschaft noch besitzt.

\begin{itemize}
\item Güte von Sortiernetzwerken (Anzahl der Komparatoren, Anzahl der
Schichten, kobiniert)
\item Rekombination: Merge Anhängen und Leitungen entfernen.
\end{itemize}

Ein Beispielnetzwerk, das von dem Algorithmus gefunden wird, zeigt
Abbildung~\ref{fig:evolutionary_08}.

\begin{figure}
\begin{center}
\input{images/evolutionary-08.tex}
\end{center}
\caption{Ein mit dem evolutionären Algorithmus erzeugtes Sortiernetzwerk mit
acht Eingängen. Es besteht aus 19~Komparatoren in 6~Schichten.}
\label{fig:evolutionary_08}
\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{Güte}

\begin{itemize}
\item So gut kann man mindestens werden {\em ($\rightarrow$ Bitonic-Mergesort, vermute ich)}.
\item Wie gut die Netzwerke werden, hängt stark vom verwendeten \em{Mischer} ab.
\end{itemize}

\section{Markov-Kette}

Der evolutionäre Algorithmus aus dem vorherigen Abschnitt verwendete 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, indem man \emph{immer} das
aktuelle Netzwerk mit sich selbst kombiniert und anschließend die Hälfte aller
Leitungen eliminiert, 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 man $S_1$ durch die Rekombination von $S_0$ mit sich
selbst erzeugen kann.

Der Algorithmus {\sc SN-Markov} legt auf diesem 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 er das aktuelle Sortiernetzwerk mit sich selbst und erhält so
einen zufälligen Nachfolger.

\begin{itemize}
  \item $n \leftarrow \mathrm{Input}$
  \item \texttt{while} \textit{true}
  \begin{itemize}
    \item $n \leftarrow \operatorname{recombine} (n, n)$
  \end{itemize}
\end{itemize}

\begin{itemize}
  \item Beste erreichte Netzwerke (gleich zu \emph{OE-Mergesort}).
  \item Anzahl der erreichbaren Sortiernetzwerke.
  \item Anzahl der Komparatoren und Anzahl der Schichten der durchlaufenen
    Netzwerke. (Abbildung~\ref{fig:markov-comparators-16})
\end{itemize}

\begin{figure}
  \begin{center}
  \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-16.pdf}
  \end{center}
  \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 16~Leitungen), die von {\sc SN-Markov} durchlaufen wurden.}
  \label{fig:markov-comparators-16}
\end{figure}

%\input{shmoo-aequivalenz.tex}

\section{Optimierung der Schnitte}

\todo{In den Abschnitt "`Leitungen entfernen"' einbauen.}

\begin{figure}
\begin{center}
\input{images/32-ec-1277190372.tex}
\end{center}
\caption{{\tt images/32-ec-1277190372.tex}: Sortiernetzwerk mit 32~Leitungen
  und 206~Komparatoren in 15~Schichten. Das Netzwerk wurde von dem Algorithmus
  \textsc{SN-Evolution-Cut} aus dem Bitonic-Mergesort-Netzwerk $BS(64)$ durch
  32~Schnitte erzeugt.}
\label{fig:32-ec-1277190372}
\end{figure}

Abbildung~\ref{fig:32-ec-1277190372} zeigt ein 32-Sortiernetzwerk, dass vom
\textsc{SN-Evolution-Cut}-Algorithmus aus dem $BS(64)$-Netzwerk erzeugt wurde.
Es besteht aus 206~Komparatoren in 15~Schichten -- 34~Komparatoren weniger als
$BS(32)$ und zwei Komparatoren weniger als das Netzwerk, das nach Mühlenthaler
und Wankas Methode konstruiert wird. Die Anzahl der Schichten ist bei allen
Netzwerken gleich.

\textbf{TODO:} $BS(128) \rightarrow n=64$: 584~Komparatoren in 21~Schichten
möglich (nach ca. 600k Iterationen). Moritz und Rolf: $672-80=592$
Komparatoren; $BS(64)$: 672~Komparatoren.

Schnitt-Sequenz:
MIN( 92)
MAX( 80)
MIN(100)
MAX( 54)
MAX(102)
MAX( 53)
MAX(105)
MAX(  6)
MAX( 99)
MAX( 79)
MAX( 26)
MIN(111)
MAX( 12)
MIN( 22)
MAX( 61)
MAX( 72)
MAX( 68)
MIN( 80)
MAX( 80)
MAX( 99)
MAX(105)
MAX(  0)
MIN(  8)
MAX( 40)
MAX( 74)
MAX( 40)
MAX( 40)
MIN( 56)
MAX( 27)
MAX( 13)
MAX(  1)
MAX( 81)
MAX( 17)
MAX(  4)
MIN( 36)
MIN( 22)
MAX( 13)
MIN( 72)
MAX( 24)
MAX(  5)
MIN( 10)
MAX( 59)
MIN( 37)
MAX( 65)
MAX( 46)
MAX( 73)
MAX( 58)
MAX( 29)
MAX( 65)
MIN( 23)
MAX( 56)
MAX( 11)
MIN( 75)
MIN( 51)
MIN( 46)
MIN( 34)
MAX( 32)
MAX(  6)
MAX( 37)
MIN(  4)
MIN( 28)
MIN( 20)
MAX( 33)
MAX( 34)

% images/32-ec-1277190372.tex

\section{Empirische Beobachtungen}

\begin{itemize}
\item So schnell konvergiert der Algorithmus.
\item $\ldots$
\end{itemize}

\section{Ausblick}

Das würde mir noch einfallen$\ldots$

\bibliography{references}
\bibliographystyle{plain}

%\listoffigures

\end{document}

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