\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}
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
\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
\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}
beschrieben und initial analysiert worden. Eine weitere Gemeinsamkeit besteht
darin, dass es ebenfalls rekursiv durch einen Mischer definiert ist.
-\subsubsection{Der Odd-Even-Mischer}\label{sect:der_odd_even_mischer}
+\subsubsection{Der \emph{Odd-Even}-Mischer}\label{sect:der_odd_even_mischer}
-Der \emph{Odd-Even-Mischer} $\operatorname{OEM}(n,m)$ ist ein
+Der \emph{Odd-Even}-Mischer $\operatorname{OEM}(n,m)$ ist ein
Komperatornetzwerk, dass zwei sortierte Folgen mit $n$ beziehungsweise $m$
Elementen zu einer sortierten Ausgabefolge mit $N = n+m$~Elementen
zusammenfügen kann. Dabei kommt es mit weniger Vergleichen aus als der
\emph{bitone Mischer}, der im Abschnitt~\ref{sect:der_bitone_mischer}
-vorgestellt wurde. Allerdings benötigt der \emph{Odd-Even-Mischer} unter
+vorgestellt wurde. Allerdings benötigt der \emph{Odd-Even}-Mischer unter
Umständen mehr Schichten als der \emph{bitone Mischer}.~\cite{KNUTH}
-Der \emph{Odd-Even-Mischer} selbst ist ebenfalls rekursiv aufgebaut: Die
+Der \emph{Odd-Even}-Mischer selbst ist ebenfalls rekursiv aufgebaut: Die
Eingabe für den Mischer mit $N = n + m$ Leitungen besteht aus den beiden
sortierten Folgen $U = \left(u_0, u_1, \ldots, u_{n-1}\right)$ und
$V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die gesamte Eingabe sei
Die geraden Folgen $U_{\textrm{gerade}}$ und $V_{\textrm{gerade}}$ bzw. die
ungeraden Folgen $U_{\textrm{ungerade}}$ und $V_{\textrm{ungerade}}$ werden
-rekursiv von kleineren {\em Odd-Even-Mischern} zusammengefügt, so dass sich am
+rekursiv von kleineren \emph{Odd-Even}-Mischern zusammengefügt, so dass sich am
Ausgang der Mischer die Folgen
\begin{eqnarray}
W_{\textrm{gerade}} &=& \left(w_0, w_2, w_4, \ldots\right) \\
\begin{equation}
w_{2i-1} \longleftrightarrow w_{2i}, \quad 1 \leqq i < \frac{N}{2}
\end{equation}
-die die Folge~$W$ sortieren. Den schematischen Aufbau des {\em
-Odd-Even-Mischers} zeigt Abbildung~\ref{fig:oe-merge}.
+die die Folge~$W$ sortieren. Den schematischen Aufbau des
+\emph{Odd-Even}-Mischers zeigt Abbildung~\ref{fig:oe-merge}.
Leider bricht die Rekursion nicht so schön ab, wie das beim {\em bitonen
Mischer} der Fall gewesen ist. Insbesondere für ${n = m = 1}$ würde --
\qquad
\subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 2$]{\input{images/oe-post-recursive-diff2.tex}}
\caption{Die drei Situationen, die nach dem Verzahnen der Ausgaben der
- kleineren {\em Odd-Even-Mischer} entstehen können. Ist die Differenz der
+ kleineren \emph{Odd-Even}-Mischer entstehen können. Ist die Differenz der
Anzahl der Nullen gleich $0$ oder $1$, ist die Folge bereits sortiert. Im
letzten Fall stellt einer der Komparatoren sicher, dass das Ergebnis
sortiert ist.}
Das \emph{Odd-Even-Mergesort-Netzwerk} $\operatorname{OES}(n)$ besteht --~wie
das \emph{bitone Mergesort-Netzwerk}~-- rekursiv aus kleineren Varianten von
-sich selbst und einem abschließenden \emph{Odd-Even-Mischer}. Die
+sich selbst und einem abschließenden \emph{Odd-Even}-Mischer. Die
effizientesten Sortiernetzwerke in Bezug auf Komparator- und Schichtzahl
entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht
$\operatorname{OES}(n)$ aus
\end{center}
\caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge. Markiert
sind die Instanzen von $\operatorname{OES}(4)$ (rot), die beiden
- \emph{Odd-Even-Mischer} $\operatorname{OEM}(4)$ für gerade und ungerade
+ \emph{Odd-Even}-Mischer $\operatorname{OEM}(4)$ für gerade und ungerade
Leitungen (blau) und die im ersten Rekursionsschritt hinzugefügten
Komparatoren zwischen benachbarten Leitungen (grün).}
\label{fig:odd-even-mergesort-08}
In Abbildung~\ref{fig:odd-even-mergesort-08} ist das konkrete Sortiernetzwerk
$\operatorname{OES}(8)$ zu sehen. Rot markiert sind die beiden rekursiven
Instanzen $\operatorname{OES}(4)$. Die blauen und der grüne Block stellen den
-\emph{Odd-Even-Mischer} für acht Leitungen dar: Die beiden blauen Blöcke sind
+\emph{Odd-Even}-Mischer für acht Leitungen dar: Die beiden blauen Blöcke sind
die rekursiven Instanzen von $\operatorname{OEM}(4)$, der grüne Block markiert
die Komparatoren, die in ersten Rekursionsschritt hinzugefügt werden.
Komprimierung durchgeführt werden.
\subsection{Normalisieren}
+\label{sect:normalisieren}
\begin{figure}
\centering
neun Schichten angeordnet sind. Es sind allerdings Sortiernetzwerke mit neun
Eingängen bekannt, die lediglich 25~Komparatoren in sieben Schichten
benötigen. Kombiniert man zwei dieser Netzwerke mit dem
-\emph{Odd-Even-Mischer} erhält man ein Sortiernetzwerk mit 18~Eingängen, das
+\emph{Odd-Even}-Mischer erhält man ein Sortiernetzwerk mit 18~Eingängen, das
80~Komparatoren in 11~Schichten benötigt -- $\operatorname{OES}(18)$ benötigt
82~Komparatoren in 13~Schichten. Damit ist das resultierende Netzwerk so
schnell wie das Sortiernetzwerk mit 18~Eingängen, das \textit{Sherenaz~W.
\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}
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}
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}.
\textit{Moritz Mühlenthaler} zeigt in seiner Arbeit~\cite{M2009}, dass es
möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise Maximum
-vorzubelegen. Dadurch wird die Anzahl der möglichen Schnittmuster reduziert,
-die Menge der so erzeugbaren Sortiernetzwerke bleibt aber unverändert. Die
-Anzahl der möglichen Schnittmuster setzt sich zusammen aus der Anzahl von
-Möglichkeiten, $k$~Leitungen aus $n$~Leitungen auszuwählen, und die möglichen
-Minimum-~/ Maximum-Muster. Damit ergibt sich folgende Formel für die Anzahl
-der möglichen Schnittmuster:
+vorzubelegen, ohne die Menge der erreichbaren Sortiernetzwerke einzuschränken.
+Dadurch wird die Anzahl der möglichen Schnittmuster reduziert, die Menge der
+so erzeugbaren Sortiernetzwerke bleibt aber unverändert. Die Anzahl der
+möglichen Schnittmuster setzt sich zusammen aus der Anzahl von Möglichkeiten,
+$k$~Leitungen aus $n$~Leitungen auszuwählen, und die möglichen Minimum-~/
+Maximum-Muster. Damit ergibt sich folgende Formel für die Anzahl der möglichen
+Schnittmuster:
\begin{displaymath}
2^k \cdot \left( \begin{array}{c} n \\ k \end{array} \right)
= 2^{k} \cdot \frac{n!}{k! (n-k)!}
8-Schnittmuster aus $\operatorname{OES}(16)$, $\operatorname{BS}(16)$ und
$\operatorname{PS}(16)$ hervorgegangen sind. Die Anzahl der
unterschiedlichen Netzwerke nach $10^6$~Iterationen ist 3519 für das
- \emph{Odd-Even-Mergesort-Netzwerk}, 4973 für das \emph{bitone
- Mergesort-Netzwerk} und 18764 für das \emph{Pairwise-Sorting-Netzwerk}.}
+ \emph{Odd-Even-Mergesort}-Netzwerk, 4973 für das \emph{bitone
+ Mergesort}-Netzwerk und 18764 für das \emph{Pairwise-Sorting}-Netzwerk.}
\label{fig:count-cuts-16}
\end{figure}
Formel~\eqref{eqn:anzahl_schnittmuster} 3.294.720. Diese möglichen
Schnittmuster führen aber nur zu wenigen \emph{unterschiedlichen}
Sortiernetzwerken: 3519 ($\approx 0,1\%$) im Fall des
-\emph{Odd-Even-Mergesort-Netzwerks}, 4973 ($\approx 0,15\%$) beim
-\emph{bitonen Mergesort-Netzwerk} und 18764 ($\approx 0,57\%$) beim
-\emph{Pairwise-Sorting-Netzwerk}. Zwar ist es möglich, dass mehr Iterationen
+\emph{Odd-Even-Mergesort}-Netzwerks, 4973 ($\approx 0,15\%$) beim
+\emph{bitonen Mergesort}-Netzwerk und 18764 ($\approx 0,57\%$) beim
+\emph{Pairwise-Sorting}-Netzwerk. Zwar ist es möglich, dass mehr Iterationen
die Anzahl der unterschiedlichen Schnittmuster noch wachsen lässt. Die Graphen
in Abbildung~\ref{fig:count-cuts-16} geben jedoch Grund zu der Annahme, dass
die Anzahl dieser zusätzlichen, unterschiedlichen Schnittmuster
Um die Anzahl der unterschiedlichen Schnittmuster trotzdem abschätzen zu
können, kann man sich einer stochastischen Methode bedienen, der sogenannten
-\emph{Monte-Carlo-Methode}. Zunächst generiert man eine Menge~$S$ von
+\emph{Monte-Carlo-Methode}, die \textit{Rolf Wanka} in~\cite{W2006} für
+schwierige Zählprobleme vorstellt. Zunächst generiert man eine Menge~$S$ von
$k$~unterschiedlichen Schnittmustern. Anschließend werden $n$~Schnittmuster
zufällig erzeugt und überprüft, ob sie in der Menge~$S$ enthalten sind. Unter
der Annahme, dass das Verhältnis der zufälligen Schnittmuster, die in $S$
Die in \textsc{SN-Evolution} implementierte Selektion lässt sich mithilfe von
Pseudocode wie folgt beschreiben:
\begin{verbatim}
-Gütesumme := 0
-Auswahl := (leer)
-
-für jedes Individuum in Population
-{
- reziproke Güte := 1.0 / Guete(Individuum)
- Wahrscheinlichkeit P := reziproke Güte / (Gütesumme + reziproke Güte)
- Gütesumme := Gütesumme + reziproke Güte
-
- mit Wahrscheinlichkeit P
+ Gütesumme := 0
+ Auswahl := (leer)
+
+ für jedes Individuum in Population
{
- Auswahl := Individuum
+ reziproke Güte := 1.0 / Guete(Individuum)
+ Wahrscheinlichkeit P := reziproke Güte / (Gütesumme + reziproke Güte)
+ Gütesumme := Gütesumme + reziproke Güte
+
+ mit Wahrscheinlichkeit P
+ {
+ Auswahl := Individuum
+ }
}
-}
-gib Auswahl zurück
+ gib Auswahl zurück
\end{verbatim}
\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
+\emph{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.
+Anschließend werden zufällig $n$~Leitungen mit einem $n$-Schnittmuster wie in
+Abschnitt~\ref{sect:leitungen_entfernen} beschrieben entfernt.
Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft
-erhält.
+erhält. Entsprechend muss nicht aufwendig überprüft werden, ob das
+Komparatornetzwerk die Sortiereigenschaft besitzt. Der Nachteil ist, dass
+nicht alle Sortiernetzwerke auf diese Art und Weise erzeugt werden können.
\subsection{Mutation}
80~Komparatoren, das Sortiernetzwerk in
Abbildung~\ref{fig:16-e1-bitonic-1296542566} benötigt lediglich~67.
-\subsection{Versuche mit dem Odd-Even-Mischer}
+\subsection{Versuche mit dem \emph{Odd-Even}-Mischer}
\begin{figure}
\begin{center}
\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}
+ \textsc{SN-Evolution} unter Verwendung des \emph{Odd-Even}-Mischers
erzeugt.}
\label{fig:16-e1-oddeven-1296543330}
\end{figure}
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
+\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
+\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
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
\label{fig:32-ec-from-bs64}
\end{figure}
-Das Ergebnis von \textit{Mühlenthaler} von \textit{Wanka}, die den bitonen
+Das Ergebnis von \textit{Mühlenthaler} und \textit{Wanka}, die den bitonen
Mischer optimiert und anschließend aus diesen Mischern ein Sortiernetzwerk
konstruiert haben, kann demnach auch erreicht werden, wenn
$\operatorname{BS}(32)$ auf ein 16-Sortiernetzwerk reduziert wird. Bei anderen
$\operatorname{OES}(16)$. Eines dieser Sortiernetzwerke ist in
Abbildung~\ref{fig:16-ec-from-ps32} dargestellt.
-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 der
$\operatorname{OEM}(8,8)$ im Sortiernetzwerk in
Abbildung~\ref{fig:16-ec-from-ps32} eindeutig erkennbar (Schichten~7--10). In
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 20.000, 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
Algorithmus wie folgt beschreiben:
\begin{verbatim}
-Netzwerk := Eingabe
-
-für n Iterationen
-{
- Nachfolger := kombiniere (Netzwerk, Netzwerk)
- Netzwerk := Nachfolger
-}
-
-gib Netzwerk zurück
+ Netzwerk := Eingabe
+
+ für n Iterationen
+ {
+ Nachfolger := kombiniere (Netzwerk, Netzwerk)
+ Netzwerk := Nachfolger
+ }
+
+ gib Netzwerk zurück
\end{verbatim}
-Die Abbildungen~\ref{fig:markov-comparators-12},
-\ref{fig:markov-comparators-14}, \ref{fig:markov-comparators-12},
-\ref{fig:markov-comparators-16} und~\ref{fig:markov-comparators-18} zeigen die
-Anzahl der Komparatoren der Sortiernetzwerke, die \textsc{SN-Markov} auf
-seinem zufälligen Pfad durchläuft. Ausserdem eingezeichnet ist eine
-\emph{Gamma-Verteilung}.
+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}
+ \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-cycles-16.pdf}
+ \includegraphics[viewport=0 0 425 262,width=15cm]{images/comparison-comparators-16.pdf}
\end{center}
- \caption{Zyklen, die beim \textit{Random Walk} des
- \textsc{SN-Markov}-Algorithmus detektiert wurden. Auf der x-Achse sind die
- Anzahl der Schritte, die \textsc{SN-Markov} zurückgelegt hat, auf der
- y-Achse die Längen der gefundenen Zyklen aufgetragen. Das initiale
- Start-Sortiernetzwerk war $\operatorname{OET}(16)$.}
- \label{fig:markov-cycles-16}
+ \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}) besaßen.}
+ \label{fig:comparison-comparators}
\end{figure}
+Dass der \textsc{SN-Markov}-Algorithmus nicht schlechter ist als der
+\textsc{SN-Evolution}-Algo\-rithmus, ist aus dem Graphen in
+Abbildung~\ref{fig:comparison-comparators} ersichtlich. Analog zu dem Versuch
+mit \textsc{SN-Markov}, wurde beim \textsc{SN-Evolution}-Algorithmus die
+Anzahl der Komparatoren jedes neuen Individuums ermittelt und gespeichert. Als
+Startnetzwerk diente bei beiden Algorithmen das
+\emph{Odd-Even-Transpositionsort}-Netzwerk \oet{16}. Der Graph zeigt auf der
+x-Achse die Anzahl der Komparatoren, auf der y-Achse die Häufigkeit, mit der
+ein Sortiernetzwerk mit dieser Komparatorzahl durch die Rekombination erzeugt
+wurde. Die Ergebnisse von \textsc{SN-Evolution} unterscheiden außerdem nach
+dem verwendeten Mischer-Netzwerk -- \oem{32} beziehungsweise \bm{32}.
+
+Sowohl der \textsc{SN-Markov}-Algorithmus, der das
+\emph{Odd-Even-Merge}-Netzwerk verwendet, als auch \textsc{SN-Evolution} mit
+\oem{32} erreichen eine Komparatorzahl von~63 und finden Sortiernetzwerke, die
+bezüglich Effizienz und Geschwindigkeit identisch zu \oes{16} sind.
+Interessanterweise erzeugt \textsc{SN-Markov} derartige Netzwerke häufiger:
+Während nur $0,000017 \%$ der Individuen von \textsc{SN-Evolution} mit
+63~Komparatoren auskamen, ist die Rate bei \textsc{SN-Markov} mit $0,000335
+\%$ rund 20~mal höher.
+
+Erwartunggemäß sind die besten Netzwerke, die \textsc{SN-Evolution} mit dem
+\emph{bitonen Mischer} findet, aus 67~Komparatoren aufgebaut. Überraschend ist
+jedoch, dass in dieser Konfiguration Sortiernetzwerke auftreten können, die
+mehr Komparatoren besitzen als \emph{Odd-Even-Transpositionsort} -- \oet{16}
+ist aus 120~Komparatoren aufgebaut, bei dem Lauf, der die Daten für
+Abbildung~\ref{fig:comparison-comparators} lieferte, traten auch jeweils ein
+Sortiernetzwerk mit 121 und 124~Komparatoren auf. Da Sortiernetzwerke mit so
+vielen Komparatoren im Verlauf des Experiments selbst nach über 100~Millionen
+Iterationen nicht noch einmal erzeugt wurden, handelt es sich vermutlich um
+ein Phänomen, das mit der Initialisierung mit dem
+\emph{Odd-Even-Transpositionsort}-Netzwerk zusammenhängt.
+
+%\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}
+
+%\begin{figure}
+% \begin{center}
+% \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-cycles-16.pdf}
+% \end{center}
+% \caption{Zyklen, die beim \textit{Random Walk} des
+% \textsc{SN-Markov}-Algorithmus detektiert wurden. Auf der x-Achse sind die
+% Anzahl der Schritte, die \textsc{SN-Markov} zurückgelegt hat, auf der
+% y-Achse die Längen der gefundenen Zyklen aufgetragen. Das initiale
+% Start-Sortiernetzwerk war $\operatorname{OET}(16)$.}
+% \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.
\item Anzahl der Komparatoren und Anzahl der Schichten der durchlaufenen
Netzwerke. (Abbildung~\ref{fig:markov-comparators-16})
+ \item \textsc{SN-Count-Markov} (ggf)
\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}
-\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}
+\section{Fazit und Ausblick}
+
+\todo{Ausformulieren}
+\begin{itemize}
+\item Mit \textsc{SN-Evolution} und \oem{n} kann man nicht besser werden als
+ \oes{n}.
+\item Mit \textsc{SN-Evolution} und \bm{n} kann man besser werden als \bs{n}.
+\item Vermutlich kann man mit \textsc{SN-Evolution} und \bm{n} so gut werden
+wie \textsc{SN-Evolution-Cut}, wenn er mit \bs{2n} gestartet wird.
+\item Leider sind keine konstruktiven Methoden erkannt worden.
+\end{itemize}
Die Möglichkeiten, die Evolutionäre Algorithmen bei der Optimierung von
Sortiernetzwerken bieten, sind durch die in dieser Arbeit vorgestellten
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}}
+\subsection{Ausblick: Das \textit{Pairwise-Sorting}-Netzwerk und \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
+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
$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}}
+\subsection{Ausblick: 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}
Mergesort}-Netzwerks \bs{18} zu erzeugen, kann folgendes Kommando verwendet
werden:
\begin{verbatim}
-$ sn-bitonicsort 18 | sn-normalize >sn-18
+ $ 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
projects / diplomarbeit.git / blobdiff