From 59e5e54ec3f7f8206e8796c18039456fe7093611 Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Wed, 25 Mar 2009 16:32:28 +0100 Subject: [PATCH] diplomarbeit.tex: Didn't really keep track.. A lot of stuff changed I guess.. --- diplomarbeit.tex | 366 +++++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 357 insertions(+), 9 deletions(-) diff --git a/diplomarbeit.tex b/diplomarbeit.tex index bdb7296..2656d75 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -13,6 +13,9 @@ \usepackage{subfigure} \usepackage{icomma} +\usepackage{tikz} +\usetikzlibrary{arrows,shapes} + % Fuer mathtoolsset \usepackage{mathtools} @@ -41,9 +44,24 @@ \begin{document} +\tikzstyle{vertex} = [circle,draw,thick,fill=black,minimum size=5pt,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] + \maketitle \begin{abstract} -Dies ist der 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 @@ -52,21 +70,351 @@ Dies ist der Abstract. \section{Motivation und Einleitung} -\subsection{Motivation} +\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} + +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}$. + +\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) + +\subsubsection{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}} + \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_0, u_1, \ldots, u_{m-1}}$ und +${v_0, v_1, \ldots, v_{m-1}}$. Die Folge der $u_i$ sei aufsteigend sortiert, +die Folge der $v_i$ 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)$, as {\em Batcher-Mergesort} Netzwerk für acht Eingänge. +Markiert sind die beiden Instanzen von $S(4)$ (rot) und der bitone Mischer +$M(8)$ (blau).} +\label{fig:batcher_08} +\end{figure} + +\subsection{Odd-Even-Mergesort} + +Obwohl der Name ähnlich klingt, haben {\em Odd-Even-Mergesort} (OEM) und +Odd-Even-Transporisionsort (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. + +Beispiel: Siehe Abbildung~\ref{fig:odd_even_mergesort_08}. + +\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} + +\begin{itemize} +\item Min-Richtung +\item Max-Richtung +\end{itemize} + +\section{Der evolutionäre Ansatz} + +\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} + +\subsection{Güte} -Das habe ich gemacht, bzw. darum habe ich das gemacht. +\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{Einleitung}\label{sect:introduction} +\subsection{Vom evolutionären Algorithmus zu einer Markov-Kette} -Das sind Sortiernetzwerke und so. +\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{Die Algorithmen} +\section{Empirische Beobachtungen} -... +\begin{itemize} +\item So schnell konvergiert der Algorithmus. +\item $\ldots$ +\end{itemize} -\subsection{Ausblick} +\section{Ausblick} -So geht's jetzt weiter. +Das würde mir noch einfallen$\ldots$ %\bibliography{references} %\bibliographystyle{plain} -- 2.11.0