X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=711684092091b4816cacc7f8c4560c2b499329fc;hb=e3d11cafeebaaaf9dcf1344bb690cb5b16fcb644;hp=9a18aef4271a4ec41557d4a095274f560ed934a5;hpb=e81afe3513a7297779b5ecfaecafb5ad6e1db6f6;p=diplomarbeit.git

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index 9a18aef..7116840 100644
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -262,9 +262,12 @@ 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
@@ -286,11 +289,26 @@ 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
-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}
@@ -728,19 +746,28 @@ gilt.
 
 \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}
 
@@ -757,8 +784,8 @@ Komparatornetzwerken interessant. \dots
 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}
@@ -842,7 +869,8 @@ nur mit exponentiellem Aufwand möglich ist.
 %\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
@@ -1108,16 +1136,16 @@ Um Sortiernetzwerke überhaupt optimieren zu können, muss zunächst die
 {\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}}
@@ -1132,10 +1160,10 @@ 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}.
+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