\begin{center}
\input{images/oe-transposition-8.tex}
\end{center}
- \caption{Das \emph{Odd-Even-Transpositionsort}-Netzwerk mit acht Eingängen.}
+ \caption{Das \emph{Odd-Even-Transpositionsort}-Netzwerk mit 8~Eingängen.}
\label{fig:odd-even-transposition-08}
\end{figure}
\begin{center}
\input{images/batcher-8.tex}
\end{center}
- \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).}
+ \caption{\bs{8}, Batchers \emph{bitones Mergesort}-Netzwerk für 8~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}
\begin{center}
\input{images/oe-merge.tex}
\end{center}
- \caption{Schematischer Aufbau des \emph{Odd-Even-Merge}-Netzwerks. Im
- Vergleich zum bitonen Mischer für acht Leitungen kommt dieses Schema mit
- einem Komparator weniger aus. Der Effekt wird durch den rekursiven Aufbau
- verstärkt.}
+ \caption{Schematischer Aufbau des \emph{Odd-Even-Merge}-Netzwerks. Die
+ beiden Dreiecke symbolisieren die beiden sortierten Folgen $U$ und $V$,
+ die Blöcke darunter die rekursiven Mischer mit etwa der Hälfte der
+ Leitungen. Im Vergleich zum \emph{bitonen Mischer} für 8~Leitungen kommt
+ dieses Schema mit einem Komparator weniger aus. Der Effekt wird durch den
+ rekursiven Aufbau verstärkt.}
\label{fig:oe-merge}
\end{figure}
\begin{center}
\input{images/oe-mergesort-8.tex}
\end{center}
- \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge. Markiert
+ \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für 8~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
Leitungen (blau) und die im ersten Rekursionsschritt hinzugefügten
In Abbildung~\ref{fig:odd-even-mergesort-08} ist das \oes{8}-Sortiernetzwerk
zu sehen. Rot markiert sind die beiden rekursiven Instanzen
$\operatorname{OES}(4)$. Die anderen Blöcke stellen den
-\emph{Odd-Even}-Mischer für acht Leitungen dar: die beiden blauen Blöcke sind
+\emph{Odd-Even}-Mischer für 8~Leitungen dar: die beiden blauen Blöcke sind
die rekursiven Instanzen von $\operatorname{OEM}(4)$, der grüne Block markiert
die Komparatoren, die im ersten Rekursionsschritt hinzugefügt werden.
zusammenfügen.
Beispielsweise kann die Ausgabe von zwei \emph{bitonen Mergesort-Netzwerken}
-$\operatorname{BS}(8)$ mit je acht Leitungen mit dem
+$\operatorname{BS}(8)$ mit je 8~Leitungen mit dem
\emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM(8,8)}$ zu einer sortierten
Gesamtfolge zusammengefügt werden. Das resultierende Sortiernetzwerk besitzt
73~Komparatoren (zum Vergleich: $\operatorname{BS}(16)$ benötigt
\subsection{Selektion}
-Die \emph{Selektion} sorgt dafür, dass bessere Individuen eine größere
-Wahrscheinlichkeit haben zur nächsten Generation beizutragen. Diese
-Ungleichbehandlung von Individuen verschiedener Güte ist der Grund für das
-Streben des Algorithmus nach besseren Lösungen.
+Als \emph{Selektion} wird der Vorgang bezeichnet, der zwei Individuen zufällig
+aus der Population auswählt. Sie werden im folgenden Schritt miteinander
+rekombiniert. Die Auswahl der Individuen erfolgt zufällig, aber nicht
+gleichverteilt. So sorgt die \emph{Selektion} dafür, dass bessere Individuen
+eine größere Wahrscheinlichkeit haben zur nächsten Generation beizutragen.
+Diese Ungleichbehandlung von Individuen verschiedener Güte ist der Grund für
+das Streben des Algorithmus nach besseren Lösungen.
Obwohl dieser Vorteil für gute Individuen intuitiv als sehr gering erscheint,
-ist es sehr häufig, dass die \emph{Exploitation} überhand gewinnt und der
-Algorithmus vorschnell in Richtung eines lokalen Optimums optimiert.
+passiert es häufig, dass die Ausnutzung \emph{(Exploitation)} überhand gewinnt
+und der Algorithmus vorschnell in Richtung eines lokalen Optimums optimiert.
-Die in \textsc{SN-Evolution} implementierte Selektion lässt sich mithilfe von
-Pseudocode wie folgt beschreiben:
+Die in \textsc{SN-Evolution} implementierte Selektion eines Individuums lässt
+sich mit Pseudocode wie folgt beschreiben:
\begin{verbatim}
Gütesumme := 0
Auswahl := (leer)
gib Auswahl zurück
\end{verbatim}
+Diese Auswahl wird zweimal ausgeführt, um zwei Individuen für die
+Rekombination zu erhalten. Das heißt, dass die Individuen bei
+\textsc{SN-Evolution} stochastisch unabhängig voneinander ausgewählt werden.
+
\subsection{Rekombination}
\label{sect:sn-evolution:rekombination}
\subsection[Bitones Mergesort-Netzwerk]{Versuche mit dem bitonen Mergesort-Netzwerk}
\label{sect:sn-evolution-cut:bs}
+\begin{figure}
+ \begin{center}
+ \input{images/16-ec-from-bs22.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 16~Leitungen und 67~Komparatoren in
+ 10~Schichten. Das Netzwerk wurde von dem Algorithmus
+ \textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort}-Netzwerk
+ $\operatorname{BS}(22)$ durch das 6-Schnittmuster $\operatorname{MIN}(4,
+ 10, 17)$, $\operatorname{MAX}(7, 15, 20)$ erzeugt.}
+ \label{fig:16-ec-from-bs22}
+\end{figure}
+
\textit{Moritz Mühlenthaler} und \textit{Rolf Wanka} zeigen in~\cite{MW2010},
wie man einen bitonen Mischer, der nach Batchers Methode konstruiert wurde,
durch systematisches Entfernen von Leitungen in einen ebenfalls bitonen
haben, ist jedoch kein Eigenschaft des Algorithmus, sondern hängt insbesondere
von der Eingabe ab. Wird \textsc{SN-Evolution-Cut} beispielsweise mit dem
\emph{Odd-Even-Transpositionsort-Netzwerk} $\operatorname{OET}(n)$ und
-$m$~Schnitten gestartet, so ist das beste Ergebnis immer das
-$\operatorname{OET}(n-m)$-Netzwerk.
+$k$~Schnitten gestartet, so ist das beste Ergebnis immer das
+$\operatorname{OET}(n-k)$-Netzwerk.
+
+\begin{table}
+ \begin{center}
+ \rowcolors{2}{black!5}{}
+ \begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
+ \hline
+ & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
+ \hline
+ 9 & 21 & & & & & & & & & & & & & & & \\
+ 10 & 20 & 27 & & & & & & & & & & & & & & \\
+ 11 & 20 & 27 & 32 & & & & & & & & & & & & & \\
+ 12 & 20 & 26 & 32 & 39 & & & & & & & & & & & & \\
+ 13 & 20 & 26 & 32 & 39 & 45 & & & & & & & & & & & \\
+ 14 & 20 & 26 & 32 & 39 & 45 & 53 & & & & & & & & & & \\
+ 15 & 20 & 26 & 32 & 39 & 45 & 53 & 61 & & & & & & & & & \\
+ 16 & 20 & 26 & 32 & 39 & 45 & 53 & 61 & 70 & & & & & & & & \\
+ 17 & 20 & 26 & 32 & 37 & 43 & 50 & 57 & 65 & 74 & & & & & & & \\
+ 18 & 20 & 26 & 31 & 37 & 43 & 49 & 56 & 63 & 71 & 82 & & & & & & \\
+ 19 & 20 & 26 & 31 & 37 & 43 & 48 & 55 & 62 & 70 & 79 & 88 & & & & & \\
+ 20 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 86 & 95 & & & & \\
+ 21 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 85 & 94 & 103 & & & \\
+ 22 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 67 & 77 & 84 & 93 & 102 & 112 & & \\
+ 23 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 & \\
+ 24 & 20 & 26 & 32 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 & 133 \\
+ \hline
+\bs{n} & 24 & 28 & 33 & 39 & 46 & 53 & 61 & 70 & 80 & 85 & 91 & 98 & 106 & 114 & 123 & 133 \\
+ \hline
+ \end{tabular}
+ \end{center}
+ \caption{Anzahl der Komparatoren der Ergebnisse des
+ \textsc{SN-Evolution-Cut} mit verschiedenen Größen des \emph{bitonen
+ Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. Jede Zeile gibt
+ die Ergebnisse für ein Eingabenetzwerk \bs{n} an, die Spalten
+ repräsentieren die Anzahl der Leitungen des Ausgabenetzwerks.}
+ \label{tbl:ec-bs-fast}
+\end{table}
\subsection[Odd-Even-Mergesort-Netzwerk]{Versuche mit dem Odd-Even-Mergesort-Netzwerk}
\label{sect:sn-evolution-cut:oes}
ist bei dem Netzwerk in Abbildung~\ref{fig:32-ec-from-bs64} nicht ersichtlich,
wie und warum es jede beliebige Eingabe sortiert.
+\begin{table}
+ \begin{center}
+ \rowcolors{2}{black!5}{}
+\begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
+\hline
+ & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
+\hline
+ 9 & 20 & & & & & & & & & & & & & & & \\
+ 10 & 20 & 27 & & & & & & & & & & & & & & \\
+ 11 & 20 & 28 & 32 & & & & & & & & & & & & & \\
+ 12 & 20 & 28 & 32 & 38 & & & & & & & & & & & & \\
+ 13 & 19 & 27 & 31 & 37 & 41 & & & & & & & & & & & \\
+ 14 & 19 & 27 & 31 & 37 & 41 & 48 & & & & & & & & & & \\
+ 15 & 19 & 27 & 31 & 37 & 41 & 48 & 53 & & & & & & & & & \\
+ 16 & 19 & 27 & 31 & 37 & 41 & 48 & 53 & 59 & & & & & & & & \\
+ 17 & 21 & 29 & 32 & 39 & 43 & 51 & 57 & 64 & 68 & & & & & & & \\
+ 18 & 22 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & & & & & & \\
+ 19 & 23 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & 88 & & & & & \\
+ 20 & 23 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & 88 & 97 & & & & \\
+ 21 & 20 & 30 & 34 & 38 & 44 & 51 & 57 & 64 & 74 & 82 & 87 & 96 & 102 & & & \\
+ 22 & 20 & 30 & 34 & 38 & 46 & 51 & 57 & 64 & 72 & 82 & 89 & 96 & 102 & 112 & & \\
+ 23 & 20 & 27 & 34 & 38 & 42 & 51 & 57 & 66 & 72 & 83 & 89 & 97 & 102 & 112 & 119 & \\
+ 24 & 20 & 27 & 34 & 38 & 42 & 51 & 57 & 64 & 72 & 82 & 89 & 96 & 102 & 112 & 119 & 127 \\
+\hline
+\ps{m}&19 & 27 & 32 & 38 & 42 & 48 & 53 & 59 & 63 & 79 & 88 & 97 & 103 & 112 & 119 & 127 \\
+\hline
+\end{tabular}
+ \end{center}
+ \caption{Anzahl der Komparatoren der Ergebnisse von
+ \textsc{SN-Evolution-Cut} mit verschiedenen Größen des
+ \emph{Pairwise-Sorting}-Netzwerks und unterschiedlichen Werten für~$k$.
+ Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \ps{n} an, jede
+ Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
+ Ausgabenetzwerks.}
+ \label{tbl:ec-bs-fast}
+\end{table}
+
Das \emph{Pairwise-Sorting-Netzwerk} $\operatorname{PS}(n)$, das \textit{Ian
Parberry} in seiner Arbeit „The Pairwise Sorting Network“ \cite{P1992}
definiert, verhält sich anders. Startet man \textsc{SN-Evolution-Cut} mit
projects / diplomarbeit.git / blobdiff