diff --git "a/ea/UB6/blatt6 \0501\051.pdf" "b/ea/UB6/blatt6 \0501\051.pdf" new file mode 100644 index 0000000..f48a28a --- /dev/null +++ "b/ea/UB6/blatt6 \0501\051.pdf" Binary files differ diff --git a/ea/UB6/ea6.pdf b/ea/UB6/ea6.pdf new file mode 100644 index 0000000..d767d7d --- /dev/null +++ b/ea/UB6/ea6.pdf Binary files differ diff --git a/ea/UB6/ea6.tex b/ea/UB6/ea6.tex new file mode 100644 index 0000000..dc9f792 --- /dev/null +++ b/ea/UB6/ea6.tex @@ -0,0 +1,177 @@ +\documentclass[a4paper,12pt]{scrartcl} +\usepackage[ngerman]{babel} +\usepackage{graphicx} %BIlder einbinden +\usepackage{amsmath} %erweiterte Mathe-Zeichen +\usepackage{amsfonts} %weitere fonts +\usepackage[utf8]{inputenc} %Umlaute & Co +\usepackage{hyperref} %Links +\usepackage{ifthen} %ifthenelse +\usepackage{enumerate} +\usepackage{listings} +\lstset{language=Python} + +\usepackage{algpseudocode} %Pseudocode +\usepackage{dsfont} % schöne Zahlenräumezeichen +\usepackage{amssymb, amsthm} %noch stärker erweiterte Mathe-Zeichen +\usepackage{tikz} %TikZ ist kein Zeichenprogramm +\usetikzlibrary{trees,automata,arrows,shapes} + +\pagestyle{empty} + + +\topmargin-50pt + +\newcounter{aufgabe} +\def\tand{&} + + +\newcommand{\makeTableLine}[2][0]{% + \setcounter{aufgabe}{16}%TODO update + \whiledo{\value{aufgabe} < 19}%TODO update + {% + #2\tand\stepcounter{aufgabe}% + } +} + +\newcommand{\aufgTable}[1]{ + \def\spalten{\numexpr #1 + 1 \relax} + \begin{tabular}{|*{\spalten}{p{1cm}|}} + \makeTableLine[\spalten]{A\theaufgabe}$\Sigma$~~\\ \hline + \rule{0pt}{15pt}\makeTableLine[\spalten]{}\\ + \end{tabular} +} + +\def\header#1#2#3#4#5#6#7{\pagestyle{empty} +\begin{minipage}[t]{0.47\textwidth} +\begin{flushleft} +{\bf #4}\\ +#5 +\end{flushleft} +\end{minipage} +\begin{minipage}[t]{0.5\textwidth} +\begin{flushright} +#6 \vspace{0.5cm}\\ +% Number of Columns Definition of Columns second empty line +% \begin{tabular}{|*{5}{C{1cm}|}}\hline A1&A2&A3&A4&$\Sigma$\\\hline&&&&\\\hline\end{tabular}\\\vspace*{0.1cm} +\aufgTable{#7} +\end{flushright} +\end{minipage} +\vspace{1cm} +\begin{center} +{\Large\bf Übungsblatt #1} + +{(Abgabe #3)} +\end{center} +} + + + +%counts the exercisenumber +\newcounter{n} +\setcounter{n}{15} %TODO update + +%Kommando für Aufgaben +%\Aufgabe{AufgTitel}{Punktezahl} +\newcommand{\Aufgabe}[2]{\stepcounter{n} +\textbf{Aufgabe \arabic{n}: #1} (#2 Punkte)} + + +\begin{document} + %\header{BlattNr}{Tutor}{Abgabedatum}{Vorlesungsname}{Namen}{Semester}{Anzahl Aufgaben} + \header{6}{}{2015-06-09}{Evolutionäre Algorithmen}{ + \textit{Jan-Peter Hohloch}\\ \textit{Maximus Mutschler} + }{SS 15}{3}%TODO update + \vspace{0.5cm} \Aufgabe{Crossover-Operatoren}{6}\\ + \begin{enumerate}[(a)] + \item + A=(1010110000)\\ + B=(0011100011)\\ + \begin{enumerate}[(i)] + \item 1-Punkt Crossover an 4 : A'=(1010|\textbf{100011}) B'=(0011|\textbf{110000}) + \item 2-Punkt Crossover an 3,7 : A'=(101|\textbf{1100}|000) B'=(001|\textbf{0110}|000) + \item Uniformes Crossover 2,4,6,8: A'=(1\textbf{0}1\textbf{1}1\textbf{0}0\textbf{0}00) B'=(0\textbf{0}1\textbf{0}1\textbf{1}0\textbf{0}11) + \end{enumerate} + \item + C=(9,4,6,7,1,2,10,8,5,3)\\ + D=(7,3,8,10,5,4,2,9,6,1)\\ + \begin{enumerate}[(i)] + \item Partially matched Xover: 3,7 C'=(9,\textbf{2},6|\textbf{10,5,4,2}|8,\textbf{1},3) D'=(\textbf{2},3,8|\textbf{7,1,2,10}|9,6,\textbf{5}) + \item order xover 1,4 C'=(7|3,8,10|1,2,5,9,4,6) D'=(10|4,6,7|5,2,9,1,3,8) + \item Cycle Xover in C, 5 . C'=C=(9,4,6,7,1,2,10,8,5,3) D'=D=(7,3,8,10,5,4,2,9,6,1) + \end{enumerate} + \end{enumerate} + \Aufgabe{Selektionswahrscheinlichkeit}{6}\\ + $P_{Sorted}=(110110,110101,001011,010011,010100)$\\ + \begin{enumerate}[(a)] + \item Lineares Ranking\\$p_i=\frac{1}{\lambda}\left(\mu^+-(\mu^+-\mu^-)\dfrac{i-1}{\lambda-1}\right)$\\ + $\mu^+=1\\ + \mu^-=1 + \lambda = 5\\ + p_i=\frac{1}{5}$ für alle i\\ + $ + \mu^+=2\\ + \mu^-=0\\ + p_i=\dfrac{1}{5}(2-\dfrac{2(i-1)}{4})= \dfrac{2}{5}-\dfrac{1}{10}(i-1)=\dfrac{5-i}{10}\\ + p_1=0.4\\ + p_2=0.3\\ + p_3=0.2\\ + p_4=0.1\\ + p_5=0\\ + $ + \item nicht lineares ranking\\ + $ p_i=c(1-c)^{i-1} + \\c=0.04\\ + p_i= 0.04(0.96)^{i-1}\\ + p_1=0.04*1= 0.04\cdot s= 0.217\\ + p_2=0.04*0.96= 0.0384\cdot s= 0.208\\ + p_3=0.04*(0.96)^2= 0.036864\cdot s=0.2\\ + p_4=0.04*(0.96)^3= 0.03538944\cdot s=0.192\\ + p_5=0.04*(0.96)^4= 0.0339738624\cdot s=0.183\\ + Saklierungsfaktor=s = 5.41632 + $ + \item tournament selektion \\ + $ + p_i= \dfrac{1}{\lambda^q}((\lambda-i+1)^q-(\lambda-i)^q)\\ + \lambda =5\\ + p=2\\ + p_i= \dfrac{1}{25}((6-i)^2-(5-i)^2)= \dfrac{1}{25}(36-12i+i^2-25+10i-i^2)= \dfrac{11-2i}{25} \\ + p_1=\dfrac{9}{25}\\ + p_2=\dfrac{7}{25}\\ + p_3=\dfrac{5}{25}\\ + p_4=\dfrac{3}{25}\\ + p_5=\dfrac{1}{25}\\ + $ + \end{enumerate} + \Aufgabe{ Population-based Incremental Learning -}{8} + \begin{enumerate}[(a)] + \item $f_{twin}=\left| \sum_{i=1}^{\frac{l}{2}}a_i- \sum_{i=1+\frac{l}{2}}^{l}a_i\right| = f_{twin}=\left| \sum_{i=1}^{3}a_i- \sum_{i=4}^{6}a_i\right|\\ + \mu = 2\\ + \eta = \frac{1}{5}\\ + l = 6\\ + P_i=P_i*(1-\eta)+a_{ij}\eta = P_i +\frac{1}{5}\cdot(a_{ij}-P_i)\\ + f(1)=-2 ,f(2)=0,f(3)=0,f(4)=2,f(5)=1,f(6)=-1\\ + $ + Beste 2 Kinder:$ 4:(111010),5:(101010)$\\ + P mit Kind 4:$ (\frac{3}{5},\frac{3}{5},\frac{3}{5},\frac{2}{5},\frac{3}{5},\frac{2}{5})$\\ + $P_{twin}(1)$ mit Kind 4 und 5: $(\frac{17}{25},\frac{12}{25},\frac{17}{25},\frac{8}{25},\frac{17}{25},\frac{8}{25})$ + \item $ + f_{bmax}=\sum_{i=1}^{6}a_i\\ + f(1)=2, f(2)=2,f(3)=4,f(4)=4,f(5)=3,f(6)=3$\\ + Beste 2 Kinder: 3:$(011101), 4:(111010)$\\ + P mit Kind 4: $(\frac{3}{5},\frac{3}{5},\frac{3}{5},\frac{2}{5},\frac{3}{5},\frac{2}{5})$\\ + $P_{bmax}(1)$ mit Kind 3 und 4: $(\frac{12}{25},\frac{17}{25},\frac{17}{25},\frac{13}{25},\frac{12}{25},\frac{13}{25})$\\ + \item + max $f_{bmax}=6$\\ + max $f_{twin}=3$\\ + \item$ + f_{twin}(P(0))= 0 \\ + f_{twin}(P(1))= \frac{13}{25}=0.52\\ + f_{bmax}(P(0))= 3 \\ + f_{bmax}(P(1))= \frac{84}{25}= 3.36 \\ + $ + Die Fitness von $P_{pmax}$ ist 2.64 und die von $P_{tmin}$ 2.58 von ihrem Maximum entfernt. Durch die verschiedenen Fitnessfunktionen sind andere Kinder Maxima in der aktuellen Population, wodurch sich die ermittelten Wahrscheinlichkeiten verändern und es zu einem unterschiedlichen Fortschritt kommt. %TODO + Auf Gundlage der Änderung zwischen Schritt 0 und 1 wird PBIL auf $f_{twin}$ schneller konvergieren da es die höhere Änderungsrate hat \TODO + \item Todo keine ahnung, kann hier nicht denken %TODO + \end{enumerate} +\end{document} +