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
-werden bessere Lösungen bevorzugt. Zur Bewertung die die sogenannte {\em
+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
Methode für die Rekombination existieren. Das 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
+bevorzugt werden, hat einen starken Einfluss auf das Verhalten des
+Algorithmus. Werden gute Lösungen stark bevorzugt, konvergiert der Algorithmus
+schnell gegen ein (lokales) Optimum. Dieses \textit{Exploitation} (Englisch
+für „Ausnutzung“) genannte Verhalten sorgt dafür, dass sich der Algorithmus
+schnell auf eine Lösung festlegt und andere, möglicherweise bessere lokale
+Optima nicht mehr findet. Werden gute Lösungen hingegen nur wenig bevorzugt,
+erforscht der Algorithmus den Lösungsraum in viele Richtungen. Dieses
+\textit{Exploration} (Englisch für „Erforschung“) genannte Verhalten sorgt
+zwar dafür, dass der Algorithmus langsamer auf ein Optimum zusteuert, dafür
+findet er aber in der Regel bessere Lösungen.
+
+Die Parameter evolutionärer Algorithmen so einzustellen, dass sich ein guter
+Mittelweg zwischen den beiden Extremen einstellt, ist eine Aufgabe, die sich
+nur experimentell lösen lässt. Die genauen Parameter hängen nicht nur vom
+eigentlichen Algorithmus, sondern auch vom konkreten Problem ab, so dass sich
+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
\newpage
\section{Bekannte konstruktive Sortiernetzwerke}
+\label{sect:konstruktive_netzwerke}
Übersicht über bekannte konstruktive Sortiernetzwerke.
zusammenfügen kann. Dabei kommt es mit weniger Vergleichen aus als der
\emph{bitone Mischer}, der im Abschnitt~\ref{sect:der_bitone_mischer}
vorgestellt wurde. Allerdings benötigt der \emph{Odd-Even-Mischer} unter
-Umständen mehr Schichten als der \emph{bitone Mischer}.\footnote{Knuth,
-“Bitonic Sorting”, Seite~230}
+Umständen mehr Schichten als der \emph{bitone Mischer}.~\cite{KNUTH}
Der \emph{Odd-Even-Mischer} selbst ist ebenfalls rekursiv aufgebaut: Die
Eingabe für den Mischer mit $N = n + m$ Leitungen besteht aus den beiden
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 wir auf diese Art und
-Weise einen Sortiernetzwerk mit $2n$~Eingängen wieder auf ein Sortiernetzwerk
-mit $n$~Eingängen reduzieren. Das Anwenden mehrerer Minimum- und
-Maximum-Schnitte bezeichnen wir als \emph{Schnittmuster}.
+$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
+nacheinander angewendet ein $n$-Sortiernetzwerk auf ein
+${(n-k)}$-Sortiernetz\-werk reduzieren, bezeichnen wir als
+\emph{$k$-Schnittmuster}.
Zwei Schnittmuster heißen \emph{äquivalent} bezüglich~$S$, wenn ihre Anwendung
auf das Sortiernetzwerk~$S$ das selbe Ergebnis liefert. Ansonsten heißen die
Bei einem Sortiernetzwerk mit $n$~Eingängen gibt es $2n$~Möglichkeiten eine
Leitung zu entfernen: Auf jeder der $n$~Leitungen kann sowohl das Minimum als
auch das Maximum angenommen werden. Wendet man das Verfahren iterativ an, um
-ein $n$-Sortiernetzwerk auf ein $m$-Sortiernetzwerk zu reduzieren, ergeben
-sich insgesamt
+ein $n$-Sortiernetzwerk auf ein ${(n-k)}$-Sortiernetzwerk zu reduzieren,
+ergeben sich insgesamt
\begin{equation}\label{eqn:anzahl_schnittmuster}
- \prod_{i=n}^{m+1} 2i = 2^{n-m} \frac{n!}{m!}
+ \prod_{i=n}^{1+n-k} 2i = 2^k \frac{n!}{(n-k)!}
\quad (n > m)
\end{equation}
\emph{mögliche} Schnittmuster. Diese Schnittmuster sind nicht alle
und das Maximum auf die oberste Leitung eines Standard-Sortiernetzwerks,
führen beide Reihenfolgen zum selben Ergebnis.
-\textit{Moritz Mühlenthaler} zeigt in seiner Arbeit (\todo{Referenz}), dass
-es möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise
-Maximum vorzubelegen. Dadurch wird die Anzahl der möglichen Schnittmuster
-reduziert, die Menge der so erzeugbaren Sortiernetzwerke bleibt aber
-unverändert. Die Anzahl der möglichen Schnittmuster setzt sich zusammen aus
-der Anzahl von Möglichkeiten, $n-m$~Leitungen aus $n$ Leitungen auszuwählen,
-und die möglichen Minimum-~/ Maximum-Muster. Damit ergibt sich folgende
-Formel für die Anzahl der Schnittmuster:
+\textit{Moritz Mühlenthaler} zeigt in seiner Arbeit (\todo{Referenz}), dass es
+möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise Maximum
+vorzubelegen. Dadurch wird die Anzahl der möglichen Schnittmuster reduziert,
+die Menge der so erzeugbaren Sortiernetzwerke bleibt aber unverändert. Die
+Anzahl der möglichen Schnittmuster setzt sich zusammen aus der Anzahl von
+Möglichkeiten, $k$~Leitungen aus $n$~Leitungen auszuwählen, und die möglichen
+Minimum-~/ Maximum-Muster. Damit ergibt sich folgende Formel für die Anzahl
+der möglichen Schnittmuster:
\begin{displaymath}
- 2^{n-m} \cdot \left( \begin{array}{c} n \\ n-m \end{array} \right)
- = 2^{n-m} \cdot \frac{n!}{(n-m)! m!}
- = 2^{n-m} \cdot \frac{n!}{m!} \cdot \frac{1}{(n-m)!}
- \quad (n > m)
+ 2^k \cdot \left( \begin{array}{c} n \\ k \end{array} \right)
+ = 2^{k} \cdot \frac{n!}{k! (n-k)!}
+ = 2^{k} \cdot \frac{n!}{(n-k)!} \cdot \frac{1}{k!}
+ \quad (1 \leqq k < n)
\end{displaymath}
Die Anzahl der möglichen Schnittmuster wird mit der Anzahl der zu entfernenden
wurden je eine Million zufällige 8-Schnittmuster auf die 16-Sortiernetzwerke
$\operatorname{OES}(16)$, $\operatorname{BS}(16)$ und $\operatorname{PS}(16)$
angewandt. Abbildung~\ref{fig:count-cuts-16} trägt die Anzahl der
-\emph{unterschiedlichen} Sortiernetzwerke gegen die Anzahl der zufälligen
+\emph{unterschiedlichen} Schnittmuster gegen die Anzahl der zufälligen
Schnittmuster auf. Klar zu sehen ist, dass sich die Anzahl der erzeugten
Sortiernetzwerke nach $500.000$~Iterationen nur noch gering verändert und der
Wert nach $1.000.000$~Iterationen allem Anschein nach dem Endwert schon sehr
($\approx 0,1\%$) im Fall des \emph{Odd-Even-Mergesort-Netzwerks}, 4973
($\approx 0,15\%$) beim \emph{bitonen Mergesort-Netzwerk} und 18764 ($\approx
0,57\%$) beim \emph{Pairwise-Sorting-Netzwerk}. Zwar ist es möglich, dass mehr
-Iterationen die Anzahl der unterschiedlichen Netzwerke noch wachsen lässt. Die
-Graphen in Abbildung~\ref{fig:count-cuts-16} geben jedoch Grund zu der
-Annahme, dass Anzahl dieser zusätzlichen, unterschiedlichen Schnittmuster
+Iterationen die Anzahl der unterschiedlichen Schnittmuster noch wachsen lässt.
+Die Graphen in Abbildung~\ref{fig:count-cuts-16} geben jedoch Grund zu der
+Annahme, dass die Anzahl dieser zusätzlichen, unterschiedlichen Schnittmuster
vernachlässigbar klein ist.
Bedingt durch die sehr große Anzahl möglicher Schnittmuster ist dieses
kann man sich einer stochastischen Methode bedienen, der sogenannten
\emph{Monte-Carlo-Methode}. Zunächst generiert man eine Menge~$S$ von
$k$~unterschiedlichen Schnittmustern. Anschließend werden $n$~Schnittmuster
-zufällig erzeugt, und überprüft, ob sie sich in der Menge~$S$ enthalten sind.
+zufällig erzeugt und überprüft, ob sie sich in der Menge~$S$ enthalten sind.
Unter der Annahme, dass das Verhältnis der zufälligen Schnittmuster, die in $S$
enthalten sind, und $n$ dem Verhältnis von $k$ und der Anzahl der
unterschiedlichen Schnittmuster ingesamt entspricht, kann man die Anzahl der
In Abbildung~\ref{fig:collisions-10000-1000000-32} ist das Ergebnis des
Monte-Carlo-Algorithmus für 16-Schnittmuster zu sehen, die auf
$\operatorname{OES}(32)$ und $\operatorname{BS}(32)$ angewandt wurden: Von
-jedem Sortiernetzwerk wurden zunächst eine Menge von 10.000
+jedem Sortiernetzwerk wurden zunächst eine Menge~$S$ von 10.000
\emph{unterschiedlichen} Schnittmustern erzeugt. Anschließend wurden 1.000.000
zufällige Schnittmuster erzeugt und der Anteil der zufälligen Schnittmuster,
-die identisch zu einem in der Menge enthalten Schnittmuster sind, berechnet.
+die \emph{äquivalent} zu einem in~$S$ enthalten Schnittmuster sind, berechnet.
Für $\operatorname{OES}(32)$ war dieser Anteil etwa $0,19 \%$, für
$\operatorname{BS}(32)$ etwa $0,29 \%$. Das ergibt eine Abschätzung von $5,2
\cdot 10^6$ unterschiedlichen Schnittmustern für $\operatorname{OES}(32)$ und
unterschiedlicher Schnittmuster, wurde für das gleiche Experiment mit
$\operatorname{PS}(32)$ eine initiale Menge von 100.000 unterschiedilchen
Schnittmustern erzeugt. Trotzdem wurden nach 1.000.000 Iterationen nur 385
-Schnittmuster gefunden, die ein Sortiernetzwerk aus dieser Menge erzeugen.
-Daraus ergibt sich eine Abschätzung von $2,6 \cdot 10^8$ unterschiedlichen
-Schnittmustern -- zwei Zehnerpotenzen mehr als bei den vorherigen
-Sortiernetzwerken, aber immernoch fünf Zehnerpotenzen kleiner als die Anzahl
-der \emph{möglichen} Schnittmuster.
+Schnittmuster gefunden, die zu einem Schnittmuster in der Menge äquivalent
+sind. Daraus ergibt sich eine Abschätzung von $2,6 \cdot 10^8$
+unterschiedlichen Schnittmustern -- zwei Zehnerpotenzen mehr als bei den
+vorherigen Sortiernetzwerken, aber immernoch fünf Zehnerpotenzen kleiner als
+die Anzahl der \emph{möglichen} Schnittmuster.
\newpage
\section{Der \textsc{SN-Evolution}-Algorithmus}
hervorgehen können, heißen \emph{Nachfolger} von $S_0$.
Beim beschriebenen Vorgehen kann man die Sortiernetzwerke als Knoten in einem
-gerichteten Graphen betrachten. Zwei Knoten $V_0$ und $V_1$, die zwei
+(gerichteten) Graphen betrachten. Zwei Knoten $V_0$ und $V_1$, die zwei
Sortiernetzwerke $S_0$ und $S_1$ repräsentieren, sind genau dann mit einer
-Kante ${E_{0,1} = (V_0, V_1)}$ verbunden, wenn $S_1$ ein \emph{Nachfolger} von $S_0$
-ist, das heißt dass man $S_1$ durch die Rekombination von $S_0$ mit sich
+Kante ${E_{0,1} = (V_0, V_1)}$ verbunden, wenn $S_1$ ein \emph{Nachfolger} von
+$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
-(unterschiedlichen) Schnittmuster und damit die Anzahl der Nachfolger sehr
+(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}
\end{displaymath}
Nachfolger.
-Der Algorithmus {\sc SN-Markov} legt auf diesem 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 er das aktuelle Sortiernetzwerk mit sich selbst und erhält so
-einen zufälligen Nachfolger.
+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.
\begin{itemize}
\item $n \leftarrow \mathrm{Input}$
Das würde mir noch einfallen$\ldots$
\newpage
+\section{Implementierung}
+
+So habe ich die ganzen Versuche durchgeführt.
+
+\newpage
\bibliography{references}
\bibliographystyle{plain}
projects / diplomarbeit.git / blobdiff