Viele {\em kombinatorische Optimierungsprobleme} sind schwer zu lösen -- die
entsprechenden Entscheidungsprobleme liegen oft in der Komplexitätsklasse
-$NP$, sind also mit bekannten Verfahren nicht effizient exakt lösbar. Sollte
-sich herausstellen, dass diese Probleme nicht in der Komplexitätsklasse $P$
-liegen, wäre eine Konsequenz, dass es effiziente exakte Algorithmen für diese
-Probleme nicht geben kann. Falls sich hingegen herausstellt, dass diese
-Probleme in der Komplexitätsklasse~$P$ liegen, wird es mit großer
-Wahrscheinlichkeit noch einige Zeit dauern bis auch Algorithmen mit
-praktikablen Zeitkonstanten gefunden werden.
+\textit{NP}, das heißt das keine Verfahren bekannt sind, die das Problem
+effizient exakt lösbar. Sollte sich herausstellen, dass diese Probleme nicht
+in der Komplexitätsklasse~\textit{P} liegen, wäre eine Konsequenz, dass es
+effiziente exakte Algorithmen für diese Probleme nicht geben kann. Falls sich
+hingegen herausstellt, dass diese Probleme in der
+Komplexitätsklasse~\textit{P} liegen, wird es mit großer Wahrscheinlichkeit
+noch einige Zeit dauern, bis auch Algorithmen mit praktikablen Zeitkonstanten
+gefunden werden.
Aus diesem Grund besteht die Notwendigkeit einen Kompromiss einzugehen: Statt
-die bzw. eine der {\em optimalen} Lösungen als einzige Ausgabe des Algorithmus
-zuzulassen, wird eine "`möglichst gute"' Lösung ausgegeben. Viele dieser
-Optimierungsalgorithmen orientieren sich an Vorgängen in der Natur,
-beispielsweise immitieren die "`Ameisenalgorithmen"' das Verhalten von Ameisen
+die beziehungsweise eine der {\em optimalen} Lösungen als einzige Ausgabe des
+Algorithmus zuzulassen, wird eine "`möglichst gute"' Lösung ausgegeben. Viele
+dieser Optimierungsalgorithmen orientieren sich an Vorgängen in der Natur,
+beispielsweise imitieren die "`Ameisenalgorithmen"' das Verhalten von Ameisen
auf der Futtersuche um kurze Rundreisen auf Graphen zu berechnen.
Bei {\em Evolutionären Algorithmen} stand die Evolution pate. Die Grundidee
-ist es, bestehende Lösungen zu neuen, unter Umständen besseren Lösungen zu
+ist, bekannte Lösungen zu neuen -- unter Umständen besseren -- Lösungen zu
kombinieren. Dabei bedient man sich der in der Evolutionstheorie etablierten
-Nomenklatur, beispielsweise werden konkrete Lösungen für ein Problem häufig
-als {\em Individuum} bezeichnet.
+Nomenklatur, beispielsweise werden konkrete Lösungen für ein Problem als {\em
+Individuen} bezeichnet.
Die Vorgehensweise lässt sich abstrakt wie folgt beschreiben. Aus einer
-bestehenden Lösungsmenge, der {\em Population} werden zufällig Lösungen
+bestehenden Lösungsmenge, der {\em Population}, werden zufällig Lösungen
ausgesucht {\em (Selektion)} und zu einer neuen Lösung kombiniert ({\em
Rekombination}). Unter Umständen wird die neue Lösung noch zufällig
verändert {\em (Mutation)}, bevor sie in die bestehende Lösungsmenge
-integriert wird. Die Wahrscheinlichkeiten, beispielsweise bei der {\em
-Selektion}, sind dabei nicht zwangsläufig gleichverteilt -- üblicherweise
+eingefügt wird. Die verwendeten Wahrscheinlichkeiten, beispielsweise bei der
+{\em Selektion}, sind dabei nicht zwangsläufig gleichverteilt -- üblicherweise
werden bessere Lösungen bevorzugt. Zur Bewertung dient die sogenannte {\em
Gütefunktion}.
Nicht alle Probleme eignen sich für diese Strategie: Zum einen muss es möglich
sein, eine initiale Population zur Verfügung zu stellen, da diese als Basis
aller weiteren Operationen dient. Das ist häufig keine große Einschränkung, da
-es oft einfach ist {\em irgendeine} Lösung anzugeben. Zum anderen muss eine
-Methode für die Rekombination existieren. Das insbesondere dann problematisch
-wenn {\em Nebenbedingungen} eingehalten werden müssen.
+es oft einfach ist {\em irgendeine} Lösung anzugeben. Die angegebenen
+Algorithmen verwenden als einfache, initiale Lösung häufig das
+\emph{Odd-Even-Transpositionsort}-Netzwerk, das in
+Abschnitt~\ref{sect:odd_even_transpositionsort} beschrieben wird. Zum anderen
+muss eine Methode für die Rekombination existieren. Das ist insbesondere dann
+problematisch, wenn {\em Nebenbedingungen} eingehalten werden müssen.
Beim Aussuchen von zufälligen Lösungen aus der Population, der
\emph{Selektion}, werden gute Lösungen bevorzugt. Wie sehr diese Lösungen
beispielsweise bei der Optimierung von Sortiernetzwerken die Parameter
zwischen verschiedenen Leitungszahlen stark unterscheiden.
-\begin{itemize}
-\item Unter einem "`Evolutionären Algorithmus"' versteht man $\ldots$
-\item Da die Sortiereigenschaft zu überprüfen NP-schwer ist, ist die
-Mutation \textit{(vermutlich)} nicht (effizient) möglich.
-\end{itemize}
+Die \textit{Exploration} kann von einem weiteren Mechanismus unterstützt
+werden, der ebenfalls der Evolutionslehre entliehen ist, der \emph{Mutation}.
+Dabei werden Lösungen zufällig verändert, so dass auch andere Lösungen „in der
+Nähe“ von direkten Nachfolgern erreicht werden können. Das hilft insbesondere
+bei der intensiven Suche in der Nähe eines lokalen Optimums aber auch beim
+„Ausbrechen“ und finden noch besserer Lösungen.
+
+Bei \emph{Sortiernetzwerken} ist eine \emph{Mutation} leider immer damit
+verbunden, dass anschließend die Sortiereigenschaft des resultierenden
+\emph{Komparatornetzwerks} wieder überprüft werden muss, da selbst das
+Hinzufügen eines zufälligen Komparators diese Eigenschaft zerstören kann. Beim
+Suchen möglichst effizienter Netzwerke ist natürlich das zufällige Entfernen
+von Komparatoren interessanter, was die Sortiereigenschaft sehr oft aufhebt.
+
+Die im Folgenden beschriebenen Algorithmen mutieren (verändern) daher nicht
+die \emph{Sortiernetzwerke} selbst, sondern verzichten auf Mutation oder
+mutieren lediglich Transformationen von Sortiernetzwerken, die die
+Sortiereigenschaft erhält. Transformationen von Sortiernetzwerken werden in
+Abschnitt~\ref{sect:tranformation} beschrieben, ein Algorithmus, der Mutation
+einsetzt, wird in Abschnitt~\ref{sect:sn-evolution-cut} vorgestellt.
\newpage
\section{Bekannte konstruktive Sortiernetzwerke}
Das \emph{Odd-Even-Mergesort-Netzwerk} $\operatorname{OES}(n)$ besteht --~wie
das \emph{bitone Mergesort-Netzwerk}~-- rekursiv aus kleineren Varianten von
sich selbst und einem abschließenden \emph{Odd-Even-Mischer}. Die
-effizientesten Sortiernetzwerke in Bezuf auf Komparator- und Schichtzahl
+effizientesten Sortiernetzwerke in Bezug auf Komparator- und Schichtzahl
entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht
$\operatorname{OES}(n)$ aus
$\operatorname{OES}\left(\left\lceil\frac{n}{2}\right\rceil\right)$,
die Komparatoren, die in ersten Rekursionsschritt hinzugefügt werden.
Im Allgemeinen ist die Anzahl der Komparatoren, die vom
-\emph{Odd-Even-Mergesort-Netzwerk} verwendet wird, $k(n)$, direkt aus der
+\emph{Odd-Even-Mergesort-Netz\-werk} verwendet wird, $k(n)$, direkt aus der
Definition beziehungsweise der Konstruktionsanleitung abzulesen:
\begin{displaymath}
k(n) = k\left(\left\lceil\frac{n}{2}\right\rceil\right)
\newpage
\section{Transformation von Sortiernetzwerken}
+\label{sect:tranformation}
\subsection{Komprimieren}
-\todo{Aus theoretischer Sicht eigentlich eine Trivialität. Rausschmeißen?}
-
Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
gleichzeitig ausgewertet werden, wie bereits in
-Abschnitt~\ref{sect:einleitung_sortiernetzwerke} beschrieben. Unter
-\emph{Komprimieren} wird eine (Neu-)Gruppierung in die kleinstmögliche Anzahl
-von \emph{Schichten} verstanden.
+Abschnitt~\ref{sect:einleitung_sortiernetzwerke} beschrieben. Durch manche
+Transformationen, insbesondere das Entfernen einer Leitung, das in
+Abschnitt~\ref{sect:leitungen_entfernen} beschrieben wird, kann es vorkommen,
+dass die Komparatoren eines Sortiernetzwerks nicht mehr in der
+kleinstmöglichen Anzahl von \emph{Schichten} angeordnet sind. Unter
+\emph{Komprimierung} wird eine (Neu-)Gruppierung der Komparatoren verstanden,
+die jeden Komparator so früh wie möglich ausführt. So entsteht die
+kleinstmögliche Anzahl von \emph{Schichten}, in die sich ein Sortiernetzwerk
+unterteilen lässt.
Diese Anzahl ist insbesondere beim automatisierten Bewerten von
-Komparatornetzwerken interessant. \dots
+Komparatornetzwerken interessant, wie in Abschnitt~\ref{sect:bewertung}
+beschrieben. Die Anzahl der Schichten kann künstlich vergrößert werden, indem
+Komparatoren später angewandt werden. Deshalb sollte vor einer Bewertung, die
+die Anzahl der Schichten als Bewertungskriterium verwendet, immer eine
+Komprimierung durchgeführt werden.
\subsection{Normalisieren}
Ein \emph{Standard-Sortiernetzwerk} oder \emph{normalisiertes Sortiernetzwerk}
ist ein Sortiernetzwerk, dessen Komparatoren alle in die selbe Richtung
zeigen. Jedes Sortiernetzwerk kann in eine normaliesierte Variante
-transformiert werden. Dazu gibt beispielsweise \emph{Knuth} (\todo{Verweis})
-einen Algorithmus an.
+transformiert werden. Dazu gibt beispielsweise \emph{Donald~E. Knuth}
+in~\cite{KNUTH} einen Algorithmus an.
Abbildung~\ref{fig:beispiel_normalisieren} zeigt das das
bitone Sortiernetzwerk in zwei Varianten. Abbildung~\ref{fig:bitonic-nonstd}
%\item Nach dem Pairwise sorting-network Schema.
%\end{itemize}
-\subsection{Leitungen entfernen}\label{sect:leitungen_entfernen}
+\subsection{Leitungen entfernen}
+\label{sect:leitungen_entfernen}
Im vorherigen Abschnitt haben wir gesehen, dass es mithilfe von
\emph{Mischern} möglich ist, aus zwei Sortiernetzwerken mit je $n$~Eingängen
\begin{figure}
\begin{center}
- \includegraphics[viewport=0 0 360 216,width=15cm]{images/count-cuts-16.pdf}
+ \includegraphics[viewport=0 0 425 262,width=15cm]{images/count-cuts-16.pdf}
\end{center}
\caption{Anzahl der \emph{unterschiedlichen} Sortiernetzwerke, die durch
8-Schnittmuster aus $\operatorname{OES}(16)$, $\operatorname{BS}(16)$ und
{\em Güte} eines Netzwerkes definiert werden. Prinzipiell gibt es zwei Ziele,
die bei Sortiernetzwerken verfolgt werden können:
\begin{itemize}
- \item Möglichst wenige Komparatoren („billig“)
+ \item Möglichst wenige Komparatoren („effizient“)
\item Möglichst wenige Schichten („schnell“)
\end{itemize}
Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das
-billigste bekannte Sortiernetzwerk für 16~Eingänge besteht aus 60~Komparatoren
-in 10~Schichten. Das schnellste Netzwerk besteht aus 61~Komparatoren in nur
-9~Schichten.
+effizienteste bekannte Sortiernetzwerk für 16~Eingänge besteht aus
+60~Komparatoren in 10~Schichten. Das schnellste Netzwerk besteht aus
+61~Komparatoren in nur 9~Schichten.
-Eine Gütefunktion, die die beiden Ziele "`billig"' und "`schnell"'
+Eine Gütefunktion, die die beiden Ziele "`effizient"' und "`schnell"'
berücksichtigen kann, hat die folgende allgemeine Form:
\begin{equation}
\operatorname{Guete}(S) = w_{\mathrm{Basis}}
so schlecht ist wie man intuitiv vermuten könnte, zeigt der
\textsc{SN-Markov}-Algorithmus in Abschnitt~\ref{sect:markov}.}
-Da möglichst billige und schnelle Sortiernetzwerke gefunden werden sollen, ist
-ein kleiner Wert von $\operatorname{Guete}(S)$ besser als ein großer Wert. Das
-heißt, dass das Ziel von \textsc{SN-Evolution} ist, $\operatorname{Guete}(S)$
-zu \emph{minimieren}.
+Da möglichst effiziente und schnelle Sortiernetzwerke gefunden werden sollen,
+ist ein kleiner Wert von $\operatorname{Guete}(S)$ besser als ein großer Wert.
+Das heißt, dass das Ziel von \textsc{SN-Evolution} ist,
+$\operatorname{Guete}(S)$ zu \emph{minimieren}.
Mit dem Parameter $w_{\mathrm{Basis}}$ kann auf die Selektion Einfluss
genommen werden. Ist er groß, wird der relative Unterschied der Güten
Die in \textsc{SN-Evolution} implementierte Selektion lässt sich mithilfe von
Pseudocode wie folgt beschreiben:
\begin{verbatim}
-Guetesumme := 0
+Gütesumme := 0
Auswahl := (leer)
-fuer jedes Individuum in Population
+für jedes Individuum in Population
{
- reziproke Guete := 1.0 / Guete(Individuum)
- Wahrscheinlichkeit P := reziproke Guete / (reziproke Guete + Guetesumme)
- Guetesumme := Guetesumme + reziproke Guete
+ reziproke Güte := 1.0 / Guete(Individuum)
+ Wahrscheinlichkeit P := reziproke Güte / (reziproke Güte + Gütesumme)
+ Gütesumme := Gütesumme + reziproke Güte
mit Wahrscheinlichkeit P
{
Auswahl := Individuum
}
}
-gebe Auswahl zurueck
+gib Auswahl zurück
\end{verbatim}
\subsection{Rekombination}
$S_0$ ist, das heißt dass man $S_1$ durch die Rekombination von $S_0$ mit sich
selbst erzeugen kann.
-Wie in Abschnitt~\ref{sect:anzahl_schnittmuster} beschrieben ist die Anzahl
-(unterschiedlicher) Schnittmuster und damit die Anzahl der Nachfolger sehr
-groß. Wenn $S_0$ ein Sortiernetzwerk mit $n$~Leitungen ist, so hat $S_0$ bis
-zu
-\begin{displaymath}
- 2^n \cdot \left( \begin{array}{c} 2n \\ n \end{array} \right)
-\end{displaymath}
-Nachfolger.
+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.
Der Algorithmus {\sc SN-Markov} legt auf diesem Nachfolger-Graph einen
zufälligen Weg (englisch: \textit{random walk}) zurück. Er startet auf einem
gegebenen Sortiernetzwerk. Um von einem Sortiernetzwerk zum Nächsten zu
gelangen, rekombiniert der Algorithmus das aktuelle Sortiernetzwerk mit sich
-selbst und erhält so einen zufälligen Nachfolger.
+selbst und erhält so einen zufälligen Nachfolger. In Pseudocode lässt dich der
+Algorithmus wie folgt beschreiben:
+
+\begin{verbatim}
+Netzwerk := Eingabe
+
+für n Iterationen
+{
+ Nachfolger := kombiniere (Netzwerk, Netzwerk)
+ Netzwerk := Nachfolger
+}
+
+gib Netzwerk zurück
+\end{verbatim}
+
+\begin{figure}
+ \begin{center}
+ \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-cycles-16.pdf}
+ \end{center}
+ \caption{Zyklen, die beim \textit{Random Walk} des
+ \textsc{SN-Markov}-Algorithmus detektiert wurden. Auf der x-Achse sind die
+ Anzahl der Schritte, die \textsc{SN-Markov} zurückgelegt hat, auf der
+ y-Achse die Längen der gefundenen Zyklen aufgetragen. Das initiale
+ Start-Sortiernetzwerk war $\operatorname{OET}(16)$.}
+ \label{fig:markov-cycles-16}
+\end{figure}
-\begin{itemize}
- \item $n \leftarrow \mathrm{Input}$
- \item \texttt{while} \textit{true}
- \begin{itemize}
- \item $n \leftarrow \operatorname{recombine} (n, n)$
- \end{itemize}
-\end{itemize}
\begin{itemize}
\item Beste erreichte Netzwerke (gleich zu \emph{OE-Mergesort}).
\begin{figure}
\begin{center}
- \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-12-pct.pdf}
+ \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
\begin{figure}
\begin{center}
- \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-14-pct.pdf}
+ \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
\begin{figure}
\begin{center}
- \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-16-pct.pdf}
+ \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
\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{Empirische Beobachtungen}
projects / diplomarbeit.git / blobdiff