Abbildung~\ref{fig:oe-transposition-cut0} zeigt den Weg eines Maximums durch
das \emph{Odd-Even-Transpositionsort}-Netzwerk.
+Im ersten Schritt wird eine Leitung ausgewählt und Maximum oder Minimum auf
+dieser Leitung angenommen. Dadurch ist der Weg durch das Sortiernetzwerk
+eindeutig festgelegt.
+
\begin{figure}
\centering
\subfigure[Auf der Leitung~4 wird $-\infty$ angelegt. Dadurch ist der Pfad
\caption{Eine Leitung wird aus dem
\emph{Odd-Even-Transpositionsort}-Netzwerk \oet{8} entfernt: Auf der rot
markierten Leitung wird $-\infty$ angelegt. Da der Wert bei jedem Komparator
- am unteren Ende herauskommt, ist der Pfad fest vorgegeben. Da die restlichen
- Werte trotzdem noch richtig sortiert werden müssen, kann dieser Pfad
- heraus getrennt werden. In der letzten Abbildung ist \oet{7} markiert.}
+ nach unten weiter gegeben wird, ist der Pfad fest vorgegeben. Da die
+ restlichen Werte trotzdem noch richtig sortiert werden müssen, kann dieser
+ Pfad heraus getrennt werden. In der letzten Abbildung ist \oet{7} markiert.}
\label{fig:oe-transposition-cut}
\end{figure}
-Im nächsten Schritt werden alle beteiligten Komparatoren gelöscht
+Im nächsten Schritt werden alle beteiligten Komparatoren gelöscht,
beziehungsweise ersetzt: Komparatoren, die {\em nicht} zu einem Wechsel der
Leitung geführt haben, werden ersatzlos gelöscht. Diese Komparatoren sind in
Abbildung~\ref{fig:oe-transposition-cut0} grün markiert. Die Komparatoren, die
zum Wechsel der Leitung geführt haben, werden durch sich kreuzende Leitungen
ersetzt. Das Resultat ist eine Leitung, auf der das Minimum beziehungsweise
das Maximum angenommen wird, die an unterster oder oberster Stelle endet und
-auf die keine Komparatoren mehr berührt
+die keine Komparatoren mehr berührt
(Abbildung~\ref{fig:oe-transposition-cut1}).
Die Werte auf den verbleibenden $(n-1)$~Leitungen müssen vom restlichen
-Komparatornetzwerk immer noch sortiert werden: Wir haben lediglich die
-Position des Minimums oder des Maximums angenommen. Ein Sortiernetzwerk muss
-die Eingabe sortieren, egal auf welcher Leitung das Minimum~/ das Maximum
-liegt. Wir haben nur angefangen, das Sortiernetzwerk unter diese Annahme
-auszuwerten -- über die verbleibenden Eingänge haben wir keine Aussage
+Komparatornetzwerk immer noch sortiert werden: Es wurde lediglich die
+\emph{Position} des Minimums oder des Maximums in der Eingabe angenommen. Ein
+Sortiernetzwerk muss die Eingabe sortieren, unabhängig davon auf welcher
+Leitung das Minimum oder das Maximum liegt. Das Sortiernetzwerk unter diese
+Annahme auszuwerten -- über die verbleibenden Eingänge wurde keine Aussage
getroffen. Entsprechend müssen die verbleibenden Ausgänge eine sortierte Liste
mit $(n-1)$~Elementen darstellen.
-Wenn man die Minimum- beziehungsweise Maximum-Leitung entfernt, wie in
+Wird die Minimum- beziehungsweise Maximum-Leitung entfernt, wie in
Abbildung~\ref{fig:oe-transposition-cut2} dargestellt, bleibt das
Sortiernetzwerk für $(n-1)$~Leitungen übrig. Je nachdem, ob auf einer Leitung
-ein Minimum oder ein Maximum angenommen wird, bezeichnen wir das eliminieren
-einer Leitung auf diese Art und Weise als \emph{Minimum-Schnitt}
-beziehungsweise \emph{Maximum-Schnitt}.
+ein Minimum oder ein Maximum angenommen wird, wird das eliminieren einer
+Leitung auf diese Art und Weise als \emph{Minimum-Schnitt}, beziehungsweise
+\emph{Maximum-Schnitt} bezeichnet.
Die letzte Abbildung, \ref{fig:oe-transposition-cut3}, zeigt das
Sortiernetzwerk wieder mit den üblichen geraden Leitungen und die rot
-markierten Komparatoren wurden verschoben, so dass sich eine kompaktere
+markierten Komparatoren sind verschoben, so dass sich eine kompaktere
Darstellung ergibt. Außerdem ist das
\emph{Odd-Even-Transpositionsort}-Netzwerk für sieben Werte markiert. Der
zusätzliche Komparator vor dem \oet{7} hat keinen Einfluss auf die Ausgabe und
Sortiernetzwerk mit $n$~Ein\-gängen Sortiernetzwerke mit $n-1$, $n-2$,
$n-3$,~\dots Eingängen zu erzeugen. Insbesondere können auf diese Art und
Weise Sortiernetzwerke mit $2n$~Eingängen auf Sortiernetzwerke mit
-$n$~Eingängen reduziert werden. $k$~Minimum- und Maximum-Schnitte, die
-nacheinander angewendet ein $n$-Sortiernetzwerk auf ein
-${(n-k)}$-Sortiernetz\-werk reduzieren, bezeichnen wir als
-\emph{$k$-Schnittmuster}.
+$n$~Eingängen reduziert werden. Als \emph{$k$-Schnittmuster} bezeichnet man
+die $k$~Minimum- und Maximum-Schnitte, die nacheinander angewendet ein
+$n$-Sortiernetzwerk auf ein ${(n-k)}$-Sortiernetz\-werk reduzieren.
Zwei Schnittmuster heißen \emph{äquivalent} bezüglich~$S$, wenn ihre Anwendung
auf das Sortiernetzwerk~$S$ das selbe Ergebnis liefert. Ansonsten heißen die
\quad (n > m)
\end{displaymath}
\emph{mögliche} Schnittmuster. Diese Schnittmuster sind nicht alle
-unterschiedlich. Legt man beispielsweise das Minimum auf die unterste Leitung
-und das Maximum auf die oberste Leitung eines Standard-Sortiernetzwerks,
-führen beide Reihenfolgen zum selben Ergebnis.
+unterschiedlich. Wird beispielsweise das Minimum auf der untersten Leitung
+und das Maximum auf der obersten Leitung eines Standard-Sortiernetzwerks
+angenommen, führen beide möglichen Schnitt-Reihenfolgen zum selben Ergebnis.
\textit{Moritz Mühlenthaler} zeigt in seiner Arbeit~\cite{M2009}, dass es
möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise Maximum
Netzwerke nicht oder nur unter erheblichem Ressourcenaufwand möglich.
Die Anzahl der \emph{unterschiedlichen} Schnittmuster ist allerdings kleiner
-als die Anzahl der möglichen Schnittmuster. Für jeden Komparator auf der
-ersten Stufe gibt es neun verschiedene Eingangskonfigurationen: Für beide
+als die Anzahl der \emph{möglichen} Schnittmuster. Für jeden Komparator auf
+der ersten Stufe gibt es neun verschiedene Eingangskonfigurationen: Für beide
Eingänge gibt es drei mögliche Eingangswerte, Minimum, Maximum und
unspezifiziert. Es gibt drei Konfigurationen, bei denen an beiden Eingängen
der gleiche Wert angelegt wird, und sechs Konfigurationen, bei denen sich die
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.
-Die Hashtabelle würde mehr Arbeitsspeicher benötigen als in derzeitigen
-Rechnern vorhanden ist, bevor ein entsprechender Graph den linearen Bereich
-für „kleine“ x-Werte verlässt.
+Experiment für größere Sortiernetzwerke nicht sinnvoll durchführbar. Die
+Hashtabelle würde mehr Arbeitsspeicher benötigen 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
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
+Lösungen findet oder sich in \emph{lokalen} Optima "`verfängt"'. Leider gibt
+es kein Patentrezept für die Wahl der Parameter, so dass für verschiedene
Leitungszahlen und Mischer-Typen experimentiert werden muss.
Als guter Standardansatz für \textsc{SN-Evolution} haben sich die folgenden
\label{sect:sn-evolution:rekombination}
Bei der Rekombination werden zwei Individuen --~hier Sortiernetzwerke~-- zu
-einer neuen Lösung kombiniert. Dazu verwenden wir einen Mischer, zum Beispiel
-den {\em bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) oder den
-\emph{Odd-Even}-Mischer (Abschnitt~\ref{sect:der_odd_even_mischer}), um die
-beiden Netzwerke zu einem Netzwerk mit $2n$~Leitungen zusammenzufügen.
-Anschließend werden zufällig $n$~Leitungen mit einem $n$-Schnittmuster wie in
-Abschnitt~\ref{sect:leitungen_entfernen} beschrieben entfernt.
+einer neuen Lösung kombiniert. Geeignete Mischer, um die beiden Netzwerke zu
+einem Netzwerk mit $2n$~Leitungen zusammenzufügen, sind zum Beispiel der {\em
+bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) und der
+\emph{Odd-Even}-Mischer (Abschnitt~\ref{sect:der_odd_even_mischer}),
+Anschließend werden $n$~Leitungen mit einem zufälligen $n$-Schnittmuster wie
+in Abschnitt~\ref{sect:leitungen_entfernen} beschrieben entfernt.
Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft
erhält. Entsprechend muss nicht aufwendig überprüft werden, ob das
projects / diplomarbeit.git / blobdiff