\tikzstyle{red box} = [draw,-,color=red, top color=red!2,bottom color=red!10]
\tikzstyle{blue box} = [draw,-,color=blue,top color=blue!2,bottom color=blue!10]
\tikzstyle{green box} = [draw,-,color=teal,top color=teal!2,bottom color=teal!10]
-\tikzstyle{gray box} = [draw,-,color=black, top color=black!2,bottom color=black!10]
+\tikzstyle{gray box} = [draw,-,color=black, top color=black!2,bottom color=black!10]
\maketitle
\begin{abstract}
\end{figure}
Der Mischer funktioniert folgendermaßen: Gegeben sind zwei Folgen mit je
-${m = \frac{n}{2}}$~Elementen, ${u_0, u_1, \ldots, u_{m-1}}$ und
-${v_0, v_1, \ldots, v_{m-1}}$. Die Folge der $u_i$ sei aufsteigend sortiert,
-die Folge der $v_i$ sei absteigend sortiert:
+${m = \frac{n}{2}}$ Elementen, $U = \left(u_0, u_1, \ldots, u_{m-1}\right)$ und
+$V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die Folge $U$ sei aufsteigend
+sortiert, die Folge $V$ sei absteigend sortiert:
\begin{eqnarray}
u_0 \leqq u_1 \leqq &\ldots& \leqq u_{m-1} \\
v_0 \geqq v_1 \geqq &\ldots& \geqq v_{m-1}
Netzwerk ist von K.~Batcher gefunden worden und wird rekursiv durch einen
"`Mischer"' definiert.
-\subsubsection{Der Odd-Even-Mischer}
+\subsubsection{Der Odd-Even-Mischer}\label{sect:der_odd_even_mischer}
Der {\em Odd-Even-Mischer} ist ein Komperatornetzwerk, dass zwei sortierte
Folgen zu einer sortierten Ausgabe zusammenfügen kann. Dabei kommt es mit
\begin{center}
\input{images/oe-mergesort-8.tex}
\end{center}
-\caption{Das {\em Odd-Even-Mergesort} Netzwerk für acht Eingänge.}
+\caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge.}
\label{fig:odd_even_mergesort_08}
\end{figure}
\item Nach dem Pairwise sorting-network Schema.
\end{itemize}
-\subsection{Leitungen entfernen}
+\subsection{Leitungen entfernen}\label{sect:leitungen_entfernen}
+
+Man kann ein gegebenes Sortiernetzwerk mit $n$~Eingängen auf ein
+Sortiernetzwerk mit $(n-1)$~Leitungen verkleinern, indem man eine Leitung
+entfernt. Zunächst wird angenommen, dass das Minimum oder das Maximum an einem
+der Eingänge anliegt. Der Weg durch das Netzwerk zum entsprechenden Ausgang
+ist dadurch fest vorgegeben, insbesondere welche Komparatoren dafür sorgen,
+dass die Leitung gewechselt wird und welche nicht.
+Abbildung~\ref{fig:oe-transposition-cut0} zeigt den Weg eines Maximums durch
+das {\em Odd-Even-Transpositionsort-Netzwerk}.
+
+Im nächsten Schritt werden alle beteiligten Komparatoren gelöscht bzw.
+ersetzt: Komparatoren, die {\em nicht} zu einem Wechsel der Leitung geführt
+haben, werden ersatzlos gelöscht. Diese Komparatoren sind in
+Abbildung~\ref{fig:oe-transposition-cut0} grün markiert. Die Komparatoren, die
+zum Wechsel der Leitung geführt haben, werden durch sich kreuzende Leitungen
+ersetzt. Das Resultat zeigt Abbildung~\ref{fig:oe-transposition-cut1}. Wenn
+man die Maximum-Leitung entfernt (Abbildung~\ref{fig:oe-transposition-cut2}),
+erhält man ein Sortiernetzwerk für $(n-1)$~Leitungen.
\begin{figure}
\centering
letzten Abbildung ist $\textrm{OET}(7)$ markiert.}
\end{figure}
+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.
+
\begin{itemize}
\item Min-Richtung
\item Max-Richtung
\section{Der evolutionäre Ansatz}
+Um einen evolutionären Algorithmus für Sortiernetzwerke zu entwickeln, werden
+die vorgestellten Methoden kombiniert.
+
+\subsection{Bewertungsfunktion}
+
+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}
+ \mathit{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}
+
+{\em Mutation ist schwierig, weil es die Sortiereigenschaft eben nicht
+erhält.}
+
+
\begin{itemize}
\item Güte von Sortiernetzwerken (Anzahl der Komparatoren, Anzahl der
Schichten, kobiniert)
\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 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}
projects / diplomarbeit.git / commitdiff