From 400ed37639a4d958fe07ccc3858554599bc99c2d Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Sat, 19 Feb 2011 18:24:44 +0100 Subject: [PATCH] Abschnitt "Ausblick": Erste Version. --- diplomarbeit.tex | 57 ++++++++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 53 insertions(+), 4 deletions(-) diff --git a/diplomarbeit.tex b/diplomarbeit.tex index c090c39..cdcba09 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -1773,10 +1773,59 @@ gib Netzwerk zurück \newpage \section{Ausblick} -Das würde mir noch einfallen$\ldots$ - -- SN-Evolution mit Pairwise als „Mischer“. -- Co-Evolution von Netzwerken und Schnittmustern. +Die Möglichkeiten, die Evolutionäre Algorithmen bei der Optimierung von +Sortiernetzwerken bieten, sind durch die in dieser Arbeit vorgestellten +Herangehensweisen bei weitem nicht erschöpft. + +Im Folgenden werden Ansätze umrissen, mit denen an die Untersuchungen in +dieser Arbeit nahtlos angeknöpft werden könnte. + +\subsection{Verwendung des Pairwise-Sorting-Netzwerk in \textsc{SN-Evolution}} + +Die aktuelle Implementierung von \textsc{SN-Evolution} +(Abschnitt~\ref{sect:sn-evolution}) kann sowohl den \emph{bitonen Mischer} als +auch den \emph{Odd-Even-Mischer} verwenden, um zwei Individuen zu +rekombinieren. Das \emph{Pairwise-Sorting}-Netzwerk verwendet zwar keinen +Mischer, es ist aber ebenfalls rekursiv über kleinere Versionen von sich +selbst definiert. Das heißt, dass \ps{n} aus zwei Instanzen von +$\ps{\frac{n}{2}}$ und zusätzlichen Komparatoren besteht, die die Eingabe für +die kleineren Sortiernetzwerke vorbereiten und anschließend für eine sortierte +Ausgaben sorgen. Anstelle von $\ps{\frac{n}{2}}$ kann man natürlich beliebige +Sortiernetzwerke mit $\frac{n}{2}$~Leitungen verwenden. + +Dies ließe sich für \textsc{SN-Evolution} nutzen, um zwei Individuen zu +rekombinieren. Da es für das \emph{Pairwise-Sorting}-Netzwerk sehr viele +\emph{unterscheidliche} Schnittmuster gibt +(Abbschnitt~\ref{sect:anzahl_schnittmuster}), ist es möglich, dass die +Verwendung dieser Rekombinationsmethode neue Ergebnisse ermöglicht. Leider +wird die Aussicht auf Erfolg durch die Tatsache geschmälert, dass keine +$n$-Schnittmuster für \ps{2n} gefunden werden konnten, die zu besseren +$n$-Sortiernetzwerken als \ps{n} führen. + +\subsection{Kooperation von \textsc{SN-Evolution} und +\textsc{SN-Evolution-Cut}} + +Ähnlich zu der parasitären \emph{Co-Evolution}, die \textit{W.~Daniel Hillis} +in~\cite{H1992} beschreibt, könnte man die Algorithmen \textsc{SN-Evolution} +und \textsc{SN-Evolution-Cut} versuchen zu kombinieren. Nach dem Zusammenfügen +von zwei $n$-Sortiernetzwerken könnte der Algorithmus +\textsc{SN-Evolution-Cut} beispielsweise einen möglichst guten Schnitt für +\emph{dieses} Netzwerk ermitteln. Da sich die Lösungen, die Evolutionäre +Algorithmen in ihre Population aufnehmen, in den ersten Schritten rasch +verbessern, könnten selbst weniger Iterationen von \textsc{SN-Evolution-Cut} +die Zwischenlösungen von \textsc{SN-Evolution} deutlich verbessern. + +Alternativ könnte man -- analog zur Herangehensweise von \textit{Hillis} -- +eine zweite Population von Schnittmustern evolvieren, die für die +Sortiernetzwerke in der Population von \textsc{SN-Evolution} besonders gut +funktionieren. In jeder Iteration wendet man alle oder eine zufällige Menge +Schnittmuster auf das zusammengeführte Netzwerk an und gibt dem besten +Ergebnis den Zuschlag. Anschließend erfährt das entsprechende Schnittmuster +eine Aufwertung, so dass es wahrscheinlicher wird, dass \emph{dieses} +Schnittmuster zur nächten Generation beiträgt. Im Gegensatz zum Ansatz der +parasitären Eingaben entsteht eine \emph{Synergie} zweier Populationen, die +das Gesamtergebnis oder zumindest die Konvergenzgeschwindigkeit verbessern +könnte. \newpage \section{Implementierung} -- 2.11.0