From fc5785676841c1186ea1240150e9e27622fbabd2 Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Tue, 22 Feb 2011 09:55:11 +0100 Subject: [PATCH] Diverse ToDos abgearbeitet. --- diplomarbeit.tex | 133 +++++++++++++++++++++++++++++++++++-------------------- 1 file changed, 84 insertions(+), 49 deletions(-) diff --git a/diplomarbeit.tex b/diplomarbeit.tex index e0a902c..a074468 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -81,16 +81,20 @@ \maketitle \begin{abstract} -\todo{Einleitung schreiben.} - -Sortiernetzwerke werden eingeführt und einige bekannte Konstruktionen werden -vorgestellt (Odd-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 hin bekomme bzw. Recht behalte.} +Sortiernetzwerke erweisen sich als sehr schwieriges Optimierungsproblem. Zwar +ist das Konzept leicht verständlich und schnell erklärt, effiziente und +schnelle Sortiernetzwerke zu finden oder zu konstruieren bleibt aber eine +Herausforderung. + +Diese Arbeit verwendet „Schnitte“ oder „Leitungselimination“ und +Mischer-Netzwerke, um evolutionäre Algorithmen anzugeben, deren Individuen die +Menge der gültigen Sortiernetzwerke nie verlassen. Bisherige Ansätze bewegten +sich in der Regel in der Menge aller Komparatornetzwerke und suchten dort nach +Sortiernetzwerken. Nach dem Vorstellen der zwei Algorithmen +\textsc{SN-Evolution} und \textsc{SN-Evolution-Cut} sowie einiger Ergebnisse, +die diese Algorithmen erzielen konnten, wird -- basierend auf dem +evolutionären Algorithmus \textsc{SN-Evolution} -- eine Markov-Kette für +Sortiernetzwerke angegeben. \end{abstract} \newpage @@ -114,9 +118,9 @@ Einfacher ist der Korrektheitsbeweis bei konstruktiven Verfahren, da hier die Konstruktionsvorschrift genutzt werden kann um die Korrektheit für beliebige Eingabegrößen zu beweisen. Im Abschnitt~\ref{sect:konstruktive_netzwerke} geschieht dies beispielsweise für zwei von \emph{Kenneth~E. Batcher} 1968 -gefundenen Konstruktionsvorschriften. +gefundene Konstruktionsvorschriften. -Um effiziente und schnelle Sortiernetzwerke zu finden, wurden schon früh +Um effiziente und schnelle Sortiernetzwerke zu finden, wurden schon wiederholt Computer und automatische Suchverfahren eingesetzt. Bisherige Ansätze versuchen meist, in der Menge aller Komparatornetzwerke jene zu finden, die die Sortiereigenschaft besitzen und aus wenigen Komparatoren bestehen. Die @@ -353,7 +357,6 @@ Sortiereigenschaft erhält. Transformationen von Sortiernetzwerken werden in Abschnitt~\ref{sect:tranformation} beschrieben, ein Algorithmus, der Mutation einsetzt, wird in Abschnitt~\ref{sect:sn-evolution-cut} vorgestellt. - \begin{figure} \begin{center} \input{images/16-hillis.tex} @@ -395,12 +398,13 @@ anzugeben, die mit 45~Komparatoren effizienter sind als alle bis dahin Bekannten (Abbildung~\ref{fig:13-juille}). \newpage -\section{Bekannte konstruktive Sortiernetzwerke} +\section[Konstruktionsverfahren]{Bekannte konstruktive Sortiernetzwerke} \label{sect:konstruktive_netzwerke} -Übersicht über bekannte konstruktive Sortiernetzwerke. - -\todo{Einleitungssatz} +Die bekannten Konstruktionsverfahren für Sortiernetzwerke, insbesondere +sogenannte \emph{Mischer}, bilden die Grundlage für die beschriebenen +evolutionären Algorithmen beziehungsweise dienen als initiale Eingabe. Im +Folgenden werden daher drei Konstruktionsverfahren vorgestellt. \subsection{Das Odd-Even-Transpositionsort-Netzwerk} \label{sect:odd_even_transpositionsort} @@ -447,6 +451,11 @@ Starteingabe, auf dessen Basis sie versuchen optimierte Sortiernetzwerke zu finden. Häufig dient $\operatorname{OET}(n)$ als Eingabe für diese Algorithmen. +Außerdem bedienen sich die Algorithmen der Technik des Herausschneidens einer +beziehungsweise mehrerer Leitungen, um die Anzahl der Leitungen eines +Sortiernetzwerks zu reduzieren. Die Technik wird in Detail im +Abschnitt~\ref{sect:leitungen_entfernen} beschrieben. + \subsection{Das bitone Mergesort-Netzwerk} Das \emph{bitone Mergesort}-Netzwerk ($\operatorname{BS}(n)$) ist ein @@ -1336,7 +1345,7 @@ w_{\mathrm{Komparatoren}} &=& 1 \\ w_{\mathrm{Schichten}} &=& \left|S\right|_\mathrm{Leitungen} \end{eqnarray*} -\subsection{Versuche mit dem bitonen Mischer} +\subsection[Bitoner Mischer]{Versuche mit dem bitonen Mischer} \begin{figure} \begin{center} @@ -1358,7 +1367,7 @@ als das \emph{bitone Mergesort}-Netzwerk: \bs{16} benötigt 80~Komparatoren, das Sortiernetzwerk in Abbildung~\ref{fig:16-e1-bitonic-1296542566} benötigt lediglich~67. -\subsection{Versuche mit dem \emph{Odd-Even}-Mischer} +\subsection[Odd-Even-Mischer]{Versuche mit dem Odd-Even-Mischer} \begin{figure} \begin{center} @@ -1432,7 +1441,7 @@ Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet \emph{Schnittmuster}, die in Abschnitt~\ref{sect:anzahl_schnittmuster} definiert wurden, als Individuen. Um zwei Individuen zu rekombinieren werden die ersten $r$~Schnitte des einen Schnittmusters verwendet und die letzten ${c-r}$~Schnitte des zweiten -Schmittmusters. $r$ ist eine Zufallsvariable mit $0 \leqq r \leqq c$. +Schnittmusters. $r$ ist eine Zufallsvariable mit $0 \leqq r \leqq c$. Die Mutation setzt entweder die Leitungsnummer eines Schnitts~$i$ zufällig auf einen neuen Wert $l$ mit $0 \leqq l \le n-i$ oder invertiert die @@ -1675,6 +1684,7 @@ konvertiert werden. Die Verwandtschaft von $\operatorname{PS}(n)$ und \oes{n} untersucht \textit{Moritz Mühlenthaler} ausführlich in~\cite{M2009}. \subsection{Versuche mit dem Odd-Even-Mergesort-Netzwerk} +\label{sect:sn-evolution-cut:oes} In Abschnitt~\ref{sect:anzahl_schnittmuster} wurde bereits untersucht, wie viele \emph{unterschiedliche} Schnittmuster die konstruktiven Sortiernetzwerke @@ -1788,13 +1798,11 @@ Eingängen. In der folgenden Tabelle sind einige schnelle Netzwerke, die von \textsc{SN-Evolution-Cut} generiert werden können, charakterisiert. Die Eingabe für \textsc{SN-Evolution-Cut} war jeweils das \emph{Odd-Even-Mergesort}-Netzwerk mit der doppelten Leitungszahl. -Abbildung~\ref{fig:23-ec-from-oes46} zeigt beispielhaft ein -23-Sortiernetzwerk, das aus \oes{46} generiert wurde. \begin{center} \begin{tabular}{|r|r|r|r|r|} \hline Leitungen & Komparatoren & Schichten & Komparatoren & Schichten \\ -(Resultat) & \textsc{SN-EC} & \textsc{SN-EC} & \oes{n} & \oes{n} \\ + & \textsc{SN-EC} & \textsc{SN-EC} & \oes{n} & \oes{n} \\ \hline 11 & 38 & 9 & 37 & 10 \\ 12 & 43 & 9 & 41 & 10 \\ @@ -1806,6 +1814,14 @@ Leitungen & Komparatoren & Schichten & Komparatoren & Schichten \\ \hline \end{tabular} \end{center} +Abbildung~\ref{fig:23-ec-from-oes46} zeigt beispielhaft ein +23-Sortiernetzwerk, das aus \oes{46} generiert wurde. Bemerkenswert an diesem +Sortiernetzwerk ist insbesondere, dass \textsc{SN-Evolution-Cut} mit der +Eingabe \bs{46} ein besseres Ergebnis liefert als mit der Eingabe \oes{46}. In +beiden Fällen wird ein Sortiernetzwerk zurückgegeben, das im Vergleich zu +\bs{23} beziehungsweise \oes{23} eine Schicht einspart. Allerdings ist das +Sortiernetzwerk auf Basis von \bs{46} (Abbildung~\ref{fig:23-ec-from-bs46}) +effizienter, da es nur 124~Komparatoren benötigt. \begin{figure} \begin{center} @@ -1939,7 +1955,7 @@ Erwartungsgemäß sind die besten Netzwerke, die \textsc{SN-Evolution} mit dem jedoch, dass in dieser Konfiguration Sortiernetzwerke auftreten können, die mehr Komparatoren besitzen als \emph{Odd-Even-Transpositionsort} -- \oet{16} ist aus 120~Komparatoren aufgebaut, bei dem Lauf, der die Daten für -Abbildung~\ref{fig:comparison-comparators} lieferte, traten auch jeweils ein +Abbildung~\ref{fig:comparison-comparators} lieferte, trat auch jeweils ein Sortiernetzwerk mit 121 und 124~Komparatoren auf. Da Sortiernetzwerke mit so vielen Komparatoren im Verlauf des Experiments selbst nach über 100~Millionen Iterationen nicht noch einmal erzeugt wurden, handelt es sich vermutlich um @@ -1988,33 +2004,49 @@ ein Phänomen, das mit der Initialisierung mit dem % \label{fig:markov-cycles-16} %\end{figure} - -\todo{Schreibe noch etwas zu …} -\begin{itemize} - \item Beste erreichte Netzwerke (gleich zu \emph{OE-Mergesort}). - \item Anzahl der erreichbaren Sortiernetzwerke. - \item \textsc{SN-Count-Markov} (ggf) -\end{itemize} - \newpage \section{Fazit und Ausblick} -\todo{Ausformulieren} -\begin{itemize} -\item Mit \textsc{SN-Evolution} und \oem{n} kann man nicht besser werden als - \oes{n}. -\item Mit \textsc{SN-Evolution} und \bm{n} kann man besser werden als \bs{n}. -\item Vermutlich kann man mit \textsc{SN-Evolution} und \bm{n} so gut werden -wie \textsc{SN-Evolution-Cut}, wenn er mit \bs{2n} gestartet wird. -\item Leider sind keine konstruktiven Methoden erkannt worden. -\end{itemize} +Dass sich mithilfe dem Entfernen von Leitungen aus bekannten Sortiernetzwerke +interessante Ergebnisse erzielen lassen, zeige \textit{Moritz Mühlenthaler} +bereits in~\cite{M2009}. Die in dieser Arbeit vorgestellten Methoden und +Resultate machen deutlich, dass sich mit diesem Verfahren noch weitere +interessante Beobachtungen machen lassen. + +Das \emph{Odd-Even-Mergesort}-Netzwerk wird sowohl von \textsc{SN-Evolution}, +\textsc{SN-Evolution-Cut} und \textsc{SN-Markov} erreicht. Wenn die Anzahl der +Leitungen keine Zweierpotenz ist, kann gegebenenfalls ein schnelleres +Sortiernetzwerk erzeugt werden. Einige Beispiele hierfür wurden in +Abschnitt~\ref{sect:sn-evolution-cut:oes} aufgezeigt. + +Das \emph{bitone Mergesort}-Netzwerk kann in Bezug auf Effizienz von den +vorgestellten Algorithmen übertroffen werden. Der Algorithmus +\textsc{SN-Evolution-Cut} kann das Ergebnis von \textit{Mühlenthaler} und +\textit{Wanka} (\cite{MW2010}) für ein 16-Sortiernetzwerk reproduzieren und +für ein 32-Sortiernetzwerk sogar noch übertreffen. Der +\textsc{SN-Evolution}-Algorithmus fand ein 16-Sortiernetzwerk, das gegenüber +dem Ergebnis von \textsc{SN-Evolution-Cut} beziehungsweise~\cite{MW2010} einen +weiteren Komparator einspart. + +Leider weisen die Sortiernetzwerke, die von den angegebenen Algorithmen +zurückgegeben werden, keine Struktur auf, die sich zur Angabe einer +Konstruktionsanweisung eigenen würde. Für das \emph{Pairwise-Sorting}- und das +\emph{Odd-Even-Mergesort}-Netzwerk mit Zweierpotenzen als Leitungszahl wurden +regelmäßige Schnittmuster angegeben, die Sortiernetzwerke ergeben, die so +schnell und effizient sind wie die vergleichbaren \oes{n} und \ps{n} +Netzwerke. + +Die Anzahl der \emph{unterschiedlichen} Schnitte von verschiedenen +Sortiernetzwerken wurde experimentell bestimmt und gezeigt, dass es deutlich +weniger \emph{unterschiedliche} als \emph{mögliche} Schnittmuster gibt. Das +bedeutet im Umkehrschluss, dass die gewonnenen Sortiernetzwerke mit mehreren +unterschiedlichen Schnittmustern erreicht werden können. Die Möglichkeiten, die Evolutionäre Algorithmen bei der Optimierung von Sortiernetzwerken bieten, sind durch die in dieser Arbeit vorgestellten -Herangehensweisen bei weitem nicht erschöpft. - -Im Folgenden werden Ansätze umrissen, mit denen an die Untersuchungen in -dieser Arbeit nahtlos angeknöpft werden könnte. +Herangehensweisen bei weitem nicht erschöpft. Im Folgenden werden Ansätze +umrissen, mit denen an die Untersuchungen in dieser Arbeit nahtlos angeknöpft +werden könnte. \subsection{Ausblick: Das \textit{Pairwise-Sorting}-Netzwerk und \textsc{SN-Evolution}} @@ -2099,10 +2131,13 @@ Jahrzehnten und beim Verfassen dieser Arbeit als sehr flexibel und mächtig erwiesen. Funktionen, die von Kommandozeilen-Programmen zur Verfügung gestellt werden, -sind unter anderem das Erzeugen von Odd-Even-Mergesort-, bitonic Mergesort- -und Pairwise-Sorting-Netzwerken, das Normalisieren von Sortiernetzwerken, -Anwendung von Schnittmustern auf Sortiernetzwerke und Anwendung eines -Komparatornetzwerks auf eine Eingabe-Permutation. +sind unter anderem das Erzeugen des \emph{Odd-Even-Mergesort}-, \emph{bitonen +Mergesort}- und \emph{Pairwise-Sorting}-Netzwerks, das Normalisieren von +Sortiernetzwerken, Anwendung von Schnittmustern auf Sortiernetzwerke und +Anwendung eines Komparatornetzwerks auf eine Eingabepermutation. Das +Darstellen von Sortiernetzwerken wird ebenfalls angeboten, beispielsweise +wurden die Sortiernetzwerke in dieser Arbeit mit dem Kommando \texttt{sn-tex} +visualisiert. \textit{libsortnetwork} kann unter der Web-Adresse \url{http://octo.it/libsortnetwork/} unentgeltlich heruntergeladen werden. -- 2.11.0