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
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{Transformation von Sortiernetzwerken}
+\label{sect:tranformation}
\subsection{Komprimieren}
{\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}}
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