\usepackage{listings}
\usepackage{graphicx}
\usepackage{url}
+\usepackage[table]{xcolor}
%\usepackage{longtable}
\usepackage{subfigure}
\usepackage{icomma}
\newcommand{\bm}[1]{\ensuremath{\operatorname{BM}\left(#1\right)}}
\newcommand{\oet}[1]{\ensuremath{\operatorname{OET}\left(#1\right)}}
+\newcommand{\gcell}{\cellcolor{green!10}}
+\newcommand{\Gcell}{\cellcolor{green!10!white!95!black}}
+
\newtheorem{definition}{Definition}
\newtheorem{satz}{Satz}
vernachlässigbar klein ist.
Bedingt durch die sehr große Anzahl möglicher Schnittmuster ist dieses
-Experiment für größere Sortiernetzwerke leider nicht sinnvoll durchführbar.
-Die Hashtabelle würde mehr Arbeitsspeicher benötigen als in derzeitigen
-Rechnern vorhanden ist, bevor ein entsprechender Graph den linearen Bereich
-für „kleine“ x-Werte verlässt.
+Experiment für größere Sortiernetzwerke nicht sinnvoll durchführbar. Die
+Hashtabelle würde mehr Arbeitsspeicher benötigen als in derzeitigen Rechnern
+vorhanden ist, bevor ein entsprechender Graph den linearen Bereich für
+„kleine“ x-Werte verlässt.
Um die Anzahl der unterschiedlichen Schnittmuster trotzdem abschätzen zu
können, kann man sich einer stochastischen Methode bedienen, der sogenannten
Diese Parameter haben einen großen Einfluss auf die Geschwindigkeit, mit der
der \textsc{SN-Evolution}-Algorithmus konvergiert und ob er tatsächlich gute
-Lösungen findet oder sich in \emph{lokalen} Optima verrennt. Leider gibt es
-kein Patentrezept für die Wahl der Parameter, so dass für verschiedene
+Lösungen findet oder sich in \emph{lokalen} Optima "`verfängt"'. Leider gibt
+es kein Patentrezept für die Wahl der Parameter, so dass für verschiedene
Leitungszahlen und Mischer-Typen experimentiert werden muss.
Als guter Standardansatz für \textsc{SN-Evolution} haben sich die folgenden
\label{sect:sn-evolution: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
-\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 werden zufällig $n$~Leitungen mit einem $n$-Schnittmuster wie in
-Abschnitt~\ref{sect:leitungen_entfernen} beschrieben entfernt.
+einer neuen Lösung kombiniert. Geeignete Mischer, um die beiden Netzwerke zu
+einem Netzwerk mit $2n$~Leitungen zusammenzufügen, sind zum Beispiel der {\em
+bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) und der
+\emph{Odd-Even}-Mischer (Abschnitt~\ref{sect:der_odd_even_mischer}),
+Anschließend werden $n$~Leitungen mit einem zufälligen $n$-Schnittmuster wie
+in Abschnitt~\ref{sect:leitungen_entfernen} beschrieben entfernt.
Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft
erhält. Entsprechend muss nicht aufwendig überprüft werden, ob das
\label{fig:16-e1-bitonic-1296542566}
\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 \emph{bitone Mergesort}-Netzwerk: \bs{16} benötigt 80~Komparatoren,
-das Sortiernetzwerk in Abbildung~\ref{fig:16-e1-bitonic-1296542566} benötigt
-lediglich~67. Die Effizienz des \emph{Odd-Even-Mergesort}-Netzwerks wurde
-leider mit keiner Leitungszahl erreicht.
+Wenn \textsc{SN-Evolution} mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk
+als Eingabe gestartet wird und in der Rekombinationsphase den \emph{bitonen
+Mischer} verwendet, gibt der Algorithmus Sortiernetzwerke wie das in
+Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte zurück.
+
+Viele der Sortiernetzwerke, die von \textsc{SN-Evolution} in dieser
+Konfiguration gefunden werden, sind effizienter als das \emph{bitone
+Mergesort}-Netzwerk \bs{n}, das ebenfalls auf dem \emph{bitonen
+Merge}-Netzwerk \bm{n} beruht. Das in
+Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte 16-Sortiernetzwerk
+benötigt 67~Komparatoren, 13~Komparatoren weniger als \bs{n}.
+
+Wenn die Gütefunktion so gewählt ist, dass sie schnelle Sortiernetzwerke
+bevorzugt, können Netzwerke zurückgegeben werden, die schneller als \bs{n}
+sind. Viele der schnellen Sortiernetzwerke sind außerdem effizienter als
+\bs{n}. Das Sortiernetzwerk mit $n = 23$ Leitungen benötigt mit
+134~Komparatoren jedoch einen Komparator mehr als \bs{23}. Die Daten von
+schnellen Sortiernetzwerken, die \textsc{SN-Evolution} mit dem \emph{bitonen
+Merge}-Netzwerk erzeugt hat, sind in Tabelle~\ref{tbl:sn-ev-bm-fast}
+aufgelistet.
+
+\begin{table}\label{tbl:sn-ev-bm-fast}
+\begin{center}
+\rowcolors{4}{black!5}{}
+\begin{tabular}{|r|r|r|r|r|}
+\hline
+Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}} & \multicolumn{2}{|l|}{\bs{n}} \\
+\cline{2-5}
+ ($n$) & Komp. & Schichten & Komp. & Schichten \\
+\hline
+ 8 & \gcell 20 & 6 & 24 & 6 \\
+ 9 & \Gcell 26 & 8 & 28 & 8 \\
+ 10 & \gcell 31 & \gcell 8 & 33 & 9 \\
+ 11 & \Gcell 37 & \Gcell 9 & 39 & 10 \\
+ 12 & \gcell 42 & \gcell 9 & 46 & 10 \\
+ 13 & \Gcell 48 & 10 & 53 & 10 \\
+ 14 & \gcell 54 & 10 & 61 & 10 \\
+ 15 & \Gcell 61 & 10 & 70 & 10 \\
+ 16 & \gcell 67 & 10 & 80 & 10 \\
+ 17 & \Gcell 76 & 12 & 85 & 12 \\
+ 18 & \gcell 87 & \gcell 12 & 91 & 13 \\
+ 19 & \Gcell 93 & \Gcell 13 & 98 & 14 \\
+ 20 & \gcell 104 & \gcell 13 & 106 & 14 \\
+ 21 & \Gcell 109 & \Gcell 14 & 114 & 15 \\
+ 22 & \gcell 118 & \gcell 14 & 123 & 15 \\
+ 23 & 134 & \Gcell 14 & \Gcell 133 & 15 \\
+ 24 & \gcell 133 & 15 & 144 & 15 \\
+\hline
+\end{tabular}
+\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus
+ unter Verwendung des \emph{bitonen Merge}-Netzwerks \bm{n}. Der Algorithmus
+ wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n} gestartet
+ und nach 2.500.000 Iterationen beendet. Die Bewertungsfunktion nutzte die
+ Konstanten $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = 1$,
+ $w_{\mathrm{Schichten}} = n$.}
+\end{center}
+\end{table}
\subsection[Odd-Even-Mischer]{Versuche mit dem Odd-Even-Mischer}
\label{fig:16-e1-oddeven-1296543330}
\end{figure}
-Leider lies sich das Ergebnis des bitonen Mischers -- die von
-\textsc{SN-Evolution} ausgegebenen Netzwerke waren effizienter als das
-rekursiv aus dem verwendeten Mischer aufgebaute Sortiernetzwerk -- mit dem
-\emph{Odd-Even-Merge}-Netzwerk 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 Geschwindigkeit und Effizienz, ein Beispiel hierfür ist in
-Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen. Sortiernetzwerkde, die
-effizienter als $\operatorname{OES}(n)$ sind, konnten leider nicht beobachtet
-werden. Wenn $n$ keine Zweietpotenz ist, kann \textsc{SN-Evolution} unter
-Umständen Sortiernetzwerke ausgeben, die schneller als \oes{n} sind.
+Im vorherigen Abschnitt wurde gezeigt, dass der
+\textsc{SN-Evolution}-Algorithmus unter Verwendung des \emph{bitonen Mischers}
+Sortiernetzwerke erzeugen kann, die effizienter als das rekursiv aus dem
+\emph{bitonen Mischer} aufgebaute \emph{bitone Mergesort}-Netzwerk sind.
+Dieses Ergebnis lies sich mit dem \emph{Odd-Even-Merge}-Netzwerk nicht
+erzielen. Die Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung des
+\emph{Odd-Even-Merge}-Netzwerks findet, erreichen das
+\emph{Odd-Even-Mergesort}-Netzwerk bezüglich Effizienz, übertreffen es aber
+nicht. Ein Beispiel für ein entsprechendes Sortiernetzwerk ist in
+Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen.
+
+Mit einer Gütefunktion, die schnelle Sortiernetzwerke bevorzugt, ist es auch
+mit dem \emph{Odd-Even}-Mischer möglich, dass \textsc{SN-Evolution}
+Sortiernetzwerke zurück gibt, die schneller als \oes{n} sind. Dies geschieht
+beispielsweise bei $n = 11$ und $n = 12$: für diese Leitungszahlen gibt
+\textsc{SN-Evolution} Sortiernetzwerke aus, die nur 9~Schicten benötigen.
+\oes{11} und \oes{12} benötigen jeweils 10~Schichten. Eine Auflistung der
+Ergebnisse von \textsc{SN-Evolution} mit dem \emph{Odd-Even}-Mischer befindet
+sich in Tabelle~\ref{tbl:sn-ev-oem-fast}.
%\begin{figure}
%\begin{center}
%\label{fig:10-e2-1239014566}
%\end{figure}
+\begin{table}\label{tbl:sn-ev-oem-fast}
+\begin{center}
+\rowcolors{4}{black!5}{}
+\begin{tabular}{|r|r|r|r|r|}
+\hline
+Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}} & \multicolumn{2}{|l|}{\oes{n}} \\
+\cline{2-5}
+ & Komp. & Schichten & Komp. & Schichten \\
+\hline
+ 8 & 19 & 6 & 19 & 6 \\
+ 9 & 26 & 8 & 26 & 8 \\
+ 10 & 31 & 9 & 31 & 9 \\
+ 11 & 38 & \Gcell 9 & \Gcell 37 & 10 \\
+ 12 & 43 & \gcell 9 & \gcell 41 & 10 \\
+ 13 & 48 & 10 & 48 & 10 \\
+ 14 & 53 & 10 & 53 & 10 \\
+ 15 & 59 & 10 & 59 & 10 \\
+ 16 & 63 & 10 & 63 & 10 \\
+ 17 & 74 & 12 & 74 & 12 \\
+ 18 & 82 & 13 & 82 & 13 \\
+ 19 & 93 & \Gcell 13 & \Gcell 91 & 14 \\
+ 20 & 97 & 14 & 97 & 14 \\
+ 21 & 108 & \Gcell 14 & \Gcell 107 & 15 \\
+ 22 & 117 & \gcell 14 & \gcell 114 & 15 \\
+ 23 & 129 & \Gcell 14 & \Gcell 122 & 15 \\
+ 24 & 128 & 15 & \gcell 127 & 15 \\
+\hline
+\end{tabular}
+\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus
+ unter Verwendung des \emph{Odd-Even-Merge}-Netzwerks \oem{n}. Der
+ Algorithmus wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n}
+ gestartet und nach 2.500.000 Iterationen beendet. Die Bewertungsfunktion
+ nutzte die Konstanten $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} =
+ 1$, $w_{\mathrm{Schichten}} = n$.}
+\end{center}
+\end{table}
+
+\subsection{Zufälliger Mischer}
+
+Die Ergebnisse der beiden vorhergehenden Abschnitte zeigen, dass für einige
+Leitungszahlen der \emph{bitone Mischer} und für andere Leitungszahlen der
+\emph{Odd-Even}-Mischer bessere Ergebnisse liefert. Beispielsweise hat das
+Netzwerk für $n = 18$ bei Verwendung des \emph{bitone Mischers} nur
+12~Schichten, bei Verwendung des \emph{Odd-Even}-Mischers hingegen nur
+82~Komparatoren. Daher liegt die Idee nahe, beide Mischer-Netzwerke zu nutzen,
+um das beste Ergebnis beider Konstruktionen zu erreichen.
+\textsc{SN-Evolution} kann zu diesem Zweck beim Zusammenfügen zweier
+Individuen zufällig zwischen dem \emph{bitonen Mischer} und dem
+\emph{Odd-Even}-Mischer wählen. \todo{Daten noch in eine Tabelle einfügen.}
+
%\input{shmoo-aequivalenz.tex}
\newpage
Sortiernetzwerken mit 68~Komparatoren in 10~Schichten resultieren, hatten 73
ein Verhältnis von $5/11$, 13 hatten ein Verhältnis von $4/12$ und 14 hatten
ein Verhältnis von $3/13$ Minimum- beziehungsweise Maximumschnitten. Da sich
-die Schnittmuster aufgrund der Symmetrie des bitonen Mergesort-Netzwerks
-leicht invertieren lassen, werden der Fall, dass es mehr Minimumschnitte, und
-der Fall, dass es mehr Maximumschnitte gibt, nicht unterschieden.
+die Schnittmuster aufgrund der Symmetrie des \emph{bitonen
+Mergesort}-Netzwerks leicht invertieren lassen, ist eine Fallunterscheidung --
+mehr Minimum- oder mehr Maximumschnitte -- nicht notwendig.
\begin{figure}
\centering
$\operatorname{PS}(n)$, das \textit{Ian Parberry} in seiner Arbeit „The
Pairwise Sorting Network“ \cite{P1992} definiert. Startet man
\textsc{SN-Evolution-Cut} mit $\operatorname{PS}(32)$ und der Vorgabe,
-16~Leitungen zu entfernen, erhält man ein Sortiernetzwerk, dass die gleiche
+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 Sortiernetzwerke ist in
Abbildung~\ref{fig:16-ec-from-ps32} dargestellt.
\end{figure}
Für das \emph{Pairwise-Sorting-Netzwerk} ist es vergleichsweise einfach
-regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk einen kleineres
+regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk ein kleineres
schnelles und effizientes Sortiernetzwerk erzeugen. Beispielsweise führt das
einfache Schnittmuster
\begin{displaymath}
16)$, $\operatorname{MAX}(1, 3, 10, 17, 20, 23)$ ausgegeben. Das Ergebnis
dieses Schnittmusters ist in Abbildung~\ref{fig:12-ec-from-oes24-fast} zu
sehen. Das Sortiernetzwerk besteht aus 43~Komparatoren, die in 9~Schichten
-angeordnet sind. Das heißt, dass das resultierende Netzwerk zwar nicht so
-effizient wie \oes{12}, dafür aber schneller als \oes{12} und \bs{12} ist.
+angeordnet sind. Das resultierende Netzwerk zwar nicht so effizient wie
+\oes{12}, dafür aber schneller als \oes{12} und \bs{12}.
\begin{figure}
\centering
projects / diplomarbeit.git / blobdiff