X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=c0213f2c4b4596093891772c68de0885916bc83c;hb=c145acd32aa61c8e213cd1a15ccf79bf30563a5e;hp=711684092091b4816cacc7f8c4560c2b499329fc;hpb=e3d11cafeebaaaf9dcf1344bb690cb5b16fcb644;p=diplomarbeit.git diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 7116840..c0213f2 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -75,7 +75,7 @@ \maketitle \begin{abstract} Sortiernetzwerke werden eingeführt und einige bekannte Konstruktionen werden -vorgestellt (Off-Even-Transposition, Bitonic-Merge, Odd-Even-Merge, Pairwise). +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. @@ -175,12 +175,12 @@ Definition handelt es sich bei dem \emph{Komparatornetzwerk} folglich gegebenes Komparatornetzwerk zu finden ist nach heutigem Kenntnisstand jedoch nicht \emph{effizient} möglich. -Beispielsweise sortiert das Komparatornetzwerk in -Abbildung~\ref{fig:09-e2-c24-allbut1} viele der 362.880 möglichen -Eingabepermutationen. Mit dem Gegenbeispiel $(3, 5, 2, 1, 0, 7, 4, 8, 6)$ -lässt sich jedoch leicht beweisen, dass das Komparatornetzwerk die -Sortiereigenschaft \emph{nicht} besitzt, da es in diesem Fall die Folge -$(1, 0, 2, 3, 4, 5, 6, 7, 8)$ ausgibt. +Beispielsweise sortiert das im Rahmen dieser Arbeit entdeckte +Komparatornetzwerk in Abbildung~\ref{fig:09-e2-c24-allbut1} viele der 362.880 +möglichen Eingabepermutationen. Mit dem Gegenbeispiel $(3, 5, 2, 1, 0, 7, 4, +8, 6)$ lässt sich jedoch leicht beweisen, dass das Komparatornetzwerk die +Sortiereigenschaft \emph{nicht} besitzt, da es in diesem Fall die Folge $(1, +0, 2, 3, 4, 5, 6, 7, 8)$ ausgibt. Insgesamt gibt es $n!$~Permutationen von $n$~Elementen. Wenn ein Komparatornetzwerk die Sortiereigenschaft besitzt, bildet es alle diese @@ -189,6 +189,7 @@ Permutationen auf die sortierte Reihenfolge ab. Allerdings wächst $n!$ Permutationen schon bei 16~Leitungen praktisch nicht mehr zu bewerkstelligen ist.\footnote{1.307.674.368.000 Permutationen} +\label{sect:0-1-prinzip} Glücklicherweise reicht es aus, alle möglichen 0-1-Folgen zu überprüfen, wie \textit{Donald~E. Knuth} in \cite{KNUTH} zeigt. Die Beweisidee ist folgende: Angenommen ein Komparatornetzwerk sortiert alle 0-1-Folgen und es gibt eine @@ -206,10 +207,19 @@ Die Eingabe kann mittels 1 & e_j > a_i \end{array} \right. \end{displaymath} -auf eine 0-1-Folge abgebildet werden, die entsprechen der Annahme von +auf eine 0-1-Folge abgebildet werden, die entsprechen der Annahme vom Komparatornetzwerk sortiert wird. Allerdings verändert diese Abbildung das -Verhalten jedes einzelnen Komparators nicht, so dass die Annahme auf einen -Widerspruch geführt wird. +Verhalten jedes einzelnen Komparators nicht: Wenn bei der Permutation eine +Zahl größer als $a_i$ und eine Zahl kleiner oder gleich $a_i$ verglichen +wurden, liegen jetzt entsprechend eine Null und eine Eins an, die genauso +vertauscht werden oder nicht, wie das bei der Permutation der Fall war. Liegen +zwei Nullen oder zwei Einsen an, entsprechen sie zwei Zahlen kleiner als $a_i$ +oder zwei Zahlen größer oder gleich $a_i$. Da im Fall der 0-1-Folge zwei +gleiche Zahlen am Komparator anliegen, dürfen wir davon ausgehen, dass sich +der Komparator so verhält, wie er sich bei der Permutation verhalten hat -- +ohne das Ergebnis zu beeinflussen. Entsprechend kommen an den Ausgängen $i-1$ +und $i$ eine Null und eine Eins in der falschen Reihenfolge an. Das steht im +Widerspruch zu der Annahme, dass alle 0-1-Folgen sortiert werden. Im Gegensatz zum Überprüfen aller möglichen Permutationen, was der Komplexitätsklasse @@ -228,34 +238,35 @@ beschäftigen. 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. +\textit{NP}, das heißt das keine Verfahren bekannt sind, die das Problem +effizient exakt lösbar. Sollte sich herausstellen, dass diese Probleme nicht +in der Komplexitätsklasse~\textit{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~\textit{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 +die beziehungsweise 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 imitieren 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 +ist, bekannte 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. +Nomenklatur, beispielsweise werden konkrete Lösungen für ein Problem als {\em +Individuen} bezeichnet. Die Vorgehensweise lässt sich abstrakt wie folgt beschreiben. Aus einer -bestehenden Lösungsmenge, der {\em Population} werden zufällig Lösungen +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 +eingefügt wird. Die verwendeten Wahrscheinlichkeiten, beispielsweise bei der +{\em Selektion}, sind dabei nicht zwangsläufig gleichverteilt -- üblicherweise werden bessere Lösungen bevorzugt. Zur Bewertung dient die sogenannte {\em Gütefunktion}. @@ -686,7 +697,7 @@ benötigt werden. Das \emph{Odd-Even-Mergesort-Netzwerk} $\operatorname{OES}(n)$ besteht --~wie das \emph{bitone Mergesort-Netzwerk}~-- rekursiv aus kleineren Varianten von sich selbst und einem abschließenden \emph{Odd-Even-Mischer}. Die -effizientesten Sortiernetzwerke in Bezuf auf Komparator- und Schichtzahl +effizientesten Sortiernetzwerke in Bezug auf Komparator- und Schichtzahl entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht $\operatorname{OES}(n)$ aus $\operatorname{OES}\left(\left\lceil\frac{n}{2}\right\rceil\right)$, @@ -716,7 +727,7 @@ die rekursiven Instanzen von $\operatorname{OEM}(4)$, der grüne Block markiert die Komparatoren, die in ersten Rekursionsschritt hinzugefügt werden. Im Allgemeinen ist die Anzahl der Komparatoren, die vom -\emph{Odd-Even-Mergesort-Netzwerk} verwendet wird, $k(n)$, direkt aus der +\emph{Odd-Even-Mergesort-Netz\-werk} verwendet wird, $k(n)$, direkt aus der Definition beziehungsweise der Konstruktionsanleitung abzulesen: \begin{displaymath} k(n) = k\left(\left\lceil\frac{n}{2}\right\rceil\right) @@ -970,7 +981,7 @@ unterschiedlich. Legt man beispielsweise das Minimum auf die unterste Leitung und das Maximum auf die oberste Leitung eines Standard-Sortiernetzwerks, führen beide Reihenfolgen zum selben Ergebnis. -\textit{Moritz Mühlenthaler} zeigt in seiner Arbeit (\todo{Referenz}), dass es +\textit{Moritz Mühlenthaler} zeigt in seiner Arbeit~\cite{M2009}, dass es möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise Maximum vorzubelegen. Dadurch wird die Anzahl der möglichen Schnittmuster reduziert, die Menge der so erzeugbaren Sortiernetzwerke bleibt aber unverändert. Die @@ -1011,7 +1022,7 @@ sich die Resultate auch in der ersten Schicht nicht unterscheiden. \begin{figure} \begin{center} - \includegraphics[viewport=0 0 360 216,width=15cm]{images/count-cuts-16.pdf} + \includegraphics[viewport=0 0 425 262,width=15cm]{images/count-cuts-16.pdf} \end{center} \caption{Anzahl der \emph{unterschiedlichen} Sortiernetzwerke, die durch 8-Schnittmuster aus $\operatorname{OES}(16)$, $\operatorname{BS}(16)$ und @@ -1193,21 +1204,21 @@ Algorithmus vorschnell in Richtung eines lokalen Optimums optimiert. Die in \textsc{SN-Evolution} implementierte Selektion lässt sich mithilfe von Pseudocode wie folgt beschreiben: \begin{verbatim} -Guetesumme := 0 +Gütesumme := 0 Auswahl := (leer) -fuer jedes Individuum in Population +für jedes Individuum in Population { - reziproke Guete := 1.0 / Guete(Individuum) - Wahrscheinlichkeit P := reziproke Guete / (reziproke Guete + Guetesumme) - Guetesumme := Guetesumme + reziproke Guete + reziproke Güte := 1.0 / Guete(Individuum) + Wahrscheinlichkeit P := reziproke Güte / (reziproke Güte + Gütesumme) + Gütesumme := Gütesumme + reziproke Güte mit Wahrscheinlichkeit P { Auswahl := Individuum } } -gebe Auswahl zurueck +gib Auswahl zurück \end{verbatim} \subsection{Rekombination} @@ -1225,7 +1236,7 @@ erhält. \subsection{Mutation} -Zu einem vollständigen evolutionären Algorithmus gehört außerdem eine Mutation +Zu einem vollständigen evolutionären Algorithmus gehört außerdem die 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 @@ -1234,7 +1245,8 @@ 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. +Ausprobieren aller $2^n$~Bitmuster, wie in Abschnitt~\ref{sect:0-1-prinzip} +beschrieben. 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 @@ -1333,7 +1345,7 @@ Mischer mit der Hälfte der Leitungen transformiert. Diese alternativen Mischer sparen im Vergleich zu den Mischern, die nach Batchers Methode konstruiert werden, Komparatoren ein. -Beispeilsweise geben \textit{Mühlenthaler} und \textit{Wanka} ein +Beispielsweise geben \textit{Mühlenthaler} und \textit{Wanka} ein Sortiernetzwerk mit 16~Eingängen an, das mithilfe der alternativen Mischer konstruiert wurde. Dieses Sortiernetzwerk benötigt 68~Komparatoren, 12~weniger als das bitone Mergesort-Netzwerk nach Batchers Methode. Gegenüber Batchers @@ -1527,28 +1539,44 @@ Kante ${E_{0,1} = (V_0, V_1)}$ verbunden, wenn $S_1$ ein \emph{Nachfolger} von $S_0$ ist, das heißt dass man $S_1$ durch die Rekombination von $S_0$ mit sich selbst erzeugen kann. -Wie in Abschnitt~\ref{sect:anzahl_schnittmuster} beschrieben ist die Anzahl -(unterschiedlicher) Schnittmuster und damit die Anzahl der Nachfolger sehr -groß. Wenn $S_0$ ein Sortiernetzwerk mit $n$~Leitungen ist, so hat $S_0$ bis -zu -\begin{displaymath} - 2^n \cdot \left( \begin{array}{c} 2n \\ n \end{array} \right) -\end{displaymath} -Nachfolger. +Wie in Abschnitt~\ref{sect:anzahl_schnittmuster} beschrieben, ist die Anzahl +der \emph{unterschiedlichen} Schnittmuster und damit die Anzahl der Nachfolger +sehr groß. Bei den untersuchten 16-Sortiernetzwerken lag die Anzahl der +Nachfolger zwar noch unter 20000, bei den untersuchten 32-Sortiernetzwerken +wurden jedoch bereits bis zu $2,6 \cdot 10^8$ unterschiedliche Schnittmuster +geschätzt. Der Algorithmus {\sc SN-Markov} legt auf diesem Nachfolger-Graph einen zufälligen Weg (englisch: \textit{random walk}) zurück. Er startet auf einem gegebenen Sortiernetzwerk. Um von einem Sortiernetzwerk zum Nächsten zu gelangen, rekombiniert der Algorithmus das aktuelle Sortiernetzwerk mit sich -selbst und erhält so einen zufälligen Nachfolger. +selbst und erhält so einen zufälligen Nachfolger. In Pseudocode lässt dich der +Algorithmus wie folgt beschreiben: + +\begin{verbatim} +Netzwerk := Eingabe + +für n Iterationen +{ + Nachfolger := kombiniere (Netzwerk, Netzwerk) + Netzwerk := Nachfolger +} + +gib Netzwerk zurück +\end{verbatim} + +\begin{figure} + \begin{center} + \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-cycles-16.pdf} + \end{center} + \caption{Zyklen, die beim \textit{Random Walk} des + \textsc{SN-Markov}-Algorithmus detektiert wurden. Auf der x-Achse sind die + Anzahl der Schritte, die \textsc{SN-Markov} zurückgelegt hat, auf der + y-Achse die Längen der gefundenen Zyklen aufgetragen. Das initiale + Start-Sortiernetzwerk war $\operatorname{OET}(16)$.} + \label{fig:markov-cycles-16} +\end{figure} -\begin{itemize} - \item $n \leftarrow \mathrm{Input}$ - \item \texttt{while} \textit{true} - \begin{itemize} - \item $n \leftarrow \operatorname{recombine} (n, n)$ - \end{itemize} -\end{itemize} \begin{itemize} \item Beste erreichte Netzwerke (gleich zu \emph{OE-Mergesort}). @@ -1559,7 +1587,7 @@ selbst und erhält so einen zufälligen Nachfolger. \begin{figure} \begin{center} - \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-12-pct.pdf} + \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-12-pct.pdf} \end{center} \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 12~Leitungen), die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die @@ -1569,7 +1597,7 @@ selbst und erhält so einen zufälligen Nachfolger. \begin{figure} \begin{center} - \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-14-pct.pdf} + \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-14-pct.pdf} \end{center} \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 14~Leitungen), die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die @@ -1579,7 +1607,7 @@ selbst und erhält so einen zufälligen Nachfolger. \begin{figure} \begin{center} - \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-16-pct.pdf} + \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-16-pct.pdf} \end{center} \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 16~Leitungen), die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die @@ -1587,6 +1615,16 @@ selbst und erhält so einen zufälligen Nachfolger. \label{fig:markov-comparators-16} \end{figure} +\begin{figure} + \begin{center} + \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-18-pct.pdf} + \end{center} + \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 18~Leitungen), + die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die + \emph{Gamma-Verteilung} $f(x - 81)$ mit $k = 10,724$ und $\theta = 0,766$.} + \label{fig:markov-comparators-18} +\end{figure} + \newpage \section{Empirische Beobachtungen}