diff --git a/ea/Ub2/ea2.pdf b/ea/Ub2/ea2.pdf index afd145a..18fe33a 100644 --- a/ea/Ub2/ea2.pdf +++ b/ea/Ub2/ea2.pdf Binary files differ diff --git a/ea/Ub2/ea2.tex b/ea/Ub2/ea2.tex index be15699..27c1543 100644 --- a/ea/Ub2/ea2.tex +++ b/ea/Ub2/ea2.tex @@ -72,8 +72,6 @@ \textbf{Aufgabe \arabic{n}: #1} (#2 Punkte)\\} - - \begin{document} %\header{BlattNr}{Tutor}{Abgabedatum}{Vorlesungsname}{Namen}{Semester}{Anzahl Aufgaben} \header{2}{}{2015-05-05}{Evolutionäre Algorithmen}{ @@ -93,6 +91,26 @@ \item Lokale Maxima liegen in $0$ und $63$. %TODO \end{enumerate} + \Aufgabe{Monte-Carlo-Algorithmus}{6} + \begin{enumerate}[(a)] + \item Suchraum $\left|\{0,1\}\right|^6=2^6=64$, $p=\frac{1}{64}$\\ + $P(a^*\text{ nach n Würfen})=\sum\limits_{k=0}^{n-1}(1-p)^kp=p\cdot\frac{1-(1-p)^n}{1-(1-p)}=1-(1-p)^n$\\ + gefordert: $P\geq 0.95$\\ + \begin{align*} + &1-(1-p)^n &\geq& 0.95\\ + \Leftrightarrow &(1-p)^n &\leq& 0.05\\ + \Leftrightarrow &\left(\frac{63}{64}\right)^n &\leq& 0.05\\ + \Leftrightarrow &n\log\left(\frac{63}{64}\right) &\leq& \log(0.05)\\ + \Leftrightarrow &n&\geq& \frac{\log 0.05}{\log \frac{63}{64}} + \end{align*} $\Rightarrow n\geq 194$\\ + Codiert man Zahlen im Zehnersystem, so vergrößert sich der Suchraum bei gleichbleibender Stellenzahl: $\left|\{0,1,\dots, 9\}\right|=10^6$ Dadurch verringert sich die Wahrscheinlichkeit das Optimum zu ziehen $p=10^{-6}$\\ + Für $n$ gilt dann: $n\geq\frac{\log 0.05}{\log \frac{10^6-1}{10^6}}\approx 2.99\cdot 10^6$ + \item Man kann manuell würfeln. Mögliche Zufallsfolge: $46,33,14$\\ + Das Optimum wurde nicht gefunden. Auch könnte der Algorithmus noch viele Iterationen benötigen, bis er terminiert. Darin besteht schon ein Gegensatz zum Bit-Climber. Dieser hält bereits nach dem vierten Versuch. Bei einer anderen Zufallsfolge ($23$ enthalten) würde der Monte-Carlo-Algorithmus jedoch schneller terminieren.\\ + Außerdem muss für den aus der VL bekannten Monte-Carlo-Algorithmus das Optimum bereits bekannt sein, während der Bit-Climber lediglich die Fitnessfunktion benötigt. Im gegebenen Beispiel ergibt jedoch die Suche nach einem bekannten Optimum keinen Sinn. + \item Ein bekanntes Beispiel ist die Berechnung der Kreiszahl $\pi$ mittels eines two-sided Monte-Carlo-Algorithmus. Hierbei werden zufällig Punkte in einem Quadrat (Seitenlänge $a$) erzeugt, in dem ein Kreis (Durchmesser $a$) liegt. Aus der Häufigkeit mit der die Punkte im Kreis liegen, lässt sich seine Fläche und damit $\pi$ schätzen. ($A=\pi\cdot \frac{a^2}{4}$ vs. $A=a^2$ $\Rightarrow P(\text{Kreis})=\frac{\pi}{4}$) + \end{enumerate} + \Aufgabe{Gradientenverfahren}{7} \begin{enumerate}[(a)] \item $f'(x)=-\sin(x+2)+\frac{1}{2}$. Lokale Extrema in Nullstellen der Ableitung:\\