From: Florian Forster <octo@leeloo.octo.it>
Date: Fri, 28 Jan 2011 15:08:03 +0000 (+0100)
Subject: Evolutionäre Algorithmen: Etwas zur Mutation geschrieben.
X-Git-Url: https://git.octo.it/?p=diplomarbeit.git;a=commitdiff_plain;h=c3990a4c7e0ec6131411a275ee4b17457f9f995c

Evolutionäre Algorithmen: Etwas zur Mutation geschrieben.
---

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index 9a18aef..5af502f 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,6 +746,7 @@ gilt.
 
 \newpage
 \section{Transformation von Sortiernetzwerken}
+\label{sect:tranformation}
 
 \subsection{Komprimieren}