SN-Evolution: Versuche mit dem Odd-Even-Mischer überarbeitet.

[diplomarbeit.git] / diplomarbeit.tex

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index 6cd4078..98dd41e 100644 (file)
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -9,6 +9,7 @@
 \usepackage{listings}
 \usepackage{graphicx}
 \usepackage{url}
 \usepackage{listings}
 \usepackage{graphicx}
 \usepackage{url}

+\usepackage[table]{xcolor}

 %\usepackage{longtable}
 \usepackage{subfigure}
 \usepackage{icomma}
 %\usepackage{longtable}
 \usepackage{subfigure}
 \usepackage{icomma}


@@ -43,6 +44,9 @@
 \newcommand{\bm}[1]{\ensuremath{\operatorname{BM}\left(#1\right)}}
 \newcommand{\oet}[1]{\ensuremath{\operatorname{OET}\left(#1\right)}}
 
 \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}
 
 \newtheorem{definition}{Definition}
 \newtheorem{satz}{Satz}
 


@@ -1158,10 +1162,10 @@ die Anzahl dieser zusätzlichen, unterschiedlichen Schnittmuster
 vernachlässigbar klein ist.
 
 Bedingt durch die sehr große Anzahl möglicher Schnittmuster ist dieses
 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
 
 Um die Anzahl der unterschiedlichen Schnittmuster trotzdem abschätzen zu
 können, kann man sich einer stochastischen Methode bedienen, der sogenannten


@@ -1283,8 +1287,8 @@ Exploitation}, das Finden (lokaler) Optima, bevorzugt.
 
 Diese Parameter haben einen großen Einfluss auf die Geschwindigkeit, mit der
 der \textsc{SN-Evolution}-Algorithmus konvergiert und ob er tatsächlich gute
 
 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
 Leitungszahlen und Mischer-Typen experimentiert werden muss.
 
 Als guter Standardansatz für \textsc{SN-Evolution} haben sich die folgenden


@@ -1330,12 +1334,12 @@ Pseudocode wie folgt beschreiben:
 \label{sect:sn-evolution:rekombination}
 
 Bei der Rekombination werden zwei Individuen --~hier Sortiernetzwerke~-- zu
 \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
 
 Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft
 erhält. Entsprechend muss nicht aufwendig überprüft werden, ob das


@@ -1380,15 +1384,63 @@ wurde beim \textsc{SN-Evolution}-Algorithmus auf eine Mutation verzichtet.
   \label{fig:16-e1-bitonic-1296542566}
 \end{figure}
 
   \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}
 
 
 \subsection[Odd-Even-Mischer]{Versuche mit dem Odd-Even-Mischer}
 


@@ -1403,17 +1455,25 @@ leider mit keiner Leitungszahl erreicht.
   \label{fig:16-e1-oddeven-1296543330}
 \end{figure}
 
   \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}
 
 %\begin{figure}
 %\begin{center}


@@ -1447,6 +1507,43 @@ Umständen Sortiernetzwerke ausgeben, die schneller als \oes{n} sind.
 %\label{fig:10-e2-1239014566}
 %\end{figure}
 
 %\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}
+

 %\input{shmoo-aequivalenz.tex}
 
 \newpage
 %\input{shmoo-aequivalenz.tex}
 
 \newpage


@@ -1573,9 +1670,9 @@ Von Hundert 16-Schnittmustern für $\operatorname{BS}(32)$, die in
 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
 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
 
 \begin{figure}
   \centering


@@ -1642,7 +1739,7 @@ Anders verhält sich das \emph{Pairwise-Sorting-Netzwerk}
 $\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,
 $\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.
 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.


@@ -1677,7 +1774,7 @@ Schichten~1 und~2 sowie 4~und~5 sind vertauscht.
 \end{figure}
 
 Für das \emph{Pairwise-Sorting-Netzwerk} ist es vergleichsweise einfach
 \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}
 schnelles und effizientes Sortiernetzwerk erzeugen. Beispielsweise führt das
 einfache Schnittmuster
 \begin{displaymath}


@@ -1805,8 +1902,8 @@ werden stattdessen Schnittmuster wie $\operatorname{MIN}(6, 7, 11, 12, 15,
 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
 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
 
 \begin{figure}
   \centering