\emph{Schichten}, in die sich ein Sortiernetzwerk unterteilen lässt.
Diese Anzahl ist insbesondere beim automatisierten Bewerten von
-Komparatornetzwerken interessant, wie in Abschnitt~\ref{sect:bewertung}
+Komparatornetzwerken interessant, wie in Abschnitt~\ref{sect:sn-evolution:bewertung}
beschrieben. Die Anzahl der Schichten kann künstlich vergrößert werden, indem
Komparatoren später angewendet werden. Deshalb sollte vor einer Bewertung, die
die Anzahl der Schichten als Bewertungskriterium verwendet, immer eine
(Abschnitt~\ref{sect:konstruktive_netzwerke}) und Schnittmuster
(Abschnitt~\ref{sect:leitungen_entfernen}) verwendet, um „möglichst gute“
Sortiernetzwerke zu erzeugen. Was ein „gutes“ Sortiernetzwerk ausmacht, wird
-in Abschnitt~\ref{sect:bewertung} behandelt.
+in Abschnitt~\ref{sect:sn-evolution:bewertung} behandelt. Informationen zur Implementierung
+von \textsc{SN-Evolution} befinden sich in
+Abschnitt~\ref{sect:implementierung}.
-\subsection{Bewertungsfunktion}\label{sect:bewertung}
+\subsection{Bewertungsfunktion}\label{sect:sn-evolution:bewertung}
Um Sortiernetzwerke überhaupt optimieren zu können, muss zunächst die
{\em Güte} eines Netzwerks definiert werden. Prinzipiell gibt es zwei Ziele,
16-Sortiernetzwerk besteht aus 61~Komparatoren in nur 9~Schichten und ist in
Abbildung~\ref{fig:16-voorhis} zu sehen.
-Eine Gütefunktion, die die beiden Ziele "`effizient"' und "`schnell"'
-berücksichtigen kann, hat die folgende allgemeine Form:
+\textsc{SN-Evolution} verwendet eine Gütefunktion, die die beiden Ziele
+"`effizient"' und "`schnell"' berücksichtigen kann. Sie hat die folgende
+generelle Form:
\begin{equation}
\operatorname{Guete}(S) = w_{\mathrm{Basis}}
+ w_{\mathrm{Komparatoren}} \cdot \left|S\right|_\mathrm{Komparatoren}
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 Finden (lokaler) Optima, bevorzugt.
+Exploitation}, das Streben zu (lokalen) Optima, verstärkt.
Diese Parameter haben einen großen Einfluss auf die Geschwindigkeit, mit der
der \textsc{SN-Evolution}-Algorithmus konvergiert und ob er tatsächlich gute
Als guter Standardansatz für \textsc{SN-Evolution} haben sich die folgenden
Werte herausgestellt:
\begin{eqnarray*}
-w_{\mathrm{Basis}} &=& 0 \\
-w_{\mathrm{Komparatoren}} &=& 1 \\
-w_{\mathrm{Schichten}} &=& \left|S\right|_\mathrm{Leitungen}
+ w_{\mathrm{Basis}} &=& 0 \\
+ w_{\mathrm{Komparatoren}} &=& 1 \\
+ w_{\mathrm{Schichten}} &=& \left|S\right|_\mathrm{Leitungen}
\end{eqnarray*}
+Sofern nicht anders angegeben, werden diese Werte im Folgenden zur Bewertung
+von Sortiernetzwerken verwendet. Die Bewertungsfunktion bevorzugt mit diesen
+Konstanten \emph{schnelle} Sortiernetzwerke, da das Einsparen einer Schicht
+ein höheres Gewicht als das Einsparen von Komparatoren hat.
+
+Wenn der \textsc{SN-Evolution}-Algorithmus nach \emph{effizienten}
+Sortiernetzwerken suchen soll, werden alternative Werte für die Konstanten der
+Bewertungsfunktion verwendet. Die Werte
+\begin{eqnarray*}
+ w_{\mathrm{Basis}} &=& 0 \\
+ w_{\mathrm{Komparatoren}} &=& 2 \\
+ 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?}
\subsection{Selektion}
Algorithmus, der zu einem gegebenen Sortiernetzwerk und einer gewünschten
Leitungszahl ein Schnittmuster sucht, dass ein Sortiernetzwerk mit einer
möglichst geringen Anzahl von Komparatoren und Schichten ergibt. Zur Bewertung
-von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}.
+von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:sn-evolution:bewertung}.
Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet \emph{Schnittmuster}, die
in Abschnitt~\ref{sect:anzahl_schnittmuster} definiert wurden, als Individuen.
projects / diplomarbeit.git / blobdiff