X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=25d6329db092daf40bb3a9311a9c98991c8b7818;hb=678969a72ce687ffdfcb64e9ec8a2f60ad7266c9;hp=21ff5e0377a580aa181acfed54aca62f5b12f214;hpb=88f8374f92aaee4c291f70e9faa72d42427d82cd;p=diplomarbeit.git

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index 21ff5e0..25d6329 100644
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -208,7 +208,7 @@ 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
-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
@@ -218,6 +218,26 @@ 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.
 
+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
@@ -226,6 +246,7 @@ Mutation \textit{(vermutlich)} nicht (effizient) möglich.
 
 \newpage
 \section{Bekannte konstruktive Sortiernetzwerke}
+\label{sect:konstruktive_netzwerke}
 
 Übersicht über bekannte konstruktive Sortiernetzwerke.
 
@@ -447,8 +468,7 @@ Elementen zu einer sortierten Ausgabefolge mit $N = n+m$~Elementen
 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
@@ -849,10 +869,12 @@ Ausgabe und kann entfernt werden.
 
 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
@@ -861,10 +883,10 @@ Schnittmuster \emph{unterschiedlich} bezüglich~$S$.
 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
@@ -872,19 +894,19 @@ unterschiedlich. Legt man beispielsweise das Minimum auf die unterste Leitung
 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
@@ -928,7 +950,7 @@ Um die Anzahl der \emph{unterschiedlichen} Schnittmuster abschätzen zu können,
 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
@@ -940,9 +962,9 @@ führen aber nur zu wenigen \emph{unterschiedlichen} Sortiernetzwerken: 3519
 ($\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
@@ -951,7 +973,7 @@ die Anzahl der unterschiedlichen Schnittmuster trotzdem abschätzen zu können,
 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
@@ -970,10 +992,10 @@ unterschiedlichen Schnittmuster abschätzen.
 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
@@ -1003,11 +1025,11 @@ man keine Details mehr erkennen können. Aufgrund der hohen Anzahl
 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}
@@ -1365,14 +1387,14 @@ $S_0$ mit sich selbst und anschließendem Eliminieren der Hälfte der Leitungen
 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}
@@ -1380,11 +1402,11 @@ zu
 \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}$
@@ -1445,6 +1467,11 @@ einen zufälligen Nachfolger.
 Das würde mir noch einfallen$\ldots$
 
 \newpage
+\section{Implementierung}
+
+So habe ich die ganzen Versuche durchgeführt.
+
+\newpage
 \bibliography{references}
 \bibliographystyle{plain}