Geschützte Leerzeichen verwendet wo sinnvoll.

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

\begin{itemize}
\item Komprimieren (Alle Komparatoren so früh wie möglich anwenden).
\item Normalisieren (Transformation zu Standard-Sortiernetzwerken).
\end{itemize}

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

{\em Mutation ist schwierig, weil es die Sortiereigenschaft eben nicht
erhält.}


\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}
\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}
\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}
\label{fig:09-e2-1237999719}
\end{figure}

\begin{figure}
\begin{center}
\input{images/10-e2-1239014566.tex}
\end{center}
\caption{{\tt images/10-e2-1239014566.tex}: 29~Komparatoren in 8~Schichten}
\label{fig:10-e2-1239014566}
\end{figure}

% ============

\section{Shmoo-Äquivalenz}

Die folgenden 16-Eingang-Sortiernetzwerke wurden alle mit dem
\emph{Algorithmus~1} gefunden. Sie haben alle 63~Komparatoren in 10~Schichten,
jeweils die selbe Anzahl wie Odd-Even-Mergesort.

Um wiederkehrende Muster in den hinteren Schichten der erzeugten
Sortiernetzwerke besser untersuchen zu können, wurden die erzeugten Netzwerke
in Gruppen aufgeteilt. Zwei Netzwerke befinden sich dann in der selben
Gruppen, wenn die Nullen bzw. Einsen, die auf einer Leitung vorkommen können,
nach der 5.~Schicht (Schicht~4, da bei Null mit dem Zählen begonnen wird)
nicht mehr ändert. Das heißt, dass die Schichten 0--4 unterschiedlich
aufgebaut sind, aber den selben Effekt erziehlen. Die Schichten 5--9 sind
hingegen innerhalb einer Gruppe austauschbar und oft (immer?) identisch.

Die Anzahl der Netzwerke in den jeweiligen Gruppen ist unterschiedlich. Zur
Zeit sind in den Gruppen so viele Netzwerke:\\
\begin{tabular}{|l|r|r|} \hline
Gruppe~0 & 18 & $48,7\%$ \\
Gruppe~1 & 9  & $24,3\%$ \\
Gruppe~2 & 6  & $16,2\%$ \\
Gruppe~3 & 3  & $8,1\%$ \\
Gruppe~4 & 1  & $2,7\%$ \\ \hline
\end{tabular}

Die hinteren Schichten zwischen den Gruppen~1 und~3 schauen so aus, als wären
sie nur gespiegelt. Warum kommt Gruppe~1 aber viel häufiger vor? Ggf. eine
Konsequenz aus dem Normieren?

Dito für die Gruppen~2 und~4. Warum ist die eine häufiger?

Ist Gruppe~0 symmetrisch bzgl. der Leitungen?

% Gruppe 0

\begin{figure}
\begin{center}
\input{images/16-e1/group0/16-e1-1258009316.tex}
\end{center}
\caption{{\tt images/16-e1/group0/16-e1-1258009316.tex}: 63~Komparatoren in
10~Schichten.}
\label{fig:16-e1-1258009316}
\end{figure}

\begin{figure}
\begin{center}
\input{images/16-e1/group0/16-e1-1258010866.tex}
\end{center}
\caption{{\tt images/16-e1/group0/16-e1-1258010866.tex}: 63~Komparatoren in
10~Schichten.}
\label{fig:16-e1-1258010866}
\end{figure}

\begin{figure}
\begin{center}
\input{images/16-e1/group0/16-e1-1258011861.tex}
\end{center}
\caption{{\tt images/16-e1/group0/16-e1-1258011861.tex}: 63~Komparatoren in
10~Schichten.}
\label{fig:16-e1-1258011861}
\end{figure}

\begin{figure}
\begin{center}
\input{images/16-e1/group0/16-e1-1259060992.tex}
\end{center}
\caption{{\tt images/16-e1/group0/16-e1-1259060992.tex}: 63~Komparatoren in
10~Schichten.}
\label{fig:16-e1-1259060992}
\end{figure}

%\begin{figure}
%\begin{center}
%\input{images/16-e1/group0/16-e1-1259061148.tex}
%\end{center}
%\caption{{\tt images/16-e1/group0/16-e1-1259061148.tex}: 63~Komparatoren in
%10~Schichten.}
%\label{fig:16-e1-1259061148}
%\end{figure}

% Gruppe 1

\begin{figure}
\begin{center}
\input{images/16-e1/group1/16-e1-1258009982.tex}
\end{center}
\caption{{\tt images/16-e1/group1/16-e1-1258009982.tex}: 63~Komparatoren in 10~Schichten.
Schichten 4--9 identisch zu 16-e1-1258030047 (Gruppe~1).}
\label{fig:16-e1-1258009982}
\end{figure}

\begin{figure}
\begin{center}
\input{images/16-e1/group1/16-e1-1258010023.tex}
\end{center}
\caption{{\tt images/16-e1/group1/16-e1-1258010023.tex}: 63~Komparatoren in
10~Schichten.}
\label{fig:16-e1-1258010023}
\end{figure}

\begin{figure}
\begin{center}
\input{images/16-e1/group1/16-e1-1258029734.tex}
\end{center}
\caption{{\tt images/16-e1/group1/16-e1-1258029734.tex}: 63~Komparatoren in
10~Schichten.}
\label{fig:16-e1-1258029734}
\end{figure}

\begin{figure}
\begin{center}
\input{images/16-e1/group1/16-e1-1258030047.tex}
\end{center}
\caption{{\tt images/16-e1/group1/16-e1-1258030047.tex}: 63~Komparatoren in
10~Schichten.}
\label{fig:16-e1-1258030047}
\end{figure}

%\begin{figure}
%\begin{center}
%\input{images/16-e1/group1/16-e1-1258034768.tex}
%\end{center}
%\caption{{\tt images/16-e1/group1/16-e1-1258034768.tex}: 63~Komparatoren in
%10~Schichten.}
%\label{fig:16-e1-1258034768}
%\end{figure}

% Gruppe 2

\begin{figure}
\begin{center}
\input{images/16-e1/group2/16-e1-1258029063.tex}
\end{center}
\caption{{\tt images/16-e1/group2/16-e1-1258029063.tex}: 63~Komparatoren in
10~Schichten.}
\label{fig:16-e1-1258029063}
\end{figure}

\begin{figure}
\begin{center}
\input{images/16-e1/group2/16-e1-1258034821.tex}
\end{center}
\caption{{\tt images/16-e1/group2/16-e1-1258034821.tex}: 63~Komparatoren in
10~Schichten.}
\label{fig:16-e1-1258034821}
\end{figure}

\begin{figure}
\begin{center}
\input{images/16-e1/group2/16-e1-1259054993.tex}
\end{center}
\caption{{\tt images/16-e1/group2/16-e1-1259054993.tex}: 63~Komparatoren in
10~Schichten.}
\label{fig:16-e1-1259054993}
\end{figure}

\begin{figure}
\begin{center}
\input{images/16-e1/group2/16-e1-1259058588.tex}
\end{center}
\caption{{\tt images/16-e1/group2/16-e1-1259058588.tex}: 63~Komparatoren in
10~Schichten.}
\label{fig:16-e1-1259058588}
\end{figure}

%\begin{figure}
%\begin{center}
%\input{images/16-e1/group2/16-e1-1259063485.tex}
%\end{center}
%\caption{{\tt images/16-e1/group2/16-e1-1259063485.tex}: 63~Komparatoren in
%10~Schichten.}
%\label{fig:16-e1-1259063485}
%\end{figure}

%\begin{figure}
%\begin{center}
%\input{images/16-e1/group2/16-e1-1259063618.tex}
%\end{center}
%\caption{{\tt images/16-e1/group2/16-e1-1259063618.tex}: 63~Komparatoren in
%10~Schichten.}
%\label{fig:16-e1-1259063618}
%\end{figure}

% Gruppe 3

\begin{figure}
\begin{center}
\input{images/16-e1/group3/16-e1-1258012027.tex}
\end{center}
\caption{{\tt images/16-e1/group3/16-e1-1258012027.tex}: 63~Komparatoren in
10~Schichten.}
\label{fig:16-e1-1258012027}
\end{figure}

\begin{figure}
\begin{center}
\input{images/16-e1/group3/16-e1-1258037039.tex}
\end{center}
\caption{{\tt images/16-e1/group3/16-e1-1258037039.tex}: 63~Komparatoren in
10~Schichten.}
\label{fig:16-e1-1258037039}
\end{figure}

\begin{figure}
\begin{center}
\input{images/16-e1/group3/16-e1-1259065042.tex}
\end{center}
\caption{{\tt images/16-e1/group3/16-e1-1259065042.tex}: 63~Komparatoren in
10~Schichten.}
\label{fig:16-e1-1259065042}
\end{figure}

% Gruppe 4

\begin{figure}
\begin{center}
\input{images/16-e1/group4/16-e1-1259060520.tex}
\end{center}
\caption{{\tt images/16-e1/group4/16-e1-1259060520.tex}: 63~Komparatoren in 10~Schichten.
(Gruppe~4).}
\label{fig:16-e1-1259060520}
\end{figure}

\begin{figure}
\begin{center}
\input{images/16-e1/group4/16-e1-1259067171.tex}
\end{center}
\caption{{\tt images/16-e1/group4/16-e1-1259067171.tex}: 63~Komparatoren in 10~Schichten.
(Gruppe~4).}
\label{fig:16-e1-1259067171}
\end{figure}

\subsection{Güte}

\begin{itemize}
\item So gut kann man mindestens werden {\em ($\rightarrow$ Bitonic-Mergesort, vermute ich)}.
\item 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}

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