Evolutionäre Algorithmen: Etwas zur Mutation geschrieben.

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index 9a18aef..5af502f 100644 (file)
--- 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
 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
 
 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.
 
 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}
 
 \newpage
 \section{Bekannte konstruktive Sortiernetzwerke}


@@ -728,6 +746,7 @@ gilt.
 
 \newpage
 \section{Transformation von Sortiernetzwerken}
 
 \newpage
 \section{Transformation von Sortiernetzwerken}

+\label{sect:tranformation}

 
 \subsection{Komprimieren}
 
 
 \subsection{Komprimieren}