1 \documentclass[a4paper,10pt]{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=25mm}
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{red box} = [draw,-,color=red, top color=red!2,bottom color=red!10]
56 \tikzstyle{blue box} = [draw,-,color=blue,top color=blue!2,bottom color=blue!10]
57 \tikzstyle{green box} = [draw,-,color=teal,top color=teal!2,bottom color=teal!10]
58 \tikzstyle{gray box} = [draw,-,color=black, top color=black!2,bottom color=black!10]
62 Sortiernetzwerke werden eingeführt und einige bekannte Konstruktionen werden
63 vorgestellt (Off-Even-Transposition, Bitonic-Merge, Odd-Even-Merge, Pairwise).
64 Transformationsmöglichkeiten für Sortiernetzwerke werden besprochen.
65 Evolutionäre Algorithmen werden beschrieben und ein evolutionärer
66 Algorithmus für die Optimierung von Sortiernetzwerken wird angegeben.
67 Die mindestens von diesem Algorithmus erreichte Güte wird angegeben und die
68 Transformation zu einer Markov-Kette wird gezeigt. {\em Natürlich: So fern ich
69 das hinbekomme bzw. Recht behalte.}
76 \section{Motivation und Einleitung}
78 \subsection{Motivation}\label{sect:motivation}
81 \item Sortiernetzwerke sind toll, weil $\ldots$
82 \item Sortiernetzwerke sind einfach erklärt, aber trotzdem kompliziert.
83 \item Bisher noch kein evolutionärer Algorithmus zur automatischen
84 Optimierung von Sortiernetzwerken bekannt. \textit{(Glaube ich zumindest.)}
87 \subsection{Einleitung}\label{sect:einleitung}
89 \subsubsection{Sortiernetzwerke}\label{sect:einleitung_sortiernetzwerke}
91 {\em Komparatoren} sind die Bausteine, die {\em Sortiernetzwerken} zugrunde
92 liegen. Sie haben zwei Eingänge über die sie zwei Zahlen erhalten können.
93 Ausserdem besitzt ein {\em Komparator} zwei Ausgänge, die im Gegensatz zu den
94 Eingängen unterscheidbar sind: Die grö"sere der beiden Zahlen wird immer auf
95 dem einen, die kleinere der beiden Zahlen immer auf dem anderen Ausgang
98 Wenn man nun mehrere {\em Komparatoren} miteinander kombiniert, also die
99 Ausgänge von Komparatoren mit dem Eingängen anderer Komparatoren verbindet,
100 erhält man ein {\em Komparatornetzwerk}.
104 \input{images/einfaches_komparatornetzwerk.tex}
106 \caption{Einfaches Komparatornetzwerk mit vier Ein- bzw. Ausgängen, bestehend
108 \label{fig:einfaches_komparatornetzwerk}
111 Abbildung~\ref{fig:einfaches_komparatornetzwerk} zeigt ein einfaches
112 Komparatornetzwerk aus fünf Komparatoren in der üblichen Darstellungsweise:
113 Die horizontalen Linien stellen Leitungen von den Eingängen auf der linken
114 Seite zu den Ausgängen auf er rechten Seite dar. Die vertikalen Pfeile
115 symbolisieren die Komparatoren, die die Werte "`auf den Leitungen"'
116 vergleichen und ggf. vertauschen. Nach einem Komparator befindet sich die
117 kleinere Zahl immer auf der Leitung, auf die der Pfeil zeigt, die größere Zahl
118 befindet sich auf der Leitung auf der der Pfeil seinen Ursprung hat.
120 Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
121 gleichzeitig angewandt werden. Das Beispiel in
122 Abbildung~\ref{fig:einfaches_komparatornetzwerk} verwendet diesen Umstand und
123 vergleicht in einem ersten Schritt die zwei oberen und die zwei unteren
124 Leitungen gleichzeitig. Eine Gruppe von Komparatoren, die gleichzeitig
125 angewendet werden können, nennt man eine \emph{Schicht} des
126 Komparatornetwerks. Die \emph{Verzögerung} eines Komparatornetzwerks ist
127 gleichbedeutend mit der Anzahl der Schichten, in die sich die Komparatoren
128 mindestens gruppieren lassen, da sie die Anzahl der benötigten parallelen
131 Komparatornetzwerke, die für jede beliebige Eingabepermutation eine
132 Ausgabe erzeugen, die der Sortierung der Eingabe entspricht, heißen
133 {\em Sortiernetzwerke}. Das in
134 Abbildung~\ref{fig:einfaches_komparatornetzwerk} gezeigte Komparatornetzwerk
135 ist kein Sotiernetzwerk: Die Eingabefolge ${(1, 2, 3, 4)}$ würde zur Ausgabe
136 ${(2, 1, 3, 4)}$ führen -- die bestehenden Sortierung wird also sogar
139 Zu beweisen, dass ein gegebenes Komparatornetzwerk die Sortiereigenschaft
140 {\em nicht} hat, ist mit einem gegebenen Gegenbeispiel einfach möglich.
141 Dieses Gegenbeispiel zu finden ist allerdings aufwendig.
143 \todo{Wie findet man die Gegenbeispiele? Die {\em Entscheidung}, ob ein
144 Netzwerk sortiert, ist doch NP-vollständig, also müsste doch das Finden eines
145 Gegenbeispiels im Allgemeinen auch exponentialle Laufzeit haben..?}
146 \todo{Wenn die {\em Entscheidung}, ob ein Netzwerk sortiert, NP-vollständig
147 ist, müsse man dann nicht einen Zeugen für die Sortiereigenschaft angeben
152 Um zu überprüfen, ob ein gegebenes Komparatornetzwerk die Sortiereigenschaft
153 besetzt, müssen nicht alle $n!$ Permutationen von $n$~unterschiedlichen Zahlen
154 ausprobieren. Stattdessen reicht es zu überprüfen, dass das Netzwerk alle
155 $2^n$~0-1-Folgen sortiert.
159 \item Ein Komparator-Netzwerk ist $\ldots$
160 \item Ein Komparator-Netzwerk ist ein Sortiernetzwerk, wenn $\ldots$
161 \item Die Frage nach der Sortiereigenschaft ist NP-vollständig.
164 \subsubsection{Evolutionäre Algorithmen}
166 Viele {\em kombinatorische Optimierungsprobleme} sind schwer zu lösen -- die
167 entsprechenden Entscheidungsprobleme liegen oft in der Komplexitätsklasse
168 $NP$, sind also mit bekannten Verfahren nicht effizient exakt lösbar. Sollte
169 sich herausstellen, dass diese Probleme nicht in der Komplexitätsklasse $P$
170 liegen, wäre eine Konsequenz, dass es effiziente exakte Algorithmen für diese
171 Probleme nicht geben kann. Falls sich hingegen herausstellt, dass diese
172 Probleme in der Komplexitätsklasse~$P$ liegen, wird es mit großer
173 Wahrscheinlichkeit noch einige Zeit dauern bis auch Algorithmen mit
174 praktikablen Zeitkonstanten gefunden werden.
176 Aus diesem Grund besteht die Notwendigkeit einen Kompromiss einzugehen: Statt
177 die bzw. eine der {\em optimalen} Lösungen als einzige Ausgabe des Algorithmus
178 zuzulassen, wird eine "`möglichst gute"' Lösung ausgegeben. Viele dieser
179 Optimierungsalgorithmen orientieren sich an Vorgängen in der Natur,
180 beispielsweise immitieren die "`Ameisenalgorithmen"' das Verhalten von Ameisen
181 auf der Futtersuche um kurze Rundreisen auf Graphen zu berechnen.
183 Bei {\em Evolutionären Algorithmen} stand die Evolution pate. Die Grundidee
184 ist es, bestehende Lösungen zu neuen, unter Umständen besseren Lösungen zu
185 kombinieren. Dabei bedient man sich der in der Evolutionstheorie etablierten
186 Nomenklatur, beispielsweise werden konkrete Lösungen für ein Problem häufig
187 als {\em Individuum} bezeichnet.
189 Die Vorgehensweise lässt sich abstrakt wie folgt beschreiben. Aus einer
190 bestehenden Lösungsmenge, der {\em Population} werden zufällig Lösungen
191 ausgesucht {\em (Selektion)} und zu einer neuen Lösung kombiniert ({\em
192 Rekombination}). Unter Umständen wird die neue Lösung noch zufällig
193 verändert {\em (Mutation)}, bevor sie in die bestehende Lösungsmenge
194 integriert wird. Die Wahrscheinlichkeiten, beispielsweise bei der {\em
195 Selektion}, sind dabei nicht zwangsläufig gleichverteilt -- üblicherweise
196 werden bessere Lösungen bevorzugt. Zur Bewertung die die sogenannte {\em
199 Nicht alle Probleme eignen sich für diese Strategie: Zum einen muss es möglich
200 sein, eine initiale Population zur Verfügung zu stellen, da diese als Basis
201 aller weiteren Operationen dient. Das ist häufig keine große Einschränkung, da
202 es oft einfach ist {\em irgendeine} Lösung anzugeben. Zum anderen muss eine
203 Methode für die Rekombination existieren. Das insbesondere dann problematisch
204 wenn {\em Nebenbedingungen} eingehalten werden müssen.
207 \item Unter einem "`Evolutionären Algorithmus"' versteht man $\ldots$
208 \item Da die Sortiereigenschaft zu überprüfen NP-schwer ist, ist die
209 Mutation \textit{(vermutlich)} nicht (effizient) möglich.
212 \section{Bekannte konstruktive Sortiernetzwerke}
214 Übersicht über bekannte konstruktive Sortiernetzwerke.
216 \subsection{Odd-Even-Transpositionsort}
217 \label{sect:odd_even_transpositionsort}
219 Das Sortiernetzwerk {\em Odd-Even-Transpositionsort} (OET) ist eines der
220 einfachsten Sortiernetzwerke. Es besteht aus $n$~{\em Schichten}, die jede
221 "`Leitung"' abwechselnd mit den benachbarten Leitungen verbindet.
222 Abbildung~\ref{fig:odd_even_transposition_08} zeigt das OET-Netzwerk für
227 \input{images/oe-transposition-8.tex}
229 \caption{Das {\em Odd-Even-Transpositionsort-Netzwerk} für acht Eingänge.}
230 \label{fig:odd_even_transposition_08}
233 \subsection{Batcher's Mergesort}
235 Ein Netzwerk von K.~E.~Batcher. Siehe:
236 K.E. Batcher: Sorting Networks and their Applications. Proc. AFIPS Spring
237 Joint Comput. Conf., Vol. 32, 307-314 (1968)
240 \subsubsection{Der bitone Mischer}\label{sect:der_bitone_mischer}
242 Das Netzwerk basiert auf dem {\em bitonen Mischer}, einem Komparator-Netzwerk,
243 das eine beliebige bitone Folge in eine sortierte Listen umordnen kann. Eine
244 {\em bitone Folge} ist eine monoton steigende Folge gefolgt von einer monoton
245 fallenden Folge, oder ein zyklischer Shift davon.
246 Abbildung~\ref{fig:beispiel-biton} zeigt die vier prinipiellen Möglichkeiten
247 die durch zyklische Shifts entstehen können. Die wichtigsten Varianten für
248 Batcher's Mergesort-Netzwerk zeigen die Abbildungen~\ref{fig:beispiel-biton-0}
249 und~\ref{fig:beispiel-biton-1}. Sie erhält man, wenn man eine aufsteigend und
250 eine absteigend sortierte Liste aneinanderhängt. Bei den
251 anderen beiden Formen ist wichtig zu beachten, dass das letzte Element nicht
252 größer (Abbildung~\ref{fig:beispiel-biton-2}) bzw. kleiner
253 (Abbildung~\ref{fig:beispiel-biton-3}) als das erste Element der Folge sein
258 \subfigure[aufsteigend, absteigend]{\input{images/beispiel-biton-0.tex}\label{fig:beispiel-biton-0}}
259 \subfigure[absteigend, aufsteigend]{\input{images/beispiel-biton-1.tex}\label{fig:beispiel-biton-1}}
260 \subfigure[aufsteigend, absteigend, aufsteigend]{\input{images/beispiel-biton-2.tex}\label{fig:beispiel-biton-2}}
261 \subfigure[absteigend, aufsteigend, absteigend]{\input{images/beispiel-biton-3.tex}\label{fig:beispiel-biton-3}}
262 \caption{Beispiele bitoner Folgen.}
263 \label{fig:beispiel-biton}
268 \subfigure[normal]{\input{images/bitonic-merge.tex}\label{fig:bitonic-merge-normal}}
270 \subfigure[trichter]{\input{images/bitonic-merge-trichter.tex}\label{fig:bitonic-merge-tricheter}}
271 \caption{Schematischer Aufbau des bitonen Mischers: Jedes Element der
272 aufsteigenden Folge $u_0, u_1, \ldots$ wird mit dem entsprechenden Element
273 der absteigend sortierten Folge $v_0, v_1, \ldots$ verglichen. Die beiden
274 resultierenden Teilfolgen sind wiederum biton.}
275 \label{fig:bitonic-merge-schema}
278 Der Mischer funktioniert folgendermaßen: Gegeben sind zwei Folgen mit je
279 ${m = \frac{n}{2}}$ Elementen, $U = \left(u_0, u_1, \ldots, u_{m-1}\right)$ und
280 $V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die Folge $U$ sei aufsteigend
281 sortiert, die Folge $V$ sei absteigend sortiert:
283 u_0 \leqq u_1 \leqq &\ldots& \leqq u_{m-1} \\
284 v_0 \geqq v_1 \geqq &\ldots& \geqq v_{m-1}
286 Im ersten Schritt werden nun jeweils die Elemente an den gleichen relativen
287 Positionen verglichen und ggf. vertauscht:
289 u_i \longleftrightarrow v_i, \quad 0 \leqq i < m
291 Sei $j \in \{0 \ldots m\}$ der Index der ersten Elemente $u_j$ und $v_j$, die
292 durch den gemeinsamen Komparator vertauscht werden. Unter der Annahme, dass
293 Elemente nur vertauscht werden wenn, sie ungleich sind, muss ${u_j > v_j}$
294 gelten. Mit $u_j \leqq u_{j+1}$ und $v_j \geqq v_{j+1}$ folgt daraus $u_{j+1}
295 > v_{j+1}$. Es werden also alle Elemente $u_k$ und $v_k$ mit $k \geqq j$
296 vertauscht. $j = m$ bezeichnet den Fall, in dem das größte Element der
297 "`linken"' Folge, $u_{m-1}$, kleiner ist als das kleinste Element der
298 "`rechten"' Folge, $v_{m-1}$. Daraus folgt, dass die entstehende Folge aus
299 zwei bitonen Folgen besteht, die rekursiv zusammengeführt werden können.
300 Abbildung~\ref{fig:bitonic-merge-normal} zeigt die Situationen vor und nach
301 diesem Schritt des Mischers.
303 Mit dem bitonen Mischer auch zwei aufsteigend sortierte Folgen sortiert
304 werden. Dazu ist lediglich das "`Umbenennen"' der Leitungen notwendig.
305 Abbildung~\ref{fig:bitonic-merge-tricheter} zeigt das Schema des bitonen
306 Mischers für zwei aufsteigend sortierte Foglen. Durch das Umbenennen verändert
307 sich das Muster der Komparatoren ein wenig: Statt an eine Treppe erinnert das
308 Muster nun an einen Trichter.
310 \subsubsection{Batcher's Bitonic-Mergesort-Netzwerk}
312 Das Sortiernetzwerk $S(n)$ mit $n$~Eingängen besteht aus zwei Instanzen von
313 $S(\frac{n}{2})$, dem Netzwerk mit $\frac{n}{2}$~Eingängen und dem bitonen
314 Mischer~$M(n)$. Die Rekursion bricht bei ${n = 1}$~ab --~eine einelementige
315 Liste ist immer sortiert.
316 Das konkrete Netzwerk~$S(8)$ ist in Abbildung~\ref{fig:batcher_08} zu sehen.
317 Eingezeichnet sind ebenfalls die beiden Instanzen des Netzwerks~$S(4)$ (rot)
318 sowie der bitone Mischer~$M(8)$ (blau).
324 %\includegraphics[viewport=115 491 372 782,width=7.5cm]{images/sn-rekursiver-aufbau.pdf}
326 %\caption{Rekursiver Aufbau von $S(n)$: Es besteht aus zwei Instanzen von
327 %$S(n/2)$ und dem Mischer $M(n)$.}
328 %\label{fig:bms_rekursiver_aufbau}
333 \input{images/batcher-8.tex}
335 \caption{$S(8)$, Batcher's {\em bitone Mergesort-Netzwerk} für acht
336 Eingänge. Markiert sind die beiden Instanzen von $S(4)$ (rot), die beiden
337 bitonen Mischer~$M(4)$ (blau) und die Komparatoren, die im letzten rekursiven
338 Schritt hinzugefügt wurden (grün).}
339 \label{fig:batcher_08}
342 \subsection{Odd-Even-Mergesort}
344 Obwohl der Name ähnlich klingt, haben {\em Odd-Even-Mergesort} (OEM) und
345 {\em Odd-Even-Transpositionsort} (OET, siehe
346 Abschnitt~\ref{sect:odd_even_transpositionsort}) wenig gemein. Auch dieses
347 Netzwerk ist von K.~Batcher gefunden worden und wird rekursiv durch einen
348 "`Mischer"' definiert.
350 \subsubsection{Der Odd-Even-Mischer}\label{sect:der_odd_even_mischer}
352 Der {\em Odd-Even-Mischer} ist ein Komperatornetzwerk, dass zwei sortierte
353 Folgen zu einer sortierten Ausgabe zusammenfügen kann. Dabei kommt es mit
354 weniger Vergleichen aus als der {\em bitone Mischer}, der im
355 Abschnitt~\ref{sect:der_bitone_mischer} vorgestellt wurde, aus.
357 Der {\em Odd-Even-Mischer} selbst ist ebenfalls rekursiv aufgebaut: Die
358 Eingabe für den Mischer mit $N = n + m$ Leitungen besteht aus den beiden
359 sortierten Folgen $U = \left(u_0, u_1, \ldots, u_{n-1}\right)$ und
360 $V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die gesamte Eingabe sei
361 $W = \left(w_0, w_1, \ldots, w_{N-1}\right)$ mit:
363 w_i = \left\{ \begin{array}{ll}
372 \input{images/oe-merge.tex}
374 \caption{Schematischer Aufbau des {\em Odd-Even} Mischers. Im Vergleich zum
375 bitonen Mischer für Acht kommt dieses Schema mit einem Komparator weniger
376 aus. Der Effekt wird duch den rekursiven Aufbau noch verstärkt.}
380 Diese werden jetzt in insgesamt vier sortierte Folgen aufgeteilt, je eine
381 Liste der geraden Indizes und je eine Liste der ungeraden Indizes.
383 U_{\textrm{gerade}} &=& \left(u_0, u_2, u_4, \ldots\right) \\
384 U_{\textrm{ungerade}} &=& \left(u_1, u_3, u_5, \ldots\right) \\
385 V_{\textrm{gerade}} &=& \left(v_0, v_2, u_4, \ldots\right) \\
386 V_{\textrm{ungerade}} &=& \left(v_1, v_3, u_5, \ldots\right)
389 Die geraden Folgen $U_{\textrm{gerade}}$ und $V_{\textrm{gerade}}$ bzw. die
390 ungeraden Folgen $U_{\textrm{ungerade}}$ und $V_{\textrm{ungerade}}$ werden
391 rekursiv von kleineren {\em Odd-Even-Mischern} zusammengefügt, so dass sich am
392 Ausgang der Mischer die Folgen
394 W_{\textrm{gerade}} &=& \left(w_0, w_2, w_4, \ldots\right) \\
395 W_{\textrm{ungerade}} &=& \left(w_1, w_3, w_5, \ldots\right)
399 Anschließend werden die Komparatoren zwischen benachbarten Leitungen
402 w_{2i-1} \longleftrightarrow w_{2i}, \quad 1 \leqq i < \frac{N}{2}
404 die die Folge~$W$ sortieren. Den schematischen Aufbau des {\em
405 Odd-Even-Mischers} zeigt Abbildung~\ref{fig:oe-merge}.
407 Leider bricht die Rekursion nicht so schön ab, wie das beim {\em bitonen
408 Mischer} der Fall gewesen ist. Insbesondere für ${n = m = 1}$ würde --
409 entsprechend der Konstruktionsvorschrift -- ein leeres Netzwerk entstehen, was
410 offensichtlich nicht korrekt wäre. Die Abbruchbedingungen für den rekursiven
413 \item Falls ${n = 0}$ oder ${m = 0}$: Das Netzwerk ist leer.
414 \item Falls ${n = 1}$ und ${m = 1}$: Das Netzwerk besteht aus einem
415 einzelnen Komparator.
418 Dass die resultierende Folge sortiert ist, lässt sich mit dem
419 {\em 0-1-Prinzip} leicht zeigen:
420 Da $U$ und $V$ sortiert sind, ist die Anzahl der Nullen in den geraden
421 Teilfolgen, $U_{\textrm{gerade}}$ bzw. $V_{\textrm{gerade}}$, größer oder
422 gleich der Anzahl der Nullen in den ungeraden Teilfolgen
423 $U_{\textrm{ungerade}}$ bzw. $V_{\textrm{ungerade}}$ --~die Einsen verhalten
424 sich entsprechend umgekehrt. Das trifft demnach auch auf die Folgen
425 $W_{\textrm{gerade}}$ und $W_{\textrm{ungerade}}$ entsprechend zu:
427 \left|W_{\textrm{gerade}}\right|_0
428 &=& \left|U_{\textrm{gerade}}\right|_0
429 + \left|V_{\textrm{gerade}}\right|_0
430 = \left\lceil \frac{1}{2} \left|U\right|_0 \right\rceil
431 + \left\lceil \frac{1}{2} \left|V\right|_0 \right\rceil \\
432 \left|W_{\textrm{ungerade}}\right|_0
433 &=& \left|U_{\textrm{ungerade}}\right|_0
434 + \left|V_{\textrm{ungerade}}\right|_0
435 = \left\lfloor \frac{1}{2} \left|U\right|_0 \right\rfloor
436 + \left\lfloor \frac{1}{2} \left|V\right|_0 \right\rfloor
438 Daraus folgt, dass $W_{\textrm{gerade}}$ $0$, $1$ oder $2$ Nullen mehr enthält
439 als $W_{\textrm{ungerade}}$. In den ersten beiden Fällen ist die "`verzahnte"'
440 Ausgabe der beiden kleineren Mischer bereits sortiert. Nur im letzten Fall,
441 wenn $W_{\textrm{gerade}}$ $2$~Nullen mehr enthählt als
442 $W_{\textrm{ungerade}}$, muss eine Vertauschung stattfinden, um die Ausgabe zu
443 sortieren. Die jeweiligen Situationen sind in
444 Abbildung~\ref{fig:oe-post-recursive} dargestellt.
448 \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 0$]{\input{images/oe-post-recursive-diff0.tex}}
450 \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 1$]{\input{images/oe-post-recursive-diff1.tex}}
452 \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 2$]{\input{images/oe-post-recursive-diff2.tex}}
453 \caption{Die drei Situationen, die nach dem Verzahnen der Ausgaben der
454 kleineren {\em Odd-Even-Mischer} entstehen können. Ist die Differenz der
455 Anzahl der Nullen gleich $0$ oder $1$, ist die Folge bereits sortiert. Im
456 letzten Fall stellt einer der Komparatoren sicher, dass das Ergebnis
458 \label{fig:oe-post-recursive}
461 \subsubsection{Das Odd-Even-Mergesort-Netzwerk}
463 Auch beim \emph{Odd-Even-Mergesort-Netzwerk} --~wie beim \emph{bitonen
464 Mergesort-Netzwerk}~-- entsteht das Sortiernetzwerk aus dem {\em
465 Odd-Even-Mischer} durch rekursives Anwenden auf einen Teil der Eingabe
466 (üblicherweise die Hälfte der Leitungen) und anschließendes zusammenfügen.
467 Abbildung~\ref{fig:odd_even_mergesort_08} zeigt das Netzwerk für $8$~Eingänge.
471 \input{images/oe-mergesort-8.tex}
473 \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge. Markiert
474 sind die Instanzen von $S(4)$ (rot), die beiden \emph{Odd-Even-Mischer}
475 $\mathit{OEM}(4)$ für gerade und ungerade Leitungen (blau) und die im letzten
476 Rekursionsschritt hinzugefügten Komparatoren zwischen benachbarten Leitungen
478 \label{fig:odd_even_mergesort_08}
482 \item Odd-Even-Transpositionsort
483 \item Bitonic-Mergesort
484 \item Odd-Even-Mergesort
485 \item Pairwise sorting-network
488 \section{Transformation von Sortiernetzwerken}
490 \subsection{Komprimieren}
492 \todo{Aus theoretischer Sicht eigentlich eine Trivialität. Rausschmeißen?}
494 Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
495 gleichzeitig ausgewertet werden, wie bereits in
496 Abschnitt~\ref{sect:einleitung_sortiernetzwerke} beschrieben. Unter
497 \emph{Komprimieren} wird eine (Neu-)Gruppierung in die kleinstmögliche Anzahl
498 von \emph{Schichten} verstanden.
500 Diese Anzahl ist insbesondere beim automatisierten Bewerten von
501 Komparatornetzwerken interessant. \dots
503 \subsection{Normalisieren}
507 \subfigure[$S(8)$ (nach Konstruktion)]{\input{images/batcher-8-nonstd.tex}\label{fig:bitonic-nonstd}}
508 \subfigure[$S(8)$ (normalisiert)]{\input{images/batcher-8-std.tex}\label{fig:bitonic-std}}
509 \caption{Jedes Sortiernetzwerk kann in ein Standard-Sortiernetzwerk
510 transformiert werden. Gezeigt ist das bitone Sortiernetzwerk nach der
511 intuitiven Konstruktion und die normalisierte Variante.}
512 \label{fig:beispiel_normalisieren}
515 Ein \emph{Standard-Sortiernetzwerk} oder \emph{normalisiertes Sortiernetzwerk}
516 ist ein Sortiernetzwerk, dessen Komparatoren alle in die selbe Richtung
517 zeigen. Jedes Sortiernetzwerk kann in eine normaliesierte Variante
518 transformiert werden. Dazu gibt beispielsweise \emph{Knuth} (\todo{Verweis})
519 einen Algorithmus an.
521 Abbildung~\ref{fig:beispiel_normalisieren} zeigt das das
522 bitone Sortiernetzwerk in zwei Varianten. Abbildung~\ref{fig:bitonic-nonstd}
523 zeigt das Netzwerk nach der Konstruktionsvorschrift, siehe auch
524 Abbildung~\ref{fig:bitonic-merge-normal}: In den ersten drei Schichten werden
525 die unter und die obere Hälfte gegenläufig sortiert. Das heißt dass nach drei
526 Schritten die eine Hälfte auf- und die andere Hälfte absteigend sortiert ist.
527 In den Schichten~4 bis~6 folgt der bitone Mischer entsprechend der rekursiven
530 In Abbildung~\ref{fig:bitonic-std} ist die normalisierte Version des bitonen
531 Mergesort-Netzwerks zu sehen. Alle Komparatoren zeigen hier in die gleiche
532 Richtung. Statt dem typischen "`Treppenmuster"' sind abwechselnd das Treppen-
533 und das Trichtermuster zu sehen.
535 \subsection{Zwei Netzwerke kombinieren}
538 \item Mit dem Bitonic-Merge
539 \item Mit dem Odd-Even-Merge
540 \item Nach dem Pairwise sorting-network Schema.
543 \subsection{Leitungen entfernen}\label{sect:leitungen_entfernen}
545 Im vorherigen Abschnitt haben wir gesehen, dass es mithilfe von
546 \emph{Mischern} möglich ist, aus zwei Sortiernetzwerken mit je $n$~Eingängen
547 ein neues Sortiernetzwerk mit $2n$~Eingängen zu erzeugen. Für einen
548 beabsichtigen \emph{evolutionären Algorithmus} ist es jedoch notwendig, dass
549 sich die Anzahl der Eingänge nicht verändert. Das heißt, dass wir wieder ein
550 Sortiernetzwerk mit $n$~Eingängen erhalten müssen.
552 Man kann ein gegebenes Sortiernetzwerk mit $n$~Eingängen auf ein
553 Sortiernetzwerk mit $(n-1)$~Leitungen verkleinern, indem man eine Leitung
554 „eliminiert“. Dazu nehmen wir an, dass das Minimum oder das Maximum an einem
555 bestimmten Eingang anliegt. Der Weg, den das Minimum beziehungsweise das Maxim
556 durch das Sortiernetzwerk nimmt, ist eindeutig bestimmt und endet an einem der
557 „Ränder“, also auf der Leitung mit dem höchsten oder dem niedrigsten Index.
558 Insbesondere ist bekannt, welche Komparatoren „berührt“ werden und welche
559 dafür sorgen, dass der Wert die Leitung gewechselt, da das Minimum jeden
560 Vergleich „verliert“ und das Maximum jeden Vergleich „gewinnt“. Die
561 Abbildung~\ref{fig:oe-transposition-cut0} zeigt den Weg eines Maximums durch
562 das {\em Odd-Even-Transpositionsort-Netzwerk}.
566 \subfigure[foo]{\input{images/oe-transposition-cut0.tex}\label{fig:oe-transposition-cut0}}
567 \subfigure[bar]{\input{images/oe-transposition-cut1.tex}\label{fig:oe-transposition-cut1}}
568 \subfigure[baz]{\input{images/oe-transposition-cut2.tex}\label{fig:oe-transposition-cut2}}
569 \subfigure[qux]{\input{images/oe-transposition-cut3.tex}\label{fig:oe-transposition-cut3}}
570 \caption{Eine Leitung wird aus dem {\em Odd-Even-Transpositionsort} Netzwerk
571 $\textrm{OET}(8)$ entfernt: Auf der rot markierten Leitung wird $\infty$
572 angelegt. Da der Wert bei jedem Komparator am unteren Ende herauskommt, ist
573 der Pfad fest vorgegeben. Da die restlichen Werte trotzdem noch richtig
574 sortiert werden müssen, kann dieser Pfad herausgetrennt werden. In der
575 letzten Abbildung ist $\textrm{OET}(7)$ markiert.}
578 Im nächsten Schritt werden alle beteiligten Komparatoren gelöscht bzw.
579 ersetzt: Komparatoren, die {\em nicht} zu einem Wechsel der Leitung geführt
580 haben, werden ersatzlos gelöscht. Diese Komparatoren sind in
581 Abbildung~\ref{fig:oe-transposition-cut0} grün markiert. Die Komparatoren, die
582 zum Wechsel der Leitung geführt haben, werden durch sich kreuzende Leitungen
583 ersetzt. Das Resultat ist eine Leitung, auf der das Minimum beziehungsweise
584 das Maximum angenommen wird, die an unterster oder oberster Stelle endet und
585 auf die keine Komparatoren mehr berührt
586 (Abbildung~\ref{fig:oe-transposition-cut1}).
588 Die Werte auf den verbleibenden $(n-1)$~Leitungen müssen vom restlichen
589 Komparatornetzwerk immernoch sortiert werden: Wir haben lediglich die Position
590 des Minimums oder des Maximums angenommen. Ein Sortiernetzwerk muss die
591 Eingabe sortieren, egal auf welcher Leitung das Minimum~/ das Maximum liegt.
592 Wir haben lediglich angefangen, das Sortiernetzwerk unter diese Annahme
593 auszuwerten -- über die verbleibenden Eingänge haben wir keine Aussage
594 getroffen. Entsprechend müssen die verbleibenden Ausgänge eine sortierte Liste
595 mit $(n-1)$~Elementen darstellen.
597 Wenn wir die Minimum- beziehungsweise Maximum-Leitung entfernen
598 (Abbildung~\ref{fig:oe-transposition-cut2}), bleibt das Sortiernetzwerk für
599 $(n-1)$~Leitungen übrig. Je nachdem, ob auf einer Leitung ein Minimum oder ein
600 Maximum angenommen wird, bezeichnen wir das eliminieren einer Leitung als
601 \emph{Minimum-Schnitt} beziehungsweise \emph{Maximum-Schnitt}.
603 Die letzte Abbildung, \ref{fig:oe-transposition-cut3}, zeigt das
604 Sortiernetzwerk wieder mit den üblichen geraden Leitungen und die rot
605 markierten Komparatoren wurden verschoben, so dass sich eine kompaktere
606 Darstellung ergibt. Ausserdem ist das
607 {\em Odd-Even-Transpositionsort-Netzwerk} für sieben Werte markiert. Der
608 zusätzliche Komparator vor dem $\textrm{OET}(7)$ hat keinen Einfluss auf die
609 Ausgabe und kann entfernt werden.
611 Der Eliminierungsschritt kann iterativ angewandt werden, um aus einem
612 Sortiernetzwerk mit $n$~Ein\-gängen Sortiernetzwerke mit $n-1$, $n-2$,
613 $n-3$,~\dots Eingängen zu erzeugen. Insbesondere können wir auf diese Art und
614 Weise einen Sortiernetzwerk mit $2n$~Eingängen wieder auf ein Sortiernetzwerk
615 mit $n$~Eingängen reduzieren.
617 Bei einem Sortiernetzwerk mit $n$~Eingängen gibt es $2n$~Möglichkeiten eine
618 Leitung zu entfernen: Auf jeder der $n$~Leitungen kann sowohl das Minimum als
619 auch das Maximum angenommen werden. Wendet man das Verfahren iterativ an, um
620 ein $n$-Sortiernetzwerk auf ein $m$-Sortiernetzwerk zu reduzieren, ergeben
623 \prod_{i=n}^{m+1} 2i = 2^{n-m} \frac{n!}{m!}
626 Möglichkeiten. Diese Möglichkeiten sind nicht alle unterschiedlich. Legt man
627 beispielsweise das Minimum auf die unterste Leitung und das Maximum auf die
628 oberste Leitung eines Standard-Sortiernetzwerks, führen beide Reihenfolgen zum
631 \textit{Moritz Mühlenthaler} zeigt in seiner Arbeit (\todo{Referenz}), dass
632 es möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise
633 Maximum vorzubelegen. Dadurch wird die Anzahl der möglichen Schnitte
634 reduziert, die Menge der erreichbaren Sortiernetzwerke bleibt aber
635 unverändert. Die Anzahl der möglichen „Schnittmuster“ setzt sich zusammen aus
636 der Anzahl von Möglichkeiten, $n-m$~Leitungen aus $n$ Leitungen auszuwählen,
637 und die möglichen Minimum-~/ Maximum-Muster. Damit ergibt sich folgende
640 2^{n-m} \cdot \left( \begin{array}{c} n \\ n-m \end{array} \right)
641 = 2^{n-m} \cdot \frac{n!}{(n-m)! m!}
642 = 2^{n-m} \cdot \frac{n!}{m!} \cdot \frac{1}{(n-m)!}
646 Die Anzahl der möglichen Schnitte wird mit der Anzahl der zu entfernenden
647 Leitungen sehr schnell sehr groß. Um ein Sortiernetzwerk mit 32~Eingängen auf
648 ein Sortiernetzwerk mit 16~Eingängen zu reduzieren sind 16~Schnitte notwendig,
649 für die es bereits etwa ${3,939 \cdot 10^{13}}$ Möglichkeiten gibt. Ein
650 Ausprobieren aller Möglichkeiten ist für große Netzwerke nicht oder nur unter
651 erheblichem Ressourcenaufwand möglich.
653 Das Programm {\sc SN-Evolution-Cut} implementiert einen evolutionären
654 Algorithmus, der zu einem gegebenen Sortiernetzwerk und einer gewünschten
655 Leitungszahl ein Schnittmuster sucht, dass ein Sortiernetzwerk mit einer
656 möglichst geringen Anzahl von Komparatoren und Schichten ergibt. Zur Bewertung
657 von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}. Mit diesem
658 Algorithmus wurden zu einer Reihe von „interessanten“ Netzwerken möglichst
659 gute Schnittmuster gesucht.
661 In ihrer Arbeit “Improving Bitonic Sorting by Wire Elimination” zeigen Moritz
662 Mühlenthaler und Rolf Wanka, wie man einen bitonen Mischer, der nach Batchers
663 Methode konstruiert wurde, durch systematisches Entfernen von Leitungen in
664 einen ebenfalls bitonen Mischer mit der Hälfte der Leitungen transformiert.
665 Diese alternativen Mischer sparen im Vergleich zu den Mischern, die nach
666 Batchers Methode konstruiert werden, Komparatoren ein.
668 Beispeilsweise geben Mühlenthaler und Wanka ein Sortiernetzwerk mit
669 16~Eingängen an, das mithilfe der alternativen Mischer konstruiert wurde.
670 Dieses Sortiernetzwerk benötigt 68~Komparatoren, 12~weniger als das
671 bitone Mergesort-Netzwerk nach Batchers Methode.
673 Startet man {\sc SN-Evolution-Cut} mit dem bitonen Mergesort-Netzwerk
674 $\operatorname{BS}(32)$ und der Vorgabe 16~Leitungen zu entfernen, liefert der
675 Algorithmus Sortiernetzwerke, die ebenfalls aus 68~Komparatoren bestehen. Ein
676 16-Sortiernetzwerk, das auf diese Weise generiert wurde, ist in
677 Abbildung~\ref{fig:16-ec-1277186619} zu sehen.
680 \item Beispiel: Moritz und Rolfs Optimierung für Bitonic-Sort.
681 \item Wie gut kann man durch wegschneiden werden?
682 \item Wieviele Schnitte ergeben das selbe Netzwerk?
683 \item Abschnitt „Optimierung der Schnitte“ hier einbauen.
686 \section{Der evolutionäre Ansatz}
688 Um einen evolutionären Algorithmus für Sortiernetzwerke zu entwickeln, werden
689 die vorgestellten Methoden kombiniert.
691 \subsection{Bewertungsfunktion}\label{sect:bewertung}
693 Um Sortiernetzwerke überhaupt optimieren zu können, muss zunächst die
694 {\em Güte} eines Netzwerkes definiert werden. Prinzipiell gibt es zwei Ziele,
695 die interessant sind:
697 \item Möglichst wenige Komparatoren ("`klein"')
698 \item Möglichst wenige Schichten ("`schnell"')
701 Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das
702 kleinste bekannte Sortiernetzwerk für 16~Eingänge besteht aus 60~Komparatoren
703 in 10~Schichten. Das schnellste Netzwerk besteht aus 61~Komparatoren in nur
706 Eine Gütefunktion, die die beiden Ziele "`klein"' und "`schnell"'
707 berücksichtigen kann, hat die folgende allgemeine Form:
709 \mathit{Guete}(S) = w_{\mathrm{Basis}}
710 + w_{\mathrm{Komparatoren}} \cdot \left|S\right|_\mathrm{Komparatoren}
711 + w_{\mathrm{Schichten}} \cdot \left|S\right|_\mathrm{Schichten}
713 Die Parameter $w_{\mathrm{Komparatoren}}$ und $w_{\mathrm{Schichten}}$ dienen
714 dabei der Festlegung des Optimierungsziels. Wenn einer der beiden Parameter
715 gleich Null ist, wird nur das jeweils andere Ziel verfolgt. Sind beide
716 Parameter gleich Null, werden alle Netzwerke mit der gleich Güte bewertet --
717 jegliche Ergebnisse sind dann rein zufälliger Natur.
719 Mit dem Parameter $w_{\mathrm{Basis}}$ kann auf die Selektion Einfluss
720 genommen werden. Ist er groß, wird der relative Unterschied der Güten
721 verschiedener Netzwerke kleiner, was die {\em Exploration}, das Absuchen des
722 gesamten Lösungsraums, begünstigt. Wählt man $w_{\mathrm{Basis}}$ hingegen
723 klein, in Abhängigkeit von den anderen beiden Parametern sind auch negative
724 Werte möglich, werden die relativen Unterschiede groß. Dadurch wird die {\em
725 Exploitation}, das Finden lokaler Optima, bevorzugt.
727 \subsection{Selektion}
731 \subsection{Rekombination}
733 Bei der Rekombination werden zwei Individuen --~hier Sortiernetzwerke~-- zu
734 einer neuen Lösung kombiniert. Dazu verwenden wir einen Mischer, zum Beispiel
735 den {\em bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) oder den
736 {\em Odd-Even-Mischer} (Abschnitt~\ref{sect:der_odd_even_mischer}), um die
737 beiden Netzwerke zu einem Netzwerk mit $2n$~Leitungen zusammenzufügen.
738 Anschließend entfernen wir zufällig $n$~Leitungen wie in
739 Abschnitt~\ref{sect:leitungen_entfernen} beschrieben.
741 Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft
744 \subsection{Mutation}
746 Zu einem vollständigen evolutionären Algorithmus gehört außerdem eine Mutation
747 --~eine zufällige Veränderung einer Lösung. Leider ist es nicht möglich ein
748 Sortiernetzwerk zufällig zu verändern aber trotzdem die Sortiereigenschaft zu
749 erhalten. Selbst das \emph{Hinzufügen} eines zufälligen Komparators kann diese
750 Eigenschaft zerstören.
752 Nach einer Mutation müsste man überprüfen, ob das neue Komparatornetzwerk die
753 Sortiereigenschaft noch besitzt. Nach heutigem Wissenstand ist diese
754 Überprüfung nur mit exponentiellem Aufwand möglich, etwa durch das
755 Ausprobieren aller $2^n$~Bitmuster.
757 Um das Potenzial einer Mutation abzuschätzen habe ich in den evolutionären
758 Algorithmus eine Überprüfung eingebaut. Unmittelbar vor dem Einfügen in die
759 Population überprüft das Programm die Notwendigkeit jedes einzelnen
760 Komparators. Dazu wurde nacheinander jeder Komparator entfernt und überprüft,
761 ob das verbleibende Netzwerk die Sortiereigenschaft noch besitzt.
764 \item Güte von Sortiernetzwerken (Anzahl der Komparatoren, Anzahl der
765 Schichten, kobiniert)
766 \item Rekombination: Merge Anhängen und Leitungen entfernen.
769 Ein Beispielnetzwerk, das von dem Algorithmus gefunden wird, zeigt
770 Abbildung~\ref{fig:evolutionary_08}.
774 \input{images/evolutionary-08.tex}
776 \caption{Ein mit dem evolutionären Algorithmus erzeugtes Sortiernetzwerk mit
777 acht Eingängen. Es besteht aus 19~Komparatoren in 6~Schichten.}
778 \label{fig:evolutionary_08}
783 \input{images/08-e2-1237993371.tex}
785 \caption{{\tt images/08-e2-1237993371.tex}: 19~Komparatoren in 6~Schichten}
786 \label{fig:08-e2-1237993371}
791 \input{images/09-e2-1237997073.tex}
793 \caption{{\tt images/09-e2-1237997073.tex}: 25~Komparatoren in 8~Schichten}
794 \label{fig:09-e2-1237997073}
799 \input{images/09-e2-1237999719.tex}
801 \caption{{\tt images/09-e2-1237999719.tex}: 25~Komparatoren in 7~Schichten}
802 \label{fig:09-e2-1237999719}
807 \input{images/10-e2-1239014566.tex}
809 \caption{{\tt images/10-e2-1239014566.tex}: 29~Komparatoren in 8~Schichten}
810 \label{fig:10-e2-1239014566}
816 \item So gut kann man mindestens werden {\em ($\rightarrow$ Bitonic-Mergesort, vermute ich)}.
817 \item Wie gut die Netzwerke werden, hängt stark vom verwendeten \em{Mischer} ab.
820 \section{Markov-Kette}
822 Der evolutionäre Algorithmus aus dem vorherigen Abschnitt verwendete immer
823 zwei zufällige Sortiernetzwerke („Individuen“) aus einer Population. Da die
824 beiden „Eltern“ zufällig und unabhängig voneinander ausgewählt werden, kann es
825 vorkommen, dass das selbe Sortiernetzwerk zweimal verwendet und mit sich
826 selbst kombiniert wird.
828 Macht man diesen Spezialfall zum Regelfall, indem man \emph{immer} das
829 aktuelle Netzwerk mit sich selbst kombiniert und anschließend die Hälfte aller
830 Leitungen eliminiert, lassen sich einige interessante Beobachtungen anstellen.
831 Netzwerke, die aus einem Netzwerk $S_0$ durch die beschriebene Kombination von
832 $S_0$ mit sich selbst und anschließendem Eliminieren der Hälfte der Leitungen
833 hervorgehen können, heißen \emph{Nachfolger} von $S_0$.
835 Beim beschriebenen Vorgehen kann man die Sortiernetzwerke als Knoten in einem
836 gerichteten Graphen betrachten. Zwei Knoten $V_0$ und $V_1$, die zwei
837 Sortiernetzwerke $S_0$ und $S_1$ repräsentieren, sind genau dann mit einer
838 Kante ${E_{0,1} = (V_0, V_1)}$ verbunden, wenn $S_1$ ein \emph{Nachfolger} von $S_0$
839 ist, das heißt dass man $S_1$ durch die Rekombination von $S_0$ mit sich
840 selbst erzeugen kann.
842 Der Algorithmus {\sc SN-Markov} legt auf diesem Graph einen zufälligen Weg
843 (englisch: \textit{random walk}) zurück. Er startet auf einem gegebenen
844 Sortiernetzwerk. Um von einem Sortiernetzwerk zum Nächsten zu gelangen
845 rekombiniert er das aktuelle Sortiernetzwerk mit sich selbst und erhält so
846 einen zufälligen Nachfolger.
849 \item $n \leftarrow \mathrm{Input}$
850 \item \texttt{while} \textit{true}
852 \item $n \leftarrow \operatorname{recombine} (n, n)$
857 \item Beste erreichte Netzwerke (gleich zu \emph{OE-Mergesort}).
858 \item Anzahl der erreichbaren Sortiernetzwerke.
859 \item Anzahl der Komparatoren und Anzahl der Schichten der durchlaufenen
860 Netzwerke. (Abbildung~\ref{fig:markov-comparators-16})
865 \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-16.pdf}
867 \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 16~Leitungen), die von {\sc SN-Markov} durchlaufen wurden.}
868 \label{fig:markov-comparators-16}
871 %\input{shmoo-aequivalenz.tex}
873 \section{Optimierung der Schnitte}
875 Der \emph{evolution-cut}-Algorithmus nimmt ein gegebenes Sortiernetzwerk mit
876 $n$~Leitungen und sucht die beste Sequenz von $c$~Min- und Max-Schnitten um
877 ein ${(n-c)}$-Sortiernetzwerk zu erhalten.
879 Bei diesem Algorithmus werden die \emph{Schnitt-Sequenzen} als Individuen
880 verwendet. Eine \emph{Schnitt-Sequenz} ist eine Liste mit $c$~Schnitten, die
881 jeweils durch die Start-Leitung und die Richtung \textit{Min} beziehungsweise
882 \textit{Max} gegeben ist. Der Algorithmus wendet jeden Schnitt einzeln an, so
883 dass eine Leitungsnummer mehrfach in einer Schnittsequenz vorkommen kann. Die
884 höchste zulässige Leitungsnummer ist abhängig von der Position des Schnitts in
885 der Sequenz. Der Schnitt an Position~$i$ darf höchstens die
886 Leitungsnummer~${n-i-1}$ enthalten.\footnote{Die niedrigste Leitungsnummer ist
887 $0$, die höchste Leitungsnummer eines $n$-Sortiernetzwerks ist $n-1$.}
889 Um zwei Individuen zu rekombinieren werden die ersten $r$~Schnitte der einen
890 Schnitt-Sequenz verwendet und die letzten ${c-r}$~Schnitte der zweiten
891 Sequenz. $r$ ist eine Zufallsvariable mit $0 \leqq r \leqq c$.
893 Die Mutation setzt entweder die Leitungs-Nummer eines Schnitts~$i$ zufällig
894 auf einen neuen Wert $l$ mit $0 \leqq l \le n-i$ oder invertiert die
899 \input{images/16-ec-1277186619.tex}
901 \caption{{\tt images/16-ec-1277186619.tex}: Sortiernetzwerk mit 16~Leitungen
902 und 68~Komparatoren in 10~Schichten. Das Netzwerk wurde von dem Algorithmus
903 \emph{evolution-cut} aus dem Bitonic-Mergesort-Netzwerk $M(32)$ durch
904 16~Schnitte erzeugt.}
905 \label{fig:16-ec-1277186619}
908 Wendet man den \emph{evolution-cut}-Algorithmus auf das
909 Bitonic-Mergesort-Netzwerk $M(n)$ an und setzt die Anzahl der Schnitte~$c$ auf
910 $\frac{n}{2}$, so erhält man Sortiernetzwerke, die weniger Komparatoren
911 benötigen als $M(\frac{n}{2})$.
913 Das Sortiernetzwerk in Abbildung~\ref{fig:16-ec-1277186619} ist entstanden,
914 indem der Algorithmus \emph{evolution-cut} auf das $M(32)$-Sortiernetzwerk
915 angewendet wurde. Der Algorithmus fand eine Schnitt-Sequenz aus 16~Schnitten,
916 die ein Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in 10~Schichten
917 erzeugt. Das $M(16)$-Sortiernetzwerk besteht aus 80~Komparatoren in
920 Dieses Ergebnis deckt sich mit dem Sortiernetzwerk, dass
921 \emph{Moritz Mühlenthaler} und \emph{Rolf Wanka} in ihrer Veröffentlichung
922 „Improving Bitonic Sorting by Wire Elimination“ vorstellen. Sie verwenden
923 Schnitte, um Komparatoren beim bitonen $(n,n)$-Mischer enizusparen. Ein
924 sukzessive aus optimieren Mischern aufgebautes Sortiernetzwerk spart
925 --~verglichen mit dem Bitonic-Mergesort-Netzwerk~-- $\frac{1}{4}n(\log n - 1)$
926 Komparatoren ein. Bei einem Sortiernetzwerk mit 16~Leitungen also
927 12~Komparatoren -- 68 statt 80.
931 \input{images/32-ec-1277190372.tex}
933 \caption{{\tt images/32-ec-1277190372.tex}: Sortiernetzwerk mit 32~Leitungen
934 und 206~Komparatoren in 15~Schichten. Das Netzwerk wurde von dem Algorithmus
935 \emph{evolution-cut} aus dem Bitonic-Mergesort-Netzwerk $M(64)$ durch
936 32~Schnitte erzeugt.}
937 \label{fig:32-ec-1277190372}
940 Abbildung~\ref{fig:32-ec-1277190372} zeigt ein 32-Sortiernetzwerk, dass vom
941 \emph{evolution-cut}-Algorithmus aus dem $M(64)$-Netzwerk erzeugt wurde. Es
942 besteht aus 206~Komparatoren in 15~Schichten -- 34~Komparatoren weniger als
943 $M(32)$ und zwei Komparatoren weniger als das Netzwerk, das nach Mühlenthaler
944 und Wankas Methode konstruiert wird. Die Anzahl der Schichten ist bei allen
947 \textbf{TODO:} $M(128) \rightarrow n=64$: 584~Komparatoren in 21~Schichten
948 möglich (nach ca. 600k Iterationen). Moritz und Rolf: $672-80=592$
949 Komparatoren; $M(64)$: 672~Komparatoren.
1017 % images/32-ec-1277190372.tex
1019 \section{Empirische Beobachtungen}
1022 \item So schnell konvergiert der Algorithmus.
1028 Das würde mir noch einfallen$\ldots$
1030 %\bibliography{references}
1031 %\bibliographystyle{plain}
1037 % vim: set shiftwidth=2 softtabstop=2 tabstop=8 fdm=marker tw=78 :