[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=25mm}

\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 {\em Komparatoren} mit dem Eingängen anderer {\em 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.

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 also 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{Odd-Even-Transpositionsort}
\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 {\em Odd-Even-Transpositionsort} Netzwerk für acht Eingänge.}
\label{fig:odd_even_transposition_08}
\end{figure}

\subsection{Batcher's Mergesort}

Ein Netzwerk von K.~E.~Batcher. Siehe:
K.E. Batcher: Sorting Networks and their Applications. Proc. AFIPS Spring
Joint Comput. Conf., Vol. 32, 307-314 (1968)
\todo{Bibtex!}

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

Das Netzwerk basiert auf dem {\em bitonen Mischer}, einem Komparator-Netzwerk,
das eine beliebige bitone Folge in eine sortierte Listen umordnen kann. Eine
{\em bitone Folge} ist eine monoton steigende Folge gefolgt von einer monoton
fallenden Folge, oder ein zyklischer Shift davon.
Abbildung~\ref{fig:beispiel-biton} zeigt die vier prinipiellen Möglichkeiten
die durch zyklische Shifts entstehen können. Die wichtigsten Varianten für
Batcher's 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 die entstehende Folge aus
zwei bitonen Folgen besteht, die rekursiv zusammengeführt werden können.
Abbildung~\ref{fig:bitonic-merge-normal} zeigt die Situationen vor und nach
diesem Schritt des Mischers.

Mit dem bitonen Mischer auch zwei aufsteigend sortierte Folgen sortiert
werden. Dazu ist lediglich das "`Umbenennen"' der Leitungen notwendig.
Abbildung~\ref{fig:bitonic-merge-tricheter} zeigt das Schema des bitonen
Mischers für zwei aufsteigend sortierte Foglen. Durch das Umbenennen verändert
sich das Muster der Komparatoren ein wenig: Statt an eine Treppe erinnert das
Muster nun an einen Trichter.

\subsubsection{Batcher's Bitonic-Mergesort-Netzwerk}

Das Sortiernetzwerk $S(n)$ mit $n$~Eingängen besteht aus zwei Instanzen von
$S(\frac{n}{2})$, dem Netzwerk mit $\frac{n}{2}$~Eingängen und dem bitonen
Mischer~$M(n)$. Die Rekursion bricht bei ${n = 1}$~ab --~eine einelementige
Liste ist immer sortiert.
Das konkrete Netzwerk~$S(8)$ ist in Abbildung~\ref{fig:batcher_08} zu sehen.
Eingezeichnet sind ebenfalls die beiden Instanzen des Netzwerks~$S(4)$ (rot)
sowie der bitone Mischer~$M(8)$ (blau).



%\begin{figure}
%\begin{center}
%\includegraphics[viewport=115 491 372 782,width=7.5cm]{images/sn-rekursiver-aufbau.pdf}
%\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}

\begin{figure}
  \begin{center}
  \input{images/batcher-8.tex}
  \end{center}
  \caption{$S(8)$, Batcher's {\em bitone Mergesort-Netzwerk} für acht
  Eingänge. Markiert sind die beiden Instanzen von $S(4)$ (rot), die beiden
  bitonen Mischer~$M(4)$ (blau) und die Komparatoren, die im letzten rekursiven
  Schritt hinzugefügt wurden (grün).}
  \label{fig:batcher_08}
\end{figure}

\subsection{Odd-Even-Mergesort}

Obwohl der Name ähnlich klingt, haben {\em Odd-Even-Mergesort} (OEM) und
{\em Odd-Even-Transpositionsort} (OET, siehe
Abschnitt~\ref{sect:odd_even_transpositionsort}) wenig gemein. Auch dieses
Netzwerk ist von K.~Batcher gefunden worden und wird rekursiv durch einen
"`Mischer"' definiert.

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

Der {\em Odd-Even-Mischer} ist ein Komperatornetzwerk, dass zwei sortierte
Folgen zu einer sortierten Ausgabe zusammenfügen kann. Dabei kommt es mit
weniger Vergleichen aus als der {\em bitone Mischer}, der im
Abschnitt~\ref{sect:der_bitone_mischer} vorgestellt wurde.

Der {\em 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 jetzt 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} leicht 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}}$ $2$~Nullen mehr enthählt als
$W_{\textrm{ungerade}}$, muss eine Vertauschung stattfinden, um die Ausgabe zu
sortieren. 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}

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

Auch beim \emph{Odd-Even-Mergesort-Netzwerk} --~wie beim \emph{bitonen
Mergesort-Netzwerk}~-- entsteht das Sortiernetzwerk aus dem {\em
Odd-Even-Mischer} durch rekursives Anwenden auf einen Teil der Eingabe
(üblicherweise die Hälfte der Leitungen) und anschließendes zusammenfügen.
Abbildung~\ref{fig:odd_even_mergesort_08} zeigt das Netzwerk für $8$~Eingänge.

\begin{figure}
\begin{center}
\input{images/oe-mergesort-8.tex}
\end{center}
\caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge.}
\label{fig:odd_even_mergesort_08}
\end{figure}

\begin{itemize}
\item Odd-Even-Transpositionsort
\item Bitonic-Mergesort
\item Odd-Even-Mergesort
\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.

\subsection{Zwei Netzwerke kombinieren}

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

Man kann ein gegebenes Sortiernetzwerk mit $n$~Eingängen auf ein
Sortiernetzwerk mit $(n-1)$~Leitungen verkleinern, indem man eine Leitung
entfernt. Zunächst wird angenommen, dass das Minimum oder das Maximum an einem
der Eingänge anliegt. Der Weg durch das Netzwerk zum entsprechenden Ausgang
ist dadurch fest vorgegeben, insbesondere welche Komparatoren dafür sorgen,
dass die Leitung gewechselt wird und welche nicht.
Abbildung~\ref{fig:oe-transposition-cut0} zeigt den Weg eines Maximums durch
das {\em Odd-Even-Transpositionsort-Netzwerk}.

Im nächsten Schritt werden alle beteiligten Komparatoren gelöscht bzw.
ersetzt: Komparatoren, die {\em nicht} zu einem Wechsel der Leitung geführt
haben, werden ersatzlos gelöscht. Diese Komparatoren sind in
Abbildung~\ref{fig:oe-transposition-cut0} grün markiert. Die Komparatoren, die
zum Wechsel der Leitung geführt haben, werden durch sich kreuzende Leitungen
ersetzt. Das Resultat zeigt Abbildung~\ref{fig:oe-transposition-cut1}. Wenn
man die Maximum-Leitung entfernt (Abbildung~\ref{fig:oe-transposition-cut2}),
erhält man ein Sortiernetzwerk für $(n-1)$~Leitungen.

\begin{figure}
  \centering
  \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 {\em Odd-Even-Transpositionsort} Netzwerk
  $\textrm{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 $\textrm{OET}(7)$ markiert.}
\end{figure}

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

\begin{itemize}
\item Min-Richtung
\item Max-Richtung
\end{itemize}

\section{Der evolutionäre Ansatz}

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

\subsection{Bewertungsfunktion}

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

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

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

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

\subsection{Selektion}

...

\subsection{Rekombination}

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

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

\subsection{Mutation}

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

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

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

\begin{itemize}
\item Güte von Sortiernetzwerken (Anzahl der Komparatoren, Anzahl der
Schichten, kobiniert)
\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}

\subsection{Vom evolutionären Algorithmus zu einer Markov-Kette}

\begin{itemize}
\item Kombiniere immer das aktuelle Netzwerk mit sich selbst.
\item Kann die Mindestgüte immernoch erreicht werden? ({\em Ich denke schon.})
\item Anzahl der erreichbaren Sortiernetzwerke.
\end{itemize}

%\input{shmoo-aequivalenz.tex}

\section{Optimierung der Schnitte}

Der \emph{evolution-cut}-Algorithmus nimmt ein gegebenes Sortiernetzwerk mit
$n$~Leitungen und sucht die beste Sequenz von $c$~Min- und Max-Schnitten um
ein ${(n-c)}$-Sortiernetzwerk zu erhalten.

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

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

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

\begin{figure}
\begin{center}
\input{images/16-ec-1277186619.tex}
\end{center}
\caption{{\tt images/16-ec-1277186619.tex}: Sortiernetzwerk mit 16~Leitungen
  und 68~Komparatoren in 10~Schichten. Das Netzwerk wurde von dem Algorithmus
  \emph{evolution-cut} aus dem Bitonic-Mergesort-Netzwerk $M(32)$ durch
  16~Schnitte erzeugt.}
\label{fig:16-ec-1277186619}
\end{figure}

Wendet man den \emph{evolution-cut}-Algorithmus auf das
Bitonic-Mergesort-Netzwerk $M(n)$ an und setzt die Anzahl der Schnitte~$c$ auf
$\frac{n}{2}$, so erhält man Sortiernetzwerke, die weniger Komparatoren
benötigen als $M(\frac{n}{2})$.

Das Sortiernetzwerk in Abbildung~\ref{fig:16-ec-1277186619} ist entstanden,
indem der Algorithmus \emph{evolution-cut} auf das $M(32)$-Sortiernetzwerk
angewendet wurde. Der Algorithmus fand eine Schnitt-Sequenz aus 16~Schnitten,
die ein Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in 10~Schichten
erzeugt. Das $M(16)$-Sortiernetzwerk besteht aus 80~Komparatoren in
10~Schichten.

Dieses Ergebnis deckt sich mit dem Sortiernetzwerk, dass
\emph{Moritz Mühlenthaler} und \emph{Rolf Wanka} in ihrer Veröffentlichung
„Improving Bitonic Sorting by Wire Elimination“ vorstellen. Sie verwenden
Schnitte, um Komparatoren beim bitonen $(n,n)$-Mischer enizusparen. Ein
sukzessive aus optimieren Mischern aufgebautes Sortiernetzwerk spart
--~verglichen mit dem Bitonic-Mergesort-Netzwerk~-- $\frac{1}{4}n(\log n - 1)$
Komparatoren ein. Bei einem Sortiernetzwerk mit 16~Leitungen also
12~Komparatoren -- 68 statt 80.

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

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

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

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

% images/32-ec-1277190372.tex

\section{Empirische Beobachtungen}

\begin{itemize}
\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 :