diff --git a/ea/Ub2/ea2.pdf b/ea/Ub2/ea2.pdf index 18fe33a..8e90a11 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 27c1543..bdad7a2 100644 --- a/ea/Ub2/ea2.tex +++ b/ea/Ub2/ea2.tex @@ -69,7 +69,7 @@ %Kommando für Aufgaben %\Aufgabe{AufgTitel}{Punktezahl} \newcommand{\Aufgabe}[2]{\stepcounter{n} -\textbf{Aufgabe \arabic{n}: #1} (#2 Punkte)\\} +\textbf{Aufgabe \arabic{n}: #1} (#2 Punkte)} \begin{document} @@ -77,18 +77,39 @@ \header{2}{}{2015-05-05}{Evolutionäre Algorithmen}{ \textit{Jan-Peter Hohloch}\\ \textit{Maximus Mutschler} }{SS 15}{4} - \vspace{1cm} - \Aufgabe{Bit-Climber}{7} + \vspace{0.5cm} \Aufgabe{Bit-Climber}{7} \begin{enumerate}[(a)] \item $\left|N_1(x)\right|=1+n=1+6=7$, $\left|N_4(x)\right|=1+6+{6\choose 2}+{6\choose 3}+{6\choose 4}=57$\\ - $\left|N_k(x)\right|=\sum\limits_{i=0}^{k}{n\choose i}$, dies ist linear in $n$, exponentiell in $k$. Für $k << n$ also recht effizient. + $\left|N_k(x)\right|=\sum\limits_{i=0}^{k}{n\choose i}=\sum\limits_{i=0}^{k} \frac{n!}{i!\cdot (n-i)!}=1+n+\frac{n(n-1)}{2}+\frac{n(n-1)(n-2)}{3!}+\dots \Rightarrow\mathcal{O}(n^k)$; für kleine $k$ also effizient, für $k$ fest polynomiell. \item Die Fitness wächst, wenn der Abstand zu 23 verringert wird:\\ $x_0=101101_2,\ f(x_0)=484$\\ $x_1=001101_2,\ f(x_1)=100$\\ $x_2=011101_2,\ f(x_2)=36$\\ $x_3=010101_2,\ f(x_3)=4$\\ $x_4=010111_2,\ f(x_4)=0$ - \item Lokale Maxima liegen in $0$ und $63$. %TODO + \item Lokales Maximum: $000000_2 \rightarrow f(x) = 529_{10}$\\ + Globales Maximum : $111111_2 = 63_{10} \rightarrow f(x) = 1600_{10}$\\ + Gute Werte liegen möglichst weit am Rand des möglichen Bereiches. Wir betrachten also jeweils die höchste und kleinste mutierbare Zahl.\\ + Startlösung $x_b = 000001_2 \rightarrow f(x)= 484_{10}$ + \begin{itemize} + \item Sei $k=1$ + \begin{itemize} + \item In erster Iteration mutierter kleinster + Wert: $ 000000_2\rightarrow f(x)=529_{10}$\\ + In erster Iteration mutierter höchster Wert: $100001_2 \rightarrow f(x)=100_{10} $\\ + $\rightarrow f(000000_2) > f(000001_2) \rightarrow$ übernehme $000000_2$ + \item In zweiter Iteration mutierter kleinster + Wert: $ 000000_2\rightarrow f(x)=529_{10}$\\ + In erster Iteration mutierter höchster Wert: $100000_2 \rightarrow f(x)=81_{10} $\\ + $\rightarrow f(000000_2) > f(100000_2) \rightarrow$ behalte $000000_2$ + \end{itemize} + \item Sei $k=2$ + \begin{itemize} + \item In erster Iteration mutierter kleinster Wert: $ 000000_2\rightarrow f(x)=529_{10} $ \\ + In erster Iteration mutierter höchster Wert: $110001_2 \rightarrow f(x)=676_{10} $\\ + $\rightarrow$ da $110000_2$ bereits größer als das lokale Maximum bei $0$ ist, wird kein kleinerer Wert mehr gewählt werden $\rightarrow$ Konvergenz gegen globales Maximum ($63$).\\ + \end{itemize} + \end{itemize} \end{enumerate} \Aufgabe{Monte-Carlo-Algorithmus}{6} @@ -103,12 +124,13 @@ \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$ + Codiert man Zahlen im Zehnersystem, so vergrößert sich der Suchraum bei gleichbleibender Stellenzahl: $\left|\{0,1,\dots, 9\}\right|=10^6$ (sollten auch negative Zahlen berücksichtigt werden, so vergrößert sich der Suchraum auf $2\cdot 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.996\cdot 10^6$ (bzw. $\geq\frac{\log 0.05}{\log \frac{2\cdot 10^6-1}{2\cdot 10^6}}\approx5.991\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}$) + \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}$) (vgl. \href{https://de.wikipedia.org/wiki/Monte-Carlo-Algorithmus#Probabilistische_Bestimmung_der_Zahl_Pi}{Wikipedia}) \end{enumerate} \Aufgabe{Gradientenverfahren}{7}