1 \documentclass[a4paper,11pt]{article}
2 \usepackage[utf8]{inputenc}
6 \usepackage{amsmath, bbm}
12 %\usepackage{longtable}
13 \usepackage{subfigure}
17 \usetikzlibrary{arrows,shapes}
20 \usepackage{mathtools}
22 \geometry{paper=a4paper,margin=30mm}
26 %\fancyhead[LO,LE]{"Ubung zu Computational Intelligence}
27 %\fancyhead[CO,CE]{2006-05-15}
28 %\fancyhead[RO,RE]{Florian Forster (2099894)}
30 \title{Evolutionäre Optimierung von Sortiernetzwerken}
31 \author{Florian Forster}
34 \newcommand{\false}{\textsc{False}}
35 \newcommand{\true}{\textsc{True}}
36 \newcommand{\todo}[1]{{\bf TODO:} #1}
37 \newcommand{\qed}{\hfill $\Box$ \par \bigskip}
39 \newtheorem{definition}{Definition}
40 \newtheorem{satz}{Satz}
42 % Zeige Nummern nur bei referenzierten Gleichungen an.
43 \mathtoolsset{showonlyrefs=true}
47 \tikzstyle{vertex} = [circle,draw,thick,fill=black,minimum size=5,inner sep=0pt]
48 \tikzstyle{comp} = [draw,thick,-]
49 \tikzstyle{compup} = [draw,thick,->]
50 \tikzstyle{compdown} = [draw,thick,<-]
51 \tikzstyle{edge} = [draw,thick,-]
52 \tikzstyle{diredge} = [draw,thick,->]
53 \tikzstyle{prob} = [font=\tiny]
55 \tikzstyle{edge minimum} = [edge,color=blue!20]
56 \tikzstyle{edge maximum} = [edge,color=red!20]
57 \tikzstyle{vertex active minimum} = [vertex,color=blue!50, fill=blue!50]
58 \tikzstyle{vertex active maximum} = [vertex,color=red!50, fill=red!50]
59 \tikzstyle{vertex active minimum maximum} = [vertex,color=violet!50, fill=violet!50]
60 \tikzstyle{vertex inactive minimum} = [vertex,color=blue!20, fill=blue!20]
61 \tikzstyle{vertex inactive maximum} = [vertex,color=red!20, fill=red!20]
62 \tikzstyle{vertex inactive minimum maximum} = [vertex,color=black!20, fill=black!20]
63 \tikzstyle{comp active minimum} = [comp]
64 \tikzstyle{comp active maximum} = [comp]
65 \tikzstyle{comp active minimum maximum} = [comp,color=black!20]
66 \tikzstyle{comp inactive minimum} = [comp,color=blue!20]
67 \tikzstyle{comp inactive maximum} = [comp,color=red!20]
68 \tikzstyle{comp inactive minimum maximum} = [comp,color=black!20]
70 \tikzstyle{red box} = [draw,-,color=red, top color=red!2,bottom color=red!10]
71 \tikzstyle{blue box} = [draw,-,color=blue,top color=blue!2,bottom color=blue!10]
72 \tikzstyle{green box} = [draw,-,color=teal,top color=teal!2,bottom color=teal!10]
73 \tikzstyle{gray box} = [draw,-,color=black, top color=black!2,bottom color=black!10]
77 Sortiernetzwerke werden eingeführt und einige bekannte Konstruktionen werden
78 vorgestellt (Off-Even-Transposition, Bitonic-Merge, Odd-Even-Merge, Pairwise).
79 Transformationsmöglichkeiten für Sortiernetzwerke werden besprochen.
80 Evolutionäre Algorithmen werden beschrieben und ein evolutionärer
81 Algorithmus für die Optimierung von Sortiernetzwerken wird angegeben.
82 Die mindestens von diesem Algorithmus erreichte Güte wird angegeben und die
83 Transformation zu einer Markov-Kette wird gezeigt. {\em Natürlich: So fern ich
84 das hinbekomme bzw. Recht behalte.}
91 \section{Motivation und Einleitung}
93 \subsection{Motivation}\label{sect:motivation}
96 \item Sortiernetzwerke sind toll, weil $\ldots$
97 \item Sortiernetzwerke sind einfach erklärt, aber trotzdem kompliziert.
98 \item Bisher noch kein evolutionärer Algorithmus zur automatischen
99 Optimierung von Sortiernetzwerken bekannt. \textit{(Glaube ich zumindest.)}
102 \subsection{Einleitung}\label{sect:einleitung}
104 \subsubsection{Sortiernetzwerke}\label{sect:einleitung_sortiernetzwerke}
106 {\em Komparatoren} sind die Bausteine, die {\em Sortiernetzwerken} zugrunde
107 liegen. Sie haben zwei Eingänge über die sie zwei Zahlen erhalten können.
108 Ausserdem besitzt ein {\em Komparator} zwei Ausgänge, die im Gegensatz zu den
109 Eingängen unterscheidbar sind: Die grö"sere der beiden Zahlen wird immer auf
110 dem einen, die kleinere der beiden Zahlen immer auf dem anderen Ausgang
113 Wenn man nun mehrere {\em Komparatoren} miteinander kombiniert, also die
114 Ausgänge von Komparatoren mit dem Eingängen anderer Komparatoren verbindet,
115 erhält man ein {\em Komparatornetzwerk}.
119 \input{images/einfaches_komparatornetzwerk.tex}
121 \caption{Einfaches Komparatornetzwerk mit vier Ein- bzw. Ausgängen, bestehend
123 \label{fig:einfaches_komparatornetzwerk}
126 Abbildung~\ref{fig:einfaches_komparatornetzwerk} zeigt ein einfaches
127 Komparatornetzwerk aus fünf Komparatoren in der üblichen Darstellungsweise:
128 Die horizontalen Linien stellen Leitungen von den Eingängen auf der linken
129 Seite zu den Ausgängen auf er rechten Seite dar. Die vertikalen Pfeile
130 symbolisieren die Komparatoren, die die Werte "`auf den Leitungen"'
131 vergleichen und ggf. vertauschen. Nach einem Komparator befindet sich die
132 kleinere Zahl immer auf der Leitung, auf die der Pfeil zeigt, die größere Zahl
133 befindet sich auf der Leitung auf der der Pfeil seinen Ursprung hat.
135 Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
136 gleichzeitig angewandt werden. Das Beispiel in
137 Abbildung~\ref{fig:einfaches_komparatornetzwerk} verwendet diesen Umstand und
138 vergleicht in einem ersten Schritt die zwei oberen und die zwei unteren
139 Leitungen gleichzeitig. Eine Gruppe von Komparatoren, die gleichzeitig
140 angewendet werden können, nennt man eine \emph{Schicht} des
141 Komparatornetwerks. Die \emph{Verzögerung} eines Komparatornetzwerks ist
142 gleichbedeutend mit der Anzahl der Schichten, in die sich die Komparatoren
143 mindestens gruppieren lassen, da sie die Anzahl der benötigten parallelen
146 Komparatornetzwerke, die für jede beliebige Eingabepermutation eine
147 Ausgabe erzeugen, die der Sortierung der Eingabe entspricht, heißen
148 {\em Sortiernetzwerke}. Das in
149 Abbildung~\ref{fig:einfaches_komparatornetzwerk} gezeigte Komparatornetzwerk
150 ist kein Sotiernetzwerk: Die Eingabefolge ${(1, 2, 3, 4)}$ würde zur Ausgabe
151 ${(2, 1, 3, 4)}$ führen -- die bestehenden Sortierung wird also sogar
154 Zu beweisen, dass ein gegebenes Komparatornetzwerk die Sortiereigenschaft
155 {\em nicht} hat, ist mit einem gegebenen Gegenbeispiel einfach möglich.
156 Dieses Gegenbeispiel zu finden ist allerdings aufwendig.
158 \todo{Wie findet man die Gegenbeispiele? Die {\em Entscheidung}, ob ein
159 Netzwerk sortiert, ist doch NP-vollständig, also müsste doch das Finden eines
160 Gegenbeispiels im Allgemeinen auch exponentialle Laufzeit haben..?}
161 \todo{Wenn die {\em Entscheidung}, ob ein Netzwerk sortiert, NP-vollständig
162 ist, müsse man dann nicht einen Zeugen für die Sortiereigenschaft angeben
167 Um zu überprüfen, ob ein gegebenes Komparatornetzwerk die Sortiereigenschaft
168 besetzt, müssen nicht alle $n!$ Permutationen von $n$~unterschiedlichen Zahlen
169 ausprobieren. Stattdessen reicht es zu überprüfen, dass das Netzwerk alle
170 $2^n$~0-1-Folgen sortiert.
174 \item Ein Komparator-Netzwerk ist $\ldots$
175 \item Ein Komparator-Netzwerk ist ein Sortiernetzwerk, wenn $\ldots$
176 \item Die Frage nach der Sortiereigenschaft ist NP-vollständig.
179 \subsubsection{Evolutionäre Algorithmen}
181 Viele {\em kombinatorische Optimierungsprobleme} sind schwer zu lösen -- die
182 entsprechenden Entscheidungsprobleme liegen oft in der Komplexitätsklasse
183 $NP$, sind also mit bekannten Verfahren nicht effizient exakt lösbar. Sollte
184 sich herausstellen, dass diese Probleme nicht in der Komplexitätsklasse $P$
185 liegen, wäre eine Konsequenz, dass es effiziente exakte Algorithmen für diese
186 Probleme nicht geben kann. Falls sich hingegen herausstellt, dass diese
187 Probleme in der Komplexitätsklasse~$P$ liegen, wird es mit großer
188 Wahrscheinlichkeit noch einige Zeit dauern bis auch Algorithmen mit
189 praktikablen Zeitkonstanten gefunden werden.
191 Aus diesem Grund besteht die Notwendigkeit einen Kompromiss einzugehen: Statt
192 die bzw. eine der {\em optimalen} Lösungen als einzige Ausgabe des Algorithmus
193 zuzulassen, wird eine "`möglichst gute"' Lösung ausgegeben. Viele dieser
194 Optimierungsalgorithmen orientieren sich an Vorgängen in der Natur,
195 beispielsweise immitieren die "`Ameisenalgorithmen"' das Verhalten von Ameisen
196 auf der Futtersuche um kurze Rundreisen auf Graphen zu berechnen.
198 Bei {\em Evolutionären Algorithmen} stand die Evolution pate. Die Grundidee
199 ist es, bestehende Lösungen zu neuen, unter Umständen besseren Lösungen zu
200 kombinieren. Dabei bedient man sich der in der Evolutionstheorie etablierten
201 Nomenklatur, beispielsweise werden konkrete Lösungen für ein Problem häufig
202 als {\em Individuum} bezeichnet.
204 Die Vorgehensweise lässt sich abstrakt wie folgt beschreiben. Aus einer
205 bestehenden Lösungsmenge, der {\em Population} werden zufällig Lösungen
206 ausgesucht {\em (Selektion)} und zu einer neuen Lösung kombiniert ({\em
207 Rekombination}). Unter Umständen wird die neue Lösung noch zufällig
208 verändert {\em (Mutation)}, bevor sie in die bestehende Lösungsmenge
209 integriert wird. Die Wahrscheinlichkeiten, beispielsweise bei der {\em
210 Selektion}, sind dabei nicht zwangsläufig gleichverteilt -- üblicherweise
211 werden bessere Lösungen bevorzugt. Zur Bewertung die die sogenannte {\em
214 Nicht alle Probleme eignen sich für diese Strategie: Zum einen muss es möglich
215 sein, eine initiale Population zur Verfügung zu stellen, da diese als Basis
216 aller weiteren Operationen dient. Das ist häufig keine große Einschränkung, da
217 es oft einfach ist {\em irgendeine} Lösung anzugeben. Zum anderen muss eine
218 Methode für die Rekombination existieren. Das insbesondere dann problematisch
219 wenn {\em Nebenbedingungen} eingehalten werden müssen.
222 \item Unter einem "`Evolutionären Algorithmus"' versteht man $\ldots$
223 \item Da die Sortiereigenschaft zu überprüfen NP-schwer ist, ist die
224 Mutation \textit{(vermutlich)} nicht (effizient) möglich.
228 \section{Bekannte konstruktive Sortiernetzwerke}
230 Übersicht über bekannte konstruktive Sortiernetzwerke.
232 \subsection{Das Odd-Even-Transpositionsort-Netzwerk}
233 \label{sect:odd_even_transpositionsort}
235 Das Sortiernetzwerk {\em Odd-Even-Transpositionsort} (OET) ist eines der
236 einfachsten Sortiernetzwerke. Es besteht aus $n$~{\em Schichten}, die jede
237 "`Leitung"' abwechselnd mit den benachbarten Leitungen verbindet.
238 Abbildung~\ref{fig:odd-even-transposition-08} zeigt das OET-Netzwerk für
243 \input{images/oe-transposition-8.tex}
245 \caption{Das \emph{Odd-Even-Transpositionsort}-Netzwerk mit acht Eingängen.}
246 \label{fig:odd-even-transposition-08}
249 Dass das Odd-Even-Transporitionsort-Netzwerk tatsächlich jede beliegibe
250 Eingabe sortiert ist nicht offensichtlich. Leicht zu sehen ist jedoch, dass
251 sowohl das Minimum als auch das Maximum durch das im Netzwerk enthaltene
252 Treppenmuster auf die unterste beziehungsweise oberste Leitung gelangt. Beim
253 Odd-Even-Transporitionsort-Netzwerk mit drei Eingängen,
254 $\operatorname{OET}(3)$, ist die Ausgabe folglich sortiert.
256 Die Sortiereigenschaft größerer OET-Netzwerke lässt sich rekursiv beweisen,
257 indem man $\operatorname{OET}(n)$ auf $\operatorname{OET}(n-1)$ durch
258 Herausschneiden einer Leitung reduziert. In
259 Abschnitt~\ref{sect:leitungen_entfernen} wird das Vorgehen im Detail
260 beschrieben, Abbildung~\ref{fig:oe-transposition-cut} zeigt das
261 Herausschneiden einer Leitung aus $\operatorname{OET}(8)$.
263 Das Odd-Even-Transporitionsort-Netzwerk ist weder in Bezug auf die Anzahl der
264 Komparatoren noch in Bezug auf die Anzahl der Schichten, in denen sich die
265 Komparatoren anordnen lassen, effizient. Es benötigt
266 ${\frac12 n (n-1)} = \mathcal{O}(n^2)$~Komparatoren, die in $n$~Schichten
267 angeordnet sind. Andere Sortiernetzwerke benötigen deutlich weniger
268 Komparatoren, beispielsweise $\mathcal{O}(n (\log n)^2)$, die in weniger
269 Schichten, zum Beispiel $\mathcal{O}(\log n)$, angeordnet sind.
271 Das Interessante am OET-Netzwerk ist seine einfache Konstruktion. Einige der
272 folgenden Algorithmen benötigen ein (einfaches) Sortiernetzwerk als
273 Starteingabe, auf dessen Basis sie versuchen optimierte Sortiernetzwerke zu
274 finden. Häufig dient $\operatorname{OET}(n)$ als Eingabe für diese
277 \subsection{Das bitone Mergesort-Netzwerk}
279 Das \emph{bitone Mergesort}-Netzwerk ($\operatorname{BS}(n)$) ist ein
280 Sortiernetzwerk, das 1968 von \emph{Kenneth~E. Batcher} in~\cite{B1968}
281 veröffentlicht wurde. Es ist deutlich effizienter als das
282 Odd-Even-Transporitionsort-Netzwerk -- sowohl in Bezug auf die Anzahl der
283 Komparatoren als auch bezüglich der benötigten Zeit, also der Anzahl der
286 Das Sortiernetzwerk basiert auf einem Komparatornetzwerk, welches zwei
287 sortierte Listen zusammenfügen (englisch: \textit{to~merge}) kann. Dieser
288 \emph{„bitoner Mischer“} (englisch: \textit{bitonic merger}) genannte Baustein
289 verleiht dem Sortiernetzwerk seinen Namen.
291 Da das Sortiernetzwerk rekursiv definiert ist, betrachten wir hier nur die
292 Instanzen des Netzwerks, deren Leitungszahl eine Zweierpotenz ist,
293 $\operatorname{BS}(n = 2^t)$.
295 \subsubsection{Der bitone Mischer}\label{sect:der_bitone_mischer}
297 Das \emph{bitone Mergesort-Netzwerk} basiert auf dem sogenannten \emph{bitonen
298 Mischer} $\operatorname{BM}(n)$, einem Kom\-parator-Netzwerk, das eine beliebige
299 \emph{bitone Folge} in eine sortierte Listen umordnen kann. Eine \emph{bitone
300 Folge} ist eine monoton steigende Folge gefolgt von einer monoton absteigenden
301 Folge, oder ein zyklischer Shift davon. Abbildung~\ref{fig:beispiel-biton}
302 zeigt die vier prinzipiellen Möglichkeiten die durch zyklische Shifts
303 entstehen können. Die wichtigsten Varianten für das \emph{bitone
304 Mergesort-Netzwerk} zeigen die Abbildungen~\ref{fig:beispiel-biton-0}
305 und~\ref{fig:beispiel-biton-1}. Sie erhält man, wenn man eine aufsteigend und
306 eine absteigend sortierte Liste aneinanderhängt. Bei den anderen beiden Formen
307 ist wichtig zu beachten, dass das letzte Element nicht größer
308 (Abbildung~\ref{fig:beispiel-biton-2}) bzw. kleiner
309 (Abbildung~\ref{fig:beispiel-biton-3}) als das erste Element der Folge sein
314 \subfigure[aufsteigend, absteigend]{\input{images/beispiel-biton-0.tex}\label{fig:beispiel-biton-0}}
315 \subfigure[absteigend, aufsteigend]{\input{images/beispiel-biton-1.tex}\label{fig:beispiel-biton-1}}
316 \subfigure[aufsteigend, absteigend, aufsteigend]{\input{images/beispiel-biton-2.tex}\label{fig:beispiel-biton-2}}
317 \subfigure[absteigend, aufsteigend, absteigend]{\input{images/beispiel-biton-3.tex}\label{fig:beispiel-biton-3}}
318 \caption{Beispiele bitoner Folgen.}
319 \label{fig:beispiel-biton}
324 \subfigure[normal]{\input{images/bitonic-merge.tex}\label{fig:bitonic-merge-normal}}
326 \subfigure[trichter]{\input{images/bitonic-merge-trichter.tex}\label{fig:bitonic-merge-tricheter}}
327 \caption{Schematischer Aufbau des bitonen Mischers: Jedes Element der
328 aufsteigenden Folge $u_0, u_1, \ldots$ wird mit dem entsprechenden Element
329 der absteigend sortierten Folge $v_0, v_1, \ldots$ verglichen. Die beiden
330 resultierenden Teilfolgen sind wiederum biton.}
331 \label{fig:bitonic-merge-schema}
334 Der Mischer funktioniert folgendermaßen: Gegeben sind zwei Folgen mit je
335 ${m = \frac{n}{2}}$ Elementen, $U = \left(u_0, u_1, \ldots, u_{m-1}\right)$ und
336 $V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die Folge $U$ sei aufsteigend
337 sortiert, die Folge $V$ sei absteigend sortiert:
339 u_0 \leqq u_1 \leqq &\ldots& \leqq u_{m-1} \\
340 v_0 \geqq v_1 \geqq &\ldots& \geqq v_{m-1}
342 Im ersten Schritt werden nun jeweils die Elemente an den gleichen relativen
343 Positionen verglichen und ggf. vertauscht:
345 u_i \longleftrightarrow v_i, \quad 0 \leqq i < m
347 Sei $j \in \{0 \ldots m\}$ der Index der ersten Elemente $u_j$ und $v_j$, die
348 durch den gemeinsamen Komparator vertauscht werden. Unter der Annahme, dass
349 Elemente nur vertauscht werden wenn, sie ungleich sind, muss ${u_j > v_j}$
350 gelten. Mit $u_j \leqq u_{j+1}$ und $v_j \geqq v_{j+1}$ folgt daraus $u_{j+1}
351 > v_{j+1}$. Es werden also alle Elemente $u_k$ und $v_k$ mit $k \geqq j$
352 vertauscht. $j = m$ bezeichnet den Fall, in dem das größte Element der
353 "`linken"' Folge, $u_{m-1}$, kleiner ist als das kleinste Element der
354 "`rechten"' Folge, $v_{m-1}$. Daraus folgt, dass das Resultat in zwei bitone
355 Folgen aufteilen lässt: Eine aufsteigende~/ absteigende Folge und eine
356 absteigende~/ aufsteigende Folge. Abbildung~\ref{fig:bitonic-merge-normal}
357 zeigt die Situationen vor und nach diesem Schritt des Mischers.
359 Um die Folge vollständig zu sortieren, müssen anschließend die beiden
360 resultierenden bitonen Folgen sortiert werden. Die geschieht ebenfalls
361 mithilfe des bitonen Mischers, mit zwei Instanzen von
362 $\operatorname{BM}(\frac{n}{2})$. Diese rekursive Definition endet mit dem
363 bitonen Mischer mit zwei Leitungen, $\operatorname{BM}(2)$, der als
364 Komparator-Netzwerk mit einem Komparator zwischen den beiden Leitungen
367 Der bitonen Mischer kann auch zwei aufsteigende Folgen sortieren. Dazu ist
368 lediglich eine etwas modifizierte Vergleichs-Kaskade im ersten Schritt
369 notwendig. Die folgenden, kleineren Mischer erhalten als Eingabe wieder eine
370 „echte“ bitone Folge. Abbildung~\ref{fig:bitonic-merge-tricheter} zeigt das
371 Schema des bitonen Mischers für zwei aufsteigend sortierte Foglen. Durch das
372 Umdrehen einer Folge verändert sich das Muster der Komparatoren ein wenig:
373 Statt an eine Treppe erinnert das Muster nun an einen Trichter.
375 Da sich die Anzahl der Leitungen in jedem Rekursionsschritt halbiert, endet
376 die Rekursion nach $\log(n)$~Schritten. In jedem Rekursionsschritt werden
377 $\frac{n}{2}$~Komparatoren eingefügt, so dass der gesamte Mischer aus
378 $\frac{1}{2} n \log(n) = \mathcal{O}\left(n \log(n)\right)$~Komparatoren
379 besteht, die in $\log(n)$~Schichten angeordnet werden können.
381 \subsubsection{Das bitone Mergesort-Netzwerk}
383 Ebenso wie der bitone Mischer $\operatorname{BM}(n)$ ist auch das \emph{bitone
384 Mergesort-Netzwerk} $\operatorname{BS}(n)$ rekursiv definiert. Es setzt sich
385 zusammen aus zwei Instanzen des bitonen Mergesort-Netzwerks halber Größe,
386 $\operatorname{BS}(\frac{n}{2})$, für je die Hälfte der Eingänge, sowie dem
387 bitonen Mischer für $n$~Leitungen, $\operatorname{BM}(n)$. Das Rekursionsende
388 ist das bitone Mergesort-Netzwerk mit nur einer Leitung,
389 $\operatorname{BS}(1)$, welches als leeres Komparatornetzwerk definiert ist.
390 Entsprechend sind die Komparatornetzwerke $\operatorname{BM}(2)$ und
391 $\operatorname{BS}(2)$ identisch.
393 Bei der Konstruktion kommt die trichterförmige Anordnung der Komparatoren
394 (Abbildung~\ref{fig:bitonic-merge-tricheter}) gelegen, weil so die beiden
395 rekursiven Sortiernetzwerke in die gleiche Richtung sortieren können und so
396 alle Komparatoren in die gleiche Richtung zeigen.
400 \input{images/batcher-8.tex}
402 \caption{$\operatorname{BS}(8)$, Batchers {\em bitones Mergesort-Netzwerk}
403 für acht Eingänge. Markiert sind die beiden Instanzen von
404 $\operatorname{BS}(4)$ (rot), die beiden bitonen
405 Mischer~$\operatorname{BM}(4)$ (blau) und die Komparatoren, die im letzten
406 rekursiven Schritt hinzugefügt wurden (grün).}
407 \label{fig:bitonic-08}
410 Das konkrete Netzwerk~$\operatorname{BS}(8)$ ist in
411 Abbildung~\ref{fig:bitonic-08} zu sehen. Eingezeichnet sind ebenfalls die
412 beiden Instanzen des Netzwerks~$\operatorname{BS}(4)$ (rot) sowie der bitone
413 Mischer~$\operatorname{BM}(8)$ (blau). Die trichterförmige Komparator-Kaskade,
414 die die bitone Eingabefolge in zwei bitone Ausgabefolgen transformiert, ist
417 Das \emph{bitone Mergesort-Netzwerk} $\operatorname{BS}(8)$ besteht aus
418 $\frac{1}{4} n \log(n) \log(n+1) = \mathcal{O}\left(n (log (n))^2\right)$
419 Komparatoren, die in $\frac{1}{2} \log(n) \log(n+1) = \mathcal{O}(\log(n))$
420 Schichten angeordnet sind.
424 %\includegraphics[viewport=115 491 372 782,width=7.5cm]{images/sn-rekursiver-aufbau.pdf}
426 %\caption{Rekursiver Aufbau von $S(n)$: Es besteht aus zwei Instanzen von
427 %$S(n/2)$ und dem Mischer $M(n)$.}
428 %\label{fig:bms_rekursiver_aufbau}
431 \subsection{Das Odd-Even-Mergesort-Netzwerk}
433 Obwohl der Name ähnlich klingt, haben das \emph{Odd-Even-Mergesort-Netzwerk}
434 (OES) und das \emph{Odd-Even-Transpositionsort-Netzwerk} (siehe
435 Abschnitt~\ref{sect:odd_even_transpositionsort}) wenig gemein. Vielmehr ist
436 OES dem \emph{bitonen Mergesort-Netzwerk}, das im vorherigen Abschnitt
437 vorgestellt wurde, ähnlich: Auch dieses Sortiernetzwerk ist von
438 \textit{Kenneth~E. Batcher} gefunden worden und ist ebenfalls in~\cite{B1968}
439 beschrieben und initial analysiert worden. Eine weitere Gemeinsamkeit besteht
440 darin, dass es ebenfalls rekursiv durch einen Mischer definiert ist.
442 \subsubsection{Der Odd-Even-Mischer}\label{sect:der_odd_even_mischer}
444 Der \emph{Odd-Even-Mischer} $\operatorname{OEM}(n,m)$ ist ein
445 Komperatornetzwerk, dass zwei sortierte Folgen mit $n$ beziehungsweise $m$
446 Elementen zu einer sortierten Ausgabefolge mit $N = n+m$~Elementen
447 zusammenfügen kann. Dabei kommt es mit weniger Vergleichen aus als der
448 \emph{bitone Mischer}, der im Abschnitt~\ref{sect:der_bitone_mischer}
449 vorgestellt wurde. Allerdings benötigt der \emph{Odd-Even-Mischer} unter
450 Umständen mehr Schichten als der \emph{bitone Mischer}.\footnote{Knuth,
451 “Bitonic Sorting”, Seite~230}
453 Der \emph{Odd-Even-Mischer} selbst ist ebenfalls rekursiv aufgebaut: Die
454 Eingabe für den Mischer mit $N = n + m$ Leitungen besteht aus den beiden
455 sortierten Folgen $U = \left(u_0, u_1, \ldots, u_{n-1}\right)$ und
456 $V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die gesamte Eingabe sei
457 $W = \left(w_0, w_1, \ldots, w_{N-1}\right)$ mit:
459 w_i = \left\{ \begin{array}{ll}
468 \input{images/oe-merge.tex}
470 \caption{Schematischer Aufbau des {\em Odd-Even} Mischers. Im Vergleich zum
471 bitonen Mischer für Acht kommt dieses Schema mit einem Komparator weniger
472 aus. Der Effekt wird duch den rekursiven Aufbau noch verstärkt.}
476 Diese werden in insgesamt vier sortierte Folgen aufgeteilt, je eine Liste der
477 geraden Indizes und je eine Liste der ungeraden Indizes.
479 U_{\textrm{gerade}} &=& \left(u_0, u_2, u_4, \ldots\right) \\
480 U_{\textrm{ungerade}} &=& \left(u_1, u_3, u_5, \ldots\right) \\
481 V_{\textrm{gerade}} &=& \left(v_0, v_2, u_4, \ldots\right) \\
482 V_{\textrm{ungerade}} &=& \left(v_1, v_3, u_5, \ldots\right)
485 Die geraden Folgen $U_{\textrm{gerade}}$ und $V_{\textrm{gerade}}$ bzw. die
486 ungeraden Folgen $U_{\textrm{ungerade}}$ und $V_{\textrm{ungerade}}$ werden
487 rekursiv von kleineren {\em Odd-Even-Mischern} zusammengefügt, so dass sich am
488 Ausgang der Mischer die Folgen
490 W_{\textrm{gerade}} &=& \left(w_0, w_2, w_4, \ldots\right) \\
491 W_{\textrm{ungerade}} &=& \left(w_1, w_3, w_5, \ldots\right)
495 Anschließend werden die Komparatoren zwischen benachbarten Leitungen
498 w_{2i-1} \longleftrightarrow w_{2i}, \quad 1 \leqq i < \frac{N}{2}
500 die die Folge~$W$ sortieren. Den schematischen Aufbau des {\em
501 Odd-Even-Mischers} zeigt Abbildung~\ref{fig:oe-merge}.
503 Leider bricht die Rekursion nicht so schön ab, wie das beim {\em bitonen
504 Mischer} der Fall gewesen ist. Insbesondere für ${n = m = 1}$ würde --
505 entsprechend der Konstruktionsvorschrift -- ein leeres Netzwerk entstehen, was
506 offensichtlich nicht korrekt wäre. Die Abbruchbedingungen für den rekursiven
509 \item Falls ${n = 0}$ oder ${m = 0}$: Das Netzwerk ist leer.
510 \item Falls ${n = 1}$ und ${m = 1}$: Das Netzwerk besteht aus einem
511 einzelnen Komparator.
514 Dass die resultierende Folge sortiert ist, lässt sich mit dem
515 {\em 0-1-Prinzip} zeigen:
516 Da $U$ und $V$ sortiert sind, ist die Anzahl der Nullen in den geraden
517 Teilfolgen, $U_{\textrm{gerade}}$ bzw. $V_{\textrm{gerade}}$, größer oder
518 gleich der Anzahl der Nullen in den ungeraden Teilfolgen
519 $U_{\textrm{ungerade}}$ bzw. $V_{\textrm{ungerade}}$ --~die Einsen verhalten
520 sich entsprechend umgekehrt. Das trifft demnach auch auf die Folgen
521 $W_{\textrm{gerade}}$ und $W_{\textrm{ungerade}}$ entsprechend zu:
523 \left|W_{\textrm{gerade}}\right|_0
524 &=& \left|U_{\textrm{gerade}}\right|_0
525 + \left|V_{\textrm{gerade}}\right|_0
526 = \left\lceil \frac{1}{2} \left|U\right|_0 \right\rceil
527 + \left\lceil \frac{1}{2} \left|V\right|_0 \right\rceil \\
528 \left|W_{\textrm{ungerade}}\right|_0
529 &=& \left|U_{\textrm{ungerade}}\right|_0
530 + \left|V_{\textrm{ungerade}}\right|_0
531 = \left\lfloor \frac{1}{2} \left|U\right|_0 \right\rfloor
532 + \left\lfloor \frac{1}{2} \left|V\right|_0 \right\rfloor
534 Daraus folgt, dass $W_{\textrm{gerade}}$ $0$, $1$ oder $2$ Nullen mehr enthält
535 als $W_{\textrm{ungerade}}$. In den ersten beiden Fällen ist die "`verzahnte"'
536 Ausgabe der beiden kleineren Mischer bereits sortiert. Nur im letzten Fall,
537 wenn $W_{\textrm{gerade}}$ zwei Nullen mehr enthählt als
538 $W_{\textrm{ungerade}}$, muss genau eine Vertauschung stattfinden, um die
539 Ausgabe zu sortieren. Diese wird von den Komparatoren, die benachbarte
540 Leitungen miteinander vergleichen, ausgeführt. Die jeweiligen Situationen sind
541 in Abbildung~\ref{fig:oe-post-recursive} dargestellt.
545 \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 0$]{\input{images/oe-post-recursive-diff0.tex}}
547 \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 1$]{\input{images/oe-post-recursive-diff1.tex}}
549 \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 2$]{\input{images/oe-post-recursive-diff2.tex}}
550 \caption{Die drei Situationen, die nach dem Verzahnen der Ausgaben der
551 kleineren {\em Odd-Even-Mischer} entstehen können. Ist die Differenz der
552 Anzahl der Nullen gleich $0$ oder $1$, ist die Folge bereits sortiert. Im
553 letzten Fall stellt einer der Komparatoren sicher, dass das Ergebnis
555 \label{fig:oe-post-recursive}
558 Da die Teilfolgen $U$ und $V$ in jedem Rekursionsschritt etwa halbiert werden,
559 bricht die Rekursion nach $\mathcal{O}\left(\log (n) + \log (m)\right)$
560 Schritten ab. Die exakte Anzahl der benötigten Rekursionsschritte (und damit
561 Schichten im Mischer-Netzwerk), hängt von der Längeren der beiden
562 Eingabefolgen ab und beträgt $1 + \lceil \log\left(\max(n, m)\right) \rceil$.
564 Die Anzahl der Komparatoren $K(n,m)$, die $\operatorname{OEM}(n,m)$ im
565 allgemeinen Fall verwendet, ist Gemäß der rekursiven Definition in
566 Abhängigkeit der Länge der Eingabefolgen, $n$ und $m$:
568 K(n,m) = \left\{ \begin{array}{ll}
569 nm, & \mathrm{falls} \quad nm \leqq 1 \\
570 K\left(\left\lceil \frac{n}{2} \right\rceil, \left\lceil \frac{m}{2} \right\rceil\right)
571 + K\left(\left\lfloor \frac{n}{2} \right\rfloor, \left\lfloor \frac{m}{2} \right\rfloor\right)
572 + \left\lfloor \frac{1}{2} (m + n - 1) \right\rfloor & \mathrm{falls} \quad nm > 1
575 Leider ist es schwierig, diese allgemeine Formel in einer geschlossenen Form
576 anzugeben. Aus der Anzahl der Rekursionsschritte ist jedoch leicht erkennbar,
577 dass $K(n,m)$ in $\mathcal{O}(N \log (N))$ enthalten ist.
579 Für den wichtigen Spezialfall, dass $n = m = 2^{t-1}$, lässt sich die Anzahl
580 der Komparatoren im Vergleich zum \emph{bitonen Mischer} angeben: Der erste
581 Rekursionsschritt der OEM-Konstruktion fügt
582 $\left\lfloor \frac{1}{2} (m + n - 1) \right\rfloor = \frac{N}{2} - 1$
583 Komparatoren ein -- einen Komparator weniger als der \emph{bitone Mischer} in
584 diesem Schritt. Das selbe gilt für die rekursiv verwendeten kleineren Mischer,
585 $\operatorname{OEM}(\frac{n}{2}, \frac{n}{2})$ und so weiter bis
586 einschließlich $\operatorname{OEM}(2, 2)$, von denen es $2, 4, \dots,
587 \frac{N}{4} = 2^{\log(N)-2}$ Instanzen gibt. Insgesamt werden
589 \sum_{i=0}^{\log(N)-2} 2^i = 2^{\log(N) - 1} - 1 = \frac{N}{2} - 1 = n - 1
591 Komparatoren eingespart. Damit ergibt sich
593 K\left(n = 2^{t-1}, n = 2^{t-1}\right) = \frac{1}{2} N \log(N) - \frac{N}{2} + 1
595 für die Anzahl der Komparatoren, die von $\operatorname{OEM}(N = 2^t)$
598 \subsubsection{Das Odd-Even-Mergesort-Netzwerk}
600 Das \emph{Odd-Even-Mergesort-Netzwerk} $\operatorname{OES}(n)$ besteht, --~wie
601 das \emph{bitonen Mergesort-Netzwerk}~-- rekursiv aus kleineren Varianten von
602 sich selbst und einem abschließenden \emph{Odd-Even-Mischer}. Die
603 effizientesten Sortiernetzwerke in Bezuf auf Komparator- und Schichtzahl
604 entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht
605 $\operatorname{OES}(n)$ aus
606 $\operatorname{OES}\left(\left\lceil\frac{n}{2}\right\rceil\right)$,
607 $\operatorname{OES}\left(\left\lfloor\frac{n}{2}\right\rfloor\right)$
608 und $\operatorname{OEM}\left(\left\lceil\frac{n}{2}\right\rceil,
609 \left\lfloor\frac{n}{2}\right\rfloor\right)$. Die Rekursion endet mit
610 $\operatorname{OES}(1)$ und $\operatorname{OES}(0)$, die als leere
611 Komparatornetzwerke definiert sind.
615 \input{images/oe-mergesort-8.tex}
617 \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge. Markiert
618 sind die Instanzen von $\operatorname{OES}(4)$ (rot), die beiden
619 \emph{Odd-Even-Mischer} $\operatorname{OEM}(4)$ für gerade und ungerade
620 Leitungen (blau) und die im ersten Rekursionsschritt hinzugefügten
621 Komparatoren zwischen benachbarten Leitungen (grün).}
622 \label{fig:odd-even-mergesort-08}
625 In Abbildung~\ref{fig:odd-even-mergesort-08} ist das konkrete Sortiernetzwerk
626 $\operatorname{OES}(8)$ zu sehen. Rot markiert sind die beiden rekursiven
627 Instanzen $\operatorname{OES}(4)$. Die blauen und der grüne Block stellen den
628 \emph{Odd-Even-Mischer} für acht Leitungen dar: Die beiden blauen Blöcke sind
629 die rekursiven Instanzen von $\operatorname{OEM}(4)$, der grüne Block markiert
630 die Komparatoren, die in ersten Rekursionsschritt hinzugefügt werden.
632 Im Allgemeinen ist die Anzahl der Komparatoren, die vom
633 \emph{Odd-Even-Mergesort-Netzwerk} verwendet wird, $k(n)$, direkt aus der
634 Definition beziehungsweise der Konstruktionsanleitung abzulesen:
636 k(n) = k\left(\left\lceil\frac{n}{2}\right\rceil\right)
637 + k\left(\left\lfloor\frac{n}{2}\right\rfloor\right)
638 + K\left(\left\lceil\frac{n}{2}\right\rceil, \left\lfloor\frac{n}{2}\right\rfloor\right)
640 Eine geschlossene Form dieser Formel ist schon alleine deshalb schwierig, weil
641 sie für $K(n,m)$ schwierig anzugeben ist. Es ist allerdings bekannt, dass
642 $k(n)$ in $\mathcal{O}\left(n \left(\log (n)\right)^2\right)$ enthalten ist.
644 Für den wichtigen Spezialfall, dass $n = 2^t$ eine Zweierpotenz ist, kann die
645 Anzahl der Komparatoren wieder explizit angegeben werden. \textit{K.~Batcher}
646 zeigt in seiner Arbeit\footnote{\todo{Referenz!}}, dass in diesem Fall
648 k(n = 2^t) = \frac{1}{4} n \left(\log (n)\right)^2 - \frac{1}{4}n\log(n) + n - 1
653 % 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))
654 % oem1(n) = oem(ceil(.5*n),floor(.5*n))
655 % oes(n) = (n <= 1.0) ? 0 : oes(ceil(0.5*n)) + oes(floor(0.5*n)) + oem1(n)
658 %\item Pairwise sorting-network
662 \section{Transformation von Sortiernetzwerken}
664 \subsection{Komprimieren}
666 \todo{Aus theoretischer Sicht eigentlich eine Trivialität. Rausschmeißen?}
668 Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
669 gleichzeitig ausgewertet werden, wie bereits in
670 Abschnitt~\ref{sect:einleitung_sortiernetzwerke} beschrieben. Unter
671 \emph{Komprimieren} wird eine (Neu-)Gruppierung in die kleinstmögliche Anzahl
672 von \emph{Schichten} verstanden.
674 Diese Anzahl ist insbesondere beim automatisierten Bewerten von
675 Komparatornetzwerken interessant. \dots
677 \subsection{Normalisieren}
681 \subfigure[$S(8)$ (nach Konstruktion)]{\input{images/batcher-8-nonstd.tex}\label{fig:bitonic-nonstd}}
682 \subfigure[$S(8)$ (normalisiert)]{\input{images/batcher-8-std.tex}\label{fig:bitonic-std}}
683 \caption{Jedes Sortiernetzwerk kann in ein Standard-Sortiernetzwerk
684 transformiert werden. Gezeigt ist das bitone Sortiernetzwerk nach der
685 intuitiven Konstruktion und die normalisierte Variante.}
686 \label{fig:beispiel_normalisieren}
689 Ein \emph{Standard-Sortiernetzwerk} oder \emph{normalisiertes Sortiernetzwerk}
690 ist ein Sortiernetzwerk, dessen Komparatoren alle in die selbe Richtung
691 zeigen. Jedes Sortiernetzwerk kann in eine normaliesierte Variante
692 transformiert werden. Dazu gibt beispielsweise \emph{Knuth} (\todo{Verweis})
693 einen Algorithmus an.
695 Abbildung~\ref{fig:beispiel_normalisieren} zeigt das das
696 bitone Sortiernetzwerk in zwei Varianten. Abbildung~\ref{fig:bitonic-nonstd}
697 zeigt das Netzwerk nach der Konstruktionsvorschrift, siehe auch
698 Abbildung~\ref{fig:bitonic-merge-normal}: In den ersten drei Schichten werden
699 die unter und die obere Hälfte gegenläufig sortiert. Das heißt dass nach drei
700 Schritten die eine Hälfte auf- und die andere Hälfte absteigend sortiert ist.
701 In den Schichten~4 bis~6 folgt der bitone Mischer entsprechend der rekursiven
704 In Abbildung~\ref{fig:bitonic-std} ist die normalisierte Version des bitonen
705 Mergesort-Netzwerks zu sehen. Alle Komparatoren zeigen hier in die gleiche
706 Richtung. Statt dem typischen "`Treppenmuster"' sind abwechselnd das Treppen-
707 und das Trichtermuster zu sehen.
709 \subsection{Zwei Netzwerke kombinieren}
711 Um Sortiernetzwerke als \emph{Individuen} evolutionärer Algorithmen verwenden
712 zu können, muss es möglich sein, zwei Sortiernetzwerke zu einem neuen
713 Sortiernetzwerk zusammenzufassen.
715 Wir haben diese Technik in den vorangegangen Abschnitten bereits verwendet,
716 beispielsweise um zwei \emph{bitone Mergesort-Netzwerke} mit jeweils der
717 halben Leitungszahl, $\operatorname{BS}\left(\frac{n}{2}\right)$, zu einem
718 einzigen Sortiernetzwerk $\operatorname{BS}(n)$ zu kombinieren. Auch das
719 \emph{Odd-Even-Mergesort-Netzwerk} $\operatorname{OES}(n)$ wurde auf diese Art
720 und Weise rekursiv aufgebaut.
722 Die vorgestellten \emph{Mischer} erwarten als Eingabe zwei bereits sortierte
723 Folgen. \emph{Wie} diese Folgen sortiert wurden, ist unerheblich. Entsprechend
724 können wir beliebige Sortiernetzwerke einsetzen, um die beiden Eingabefolgen
725 zu sortieren, und die Ausgaben mit einem der beschriebenen Mischer
728 Beispielsweise kann man die Ausgabe von zwei \emph{bitonen
729 Mergesort-Netzwerken} $\operatorname{BS}(8)$ mit je acht Leitungen mit dem
730 \emph{Odd-Even-Merge} $\operatorname{OEM(8,8)}$ zu einer sortierten
731 Gesamtfolge zusammenfügen. Das resultierende Sortiernetzwerk besitzt
732 73~Komparatoren (zum Vergleich: $\operatorname{BS}(16)$ benötigt
733 80~Komparatoren, $\operatorname{OES}(16)$ nur 63).
735 Verbesserungen in der Anzahl der benötigten Komparatoren beziehungsweise der
736 Schichten eines „kleinen“ Sortiernetzwerks übertragen sich direkt auf das
737 resultierende Gesamtnetzwerk. Das \emph{Odd-Even-Mergesort-Netzwerk}
738 $\operatorname{OES}(9)$ benötigt beispielsweise 26~Komparatoren, die in in
739 neun Schichten angeordnet sind. Es sind allerdings Sortiernetzwerke mit neun
740 Eingängen bekannt, die lediglich 25~Komparatoren in sieben Schichten
741 benötigen. Kombiniert man zwei dieser Netzwerke mit dem
742 \emph{Odd-Even-Mischer} erhält man ein Sortiernetzwerk mit 18~Eingängen, das
743 80~Komparatoren in 11~Schichten benötigt -- $\operatorname{OES}(18)$ benötigt
744 82~Komparatoren in 13~Schichten. Damit ist das resultierende Netzwerk so
745 schnell wie das Sortiernetzwerk mit 18~Eingängen, das \textit{Baddar} und
746 \textit{Batcher} in ihrer Arbeit „An 11-Step Sorting Network for 18~Elements“
747 vorstellen, benötigt aber 6~Komparatoren weniger.
761 Das Zusammenfassen von zwei Sortiernetzwerken durch Hintereinanderausführung
762 ist nicht sinnvoll: Da die Ausgabe des ersten Sortiernetzwerks bereits
763 sortiert ist, ist das zweite Sortiernetzwerk überflüssig. Eine
764 Aneinanderreihung der Art „die ersten $x$~Schichten des einen, dann die
765 letzten $y$~Schichten des anderen Sortiernetzwerks“ zerstören im Allgemeinen
766 die Sortiereigenschaft. Die Sortiereigenschaft des resultierenden
767 Komparatornetzwerks müsste überprüft werden, was nach heutigem Wissensstand
768 nur mit exponentiellem Aufwand möglich ist.
771 %\item Mit dem Bitonic-Merge
772 %\item Mit dem Odd-Even-Merge
773 %\item Nach dem Pairwise sorting-network Schema.
776 \subsection{Leitungen entfernen}\label{sect:leitungen_entfernen}
778 Im vorherigen Abschnitt haben wir gesehen, dass es mithilfe von
779 \emph{Mischern} möglich ist, aus zwei Sortiernetzwerken mit je $n$~Eingängen
780 ein neues Sortiernetzwerk mit $2n$~Eingängen zu erzeugen. Für einen
781 beabsichtigen \emph{evolutionären Algorithmus} ist es jedoch notwendig, dass
782 sich die Anzahl der Eingänge nicht verändert. Das heißt, dass wir wieder ein
783 Sortiernetzwerk mit $n$~Eingängen erhalten müssen.
785 Man kann ein gegebenes Sortiernetzwerk mit $n$~Eingängen auf ein
786 Sortiernetzwerk mit ${n-1}$~Leitungen verkleinern, indem man eine Leitung
787 „eliminiert“. Dazu nehmen wir an, dass das Minimum oder das Maximum an einem
788 bestimmten Eingang anliegt. Der Weg, den das Minimum beziehungsweise das Maxim
789 durch das Sortiernetzwerk nimmt, ist eindeutig bestimmt und endet an einem der
790 „Ränder“, also auf der Leitung mit dem höchsten oder dem niedrigsten Index.
791 Insbesondere ist bekannt, welche Komparatoren „berührt“ werden und welche
792 dafür sorgen, dass der Wert die Leitung gewechselt, da das Minimum jeden
793 Vergleich „verliert“ und das Maximum jeden Vergleich „gewinnt“. Die
794 Abbildung~\ref{fig:oe-transposition-cut0} zeigt den Weg eines Maximums durch
795 das {\em Odd-Even-Transpositionsort-Netzwerk}.
799 \subfigure[foo]{\input{images/oe-transposition-cut0.tex}\label{fig:oe-transposition-cut0}}
800 \subfigure[bar]{\input{images/oe-transposition-cut1.tex}\label{fig:oe-transposition-cut1}}
801 \subfigure[baz]{\input{images/oe-transposition-cut2.tex}\label{fig:oe-transposition-cut2}}
802 \subfigure[qux]{\input{images/oe-transposition-cut3.tex}\label{fig:oe-transposition-cut3}}
803 \caption{Eine Leitung wird aus dem
804 \emph{Odd-Even-Transpositionsort}-Netzwerk $\operatorname{OET}(8)$ entfernt:
805 Auf der rot markierten Leitung wird $\infty$ angelegt. Da der Wert bei jedem
806 Komparator am unteren Ende herauskommt, ist der Pfad fest vorgegeben. Da die
807 restlichen Werte trotzdem noch richtig sortiert werden müssen, kann dieser
808 Pfad herausgetrennt werden. In der letzten Abbildung ist
809 $\operatorname{OET}(7)$ markiert.}
810 \label{fig:oe-transposition-cut}
813 Im nächsten Schritt werden alle beteiligten Komparatoren gelöscht bzw.
814 ersetzt: Komparatoren, die {\em nicht} zu einem Wechsel der Leitung geführt
815 haben, werden ersatzlos gelöscht. Diese Komparatoren sind in
816 Abbildung~\ref{fig:oe-transposition-cut0} grün markiert. Die Komparatoren, die
817 zum Wechsel der Leitung geführt haben, werden durch sich kreuzende Leitungen
818 ersetzt. Das Resultat ist eine Leitung, auf der das Minimum beziehungsweise
819 das Maximum angenommen wird, die an unterster oder oberster Stelle endet und
820 auf die keine Komparatoren mehr berührt
821 (Abbildung~\ref{fig:oe-transposition-cut1}).
823 Die Werte auf den verbleibenden $(n-1)$~Leitungen müssen vom restlichen
824 Komparatornetzwerk immernoch sortiert werden: Wir haben lediglich die Position
825 des Minimums oder des Maximums angenommen. Ein Sortiernetzwerk muss die
826 Eingabe sortieren, egal auf welcher Leitung das Minimum~/ das Maximum liegt.
827 Wir haben lediglich angefangen, das Sortiernetzwerk unter diese Annahme
828 auszuwerten -- über die verbleibenden Eingänge haben wir keine Aussage
829 getroffen. Entsprechend müssen die verbleibenden Ausgänge eine sortierte Liste
830 mit $(n-1)$~Elementen darstellen.
832 Wenn wir die Minimum- beziehungsweise Maximum-Leitung entfernen
833 (Abbildung~\ref{fig:oe-transposition-cut2}), bleibt das Sortiernetzwerk für
834 $(n-1)$~Leitungen übrig. Je nachdem, ob auf einer Leitung ein Minimum oder ein
835 Maximum angenommen wird, bezeichnen wir das eliminieren einer Leitung als
836 \emph{Minimum-Schnitt} beziehungsweise \emph{Maximum-Schnitt}.
838 Die letzte Abbildung, \ref{fig:oe-transposition-cut3}, zeigt das
839 Sortiernetzwerk wieder mit den üblichen geraden Leitungen und die rot
840 markierten Komparatoren wurden verschoben, so dass sich eine kompaktere
841 Darstellung ergibt. Ausserdem ist das
842 {\em Odd-Even-Transpositionsort-Netzwerk} für sieben Werte markiert. Der
843 zusätzliche Komparator vor dem $\textrm{OET}(7)$ hat keinen Einfluss auf die
844 Ausgabe und kann entfernt werden.
846 \subsubsection{Anzahl möglicher und unterschiedlicher Schnittmuster}
847 \label{sect:anzahl_schnittmuster}
849 Der Eliminierungsschritt kann iterativ angewandt werden, um aus einem
850 Sortiernetzwerk mit $n$~Ein\-gängen Sortiernetzwerke mit $n-1$, $n-2$,
851 $n-3$,~\dots Eingängen zu erzeugen. Insbesondere können wir auf diese Art und
852 Weise einen Sortiernetzwerk mit $2n$~Eingängen wieder auf ein Sortiernetzwerk
853 mit $n$~Eingängen reduzieren. Das Anwenden mehrerer Minimum- und
854 Maximum-Schnitte bezeichnen wir als \emph{Schnittmuster}.
856 Zwei Schnittmuster heißen \emph{äquivalent} bezüglich~$S$, wenn ihre Anwendung
857 auf das Sortiernetzwerk~$S$ das selbe Ergebnis liefert. Ansonsten heißen die
858 Schnittmuster \emph{unterschiedlich} bezüglich~$S$.
860 Bei einem Sortiernetzwerk mit $n$~Eingängen gibt es $2n$~Möglichkeiten eine
861 Leitung zu entfernen: Auf jeder der $n$~Leitungen kann sowohl das Minimum als
862 auch das Maximum angenommen werden. Wendet man das Verfahren iterativ an, um
863 ein $n$-Sortiernetzwerk auf ein $m$-Sortiernetzwerk zu reduzieren, ergeben
866 \prod_{i=n}^{m+1} 2i = 2^{n-m} \frac{n!}{m!}
869 \emph{mögliche} Schnittmuster. Diese Schnittmuster sind nicht alle
870 unterschiedlich. Legt man beispielsweise das Minimum auf die unterste Leitung
871 und das Maximum auf die oberste Leitung eines Standard-Sortiernetzwerks,
872 führen beide Reihenfolgen zum selben Ergebnis.
874 \textit{Moritz Mühlenthaler} zeigt in seiner Arbeit (\todo{Referenz}), dass
875 es möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise
876 Maximum vorzubelegen. Dadurch wird die Anzahl der möglichen Schnittmuster
877 reduziert, die Menge der so erzeugbaren Sortiernetzwerke bleibt aber
878 unverändert. Die Anzahl der möglichen Schnittmuster setzt sich zusammen aus
879 der Anzahl von Möglichkeiten, $n-m$~Leitungen aus $n$ Leitungen auszuwählen,
880 und die möglichen Minimum-~/ Maximum-Muster. Damit ergibt sich folgende
881 Formel für die Anzahl der Schnittmuster:
883 2^{n-m} \cdot \left( \begin{array}{c} n \\ n-m \end{array} \right)
884 = 2^{n-m} \cdot \frac{n!}{(n-m)! m!}
885 = 2^{n-m} \cdot \frac{n!}{m!} \cdot \frac{1}{(n-m)!}
889 Die Anzahl der möglichen Schnittmuster wird mit der Anzahl der zu entfernenden
890 Leitungen sehr schnell sehr groß. Um ein Sortiernetzwerk mit 32~Eingängen auf
891 ein Sortiernetzwerk mit 16~Eingängen zu reduzieren, ist ein Schmittmuster mit
892 16~Schnitten notwendig, für das es bereits etwa ${3,939 \cdot 10^{13}}$
893 Möglichkeiten gibt. Ein Ausprobieren aller Möglichkeiten ist für große
894 Netzwerke nicht oder nur unter erheblichem Ressourcenaufwand möglich.
896 Die Anzahl der \emph{unterschiedlichen} Schnittmuster ist allerdings kleiner
897 als die Anzahl der möglichen Schnittmuster. Für jeden Komparator auf der
898 ersten Stufe gibt es neun verschiedene Eingangskonfigurationen: Für beide
899 Eingänge gibt es drei mögliche Eingangswerte, Minimum, Maximum und
900 unspezifiziert. Es gibt drei Konfigurationen, bei denen an beiden Eingängen
901 der gleiche Wert angelegt wird, und sechs Konfigurationen, bei denen sich die
904 Bei diesen letzten sechs Konfigurationen werden je zwei auf das selbe
905 Ausgangmuster abgebildet, weil die Position des Minimums beziehungsweise des
906 Maximums durch den Komparator vorgegeben wird. Das heißt, dass die neun
907 unterschiedlichen Eingangsmuster nur sechs unterschiedliche Ausgangsmuster
908 erzeugen. In der zweiten und allen folgenden Schichten kann man diesen
909 Unterschied nicht mehr erkennen. In allen sechs Fällen, in denen sich die
910 Eingänge unterscheiden, wird anschließend der Komparator entfernt, so dass
911 sich die Resultate auch in der ersten Schicht nicht unterscheiden.
913 \todo{Mit \textit{Approximate Counting} könnte man die Anzahl der
914 \emph{unterschiedlichen} Schnittmuster genauer abschätzen.}
917 \section{Der \textsc{SN-Evolution}-Algorithmus}
919 Um einen evolutionären Algorithmus für Sortiernetzwerke zu entwickeln, werden
920 die vorgestellten Methoden kombiniert.
922 \subsection{Bewertungsfunktion}\label{sect:bewertung}
924 Um Sortiernetzwerke überhaupt optimieren zu können, muss zunächst die
925 {\em Güte} eines Netzwerkes definiert werden. Prinzipiell gibt es zwei Ziele,
926 die interessant sind:
928 \item Möglichst wenige Komparatoren ("`klein"')
929 \item Möglichst wenige Schichten ("`schnell"')
932 Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das
933 kleinste bekannte Sortiernetzwerk für 16~Eingänge besteht aus 60~Komparatoren
934 in 10~Schichten. Das schnellste Netzwerk besteht aus 61~Komparatoren in nur
937 Eine Gütefunktion, die die beiden Ziele "`klein"' und "`schnell"'
938 berücksichtigen kann, hat die folgende allgemeine Form:
940 \operatorname{Guete}(S) = w_{\mathrm{Basis}}
941 + w_{\mathrm{Komparatoren}} \cdot \left|S\right|_\mathrm{Komparatoren}
942 + w_{\mathrm{Schichten}} \cdot \left|S\right|_\mathrm{Schichten}
944 Die Parameter $w_{\mathrm{Komparatoren}}$ und $w_{\mathrm{Schichten}}$ dienen
945 dabei der Festlegung des Optimierungsziels. Wenn einer der beiden Parameter
946 gleich Null ist, wird nur das jeweils andere Ziel verfolgt. Sind beide
947 Parameter gleich Null, werden alle Netzwerke mit der gleich Güte bewertet --
948 jegliche Ergebnisse sind dann rein zufälliger Natur.
950 Mit dem Parameter $w_{\mathrm{Basis}}$ kann auf die Selektion Einfluss
951 genommen werden. Ist er groß, wird der relative Unterschied der Güten
952 verschiedener Netzwerke kleiner, was die {\em Exploration}, das Absuchen des
953 gesamten Lösungsraums, begünstigt. Wählt man $w_{\mathrm{Basis}}$ hingegen
954 klein, in Abhängigkeit von den anderen beiden Parametern sind auch negative
955 Werte möglich, werden die relativen Unterschiede groß. Dadurch wird die {\em
956 Exploitation}, das Finden lokaler Optima, bevorzugt.
958 \subsection{Selektion}
962 \subsection{Rekombination}
964 Bei der Rekombination werden zwei Individuen --~hier Sortiernetzwerke~-- zu
965 einer neuen Lösung kombiniert. Dazu verwenden wir einen Mischer, zum Beispiel
966 den {\em bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) oder den
967 {\em Odd-Even-Mischer} (Abschnitt~\ref{sect:der_odd_even_mischer}), um die
968 beiden Netzwerke zu einem Netzwerk mit $2n$~Leitungen zusammenzufügen.
969 Anschließend entfernen wir zufällig $n$~Leitungen wie in
970 Abschnitt~\ref{sect:leitungen_entfernen} beschrieben.
972 Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft
975 \subsection{Mutation}
977 Zu einem vollständigen evolutionären Algorithmus gehört außerdem eine Mutation
978 --~eine zufällige Veränderung einer Lösung. Leider ist es nicht möglich ein
979 Sortiernetzwerk zufällig zu verändern aber trotzdem die Sortiereigenschaft zu
980 erhalten. Selbst das \emph{Hinzufügen} eines zufälligen Komparators kann diese
981 Eigenschaft zerstören.
983 Nach einer Mutation müsste man überprüfen, ob das neue Komparatornetzwerk die
984 Sortiereigenschaft noch besitzt. Nach heutigem Wissenstand ist diese
985 Überprüfung nur mit exponentiellem Aufwand möglich, etwa durch das
986 Ausprobieren aller $2^n$~Bitmuster.
988 Um das Potenzial einer Mutation abzuschätzen habe ich in den evolutionären
989 Algorithmus eine Überprüfung eingebaut. Unmittelbar vor dem Einfügen in die
990 Population überprüft das Programm die Notwendigkeit jedes einzelnen
991 Komparators. Dazu wurde nacheinander jeder Komparator entfernt und überprüft,
992 ob das verbleibende Netzwerk die Sortiereigenschaft noch besitzt.
995 \item Güte von Sortiernetzwerken (Anzahl der Komparatoren, Anzahl der
996 Schichten, kobiniert)
997 \item Rekombination: Merge Anhängen und Leitungen entfernen.
1000 Ein Beispielnetzwerk, das von dem Algorithmus gefunden wird, zeigt
1001 Abbildung~\ref{fig:evolutionary_08}.
1005 \input{images/evolutionary-08.tex}
1007 \caption{Ein mit dem evolutionären Algorithmus erzeugtes Sortiernetzwerk mit
1008 acht Eingängen. Es besteht aus 19~Komparatoren in 6~Schichten.}
1009 \label{fig:evolutionary_08}
1014 \input{images/08-e2-1237993371.tex}
1016 \caption{{\tt images/08-e2-1237993371.tex}: 19~Komparatoren in 6~Schichten}
1017 \label{fig:08-e2-1237993371}
1022 \input{images/09-e2-1237997073.tex}
1024 \caption{{\tt images/09-e2-1237997073.tex}: 25~Komparatoren in 8~Schichten}
1025 \label{fig:09-e2-1237997073}
1030 \input{images/09-e2-1237999719.tex}
1032 \caption{{\tt images/09-e2-1237999719.tex}: 25~Komparatoren in 7~Schichten}
1033 \label{fig:09-e2-1237999719}
1038 \input{images/10-e2-1239014566.tex}
1040 \caption{{\tt images/10-e2-1239014566.tex}: 29~Komparatoren in 8~Schichten}
1041 \label{fig:10-e2-1239014566}
1047 \item So gut kann man mindestens werden {\em ($\rightarrow$ Bitonic-Mergesort, vermute ich)}.
1048 \item Wie gut die Netzwerke werden, hängt stark vom verwendeten \em{Mischer} ab.
1049 \item Ggf. Abschnitt „Shmoo-Äquivalenz“ kürzen und hier einbauen.
1052 %\input{shmoo-aequivalenz.tex}
1055 \section{Der \textsc{SN-Evolution-Cut}-Algorithmus}
1056 \label{sect:sn-evolution-cut}
1058 Das Programm \textsc{SN-Evolution-Cut} implementiert einen evolutionären
1059 Algorithmus, der zu einem gegebenen Sortiernetzwerk und einer gewünschten
1060 Leitungszahl ein Schnittmuster sucht, dass ein Sortiernetzwerk mit einer
1061 möglichst geringen Anzahl von Komparatoren und Schichten ergibt. Zur Bewertung
1062 von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}. Mit diesem
1063 Algorithmus wurden zu einer Reihe von „interessanten“ Netzwerken möglichst
1064 gute Schnittmuster gesucht.
1066 Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet die \emph{Schnittmuster}
1067 als Individuen. Um zwei Individuen zu rekombinieren werden die ersten
1068 $r$~Schnitte des einen Schnittmusters verwendet und die letzten
1069 ${c-r}$~Schnitte des zweiten Schmittmusters. $r$ ist eine Zufallsvariable mit
1070 $0 \leqq r \leqq c$.
1072 Die Mutation setzt entweder die Leitungs-Nummer eines Schnitts~$i$ zufällig
1073 auf einen neuen Wert $l$ mit $0 \leqq l \le n-i$ oder invertiert die
1076 \subsection{Versuche mit dem bitonen Mergesort-Netzwerk}
1078 In \cite{MW2010} zeigen \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka},
1079 wie man einen bitonen Mischer, der nach Batchers Methode konstruiert wurde,
1080 durch systematisches Entfernen von Leitungen in einen ebenfalls bitonen
1081 Mischer mit der Hälfte der Leitungen transformiert. Diese alternativen Mischer
1082 sparen im Vergleich zu den Mischern, die nach Batchers Methode konstruiert
1083 werden, Komparatoren ein.
1085 Beispeilsweise geben \textit{Mühlenthaler} und \textit{Wanka} ein
1086 Sortiernetzwerk mit 16~Eingängen an, das mithilfe der alternativen Mischer
1087 konstruiert wurde. Dieses Sortiernetzwerk benötigt 68~Komparatoren, 12~weniger
1088 als das bitone Mergesort-Netzwerk nach Batchers Methode. Gegenüber Batchers
1089 Methode sparen so konstruierte Sortiernetzwerke ${\frac{1}{4}n(\log n - 1)}$
1094 \input{images/16-ec-from-bs32.tex}
1096 \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in
1097 10~Schichten. Das Netzwerk wurde von dem Algorithmus
1098 \textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort-Netzwerk}
1099 $\operatorname{BS}(32)$ durch 16~Schnitte erzeugt.}
1100 \label{fig:16-ec-from-bs32}
1105 \input{images/16-ec-from-bs32-normalized.tex}
1107 \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in
1108 10~Schichten. Das Netzwerk wurde von dem Algorithmus
1109 \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk
1110 $\operatorname{BS}(32)$ durch 16~Schnitte erzeugt.}
1111 \label{fig:16-ec-from-bs32-normalized}
1114 Startet man {\sc SN-Evolution-Cut} mit dem bitonen Mergesort-Netzwerk
1115 $\operatorname{BS}(32)$ und der Vorgabe 16~Leitungen zu entfernen, liefert der
1116 Algorithmus Sortiernetzwerke, die ebenfalls aus 68~Komparatoren bestehen. Ein
1117 16-Sortiernetzwerk, das auf diese Weise generiert wurde, ist in den
1118 Abbildungen~\ref{fig:16-ec-from-bs32} und~\ref{fig:16-ec-from-bs32-normalized}
1119 zu sehen. Abbildung~\ref{fig:16-ec-from-bs32} zeigt $\operatorname{BS}(32)$
1121 ${\operatorname{MIN}(0,5,9,11,15,17,20,22,26,29,30)}$-${\operatorname{MAX}(2,4,13,19,24)}$-Schnittmuster,
1122 das durch \textsc{SN-Evolution-Cut} gefunden wurde.
1123 Abbildung~\ref{fig:16-ec-from-bs32-normalized} zeigt das 16-Sortiernetzwerk
1124 nachdem das Schnittmuster angewandt und das Netzwerk normalisiert wurde. Eine
1125 Ähnlichkeit zu $\operatorname{BS}(32)$ oder $\operatorname{BS}(16)$ ist in
1126 diesem Netzwerk nicht mehr erkennbar -- insbesondere die ersten Schichten des
1127 Netzwerks scheinen rein zufällig zu sein.
1130 % 0:MAX 1:MAX 4:MIN 6:MAX 9:MAX 11:MAX 14:MIN 15:MAX 18:MAX 19:MAX 21:MAX
1131 % 23:MIN 24:MAX 25:MAX 30:MIN 31:MIN 32:MAX 34:MAX 36:MIN 37:MAX 40:MAX
1132 % 43:MAX 46:MIN 47:MAX 48:MAX 49:MAX 54:MIN 55:MAX 56:MAX 58:MIN 60:MAX
1135 \input{images/32-ec-from-bs64.tex}
1137 \caption{Sortiernetzwerk mit 32~Leitungen und 206~Komparatoren in
1138 15~Schichten. Das Netzwerk wurde von dem Algorithmus
1139 \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk
1140 $\operatorname{BS}(64)$ durch 32~Schnitte erzeugt. Das zugehörige
1142 $\operatorname{MIN}(4, 14, 23, 30, 31, 36, 46, 54, 58)$,
1143 $\operatorname{MAX}(0, 1, 6, 9, 11, 15, 18, 19, 21, 24, 25, 32, 34, 37,
1144 40, 43, 47, 48, 49, 55, 56, 60, 63)$.}
1145 \label{fig:32-ec-from-bs64}
1148 Das Ergebnis von \textit{Mühlenthaler} von \textit{Wanka}, die den bitonen
1149 Mischer optimiert und anschließend aus diesen Mischern ein Sortiernetzwerk
1150 konstruiert haben, kann demnach auch erreicht werden, wenn
1151 $\operatorname{BS}(32)$ auf ein 16-Sortiernetzwerk reduziert wird. Bei anderen
1152 Größen, beispielsweise wenn man $\operatorname{BS}(64)$ auf ein
1153 32-Sortiernetzwerk reduziert, kann das Ergebnis sogar noch übertroffen werden,
1154 wie in Abbildung~\ref{fig:32-ec-from-bs64} zu sehen: Ein nach Batchers Methode
1155 konstruiertes Sortiernetzwerk benötigt 240~Komparatoren, ein aus den
1156 optimierten Mischern aufgebautes Netzwerk verbessert die Kosten auf
1157 208~Komparatoren. Das in Abbildung~\ref{fig:32-ec-from-bs64} dargestellte
1158 Sortiernetzwerk benötigt lediglich 206~Komparatoren. Die Komparatoren aller
1159 dieser Netzwerke können in 15~Schichten angeordnet werden, so dass die
1160 Verzögerung dieser Sortiernetzwerke gleich ist.
1162 Leider sind die Schnittmuster, die \textsc{SN-Evolution-Cut} ausgibt, sehr
1163 unregelmäßig. Bisher ist es nicht gelungen eine Konstruktionsanweisung für
1164 gute Schnittmuster anzugeben.
1166 Entscheidend für das Ergebnis eines Schnittmusters scheint beim bitonen
1167 Mergesort-Netzwerk die Aufteilung der Minimum- und Maximumschnitte zu sein.
1168 Von Hundert 16-Schnittmustern für $\operatorname{BS}(32)$, die in
1169 Sortiernetzwerken mit 68~Komparatoren in 10~Schichten resultieren, hatten 73
1170 ein Verhältnis von $5/11$, 13 hatten ein Verhältnis von $4/12$ und 14 hatten
1171 ein Verhältnis von $3/13$ Minimum- beziehungsweise Maximumschnitten. Da sich
1172 die Schnittmuster aufgrund der Symmetrie des bitonen Mergesort-Netzwerks
1173 leicht invertieren lassen, werden der Fall, dass es mehr Minimumschnitte, und
1174 der Fall, dass es mehr Maximumschnitte gibt, nicht unterschieden.
1176 Dass die Ergebnisse von \textsc{SN-Evolution-Cut} keine erkennbare Struktur
1177 haben, ist jedoch kein Eigenschaft des Algorithmus, sondern hängt insbesondere
1178 von der Eingabe ab. Wird \textsc{SN-Evolution-Cut} beispielsweise mit dem
1179 \emph{Odd-Even-Transpositionsort-Netzwerk} $\operatorname{OET}(n)$ und
1180 $m$~Schnitten gestartet, so ist das beste Ergebnis immer das
1181 $\operatorname{OET}(n-m)$-Netzwerk.
1185 \input{images/16-ec-from-ps32.tex}
1187 \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in
1188 10~Schichten. Das Netzwerk wurde von dem Algorithmus
1189 \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting-Netzwerk}
1190 $\operatorname{PS}(32)$ durch 16~Schnitte erzeugt.}
1191 \label{fig:16-ec-from-ps32}
1194 \subsection{Versuche mit dem Pairwise-Sorting-Netzwerk}
1196 Anders verhält sich das \emph{Pairwise-Sorting-Netzwerk}
1197 $\operatorname{PS}(n)$, das \textit{Ian Parberry} in seiner Arbeit „The
1198 Pairwise Sorting Network“ \cite{P1992} definiert. Startet man
1199 \textsc{SN-Evolution-Cut} mit $\operatorname{PS}(32)$ und der Vorgabe,
1200 16~Leitungen zu entfernen, erhält man ein Sortiernetzwerk, dass die gleiche
1201 Anzahl an Komparatoren und Schichten hat wie $\operatorname{PS}(16)$ und
1202 $\operatorname{OES}(16)$. Eines dieser Sortiernetzwerke ist in
1203 Abbildung~\ref{fig:16-ec-from-ps32} dargestellt.
1205 Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even-Mischer} nicht
1206 einsetzt und auch nicht auf einem Mischer basiert, ist der
1207 $\operatorname{OEM}(8,8)$ im Sortiernetzwerk in
1208 Abbildung~\ref{fig:16-ec-from-ps32} eindeutig erkennbar (Schichten~7--10). In
1209 den Schichten~1--6 erkennt man zwei unabhängige Sortiernetzerke, die
1210 strukturell identisch zu $\operatorname{PS}(8)$ sind -- lediglich die
1211 Schichten~1 und~2 sowie 4~und~5 sind vertauscht.
1214 \textit{Eingang}_i = \left\{ \begin{array}{rl}
1215 -\infty & \quad \textrm{falls } i \operatorname{mod} 8 \in \{0, 6\} \\
1216 \infty & \quad \textrm{falls } i \operatorname{mod} 8 \in \{2, 4\} \\
1217 ? & \quad \mathrm{sonst}
1223 \input{images/32-pairwise-cut-16-pairwise.tex}
1225 \caption{PS(32) mit 16 Schnitten zu PS(16).}
1226 \label{fig:ps16-from-ps32}
1231 \input{images/16-pairwise.tex}
1233 \caption{Das $\operatorname{PS}(16)$-Sortiernetzwerk mit 8~Schnitten
1234 ($\operatorname{MIN}(0,2,4,6), \operatorname{MAX}(9,11,13,15)$). Das
1235 resultierende 8-Sortiernetzwerk ist $\operatorname{OES}(8)$.}
1236 \label{fig:16-pairwise}
1239 Wendet man \textsc{SN-Evolution-Cut} auf $\operatorname{PS}(16)$ an, so kann
1240 man $\operatorname{OES}(8)$ erhalten.
1242 \subsection{Versuche mit dem Odd-Even-Mergesort-Netzwerk}
1244 \todo{Schreibe noch etwas zum Odd-Even-Mergesort-Netzwerk.}
1247 \item Beispiel: Moritz und Rolfs Optimierung für Bitonic-Sort.
1248 \item Wie gut kann man durch wegschneiden werden?
1249 \item Wieviele Schnitte ergeben das selbe Netzwerk? Oder andersrum: Wieviele
1250 unterschiedliche Netzwerke kann ich erhalten? Wieviele Nachfolger hat ein
1251 Netzwerk / Knoten in der Markov-Kette?
1252 \item Abschnitt „Optimierung der Schnitte“ hier einbauen.
1256 \section{Der \textsc{SN-Markov}-Algorithmus}
1258 Der evolutionäre \textsc{SN-Evolution}-Algorithmus aus dem vorherigen
1259 Abschnitt verwendete immer zwei zufällige Sortiernetzwerke („Individuen“) aus
1260 einer Population. Da die beiden „Eltern“ zufällig und unabhängig voneinander
1261 ausgewählt werden, kann es vorkommen, dass das selbe Sortiernetzwerk zweimal
1262 verwendet und mit sich selbst kombiniert wird.
1264 Macht man diesen Spezialfall zum Regelfall, indem man \emph{immer} das
1265 aktuelle Netzwerk mit sich selbst kombiniert und anschließend die Hälfte aller
1266 Leitungen eliminiert, lassen sich einige interessante Beobachtungen anstellen.
1267 Netzwerke, die aus einem Netzwerk $S_0$ durch die beschriebene Kombination von
1268 $S_0$ mit sich selbst und anschließendem Eliminieren der Hälfte der Leitungen
1269 hervorgehen können, heißen \emph{Nachfolger} von $S_0$.
1271 Beim beschriebenen Vorgehen kann man die Sortiernetzwerke als Knoten in einem
1272 gerichteten Graphen betrachten. Zwei Knoten $V_0$ und $V_1$, die zwei
1273 Sortiernetzwerke $S_0$ und $S_1$ repräsentieren, sind genau dann mit einer
1274 Kante ${E_{0,1} = (V_0, V_1)}$ verbunden, wenn $S_1$ ein \emph{Nachfolger} von $S_0$
1275 ist, das heißt dass man $S_1$ durch die Rekombination von $S_0$ mit sich
1276 selbst erzeugen kann.
1278 Wie in Abschnitt~\ref{sect:anzahl_schnittmuster} beschrieben ist die Anzahl
1279 (unterschiedlichen) Schnittmuster und damit die Anzahl der Nachfolger sehr
1280 groß. Wenn $S_0$ ein Sortiernetzwerk mit $n$~Leitungen ist, so hat $S_0$ bis
1283 2^n \cdot \left( \begin{array}{c} 2n \\ n \end{array} \right)
1287 Der Algorithmus {\sc SN-Markov} legt auf diesem Graph einen zufälligen Weg
1288 (englisch: \textit{random walk}) zurück. Er startet auf einem gegebenen
1289 Sortiernetzwerk. Um von einem Sortiernetzwerk zum Nächsten zu gelangen
1290 rekombiniert er das aktuelle Sortiernetzwerk mit sich selbst und erhält so
1291 einen zufälligen Nachfolger.
1294 \item $n \leftarrow \mathrm{Input}$
1295 \item \texttt{while} \textit{true}
1297 \item $n \leftarrow \operatorname{recombine} (n, n)$
1302 \item Beste erreichte Netzwerke (gleich zu \emph{OE-Mergesort}).
1303 \item Anzahl der erreichbaren Sortiernetzwerke.
1304 \item Anzahl der Komparatoren und Anzahl der Schichten der durchlaufenen
1305 Netzwerke. (Abbildung~\ref{fig:markov-comparators-16})
1310 \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-12-pct.pdf}
1312 \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 12~Leitungen),
1313 die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
1314 \emph{Gamma-Verteilung} $f(x - 40)$ mit $k = 8,267$ und $\theta = 0,962$.}
1315 \label{fig:markov-comparators-12}
1320 \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-14-pct.pdf}
1322 \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 14~Leitungen),
1323 die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
1324 \emph{Gamma-Verteilung} $f(x - 52)$ mit $k = 9,522$ und $\theta = 0,867$.}
1325 \label{fig:markov-comparators-14}
1330 \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-16-pct.pdf}
1332 \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 16~Leitungen),
1333 die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
1334 \emph{Gamma-Verteilung} $f(x - 62)$ mit $k = 17,939$ und $\theta = 1,091$.}
1335 \label{fig:markov-comparators-16}
1339 \section{Empirische Beobachtungen}
1342 \item So schnell konvergiert der Algorithmus.
1349 Das würde mir noch einfallen$\ldots$
1352 \bibliography{references}
1353 \bibliographystyle{plain}
1359 % vim: set shiftwidth=2 softtabstop=2 tabstop=8 fdm=marker tw=78 :