From: Florian Forster Date: Fri, 18 Feb 2011 14:38:01 +0000 (+0100) Subject: Diverse Änderungen. X-Git-Url: https://git.octo.it/?p=diplomarbeit.git;a=commitdiff_plain;h=59c72e9af2bc68901200ce7e816a2d20dbddc1a8 Diverse Änderungen. --- diff --git a/diplomarbeit.tex b/diplomarbeit.tex index c0213f2..a7f0bf9 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -36,6 +36,12 @@ \newcommand{\todo}[1]{{\bf TODO:} #1} \newcommand{\qed}{\hfill $\Box$ \par \bigskip} +\newcommand{\oes}[1]{\ensuremath{\operatorname{OES}(#1)}} +\newcommand{\bs}[1]{\ensuremath{\operatorname{BS}(#1)}} +\newcommand{\ps}[1]{\ensuremath{\operatorname{PS}(#1)}} +\newcommand{\oem}[1]{\ensuremath{\operatorname{OEM}(#1)}} +\newcommand{\bm}[1]{\ensuremath{\operatorname{BM}(#1)}} + \newtheorem{definition}{Definition} \newtheorem{satz}{Satz} @@ -1238,7 +1244,7 @@ erhält. 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 +Sortiernetzwerk zufällig zu verändern und dabei die Sortiereigenschaft zu erhalten. Selbst das \emph{Hinzufügen} eines zufälligen Komparators kann diese Eigenschaft zerstören. @@ -1248,70 +1254,117 @@ Sortiereigenschaft noch besitzt. Nach heutigem Wissenstand ist diese 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 -Population überprüft das Programm die Notwendigkeit jedes einzelnen -Komparators. Dazu wurde nacheinander jeder Komparator entfernt und überprüft, -ob das verbleibende Netzwerk die Sortiereigenschaft noch besitzt. +Um das Potenzial einer Mutation abzuschätzen wurde in \textsc{SN-Evolution} +eine Überprüfung eingebaut: Unmittelbar vor dem Einfügen in die Population +überprüft eine Funktion die Notwendigkeit jedes einzelnen Komparators. Dazu +wird nacheinander jeder Komparator entfernt und überprüft, ob das verbleibende +Netzwerk die Sortiereigenschaft noch besitzt. -\begin{itemize} -\item Güte von Sortiernetzwerken (Anzahl der Komparatoren, Anzahl der -Schichten, kobiniert) -\item Rekombination: Merge Anhängen und Leitungen entfernen. -\end{itemize} +Trotz des hohen Rechenaufwandes -- 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 +Komparator, den er hätte entfernen können. -Ein Beispielnetzwerk, das von dem Algorithmus gefunden wird, zeigt -Abbildung~\ref{fig:evolutionary_08}. +\subsection{Güte} -\begin{figure} -\begin{center} -\input{images/evolutionary-08.tex} -\end{center} -\caption{Ein mit dem evolutionären Algorithmus erzeugtes Sortiernetzwerk mit -acht Eingängen. Es besteht aus 19~Komparatoren in 6~Schichten.} -\label{fig:evolutionary_08} -\end{figure} +Die Qualität der erreichten Sortiernetzwerke wurde mit eine Gütefunktion +beurteilt, die entsprechend dem im Abschnitt~\ref{sect:bewertung} +vorgestellten Muster definiert ist. Wie beschrieben müssen die Faktoren häufig +an die aktuelle Problemgröße angepasst werden, damit \textsc{SN-Evolution} +schnell gute Ergebnisse liefert. Als guter Standardansatz haben sich die +folgenden Werte herausgestellt: +\begin{eqnarray*} +w_{\mathrm{Basis}} &=& 0 \\ +w_{\mathrm{Komparatoren}} &=& 1 \\ +w_{\mathrm{Schichten}} &=& \left|S\right|_\mathrm{Leitungen} +\end{eqnarray*} -\begin{figure} -\begin{center} -\input{images/08-e2-1237993371.tex} -\end{center} -\caption{{\tt images/08-e2-1237993371.tex}: 19~Komparatoren in 6~Schichten} -\label{fig:08-e2-1237993371} -\end{figure} +\subsection{Versuche mit dem bitonen Mischer} \begin{figure} -\begin{center} -\input{images/09-e2-1237997073.tex} -\end{center} -\caption{{\tt images/09-e2-1237997073.tex}: 25~Komparatoren in 8~Schichten} -\label{fig:09-e2-1237997073} + \begin{center} + \input{images/16-e1-bitonic-1296542566.tex} + \end{center} + \caption{Sortiernetzwerk mit 16~Leitungen und 67~Komparatoren in + 10~Schichten. Das Netzwerk wurde von dem Algorithmus + \textsc{SN-Evolution} unter Verwendung des \emph{bitonen Mischers} + erzeugt.} + \label{fig:16-e1-bitonic-1296542566} \end{figure} -\begin{figure} -\begin{center} -\input{images/09-e2-1237999719.tex} -\end{center} -\caption{{\tt images/09-e2-1237999719.tex}: 25~Komparatoren in 7~Schichten} -\label{fig:09-e2-1237999719} -\end{figure} +Verwendet man den \emph{bitonen Mischer} in der Rekombinationsphase von +\textsc{SN-Evolution}, so erhält man Netzwerke wie das in +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. + +\subsection{Versuche mit dem Odd-Even-Mischer} \begin{figure} -\begin{center} -\input{images/10-e2-1239014566.tex} -\end{center} -\caption{{\tt images/10-e2-1239014566.tex}: 29~Komparatoren in 8~Schichten} -\label{fig:10-e2-1239014566} + \begin{center} + \input{images/16-e1-oddeven-1296543330.tex} + \end{center} + \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in + 10~Schichten. Das Netzwerk wurde von dem Algorithmus + \textsc{SN-Evolution} unter Verwendung des \emph{Odd-Even-Mischers} + erzeugt.} + \label{fig:16-e1-oddeven-1296543330} \end{figure} -\subsection{Güte} +Leider lies sich das Ergebnis des bitonen Mischers -- das von +\textsc{SN-Evolution} ausgegebene Netzwerk war effizienter als das rekursiv +aus dem verwendeten Mischer aufgebaute Sortiernetzwerk -- mit dem +\emph{Odd-Even-Mischer} nicht wiederholen. Zwar erreichen die +Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung des +\emph{Odd-Even-Mischers} findet, das \emph{Odd-Even-Mergesort}-Netzwerk +bezüglich Schnelligkeit und Effizienz, ein Beispiel hierfür ist in +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 So gut kann man mindestens werden {\em ($\rightarrow$ Bitonic-Mergesort, vermute ich)}. -\item Wie gut die Netzwerke werden, hängt stark vom verwendeten \em{Mischer} ab. +\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} +%\begin{figure} +%\begin{center} +%\input{images/08-e2-1237993371.tex} +%\end{center} +%\caption{{\tt images/08-e2-1237993371.tex}: 19~Komparatoren in 6~Schichten} +%\label{fig:08-e2-1237993371} +%\end{figure} +% +%\begin{figure} +%\begin{center} +%\input{images/09-e2-1237997073.tex} +%\end{center} +%\caption{{\tt images/09-e2-1237997073.tex}: 25~Komparatoren in 8~Schichten} +%\label{fig:09-e2-1237997073} +%\end{figure} +% +%\begin{figure} +%\begin{center} +%\input{images/09-e2-1237999719.tex} +%\end{center} +%\caption{{\tt images/09-e2-1237999719.tex}: 25~Komparatoren in 7~Schichten} +%\label{fig:09-e2-1237999719} +%\end{figure} +% +%\begin{figure} +%\begin{center} +%\input{images/10-e2-1239014566.tex} +%\end{center} +%\caption{{\tt images/10-e2-1239014566.tex}: 29~Komparatoren in 8~Schichten} +%\label{fig:10-e2-1239014566} +%\end{figure} + %\input{shmoo-aequivalenz.tex} \newpage @@ -1473,14 +1526,6 @@ den Schichten~1--6 erkennt man zwei unabhängige Sortiernetzerke, die strukturell identisch zu $\operatorname{PS}(8)$ sind -- lediglich die Schichten~1 und~2 sowie 4~und~5 sind vertauscht. -\begin{displaymath} -\textit{Eingang}_i = \left\{ \begin{array}{rl} - -\infty & \quad \textrm{falls } i \operatorname{mod} 8 \in \{0, 6\} \\ - \infty & \quad \textrm{falls } i \operatorname{mod} 8 \in \{2, 4\} \\ - ? & \quad \mathrm{sonst} - \end{array} \right. -\end{displaymath} - \begin{figure} \begin{center} \input{images/32-pairwise-cut-16-pairwise.tex} @@ -1489,6 +1534,28 @@ Schichten~1 und~2 sowie 4~und~5 sind vertauscht. \label{fig:ps16-from-ps32} \end{figure} +Für das \emph{Pairwise-Sorting-Netzwerk} ist es vergleichsweise einfach +regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk einen kleineres +schnelles und effizientes Sortiernetzwerk erzeugen. Beispielsweise führt das +einfache Schnittmuster +\begin{displaymath} +\textit{Eingang}_i = \left\{ \begin{array}{rl} + -\infty & \quad \textrm{falls } i < \frac{1}{4} n \\ + \infty & \quad \textrm{falls } i \geqq \frac{3}{4} n \\ + ? & \quad \mathrm{sonst} + \end{array} \right. +\end{displaymath} +für $\operatorname{PS}\left(n = 2^d\right)$ zum Sortiernetzwerk +$\operatorname{PS}\left(\frac{1}{2}n\right)$. Die Art und Weise, mit der +dieses Schnittmuster Komparatoren eliminiert und welche Komparatoren das +verbleibende Netzwerk ausmachen, ist in Abbildung~\ref{fig:ps16-from-ps32} +dargestellt. Die matt blauen und roten Leitungen und Komparatoren sind +diejenigen, die Aufgrund eines Minimums oder eines Maximums im resultierenden +Netzwerk nicht mehr enthalten sind. Da die Minima und Maxima bereits auf den +„richtigen“ Leitungen angelegt werden, müssen keine Leitungen vertauscht +werden und das Ergebnis ist bereits normalisiert. Daher ist das resultierende +Netzwerk in schwarz gut zu erkennen. + \begin{figure} \begin{center} \input{images/16-pairwise.tex} @@ -1499,21 +1566,50 @@ Schichten~1 und~2 sowie 4~und~5 sind vertauscht. \label{fig:16-pairwise} \end{figure} -Wendet man \textsc{SN-Evolution-Cut} auf $\operatorname{PS}(16)$ an, so kann -man $\operatorname{OES}(8)$ erhalten. +Ein Spezialfall ergibt sich, wenn man \textsc{SN-Evolution-Cut} auf +$\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} +untersucht \textit{Moritz Mühlenthaler} ausführlich in~\cite{M2009}. \subsection{Versuche mit dem Odd-Even-Mergesort-Netzwerk} -\todo{Schreibe noch etwas zum Odd-Even-Mergesort-Netzwerk.} +In Abschnitt~\ref{sect:anzahl_schnittmuster} wurde bereits untersucht, wie +viele \emph{unterschiedliche} Schnittmuster die konstruktiven Sortiernetzwerke +$\operatorname{OES}(32)$, $\operatorname{BS}(32)$ und $\operatorname{PS}(32)$ +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. -\begin{itemize} - \item Beispiel: Moritz und Rolfs Optimierung für Bitonic-Sort. - \item Wie gut kann man durch wegschneiden werden? - \item Wieviele Schnitte ergeben das selbe Netzwerk? Oder andersrum: Wieviele - unterschiedliche Netzwerke kann ich erhalten? Wieviele Nachfolger hat ein - Netzwerk / Knoten in der Markov-Kette? - \item Abschnitt „Optimierung der Schnitte“ hier einbauen. -\end{itemize} +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. + +\begin{figure} + \begin{center} + \input{images/16-ec-from-oes32-cut.tex} + \end{center} + \caption{Visualisierung eines 16-Schnittmusters, das auf + $\operatorname{OES}(32)$ angewendet wieder ein schnelles und effizientes + Sortiernetzwerk ergibt.} + \label{fig:16-ec-from-oes32-cut} +\end{figure} + +\begin{figure} + \begin{center} + \input{images/16-ec-from-oes32.tex} + \end{center} + \caption{16-Sortiernetzwerk mit 63~Komparatoren in 10~Schichten. + Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution-Cut} aus dem + \emph{Odd-Even-Mergesort-Netzwerk} $\operatorname{OES}(32)$ durch + 16~Schnitte erzeugt.} + \label{fig:16-ec-from-oes32} +\end{figure} \newpage \section{Der \textsc{SN-Markov}-Algorithmus}