\newpage
\tableofcontents
-\newpage
+\newpage
\section{Motivation und Einleitung}
\subsection{Motivation}\label{sect:motivation}
Mutation \textit{(vermutlich)} nicht (effizient) möglich.
\end{itemize}
+\newpage
\section{Bekannte konstruktive Sortiernetzwerke}
Übersicht über bekannte konstruktive Sortiernetzwerke.
%\item Pairwise sorting-network
%\end{itemize}
+\newpage
\section{Transformation von Sortiernetzwerken}
\subsection{Komprimieren}
Eingänge unterscheiden, wird anschließend der Komparator entfernt, so dass
sich die Resultate auch in der ersten Schicht nicht unterscheiden.
-\subsubsection{Der \textsc{SN-Evolution-Cut}-Algorithmus}
+\todo{Mit \textit{Approximate Counting} könnte man die Anzahl der
+\emph{unterschiedlichen} Schnittmuster genauer abschätzen.}
+
+\newpage
+\section{Der \textsc{SN-Evolution}-Algorithmus}
+
+Um einen evolutionären Algorithmus für Sortiernetzwerke zu entwickeln, werden
+die vorgestellten Methoden kombiniert.
+
+\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,
+die interessant sind:
+\begin{itemize}
+ \item Möglichst wenige Komparatoren ("`klein"')
+ \item Möglichst wenige Schichten ("`schnell"')
+\end{itemize}
+
+Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das
+kleinste bekannte Sortiernetzwerk für 16~Eingänge besteht aus 60~Komparatoren
+in 10~Schichten. Das schnellste Netzwerk besteht aus 61~Komparatoren in nur
+9~Schichten.
+
+Eine Gütefunktion, die die beiden Ziele "`klein"' und "`schnell"'
+berücksichtigen kann, hat die folgende allgemeine Form:
+\begin{equation}
+ \operatorname{Guete}(S) = w_{\mathrm{Basis}}
+ + w_{\mathrm{Komparatoren}} \cdot \left|S\right|_\mathrm{Komparatoren}
+ + w_{\mathrm{Schichten}} \cdot \left|S\right|_\mathrm{Schichten}
+\end{equation}
+Die Parameter $w_{\mathrm{Komparatoren}}$ und $w_{\mathrm{Schichten}}$ dienen
+dabei der Festlegung des Optimierungsziels. Wenn einer der beiden Parameter
+gleich Null ist, wird nur das jeweils andere Ziel verfolgt. Sind beide
+Parameter gleich Null, werden alle Netzwerke mit der gleich Güte bewertet --
+jegliche Ergebnisse sind dann rein zufälliger Natur.
+
+Mit dem Parameter $w_{\mathrm{Basis}}$ kann auf die Selektion Einfluss
+genommen werden. Ist er groß, wird der relative Unterschied der Güten
+verschiedener Netzwerke kleiner, was die {\em Exploration}, das Absuchen des
+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 Finden lokaler Optima, bevorzugt.
+
+\subsection{Selektion}
+
+...
+
+\subsection{Rekombination}
+
+Bei der Rekombination werden zwei Individuen --~hier Sortiernetzwerke~-- zu
+einer neuen Lösung kombiniert. Dazu verwenden wir einen Mischer, zum Beispiel
+den {\em bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) oder den
+{\em Odd-Even-Mischer} (Abschnitt~\ref{sect:der_odd_even_mischer}), um die
+beiden Netzwerke zu einem Netzwerk mit $2n$~Leitungen zusammenzufügen.
+Anschließend entfernen wir zufällig $n$~Leitungen wie in
+Abschnitt~\ref{sect:leitungen_entfernen} beschrieben.
+
+Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft
+erhält.
+
+\subsection{Mutation}
+
+Zu einem vollständigen evolutionären Algorithmus gehört außerdem eine 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
+erhalten. Selbst das \emph{Hinzufügen} eines zufälligen Komparators kann diese
+Eigenschaft zerstören.
+
+Nach einer Mutation müsste man überprüfen, ob das neue Komparatornetzwerk die
+Sortiereigenschaft noch besitzt. Nach heutigem Wissenstand ist diese
+Überprüfung nur mit exponentiellem Aufwand möglich, etwa durch das
+Ausprobieren aller $2^n$~Bitmuster.
+
+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.
+
+\begin{itemize}
+\item Güte von Sortiernetzwerken (Anzahl der Komparatoren, Anzahl der
+Schichten, kobiniert)
+\item Rekombination: Merge Anhängen und Leitungen entfernen.
+\end{itemize}
+
+Ein Beispielnetzwerk, das von dem Algorithmus gefunden wird, zeigt
+Abbildung~\ref{fig:evolutionary_08}.
+
+\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}
+
+\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}
+
+\subsection{Güte}
+
+\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 Ggf. Abschnitt „Shmoo-Äquivalenz“ kürzen und hier einbauen.
+\end{itemize}
+
+%\input{shmoo-aequivalenz.tex}
+
+\newpage
+\section{Der \textsc{SN-Evolution-Cut}-Algorithmus}
\label{sect:sn-evolution-cut}
Das Programm \textsc{SN-Evolution-Cut} implementiert einen evolutionären
auf einen neuen Wert $l$ mit $0 \leqq l \le n-i$ oder invertiert die
Schnitt-Richtung.
-% bitones Mergesort-Netzwerk
+\subsection{Versuche mit dem bitonen Mergesort-Netzwerk}
In \cite{MW2010} zeigen \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka},
wie man einen bitonen Mischer, der nach Batchers Methode konstruiert wurde,
leicht invertieren lassen, werden der Fall, dass es mehr Minimumschnitte, und
der Fall, dass es mehr Maximumschnitte gibt, nicht unterschieden.
-
-
-% Odd-Even-Transpositionsort-Netzwerk
-
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
\label{fig:16-ec-from-ps32}
\end{figure}
-% Pairwise-Sorting-Netzwerk
+\subsection{Versuche mit dem Pairwise-Sorting-Netzwerk}
Anders verhält sich das \emph{Pairwise-Sorting-Netzwerk}
$\operatorname{PS}(n)$, das \textit{Ian Parberry} in seiner Arbeit „The
Wendet man \textsc{SN-Evolution-Cut} auf $\operatorname{PS}(16)$ an, so kann
man $\operatorname{OES}(8)$ erhalten.
-% Odd-Even-Mergesort-Netzwerk
+\subsection{Versuche mit dem Odd-Even-Mergesort-Netzwerk}
\todo{Schreibe noch etwas zum Odd-Even-Mergesort-Netzwerk.}
\item Abschnitt „Optimierung der Schnitte“ hier einbauen.
\end{itemize}
-\section{Der \textsc{SN-Evolution}-Algorithmus}
-
-Um einen evolutionären Algorithmus für Sortiernetzwerke zu entwickeln, werden
-die vorgestellten Methoden kombiniert.
-
-\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,
-die interessant sind:
-\begin{itemize}
- \item Möglichst wenige Komparatoren ("`klein"')
- \item Möglichst wenige Schichten ("`schnell"')
-\end{itemize}
-
-Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das
-kleinste bekannte Sortiernetzwerk für 16~Eingänge besteht aus 60~Komparatoren
-in 10~Schichten. Das schnellste Netzwerk besteht aus 61~Komparatoren in nur
-9~Schichten.
-
-Eine Gütefunktion, die die beiden Ziele "`klein"' und "`schnell"'
-berücksichtigen kann, hat die folgende allgemeine Form:
-\begin{equation}
- \operatorname{Guete}(S) = w_{\mathrm{Basis}}
- + w_{\mathrm{Komparatoren}} \cdot \left|S\right|_\mathrm{Komparatoren}
- + w_{\mathrm{Schichten}} \cdot \left|S\right|_\mathrm{Schichten}
-\end{equation}
-Die Parameter $w_{\mathrm{Komparatoren}}$ und $w_{\mathrm{Schichten}}$ dienen
-dabei der Festlegung des Optimierungsziels. Wenn einer der beiden Parameter
-gleich Null ist, wird nur das jeweils andere Ziel verfolgt. Sind beide
-Parameter gleich Null, werden alle Netzwerke mit der gleich Güte bewertet --
-jegliche Ergebnisse sind dann rein zufälliger Natur.
-
-Mit dem Parameter $w_{\mathrm{Basis}}$ kann auf die Selektion Einfluss
-genommen werden. Ist er groß, wird der relative Unterschied der Güten
-verschiedener Netzwerke kleiner, was die {\em Exploration}, das Absuchen des
-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 Finden lokaler Optima, bevorzugt.
-
-\subsection{Selektion}
-
-...
-
-\subsection{Rekombination}
-
-Bei der Rekombination werden zwei Individuen --~hier Sortiernetzwerke~-- zu
-einer neuen Lösung kombiniert. Dazu verwenden wir einen Mischer, zum Beispiel
-den {\em bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) oder den
-{\em Odd-Even-Mischer} (Abschnitt~\ref{sect:der_odd_even_mischer}), um die
-beiden Netzwerke zu einem Netzwerk mit $2n$~Leitungen zusammenzufügen.
-Anschließend entfernen wir zufällig $n$~Leitungen wie in
-Abschnitt~\ref{sect:leitungen_entfernen} beschrieben.
-
-Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft
-erhält.
-
-\subsection{Mutation}
-
-Zu einem vollständigen evolutionären Algorithmus gehört außerdem eine 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
-erhalten. Selbst das \emph{Hinzufügen} eines zufälligen Komparators kann diese
-Eigenschaft zerstören.
-
-Nach einer Mutation müsste man überprüfen, ob das neue Komparatornetzwerk die
-Sortiereigenschaft noch besitzt. Nach heutigem Wissenstand ist diese
-Überprüfung nur mit exponentiellem Aufwand möglich, etwa durch das
-Ausprobieren aller $2^n$~Bitmuster.
-
-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.
-
-\begin{itemize}
-\item Güte von Sortiernetzwerken (Anzahl der Komparatoren, Anzahl der
-Schichten, kobiniert)
-\item Rekombination: Merge Anhängen und Leitungen entfernen.
-\end{itemize}
-
-Ein Beispielnetzwerk, das von dem Algorithmus gefunden wird, zeigt
-Abbildung~\ref{fig:evolutionary_08}.
-
-\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}
-
-\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}
-
-\subsection{Güte}
-
-\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.
-\end{itemize}
-
+\newpage
\section{Der \textsc{SN-Markov}-Algorithmus}
Der evolutionäre \textsc{SN-Evolution}-Algorithmus aus dem vorherigen
\label{fig:markov-comparators-16}
\end{figure}
-%\input{shmoo-aequivalenz.tex}
-
-\section{Optimierung der Schnitte}
-
-\todo{In den Abschnitt "`Leitungen entfernen"' einbauen.}
-
-Abbildung~\ref{fig:32-ec-from-bs64} zeigt ein 32-Sortiernetzwerk, dass vom
-\textsc{SN-Evolution-Cut}-Algorithmus aus dem $BS(64)$-Netzwerk erzeugt wurde.
-Es besteht aus 206~Komparatoren in 15~Schichten -- 34~Komparatoren weniger als
-$BS(32)$ und zwei Komparatoren weniger als das Netzwerk, das nach Mühlenthaler
-und Wankas Methode konstruiert wird. Die Anzahl der Schichten ist bei allen
-Netzwerken gleich.
-
-\textbf{TODO:} $BS(128) \rightarrow n=64$: 584~Komparatoren in 21~Schichten
-möglich (nach ca. 600k Iterationen). Moritz und Rolf: $672-80=592$
-Komparatoren; $BS(64)$: 672~Komparatoren.
-
-Schnitt-Sequenz:
-MIN( 92)
-MAX( 80)
-MIN(100)
-MAX( 54)
-MAX(102)
-MAX( 53)
-MAX(105)
-MAX( 6)
-MAX( 99)
-MAX( 79)
-MAX( 26)
-MIN(111)
-MAX( 12)
-MIN( 22)
-MAX( 61)
-MAX( 72)
-MAX( 68)
-MIN( 80)
-MAX( 80)
-MAX( 99)
-MAX(105)
-MAX( 0)
-MIN( 8)
-MAX( 40)
-MAX( 74)
-MAX( 40)
-MAX( 40)
-MIN( 56)
-MAX( 27)
-MAX( 13)
-MAX( 1)
-MAX( 81)
-MAX( 17)
-MAX( 4)
-MIN( 36)
-MIN( 22)
-MAX( 13)
-MIN( 72)
-MAX( 24)
-MAX( 5)
-MIN( 10)
-MAX( 59)
-MIN( 37)
-MAX( 65)
-MAX( 46)
-MAX( 73)
-MAX( 58)
-MAX( 29)
-MAX( 65)
-MIN( 23)
-MAX( 56)
-MAX( 11)
-MIN( 75)
-MIN( 51)
-MIN( 46)
-MIN( 34)
-MAX( 32)
-MAX( 6)
-MAX( 37)
-MIN( 4)
-MIN( 28)
-MIN( 20)
-MAX( 33)
-MAX( 34)
-
-% images/32-ec-1277190372.tex
-
+\newpage
\section{Empirische Beobachtungen}
\begin{itemize}
\item $\ldots$
\end{itemize}
+\newpage
\section{Ausblick}
Das würde mir noch einfallen$\ldots$
+\newpage
\bibliography{references}
\bibliographystyle{plain}
projects / diplomarbeit.git / commitdiff