Abschnitt~\ref{sect:tranformation} beschrieben, ein Algorithmus, der Mutation
einsetzt, wird in Abschnitt~\ref{sect:sn-evolution-cut} vorgestellt.
+
+\begin{figure}
+ \begin{center}
+ \input{images/16-hillis.tex}
+ \end{center}
+ \caption{Das 16-Sortiernetzwerk, das \textit{Hillis} in~\cite{H1992} angibt.
+ Es besteht aus 61~Komparatoren in 11~Schichten.}
+ \label{fig:16-hillis}
+\end{figure}
+Evolutionäre Algorithmen wurden bereits mehrfach eingesetzt, um
+Sortiernetzwerke zu untersuchen. \textit{W.~Daniel Hillis} verwendete
+\emph{Co-Evolution} um neben Komparatornetzwerken auch „schwierige Eingaben“
+zu optimieren~\cite{H1992}. Diese \emph{Parasiten} genannten Eingaben wurden
+daran gemessen, bei wievielen Komparatornetzwerken sie beweisen konnten, dass
+sie keine Sortiernetzwerke sind. So mussten bei neuen Individuen~/
+Komparatornetzwerken nicht alle 0-1-Folgen, sondern nur erfolgreiche
+Parasiten~/ schwierige Eingaben überprüft werden. Auf diese Art und Weise
+gelang es \textit{Hillis} ein 16-Sortiernetzwerk mit 61~Komparatoren
+anzugeben, das in Abbildung~\ref{fig:16-hillis} zu sehen ist.
+
+\begin{figure}
+ \centering
+ \subfigure{\input{images/13-juille-0.tex}}
+ \subfigure{\input{images/13-juille-1.tex}}
+ \caption{13-Sortiernetzwerke, die von \textit{Hugues Juillé} mithilfe des
+ END-Algorithmus gefunden wurden. Sie bestehen jeweils aus 45~Komparatoren in
+ 10~Schichten.}
+ \label{fig:13-juille}
+\end{figure}
+\textit{Hugues Juillé} entwickelte ein Verfahren, das er \emph{Evolving
+Non-Determinism} (END) nannte. Dabei handelt es sich nicht um einen
+\emph{Evolutionären Algorithmus}, wie sie hier vorgestellt wurden, sondern um
+eine verteilte, probabilistische Breitensuche, die an die \emph{Strahlsuche}
+(englisch: \textit{beam search}), ein Verfahren der Künstlichen Intelligenz,
+angelehnt ist. Die aufwendigste Operation bei diesem Ansatz ist die
+Bewertungsfunktion, die abschätzt, wieviele Komparatoren zu einem
+Komparatornetzwerk hinzugefügt werden müssen, um ein Sortiernetzwerk zu
+erhalten. Mit diesem Ansatz gelang es \textit{Juillé} zwei 13-Sortiernetzwerke
+anzugeben, die mit 45~Komparatoren effizienter sind als alle bis dahin
+Bekannten (Abbildung~\ref{fig:13-juille}).
+
\newpage
\section{Bekannte konstruktive Sortiernetzwerke}
\label{sect:konstruktive_netzwerke}
Das würde mir noch einfallen$\ldots$
+- SN-Evolution mit Pairwise als „Mischer“.
+- Co-Evolution von Netzwerken und Schnittmustern.
+
\newpage
\section{Implementierung}
-So habe ich die ganzen Versuche durchgeführt.
+Alle in dieser Arbeit beschriebenen Versuche wurden mit einer eigens
+entwickelten C-Bibliothek, \textit{libsortnetwork}, und zugehörigen
+Kommandozeilen-Programmen durchgeführt. Die Bibliothek wurde unter der
+\textit{GNU Lesser General Public License} (LGPL) in der Version~2.1
+veröffentlicht; die Kommandozeilen-Programme, die in vielen Fällen lediglich
+Funktionalität der Bibliothek auf der Kommandozeile zur Verfügung stellen,
+stehen unter der \textit{GNU General Public License}, Version~2. Diese
+Lizenzen räumen einem Benutzer weitreichende Rechte ein, unter anderem das
+Programm beliebig zu verwenden, zu studieren, zu verändern sowie veränderte
+und unveränderte Kopien zu veröffentlichen.
+
+Die Programmierschnittstelle (API) der Bibliothek orientiert sich an
+Paradigmen der \textit{objektorientierten Programmierung}. Beispielsweise kann
+mit der Funktion \texttt{sn\_network\_ create()} ein neues Zustands-Objekt
+erzeugt werden, für das mehrere Manipulations-Methoden, zum Beispiel
+\texttt{sn\_network\_comparator\_add()}, zur Verfügung stehen. Auf diese Art
+und Weise kann die Bibliothek leicht erweitert werden, ohne dass bestehende
+Programme angepasst werden müssen.
+
+Die meisten Kommandozeilen-Programmen lesen ein Komparatornetzwerk von der
+Standard-Eingabe und schreiben ihr Ergebnis auf die Standard-Ausgabe. Um
+Beispielsweise eine \emph{normalisierte} Variante des \emph{bitonen
+Mergesort}-Netzwerks \bs{18} zu erzeugen, kann folgendes Kommando verwendet
+werden:
+\begin{verbatim}
+$ sn-bitonicsort 18 | sn-normalize >sn-18
+\end{verbatim}
+Dieses Prinzip, kleine Programme \emph{eine} Aufgabe erledigen zu lassen und
+es einfach zu ermöglichen, Programme zu verketten, ist eines der
+Grundprinzipien des UNIX-Be\-triebs\-sys\-tems. Es hat sich in den letzten
+Jahrzehnten und beim Verfassen dieser Arbeit als sehr flexibel und mächtig
+erwiesen.
+
+Funktionen, die von Kommandozeilen-Programmen zur Verfügung gestellt werden,
+sind unter anderem das Erzeugen von Odd-Even-Mergesort-, bitonic Mergesort-
+und Pairwise-Sorting-Netzwerken, das Normalisieren von Sortiernetzwerken,
+Anwendung von Schnittmustern auf Sortiernetzwerke und Anwendung eines
+Komparatornetzwerks auf eine Eingabe-Permutation.
+
+\textit{libsortnetwork} kann unter der Web-Adresse
+\url{http://octo.it/libsortnetwork/} unentgeldlich heruntergeladen werden.
\newpage
\bibliography{references}
projects / diplomarbeit.git / blobdiff