diplomarbeit.tex

   1 \documentclass[a4paper,10pt]{article}
   2 \usepackage[utf8]{inputenc}
   3 \usepackage{ngerman}
   4 \usepackage{fancyhdr}
   5 \usepackage{geometry}
   6 \usepackage{amsmath, bbm}
   7 \usepackage{amsfonts}
   8 \usepackage{amssymb}
   9 \usepackage{listings}
  10 \usepackage{graphicx}
  11 \usepackage{url}
  12 %\usepackage{longtable}
  13 \usepackage{subfigure}
  14 \usepackage{icomma}
  15
  16 \usepackage{tikz}
  17 \usetikzlibrary{arrows,shapes}
  18
  19 % Fuer mathtoolsset
  20 \usepackage{mathtools}
  21
  22 \geometry{paper=a4paper,margin=25mm}
  23
  24 \pagestyle{fancy}
  25 %\fancyhf{}
  26 %\fancyhead[LO,LE]{"Ubung zu Computational Intelligence}
  27 %\fancyhead[CO,CE]{2006-05-15}
  28 %\fancyhead[RO,RE]{Florian Forster (2099894)}
  29
  30 \title{Evolutionäre Optimierung von Sortiernetzwerken}
  31 \author{Florian Forster}
  32 \date{\today}
  33
  34 \newcommand{\false}{\textsc{False}}
  35 \newcommand{\true}{\textsc{True}}
  36 \newcommand{\todo}[1]{{\bf TODO:} #1}
  37 \newcommand{\qed}{\hfill $\Box$ \par \bigskip}
  38
  39 \newtheorem{definition}{Definition}
  40 \newtheorem{satz}{Satz}
  41
  42 % Zeige Nummern nur bei referenzierten Gleichungen an.
  43 \mathtoolsset{showonlyrefs=true}
  44
  45 \begin{document}
  46
  47 \tikzstyle{vertex}   = [circle,draw,thick,fill=black,minimum size=5pt,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]
  54
  55 \maketitle
  56 \begin{abstract}
  57 Sortiernetzwerke werden eingeführt und einige bekannte Konstruktionen werden
  58 vorgestellt (Off-Even-Transposition, Bitonic-Merge, Odd-Even-Merge, Pairwise).
  59 Transformationsmöglichkeiten für Sortiernetzwerke werden besprochen.
  60 Evolutionäre Algorithmen werden beschrieben und ein evolutionärer
  61 Algorithmus für die Optimierung von Sortiernetzwerken wird angegeben.
  62 Die mindestens von diesem Algorithmus erreichte Güte wird angegeben und die
  63 Transformation zu einer Markov-Kette wird gezeigt. {\em Natürlich: So fern ich
  64 das hinbekomme bzw. Recht behalte.}
  65 \end{abstract}
  66 \newpage
  67
  68 \tableofcontents
  69 \newpage
  70
  71 \section{Motivation und Einleitung}
  72
  73 \subsection{Motivation}\label{sect:motivation}
  74
  75 \begin{itemize}
  76 \item Sortiernetzwerke sind toll, weil $\ldots$
  77 \item Sortiernetzwerke sind einfach erklärt, aber trotzdem kompliziert.
  78 \item Bisher noch kein evolutionärer Algorithmus zur automatischen
  79   Optimierung von Sortiernetzwerken bekannt. \textit{(Glaube ich zumindest.)}
  80 \end{itemize}
  81
  82 \subsection{Einleitung}\label{sect:einleitung}
  83
  84 \subsubsection{Sortiernetzwerke}\label{sect:einleitung_sortiernetzwerke}
  85
  86 {\em Komparatoren} sind die Bausteine, die {\em Sortiernetzwerken} zugrunde
  87 liegen. Sie haben zwei Eingänge über die sie zwei Zahlen erhalten können.
  88 Ausserdem besitzt ein {\em Komparator} zwei Ausgänge, die im Gegensatz zu den
  89 Eingängen unterscheidbar sind: Die grö"sere der beiden Zahlen wird immer auf
  90 dem einen, die kleinere der beiden Zahlen immer auf dem anderen Ausgang
  91 ausgegeben.
  92
  93 Wenn man nun mehrere {\em Komparatoren} miteinander kombiniert, also die
  94 Ausgänge von {\em Komparatoren} mit dem Eingängen anderer {\em Komparatoren}
  95 verbindet, erhält man ein {\em Komparatornetzwerk}.
  96
  97 \begin{figure}
  98 \begin{center}
  99 \input{images/einfaches_komparatornetzwerk.tex}
 100 \end{center}
 101 \caption{Einfaches Komparatornetzwerk mit vier Ein- bzw. Ausgängen, bestehend
 102 aus 5~Komparatoren.}
 103 \label{fig:einfaches_komparatornetzwerk}
 104 \end{figure}
 105
 106 Abbildung~\ref{fig:einfaches_komparatornetzwerk} zeigt ein einfaches
 107 Komparatornetzwerk aus fünf Komparatoren in der üblichen Darstellungsweise:
 108 Die horizontalen Linien stellen Leitungen von den Eingängen auf der linken
 109 Seite zu den Ausgängen auf er rechten Seite dar. Die vertikalen Pfeile
 110 symbolisieren die Komparatoren, die die Werte "`auf den Leitungen"'
 111 vergleichen und ggf. vertauschen. Nach einem Komparator befindet sich die
 112 kleinere Zahl immer auf der Leitung, auf die der Pfeil zeigt, die größere Zahl
 113 befindet sich auf der Leitung auf der der Pfeil seinen Ursprung hat.
 114
 115 Komparatornetzwerke, die für jede beliebige Eingabepermutation eine
 116 Ausgabe erzeugen, die der Sortierung der Eingabe entspricht, heißen
 117 {\em Sortiernetzwerke}. Das in
 118 Abbildung~\ref{fig:einfaches_komparatornetzwerk} gezeigte Komparatornetzwerk
 119 ist kein Sotiernetzwerk: Die Eingabefolge ${(1, 2, 3, 4)}$ würde zur Ausgabe
 120 ${(2, 1, 3, 4)}$ führen -- die bestehenden Sortierung wird also sogar
 121 zerstört.
 122
 123 Zu beweisen, dass ein gegebenes Komparatornetzwerk die Sortiereigenschaft
 124 {\em nicht} hat, ist mit einem gegebenen Gegenbeispiel also einfach möglich.
 125 Dieses Gegenbeispiel zu finden ist allerdings aufwendig.
 126
 127 \todo{Wie findet man die Gegenbeispiele? Die {\em Entscheidung}, ob ein
 128 Netzwerk sortiert, ist doch NP-vollständig, also müsste doch das Finden eines
 129 Gegenbeispiels im Allgemeinen auch exponentialle Laufzeit haben..?}
 130 \todo{Wenn die {\em Entscheidung}, ob ein Netzwerk sortiert, NP-vollständig
 131 ist, müsse man dann nicht einen Zeugen für die Sortiereigenschaft angeben
 132 können?}
 133
 134 \todo{$0-1$-Prinzip}
 135
 136 Sortiernetzwerke:
 137 \begin{itemize}
 138 \item Ein Komparator-Netzwerk ist $\ldots$
 139 \item Ein Komparator-Netzwerk ist ein Sortiernetzwerk, wenn $\ldots$
 140 \item Die Frage nach der Sortiereigenschaft ist NP-vollständig.
 141 \end{itemize}
 142
 143 \subsubsection{Evolutionäre Algorithmen}
 144
 145 Viele {\em kombinatorische Optimierungsprobleme} sind schwer zu lösen -- die
 146 entsprechenden Entscheidungsprobleme liegen oft in der Komplexitätsklasse
 147 $NP$, sind also mit bekannten Verfahren nicht effizient exakt lösbar. Sollte
 148 sich herausstellen, dass diese Probleme nicht in der Komplexitätsklasse $P$
 149 liegen, wäre eine Konsequenz, dass es effiziente exakte Algorithmen für diese
 150 Probleme nicht geben kann. Falls sich hingegen herausstellt, dass diese
 151 Probleme in der Komplexitätsklasse~$P$ liegen, wird es mit großer
 152 Wahrscheinlichkeit noch einige Zeit dauern bis auch Algorithmen mit
 153 praktikablen Zeitkonstanten gefunden werden.
 154
 155 Aus diesem Grund besteht die Notwendigkeit einen Kompromiss einzugehen: Statt
 156 die bzw. eine der {\em optimalen} Lösungen als einzige Ausgabe des Algorithmus
 157 zuzulassen, wird eine "`möglichst gute"' Lösung ausgegeben. Viele dieser
 158 Optimierungsalgorithmen orientieren sich an Vorgängen in der Natur,
 159 beispielsweise immitieren die "`Ameisenalgorithmen"' das Verhalten von Ameisen
 160 auf der Futtersuche um kurze Rundreisen auf Graphen zu berechnen.
 161
 162 Bei {\em Evolutionären Algorithmen} stand die Evolution pate. Die Grundidee
 163 ist es, bestehende Lösungen zu neuen, unter Umständen besseren Lösungen zu
 164 kombinieren. Dabei bedient man sich der in der Evolutionstheorie etablierten
 165 Nomenklatur, beispielsweise werden konkrete Lösungen für ein Problem häufig
 166 als {\em Individuum} bezeichnet.
 167
 168 Die Vorgehensweise lässt sich abstrakt wie folgt beschreiben. Aus einer
 169 bestehenden Lösungsmenge, der {\em Population} werden zufällig Lösungen
 170 ausgesucht ({\em Selektion}) und zu einer neuen Lösung kombiniert ({\em
 171 Rekombination}). Unter Umständen wird die neue Lösung noch zufällig
 172 verändert ({\em Mutation}), bevor sie in die bestehende Lösungsmenge
 173 integriert wird. Die Wahrscheinlichkeiten, beispielsweise bei der {\em
 174 Selektion}, sind dabei nicht zwangsläufig gleichverteilt -- üblicherweise
 175 werden bessere Lösungen bevorzugt. Zur Bewertung die die sogenannte {\em
 176 Gütefunktion}.
 177
 178 Nicht alle Probleme eignen sich für diese Strategie: Zum einen muss es möglich
 179 sein, eine initiale Population zur Verfügung zu stellen, da diese als Basis
 180 aller weiteren Operationen dient. Das ist häufig keine große Einschränkung, da
 181 es oft einfach ist {\em irgendeine} Lösung anzugeben. Zum anderen muss eine
 182 Methode für die Rekombination existieren. Das insbesondere dann problematisch
 183 wenn {\em Nebenbedingungen} eingehalten werden müssen.
 184
 185 \begin{itemize}
 186 \item Unter einem "`Evolutionären Algorithmus"' versteht man $\ldots$
 187 \item Da die Sortiereigenschaft zu überprüfen NP-schwer ist, ist die
 188 Mutation \textit{(vermutlich)} nicht (effizient) möglich.
 189 \end{itemize}
 190
 191 \section{Bekannte konstruktive Sortiernetzwerke}
 192
 193 Übersicht über bekannte konstruktive Sortiernetzwerke.
 194
 195 \subsection{Odd-Even-Transpositionsort}
 196 \label{sect:odd_even_transpositionsort}
 197
 198 Das Sortiernetzwerk {\em Odd-Even-Transpositionsort} (OET) ist eines der
 199 einfachsten Sortiernetzwerke. Es besteht aus $n$~{\em Schichten}, die jede
 200 "`Leitung"' abwechselnd mit den benachbarten Leitungen verbindet.
 201 Abbildung~\ref{fig:odd_even_transposition_08} zeigt das OET-Netzwerk für
 202 ${n = 8}$.
 203
 204 \begin{figure}
 205 \begin{center}
 206 \input{images/oe-transposition-8.tex}
 207 \end{center}
 208 \caption{Das {\em Odd-Even-Transpositionsort} Netzwerk für acht Eingänge.}
 209 \label{fig:odd_even_transposition_08}
 210 \end{figure}
 211
 212 \subsection{Batcher's Mergesort}
 213
 214 Ein Netzwerk von K.~E.~Batcher. Siehe:
 215 K.E. Batcher: Sorting Networks and their Applications. Proc. AFIPS Spring
 216 Joint Comput. Conf., Vol. 32, 307-314 (1968)
 217
 218 \subsubsection{Der bitone Mischer}
 219
 220 Das Netzwerk basiert auf dem {\em bitonen Mischer}, einem Komparator-Netzwerk,
 221 das eine beliebige bitone Folge in eine sortierte Listen umordnen kann. Eine
 222 {\em bitone Folge} ist eine monoton steigende Folge gefolgt von einer monoton
 223 fallenden Folge, oder ein zyklischer Shift davon.
 224 Abbildung~\ref{fig:beispiel-biton} zeigt die vier prinipiellen Möglichkeiten
 225 die durch zyklische Shifts entstehen können. Die wichtigsten Varianten für
 226 Batcher's Mergesort-Netzwerk zeigen die Abbildungen~\ref{fig:beispiel-biton-0}
 227 und~\ref{fig:beispiel-biton-1}. Sie erhält man, wenn man eine aufsteigend und
 228 eine absteigend sortierte Liste aneinanderhängt. Bei den
 229 anderen beiden Formen ist wichtig zu beachten, dass das letzte Element nicht
 230 größer (Abbildung~\ref{fig:beispiel-biton-2}) bzw. kleiner
 231 (Abbildung~\ref{fig:beispiel-biton-3}) als das erste Element der Folge sein
 232 darf.
 233
 234 \begin{figure}
 235   \centering
 236   \subfigure[aufsteigend, absteigend]{\input{images/beispiel-biton-0.tex}\label{fig:beispiel-biton-0}}
 237   \subfigure[absteigend, aufsteigend]{\input{images/beispiel-biton-1.tex}\label{fig:beispiel-biton-1}}
 238   \subfigure[aufsteigend, absteigend, aufsteigend]{\input{images/beispiel-biton-2.tex}\label{fig:beispiel-biton-2}}
 239   \subfigure[absteigend, aufsteigend, absteigend]{\input{images/beispiel-biton-3.tex}\label{fig:beispiel-biton-3}}
 240   \caption{Beispiele bitoner Folgen.}
 241   \label{fig:beispiel-biton}
 242 \end{figure}
 243
 244 \begin{figure}
 245   \centering
 246   \subfigure[normal]{\input{images/bitonic-merge.tex}\label{fig:bitonic-merge-normal}}
 247   \subfigure[trichter]{\input{images/bitonic-merge-trichter.tex}\label{fig:bitonic-merge-tricheter}}
 248   \caption{Schematischer Aufbau des bitonen Mischers: Jedes Element der
 249   aufsteigenden Folge $u_0, u_1, \ldots$ wird mit dem entsprechenden Element
 250   der absteigend sortierten Folge $v_0, v_1, \ldots$ verglichen. Die beiden
 251   resultierenden Teilfolgen sind wiederum biton.
 252   }
 253   \label{fig:bitonic-merge-schema}
 254 \end{figure}
 255
 256 Der Mischer funktioniert folgendermaßen: Gegeben sind zwei Folgen mit je
 257 ${m = \frac{n}{2}}$~Elementen, ${u_0, u_1, \ldots, u_{m-1}}$ und
 258 ${v_0, v_1, \ldots, v_{m-1}}$. Die Folge der $u_i$ sei aufsteigend sortiert,
 259 die Folge der $v_i$ sei absteigend sortiert:
 260 \begin{eqnarray}
 261  u_0 \leqq u_1 \leqq &\ldots& \leqq u_{m-1} \\
 262  v_0 \geqq v_1 \geqq &\ldots& \geqq v_{m-1}
 263 \end{eqnarray}
 264 Im ersten Schritt werden nun jeweils die Elemente an den gleichen relativen
 265 Positionen verglichen und ggf. vertauscht:
 266 \begin{equation}
 267 u_i \longleftrightarrow v_i, \quad 0 \leqq i < m
 268 \end{equation}
 269 Sei $j \in \{0 \ldots m\}$ der Index der ersten Elemente $u_j$ und $v_j$, die
 270 durch den gemeinsamen Komparator vertauscht werden. Unter der Annahme, dass
 271 Elemente nur vertauscht werden wenn, sie ungleich sind, muss ${u_j > v_j}$
 272 gelten. Mit $u_j \leqq u_{j+1}$ und $v_j \geqq v_{j+1}$ folgt daraus $u_{j+1}
 273 > v_{j+1}$. Es werden also alle Elemente $u_k$ und $v_k$ mit $k \geqq j$
 274 vertauscht. $j = m$ bezeichnet den Fall, in dem das größte Element der
 275 "`linken"' Folge, $u_{m-1}$, kleiner ist als das kleinste Element der
 276 "`rechten"' Folge, $v_{m-1}$. Daraus folgt, dass die entstehende Folge aus
 277 zwei bitonen Folgen besteht, die rekursiv zusammengeführt werden können.
 278 Abbildung~\ref{fig:bitonic-merge-normal} zeigt die Situationen vor und nach
 279 diesem Schritt des Mischers.
 280
 281 Mit dem bitonen Mischer auch zwei aufsteigend sortierte Folgen sortiert
 282 werden. Dazu ist lediglich das "`Umbenennen"' der Leitungen notwendig.
 283 Abbildung~\ref{fig:bitonic-merge-tricheter} zeigt das Schema des bitonen
 284 Mischers für zwei aufsteigend sortierte Foglen. Durch das Umbenennen verändert
 285 sich das Muster der Komparatoren ein wenig: Statt an eine Treppe erinnert das
 286 Muster nun an einen Trichter.
 287
 288 \subsubsection{Batcher's Bitonic-Mergesort-Netzwerk}
 289
 290 Das Sortiernetzwerk $S(n)$ mit $n$~Eingängen besteht aus zwei Instanzen von
 291 $S(\frac{n}{2})$, dem Netzwerk mit $\frac{n}{2}$~Eingängen, und dem bitonen
 292 Mischer $M(n)$. Die Rekursion bricht bei ${n = 1}$~ab -- eine einelementige
 293 Liste ist immer sortiert.
 294 Das konkrete Netzwerk~$S(8)$ ist in Abbildung~\ref{fig:batcher_08} zu sehen.
 295 Eingezeichnet sind ebenfalls die beiden Instanzen des Netzwerks~$S(4)$ (rot)
 296 sowie der bitone Mischer~$M(8)$ (blau).
 297
 298 %\begin{figure}
 299 %\begin{center}
 300 %\includegraphics[viewport=115 491 372 782,width=7.5cm]{images/sn-rekursiver-aufbau.pdf}
 301 %\end{center}
 302 %\caption{Rekursiver Aufbau von $S(n)$: Es besteht aus zwei Instanzen von
 303 %$S(n/2)$ und dem Mischer $M(n)$.}
 304 %\label{fig:bms_rekursiver_aufbau}
 305 %\end{figure}
 306
 307 \begin{figure}
 308 \begin{center}
 309 \input{images/batcher-8.tex}
 310 \end{center}
 311 \caption{$S(8)$, as {\em Batcher-Mergesort} Netzwerk für acht Eingänge.
 312 Markiert sind die beiden Instanzen von $S(4)$ (rot) und der bitone Mischer
 313 $M(8)$ (blau).}
 314 \label{fig:batcher_08}
 315 \end{figure}
 316
 317 \subsection{Odd-Even-Mergesort}
 318
 319 Obwohl der Name ähnlich klingt, haben {\em Odd-Even-Mergesort} (OEM) und
 320 Odd-Even-Transporisionsort (OET, siehe
 321 Abschnitt~\ref{sect:odd_even_transpositionsort}) wenig gemein. Auch dieses
 322 Netzwerk ist von K.~Batcher gefunden worden und wird rekursiv durch einen
 323 Mischer definiert.
 324
 325 Beispiel: Siehe Abbildung~\ref{fig:odd_even_mergesort_08}.
 326
 327 \begin{figure}
 328 \begin{center}
 329 \input{images/oe-mergesort-8.tex}
 330 \end{center}
 331 \caption{Das {\em Odd-Even-Mergesort} Netzwerk für acht Eingänge.}
 332 \label{fig:odd_even_mergesort_08}
 333 \end{figure}
 334
 335 \begin{itemize}
 336 \item Odd-Even-Transpositionsort
 337 \item Bitonic-Mergesort
 338 \item Odd-Even-Mergesort
 339 \item Pairwise sorting-network
 340 \end{itemize}
 341
 342 \section{Transformation von Sortiernetzwerken}
 343
 344 \begin{itemize}
 345 \item Komprimieren (Alle Komparatoren so früh wie möglich anwenden).
 346 \item Normalisieren (Transformation zu Standard-Sortiernetzwerken).
 347 \end{itemize}
 348
 349 \subsection{Zwei Netzwerke kombinieren}
 350
 351 \begin{itemize}
 352 \item Mit dem Bitonic-Merge
 353 \item Mit dem Odd-Even-Merge
 354 \item Nach dem Pairwise sorting-network Schema.
 355 \end{itemize}
 356
 357 \subsection{Leitungen entfernen}
 358
 359 \begin{itemize}
 360 \item Min-Richtung
 361 \item Max-Richtung
 362 \end{itemize}
 363
 364 \section{Der evolutionäre Ansatz}
 365
 366 \begin{itemize}
 367 \item Güte von Sortiernetzwerken (Anzahl der Komparatoren, Anzahl der
 368 Schichten, kobiniert)
 369 \item Rekombination: Merge Anhängen und Leitungen entfernen.
 370 \end{itemize}
 371
 372 Ein Beispielnetzwerk, das von dem Algorithmus gefunden wird, zeigt
 373 Abbildung~\ref{fig:evolutionary_08}.
 374
 375 \begin{figure}
 376 \begin{center}
 377 \input{images/evolutionary-08.tex}
 378 \end{center}
 379 \caption{Ein mit dem evolutionären Algorithmus erzeugtes Sortiernetzwerk mit
 380 acht Eingängen. Es besteht aus 19~Komparatoren in 6~Schichten.}
 381 \label{fig:evolutionary_08}
 382 \end{figure}
 383
 384 \begin{figure}
 385 \begin{center}
 386 \input{images/08-e2-1237993371.tex}
 387 \end{center}
 388 \caption{\tt images/08-e2-1237993371.tex}
 389 \label{fig:08-e2-1237993371}
 390 \end{figure}
 391
 392 \begin{figure}
 393 \begin{center}
 394 \input{images/09-e2-1237997073.tex}
 395 \end{center}
 396 \caption{\tt images/09-e2-1237997073.tex}
 397 \label{fig:09-e2-1237997073}
 398 \end{figure}
 399
 400 \begin{figure}
 401 \begin{center}
 402 \input{images/09-e2-1237999719.tex}
 403 \end{center}
 404 \caption{\tt images/09-e2-1237999719.tex}
 405 \label{fig:09-e2-1237999719}
 406 \end{figure}
 407
 408 \subsection{Güte}
 409
 410 \begin{itemize}
 411 \item So gut kann man mindestens werden \em{($\rightarrow$ Bitonic-Mergesort,
 412 vermute ich)}.
 413 \item Wie gut die Netzwerke werden, hängt stark vom verwendeten \em{Mischer} ab.
 414 \end{itemize}
 415
 416 \subsection{Vom evolutionären Algorithmus zu einer Markov-Kette}
 417
 418 \begin{itemize}
 419 \item Kombiniere immer das aktuelle Netzwerk mit sich selbst.
 420 \item Kann die Mindestgüte immernoch erreicht werden? ({\em Ich denke schon.})
 421 \item Anzahl der erreichbaren Sortiernetzwerke.
 422 \end{itemize}
 423
 424 \section{Empirische Beobachtungen}
 425
 426 \begin{itemize}
 427 \item So schnell konvergiert der Algorithmus.
 428 \item $\ldots$
 429 \end{itemize}
 430
 431 \section{Ausblick}
 432
 433 Das würde mir noch einfallen$\ldots$
 434
 435 %\bibliography{references}
 436 %\bibliographystyle{plain}
 437
 438 %\listoffigures
 439
 440 \end{document}
 441
 442 % vim: set shiftwidth=2 softtabstop=2 tabstop=8 fdm=marker tw=78 :