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 {\em Komparatoren} mit dem Eingängen anderer {\em Komparatoren}
100 verbindet, 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 Komparatornetzwerke, die für jede beliebige Eingabepermutation eine
121 Ausgabe erzeugen, die der Sortierung der Eingabe entspricht, heißen
122 {\em Sortiernetzwerke}. Das in
123 Abbildung~\ref{fig:einfaches_komparatornetzwerk} gezeigte Komparatornetzwerk
124 ist kein Sotiernetzwerk: Die Eingabefolge ${(1, 2, 3, 4)}$ würde zur Ausgabe
125 ${(2, 1, 3, 4)}$ führen -- die bestehenden Sortierung wird also sogar
128 Zu beweisen, dass ein gegebenes Komparatornetzwerk die Sortiereigenschaft
129 {\em nicht} hat, ist mit einem gegebenen Gegenbeispiel also einfach möglich.
130 Dieses Gegenbeispiel zu finden ist allerdings aufwendig.
132 \todo{Wie findet man die Gegenbeispiele? Die {\em Entscheidung}, ob ein
133 Netzwerk sortiert, ist doch NP-vollständig, also müsste doch das Finden eines
134 Gegenbeispiels im Allgemeinen auch exponentialle Laufzeit haben..?}
135 \todo{Wenn die {\em Entscheidung}, ob ein Netzwerk sortiert, NP-vollständig
136 ist, müsse man dann nicht einen Zeugen für die Sortiereigenschaft angeben
141 Um zu überprüfen, ob ein gegebenes Komparatornetzwerk die Sortiereigenschaft
142 besetzt, müssen nicht alle $n!$ Permutationen von $n$~unterschiedlichen Zahlen
143 ausprobieren. Stattdessen reicht es zu überprüfen, dass das Netzwerk alle
144 $2^n$~${0-1}$-Folgen sortiert.
148 \item Ein Komparator-Netzwerk ist $\ldots$
149 \item Ein Komparator-Netzwerk ist ein Sortiernetzwerk, wenn $\ldots$
150 \item Die Frage nach der Sortiereigenschaft ist NP-vollständig.
153 \subsubsection{Evolutionäre Algorithmen}
155 Viele {\em kombinatorische Optimierungsprobleme} sind schwer zu lösen -- die
156 entsprechenden Entscheidungsprobleme liegen oft in der Komplexitätsklasse
157 $NP$, sind also mit bekannten Verfahren nicht effizient exakt lösbar. Sollte
158 sich herausstellen, dass diese Probleme nicht in der Komplexitätsklasse $P$
159 liegen, wäre eine Konsequenz, dass es effiziente exakte Algorithmen für diese
160 Probleme nicht geben kann. Falls sich hingegen herausstellt, dass diese
161 Probleme in der Komplexitätsklasse~$P$ liegen, wird es mit großer
162 Wahrscheinlichkeit noch einige Zeit dauern bis auch Algorithmen mit
163 praktikablen Zeitkonstanten gefunden werden.
165 Aus diesem Grund besteht die Notwendigkeit einen Kompromiss einzugehen: Statt
166 die bzw. eine der {\em optimalen} Lösungen als einzige Ausgabe des Algorithmus
167 zuzulassen, wird eine "`möglichst gute"' Lösung ausgegeben. Viele dieser
168 Optimierungsalgorithmen orientieren sich an Vorgängen in der Natur,
169 beispielsweise immitieren die "`Ameisenalgorithmen"' das Verhalten von Ameisen
170 auf der Futtersuche um kurze Rundreisen auf Graphen zu berechnen.
172 Bei {\em Evolutionären Algorithmen} stand die Evolution pate. Die Grundidee
173 ist es, bestehende Lösungen zu neuen, unter Umständen besseren Lösungen zu
174 kombinieren. Dabei bedient man sich der in der Evolutionstheorie etablierten
175 Nomenklatur, beispielsweise werden konkrete Lösungen für ein Problem häufig
176 als {\em Individuum} bezeichnet.
178 Die Vorgehensweise lässt sich abstrakt wie folgt beschreiben. Aus einer
179 bestehenden Lösungsmenge, der {\em Population} werden zufällig Lösungen
180 ausgesucht {\em (Selektion)} und zu einer neuen Lösung kombiniert ({\em
181 Rekombination}). Unter Umständen wird die neue Lösung noch zufällig
182 verändert {\em (Mutation)}, bevor sie in die bestehende Lösungsmenge
183 integriert wird. Die Wahrscheinlichkeiten, beispielsweise bei der {\em
184 Selektion}, sind dabei nicht zwangsläufig gleichverteilt -- üblicherweise
185 werden bessere Lösungen bevorzugt. Zur Bewertung die die sogenannte {\em
188 Nicht alle Probleme eignen sich für diese Strategie: Zum einen muss es möglich
189 sein, eine initiale Population zur Verfügung zu stellen, da diese als Basis
190 aller weiteren Operationen dient. Das ist häufig keine große Einschränkung, da
191 es oft einfach ist {\em irgendeine} Lösung anzugeben. Zum anderen muss eine
192 Methode für die Rekombination existieren. Das insbesondere dann problematisch
193 wenn {\em Nebenbedingungen} eingehalten werden müssen.
196 \item Unter einem "`Evolutionären Algorithmus"' versteht man $\ldots$
197 \item Da die Sortiereigenschaft zu überprüfen NP-schwer ist, ist die
198 Mutation \textit{(vermutlich)} nicht (effizient) möglich.
201 \section{Bekannte konstruktive Sortiernetzwerke}
203 Übersicht über bekannte konstruktive Sortiernetzwerke.
205 \subsection{Odd-Even-Transpositionsort}
206 \label{sect:odd_even_transpositionsort}
208 Das Sortiernetzwerk {\em Odd-Even-Transpositionsort} (OET) ist eines der
209 einfachsten Sortiernetzwerke. Es besteht aus $n$~{\em Schichten}, die jede
210 "`Leitung"' abwechselnd mit den benachbarten Leitungen verbindet.
211 Abbildung~\ref{fig:odd_even_transposition_08} zeigt das OET-Netzwerk für
216 \input{images/oe-transposition-8.tex}
218 \caption{Das {\em Odd-Even-Transpositionsort} Netzwerk für acht Eingänge.}
219 \label{fig:odd_even_transposition_08}
222 \subsection{Batcher's Mergesort}
224 Ein Netzwerk von K.~E.~Batcher. Siehe:
225 K.E. Batcher: Sorting Networks and their Applications. Proc. AFIPS Spring
226 Joint Comput. Conf., Vol. 32, 307-314 (1968)
229 \subsubsection{Der bitone Mischer}\label{sect:der_bitone_mischer}
231 Das Netzwerk basiert auf dem {\em bitonen Mischer}, einem Komparator-Netzwerk,
232 das eine beliebige bitone Folge in eine sortierte Listen umordnen kann. Eine
233 {\em bitone Folge} ist eine monoton steigende Folge gefolgt von einer monoton
234 fallenden Folge, oder ein zyklischer Shift davon.
235 Abbildung~\ref{fig:beispiel-biton} zeigt die vier prinipiellen Möglichkeiten
236 die durch zyklische Shifts entstehen können. Die wichtigsten Varianten für
237 Batcher's Mergesort-Netzwerk zeigen die Abbildungen~\ref{fig:beispiel-biton-0}
238 und~\ref{fig:beispiel-biton-1}. Sie erhält man, wenn man eine aufsteigend und
239 eine absteigend sortierte Liste aneinanderhängt. Bei den
240 anderen beiden Formen ist wichtig zu beachten, dass das letzte Element nicht
241 größer (Abbildung~\ref{fig:beispiel-biton-2}) bzw. kleiner
242 (Abbildung~\ref{fig:beispiel-biton-3}) als das erste Element der Folge sein
247 \subfigure[aufsteigend, absteigend]{\input{images/beispiel-biton-0.tex}\label{fig:beispiel-biton-0}}
248 \subfigure[absteigend, aufsteigend]{\input{images/beispiel-biton-1.tex}\label{fig:beispiel-biton-1}}
249 \subfigure[aufsteigend, absteigend, aufsteigend]{\input{images/beispiel-biton-2.tex}\label{fig:beispiel-biton-2}}
250 \subfigure[absteigend, aufsteigend, absteigend]{\input{images/beispiel-biton-3.tex}\label{fig:beispiel-biton-3}}
251 \caption{Beispiele bitoner Folgen.}
252 \label{fig:beispiel-biton}
257 \subfigure[normal]{\input{images/bitonic-merge.tex}\label{fig:bitonic-merge-normal}}
259 \subfigure[trichter]{\input{images/bitonic-merge-trichter.tex}\label{fig:bitonic-merge-tricheter}}
260 \caption{Schematischer Aufbau des bitonen Mischers: Jedes Element der
261 aufsteigenden Folge $u_0, u_1, \ldots$ wird mit dem entsprechenden Element
262 der absteigend sortierten Folge $v_0, v_1, \ldots$ verglichen. Die beiden
263 resultierenden Teilfolgen sind wiederum biton.}
264 \label{fig:bitonic-merge-schema}
267 Der Mischer funktioniert folgendermaßen: Gegeben sind zwei Folgen mit je
268 ${m = \frac{n}{2}}$ Elementen, $U = \left(u_0, u_1, \ldots, u_{m-1}\right)$ und
269 $V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die Folge $U$ sei aufsteigend
270 sortiert, die Folge $V$ sei absteigend sortiert:
272 u_0 \leqq u_1 \leqq &\ldots& \leqq u_{m-1} \\
273 v_0 \geqq v_1 \geqq &\ldots& \geqq v_{m-1}
275 Im ersten Schritt werden nun jeweils die Elemente an den gleichen relativen
276 Positionen verglichen und ggf. vertauscht:
278 u_i \longleftrightarrow v_i, \quad 0 \leqq i < m
280 Sei $j \in \{0 \ldots m\}$ der Index der ersten Elemente $u_j$ und $v_j$, die
281 durch den gemeinsamen Komparator vertauscht werden. Unter der Annahme, dass
282 Elemente nur vertauscht werden wenn, sie ungleich sind, muss ${u_j > v_j}$
283 gelten. Mit $u_j \leqq u_{j+1}$ und $v_j \geqq v_{j+1}$ folgt daraus $u_{j+1}
284 > v_{j+1}$. Es werden also alle Elemente $u_k$ und $v_k$ mit $k \geqq j$
285 vertauscht. $j = m$ bezeichnet den Fall, in dem das größte Element der
286 "`linken"' Folge, $u_{m-1}$, kleiner ist als das kleinste Element der
287 "`rechten"' Folge, $v_{m-1}$. Daraus folgt, dass die entstehende Folge aus
288 zwei bitonen Folgen besteht, die rekursiv zusammengeführt werden können.
289 Abbildung~\ref{fig:bitonic-merge-normal} zeigt die Situationen vor und nach
290 diesem Schritt des Mischers.
292 Mit dem bitonen Mischer auch zwei aufsteigend sortierte Folgen sortiert
293 werden. Dazu ist lediglich das "`Umbenennen"' der Leitungen notwendig.
294 Abbildung~\ref{fig:bitonic-merge-tricheter} zeigt das Schema des bitonen
295 Mischers für zwei aufsteigend sortierte Foglen. Durch das Umbenennen verändert
296 sich das Muster der Komparatoren ein wenig: Statt an eine Treppe erinnert das
297 Muster nun an einen Trichter.
299 \subsubsection{Batcher's Bitonic-Mergesort-Netzwerk}
301 Das Sortiernetzwerk $S(n)$ mit $n$~Eingängen besteht aus zwei Instanzen von
302 $S(\frac{n}{2})$, dem Netzwerk mit $\frac{n}{2}$~Eingängen, und dem bitonen
303 Mischer $M(n)$. Die Rekursion bricht bei ${n = 1}$~ab -- eine einelementige
304 Liste ist immer sortiert.
305 Das konkrete Netzwerk~$S(8)$ ist in Abbildung~\ref{fig:batcher_08} zu sehen.
306 Eingezeichnet sind ebenfalls die beiden Instanzen des Netzwerks~$S(4)$ (rot)
307 sowie der bitone Mischer~$M(8)$ (blau).
311 %\includegraphics[viewport=115 491 372 782,width=7.5cm]{images/sn-rekursiver-aufbau.pdf}
313 %\caption{Rekursiver Aufbau von $S(n)$: Es besteht aus zwei Instanzen von
314 %$S(n/2)$ und dem Mischer $M(n)$.}
315 %\label{fig:bms_rekursiver_aufbau}
320 \input{images/batcher-8.tex}
322 \caption{$S(8)$, Batcher's {\em bitone Mergesort-Netzwerk} für acht
323 Eingänge. Markiert sind die beiden Instanzen von $S(4)$ (rot), die beiden
324 bitonen Mischer~$M(4)$ (blau) und die Komparatoren, die im letzten rekursiven
325 Schritt hinzugefügt wurden (grün).}
326 \label{fig:batcher_08}
329 \subsection{Odd-Even-Mergesort}
331 Obwohl der Name ähnlich klingt, haben {\em Odd-Even-Mergesort} (OEM) und
332 {\em Odd-Even-Transpositionsort} (OET, siehe
333 Abschnitt~\ref{sect:odd_even_transpositionsort}) wenig gemein. Auch dieses
334 Netzwerk ist von K.~Batcher gefunden worden und wird rekursiv durch einen
335 "`Mischer"' definiert.
337 \subsubsection{Der Odd-Even-Mischer}\label{sect:der_odd_even_mischer}
339 Der {\em Odd-Even-Mischer} ist ein Komperatornetzwerk, dass zwei sortierte
340 Folgen zu einer sortierten Ausgabe zusammenfügen kann. Dabei kommt es mit
341 weniger Vergleichen aus als der {\em bitone Mischer}, der im
342 Abschnitt~\ref{sect:der_bitone_mischer} vorgestellt wurde.
344 Der {\em Odd-Even-Mischer} selbst ist ebenfalls rekursiv aufgebaut: Die
345 Eingabe für den Mischer mit $N = n + m$ Leitungen besteht aus den beiden
346 sortierten Folgen $U = \left(u_0, u_1, \ldots, u_{n-1}\right)$ und
347 $V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die gesamte Eingabe sei
348 $W = \left(w_0, w_1, \ldots, w_{N-1}\right)$ mit:
350 w_i = \left\{ \begin{array}{ll}
359 \input{images/oe-merge.tex}
361 \caption{Schematischer Aufbau des {\em Odd-Even} Mischers. Im Vergleich zum
362 bitonen Mischer für Acht kommt dieses Schema mit einem Komparator weniger
363 aus. Der Effekt wird duch den rekursiven Aufbau noch verstärkt.}
367 Diese werden jetzt in insgesamt vier sortierte Folgen aufgeteilt, je eine
368 Liste der geraden Indizes und je eine Liste der ungeraden Indizes.
370 U_{\textrm{gerade}} &=& \left(u_0, u_2, u_4, \ldots\right) \\
371 U_{\textrm{ungerade}} &=& \left(u_1, u_3, u_5, \ldots\right) \\
372 V_{\textrm{gerade}} &=& \left(v_0, v_2, u_4, \ldots\right) \\
373 V_{\textrm{ungerade}} &=& \left(v_1, v_3, u_5, \ldots\right)
376 Die geraden Folgen $U_{\textrm{gerade}}$ und $V_{\textrm{gerade}}$ bzw. die
377 ungeraden Folgen $U_{\textrm{ungerade}}$ und $V_{\textrm{ungerade}}$ werden
378 rekursiv von kleineren {\em Odd-Even-Mischern} zusammengefügt, so dass sich am
379 Ausgang der Mischer die Folgen
381 W_{\textrm{gerade}} &=& \left(w_0, w_2, w_4, \ldots\right) \\
382 W_{\textrm{ungerade}} &=& \left(w_1, w_3, w_5, \ldots\right)
386 Anschließend werden die Komparatoren zwischen benachbarten Leitungen
389 w_{2i-1} \longleftrightarrow w_{2i}, \quad 1 \leqq i < \frac{N}{2}
391 die die Folge~$W$ sortieren. Den schematischen Aufbau des {\em
392 Odd-Even-Mischers} zeigt Abbildung~\ref{fig:oe-merge}.
394 Leider bricht die Rekursion nicht so schön ab, wie das beim {\em bitonen
395 Mischer} der Fall gewesen ist. Insbesondere für ${n = m = 1}$ würde --
396 entsprechend der Konstruktionsvorschrift -- ein leeres Netzwerk entstehen, was
397 offensichtlich nicht korrekt wäre. Die Abbruchbedingungen für den rekursiven
400 \item Falls ${n = 0}$ oder ${m = 0}$: Das Netzwerk ist leer.
401 \item Falls ${n = 1}$ und ${m = 1}$: Das Netzwerk besteht aus einem
402 einzelnen Komparator.
405 Dass die resultierende Folge sortiert ist, lässt sich mit dem
406 {\em 0-1-Prinzip} leicht zeigen:
407 Da $U$ und $V$ sortiert sind, ist die Anzahl der Nullen in den geraden
408 Teilfolgen, $U_{\textrm{gerade}}$ bzw. $V_{\textrm{gerade}}$, größer oder
409 gleich der Anzahl der Nullen in den ungeraden Teilfolgen
410 $U_{\textrm{ungerade}}$ bzw. $V_{\textrm{ungerade}}$ -- die Einsen verhalten
411 sich entsprechend umgekehrt. Das trifft demnach auch auf die Folgen
412 $W_{\textrm{gerade}}$ und $W_{\textrm{ungerade}}$ entsprechend zu:
414 \left|W_{\textrm{gerade}}\right|_0
415 &=& \left|U_{\textrm{gerade}}\right|_0
416 + \left|V_{\textrm{gerade}}\right|_0
417 = \left\lceil \frac{1}{2} \left|U\right|_0 \right\rceil
418 + \left\lceil \frac{1}{2} \left|V\right|_0 \right\rceil \\
419 \left|W_{\textrm{ungerade}}\right|_0
420 &=& \left|U_{\textrm{ungerade}}\right|_0
421 + \left|V_{\textrm{ungerade}}\right|_0
422 = \left\lfloor \frac{1}{2} \left|U\right|_0 \right\rfloor
423 + \left\lfloor \frac{1}{2} \left|V\right|_0 \right\rfloor
425 Daraus folgt, dass $W_{\textrm{gerade}}$ $0$, $1$ oder $2$ Nullen mehr enthält
426 als $W_{\textrm{ungerade}}$. In den ersten beiden Fällen ist die "`verzahnte"'
427 Ausgabe der beiden kleineren Mischer bereits sortiert. Nur im letzten Fall,
428 wenn $W_{\textrm{gerade}}$ $2$~Nullen mehr enthählt als
429 $W_{\textrm{ungerade}}$, muss eine Vertauschung stattfinden, um die Ausgabe zu
430 sortieren. Die jeweiligen Situationen sind in
431 Abbildung~\ref{fig:oe-post-recursive} dargestellt.
435 \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 0$]{\input{images/oe-post-recursive-diff0.tex}}
437 \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 1$]{\input{images/oe-post-recursive-diff1.tex}}
439 \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 2$]{\input{images/oe-post-recursive-diff2.tex}}
440 \caption{Die drei Situationen, die nach dem Verzahnen der Ausgaben der
441 kleineren {\em Odd-Even-Mischer} entstehen können. Ist die Differenz der
442 Anzahl der Nullen gleich $0$ oder $1$, ist die Folge bereits sortiert. Im
443 letzten Fall stellt einer der Komparatoren sicher, dass das Ergebnis
445 \label{fig:oe-post-recursive}
448 \subsubsection{Das Odd-Even-Mergesort-Netzwerk}
450 Auch beim {\em Odd-Even-Mergesort-Netzwerk} -- wie beim {\em bitonen
451 Mergesort-Netzwerk} -- entsteht das Sortiernetzwerk aus dem {\em
452 Odd-Even-Mischer} durch resursives Anwenden auf einen Teil der Eingabe
453 (üblicherweise die Hälfte der Leitungen) und anschließendes zusammenfügen.
454 Abbildung~\ref{fig:odd_even_mergesort_08} zeigt das Netzwerk für $8$~Eingänge.
458 \input{images/oe-mergesort-8.tex}
460 \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge.}
461 \label{fig:odd_even_mergesort_08}
465 \item Odd-Even-Transpositionsort
466 \item Bitonic-Mergesort
467 \item Odd-Even-Mergesort
468 \item Pairwise sorting-network
471 \section{Transformation von Sortiernetzwerken}
474 \item Komprimieren (Alle Komparatoren so früh wie möglich anwenden).
475 \item Normalisieren (Transformation zu Standard-Sortiernetzwerken).
478 \subsection{Zwei Netzwerke kombinieren}
481 \item Mit dem Bitonic-Merge
482 \item Mit dem Odd-Even-Merge
483 \item Nach dem Pairwise sorting-network Schema.
486 \subsection{Leitungen entfernen}\label{sect:leitungen_entfernen}
488 Man kann ein gegebenes Sortiernetzwerk mit $n$~Eingängen auf ein
489 Sortiernetzwerk mit $(n-1)$~Leitungen verkleinern, indem man eine Leitung
490 entfernt. Zunächst wird angenommen, dass das Minimum oder das Maximum an einem
491 der Eingänge anliegt. Der Weg durch das Netzwerk zum entsprechenden Ausgang
492 ist dadurch fest vorgegeben, insbesondere welche Komparatoren dafür sorgen,
493 dass die Leitung gewechselt wird und welche nicht.
494 Abbildung~\ref{fig:oe-transposition-cut0} zeigt den Weg eines Maximums durch
495 das {\em Odd-Even-Transpositionsort-Netzwerk}.
497 Im nächsten Schritt werden alle beteiligten Komparatoren gelöscht bzw.
498 ersetzt: Komparatoren, die {\em nicht} zu einem Wechsel der Leitung geführt
499 haben, werden ersatzlos gelöscht. Diese Komparatoren sind in
500 Abbildung~\ref{fig:oe-transposition-cut0} grün markiert. Die Komparatoren, die
501 zum Wechsel der Leitung geführt haben, werden durch sich kreuzende Leitungen
502 ersetzt. Das Resultat zeigt Abbildung~\ref{fig:oe-transposition-cut1}. Wenn
503 man die Maximum-Leitung entfernt (Abbildung~\ref{fig:oe-transposition-cut2}),
504 erhält man ein Sortiernetzwerk für $(n-1)$~Leitungen.
508 \subfigure[foo]{\input{images/oe-transposition-cut0.tex}\label{fig:oe-transposition-cut0}}
509 \subfigure[bar]{\input{images/oe-transposition-cut1.tex}\label{fig:oe-transposition-cut1}}
510 \subfigure[baz]{\input{images/oe-transposition-cut2.tex}\label{fig:oe-transposition-cut2}}
511 \subfigure[qux]{\input{images/oe-transposition-cut3.tex}\label{fig:oe-transposition-cut3}}
512 \caption{Eine Leitung wird aus dem {\em Odd-Even-Transpositionsort} Netzwerk
513 $\textrm{OET}(8)$ entfernt: Auf der rot markierten Leitung wird $\infty$
514 angelegt. Da der Wert bei jedem Komparator am unteren Ende herauskommt, ist
515 der Pfad fest vorgegeben. Da die restlichen Werte trotzdem noch richtig
516 sortiert werden müssen, kann dieser Pfad herausgetrennt werden. In der
517 letzten Abbildung ist $\textrm{OET}(7)$ markiert.}
520 Die letzte Abbildung, \ref{fig:oe-transposition-cut3}, zeigt das
521 Sortiernetzwerk wieder mit den üblichen geraden Leitungen und die rot
522 markierten Komparatoren wurden verschoben, so dass sich eine kompaktere
523 Darstellung ergibt. Ausserdem ist das
524 {\em Odd-Even-Transpositionsort-Netzwerk} für sieben Werte markiert. Der
525 zusätzliche Komparator vor dem $\textrm{OET}(7)$ hat keinen Einfluss auf die
526 Ausgabe und kann entfernt werden.
533 \section{Der evolutionäre Ansatz}
535 Um einen evolutionären Algorithmus für Sortiernetzwerke zu entwickeln, werden
536 die vorgestellten Methoden kombiniert.
538 \subsection{Bewertungsfunktion}
540 Um Sortiernetzwerke überhaupt optimieren zu können, muss zunächst die
541 {\em Güte} eines Netzwerkes definiert werden. Prinzipiell gibt es zwei Ziele,
542 die interessant sind:
544 \item Möglichst wenige Komparatoren ("`klein"')
545 \item Möglichst wenige Schichten ("`schnell"')
548 Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das
549 kleinste bekannte Sortiernetzwerk für 16~Eingänge besteht aus 60~Komparatoren
550 in 10~Schichten. Das schnellste Netzwerk besteht aus 61~Komparatoren in nur
553 Eine Gütefunktion, die die beiden Ziele "`klein"' und "`schnell"'
554 berücksichtigen kann, hat die folgende allgemeine Form:
556 \mathit{Guete}(S) = w_{\mathrm{Basis}}
557 + w_{\mathrm{Komparatoren}} \cdot \left|S\right|_\mathrm{Komparatoren}
558 + w_{\mathrm{Schichten}} \cdot \left|S\right|_\mathrm{Schichten}
560 Die Parameter $w_{\mathrm{Komparatoren}}$ und $w_{\mathrm{Schichten}}$ dienen
561 dabei der Festlegung des Optimierungsziels. Wenn einer der beiden Parameter
562 gleich Null ist, wird nur das jeweils andere Ziel verfolgt. Sind beide
563 Parameter gleich Null, werden alle Netzwerke mit der gleich Güte bewertet --
564 jegliche Ergebnisse sind dann rein zufälliger Natur.
566 Mit dem Parameter $w_{\mathrm{Basis}}$ kann auf die Selektion Einfluss
567 genommen werden. Ist er groß, wird der relative Unterschied der Güten
568 verschiedener Netzwerke kleiner, was die {\em Exploration}, das Absuchen des
569 gesamten Lösungsraums, begünstigt. Wählt man $w_{\mathrm{Basis}}$ hingegen
570 klein, in Abhängigkeit von den anderen beiden Parametern sind auch negative
571 Werte möglich, werden die relativen Unterschiede groß. Dadurch wird die {\em
572 Exploitation}, das Finden lokaler Optima, bevorzugt.
574 \subsection{Selektion}
578 \subsection{Rekombination}
580 Bei der Rekombination werden zwei Individuen -- hier Sortiernetzwerke -- zu
581 einer neuen Lösung kombiniert. Dazu verwenden wir einen Mischer, zum Beispiel
582 den {\em bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) oder den
583 {\em Odd-Even-Mischer} (Abschnitt~\ref{sect:der_odd_even_mischer}), um die
584 beiden Netzwerke zu einem Netzwerk mit $2n$~Leitungen zusammenzufügen.
585 Anschließend entfernen wir zufällig $n$~Leitungen wie in
586 Abschnitt~\ref{sect:leitungen_entfernen} beschrieben.
588 Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft
591 \subsection{Mutation}
593 {\em Mutation ist schwierig, weil es die Sortiereigenschaft eben nicht
598 \item Güte von Sortiernetzwerken (Anzahl der Komparatoren, Anzahl der
599 Schichten, kobiniert)
600 \item Rekombination: Merge Anhängen und Leitungen entfernen.
603 Ein Beispielnetzwerk, das von dem Algorithmus gefunden wird, zeigt
604 Abbildung~\ref{fig:evolutionary_08}.
608 \input{images/evolutionary-08.tex}
610 \caption{Ein mit dem evolutionären Algorithmus erzeugtes Sortiernetzwerk mit
611 acht Eingängen. Es besteht aus 19~Komparatoren in 6~Schichten.}
612 \label{fig:evolutionary_08}
617 \input{images/08-e2-1237993371.tex}
619 \caption{\tt images/08-e2-1237993371.tex}
620 \label{fig:08-e2-1237993371}
625 \input{images/09-e2-1237997073.tex}
627 \caption{\tt images/09-e2-1237997073.tex}
628 \label{fig:09-e2-1237997073}
633 \input{images/09-e2-1237999719.tex}
635 \caption{\tt images/09-e2-1237999719.tex}
636 \label{fig:09-e2-1237999719}
641 \input{images/10-e2-1239014566.tex}
643 \caption{{\tt images/10-e2-1239014566.tex}: 29~Komparatoren in 8~Schichten}
644 \label{fig:10-e2-1239014566}
649 \section{Shmoo-Äquivalenz}
651 Die folgenden 16-Eingang-Sortiernetzwerke wurden alle mit dem
652 \emph{Algorithmus~1} gefunden. Sie haben alle 63~Komparatoren in 10~Schichten,
653 jeweils die selbe Anzahl wie Odd-Even-Mergesort.
655 Um wiederkehrende Muster in den hinteren Schichten der erzeugten
656 Sortiernetzwerke besser untersuchen zu können, wurden die erzeugten Netzwerke
657 in Gruppen aufgeteilt. Zwei Netzwerke befinden sich dann in der selben
658 Gruppen, wenn die Nullen bzw. Einsen, die auf einer Leitung vorkommen können,
659 nach der 5.~Schicht (Schicht~4, da bei Null mit dem Zählen begonnen wird)
660 nicht mehr ändert. Das heißt, dass die Schichten 0--4 unterschiedlich
661 aufgebaut sind, aber den selben Effekt erziehlen. Die Schichten 5--9 sind
662 hingegen innerhalb einer Gruppe austauschbar und oft (immer?) identisch.
664 Die Anzahl der Netzwerke in den jeweiligen Gruppen ist unterschiedlich. Zur
665 Zeit sind in den Gruppen so viele Netzwerke:\\
666 \begin{tabular}{|l|r|r|} \hline
667 Gruppe~0 & 18 & $48,7\%$ \\
668 Gruppe~1 & 9 & $24,3\%$ \\
669 Gruppe~2 & 6 & $16,2\%$ \\
670 Gruppe~3 & 3 & $8,1\%$ \\
671 Gruppe~4 & 1 & $2,7\%$ \\ \hline
674 Die hinteren Schichten zwischen den Gruppen~1 und~3 schauen so aus, als wären
675 sie nur gespiegelt. Warum kommt Gruppe~1 aber viel häufiger vor? Ggf. eine
676 Konsequenz aus dem Normieren?
678 Dito für die Gruppen~2 und~4. Warum ist die eine häufiger?
680 Ist Gruppe~0 symmetrisch bzgl. der Leitungen?
686 \input{images/16-e1/group0/16-e1-1258009316.tex}
688 \caption{{\tt images/16-e1/group0/16-e1-1258009316.tex}: 63~Komparatoren in
690 \label{fig:16-e1-1258009316}
695 \input{images/16-e1/group0/16-e1-1258010866.tex}
697 \caption{{\tt images/16-e1/group0/16-e1-1258010866.tex}: 63~Komparatoren in
699 \label{fig:16-e1-1258010866}
704 \input{images/16-e1/group0/16-e1-1258011861.tex}
706 \caption{{\tt images/16-e1/group0/16-e1-1258011861.tex}: 63~Komparatoren in
708 \label{fig:16-e1-1258011861}
713 \input{images/16-e1/group0/16-e1-1259060992.tex}
715 \caption{{\tt images/16-e1/group0/16-e1-1259060992.tex}: 63~Komparatoren in
717 \label{fig:16-e1-1259060992}
722 %\input{images/16-e1/group0/16-e1-1259061148.tex}
724 %\caption{{\tt images/16-e1/group0/16-e1-1259061148.tex}: 63~Komparatoren in
726 %\label{fig:16-e1-1259061148}
733 \input{images/16-e1/group1/16-e1-1258009982.tex}
735 \caption{{\tt images/16-e1/group1/16-e1-1258009982.tex}: 63~Komparatoren in 10~Schichten.
736 Schichten 4--9 identisch zu 16-e1-1258030047 (Gruppe~1).}
737 \label{fig:16-e1-1258009982}
742 \input{images/16-e1/group1/16-e1-1258010023.tex}
744 \caption{{\tt images/16-e1/group1/16-e1-1258010023.tex}: 63~Komparatoren in
746 \label{fig:16-e1-1258010023}
751 \input{images/16-e1/group1/16-e1-1258029734.tex}
753 \caption{{\tt images/16-e1/group1/16-e1-1258029734.tex}: 63~Komparatoren in
755 \label{fig:16-e1-1258029734}
760 \input{images/16-e1/group1/16-e1-1258030047.tex}
762 \caption{{\tt images/16-e1/group1/16-e1-1258030047.tex}: 63~Komparatoren in
764 \label{fig:16-e1-1258030047}
769 %\input{images/16-e1/group1/16-e1-1258034768.tex}
771 %\caption{{\tt images/16-e1/group1/16-e1-1258034768.tex}: 63~Komparatoren in
773 %\label{fig:16-e1-1258034768}
780 \input{images/16-e1/group2/16-e1-1258029063.tex}
782 \caption{{\tt images/16-e1/group2/16-e1-1258029063.tex}: 63~Komparatoren in
784 \label{fig:16-e1-1258029063}
789 \input{images/16-e1/group2/16-e1-1258034821.tex}
791 \caption{{\tt images/16-e1/group2/16-e1-1258034821.tex}: 63~Komparatoren in
793 \label{fig:16-e1-1258034821}
798 \input{images/16-e1/group2/16-e1-1259054993.tex}
800 \caption{{\tt images/16-e1/group2/16-e1-1259054993.tex}: 63~Komparatoren in
802 \label{fig:16-e1-1259054993}
807 \input{images/16-e1/group2/16-e1-1259058588.tex}
809 \caption{{\tt images/16-e1/group2/16-e1-1259058588.tex}: 63~Komparatoren in
811 \label{fig:16-e1-1259058588}
816 %\input{images/16-e1/group2/16-e1-1259063485.tex}
818 %\caption{{\tt images/16-e1/group2/16-e1-1259063485.tex}: 63~Komparatoren in
820 %\label{fig:16-e1-1259063485}
825 %\input{images/16-e1/group2/16-e1-1259063618.tex}
827 %\caption{{\tt images/16-e1/group2/16-e1-1259063618.tex}: 63~Komparatoren in
829 %\label{fig:16-e1-1259063618}
836 \input{images/16-e1/group3/16-e1-1258012027.tex}
838 \caption{{\tt images/16-e1/group3/16-e1-1258012027.tex}: 63~Komparatoren in
840 \label{fig:16-e1-1258012027}
845 \input{images/16-e1/group3/16-e1-1258037039.tex}
847 \caption{{\tt images/16-e1/group3/16-e1-1258037039.tex}: 63~Komparatoren in
849 \label{fig:16-e1-1258037039}
854 \input{images/16-e1/group3/16-e1-1259065042.tex}
856 \caption{{\tt images/16-e1/group3/16-e1-1259065042.tex}: 63~Komparatoren in
858 \label{fig:16-e1-1259065042}
865 \input{images/16-e1/group4/16-e1-1259060520.tex}
867 \caption{{\tt images/16-e1/group4/16-e1-1259060520.tex}: 63~Komparatoren in 10~Schichten.
869 \label{fig:16-e1-1259060520}
874 \input{images/16-e1/group4/16-e1-1259067171.tex}
876 \caption{{\tt images/16-e1/group4/16-e1-1259067171.tex}: 63~Komparatoren in 10~Schichten.
878 \label{fig:16-e1-1259067171}
884 \item So gut kann man mindestens werden {\em ($\rightarrow$ Bitonic-Mergesort, vermute ich)}.
885 \item Wie gut die Netzwerke werden, hängt stark vom verwendeten \em{Mischer} ab.
888 \subsection{Vom evolutionären Algorithmus zu einer Markov-Kette}
891 \item Kombiniere immer das aktuelle Netzwerk mit sich selbst.
892 \item Kann die Mindestgüte immernoch erreicht werden? ({\em Ich denke schon.})
893 \item Anzahl der erreichbaren Sortiernetzwerke.
896 \section{Empirische Beobachtungen}
899 \item So schnell konvergiert der Algorithmus.
905 Das würde mir noch einfallen$\ldots$
907 %\bibliography{references}
908 %\bibliographystyle{plain}
914 % vim: set shiftwidth=2 softtabstop=2 tabstop=8 fdm=marker tw=78 :