\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}
\item Möglichst wenige Schichten („schnell“)
\end{itemize}
+\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}}
+ \caption{Das effizienteste und das schnellste Sortiernetzwerk für
+ 16~Leitungen, die derzeit bekannt sind.}
+ \label{fig:16-best-known}
+\end{figure}
Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das
effizienteste bekannte Sortiernetzwerk für 16~Eingänge besteht aus
-60~Komparatoren in 10~Schichten. Das schnellste bekannte 16-Sortiernetzwerk
-besteht aus 61~Komparatoren in nur 9~Schichten.
+60~Komparatoren in 10~Schichten. Es ist in Abbildung~\ref{fig:16-green}
+dargestellt. Das schnellste bekannte 16-Sortiernetzwerk besteht aus
+61~Komparatoren in nur 9~Schichten.
Eine Gütefunktion, die die beiden Ziele "`effizient"' und "`schnell"'
berücksichtigen kann, hat die folgende allgemeine Form:
\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}
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
-wiederholen. Die Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung
-des \emph{Odd-Even}-Mischers findet, erreichen das
+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. Wenn $n$ keine
-Zweierpotenz ist, kann \textsc{SN-Evolution} unter Umständen Sortiernetzwerke
-ausgeben, die schneller als \oes{n} sind.
+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
projects / diplomarbeit.git / blobdiff