X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=b5d8a09355157cfa180203c5398c6f545076e9e1;hb=5a02f39eb2d2e5425dc15ccd93b6701417862f83;hp=b0fa6ace0bdd777ff7a34789b32671f00fea1221;hpb=feddb265381e5d1c11fc099bffcfba3ddc3d0889;p=diplomarbeit.git diff --git a/diplomarbeit.tex b/diplomarbeit.tex index b0fa6ac..b5d8a09 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -41,6 +41,7 @@ \newcommand{\ps}[1]{\ensuremath{\operatorname{PS}(#1)}} \newcommand{\oem}[1]{\ensuremath{\operatorname{OEM}(#1)}} \newcommand{\bm}[1]{\ensuremath{\operatorname{BM}(#1)}} +\newcommand{\oet}[1]{\ensuremath{\operatorname{OET}(#1)}} \newtheorem{definition}{Definition} \newtheorem{satz}{Satz} @@ -98,6 +99,7 @@ das hinbekomme bzw. Recht behalte.} \subsection{Motivation}\label{sect:motivation} +\todo{Schreibe noch etwas zu …} \begin{itemize} \item Sortiernetzwerke sind toll, weil $\ldots$ \item Sortiernetzwerke sind einfach erklärt, aber trotzdem kompliziert. @@ -327,12 +329,55 @@ 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} + \end{center} + \caption{Das 16-Sortiernetzwerk, das \textit{Hillis} in~\cite{H1992} angibt. + Es besteht aus 61~Komparatoren in 11~Schichten.} + \label{fig:16-hillis} +\end{figure} +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 +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 +gelang es \textit{Hillis} ein 16-Sortiernetzwerk mit 61~Komparatoren +anzugeben, das in Abbildung~\ref{fig:16-hillis} zu sehen ist. + +\begin{figure} + \centering + \subfigure{\input{images/13-juille-0.tex}} + \subfigure{\input{images/13-juille-1.tex}} + \caption{13-Sortiernetzwerke, die von \textit{Hugues Juillé} mithilfe des + END-Algorithmus gefunden wurden. Sie bestehen jeweils aus 45~Komparatoren in + 10~Schichten.} + \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 +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}). + \newpage \section{Bekannte konstruktive Sortiernetzwerke} \label{sect:konstruktive_netzwerke} Übersicht über bekannte konstruktive Sortiernetzwerke. +\todo{Einleitungssatz} + \subsection{Das Odd-Even-Transpositionsort-Netzwerk} \label{sect:odd_even_transpositionsort} @@ -389,7 +434,7 @@ Schichten. Das Sortiernetzwerk basiert auf einem Komparatornetzwerk, welches zwei sortierte Listen zusammenfügen (englisch: \textit{to~merge}) kann. Dieser -\emph{„bitoner Mischer“} (englisch: \textit{bitonic merger}) genannte Baustein +\emph{„bitone Mischer“} (englisch: \textit{bitonic merger}) genannte Baustein verleiht dem Sortiernetzwerk seinen Namen. Da das Sortiernetzwerk rekursiv definiert ist, betrachten wir hier nur die @@ -398,20 +443,20 @@ Es ist jedoch möglich das Sortiernetzwerk für beliebige~$n$ zu erzeugen. \subsubsection{Der bitone Mischer}\label{sect:der_bitone_mischer} -Das \emph{bitone Mergesort-Netzwerk} basiert auf dem sogenannten \emph{bitonen -Mischer} $\operatorname{BM}(n)$, einem Kom\-parator-Netzwerk, das eine beliebige -\emph{bitone Folge} in eine sortierte Listen umordnen kann. Eine \emph{bitone -Folge} ist eine monoton steigende Folge gefolgt von einer monoton absteigenden -Folge, oder ein zyklischer Shift davon. Abbildung~\ref{fig:beispiel-biton} -zeigt die vier prinzipiellen Möglichkeiten die durch zyklische Shifts -entstehen können. Die wichtigsten Varianten für das \emph{bitone -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. +Das \emph{bitone Mergesort}-Netzwerk basiert auf dem sogenannten \emph{bitonen +Mischer} $\operatorname{BM}(n)$, einem Kom\-parator-Netzwerk, das eine +beliebige \emph{bitone Folge} in eine sortierte Listen umordnen kann. Eine +\emph{bitone Folge} ist eine monoton steigende Folge gefolgt von einer monoton +absteigenden Folge, oder ein zyklischer Shift davon. +Abbildung~\ref{fig:beispiel-biton} zeigt die vier prinzipiellen Möglichkeiten +die durch zyklische Shifts entstehen können. Die wichtigsten Varianten für das +\emph{bitone 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 @@ -503,10 +548,9 @@ alle Komparatoren in die gleiche Richtung zeigen. \begin{center} \input{images/batcher-8.tex} \end{center} - \caption{$\operatorname{BS}(8)$, Batchers {\em bitones Mergesort-Netzwerk} - für acht Eingänge. Markiert sind die beiden Instanzen von - $\operatorname{BS}(4)$ (rot), die beiden bitonen - Mischer~$\operatorname{BM}(4)$ (blau) und die Komparatoren, die im letzten + \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).} \label{fig:bitonic-08} \end{figure} @@ -523,15 +567,6 @@ $\frac{1}{4} n \log(n) \log(n+1) = \mathcal{O}\left(n (log (n))^2\right)$ Komparatoren, die in $\frac{1}{2} \log(n) \log(n+1) = \mathcal{O}(\log(n))$ Schichten angeordnet sind. -%\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} - \subsection{Das Odd-Even-Mergesort-Netzwerk} Obwohl der Name ähnlich klingt, haben das \emph{Odd-Even-Mergesort-Netzwerk} @@ -787,6 +822,7 @@ die Anzahl der Schichten als Bewertungskriterium verwendet, immer eine Komprimierung durchgeführt werden. \subsection{Normalisieren} +\label{sect:normalisieren} \begin{figure} \centering @@ -859,18 +895,6 @@ Al-Haj Baddar} und \textit{Kenneth~E. Batcher} in ihrer Arbeit „An 11-Step Sorting Network for 18~Elements“~\cite{BB2009} vorstellen, benötigt aber 6~Komparatoren weniger. -% 9 9 -% 9 18 -% 9 27 -% 9 36 -% 9 45 -% 8 53 -% 8 61 -% 7 68 -% 7 75 -% 6 81 -% 5 86 - Das Zusammenfassen von zwei Sortiernetzwerken durch Hintereinanderausführung ist nicht sinnvoll: Da die Ausgabe des ersten Sortiernetzwerks bereits sortiert ist, ist das zweite Sortiernetzwerk überflüssig. Eine @@ -880,12 +904,6 @@ die Sortiereigenschaft. Die Sortiereigenschaft des resultierenden Komparatornetzwerks müsste überprüft werden, was nach heutigem Wissensstand nur mit exponentiellem Aufwand möglich ist. -%\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} \label{sect:leitungen_entfernen} @@ -910,17 +928,20 @@ das {\em Odd-Even-Transpositionsort-Netzwerk}. \begin{figure} \centering - \subfigure[foo]{\input{images/oe-transposition-cut0.tex}\label{fig:oe-transposition-cut0}} - \subfigure[bar]{\input{images/oe-transposition-cut1.tex}\label{fig:oe-transposition-cut1}} - \subfigure[baz]{\input{images/oe-transposition-cut2.tex}\label{fig:oe-transposition-cut2}} - \subfigure[qux]{\input{images/oe-transposition-cut3.tex}\label{fig:oe-transposition-cut3}} + \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 + 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}} + \subfigure[Die Leitungen wurden wieder gerade eingezeichnet und die + Komparatoren regelmäßig angeordnet. Blau eingezeichnet ist \oet{7}.]{\input{images/oe-transposition-cut3.tex}\label{fig:oe-transposition-cut3}} \caption{Eine Leitung wird aus dem - \emph{Odd-Even-Transpositionsort}-Netzwerk $\operatorname{OET}(8)$ entfernt: - Auf der rot 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 - $\operatorname{OET}(7)$ markiert.} + \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{8} entfernt: Auf der rot + 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.} \label{fig:oe-transposition-cut} \end{figure} @@ -943,19 +964,25 @@ 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. -Wenn wir die Minimum- beziehungsweise Maximum-Leitung entfernen -(Abbildung~\ref{fig:oe-transposition-cut2}), bleibt das Sortiernetzwerk für -$(n-1)$~Leitungen übrig. Je nachdem, ob auf einer Leitung ein Minimum oder ein -Maximum angenommen wird, bezeichnen wir das eliminieren einer Leitung als -\emph{Minimum-Schnitt} beziehungsweise \emph{Maximum-Schnitt}. +Wenn man die Minimum- beziehungsweise Maximum-Leitung entfernt, wie in +Abbildung~\ref{fig:oe-transposition-cut2} dargestellt, bleibt das +Sortiernetzwerk für $(n-1)$~Leitungen übrig. Je nachdem, ob auf einer Leitung +ein Minimum oder ein Maximum angenommen wird, bezeichnen wir das eliminieren +einer Leitung als \emph{Minimum-Schnitt} beziehungsweise +\emph{Maximum-Schnitt}. 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 -{\em Odd-Even-Transpositionsort-Netzwerk} für sieben Werte markiert. Der -zusätzliche Komparator vor dem $\textrm{OET}(7)$ hat keinen Einfluss auf die -Ausgabe und kann entfernt werden. +\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. + +Durch das Ersetzen von Komparatoren durch gekreuzte Leitungen werden häufig +\emph{Nicht-Standard-Sortiernetzwerke} erzeugt. Im Anschluss an einen +\emph{Schnitt} empfiehlt es sich deshalb, das Sortiernetzwerk zu +\emph{normalisieren}, wie in Abschnitt~\ref{sect:normalisieren} beschrieben. \subsubsection{Anzahl möglicher und unterschiedlicher Schnittmuster} \label{sect:anzahl_schnittmuster} @@ -963,8 +990,8 @@ Ausgabe und kann entfernt werden. Der Eliminierungsschritt kann iterativ angewandt werden, um aus einem Sortiernetzwerk mit $n$~Ein\-gängen Sortiernetzwerke mit $n-1$, $n-2$, $n-3$,~\dots Eingängen zu erzeugen. Insbesondere können auf diese Art und -Weise einen Sortiernetzwerke mit $2n$~Eingängen wieder auf Sortiernetzwerke -mit $n$~Eingängen reduziert werden. $k$~Minimum- und Maximum-Schnitte, die +Weise Sortiernetzwerke mit $2n$~Eingängen auf Sortiernetzwerke mit +$n$~Eingängen reduziert werden. $k$~Minimum- und Maximum-Schnitte, die nacheinander angewendet ein $n$-Sortiernetzwerk auf ein ${(n-k)}$-Sortiernetz\-werk reduzieren, bezeichnen wir als \emph{$k$-Schnittmuster}. @@ -1139,6 +1166,7 @@ die Anzahl der \emph{möglichen} Schnittmuster. \newpage \section{Der \textsc{SN-Evolution}-Algorithmus} +\label{sect:sn-evolution} Der \textsc{SN-Evolution}-Algorithmus ist ein \emph{evolutionärer Algorithmus}, der die in den vorherigen Abschnitten beschriebenen Mischer @@ -1216,7 +1244,7 @@ Auswahl := (leer) für jedes Individuum in Population { reziproke Güte := 1.0 / Guete(Individuum) - Wahrscheinlichkeit P := reziproke Güte / (reziproke Güte + Gütesumme) + Wahrscheinlichkeit P := reziproke Güte / (Gütesumme + reziproke Güte) Gütesumme := Gütesumme + reziproke Güte mit Wahrscheinlichkeit P @@ -1326,12 +1354,7 @@ 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. -\begin{itemize} -\item Güte von Sortiernetzwerken (Anzahl der Komparatoren, Anzahl der Schichten, kombiniert) -\item Wie gut die Netzwerke werden, hängt stark vom verwendeten \emph{Mischer} ab. -\item Ggf. Abschnitt „Shmoo-Äquivalenz“ kürzen und hier einbauen. -\item Möglicherweise: Verwende den rekursiven Aufbau des \emph{Pairwise-Sorting}-Netzwerks um Sortiernetzwerke zu mergen. -\end{itemize} +\todo{Ggf. Abschnitt „Shmoo-Äquivalenz“ kürzen und hier einbauen.} %\begin{figure} %\begin{center} @@ -1379,11 +1402,11 @@ von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}. Mit diesem Algorithmus wurden zu einer Reihe von „interessanten“ Netzwerken möglichst gute Schnittmuster gesucht. -Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet die \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$. +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$. 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 @@ -1586,7 +1609,7 @@ 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 +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. @@ -1638,9 +1661,9 @@ selbst erzeugen kann. 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. +Nachfolger zwar noch unter 20.000, bei den untersuchten +32-Sortier\-netz\-werken 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 @@ -1661,6 +1684,27 @@ für n Iterationen gib Netzwerk zurück \end{verbatim} +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 +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. + +Ebenfalls in die Graphen in Abbildung~\ref{fig:markov-comparators} +eingezeichnet ist eine \emph{Gamma-Verteilung} (grün), die die gemessenen +Daten gut annähert. Die Gamma-Verteilung verwendet einen Offset~$\delta$, der +um Eins kleiner als die kleinste erreichte Komparatorzahl gewählt wurde. +Beispielsweise war die kleinste erreichte Komparatorzahl bei +16-Sortiernetzwerken~63, entsprechend wurde der Offset $\delta = 63 - 1$ +gesetzt und die Gamma-Verteilung $g(x - 62)$ eingezeichnet. Die Parameter $k$ +und $\theta$, die eine Gamma-Verteilung charakterisieren, wurden mit einem +Fitting-Algorithmus bestimmt. Der konkrete Offset ist als Parameter~$\delta$ +unter den Graphen angegeben. + \begin{figure} \begin{center} \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-cycles-16.pdf} @@ -1673,7 +1717,7 @@ gib Netzwerk zurück \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. @@ -1682,62 +1726,159 @@ gib Netzwerk zurück \end{itemize} \begin{figure} - \begin{center} - \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 - \emph{Gamma-Verteilung} $f(x - 40)$ mit $k = 8,267$ und $\theta = 0,962$.} - \label{fig:markov-comparators-12} -\end{figure} - -\begin{figure} - \begin{center} - \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 - \emph{Gamma-Verteilung} $f(x - 52)$ mit $k = 9,522$ und $\theta = 0,867$.} - \label{fig:markov-comparators-14} -\end{figure} - -\begin{figure} - \begin{center} - \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 - \emph{Gamma-Verteilung} $f(x - 62)$ mit $k = 17,939$ und $\theta = 1,091$.} - \label{fig:markov-comparators-16} + \centering + \subfigure[12 Leitungen, $k = 8,267$, $\theta = 0,962$, $\delta = 40$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-12-pct.pdf}} + \subfigure[14 Leitungen, $k = 9,522$, $\theta = 0,867$, $\delta = 52$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-14-pct.pdf}} + \subfigure[16 Leitungen, $k = 17,939$, $\theta = 1,091$, $\delta = 62$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-16-pct.pdf}} + \subfigure[18 Leitungen, $k = 10,724$, $\theta = 0,766$, $\delta = 81$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-18-pct.pdf}} + \caption{Anzahl der Komparatoren von Sortiernetzwerken, + die von {\sc SN-Markov} durchlaufen wurden (rot). Ebenfalls eingezeichnet + ist jeweils eine \emph{Gamma-Verteilung} (grün), die eine gute Näherung der + gemessenen Daten darstellt.} + \label{fig:markov-comparators} \end{figure} \begin{figure} \begin{center} - \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-18-pct.pdf} + \includegraphics[viewport=0 0 425 262,width=15cm]{images/comparison-comparators-16.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} + \caption{Anzahl der Komparatoren, die 16-Sortiernetzwerke von + \textsc{SN-Markov} und \textsc{SN-Evolution} (mit dem + \emph{Odd-Even-Mischer} und dem \emph{bitonen Mischer}) gesaßen.} + \label{fig:comparison-comparators} \end{figure} -\newpage -\section{Empirische Beobachtungen} - -\begin{itemize} -\item So schnell konvergiert der Algorithmus. -\item $\ldots$ -\end{itemize} +%\begin{figure} +% \begin{center} +% \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 +% \emph{Gamma-Verteilung} $f(x - 52)$ mit $k = 9,522$ und $\theta = 0,867$.} +% \label{fig:markov-comparators-14} +%\end{figure} +% +%\begin{figure} +% \begin{center} +% \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 +% \emph{Gamma-Verteilung} $f(x - 62)$ mit $k = 17,939$ und $\theta = 1,091$.} +% \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{Ausblick} -Das würde mir noch einfallen$\ldots$ +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. + +\subsection{Verwendung des Pairwise-Sorting-Netzwerk in \textsc{SN-Evolution}} + +Die aktuelle Implementierung von \textsc{SN-Evolution} +(Abschnitt~\ref{sect:sn-evolution}) kann sowohl den \emph{bitonen Mischer} als +auch den \emph{Odd-Even-Mischer} verwenden, um zwei Individuen zu +rekombinieren. Das \emph{Pairwise-Sorting}-Netzwerk verwendet zwar keinen +Mischer, es ist aber ebenfalls rekursiv über kleinere Versionen von sich +selbst definiert. Das heißt, dass \ps{n} aus zwei Instanzen von +$\ps{\frac{n}{2}}$ und zusätzlichen Komparatoren besteht, die die Eingabe für +die kleineren Sortiernetzwerke vorbereiten und anschließend für eine sortierte +Ausgaben sorgen. Anstelle von $\ps{\frac{n}{2}}$ kann man natürlich beliebige +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 +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 +$n$-Sortiernetzwerken als \ps{n} führen. + +\subsection{Kooperation von \textsc{SN-Evolution} und +\textsc{SN-Evolution-Cut}} + +Ähnlich zu der parasitären \emph{Co-Evolution}, die \textit{W.~Daniel Hillis} +in~\cite{H1992} beschreibt, könnte man die Algorithmen \textsc{SN-Evolution} +und \textsc{SN-Evolution-Cut} versuchen zu kombinieren. Nach dem Zusammenfügen +von zwei $n$-Sortiernetzwerken könnte der Algorithmus +\textsc{SN-Evolution-Cut} beispielsweise einen möglichst guten Schnitt für +\emph{dieses} Netzwerk ermitteln. Da sich die Lösungen, die Evolutionäre +Algorithmen in ihre Population aufnehmen, in den ersten Schritten rasch +verbessern, könnten selbst weniger Iterationen von \textsc{SN-Evolution-Cut} +die Zwischenlösungen von \textsc{SN-Evolution} deutlich verbessern. + +Alternativ könnte man -- analog zur Herangehensweise von \textit{Hillis} -- +eine zweite Population von Schnittmustern evolvieren, die für die +Sortiernetzwerke in der Population von \textsc{SN-Evolution} besonders gut +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 +parasitären Eingaben entsteht eine \emph{Synergie} zweier Populationen, die +das Gesamtergebnis oder zumindest die Konvergenzgeschwindigkeit verbessern +könnte. \newpage \section{Implementierung} -So habe ich die ganzen Versuche durchgeführt. +Alle in dieser Arbeit beschriebenen Versuche wurden mit einer eigens +entwickelten C-Bibliothek, \textit{libsortnetwork}, und zugehörigen +Kommandozeilen-Programmen durchgeführt. Die Bibliothek wurde unter der +\textit{GNU Lesser General Public License} (LGPL) in der Version~2.1 +veröffentlicht; die Kommandozeilen-Programme, die in vielen Fällen lediglich +Funktionalität der Bibliothek auf der Kommandozeile zur Verfügung stellen, +stehen unter der \textit{GNU General Public License}, Version~2. Diese +Lizenzen räumen einem Benutzer weitreichende Rechte ein, unter anderem das +Programm beliebig zu verwenden, zu studieren, zu verändern sowie veränderte +und unveränderte Kopien zu veröffentlichen. + +Die Programmierschnittstelle (API) der Bibliothek orientiert sich an +Paradigmen der \textit{objektorientierten Programmierung}. Beispielsweise kann +mit der Funktion \texttt{sn\_network\_ create()} ein neues Zustands-Objekt +erzeugt werden, für das mehrere Manipulations-Methoden, zum Beispiel +\texttt{sn\_network\_comparator\_add()}, zur Verfügung stehen. Auf diese Art +und Weise kann die Bibliothek leicht erweitert werden, ohne dass bestehende +Programme angepasst werden müssen. + +Die meisten Kommandozeilen-Programmen lesen ein Komparatornetzwerk von der +Standard-Eingabe und schreiben ihr Ergebnis auf die Standard-Ausgabe. Um +Beispielsweise eine \emph{normalisierte} Variante des \emph{bitonen +Mergesort}-Netzwerks \bs{18} zu erzeugen, kann folgendes Kommando verwendet +werden: +\begin{verbatim} +$ sn-bitonicsort 18 | sn-normalize >sn-18 +\end{verbatim} +Dieses Prinzip, kleine Programme \emph{eine} Aufgabe erledigen zu lassen und +es einfach zu ermöglichen, Programme zu verketten, ist eines der +Grundprinzipien des UNIX-Be\-triebs\-sys\-tems. Es hat sich in den letzten +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. + +\textit{libsortnetwork} kann unter der Web-Adresse +\url{http://octo.it/libsortnetwork/} unentgeldlich heruntergeladen werden. \newpage \bibliography{references}