\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}
\subsection{Motivation}\label{sect:motivation}
+\todo{Schreibe noch etwas zu …}
\begin{itemize}
\item Sortiernetzwerke sind toll, weil $\ldots$
\item Sortiernetzwerke sind einfach erklärt, aber trotzdem kompliziert.
Abschnitt~\ref{sect:tranformation} beschrieben, ein Algorithmus, der Mutation
einsetzt, wird in Abschnitt~\ref{sect:sn-evolution-cut} vorgestellt.
+
+\begin{figure}
+ \begin{center}
+ \input{images/16-hillis.tex}
+ \end{center}
+ \caption{Das 16-Sortiernetzwerk, das \textit{Hillis} in~\cite{H1992} angibt.
+ Es besteht aus 61~Komparatoren in 11~Schichten.}
+ \label{fig:16-hillis}
+\end{figure}
+Evolutionäre Algorithmen wurden bereits mehrfach eingesetzt, um
+Sortiernetzwerke zu untersuchen. \textit{W.~Daniel Hillis} verwendete
+\emph{Co-Evolution} um neben Komparatornetzwerken auch „schwierige Eingaben“
+zu optimieren~\cite{H1992}. Diese \emph{Parasiten} genannten Eingaben wurden
+daran gemessen, bei wievielen Komparatornetzwerken sie beweisen konnten, dass
+sie keine Sortiernetzwerke sind. So mussten bei neuen Individuen~/
+Komparatornetzwerken nicht alle 0-1-Folgen, sondern nur erfolgreiche
+Parasiten~/ schwierige Eingaben überprüft werden. Auf diese Art und Weise
+gelang es \textit{Hillis} ein 16-Sortiernetzwerk mit 61~Komparatoren
+anzugeben, das in Abbildung~\ref{fig:16-hillis} zu sehen ist.
+
+\begin{figure}
+ \centering
+ \subfigure{\input{images/13-juille-0.tex}}
+ \subfigure{\input{images/13-juille-1.tex}}
+ \caption{13-Sortiernetzwerke, die von \textit{Hugues Juillé} mithilfe des
+ END-Algorithmus gefunden wurden. Sie bestehen jeweils aus 45~Komparatoren in
+ 10~Schichten.}
+ \label{fig:13-juille}
+\end{figure}
+\textit{Hugues Juillé} entwickelte ein Verfahren, das er \emph{Evolving
+Non-Determinism} (END) nannte. Dabei handelt es sich nicht um einen
+\emph{Evolutionären Algorithmus}, wie sie hier vorgestellt wurden, sondern um
+eine verteilte, probabilistische Breitensuche, die an die \emph{Strahlsuche}
+(englisch: \textit{beam search}), ein Verfahren der Künstlichen Intelligenz,
+angelehnt ist. Die aufwendigste Operation bei diesem Ansatz ist die
+Bewertungsfunktion, die abschätzt, wieviele Komparatoren zu einem
+Komparatornetzwerk hinzugefügt werden müssen, um ein Sortiernetzwerk zu
+erhalten. Mit diesem Ansatz gelang es \textit{Juillé} zwei 13-Sortiernetzwerke
+anzugeben, die mit 45~Komparatoren effizienter sind als alle bis dahin
+Bekannten (Abbildung~\ref{fig:13-juille}).
+
\newpage
\section{Bekannte konstruktive Sortiernetzwerke}
\label{sect:konstruktive_netzwerke}
Übersicht über bekannte konstruktive Sortiernetzwerke.
+\todo{Einleitungssatz}
+
\subsection{Das Odd-Even-Transpositionsort-Netzwerk}
\label{sect:odd_even_transpositionsort}
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}
Komparatoren, die in $\frac{1}{2} \log(n) \log(n+1) = \mathcal{O}(\log(n))$
Schichten angeordnet sind.
-%\begin{figure}
-%\begin{center}
-%\includegraphics[viewport=115 491 372 782,width=7.5cm]{images/sn-rekursiver-aufbau.pdf}
-%\end{center}
-%\caption{Rekursiver Aufbau von $S(n)$: Es besteht aus zwei Instanzen von
-%$S(n/2)$ und dem Mischer $M(n)$.}
-%\label{fig:bms_rekursiver_aufbau}
-%\end{figure}
-
\subsection{Das Odd-Even-Mergesort-Netzwerk}
Obwohl der Name ähnlich klingt, haben das \emph{Odd-Even-Mergesort-Netzwerk}
Komprimierung durchgeführt werden.
\subsection{Normalisieren}
+\label{sect:normalisieren}
\begin{figure}
\centering
Sorting Network for 18~Elements“~\cite{BB2009} vorstellen, benötigt aber
6~Komparatoren weniger.
-% 9 9
-% 9 18
-% 9 27
-% 9 36
-% 9 45
-% 8 53
-% 8 61
-% 7 68
-% 7 75
-% 6 81
-% 5 86
-
Das Zusammenfassen von zwei Sortiernetzwerken durch Hintereinanderausführung
ist nicht sinnvoll: Da die Ausgabe des ersten Sortiernetzwerks bereits
sortiert ist, ist das zweite Sortiernetzwerk überflüssig. Eine
Komparatornetzwerks müsste überprüft werden, was nach heutigem Wissensstand
nur mit exponentiellem Aufwand möglich ist.
-%\begin{itemize}
-%\item Mit dem Bitonic-Merge
-%\item Mit dem Odd-Even-Merge
-%\item Nach dem Pairwise sorting-network Schema.
-%\end{itemize}
-
\subsection{Leitungen entfernen}
\label{sect:leitungen_entfernen}
\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}.
\newpage
\section{Der \textsc{SN-Evolution}-Algorithmus}
+\label{sect:sn-evolution}
Der \textsc{SN-Evolution}-Algorithmus ist ein \emph{evolutionärer
Algorithmus}, der die in den vorherigen Abschnitten beschriebenen Mischer
für jedes Individuum in Population
{
reziproke Güte := 1.0 / Guete(Individuum)
- Wahrscheinlichkeit P := reziproke Güte / (reziproke Güte + Gütesumme)
+ Wahrscheinlichkeit P := reziproke Güte / (Gütesumme + reziproke Güte)
Gütesumme := Gütesumme + reziproke Güte
mit Wahrscheinlichkeit P
$\operatorname{OES}(n)$ in mindestens einem Merkmal übertrifft, konnte jedoch
nicht beobachtet werden.
-\begin{itemize}
-\item Güte von Sortiernetzwerken (Anzahl der Komparatoren, Anzahl der Schichten, kombiniert)
-\item Wie gut die Netzwerke werden, hängt stark vom verwendeten \emph{Mischer} ab.
-\item Ggf. Abschnitt „Shmoo-Äquivalenz“ kürzen und hier einbauen.
-\item Möglicherweise: Verwende den rekursiven Aufbau des \emph{Pairwise-Sorting}-Netzwerks um Sortiernetzwerke zu mergen.
-\end{itemize}
+\todo{Ggf. Abschnitt „Shmoo-Äquivalenz“ kürzen und hier einbauen.}
%\begin{figure}
%\begin{center}
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
$\operatorname{OES}(32)$ sehr schnell ein gutes 16-Schnittmuster findet.
Eines der eher zufälligen Schnittmuster ist $\operatorname{MIN}(1, 6, 11, 14,
-17, 23, 26, 29)$, $\operatorname{MAX}(2, 7, 8, 13, 18, 21, 27, 31)$. Das
+17, 23, 26, 29)$, $\operatorname{MAX}(2, 7, 8,$ $13, 18, 21, 27, 31)$. Das
Schnittmuster ist in Abbildung~\ref{fig:16-ec-from-oes32-cut} veranschaulicht,
das resultierende Netzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32} zu sehen.
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 20000, 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
gib Netzwerk zurück
\end{verbatim}
+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}
\begin{center}
\includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-cycles-16.pdf}
\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.
\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}
+ \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-comparators-18-pct.pdf}
+ \includegraphics[viewport=0 0 425 262,width=15cm]{images/comparison-comparators-16.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}
+ \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}) gesaßen.}
+ \label{fig:comparison-comparators}
\end{figure}
-\newpage
-\section{Empirische Beobachtungen}
-
-\begin{itemize}
-\item So schnell konvergiert der Algorithmus.
-\item $\ldots$
-\end{itemize}
+%\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}
-Das würde mir noch einfallen$\ldots$
-
-- SN-Evolution mit Pairwise als „Mischer“.
-- Co-Evolution von Netzwerken und Schnittmustern.
+Die Möglichkeiten, die Evolutionäre Algorithmen bei der Optimierung von
+Sortiernetzwerken bieten, sind durch die in dieser Arbeit vorgestellten
+Herangehensweisen bei weitem nicht erschöpft.
+
+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}}
+
+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
+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
+$\ps{\frac{n}{2}}$ und zusätzlichen Komparatoren besteht, die die Eingabe für
+die kleineren Sortiernetzwerke vorbereiten und anschließend für eine sortierte
+Ausgaben sorgen. Anstelle von $\ps{\frac{n}{2}}$ kann man natürlich beliebige
+Sortiernetzwerke mit $\frac{n}{2}$~Leitungen verwenden.
+
+Dies ließe sich für \textsc{SN-Evolution} nutzen, um zwei Individuen zu
+rekombinieren. Da es für das \emph{Pairwise-Sorting}-Netzwerk sehr viele
+\emph{unterscheidliche} Schnittmuster gibt
+(Abbschnitt~\ref{sect:anzahl_schnittmuster}), ist es möglich, dass die
+Verwendung dieser Rekombinationsmethode neue Ergebnisse ermöglicht. Leider
+wird die Aussicht auf Erfolg durch die Tatsache geschmälert, dass keine
+$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}}
+
+Ä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}
+und \textsc{SN-Evolution-Cut} versuchen zu kombinieren. Nach dem Zusammenfügen
+von zwei $n$-Sortiernetzwerken könnte der Algorithmus
+\textsc{SN-Evolution-Cut} beispielsweise einen möglichst guten Schnitt für
+\emph{dieses} Netzwerk ermitteln. Da sich die Lösungen, die Evolutionäre
+Algorithmen in ihre Population aufnehmen, in den ersten Schritten rasch
+verbessern, könnten selbst weniger Iterationen von \textsc{SN-Evolution-Cut}
+die Zwischenlösungen von \textsc{SN-Evolution} deutlich verbessern.
+
+Alternativ könnte man -- analog zur Herangehensweise von \textit{Hillis} --
+eine zweite Population von Schnittmustern evolvieren, die für die
+Sortiernetzwerke in der Population von \textsc{SN-Evolution} besonders gut
+funktionieren. In jeder Iteration wendet man alle oder eine zufällige Menge
+Schnittmuster auf das zusammengeführte Netzwerk an und gibt dem besten
+Ergebnis den Zuschlag. Anschließend erfährt das entsprechende Schnittmuster
+eine Aufwertung, so dass es wahrscheinlicher wird, dass \emph{dieses}
+Schnittmuster zur nächten Generation beiträgt. Im Gegensatz zum Ansatz der
+parasitären Eingaben entsteht eine \emph{Synergie} zweier Populationen, die
+das Gesamtergebnis oder zumindest die Konvergenzgeschwindigkeit verbessern
+könnte.
\newpage
\section{Implementierung}
projects / diplomarbeit.git / blobdiff