Neues Zitat: Knuth.

[diplomarbeit.git] / diplomarbeit.tex

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index dfa31d9..9c316c4 100644 (file)
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -208,7 +208,7 @@ Rekombination}). Unter Umständen wird die neue Lösung noch zufällig
 verändert {\em (Mutation)}, bevor sie in die bestehende Lösungsmenge
 integriert wird. Die Wahrscheinlichkeiten, beispielsweise bei der {\em
 Selektion}, sind dabei nicht zwangsläufig gleichverteilt -- üblicherweise
-werden bessere Lösungen bevorzugt. Zur Bewertung die die sogenannte {\em
+werden bessere Lösungen bevorzugt. Zur Bewertung dient die sogenannte {\em
 Gütefunktion}.
 
 Nicht alle Probleme eignen sich für diese Strategie: Zum einen muss es möglich
@@ -218,6 +218,26 @@ 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.
 
+Beim Aussuchen von zufälligen Lösungen aus der Population, der
+\emph{Selektion}, werden gute Lösungen bevorzugt. Wie sehr diese Lösungen
+bevorzugt werden, hat einen starken Einfluss auf das Verhalten des
+Algorithmus. Werden gute Lösungen stark bevorzugt, konvergiert der Algorithmus
+schnell gegen ein (lokales) Optimum. Dieses \textit{Exploitation} (Englisch
+für „Ausnutzung“) genannte Verhalten sorgt dafür, dass sich der Algorithmus
+schnell auf eine Lösung festlegt und andere, möglicherweise bessere lokale
+Optima nicht mehr findet. Werden gute Lösungen hingegen nur wenig bevorzugt,
+erforscht der Algorithmus den Lösungsraum in viele Richtungen. Dieses
+\textit{Exploration} (Englisch für „Erforschung“) genannte Verhalten sorgt
+zwar dafür, dass der Algorithmus langsamer auf ein Optimum zusteuert, dafür
+findet er aber in der Regel bessere Lösungen.
+
+Die Parameter evolutionärer Algorithmen so einzustellen, dass sich ein guter
+Mittelweg zwischen den beiden Extremen einstellt, ist eine Aufgabe, die sich
+nur experimentell lösen lässt. Die genauen Parameter hängen nicht nur vom
+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
@@ -226,6 +246,7 @@ Mutation \textit{(vermutlich)} nicht (effizient) möglich.
 
 \newpage
 \section{Bekannte konstruktive Sortiernetzwerke}
+\label{sect:konstruktive_netzwerke}
 
 Übersicht über bekannte konstruktive Sortiernetzwerke.
 
@@ -447,8 +468,7 @@ Elementen zu einer sortierten Ausgabefolge mit $N = n+m$~Elementen
 zusammenfügen kann. Dabei kommt es mit weniger Vergleichen aus als der
 \emph{bitone Mischer}, der im Abschnitt~\ref{sect:der_bitone_mischer}
 vorgestellt wurde. Allerdings benötigt der \emph{Odd-Even-Mischer} unter
-Umständen mehr Schichten als der \emph{bitone Mischer}.\footnote{Knuth,
-“Bitonic Sorting”, Seite~230}
+Umständen mehr Schichten als der \emph{bitone Mischer}.~\cite{KNUTH}
 
 Der \emph{Odd-Even-Mischer} selbst ist ebenfalls rekursiv aufgebaut: Die
 Eingabe für den Mischer mit $N = n + m$ Leitungen besteht aus den beiden