From 56c2c5c629b941ea34faf8ee70fe0c0a87a5ebf3 Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Fri, 25 Feb 2011 14:12:18 +0100 Subject: [PATCH] =?utf8?q?SN-Evolution:=20Versuche=20mit=20dem=20bitonen?= =?utf8?q?=20Mischer=20=C3=BCberarbeitet.?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- diplomarbeit.tex | 70 ++++++++++++-- images/16-green.tex | 259 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 320 insertions(+), 9 deletions(-) create mode 100644 images/16-green.tex diff --git a/diplomarbeit.tex b/diplomarbeit.tex index d98d914..8e7beca 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -9,6 +9,7 @@ \usepackage{listings} \usepackage{graphicx} \usepackage{url} +\usepackage[table]{xcolor} %\usepackage{longtable} \usepackage{subfigure} \usepackage{icomma} @@ -43,6 +44,9 @@ \newcommand{\bm}[1]{\ensuremath{\operatorname{BM}\left(#1\right)}} \newcommand{\oet}[1]{\ensuremath{\operatorname{OET}\left(#1\right)}} +\newcommand{\gcell}{\cellcolor{green!10}} +\newcommand{\Gcell}{\cellcolor{green!10!white!95!black}} + \newtheorem{definition}{Definition} \newtheorem{satz}{Satz} @@ -1380,15 +1384,63 @@ wurde beim \textsc{SN-Evolution}-Algorithmus auf eine Mutation verzichtet. \label{fig:16-e1-bitonic-1296542566} \end{figure} -Verwendet man den \emph{bitonen Mischer} in der Rekombinationsphase von -\textsc{SN-Evolution}, so erhält man Netzwerke wie das in -Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte: Der Algorithmus -wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk als triviale -Initiallösung gestartet. Das Ergebnis ist ein Netzwerk, das effizienter ist -als das \emph{bitone Mergesort}-Netzwerk: \bs{16} benötigt 80~Komparatoren, -das Sortiernetzwerk in Abbildung~\ref{fig:16-e1-bitonic-1296542566} benötigt -lediglich~67. Die Effizienz des \emph{Odd-Even-Mergesort}-Netzwerks wurde -leider mit keiner Leitungszahl erreicht. +Wenn \textsc{SN-Evolution} mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk +als Eingabe gestartet wird und in der Rekombinationsphase den \emph{bitonen +Mischer} verwendet, gibt der Algorithmus Sortiernetzwerke wie das in +Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte zurück. + +Viele der Sortiernetzwerke, die von \textsc{SN-Evolution} in dieser +Konfiguration gefunden werden, sind effizienter als das \emph{bitone +Mergesort}-Netzwerk \bs{n}, das ebenfalls auf dem \emph{bitonen +Merge}-Netzwerk \bm{n} beruht. Das in +Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte 16-Sortiernetzwerk +benötigt 67~Komparatoren, 13~Komparatoren weniger als \bs{n}. + +Wenn die Gütefunktion so gewählt ist, dass sie schnelle Sortiernetzwerke +bevorzugt, können Netzwerke zurückgegeben werden, die schneller als \bs{n} +sind. Viele der schnellen Sortiernetzwerke sind außerdem effizienter als +\bs{n}. Das Sortiernetzwerk mit $n = 23$ Leitungen benötigt mit +134~Komparatoren jedoch einen Komparator mehr als \bs{23}. Die Daten von +schnellen Sortiernetzwerken, die \textsc{SN-Evolution} mit dem \emph{bitonen +Merge}-Netzwerk erzeugt hat, sind in Tabelle~\ref{tbl:sn-ev-bm-fast} +aufgelistet. + +\begin{table}\label{tbl:sn-ev-bm-fast} +\begin{center} +\rowcolors{4}{black!5}{} +\begin{tabular}{|r|r|r|r|r|} +\hline +Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}} & \multicolumn{2}{|l|}{\bs{n}} \\ +\cline{2-5} + ($n$) & Komp. & Schichten & Komp. & Schichten \\ +\hline + 8 & \gcell 20 & 6 & 24 & 6 \\ + 9 & \Gcell 26 & 8 & 28 & 8 \\ + 10 & \gcell 31 & \gcell 8 & 33 & 9 \\ + 11 & \Gcell 37 & \Gcell 9 & 39 & 10 \\ + 12 & \gcell 42 & \gcell 9 & 46 & 10 \\ + 13 & \Gcell 48 & 10 & 53 & 10 \\ + 14 & \gcell 54 & 10 & 61 & 10 \\ + 15 & \Gcell 61 & 10 & 70 & 10 \\ + 16 & \gcell 67 & 10 & 80 & 10 \\ + 17 & \Gcell 76 & 12 & 85 & 12 \\ + 18 & \gcell 87 & \gcell 12 & 91 & 13 \\ + 19 & \Gcell 93 & \Gcell 13 & 98 & 14 \\ + 20 & \gcell 104 & \gcell 13 & 106 & 14 \\ + 21 & \Gcell 109 & \Gcell 14 & 114 & 15 \\ + 22 & \gcell 118 & \gcell 14 & 123 & 15 \\ + 23 & 134 & \Gcell 14 & \Gcell 133 & 15 \\ + 24 & \gcell 133 & 15 & 144 & 15 \\ +\hline +\end{tabular} +\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus + unter Verwendung des \emph{bitonen Merge}-Netzwerks \bm{n}. Der Algorithmus + wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n} gestartet + und nach 2.500.000 Iterationen beendet. Die Bewertungsfunktion nutzte die + Konstanten $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = 1$, + $w_{\mathrm{Schichten}} = n$.} +\end{center} +\end{table} \subsection[Odd-Even-Mischer]{Versuche mit dem Odd-Even-Mischer} diff --git a/images/16-green.tex b/images/16-green.tex new file mode 100644 index 0000000..225e1de --- /dev/null +++ b/images/16-green.tex @@ -0,0 +1,259 @@ +Unknown key: Comment +\begin{tikzpicture}[auto] +\node[vertex] (v0) at (0.91,0.00) {}; +\node[vertex] (v1) at (0.91,0.73) {}; +\path[comp] (v0) -- (v1); + +\node[vertex] (v2) at (0.91,1.46) {}; +\node[vertex] (v3) at (0.91,2.20) {}; +\path[comp] (v2) -- (v3); + +\node[vertex] (v4) at (0.91,2.93) {}; +\node[vertex] (v5) at (0.91,3.66) {}; +\path[comp] (v4) -- (v5); + +\node[vertex] (v6) at (0.91,4.39) {}; +\node[vertex] (v7) at (0.91,5.12) {}; +\path[comp] (v6) -- (v7); + +\node[vertex] (v8) at (0.91,5.85) {}; +\node[vertex] (v9) at (0.91,6.59) {}; +\path[comp] (v8) -- (v9); + +\node[vertex] (v10) at (0.91,7.32) {}; +\node[vertex] (v11) at (0.91,8.05) {}; +\path[comp] (v10) -- (v11); + +\node[vertex] (v12) at (0.91,8.78) {}; +\node[vertex] (v13) at (0.91,9.51) {}; +\path[comp] (v12) -- (v13); + +\node[vertex] (v14) at (0.91,10.24) {}; +\node[vertex] (v15) at (0.91,10.98) {}; +\path[comp] (v14) -- (v15); + +\node[vertex] (v16) at (1.83,0.00) {}; +\node[vertex] (v17) at (1.83,1.46) {}; +\path[comp] (v16) -- (v17); + +\node[vertex] (v18) at (2.10,0.73) {}; +\node[vertex] (v19) at (2.10,2.20) {}; +\path[comp] (v18) -- (v19); + +\node[vertex] (v20) at (1.83,2.93) {}; +\node[vertex] (v21) at (1.83,4.39) {}; +\path[comp] (v20) -- (v21); + +\node[vertex] (v22) at (2.10,3.66) {}; +\node[vertex] (v23) at (2.10,5.12) {}; +\path[comp] (v22) -- (v23); + +\node[vertex] (v24) at (1.83,5.85) {}; +\node[vertex] (v25) at (1.83,7.32) {}; +\path[comp] (v24) -- (v25); + +\node[vertex] (v26) at (2.10,6.59) {}; +\node[vertex] (v27) at (2.10,8.05) {}; +\path[comp] (v26) -- (v27); + +\node[vertex] (v28) at (1.83,8.78) {}; +\node[vertex] (v29) at (1.83,10.24) {}; +\path[comp] (v28) -- (v29); + +\node[vertex] (v30) at (2.10,9.51) {}; +\node[vertex] (v31) at (2.10,10.98) {}; +\path[comp] (v30) -- (v31); + +\node[vertex] (v32) at (3.02,0.00) {}; +\node[vertex] (v33) at (3.02,2.93) {}; +\path[comp] (v32) -- (v33); + +\node[vertex] (v34) at (3.29,0.73) {}; +\node[vertex] (v35) at (3.29,3.66) {}; +\path[comp] (v34) -- (v35); + +\node[vertex] (v36) at (3.57,1.46) {}; +\node[vertex] (v37) at (3.57,4.39) {}; +\path[comp] (v36) -- (v37); + +\node[vertex] (v38) at (3.84,2.20) {}; +\node[vertex] (v39) at (3.84,5.12) {}; +\path[comp] (v38) -- (v39); + +\node[vertex] (v40) at (3.02,5.85) {}; +\node[vertex] (v41) at (3.02,8.78) {}; +\path[comp] (v40) -- (v41); + +\node[vertex] (v42) at (3.29,6.59) {}; +\node[vertex] (v43) at (3.29,9.51) {}; +\path[comp] (v42) -- (v43); + +\node[vertex] (v44) at (3.57,7.32) {}; +\node[vertex] (v45) at (3.57,10.24) {}; +\path[comp] (v44) -- (v45); + +\node[vertex] (v46) at (3.84,8.05) {}; +\node[vertex] (v47) at (3.84,10.98) {}; +\path[comp] (v46) -- (v47); + +\node[vertex] (v48) at (4.76,0.00) {}; +\node[vertex] (v49) at (4.76,5.85) {}; +\path[comp] (v48) -- (v49); + +\node[vertex] (v50) at (5.03,0.73) {}; +\node[vertex] (v51) at (5.03,6.59) {}; +\path[comp] (v50) -- (v51); + +\node[vertex] (v52) at (5.30,1.46) {}; +\node[vertex] (v53) at (5.30,7.32) {}; +\path[comp] (v52) -- (v53); + +\node[vertex] (v54) at (5.58,2.20) {}; +\node[vertex] (v55) at (5.58,8.05) {}; +\path[comp] (v54) -- (v55); + +\node[vertex] (v56) at (5.85,2.93) {}; +\node[vertex] (v57) at (5.85,8.78) {}; +\path[comp] (v56) -- (v57); + +\node[vertex] (v58) at (6.13,3.66) {}; +\node[vertex] (v59) at (6.13,9.51) {}; +\path[comp] (v58) -- (v59); + +\node[vertex] (v60) at (6.40,4.39) {}; +\node[vertex] (v61) at (6.40,10.24) {}; +\path[comp] (v60) -- (v61); + +\node[vertex] (v62) at (6.68,5.12) {}; +\node[vertex] (v63) at (6.68,10.98) {}; +\path[comp] (v62) -- (v63); + +\node[vertex] (v64) at (7.59,0.73) {}; +\node[vertex] (v65) at (7.59,1.46) {}; +\path[comp] (v64) -- (v65); + +\node[vertex] (v66) at (7.59,2.20) {}; +\node[vertex] (v67) at (7.59,8.78) {}; +\path[comp] (v66) -- (v67); + +\node[vertex] (v68) at (7.87,2.93) {}; +\node[vertex] (v69) at (7.87,5.85) {}; +\path[comp] (v68) -- (v69); + +\node[vertex] (v70) at (8.14,3.66) {}; +\node[vertex] (v71) at (8.14,7.32) {}; +\path[comp] (v70) -- (v71); + +\node[vertex] (v72) at (8.41,4.39) {}; +\node[vertex] (v73) at (8.41,6.59) {}; +\path[comp] (v72) -- (v73); + +\node[vertex] (v74) at (8.69,5.12) {}; +\node[vertex] (v75) at (8.69,8.05) {}; +\path[comp] (v74) -- (v75); + +\node[vertex] (v76) at (7.59,9.51) {}; +\node[vertex] (v77) at (7.59,10.24) {}; +\path[comp] (v76) -- (v77); + +\node[vertex] (v78) at (9.60,0.73) {}; +\node[vertex] (v79) at (9.60,2.93) {}; +\path[comp] (v78) -- (v79); + +\node[vertex] (v80) at (9.88,1.46) {}; +\node[vertex] (v81) at (9.88,5.85) {}; +\path[comp] (v80) -- (v81); + +\node[vertex] (v82) at (9.60,5.12) {}; +\node[vertex] (v83) at (9.60,9.51) {}; +\path[comp] (v82) -- (v83); + +\node[vertex] (v84) at (9.88,8.05) {}; +\node[vertex] (v85) at (9.88,10.24) {}; +\path[comp] (v84) -- (v85); + +\node[vertex] (v86) at (10.79,1.46) {}; +\node[vertex] (v87) at (10.79,2.93) {}; +\path[comp] (v86) -- (v87); + +\node[vertex] (v88) at (11.07,2.20) {}; +\node[vertex] (v89) at (11.07,5.85) {}; +\path[comp] (v88) -- (v89); + +\node[vertex] (v90) at (10.79,3.66) {}; +\node[vertex] (v91) at (10.79,4.39) {}; +\path[comp] (v90) -- (v91); + +\node[vertex] (v92) at (10.79,5.12) {}; +\node[vertex] (v93) at (10.79,8.78) {}; +\path[comp] (v92) -- (v93); + +\node[vertex] (v94) at (11.07,6.59) {}; +\node[vertex] (v95) at (11.07,7.32) {}; +\path[comp] (v94) -- (v95); + +\node[vertex] (v96) at (11.07,8.05) {}; +\node[vertex] (v97) at (11.07,9.51) {}; +\path[comp] (v96) -- (v97); + +\node[vertex] (v98) at (11.98,2.20) {}; +\node[vertex] (v99) at (11.98,3.66) {}; +\path[comp] (v98) -- (v99); + +\node[vertex] (v100) at (11.98,4.39) {}; +\node[vertex] (v101) at (11.98,5.85) {}; +\path[comp] (v100) -- (v101); + +\node[vertex] (v102) at (12.26,5.12) {}; +\node[vertex] (v103) at (12.26,6.59) {}; +\path[comp] (v102) -- (v103); + +\node[vertex] (v104) at (11.98,7.32) {}; +\node[vertex] (v105) at (11.98,8.78) {}; +\path[comp] (v104) -- (v105); + +\node[vertex] (v106) at (13.17,2.20) {}; +\node[vertex] (v107) at (13.17,2.93) {}; +\path[comp] (v106) -- (v107); + +\node[vertex] (v108) at (13.17,3.66) {}; +\node[vertex] (v109) at (13.17,4.39) {}; +\path[comp] (v108) -- (v109); + +\node[vertex] (v110) at (13.17,5.12) {}; +\node[vertex] (v111) at (13.17,5.85) {}; +\path[comp] (v110) -- (v111); + +\node[vertex] (v112) at (13.17,6.59) {}; +\node[vertex] (v113) at (13.17,7.32) {}; +\path[comp] (v112) -- (v113); + +\node[vertex] (v114) at (13.17,8.05) {}; +\node[vertex] (v115) at (13.17,8.78) {}; +\path[comp] (v114) -- (v115); + +\node[vertex] (v116) at (14.09,4.39) {}; +\node[vertex] (v117) at (14.09,5.12) {}; +\path[comp] (v116) -- (v117); + +\node[vertex] (v118) at (14.09,5.85) {}; +\node[vertex] (v119) at (14.09,6.59) {}; +\path[comp] (v118) -- (v119); + +\path[edge] (0,0.00) -- (15.00,0.00); +\path[edge] (0,0.73) -- (15.00,0.73); +\path[edge] (0,1.46) -- (15.00,1.46); +\path[edge] (0,2.20) -- (15.00,2.20); +\path[edge] (0,2.93) -- (15.00,2.93); +\path[edge] (0,3.66) -- (15.00,3.66); +\path[edge] (0,4.39) -- (15.00,4.39); +\path[edge] (0,5.12) -- (15.00,5.12); +\path[edge] (0,5.85) -- (15.00,5.85); +\path[edge] (0,6.59) -- (15.00,6.59); +\path[edge] (0,7.32) -- (15.00,7.32); +\path[edge] (0,8.05) -- (15.00,8.05); +\path[edge] (0,8.78) -- (15.00,8.78); +\path[edge] (0,9.51) -- (15.00,9.51); +\path[edge] (0,10.24) -- (15.00,10.24); +\path[edge] (0,10.98) -- (15.00,10.98); +\end{tikzpicture} -- 2.11.0