\end{abstract}
\newpage
+\section*{Eidesstattliche Erklärung}
+
+Ich versichere, dass ich die vorliegende wissenschaftliche Arbeit
+selbstständig verfasst und keine anderen als die angegebenen Hilfsmittel
+verwendet habe. Die Stellen der Arbeit, die anderen Werken dem Wortlaut oder
+dem Sinn nach entnommen sind, wurden unter Angabe der Quelle als Entlehnung
+deutlich gemacht. Das Gleiche gilt auch für beigegebene Skizzen und
+Darstellungen. Diese Arbeit hat in gleicher oder ähnlicher Form meines Wissene
+nach noch keiner Prüfungsbehörde vorgelegen.
+\\[3cm]
+München, den 20.~März 2011,\\
+\\[1cm]
+Florian Forster
+\newpage
+
\tableofcontents
\newpage
-- 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~Milliarden Tests notwendig, die einen Rechner durchaus
-mehrere Minuten beschäftigen. Das ist deshalb problematisch, weil die im
+mehrere Stunden beschäftigen. Das ist deshalb problematisch, weil die im
Folgenden vorgestellten \emph{Evolutionären Algorithmen} eine entsprechende
Überprüfung in jeder Iteration durchführen müssten. Wenn die Überprüfung eines
-Zwischenergebnisses fünf Minuten in Anspruch nimmt, sind für eine Million
-Iterationen fast zehn Jahre Rechenzeit notwendig. Selbst wenn die Berechnung
-auf 1000~Computern mit je 4~Prozessoren verteilt wird, werden über 20~Stunden
-für einen Lauf benötigt.
+Zwischenergebnisses drei Stunden in Anspruch nimmt, sind für eine Million
+Iterationen etwa 340~Jahre Rechenzeit notwendig. Selbst wenn die Berechnung
+auf 1000~Computern mit je 4~Prozessoren verteilt wird, wird etwa ein Monat für
+einen Lauf benötigt.
\subsubsection{Evolutionäre Algorithmen}
erforscht der Algorithmus den Lösungsraum in viele Richtungen. Dieses
\textit{Exploration} (Englisch für „Erforschung“) genannte Verhalten sorgt
zwar dafür, dass der Algorithmus langsamer auf ein Optimum zusteuert, dafür
-findet er aber in der Regel bessere Lösungen.
+findet er aber in der Regel bessere Lösungen. Die Rolle, die
+\textit{Exploitation} und \textit{Exploration} bei evolutionären
+Optimierungsalgorithmen spielen, wird von \textit{Eiben} und
+\textit{Schippers} in~\cite{ES1998} untersucht.
Die Parameter evolutionärer Algorithmen so einzustellen, dass sich ein guter
Mittelweg zwischen den beiden Extremen einstellt, ist eine Aufgabe, die sich
nur experimentell lösen lässt. Die genauen Parameter hängen nicht nur vom
eigentlichen Algorithmus, sondern auch vom konkreten Problem ab, so dass sich
beispielsweise bei der Optimierung von Sortiernetzwerken die Parameter
-zwischen verschiedenen Leitungszahlen stark unterscheiden.
+zwischen verschiedenen Leitungszahlen stark unterscheiden. Einen Überblick
+geben \textit{Kalyanmoy Deb} und \textit{Samir Agrawal} in~\cite{DA1998}.
Die Erforschung (\textit{Exploration}) kann von einem weiteren Mechanismus
unterstützt werden, der ebenfalls der Evolutionslehre entliehen ist, der
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{H1990} angibt.
-Es besteht aus 61~Komparatoren in 11~Schichten.} \label{fig:16-hillis}
-\end{figure} Evolutionäre Algorithmen wurden bereits mehrfach eingesetzt, um
+\begin{figure}
+ \begin{center}
+ \input{images/16-hillis.tex}
+ \end{center}
+ \caption{Das 16-Sortiernetzwerk, das \textit{Hillis} in~\cite{H1990} 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{H1990}. Diese \emph{Parasiten} genannten Eingaben wurden
gelang es \textit{Hillis} ein 16-Sortiernetzwerk mit 61~Komparatoren
anzugeben, das in Abbildung~\ref{fig:16-hillis} zu sehen ist.
+\textit{Michael~L. Harrison} und \textit{James~A. Foster} nutzten ebenfalls
+\emph{Co-Evolution} in~\cite{HF2004}, um die Stabilität von Sortiernetzwerken
+zu erhöhen. Die zweite Population bestand aus \emph{Fehlern} -- der
+Information, welche Komparatoren defekt, beziehungsweise inaktiv sind. So
+generierte Sortiernetzwerke können auch dann noch für viele Eingaben eine
+korrekt sortierte Ausgabe erzeugen, wenn ein oder mehrere Komparatoren
+(zufällig) entfernt werden.
+
\begin{figure}
\centering
\subfigure{\input{images/13-juille-0.tex}}
"`Mischer"' in der Literatur sehr weit verbreitet ist, werden diese Begriffe
in dieser Arbeit trotzdem verwendet.}, bilden die Grundlage für die
beschriebenen evolutionären Algorithmen beziehungsweise dienen als initiale
-Eingabe. Im Folgenden werden daher vier Konstruktionsverfahren vorgestellt.
-
-\todo{Drei oder vier Verfahren? Sprich: Mit oder ohne Pairwise Sorting.}
+Eingabe. Im Folgenden werden daher drei Konstruktionsverfahren vorgestellt.
\subsection{Das Odd-Even-Transpositionsort-Netzwerk}
\label{sect:odd_even_transpositionsort}
\end{displaymath}
gilt.
-% gnuplot:
-% oem(n,m) = ((n*m) <= 1) ? (n*m) : oem(ceil(.5*n), ceil(.5*m)) + oem(floor(.5*n), floor(.5*m)) + floor(.5*(n+m-1.0))
-% oem1(n) = oem(ceil(.5*n),floor(.5*n))
-% oes(n) = (n <= 1.0) ? 0 : oes(ceil(0.5*n)) + oes(floor(0.5*n)) + oem1(n)
-
-%\begin{itemize}
-%\item Pairwise sorting-network
-%\end{itemize}
-
-\subsection{Das Pairwise-Sorting-Netzwerk}
-
-Das \emph{Pairwise-Sorting}-Netzwerk \ps{n} ist eine Konstruktionsvorschrift
-für Sortiernetzwerke, die 1992 von \textit{Ian Parberry} in seiner Arbeit „The
-Pairwise Sorting Network“ \cite{P1992} definiert wurde. Wenn die Anzahl der
-Leitungen $n = 2^d$ eine Zweierpotenz ist, hat das
-\emph{Pairwise-Sorting}-Netzwerk die selbe Effizienz und Geschwindigkeit wie
-das \emph{Odd-Even-Mergesort}-Netzwerk.
+%\subsection{Das Pairwise-Sorting-Netzwerk}
+%
+%Das \emph{Pairwise-Sorting}-Netzwerk \ps{n} ist eine Konstruktionsvorschrift
+%für Sortiernetzwerke, die 1992 von \textit{Ian Parberry} in seiner Arbeit „The
+%Pairwise Sorting Network“ \cite{P1992} definiert wurde. Wenn die Anzahl der
+%Leitungen $n = 2^d$ eine Zweierpotenz ist, hat das
+%\emph{Pairwise-Sorting}-Netzwerk die selbe Effizienz und Geschwindigkeit wie
+%das \emph{Odd-Even-Mergesort}-Netzwerk.
\newpage
\section{Transformation von Sortiernetzwerken}
\begin{figure}
\centering
- \subfigure[16-Sortiernetzwerk aus 60~Komparatoren in 10~Schichten. Das Netzwerk wurde von \textit{M.~W. Green} konstruiert und 1969 in \todo{Referenz} veröffentlicht.]{\input{images/16-green.tex}\label{fig:16-green}}
- \subfigure[16-Sortiernetzwerk aus 61~Komparatoren in 9~Schichten. Das Netzwerk wurde von \textit{D. Van~Voorhis} veröffentlicht.]{\input{images/16-voorhis.tex}\label{fig:16-voorhis}}
+ \subfigure[16-Sortiernetzwerk aus 60~Komparatoren in 10~Schichten. Das
+ Netzwerk wurde von \textit{M.~W. Green} konstruiert und 1969 in~\cite{G1972}
+ veröffentlicht.]{\input{images/16-green.tex}\label{fig:16-green}}
+ \subfigure[16-Sortiernetzwerk aus 61~Komparatoren in 9~Schichten. Das
+ Netzwerk wurde von \textit{D. Van~Voorhis} 1974 in~\cite{V1974}
+ veröffentlicht.]{\input{images/16-voorhis.tex}\label{fig:16-voorhis}}
\caption{Das effizienteste und das schnellste Sortiernetzwerk für
16~Leitungen, das derzeit bekannt ist.}
\label{fig:16-best-known}
gesamten Lösungsraums, begünstigt. Wählt man $w_{\mathrm{Basis}}$ hingegen
klein -- in Abhängigkeit von den anderen beiden Parametern sind auch negative
Werte möglich -- werden die relativen Unterschiede groß. Dadurch wird die {\em
-Exploitation}, das Streben zu (lokalen) Optima, verstärkt.
+Exploitation}, das Streben zu (lokalen) Optima, verstärkt. In~\cite{WW2002}
+geben \textit{Karsten und Nicole Weicker} einen Überblick über
+Selektionsmethoden und Rekombinationsmöglichkeiten.
Diese Parameter haben einen großen Einfluss auf die Geschwindigkeit, mit der
der \textsc{SN-Evolution}-Algorithmus konvergiert und ob er tatsächlich gute
w_{\mathrm{Schichten}} &=& 1
\end{eqnarray*}
geben dem Einsparen eines Komparators ein höheres Gewicht als dem Einsparen
-einer Schicht. \todo{Fehler hier noch was?}
+einer Schicht.
\subsection{Selektion}
35 & 93 & 13 \\
\rowcolor{green!10}
36 & 92 & 13 \\
- \rowcolor{green!10!white!95!black}
+ \rowcolor{green!10!white!95!black}
37 & 92 & 13 \\
38 & 93 & 13 \\
\hline
\subsection[Pairwise-Sorting-Netzwerk]{Versuche mit dem Pairwise-Sorting-Netzwerk}
+Eine weitere interessante Eingabe für \textsc{SN-Evolution-Cut} ist das
+\emph{Pairwise-Sorting}-Netzwerk \ps{n}, das \textit{Ian
+Parberry} in seiner Arbeit „The Pairwise Sorting Network“ \cite{P1992}
+definiert. Einerseits wurde in Abschnitt~\ref{sect:anzahl_schnittmuster}
+gezeigt, dass es für \ps{n} sehr viele \emph{unterschiedliche} Schnittmuster
+gibt. Andererseits sind die Sortiernetzwerke, die nach \textit{Parberrys}
+Methode erzeugt werden, genauso schnell und effizient wie das
+\emph{Odd-Even-Mergesort}-Netzwerk, wenn die Leitungszahl $n = 2^d$ eine
+Zweierpotenz ist.
+
% Effizienz
+Für viele Kombinationen von \ps{n} und $k$ sind die Sortiernetzwerke, die
+\textsc{SN-Evolution-Cut} ausgibt, weniger effizient als das entsprechende
+\ps{m}-Netzwerk. Für einige Kombinationen werden jedoch auch effizientere
+Netzwerke generiert, beispielsweise für $m = 11$ und $m = 20$. Die Effizienz
+der Sortiernetzwerke, die \textsc{SN-Evolution-Cut} auf Basis des
+\emph{Pairwise-Sorting}-Netzwerks berechnet, ist tabellarisch in
+Tabelle~\ref{tbl:ec-ps-efficiency} dargestellt.
+
\begin{table}
\begin{center}
\rowcolors{2}{black!5}{}
% Beispiel Effizienz
+Zwei Ergebnisse, die effizienter als die entsprechenden
+\emph{Pairwise-Sorting}-Netzwerke sind, zeigt
+Abbildung~\ref{fig:ec-ps-efficient_networks}. Sie erreichen die
+Geschwindigkeit und Effizienz des \emph{Odd-Even-Mergesort}-Netzwerks mit der
+entsprechenden Leitungszahl. Bei größeren Netzwerken, beispielsweise $m = 19$,
+ist dies mit der in Tabelle~\ref{tbl:ec-ps-efficiency} dargestellten Größe der
+Schnittmuster noch nicht zu beobachten.
+
\begin{figure}
\centering
\subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 10~Schichten. Das
\label{fig:ec-ps-efficient_networks}
\end{figure}
+% Wie viele Schnitte man braucht.
+
+Bei welchen Parametern \textsc{SN-Evolution-Cut} effiziente
+19-Sortiernetzwerke findet, ist Tabelle~\ref{tbl:ec-ps-19} zu entnehmen. Für
+$n = 31$, $k = 12$ und $n = 32$, $k = 13$ werden 19-Sortiernetzwerke mit der
+selben Effizienz und Geschwindigkeit wie \oes{19} erzeugt. Das
+19-Sortiernetzwerk, das auf diese Art und Weise aus \ps{32} erzeugt wurde, ist
+in Abbildung~\ref{fig:19-ec-from-ps32} dargestellt.
+
+\begin{table}
+ \begin{center}
+ \rowcolors{2}{black!5}{}
+ \begin{tabular}{|r|r|r|}
+ \hline
+ $n$ & Komp. & Schichten \\
+ \hline
+ 20 & 97 & 15 \\
+ 21 & 96 & 15 \\
+ 22 & 96 & 15 \\
+ 23 & 97 & 14 \\
+ 24 & 96 & 14 \\
+ 25 & 93 & 14 \\
+ 26 & 92 & 14 \\
+ 27 & 94 & 14 \\
+ 28 & 94 & 14 \\
+ 29 & 92 & 14 \\
+ 30 & 92 & 14 \\
+ \rowcolor{green!10!white!95!black}
+ 31 & 91 & 14 \\
+ \rowcolor{green!10}
+ 32 & 91 & 14 \\
+ 33 & 101 & 15 \\
+ 34 & 104 & 15 \\
+ 35 & 106 & 15 \\
+ 36 & 107 & 15 \\
+ 37 & 106 & 15 \\
+ 38 & 102 & 15 \\
+ \hline
+ \ps{19} & 97 & 15 \\
+ \oes{19} & 91 & 14 \\
+ \hline
+ \end{tabular}
+ \end{center}
+ \caption{Anzahl der Komparatoren und Schichten von 19-Sortiernetzwerken, die
+ von \textsc{SN-Evolution-Cut} aus \ps{n}, $n = 20, \dots, 38$ erzeugt
+ wurden.}
+ \label{tbl:ec-ps-19}
+\end{table}
+
+\begin{figure}
+ \begin{center}
+ \input{images/19-ec-from-ps32.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 19~Leitungen und 91~Komparatoren in
+ 14~Schichten. Das Netzwerk wurde von dem Algorithmus
+ \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting}-Netzwerk
+ $\operatorname{PS}(32)$ erzeugt.}
+ \label{fig:19-ec-from-ps32}
+\end{figure}
+
+An den Daten in Tabelle~\ref{tbl:ec-ps-19} fällt auf, dass die Effizienz und
+Geschwindigkeit der Ergebnisse für $n > 32$ schlechter werden. Das
+\emph{Pairwise-Sorting}-Netzwerk ist Leitungszahlen, die Zweierpotenzen sind,
+besonders effizient und schnell. Um der Vermutung nachzugehen, dass der
+\textsc{SN-Evolution-Cut}-Algorithmus für $\ps{n = 2^d}$ besonders effiziente
+Schnittmuster findet, wurde \textsc{SN-Evolution-Cut} mit \ps{32} und $k = 1
+\dots 16$ gestartet. Die Ergebnisse sind in Tabelle~\ref{tbl:ec-ps-32}
+zusammengefasst.
+
+\begin{table}
+ \begin{center}
+ \rowcolors{2}{black!5}{}
+ \begin{tabular}{|r|r|r|}
+ \hline
+ $m$ & Komp. & Schichten \\
+ \hline
+ 16 & 69 & 11 \\
+ 17 & 77 & 13 \\
+ 18 & 89 & 13 \\
+ 19 & 91 & 14 \\
+ 20 & 97 & 14 \\
+ 21 & 107 & 15 \\
+ 22 & 114 & 15 \\
+ 23 & 122 & 15 \\
+ 24 & 127 & 15 \\
+ 25 & 138 & 15 \\
+ 26 & 146 & 15 \\
+ 27 & 155 & 15 \\
+ 28 & 161 & 15 \\
+ 29 & 171 & 15 \\
+ 30 & 178 & 15 \\
+ 31 & 186 & 15 \\
+ \hline
+ \end{tabular}
+ \end{center}
+ \caption{Anzahl der Komparatoren und Schichten von $m$-Sortiernetzwerken,
+ die von \textsc{SN-Evolution-Cut} nach 5.000.000 Iterationen aus \ps{32}
+ erzeugt wurden.}
+ \label{tbl:ec-ps-32}
+\end{table}
+
% Geschwindigkeit
+Die Schnittmuster, die \textsc{SN-Evolution-Cut} für das
+\emph{Pairwise-Sorting}-Netzwerk berechnet, können zu schnelleren
+Sortiernetzwerken als \ps{m} führen. Beispielsweise konnte aus \ps{24} ein
+18-Sortiernetzwerk erzeugt werden, das mit 13~Schichten zwei parallele
+Schritte im Vergleich zu \ps{18} einspart. Eine Darstellung dieses
+Sortiernetzwerks befindet sich in Abbildung~\ref{fig:18-ec-from-ps24}. Für
+andere $m$ wurde die Geschwindigkeit des \emph{Pairwise-Sorting}-Netzwerks
+nicht übertroffen und im Fall von $m = 16$ wurde die Geschwindigkeit nicht
+einmal erreicht.
+
\begin{table}
\begin{center}
\rowcolors{2}{black!5}{}
ist bei dem Netzwerk in Abbildung~\ref{fig:32-ec-from-bs64} nicht ersichtlich,
wie und warum es jede beliebige Eingabe sortiert.
-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
-$\operatorname{PS}(32)$ und der Vorgabe, 16~Leitungen zu entfernen, erhält man
-ein Sortiernetzwerk, das die gleiche Anzahl Komparatoren und Schichten hat wie
-$\operatorname{PS}(16)$ und $\operatorname{OES}(16)$. Eines dieser
+Bei dem \emph{Pairwise-Sorting}-Netzwerk $\ps{n=2^d}$ ist das anders. Startet
+man \textsc{SN-Evolution-Cut} mit $\operatorname{PS}(32)$ und der Vorgabe,
+16~Leitungen zu entfernen, kann der Algorithmus ein Sortiernetzwerk
+zurückgeben, das die gleiche Anzahl Komparatoren und Schichten wie
+$\operatorname{PS}(16)$ und $\operatorname{OES}(16)$ hat. Eines dieser
Sortiernetzwerke ist in Abbildung~\ref{fig:16-ec-from-ps32} dargestellt.
+Dieses Ergebnis demonstriert, dass sich die Ergebnisse in den gezeigten
+Tabellen oft durch zusätzliche Iterationen verbessern lassen.
\begin{figure}
\begin{center}
\label{fig:16-ec-from-ps32}
\end{figure}
-Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even}-Mischer nicht
+Obwohl das \emph{Pairwise-Sorting}-Netzwerk den \emph{Odd-Even}-Mischer nicht
einsetzt und auch nicht auf einem Mischer basiert, ist das
\emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM}(8,8)$ im Sortiernetzwerk in
Abbildung~\ref{fig:16-ec-from-ps32} eindeutig erkennbar (Schichten~7--10). In
\label{fig:16-pairwise}
\end{figure}
-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 Verwandtschaft von $\operatorname{PS}(n)$ und \oes{n}
-untersucht \textit{Moritz Mühlenthaler} ausführlich in~\cite{M2009}.
+Ein Spezialfall ergibt sich, wenn \textsc{SN-Evolution-Cut} auf
+$\operatorname{PS}(16)$ angewendet wird: In diesem Fall kann ein
+8-Schnittmuster ausgegeben werden, das \emph{Odd-Even-Mergesort}-Netzwerk
+\oes{8} aus \ps{16} erzeugt.. 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 Verwandtschaft von
+$\operatorname{PS}(n)$ und \oes{n} untersucht \textit{Moritz Mühlenthaler}
+ausführlich in~\cite{M2009}.
\newpage
\section{Fazit und Ausblick}
projects / diplomarbeit.git / blobdiff