From c63d86b41a8f1d63bdad0dfdc79d3bdf4d790dfd Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Sun, 27 Feb 2011 11:35:32 +0100 Subject: [PATCH] SN-Evolution, Bewertungsfunktion: Verbesserungen. --- diplomarbeit.tex | 28 ++++++++++++++++++++++------ 1 file changed, 22 insertions(+), 6 deletions(-) diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 27be82a..d5c84bc 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -1279,8 +1279,9 @@ Abbildung~\ref{fig:16-green} dargestellt. Das \emph{schnellste} bekannte 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} @@ -1305,7 +1306,7 @@ verschiedener Netzwerke kleiner, was die {\em Exploration}, das Absuchen des 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 @@ -1316,10 +1317,25 @@ Leitungszahlen und Mischer-Typen experimentiert werden muss. 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} -- 2.11.0