Die Größe eines Schnittmusters ist immer k.

[diplomarbeit.git] / diplomarbeit.tex

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index d590287..93e41f6 100644 (file)
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -435,7 +435,7 @@ ${n = 8}$ Leitungen.
   \begin{center}
     \input{images/oe-transposition-8.tex}
   \end{center}
-  \caption{Das \emph{Odd-Even-Transpositionsort}-Netzwerk mit acht Eingängen.}
+  \caption{Das \emph{Odd-Even-Transpositionsort}-Netzwerk mit 8~Eingängen.}
   \label{fig:odd-even-transposition-08}
 \end{figure}
 
@@ -598,10 +598,10 @@ alle Komparatoren in die gleiche Richtung zeigen.
   \begin{center}
   \input{images/batcher-8.tex}
   \end{center}
-  \caption{\bs{8}, Batchers \emph{bitones Mergesort}-Netzwerk für acht
-  Eingänge. Markiert sind die beiden Instanzen von \bs{4} (rot), die beiden
-  bitonen Mischer~\bm{4} (blau) und die Komparatoren, die im letzten
-  rekursiven Schritt hinzugefügt wurden (grün).}
+  \caption{\bs{8}, Batchers \emph{bitones Mergesort}-Netzwerk für 8~Eingänge.
+    Markiert sind die beiden Instanzen von \bs{4} (rot), die beiden bitonen
+    Mischer~\bm{4} (blau) und die Komparatoren, die im letzten rekursiven
+    Schritt hinzugefügt wurden (grün).}
   \label{fig:bitonic-08}
 \end{figure}
 
@@ -804,7 +804,7 @@ die als leere Komparatornetzwerke definiert sind.
   \begin{center}
   \input{images/oe-mergesort-8.tex}
   \end{center}
-  \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge. Markiert
+  \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für 8~Eingänge. Markiert
   sind die Instanzen von $\operatorname{OES}(4)$ (rot), die beiden
   \emph{Odd-Even}-Mischer $\operatorname{OEM}(4)$ für gerade und ungerade
   Leitungen (blau) und die im ersten Rekursionsschritt hinzugefügten
@@ -815,7 +815,7 @@ die als leere Komparatornetzwerke definiert sind.
 In Abbildung~\ref{fig:odd-even-mergesort-08} ist das \oes{8}-Sortiernetzwerk
 zu sehen. Rot markiert sind die beiden rekursiven Instanzen
 $\operatorname{OES}(4)$. Die anderen Blöcke stellen den
-\emph{Odd-Even}-Mischer für acht Leitungen dar: die beiden blauen Blöcke sind
+\emph{Odd-Even}-Mischer für 8~Leitungen dar: die beiden blauen Blöcke sind
 die rekursiven Instanzen von $\operatorname{OEM}(4)$, der grüne Block markiert
 die Komparatoren, die im ersten Rekursionsschritt hinzugefügt werden.
 
@@ -937,7 +937,7 @@ zu sortieren und die Ausgaben mit einem der beschriebenen Mischer
 zusammenfügen.
 
 Beispielsweise kann die Ausgabe von zwei \emph{bitonen Mergesort-Netzwerken}
-$\operatorname{BS}(8)$ mit je acht Leitungen mit dem
+$\operatorname{BS}(8)$ mit je 8~Leitungen mit dem
 \emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM(8,8)}$ zu einer sortierten
 Gesamtfolge zusammengefügt werden. Das resultierende Sortiernetzwerk besitzt
 73~Komparatoren (zum Vergleich: $\operatorname{BS}(16)$ benötigt
@@ -1313,17 +1313,20 @@ w_{\mathrm{Schichten}} &=& \left|S\right|_\mathrm{Leitungen}
 
 \subsection{Selektion}
 
-Die \emph{Selektion} sorgt dafür, dass bessere Individuen eine größere
-Wahrscheinlichkeit haben zur nächsten Generation beizutragen. Diese
-Ungleichbehandlung von Individuen verschiedener Güte ist der Grund für das
-Streben des Algorithmus nach besseren Lösungen.
+Als \emph{Selektion} wird der Vorgang bezeichnet, der zwei Individuen zufällig
+aus der Population auswählt. Sie werden im folgenden Schritt miteinander
+rekombiniert. Die Auswahl der Individuen erfolgt zufällig, aber nicht
+gleichverteilt. So sorgt die \emph{Selektion} dafür, dass bessere Individuen
+eine größere Wahrscheinlichkeit haben zur nächsten Generation beizutragen.
+Diese Ungleichbehandlung von Individuen verschiedener Güte ist der Grund für
+das Streben des Algorithmus nach besseren Lösungen.
 
 Obwohl dieser Vorteil für gute Individuen intuitiv als sehr gering erscheint,
-ist es sehr häufig, dass die \emph{Exploitation} überhand gewinnt und der
-Algorithmus vorschnell in Richtung eines lokalen Optimums optimiert.
+passiert es häufig, dass die Ausnutzung \emph{(Exploitation)} überhand gewinnt
+und der Algorithmus vorschnell in Richtung eines lokalen Optimums optimiert.
 
-Die in \textsc{SN-Evolution} implementierte Selektion lässt sich mithilfe von
-Pseudocode wie folgt beschreiben:
+Die in \textsc{SN-Evolution} implementierte Selektion eines Individuums lässt
+sich mit Pseudocode wie folgt beschreiben:
 \begin{verbatim}
   Gütesumme := 0
   Auswahl := (leer)
@@ -1342,6 +1345,10 @@ Pseudocode wie folgt beschreiben:
   gib Auswahl zurück
 \end{verbatim}
 
+Diese Auswahl wird zweimal ausgeführt, um zwei Individuen für die
+Rekombination zu erhalten. Das heißt, dass die Individuen bei
+\textsc{SN-Evolution} stochastisch unabhängig voneinander ausgewählt werden.
+
 \subsection{Rekombination}
 \label{sect:sn-evolution:rekombination}
 
@@ -1972,8 +1979,8 @@ Dass die Ergebnisse von \textsc{SN-Evolution-Cut} keine erkennbare Struktur
 haben, ist jedoch kein Eigenschaft des Algorithmus, sondern hängt insbesondere
 von der Eingabe ab. Wird \textsc{SN-Evolution-Cut} beispielsweise mit dem
 \emph{Odd-Even-Transpositionsort-Netzwerk} $\operatorname{OET}(n)$ und
-$m$~Schnitten gestartet, so ist das beste Ergebnis immer das
-$\operatorname{OET}(n-m)$-Netzwerk. 
+$k$~Schnitten gestartet, so ist das beste Ergebnis immer das
+$\operatorname{OET}(n-k)$-Netzwerk. 
 
 \subsection[Odd-Even-Mergesort-Netzwerk]{Versuche mit dem Odd-Even-Mergesort-Netzwerk}
 \label{sect:sn-evolution-cut:oes}