X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=03be0ac8394252c14d38a6cd25a5887078f1cd66;hb=73495b061c2fa75855a6a068178f93c1d9948fa4;hp=0fd8e89bc1d04b47ebffbc9aa451200191534b06;hpb=d6fe7037c87edd9d38931b1d9c56c959c0e0561b;p=diplomarbeit.git diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 0fd8e89..03be0ac 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -435,7 +435,7 @@ ${n = 8}$ Leitungen. \begin{center} \input{images/oe-transposition-8.tex} \end{center} - \caption{Das \emph{Odd-Even-Transpositionsort}-Netzwerk mit acht Eingängen.} + \caption{Das \emph{Odd-Even-Transpositionsort}-Netzwerk mit 8~Eingängen.} \label{fig:odd-even-transposition-08} \end{figure} @@ -598,10 +598,10 @@ alle Komparatoren in die gleiche Richtung zeigen. \begin{center} \input{images/batcher-8.tex} \end{center} - \caption{\bs{8}, Batchers \emph{bitones Mergesort}-Netzwerk für acht - Eingänge. Markiert sind die beiden Instanzen von \bs{4} (rot), die beiden - bitonen Mischer~\bm{4} (blau) und die Komparatoren, die im letzten - rekursiven Schritt hinzugefügt wurden (grün).} + \caption{\bs{8}, Batchers \emph{bitones Mergesort}-Netzwerk für 8~Eingänge. + Markiert sind die beiden Instanzen von \bs{4} (rot), die beiden bitonen + Mischer~\bm{4} (blau) und die Komparatoren, die im letzten rekursiven + Schritt hinzugefügt wurden (grün).} \label{fig:bitonic-08} \end{figure} @@ -656,10 +656,12 @@ w_i = \left\{ \begin{array}{ll} \begin{center} \input{images/oe-merge.tex} \end{center} - \caption{Schematischer Aufbau des \emph{Odd-Even-Merge}-Netzwerks. Im - Vergleich zum bitonen Mischer für acht Leitungen kommt dieses Schema mit - einem Komparator weniger aus. Der Effekt wird durch den rekursiven Aufbau - verstärkt.} + \caption{Schematischer Aufbau des \emph{Odd-Even-Merge}-Netzwerks. Die + beiden Dreiecke symbolisieren die beiden sortierten Folgen $U$ und $V$, + die Blöcke darunter die rekursiven Mischer mit etwa der Hälfte der + Leitungen. Im Vergleich zum \emph{bitonen Mischer} für 8~Leitungen kommt + dieses Schema mit einem Komparator weniger aus. Der Effekt wird durch den + rekursiven Aufbau verstärkt.} \label{fig:oe-merge} \end{figure} @@ -802,7 +804,7 @@ die als leere Komparatornetzwerke definiert sind. \begin{center} \input{images/oe-mergesort-8.tex} \end{center} - \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge. Markiert + \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für 8~Eingänge. Markiert sind die Instanzen von $\operatorname{OES}(4)$ (rot), die beiden \emph{Odd-Even}-Mischer $\operatorname{OEM}(4)$ für gerade und ungerade Leitungen (blau) und die im ersten Rekursionsschritt hinzugefügten @@ -813,7 +815,7 @@ die als leere Komparatornetzwerke definiert sind. In Abbildung~\ref{fig:odd-even-mergesort-08} ist das \oes{8}-Sortiernetzwerk zu sehen. Rot markiert sind die beiden rekursiven Instanzen $\operatorname{OES}(4)$. Die anderen Blöcke stellen den -\emph{Odd-Even}-Mischer für acht Leitungen dar: die beiden blauen Blöcke sind +\emph{Odd-Even}-Mischer für 8~Leitungen dar: die beiden blauen Blöcke sind die rekursiven Instanzen von $\operatorname{OEM}(4)$, der grüne Block markiert die Komparatoren, die im ersten Rekursionsschritt hinzugefügt werden. @@ -935,7 +937,7 @@ zu sortieren und die Ausgaben mit einem der beschriebenen Mischer zusammenfügen. Beispielsweise kann die Ausgabe von zwei \emph{bitonen Mergesort-Netzwerken} -$\operatorname{BS}(8)$ mit je acht Leitungen mit dem +$\operatorname{BS}(8)$ mit je 8~Leitungen mit dem \emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM(8,8)}$ zu einer sortierten Gesamtfolge zusammengefügt werden. Das resultierende Sortiernetzwerk besitzt 73~Komparatoren (zum Vergleich: $\operatorname{BS}(16)$ benötigt @@ -1311,17 +1313,20 @@ w_{\mathrm{Schichten}} &=& \left|S\right|_\mathrm{Leitungen} \subsection{Selektion} -Die \emph{Selektion} sorgt dafür, dass bessere Individuen eine größere -Wahrscheinlichkeit haben zur nächsten Generation beizutragen. Diese -Ungleichbehandlung von Individuen verschiedener Güte ist der Grund für das -Streben des Algorithmus nach besseren Lösungen. +Als \emph{Selektion} wird der Vorgang bezeichnet, der zwei Individuen zufällig +aus der Population auswählt. Sie werden im folgenden Schritt miteinander +rekombiniert. Die Auswahl der Individuen erfolgt zufällig, aber nicht +gleichverteilt. So sorgt die \emph{Selektion} dafür, dass bessere Individuen +eine größere Wahrscheinlichkeit haben zur nächsten Generation beizutragen. +Diese Ungleichbehandlung von Individuen verschiedener Güte ist der Grund für +das Streben des Algorithmus nach besseren Lösungen. Obwohl dieser Vorteil für gute Individuen intuitiv als sehr gering erscheint, -ist es sehr häufig, dass die \emph{Exploitation} überhand gewinnt und der -Algorithmus vorschnell in Richtung eines lokalen Optimums optimiert. +passiert es häufig, dass die Ausnutzung \emph{(Exploitation)} überhand gewinnt +und der Algorithmus vorschnell in Richtung eines lokalen Optimums optimiert. -Die in \textsc{SN-Evolution} implementierte Selektion lässt sich mithilfe von -Pseudocode wie folgt beschreiben: +Die in \textsc{SN-Evolution} implementierte Selektion eines Individuums lässt +sich mit Pseudocode wie folgt beschreiben: \begin{verbatim} Gütesumme := 0 Auswahl := (leer) @@ -1340,6 +1345,10 @@ Pseudocode wie folgt beschreiben: gib Auswahl zurück \end{verbatim} +Diese Auswahl wird zweimal ausgeführt, um zwei Individuen für die +Rekombination zu erhalten. Das heißt, dass die Individuen bei +\textsc{SN-Evolution} stochastisch unabhängig voneinander ausgewählt werden. + \subsection{Rekombination} \label{sect:sn-evolution:rekombination} @@ -1816,6 +1825,18 @@ invertieren. \subsection[Bitones Mergesort-Netzwerk]{Versuche mit dem bitonen Mergesort-Netzwerk} \label{sect:sn-evolution-cut:bs} +\begin{figure} + \begin{center} + \input{images/16-ec-from-bs22.tex} + \end{center} + \caption{Sortiernetzwerk mit 16~Leitungen und 67~Komparatoren in + 10~Schichten. Das Netzwerk wurde von dem Algorithmus + \textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort}-Netzwerk + $\operatorname{BS}(22)$ durch das 6-Schnittmuster $\operatorname{MIN}(4, + 10, 17)$, $\operatorname{MAX}(7, 15, 20)$ erzeugt.} + \label{fig:16-ec-from-bs22} +\end{figure} + \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 @@ -1970,8 +1991,44 @@ 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 \emph{Odd-Even-Transpositionsort-Netzwerk} $\operatorname{OET}(n)$ und -$m$~Schnitten gestartet, so ist das beste Ergebnis immer das -$\operatorname{OET}(n-m)$-Netzwerk. +$k$~Schnitten gestartet, so ist das beste Ergebnis immer das +$\operatorname{OET}(n-k)$-Netzwerk. + +\begin{table} + \begin{center} + \rowcolors{2}{black!5}{} + \begin{tabular}{|r|rrrrrrrrrrrrrrrr|} + \hline + & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\ + \hline + 9 & 21 & & & & & & & & & & & & & & & \\ + 10 & 20 & 27 & & & & & & & & & & & & & & \\ + 11 & 20 & 27 & 32 & & & & & & & & & & & & & \\ + 12 & 20 & 26 & 32 & 39 & & & & & & & & & & & & \\ + 13 & 20 & 26 & 32 & 39 & 45 & & & & & & & & & & & \\ + 14 & 20 & 26 & 32 & 39 & 45 & 53 & & & & & & & & & & \\ + 15 & 20 & 26 & 32 & 39 & 45 & 53 & 61 & & & & & & & & & \\ + 16 & 20 & 26 & 32 & 39 & 45 & 53 & 61 & 70 & & & & & & & & \\ + 17 & 20 & 26 & 32 & 37 & 43 & 50 & 57 & 65 & 74 & & & & & & & \\ + 18 & 20 & 26 & 31 & 37 & 43 & 49 & 56 & 63 & 71 & 82 & & & & & & \\ + 19 & 20 & 26 & 31 & 37 & 43 & 48 & 55 & 62 & 70 & 79 & 88 & & & & & \\ + 20 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 86 & 95 & & & & \\ + 21 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 85 & 94 & 103 & & & \\ + 22 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 67 & 77 & 84 & 93 & 102 & 112 & & \\ + 23 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 & \\ + 24 & 20 & 26 & 32 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 & 133 \\ + \hline +\bs{n} & 24 & 28 & 33 & 39 & 46 & 53 & 61 & 70 & 80 & 85 & 91 & 98 & 106 & 114 & 123 & 133 \\ + \hline + \end{tabular} + \end{center} + \caption{Anzahl der Komparatoren der Ergebnisse des + \textsc{SN-Evolution-Cut} mit verschiedenen Größen des \emph{bitonen + Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. Jede Zeile gibt + die Ergebnisse für ein Eingabenetzwerk \bs{n} an, die Spalten + repräsentieren die Anzahl der Leitungen des Ausgabenetzwerks.} + \label{tbl:ec-bs-fast} +\end{table} \subsection[Odd-Even-Mergesort-Netzwerk]{Versuche mit dem Odd-Even-Mergesort-Netzwerk} \label{sect:sn-evolution-cut:oes} @@ -2132,6 +2189,43 @@ Sortiernetzwerk das \emph{bitone Mergesort}-Netzwerk war ist bei dem Netzwerk in Abbildung~\ref{fig:32-ec-from-bs64} nicht ersichtlich, wie und warum es jede beliebige Eingabe sortiert. +\begin{table} + \begin{center} + \rowcolors{2}{black!5}{} +\begin{tabular}{|r|rrrrrrrrrrrrrrrr|} +\hline + & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\ +\hline + 9 & 20 & & & & & & & & & & & & & & & \\ + 10 & 20 & 27 & & & & & & & & & & & & & & \\ + 11 & 20 & 28 & 32 & & & & & & & & & & & & & \\ + 12 & 20 & 28 & 32 & 38 & & & & & & & & & & & & \\ + 13 & 19 & 27 & 31 & 37 & 41 & & & & & & & & & & & \\ + 14 & 19 & 27 & 31 & 37 & 41 & 48 & & & & & & & & & & \\ + 15 & 19 & 27 & 31 & 37 & 41 & 48 & 53 & & & & & & & & & \\ + 16 & 19 & 27 & 31 & 37 & 41 & 48 & 53 & 59 & & & & & & & & \\ + 17 & 21 & 29 & 32 & 39 & 43 & 51 & 57 & 64 & 68 & & & & & & & \\ + 18 & 22 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & & & & & & \\ + 19 & 23 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & 88 & & & & & \\ + 20 & 23 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & 88 & 97 & & & & \\ + 21 & 20 & 30 & 34 & 38 & 44 & 51 & 57 & 64 & 74 & 82 & 87 & 96 & 102 & & & \\ + 22 & 20 & 30 & 34 & 38 & 46 & 51 & 57 & 64 & 72 & 82 & 89 & 96 & 102 & 112 & & \\ + 23 & 20 & 27 & 34 & 38 & 42 & 51 & 57 & 66 & 72 & 83 & 89 & 97 & 102 & 112 & 119 & \\ + 24 & 20 & 27 & 34 & 38 & 42 & 51 & 57 & 64 & 72 & 82 & 89 & 96 & 102 & 112 & 119 & 127 \\ +\hline +\ps{m}&19 & 27 & 32 & 38 & 42 & 48 & 53 & 59 & 63 & 79 & 88 & 97 & 103 & 112 & 119 & 127 \\ +\hline +\end{tabular} + \end{center} + \caption{Anzahl der Komparatoren der Ergebnisse von + \textsc{SN-Evolution-Cut} mit verschiedenen Größen des + \emph{Pairwise-Sorting}-Netzwerks und unterschiedlichen Werten für~$k$. + Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \ps{n} an, jede + Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des + Ausgabenetzwerks.} + \label{tbl:ec-bs-fast} +\end{table} + Das \emph{Pairwise-Sorting-Netzwerk} $\operatorname{PS}(n)$, das \textit{Ian Parberry} in seiner Arbeit „The Pairwise Sorting Network“ \cite{P1992} definiert, verhält sich anders. Startet man \textsc{SN-Evolution-Cut} mit