-- eine Zahl, die für aktuelle Prozessoren keine Herausforderung darstellt.
Für die Überprüfung eines Komparatornetzwerks mit 32~Leitungen sind jedoch
bereits etwa 4,3~Milliarden Tests notwendig, die einen Rechner durchaus
-mehrere Minuten beschäftigen. Das ist deshalb problematisch, weil die im
+mehrere Stunden beschäftigen. Das ist deshalb problematisch, weil die im
Folgenden vorgestellten \emph{Evolutionären Algorithmen} eine entsprechende
Überprüfung in jeder Iteration durchführen müssten. Wenn die Überprüfung eines
-Zwischenergebnisses fünf Minuten in Anspruch nimmt, sind für eine Million
-Iterationen fast zehn Jahre Rechenzeit notwendig. Selbst wenn die Berechnung
-auf 1000~Computern mit je 4~Prozessoren verteilt wird, werden über 20~Stunden
-für einen Lauf benötigt.
+Zwischenergebnisses drei Stunden in Anspruch nimmt, sind für eine Million
+Iterationen etwa 340~Jahre Rechenzeit notwendig. Selbst wenn die Berechnung
+auf 1000~Computern mit je 4~Prozessoren verteilt wird, wird etwa ein Monat für
+einen Lauf benötigt.
\subsubsection{Evolutionäre Algorithmen}
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.
+findet er aber in der Regel bessere Lösungen. Die Rolle, die
+\textit{Exploitation} und \textit{Exploration} bei evolutionären
+Optimierungsalgorithmen spielen, wird von \textit{Eiben} und
+\textit{Schippers} in~\cite{ES1998} untersucht.
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.
+zwischen verschiedenen Leitungszahlen stark unterscheiden. Einen Überblick
+geben \textit{Kalyanmoy Deb} und \textit{Samir Agrawal} in~\cite{DA1998}.
Die Erforschung (\textit{Exploration}) kann von einem weiteren Mechanismus
unterstützt werden, der ebenfalls der Evolutionslehre entliehen ist, der
\end{displaymath}
gilt.
-% gnuplot:
-% oem(n,m) = ((n*m) <= 1) ? (n*m) : oem(ceil(.5*n), ceil(.5*m)) + oem(floor(.5*n), floor(.5*m)) + floor(.5*(n+m-1.0))
-% oem1(n) = oem(ceil(.5*n),floor(.5*n))
-% oes(n) = (n <= 1.0) ? 0 : oes(ceil(0.5*n)) + oes(floor(0.5*n)) + oem1(n)
-
-%\begin{itemize}
-%\item Pairwise sorting-network
-%\end{itemize}
-
-\subsection{Das Pairwise-Sorting-Netzwerk}
-
-Das \emph{Pairwise-Sorting}-Netzwerk \ps{n} ist eine Konstruktionsvorschrift
-für Sortiernetzwerke, die 1992 von \textit{Ian Parberry} in seiner Arbeit „The
-Pairwise Sorting Network“ \cite{P1992} definiert wurde. Wenn die Anzahl der
-Leitungen $n = 2^d$ eine Zweierpotenz ist, hat das
-\emph{Pairwise-Sorting}-Netzwerk die selbe Effizienz und Geschwindigkeit wie
-das \emph{Odd-Even-Mergesort}-Netzwerk.
+%\subsection{Das Pairwise-Sorting-Netzwerk}
+%
+%Das \emph{Pairwise-Sorting}-Netzwerk \ps{n} ist eine Konstruktionsvorschrift
+%für Sortiernetzwerke, die 1992 von \textit{Ian Parberry} in seiner Arbeit „The
+%Pairwise Sorting Network“ \cite{P1992} definiert wurde. Wenn die Anzahl der
+%Leitungen $n = 2^d$ eine Zweierpotenz ist, hat das
+%\emph{Pairwise-Sorting}-Netzwerk die selbe Effizienz und Geschwindigkeit wie
+%das \emph{Odd-Even-Mergesort}-Netzwerk.
\newpage
\section{Transformation von Sortiernetzwerken}
\begin{figure}
\centering
- \subfigure[16-Sortiernetzwerk aus 60~Komparatoren in 10~Schichten. Das Netzwerk wurde von \textit{M.~W. Green} konstruiert und 1969 in \todo{Referenz} veröffentlicht.]{\input{images/16-green.tex}\label{fig:16-green}}
- \subfigure[16-Sortiernetzwerk aus 61~Komparatoren in 9~Schichten. Das Netzwerk wurde von \textit{D. Van~Voorhis} veröffentlicht.]{\input{images/16-voorhis.tex}\label{fig:16-voorhis}}
+ \subfigure[16-Sortiernetzwerk aus 60~Komparatoren in 10~Schichten. Das
+ Netzwerk wurde von \textit{M.~W. Green} konstruiert und 1969 in~\cite{G1972}
+ veröffentlicht.]{\input{images/16-green.tex}\label{fig:16-green}}
+ \subfigure[16-Sortiernetzwerk aus 61~Komparatoren in 9~Schichten. Das
+ Netzwerk wurde von \textit{D. Van~Voorhis} 1974 in~\cite{V1974}
+ veröffentlicht.]{\input{images/16-voorhis.tex}\label{fig:16-voorhis}}
\caption{Das effizienteste und das schnellste Sortiernetzwerk für
16~Leitungen, das derzeit bekannt ist.}
\label{fig:16-best-known}
gesamten Lösungsraums, begünstigt. Wählt man $w_{\mathrm{Basis}}$ hingegen
klein -- in Abhängigkeit von den anderen beiden Parametern sind auch negative
Werte möglich -- werden die relativen Unterschiede groß. Dadurch wird die {\em
-Exploitation}, das Streben zu (lokalen) Optima, verstärkt.
+Exploitation}, das Streben zu (lokalen) Optima, verstärkt. In~\cite{WW2002}
+geben \textit{Karsten und Nicole Weicker} einen Überblick über
+Selektionsmethoden und Rekombinationsmöglichkeiten.
Diese Parameter haben einen großen Einfluss auf die Geschwindigkeit, mit der
der \textsc{SN-Evolution}-Algorithmus konvergiert und ob er tatsächlich gute
w_{\mathrm{Schichten}} &=& 1
\end{eqnarray*}
geben dem Einsparen eines Komparators ein höheres Gewicht als dem Einsparen
-einer Schicht. \todo{Fehler hier noch was?}
+einer Schicht.
\subsection{Selektion}