X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=e0a902c09c1bf627bf30b7888f7a489bf776132b;hb=571050fa4c8c889abbd5fcf975da8a59dae20920;hp=7dce1ff8c57212ffc11fa0b7310bd2ca9f1b47e6;hpb=000fbb9bcc639c35182711183d50d0cc46916aee;p=diplomarbeit.git diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 7dce1ff..e0a902c 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -90,7 +90,7 @@ 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.} +das hin bekomme bzw. Recht behalte.} \end{abstract} \newpage @@ -106,7 +106,7 @@ Personen ohne Zugang zum Thema beziehungsweise der theoretischen Informatik schnell verstanden werden kann. Eine Einführung wird in Abschnitt~\ref{sect:einleitung_sortiernetzwerke} gegeben. Nichtsdestotrotz ist das Finden von Sortiernetzwerken sowie das Beweisen, dass ein -Komparatornetzwerk jede beliegibe Eingabe sortiert, im Allgemeinen sehr +Komparatornetzwerk jede beliebige Eingabe sortiert, im Allgemeinen sehr schwierig und nach heutigem Kenntnisstand nur mit exponentiellem Aufwand zu bewältigen. @@ -161,11 +161,11 @@ verschiedene Eingänge und vier Ausgänge. Die Ein- und Ausgänge werden durch eine horizontale Linie dargestellt und als \emph{Leitung} bezeichnet. Die \emph{Komparatoren} sind durch vertikale Pfeile dargestellt und verbinden je zwei verschiedene \emph{Leitungen} miteinander. Die Verbindungsstellen von -\emph{Leitungen} und \emph{Komparatoren} sind zur besseren Übersichlichkeit +\emph{Leitungen} und \emph{Komparatoren} sind zur besseren Übersichtlichkeit durch schwarze Punkte symbolisiert. Auf der linken Seite befinden sich die Eingänge. Hier wird eine Zahlenfolge in -das Netzwerk hineingegeben. Jeder Komparator vergleicht die Zahlen „auf“ den +das Netzwerk hinein gegeben. Jeder Komparator vergleicht die Zahlen „auf“ den beiden Leitungen, die er verbindet. 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. @@ -175,7 +175,7 @@ gleichzeitig angewandt werden. Das Beispiel in Abbildung~\ref{fig:einfaches_komparatornetzwerk} verwendet diesen Umstand und vergleicht die zwei oberen und die zwei unteren Leitungen gleichzeitig. Eine Gruppe von Komparatoren, die gleichzeitig angewendet werden können, nennt man -eine \emph{Schicht} des Komparatornetwerks. Die \emph{Verzögerung} eines +eine \emph{Schicht} des Komparatornetzwerks. Die \emph{Verzögerung} eines Komparatornetzwerks ist gleichbedeutend mit der Anzahl der Schichten, in die sich die Komparatoren mindestens gruppieren lassen, da sie die Anzahl der benötigten parallelen Schritte darstellt. @@ -184,7 +184,7 @@ benötigten parallelen Schritte darstellt. erzeugen, die der Sortierung der Eingabe entspricht, heißen \emph{Sortiernetzwerke}. Das in Abbildung~\ref{fig:einfaches_komparatornetzwerk} gezeigte Komparatornetzwerk -ist \emph{kein} Sotiernetzwerk: Die Eingabefolge ${(1, 2, 3, 4)}$ führt zur +ist \emph{kein} Sortiernetzwerk: Die Eingabefolge ${(1, 2, 3, 4)}$ führt zur Ausgabe ${(2, 1, 3, 4)}$ -- die bestehenden Sortierung wird also sogar zerstört. @@ -263,7 +263,7 @@ ob ein Komparatornetzwerk mit 16~Leitungen die Sortiereigenschaft besitzt, sind mit dieser Methode nur 65.536 Tests notwendig -- eine Zahl, die für aktuelle Prozessoren keine Herausforderung darstellt. Für die Überprüfung eines Komparatornetzwerks mit 32~Leitungen sind jedoch bereits etwa -4,3~Millarden Tests notwendig, die einen Rechner durchaus mehrere Minuten +4,3~Milliarden Tests notwendig, die einen Rechner durchaus mehrere Minuten beschäftigen. \subsubsection{Evolutionäre Algorithmen} @@ -282,9 +282,9 @@ gefunden werden. Aus diesem Grund besteht die Notwendigkeit einen Kompromiss einzugehen: Statt 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. +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, bekannte Lösungen zu neuen -- unter Umständen besseren -- Lösungen zu @@ -366,7 +366,7 @@ Evolutionäre Algorithmen wurden bereits mehrfach eingesetzt, um Sortiernetzwerke zu untersuchen. \textit{W.~Daniel Hillis} verwendete \emph{Co-Evolution} um neben Komparatornetzwerken auch „schwierige Eingaben“ zu optimieren~\cite{H1992}. Diese \emph{Parasiten} genannten Eingaben wurden -daran gemessen, bei wievielen Komparatornetzwerken sie beweisen konnten, dass +daran gemessen, bei wie vielen Komparatornetzwerken sie beweisen konnten, dass sie keine Sortiernetzwerke sind. So mussten bei neuen Individuen~/ Komparatornetzwerken nicht alle 0-1-Folgen, sondern nur erfolgreiche Parasiten~/ schwierige Eingaben überprüft werden. Auf diese Art und Weise @@ -383,13 +383,13 @@ anzugeben, das in Abbildung~\ref{fig:16-hillis} zu sehen ist. \label{fig:13-juille} \end{figure} \textit{Hugues Juillé} entwickelte ein Verfahren, das er \emph{Evolving -Non-Determinism} (END) nannte. Dabei handelt es sich nicht um einen -\emph{Evolutionären Algorithmus}, wie sie hier vorgestellt wurden, sondern um -eine verteilte, probabilistische Breitensuche, die an die \emph{Strahlsuche} -(englisch: \textit{beam search}), ein Verfahren der Künstlichen Intelligenz, -angelehnt ist. Die aufwendigste Operation bei diesem Ansatz ist die -Bewertungsfunktion, die abschätzt, wieviele Komparatoren zu einem -Komparatornetzwerk hinzugefügt werden müssen, um ein Sortiernetzwerk zu +Non-Determinism} (END) nannte~\cite{J1995}. Dabei handelt es sich nicht um +einen \emph{Evolutionären Algorithmus}, wie sie hier vorgestellt wurden, +sondern um eine verteilte, probabilistische Breitensuche, die an die +\emph{Strahlsuche} (englisch: \textit{beam search}), ein Verfahren der +Künstlichen Intelligenz, angelehnt ist. Die aufwendigste Operation bei diesem +Ansatz ist die Bewertungsfunktion, die abschätzt, wie viele Komparatoren zu +einem Komparatornetzwerk hinzugefügt werden müssen, um ein Sortiernetzwerk zu erhalten. Mit diesem Ansatz gelang es \textit{Juillé} zwei 13-Sortiernetzwerke anzugeben, die mit 45~Komparatoren effizienter sind als alle bis dahin Bekannten (Abbildung~\ref{fig:13-juille}). @@ -419,11 +419,11 @@ ${n = 8}$ Leitungen. \label{fig:odd-even-transposition-08} \end{figure} -Dass das Odd-Even-Transporitionsort-Netzwerk tatsächlich jede beliegibe +Dass das Odd-Even-Transpositionsort-Netzwerk tatsächlich jede beliebige Eingabe sortiert ist nicht offensichtlich. Leicht zu sehen ist jedoch, dass sowohl das Minimum als auch das Maximum durch das im Netzwerk enthaltene Treppenmuster auf die unterste beziehungsweise oberste Leitung gelangt. Beim -Odd-Even-Transporitionsort-Netzwerk mit drei Eingängen, +Odd-Even-Transpositionsort-Netzwerk mit drei Eingängen, $\operatorname{OET}(3)$, ist die Ausgabe folglich sortiert. Die Sortiereigenschaft größerer OET-Netzwerke lässt sich rekursiv beweisen, @@ -433,7 +433,7 @@ Abschnitt~\ref{sect:leitungen_entfernen} wird das Vorgehen im Detail beschrieben, Abbildung~\ref{fig:oe-transposition-cut} zeigt das Herausschneiden einer Leitung aus $\operatorname{OET}(8)$. -Das Odd-Even-Transporitionsort-Netzwerk ist weder in Bezug auf die Anzahl der +Das Odd-Even-Transpositionsort-Netzwerk ist weder in Bezug auf die Anzahl der Komparatoren noch in Bezug auf die Anzahl der Schichten, in denen sich die Komparatoren anordnen lassen, effizient. Es benötigt ${\frac12 n (n-1)} = \mathcal{O}(n^2)$~Komparatoren, die in $n$~Schichten @@ -541,7 +541,7 @@ Der bitonen Mischer kann auch zwei aufsteigende Folgen sortieren. Dazu ist lediglich eine etwas modifizierte Vergleichs-Kaskade im ersten Schritt notwendig. Die folgenden, kleineren Mischer erhalten als Eingabe wieder eine „echte“ bitone Folge. Abbildung~\ref{fig:bitonic-merge-tricheter} zeigt das -Schema des bitonen Mischers für zwei aufsteigend sortierte Foglen. Durch das +Schema des bitonen Mischers für zwei aufsteigend sortierte Folgen. Durch das Umdrehen einer Folge verändert sich das Muster der Komparatoren ein wenig: Statt an eine Treppe erinnert das Muster nun an einen Trichter. @@ -605,7 +605,7 @@ darin, dass es ebenfalls rekursiv durch einen Mischer definiert ist. \subsubsection{Der \emph{Odd-Even}-Mischer}\label{sect:der_odd_even_mischer} Der \emph{Odd-Even}-Mischer $\operatorname{OEM}(n,m)$ ist ein -Komperatornetzwerk, dass zwei sortierte Folgen mit $n$ beziehungsweise $m$ +Komparatornetzwerk, dass zwei sortierte Folgen mit $n$ beziehungsweise $m$ Elementen zu einer sortierten Ausgabefolge mit $N = n+m$~Elementen zusammenfügen kann. Dabei kommt es mit weniger Vergleichen aus als der \emph{bitone Mischer}, der im Abschnitt~\ref{sect:der_bitone_mischer} @@ -631,7 +631,7 @@ w_i = \left\{ \begin{array}{ll} \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.} + aus. Der Effekt wird durch den rekursiven Aufbau noch verstärkt.} \label{fig:oe-merge} \end{figure} @@ -696,7 +696,7 @@ $W_{\textrm{gerade}}$ und $W_{\textrm{ungerade}}$ entsprechend zu: 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}}$ zwei Nullen mehr enthählt als +wenn $W_{\textrm{gerade}}$ zwei Nullen mehr enthält als $W_{\textrm{ungerade}}$, muss genau eine Vertauschung stattfinden, um die Ausgabe zu sortieren. Diese wird von den Komparatoren, die benachbarte Leitungen miteinander vergleichen, ausgeführt. Die jeweiligen Situationen sind @@ -875,7 +875,7 @@ 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. Statt dem typischen "`Treppenmuster"' sind abwechselnd das Treppen- +Richtung. Statt dem typischen „Treppenmuster“ sind abwechselnd das Treppen- und das Trichtermuster zu sehen. \subsection{Zwei Netzwerke kombinieren} @@ -941,12 +941,12 @@ Sortiernetzwerk mit $n$~Eingängen erhalten müssen. Man kann ein gegebenes Sortiernetzwerk mit $n$~Eingängen auf ein Sortiernetzwerk mit ${n-1}$~Leitungen verkleinern, indem man eine Leitung „eliminiert“. Dazu nehmen wir an, dass das Minimum oder das Maximum an einem -bestimmten Eingang anliegt. Der Weg, den das Minimum beziehungsweise das Maxim -durch das Sortiernetzwerk nimmt, ist eindeutig bestimmt und endet an einem der -„Ränder“, also auf der Leitung mit dem höchsten oder dem niedrigsten Index. -Insbesondere ist bekannt, welche Komparatoren „berührt“ werden und welche -dafür sorgen, dass der Wert die Leitung gewechselt, da das Minimum jeden -Vergleich „verliert“ und das Maximum jeden Vergleich „gewinnt“. Die +bestimmten Eingang anliegt. Der Weg, den das Minimum beziehungsweise das +Maximum durch das Sortiernetzwerk nimmt, ist eindeutig bestimmt und endet an +einem der „Ränder“, also auf der Leitung mit dem höchsten oder dem niedrigsten +Index. Insbesondere ist bekannt, welche Komparatoren „berührt“ werden und +welche dafür sorgen, dass der Wert die Leitung gewechselt, da das Minimum +jeden Vergleich „verliert“ und das Maximum jeden Vergleich „gewinnt“. Die Abbildung~\ref{fig:oe-transposition-cut0} zeigt den Weg eines Maximums durch das {\em Odd-Even-Transpositionsort-Netzwerk}. @@ -954,7 +954,7 @@ das {\em Odd-Even-Transpositionsort-Netzwerk}. \centering \subfigure[Auf der Leitung~4 wird $-\infty$ angelegt. Dadurch ist der Pfad durch das Sortiernetzwerk eindeutig festgelegt.]{\input{images/oe-transposition-cut0.tex}\label{fig:oe-transposition-cut0}} - \subfigure[Komparatoren, die einen wechsel der Leitungen bewirken, werden + \subfigure[Komparatoren, die einen Wechsel der Leitungen bewirken, werden durch sich kreuzende Leitungen ersetzt.]{\input{images/oe-transposition-cut1.tex}\label{fig:oe-transposition-cut1}} \subfigure[Leitung~4 wurde entfernt. Übrig bleibt ein Sortiernetzwerk mit 7~Leitungen.]{\input{images/oe-transposition-cut2.tex}\label{fig:oe-transposition-cut2}} @@ -965,7 +965,7 @@ das {\em Odd-Even-Transpositionsort-Netzwerk}. 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 \oet{7} markiert.} + heraus getrennt werden. In der letzten Abbildung ist \oet{7} markiert.} \label{fig:oe-transposition-cut} \end{figure} @@ -980,10 +980,10 @@ auf die keine Komparatoren mehr berührt (Abbildung~\ref{fig:oe-transposition-cut1}). Die Werte auf den verbleibenden $(n-1)$~Leitungen müssen vom restlichen -Komparatornetzwerk immernoch sortiert werden: Wir haben lediglich die Position -des Minimums oder des Maximums angenommen. Ein Sortiernetzwerk muss die -Eingabe sortieren, egal auf welcher Leitung das Minimum~/ das Maximum liegt. -Wir haben lediglich angefangen, das Sortiernetzwerk unter diese Annahme +Komparatornetzwerk immer noch sortiert werden: Wir haben lediglich die +Position des Minimums oder des Maximums angenommen. Ein Sortiernetzwerk muss +die Eingabe sortieren, egal auf welcher Leitung das Minimum~/ das Maximum +liegt. Wir haben lediglich angefangen, das Sortiernetzwerk unter diese Annahme auszuwerten -- über die verbleibenden Eingänge haben wir keine Aussage getroffen. Entsprechend müssen die verbleibenden Ausgänge eine sortierte Liste mit $(n-1)$~Elementen darstellen. @@ -998,7 +998,7 @@ einer Leitung als \emph{Minimum-Schnitt} beziehungsweise 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 +Darstellung ergibt. Außerdem ist das \emph{Odd-Even-Transpositionsort}-Netzwerk für sieben Werte markiert. Der zusätzliche Komparator vor dem \oet{7} hat keinen Einfluss auf die Ausgabe und kann entfernt werden. @@ -1056,7 +1056,7 @@ Schnittmuster: Die Anzahl der möglichen Schnittmuster wird mit der Anzahl der zu entfernenden Leitungen sehr schnell sehr groß. Um ein Sortiernetzwerk mit 32~Eingängen auf -ein Sortiernetzwerk mit 16~Eingängen zu reduzieren, ist ein Schmittmuster mit +ein Sortiernetzwerk mit 16~Eingängen zu reduzieren, ist ein Schnittmuster mit 16~Schnitten notwendig, für das es bereits etwa ${3,939 \cdot 10^{13}}$ Möglichkeiten gibt. Ein Ausprobieren aller Möglichkeiten ist für große Netzwerke nicht oder nur unter erheblichem Ressourcenaufwand möglich. @@ -1070,7 +1070,7 @@ der gleiche Wert angelegt wird, und sechs Konfigurationen, bei denen sich die Werte unterscheiden. Bei diesen letzten sechs Konfigurationen werden je zwei auf das selbe -Ausgangmuster abgebildet, weil die Position des Minimums beziehungsweise des +Ausgangsmuster abgebildet, weil die Position des Minimums beziehungsweise des Maximums durch den Komparator vorgegeben wird. Das heißt, dass die neun unterschiedlichen Eingangsmuster nur sechs unterschiedliche Ausgangsmuster erzeugen. In der zweiten und allen folgenden Schichten kann man diesen @@ -1135,14 +1135,14 @@ $k$~unterschiedlichen Schnittmustern. Anschließend werden $n$~Schnittmuster zufällig erzeugt und überprüft, ob sie in der Menge~$S$ enthalten sind. Unter der Annahme, dass das Verhältnis der zufälligen Schnittmuster, die in $S$ enthalten sind, und $n$ dem Verhältnis von $k$ und der Anzahl der -unterschiedlichen Schnittmuster ingesamt entspricht, kann man die Anzahl der +unterschiedlichen Schnittmuster insgesamt entspricht, kann man die Anzahl der unterschiedlichen Schnittmuster abschätzen. \begin{figure} \begin{center} \includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-10000-1000000-32.pdf} \end{center} - \caption{Abschnätzung der unterschiedlichen Schnittmuster mit der + \caption{Abschätzung der unterschiedlichen Schnittmuster mit der \emph{Monte-Carlo-Methode} für $\operatorname{OES}(32)$ und $\operatorname{BS}(32)$.} \label{fig:collisions-10000-1000000-32} @@ -1164,7 +1164,7 @@ und $3,4 \cdot 10^6$ für $\operatorname{BS}(32)$. \begin{center} \includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-100000-1000000-32-ps.pdf} \end{center} - \caption{Abschnätzung der unterschiedlichen Schnittmuster mit der + \caption{Abschätzung der unterschiedlichen Schnittmuster mit der \emph{Monte-Carlo-Methode} für $\operatorname{PS}(32)$. 385 von 1.000.000 zufälligen Schnittmustern waren äquivalent zu einem Schnittmuster in einer Menge von 100.000. Daraus ergibt sich eine Schätzung von $2,6 \cdot 10^8$ @@ -1182,12 +1182,12 @@ Anzahl für $\operatorname{OES}(16)$ beziehungsweise $\operatorname{BS}(16)$, ist dieser Umstand wenig verwunderlich. Entsprechend hätte man in einem kombinierten Graphen keine Details mehr erkennen können. Aufgrund der hohen Anzahl unterschiedlicher Schnittmuster, wurde für das gleiche Experiment mit -$\operatorname{PS}(32)$ eine initiale Menge von 100.000 unterschiedilchen +$\operatorname{PS}(32)$ eine initiale Menge von 100.000 unterschiedlichen Schnittmustern erzeugt. Trotzdem wurden nach 1.000.000 Iterationen nur 385 Schnittmuster gefunden, die zu einem Schnittmuster in der Menge äquivalent sind. Daraus ergibt sich eine Abschätzung von $2,6 \cdot 10^8$ unterschiedlichen Schnittmustern -- zwei Zehnerpotenzen mehr als bei den -vorherigen Sortiernetzwerken, aber immernoch fünf Zehnerpotenzen kleiner als +vorherigen Sortiernetzwerken, aber immer noch fünf Zehnerpotenzen kleiner als die Anzahl der \emph{möglichen} Schnittmuster. \newpage @@ -1204,7 +1204,7 @@ in Abschnitt~\ref{sect:bewertung} behandelt. \subsection{Bewertungsfunktion}\label{sect:bewertung} Um Sortiernetzwerke überhaupt optimieren zu können, muss zunächst die -{\em Güte} eines Netzwerkes definiert werden. Prinzipiell gibt es zwei Ziele, +{\em Güte} eines Netzwerks definiert werden. Prinzipiell gibt es zwei Ziele, die bei Sortiernetzwerken verfolgt werden können: \begin{itemize} \item Möglichst wenige Komparatoren („effizient“) @@ -1316,7 +1316,7 @@ eine Überprüfung eingebaut: Unmittelbar vor dem Einfügen in die Population wird nacheinander jeder Komparator entfernt und überprüft, ob das verbleibende Netzwerk die Sortiereigenschaft noch besitzt. -Trotz des hohen Rechenaufwandes -- bei 16-Sortiernetzwerken sind gut +Trotz des hohen Rechenaufwands -- bei 16-Sortiernetzwerken sind gut 4~Millionen Tests notwendig, um alle Komparatoren zu überprüfen -- waren die Ergebnisse ernüchternd: Nach circa 1~Million Iterationen mit 16-Sortiernetzwerken fand der so modifizierte Algorithmus keinen einzigen @@ -1354,9 +1354,9 @@ Verwendet man den \emph{bitonen Mischer} in der Rekombinationsphase von Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte: Der Algorithmus wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk als triviale Initiallösung gestartet. Das Ergebnis ist ein Netzwerk, das effizienter ist -als das bitone Mergesort-Netzwerk: $\operatorname{BS}(16)$ benötigt -80~Komparatoren, das Sortiernetzwerk in -Abbildung~\ref{fig:16-e1-bitonic-1296542566} benötigt lediglich~67. +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} @@ -1382,8 +1382,6 @@ Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen. Ein Netzwerk, das $\operatorname{OES}(n)$ in mindestens einem Merkmal übertrifft, konnte jedoch nicht beobachtet werden. -\todo{Ggf. Abschnitt „Shmoo-Äquivalenz“ kürzen und hier einbauen.} - %\begin{figure} %\begin{center} %\input{images/08-e2-1237993371.tex} @@ -1436,13 +1434,13 @@ 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$. -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 +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 Schnitt-Richtung. \subsection{Versuche mit dem bitonen Mergesort-Netzwerk} -In \cite{MW2010} zeigen \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka}, +\textit{Moritz Mühlenthaler} und \textit{Rolf Wanka} zeigen in~\cite{MW2010}, wie man einen bitonen Mischer, der nach Batchers Methode konstruiert wurde, durch systematisches Entfernen von Leitungen in einen ebenfalls bitonen Mischer mit der Hälfte der Leitungen transformiert. Diese alternativen Mischer @@ -1452,9 +1450,9 @@ werden, Komparatoren 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 -Methode sparen so konstruierte Sortiernetzwerke ${\frac{1}{4}n(\log n - 1)}$ -Komparatoren ein. +als das \emph{bitone Mergesort}-Netzwerk nach Batchers Methode. Gegenüber +Batchers Methode sparen so konstruierte Sortiernetzwerke ${\frac{1}{4}n(\log n +- 1)}$ Komparatoren ein. \begin{figure} \begin{center} @@ -1530,8 +1528,8 @@ Leider sind die Schnittmuster, die \textsc{SN-Evolution-Cut} ausgibt, sehr unregelmäßig. Bisher ist es nicht gelungen eine Konstruktionsanweisung für gute Schnittmuster anzugeben. -Entscheidend für das Ergebnis eines Schnittmusters scheint beim bitonen -Mergesort-Netzwerk die Aufteilung der Minimum- und Maximumschnitte zu sein. +Entscheidend für das Ergebnis eines Schnittmusters scheint beim \emph{bitonen +Mergesort}-Netzwerk die Aufteilung der Minimum- und Maximumschnitte zu sein. Von Hundert 16-Schnittmustern für $\operatorname{BS}(32)$, die in Sortiernetzwerken mit 68~Komparatoren in 10~Schichten resultieren, hatten 73 ein Verhältnis von $5/11$, 13 hatten ein Verhältnis von $4/12$ und 14 hatten @@ -1540,6 +1538,57 @@ die Schnittmuster aufgrund der Symmetrie des bitonen Mergesort-Netzwerks leicht invertieren lassen, werden der Fall, dass es mehr Minimumschnitte, und der Fall, dass es mehr Maximumschnitte gibt, nicht unterschieden. +\begin{figure} + \centering + \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 9~Schichten. Das + Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{22} erzeugt.]{\input{images/11-ec-from-bs22-fast.tex}\label{fig:11-ec-from-bs22-fast}} + \subfigure[12-Sortiernetzwerk aus 42~Komparatoren in 9~Schichten. Das + Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{24} erzeugt.]{\input{images/12-ec-from-bs24-fast.tex}\label{fig:12-ec-from-bs24-fast}} + \caption{Startet man \textsc{SN-Evolution-Cut} mit \bs{22} und \bs{24}, kann + der Algorithmus schnelle Sortiernetzwerke ausgeben.} + \label{fig:11-12-ec-from-bs22-bs24} +\end{figure} + +Verwendet man als Eingabe für \textsc{SN-Evolution-Cut} Instanzen des +\emph{bitonen Mergesort}-Netzwerks, deren Leitungszahl keine Zweierpotenz ist, +können Sortiernetzwerke zurückgegeben werden, die sowohl schneller als auch +effizienter als das entsprechende \emph{bitone Mergesort}-Netzwerk sind. Die +folgende Tabelle listet einige interessante Fälle auf. Die Eingabe für +\textsc{SN-Evolution-Cut} war jeweils das \emph{bitone Mergesort}-Netzwerk mit +der doppelten Leitungszahl. +Abbildung~\ref{fig:23-ec-from-bs46} zeigt beispielhaft ein +23-Sortiernetzwerk, das aus \bs{46} generiert wurde. +\begin{center} +\begin{tabular}{|r|r|r|r|r|} +\hline +Leitungen & Komparatoren & Schichten & Komparatoren & Schichten \\ + & \textsc{SN-EC} & \textsc{SN-EC} & \bs{n} & + \bs{n} \\ +\hline +11 & 37 & 9 & 39 & 10 \\ +12 & 42 & 9 & 46 & 10 \\ +19 & 93 & 13 & 98 & 14 \\ +20 & 102 & 13 & 106 & 14 \\ +% 20: # sn-cut 2:MAX 3:MIN 4:MIN 9:MIN 10:MIN 13:MIN 14:MIN 15:MIN 19:MIN 20:MAX 24:MAX 26:MIN 27:MAX 29:MIN 31:MAX 33:MIN 34:MAX 35:MIN 37:MIN 39:MAX +21 & 109 & 14 & 114 & 15 \\ +22 & 116 & 14 & 123 & 15 \\ +23 & 124 & 14 & 133 & 15 \\ +\hline +\end{tabular} +\end{center} + +\begin{figure} + \begin{center} + \input{images/23-ec-from-bs46-fast.tex} + \end{center} + \caption{23-Sortiernetzwerk mit 124~Komparatoren in 14~Schichten. Das + Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{46} mit dem + Schnittmuster $\operatorname{MIN}(2, 4, 9, 12, 20, 22, 28, 30, 32, 33, 37, + 38, 41)$, $\operatorname{MAX}(1, 5, 16, 19, 21, 24, 25, 35, 36, 43)$ + erzeugt.} + \label{fig:23-ec-from-bs46} +\end{figure} + Dass die Ergebnisse von \textsc{SN-Evolution-Cut} keine erkennbare Struktur haben, ist jedoch kein Eigenschaft des Algorithmus, sondern hängt insbesondere von der Eingabe ab. Wird \textsc{SN-Evolution-Cut} beispielsweise mit dem @@ -1547,17 +1596,6 @@ von der Eingabe ab. Wird \textsc{SN-Evolution-Cut} beispielsweise mit dem $m$~Schnitten gestartet, so ist das beste Ergebnis immer das $\operatorname{OET}(n-m)$-Netzwerk. -\begin{figure} - \begin{center} - \input{images/16-ec-from-ps32.tex} - \end{center} - \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in - 10~Schichten. Das Netzwerk wurde von dem Algorithmus - \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting-Netzwerk} - $\operatorname{PS}(32)$ durch 16~Schnitte erzeugt.} - \label{fig:16-ec-from-ps32} -\end{figure} - \subsection{Versuche mit dem Pairwise-Sorting-Netzwerk} Anders verhält sich das \emph{Pairwise-Sorting-Netzwerk} @@ -1569,12 +1607,23 @@ Anzahl an Komparatoren und Schichten hat wie $\operatorname{PS}(16)$ und $\operatorname{OES}(16)$. Eines dieser Sortiernetzwerke ist in Abbildung~\ref{fig:16-ec-from-ps32} dargestellt. +\begin{figure} + \begin{center} + \input{images/16-ec-from-ps32.tex} + \end{center} + \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in + 10~Schichten. Das Netzwerk wurde von dem Algorithmus + \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting-Netzwerk} + $\operatorname{PS}(32)$ durch 16~Schnitte erzeugt.} + \label{fig:16-ec-from-ps32} +\end{figure} + Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even}-Mischer nicht einsetzt und auch nicht auf einem Mischer basiert, ist der $\operatorname{OEM}(8,8)$ im Sortiernetzwerk in Abbildung~\ref{fig:16-ec-from-ps32} eindeutig erkennbar (Schichten~7--10). In -den Schichten~1--6 erkennt man zwei unabhängige Sortiernetzerke, die -strukturell identisch zu $\operatorname{PS}(8)$ sind -- lediglich die +den Schichten~1--6 erkennt man zwei unabhängige Sortiernetzwerke, die +strukturell sehr ähnlich zu $\operatorname{PS}(8)$ sind -- lediglich die Schichten~1 und~2 sowie 4~und~5 sind vertauscht. \begin{figure} @@ -1622,7 +1671,7 @@ $\operatorname{PS}(16)$ anwendet: In diesem Fall kann man durch ein 8-Schnittmuster das \emph{Odd-Even-Mergesort}-Netzwerk \oes{8} erhalten. Für größere Sortiernetzwerke ist dies hingegen nicht mehr möglich, beispielsweise kann $\operatorname{PS}(32)$ nicht durch ein 16-Schnittmuster in \oes{16} -konvertiert werden. Die Verwandschaft von $\operatorname{PS}(n)$ und \oes{n} +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} @@ -1634,12 +1683,17 @@ besitzen. Eines der Ergebnisse war, dass von diesen Sortiernetzwerken das \emph{Odd-Even-Mergesort}-Netzwerk die wenigsten unterschiedlichen 16-Schnittmuster besitzt -- nur etwa $5,2$~Millionen. Entsprechend ist es wenig verwunderlich, dass \textsc{SN-Evolution-Cut} gestartet mit -$\operatorname{OES}(32)$ sehr schnell ein gutes 16-Schnittmuster findet. - -Eines der eher zufälligen Schnittmuster ist $\operatorname{MIN}(1, 6, 11, 14, -17, 23, 26, 29)$, $\operatorname{MAX}(2, 7, 8,$ $13, 18, 21, 27, 31)$. Das -Schnittmuster ist in Abbildung~\ref{fig:16-ec-from-oes32-cut} veranschaulicht, -das resultierende Netzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32} zu sehen. +$\operatorname{OES}(32)$ sehr schnell\footnote{Auf dem Computer, auf dem diese +Arbeit geschrieben wurde, dauerte es in den meisten Fällen weniger als eine +Sekunde bis ein entsprechendes Schnittmuster gefunden wurde.} ein gutes +16-Schnittmuster findet. + +Eines der 16-Schnittmuster für \oes{32}, die ein Sortiernetzwerk erzeugen, das +bezüglich Effizienz und Geschwindigkeit identisch ist zu \oes{16}, ist +$\operatorname{MIN}(1, 6, 11, 14, 17, 23, 26, 29)$, $\operatorname{MAX}(2, 7, +8,$ $13, 18, 21, 27, 31)$. Das Schnittmuster ist in +Abbildung~\ref{fig:16-ec-from-oes32-cut} veranschaulicht, das resultierende +Netzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32} zu sehen. \begin{figure} \begin{center} @@ -1662,6 +1716,109 @@ das resultierende Netzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32} zu sehen. \label{fig:16-ec-from-oes32} \end{figure} +Bei diesem Schnittmuster fällt auf, dass es für jeweils vier Eingänge (0--3, +4--7, \dots, 28--31) einen Minimum- und einen Maximumschnitt gibt. Aus dieser +Beobachtung kann man das regelmäßige Schnittmuster +\begin{displaymath} +\textit{Eingang}_i = \left\{ \begin{array}{rl} + \infty & \quad \textrm{falls } i \bmod 4 = 0 \\ + -\infty & \quad \textrm{falls } i \bmod 4 = 3 \\ + ? & \quad \mathrm{sonst} + \end{array} \right. +\end{displaymath} +ableiten. Es entfernt die Hälfte der Leitungen, vorausgesetzt die Anzahl der +Leitungen ist durch Vier teilbar. Das Schnittmuster erzeugt effiziente +Netzwerke, wenn die Anzahl der Leitungen $n = 2^d$ eine Zweierpotenz ist. Ein +32-Sortiernetzwerk, das mit diesem Schnittmuster aus \oes{64} erzeugt wurde, +ist in Abbildung~\ref{fig:32-ec-from-oes64} zu sehen. + +\begin{figure} + \begin{center} + \input{images/32-ec-from-oes64.tex} + \end{center} + \caption{32-Sortiernetzwerk mit 191~Komparatoren in 15~Schichten. + Das Netzwerk wurde mit einem regelmäßigen Schnittmuster aus dem + \emph{Odd-Even-Mergesort}-Netzwerk \oes{64} erzeugt.} + \label{fig:32-ec-from-oes64} +\end{figure} + +Wenn die Anzahl der Leitungen keine Zweierpotenz ist, erreichen die so +erzeugten Sortiernetzwerke die Effizienz des +\emph{Odd-Even-Mergesort}-Netzwerks nicht. Wendet man das Schnittmuster +beispielsweise auf \oes{24} an, so erhält man ein Sortiernetzwerk mit +43~Komparatoren -- \oes{12} kommt mit 41~Komparatoren aus. Die Geschwindigkeit +beider Sortiernetzwerke ist mit 10~Schichten identisch. + +Startet man hingegen den \textsc{SN-Evolution-Cut}-Algorithmus mit \oes{24} +und dem Ziel, ein gutes 12-Schnittmuster zu finden, hängt die Ausgabe von der +verwendeten Gütefunktion ab. Werden effiziente Netzwerke bevorzugt, findet der +Algorithmus Schnittmuster wie $\operatorname{MIN}(6, 7, 8, 9, 16, 17, 20, +22)$, $\operatorname{MAX}(2, 4, 12, 14)$, dessen Ergebnis in +Abbildung~\ref{12-ec-from-oes24-efficient} zu sehen ist. Das resultierende +Sortiernetzwerk besteht aus 41~Komparatoren, die in 10~Schichten angeordnet +werden können. Damit ist das Netzwerk bezüglich Effizienz und Geschwindigkeit +gleichauf mit \oes{12}. Werden hingegen schnelle Sortiernetzwerke bevorzugt, +werden stattdessen Schnittmuster wie $\operatorname{MIN}(6, 7, 11, 12, 15, +16)$, $\operatorname{MAX}(1, 3, 10, 17, 20, 23)$ ausgegeben. Das Ergebnis +dieses Schnittmusters ist in Abbildung~\ref{fig:12-ec-from-oes24-fast} zu +sehen. Das Sortiernetzwerk besteht aus 43~Komparatoren, die in 9~Schichten +angeordnet sind. Das heißt, dass das resultierende Netzwerk zwar nicht so +effizient wie \oes{12} ist, dafür aber schneller als \oes{12} und \bs{12}. + +\begin{figure} + \centering + \subfigure[Schnelles 12-Sortiernetzwerk aus 43~Komparatoren in 9~Schichten, + das von \textsc{SN-Evolution-Cut} aus dem \emph{Odd-Even-Mergesort}-Netzwerk + generiert + wurde.]{\input{images/12-ec-from-oes24-fast.tex}\label{fig:12-ec-from-oes24-fast}} + \subfigure[Effizientes 12-Sortiernetzwerk aus 41~Komparatoren in + 10~Schichten, das von \textsc{SN-Evolution-Cut} aus dem + \emph{Odd-Even-Mergesort}-Netzwerk generiert + wurde.]{\input{images/12-ec-from-oes24-efficient.tex}\label{fig:12-ec-from-oes24-efficient}} + \caption{Startet man \textsc{SN-Evolution-Cut} mit \oes{24}, hängt das + Ergebnis von der Bewertungsfunktion ab.} + \label{fig:12-ec-from-oes24} +\end{figure} + +Das \oes{24}-Sortiernetzwerk ist kein Einzelfall: \textsc{SN-Evolution-Cut} +findet Sortiernetzwerke, die schneller sind als das entsprechende +\emph{Odd-Even-Mergesort}-Netzwerk, unter anderem für das +\emph{Odd-Even-Mergesort}-Netzwerk mit 22, 24, 38, 40, 42, 44 und 46 +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} \\ +\hline +11 & 38 & 9 & 37 & 10 \\ +12 & 43 & 9 & 41 & 10 \\ +19 & 93 & 13 & 91 & 14 \\ +20 & 101 & 13 & 97 & 14 \\ +21 & 108 & 14 & 107 & 15 \\ +22 & 116 & 14 & 114 & 15 \\ +23 & 125 & 14 & 122 & 15 \\ +\hline +\end{tabular} +\end{center} + +\begin{figure} + \begin{center} + \input{images/23-ec-from-oes46-fast.tex} + \end{center} + \caption{23-Sortiernetzwerk mit 125~Komparatoren in 14~Schichten. + Das Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \oes{46} mit dem + Schnittmuster $\operatorname{MIN}(6, 7, 9, 17, 19, 22, 29, 30, 32, 34, 38, + 44)$, $\operatorname{MAX}(4, 5, 11, 16, 18, 25, 31, 36, 39, 42, 45)$ + erzeugt.} + \label{fig:23-ec-from-oes46} +\end{figure} + \newpage \section{Der \textsc{SN-Markov}-Algorithmus} \label{sect:markov} @@ -1716,11 +1873,11 @@ Die Graphen in Abbildung~\ref{fig:markov-comparators} zeigen die Anzahl der Komparatoren der Sortiernetzwerke, die \textsc{SN-Markov} auf seinem zufälligen Pfad durchläuft (rot). Für jeden Graphen wurde der \textsc{SN-Markov}-Algorithmus auf einem entsprechenden -\emph{Odd-Even-Transporitionsort}-Netzwerk gestartet hat mindestens +\emph{Odd-Even-Transpositionsort}-Netzwerk gestartet hat mindestens 1.000.000~Iterationen durchlaufen. In jedem Schritt wurde die Anzahl der Komparatoren des Sortiernetzwerks bestimmt und ein entsprechender Zähler erhöht. In Abbildung~\ref{fig:markov-comparators} ist die resultierende -prezenturale Verteilung zu sehen. +prozentuale Verteilung zu sehen. Ebenfalls in die Graphen in Abbildung~\ref{fig:markov-comparators} eingezeichnet ist eine \emph{Gamma-Verteilung} (grün), die die gemessenen @@ -1777,7 +1934,7 @@ Während nur $0,000017 \%$ der Individuen von \textsc{SN-Evolution} mit 63~Komparatoren auskamen, ist die Rate bei \textsc{SN-Markov} mit $0,000335 \%$ rund 20~mal höher. -Erwartunggemäß sind die besten Netzwerke, die \textsc{SN-Evolution} mit dem +Erwartungsgemäß sind die besten Netzwerke, die \textsc{SN-Evolution} mit dem \emph{bitonen Mischer} findet, aus 67~Komparatoren aufgebaut. Überraschend ist jedoch, dass in dieser Konfiguration Sortiernetzwerke auftreten können, die mehr Komparatoren besitzen als \emph{Odd-Even-Transpositionsort} -- \oet{16} @@ -1836,8 +1993,6 @@ ein Phänomen, das mit der Initialisierung mit dem \begin{itemize} \item Beste erreichte Netzwerke (gleich zu \emph{OE-Mergesort}). \item Anzahl der erreichbaren Sortiernetzwerke. - \item Anzahl der Komparatoren und Anzahl der Schichten der durchlaufenen - Netzwerke. (Abbildung~\ref{fig:markov-comparators-16}) \item \textsc{SN-Count-Markov} (ggf) \end{itemize} @@ -1876,8 +2031,8 @@ Sortiernetzwerke mit $\frac{n}{2}$~Leitungen verwenden. Dies ließe sich für \textsc{SN-Evolution} nutzen, um zwei Individuen zu rekombinieren. Da es für das \emph{Pairwise-Sorting}-Netzwerk sehr viele -\emph{unterscheidliche} Schnittmuster gibt -(Abbschnitt~\ref{sect:anzahl_schnittmuster}), ist es möglich, dass die +\emph{unterschiedliche} Schnittmuster gibt +(Abschnitt~\ref{sect:anzahl_schnittmuster}), ist es möglich, dass die Verwendung dieser Rekombinationsmethode neue Ergebnisse ermöglicht. Leider wird die Aussicht auf Erfolg durch die Tatsache geschmälert, dass keine $n$-Schnittmuster für \ps{2n} gefunden werden konnten, die zu besseren @@ -1902,7 +2057,7 @@ funktionieren. In jeder Iteration wendet man alle oder eine zufällige Menge Schnittmuster auf das zusammengeführte Netzwerk an und gibt dem besten Ergebnis den Zuschlag. Anschließend erfährt das entsprechende Schnittmuster eine Aufwertung, so dass es wahrscheinlicher wird, dass \emph{dieses} -Schnittmuster zur nächten Generation beiträgt. Im Gegensatz zum Ansatz der +Schnittmuster zur nächsten Generation beiträgt. Im Gegensatz zum Ansatz der parasitären Eingaben entsteht eine \emph{Synergie} zweier Populationen, die das Gesamtergebnis oder zumindest die Konvergenzgeschwindigkeit verbessern könnte. @@ -1950,7 +2105,7 @@ Anwendung von Schnittmustern auf Sortiernetzwerke und Anwendung eines Komparatornetzwerks auf eine Eingabe-Permutation. \textit{libsortnetwork} kann unter der Web-Adresse -\url{http://octo.it/libsortnetwork/} unentgeldlich heruntergeladen werden. +\url{http://octo.it/libsortnetwork/} unentgeltlich heruntergeladen werden. \newpage \bibliography{references} @@ -1960,4 +2115,4 @@ Komparatornetzwerks auf eine Eingabe-Permutation. \end{document} -% vim: set shiftwidth=2 softtabstop=2 tabstop=8 fdm=marker tw=78 : +% vim: set shiftwidth=2 softtabstop=2 tabstop=8 fdm=marker tw=78 spelllang=de :