\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{7},6|\textbf{10,5,4,2}|8,\textbf{1},3) D'=(\textbf{4},3,8|\textbf{7,1,2,10}|9,6,\textbf{5})$
    		\item Order Crossover 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 Crossover 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^+-\eta^-)\dfrac{i-1}{\lambda-1}\right)$\\
     	$\eta^+=1.2\\ 
     	\eta^-=0.8\\
     	\lambda = 5\\
     	p_i=\dfrac{1}{5}(1.2-\dfrac{0.4(i-1)}{4})= \dfrac{6}{25}-\dfrac{1}{50}(i-1)=\dfrac{13-i}{50}\\
     	p_1=0.24\\
     	p_2=0.22\\
     	p_3=0.2\\
     	p_4=0.18\\
     	p_5=0.16\\
     	$
     	\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  \rightarrow  \sum_{i=1}^5p_i =1	
     	$
     	\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\\
     	$
     	Besten 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_{bmax}$ ist 2.64 und die  von $P_{tmin}$ 2.58 von ihrem Maximum entfernt. Durch die verschiedenen Fitnessfunktionen sind verschiedene Kinder Maxima in der aktuellen Population, wodurch sich die ermittelten Wahrscheinlichkeiten verändern und es zu einem unterschiedlichen Fortschritt kommt. %TODO  
     	Da die Fitness von $P(1)_{twin}$ näher am Maximum liegt als die Fitness von $P(1)_{bmax}$ wird die nächste Population wahrscheinlich bessere Individuen enthalten. Dementsprechend wird diese wahrscheinlich schneller konvergieren. \\ Grundsätzlich jedoch brauchen beide Optimierungen ungefähr gleichlang, da beide 6bits optimieren müssen.
       \item   Da wir weiterhin das beste Drittel der Individuen auswählen, ist die durchschnittliche Güte der gewählten Individuen gleich gut wie zuvor. Jedoch wird der Wahrscheinlichkeitsvektor öfter aktualisiert, wodurch sich dieser schneller verbessert. Wir benötigen also weniger Iterationen. Das gilt sowohl für $f_{bmax}$ als auch für $f_{twin}$.
     \end{enumerate}
\end{document}

