\label{fig:count-cuts-16}
\end{figure}
-Um die Anzahl der \emph{unterschiedlichen} Schnittmuster abschätzen zu können,
-wurden je eine Million zufällige 8-Schnittmuster auf die 16-Sortiernetzwerke
+Alleine durch Betrachten der ersten Schicht von Komparatoren konnte die Anzahl
+der \emph{unterschiedlichen} Schnittmuster auf höchstens $\frac{2}{3}$ der
+\emph{möglichen} Schnittmuster reduziert werden. Um die Anzahl der
+\emph{unterschiedlichen} Schnittmuster experimentell zu ermitteln, 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
+angewandt. Anschließend wurde mithilfe einer Hashtabelle überprüft, ob das
+resultierende Sortiernetzwerk schon von einem \emph{äquivalenten}
+Schnittmuster erzeugt wurde. Falls das Sortiernetzwerk noch nicht in der
+Hashtabelle enthalten war, wurde der Zähler für unterschiedliche Schnittmuster
+erhöht und das Sortiernetzwerk eingefügt.
+
+Abbildung~\ref{fig:count-cuts-16} trägt die Anzahl der
\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
nahe ist.
-Die Anzahl der 8-Schnittmuster ist entsprechend der
+Die Anzahl der möglichen 8-Schnittmuster ist entsprechend der
Formel~\ref{eqn:anzahl_schnittmuster} 3.294.720. Diese möglichen Schnittmuster
führen aber nur zu wenigen \emph{unterschiedlichen} Sortiernetzwerken: 3519
($\approx 0,1\%$) im Fall des \emph{Odd-Even-Mergesort-Netzwerks}, 4973
vernachlässigbar klein ist.
Bedingt durch die sehr große Anzahl möglicher Schnittmuster ist dieses
-Experiment für größere Sortiernetzwerke leider nicht sinnvoll durchführbar. Um
-die Anzahl der unterschiedlichen Schnittmuster trotzdem abschätzen zu können,
-kann man sich einer stochastischen Methode bedienen, der sogenannten
+Experiment für größere Sortiernetzwerke leider nicht sinnvoll durchführbar.
+Die Hashtabelle benötigt mehr Arbeitsspeicher als in derzeitigen Rechnern
+vorhanden ist, bevor ein entsprechender Graph den linearen Bereich für
+„kleine“ x-Werte verlässt.
+
+Um 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.
-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
+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
unterschiedlichen Schnittmuster abschätzen.
\newpage
\section{Der \textsc{SN-Evolution}-Algorithmus}
-Um einen evolutionären Algorithmus für Sortiernetzwerke zu entwickeln, werden
-die vorgestellten Methoden kombiniert.
+Der \textsc{SN-Evolution}-Algorithmus ist ein \emph{evolutionärer
+Algorithmus}, der die in den vorherigen Abschnitten beschriebenen Mischer
+(Abschnitt~\ref{sect:konstruktive_netzwerke}) und Schnittmuster
+(Abschnitt~\ref{sect:leitungen_entfernen}) verwendet, um „möglichst gute“
+Sortiernetzwerke zu erzeugen. Was ein „gutes“ Sortiernetzwerk ausmacht, wird
+in Abschnitt~\ref{sect:bewertung} behandelt.
\subsection{Bewertungsfunktion}\label{sect:bewertung}
Um Sortiernetzwerke überhaupt optimieren zu können, muss zunächst die
{\em Güte} eines Netzwerkes definiert werden. Prinzipiell gibt es zwei Ziele,
-die interessant sind:
+die bei Sortiernetzwerken verfolgt werden können:
\begin{itemize}
- \item Möglichst wenige Komparatoren ("`klein"')
- \item Möglichst wenige Schichten ("`schnell"')
+ \item Möglichst wenige Komparatoren („billig“)
+ \item Möglichst wenige Schichten („schnell“)
\end{itemize}
Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das
-kleinste bekannte Sortiernetzwerk für 16~Eingänge besteht aus 60~Komparatoren
+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.
-Eine Gütefunktion, die die beiden Ziele "`klein"' und "`schnell"'
+Eine Gütefunktion, die die beiden Ziele "`billig"' und "`schnell"'
berücksichtigen kann, hat die folgende allgemeine Form:
\begin{equation}
\operatorname{Guete}(S) = w_{\mathrm{Basis}}
dabei der Festlegung des Optimierungsziels. Wenn einer der beiden Parameter
gleich Null ist, wird nur das jeweils andere Ziel verfolgt. Sind beide
Parameter gleich Null, werden alle Netzwerke mit der gleich Güte bewertet --
-jegliche Ergebnisse sind dann rein zufälliger Natur.
+jegliche Ergebnisse sind dann rein zufälliger Natur.\footnote{Dass dies nicht
+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}.
Mit dem Parameter $w_{\mathrm{Basis}}$ kann auf die Selektion Einfluss
genommen werden. Ist er groß, wird der relative Unterschied der Güten
verschiedener Netzwerke kleiner, was die {\em Exploration}, das Absuchen des
gesamten Lösungsraums, begünstigt. Wählt man $w_{\mathrm{Basis}}$ hingegen
-klein, in Abhängigkeit von den anderen beiden Parametern sind auch negative
-Werte möglich, werden die relativen Unterschiede groß. Dadurch wird die {\em
-Exploitation}, das Finden lokaler Optima, bevorzugt.
+klein -- in Abhängigkeit von den anderen beiden Parametern sind auch negative
+Werte möglich -- werden die relativen Unterschiede groß. Dadurch wird die {\em
+Exploitation}, das Finden (lokaler) Optima, bevorzugt.
+
+Diese Parameter haben einen großen Einfluss auf die Geschwindigkeit, mit der
+der \textsc{SN-Evolution}-Algorithmus konvergiert und ob er tatsächlich gute
+Lösungen findet oder sich in \emph{lokalen} Optima verrennt. Leider gibt es
+kein Patentrezept für die Wahl der Parameter, so dass für verschiedene
+Leitungszahlen und Mischer-Typen experimentiert werden muss.
\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.
+
+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.
+
+Die in \textsc{SN-Evolution} implementierte Selektion lässt sich mithilfe von
+Pseudocode wie folgt beschreiben:
+\begin{verbatim}
+Guetesumme := 0
+Auswahl := (leer)
+
+fuer jedes Individuum in Population
+{
+ reziproke Guete := 1.0 / Guete(Individuum)
+ Wahrscheinlichkeit P := reziproke Guete / (reziproke Guete + Guetesumme)
+ Guetesumme := Guetesumme + reziproke Guete
+
+ mit Wahrscheinlichkeit P
+ {
+ Auswahl := Individuum
+ }
+}
+gebe Auswahl zurueck
+\end{verbatim}
\subsection{Rekombination}
\newpage
\section{Der \textsc{SN-Markov}-Algorithmus}
+\label{sect:markov}
Der evolutionäre \textsc{SN-Evolution}-Algorithmus aus dem vorherigen
Abschnitt verwendete immer zwei zufällige Sortiernetzwerke („Individuen“) aus
projects / diplomarbeit.git / blobdiff