\documentclass[12pt,a4paper]{article}
\usepackage{graphicx}
\pagestyle{empty}
\oddsidemargin 2.1mm
\textwidth     155mm
\topmargin     -15mm
\textheight    240mm

\begin{document}

%-----------------------------------------------------------------------

\noindent
{\bf Evolutionary Algorithms} \hfill Winter 2017/2018 \\
PD~Dr.-Ing.~habil.~Christian~Borgelt \hfill from 2017.12.07

%-----------------------------------------------------------------------

\vskip3ex
\centerline{\bf Exercise Sheet 4}

%-----------------------------------------------------------------------

\subsubsection*{Exercise 13 \quad\rm Roulette Wheel Selection}

As mentioned in the lecture, it is one of the disadvantages of fitness
proportional selection (roulette wheel selection) that it can lead to
a substantial variance when selecting the individuals of the next
generation. In this exercise we consider this disadvantage in more
detail by computing the probabilities with which an individual is
selected for the next generation.
\begin{enumerate}\itemsep0pt
\item[a)] Compute the probability that an individual with the relative
     fitness~$p$ is represented $k$~times in the next generation if the
     individuals are chosen by roulette wheel selection! \\
     (Hint: Note that this probability depends on the population
     size {\it popsize}.)
\item[b)] How does the probability in a) change if there are already
     $m$~copies of the individual in the current population?
\item[c)] Determine the expected value and the variance of the number
     of descendants of an individual with the relative fitness~$p$! \\
     (Hint: It may not be the most convenient way to start with the
     formula determined in a), even though one may reach the result
     on this path as well.)
\item[d)] Compute numeric values for the quantities considered in a)
     to c) for a relative fitness $p = 0.02$, a population size
     $\mbox{\it popsize} = 100$, and $k = 0, 1, 2$ descendants!
\end{enumerate}

%-----------------------------------------------------------------------

\subsubsection*{Exercise 14 \quad\rm Scaling the Fitness Function}

Let the following chromosomes for the $8$-queens problem be given
(encoding as discussed in the lecture, that is, a list of file
positions, numbering starting with zero):
\[ \begin{array}{lll@{\qquad\qquad}lll}
   s_1    & = & (1, 0, 7, 6, 1, 6, 7, 2), &  % -10
   s_6    & = & (2, 3, 4, 7, 6, 6, 2, 2), \\ % -11
   s_2    & = & (5, 1, 3, 0, 2, 0, 6, 0), &  %  -7
   s_7    & = & (6, 1, 7, 4, 3, 0, 1, 2), \\ %  -8
   s_3    & = & (7, 1, 6, 6, 4, 4, 5, 2), &  %  -8
   s_8    & = & (5, 6, 5, 3, 0, 0, 7, 5), \\ %  -7
   s_4    & = & (7, 2, 1, 1, 1, 4, 1, 2), &  % -12
   s_9    & = & (6, 6, 2, 0, 0, 0, 4, 1), \\ %  -5
   s_5    & = & (4, 1, 0, 2, 6, 7, 4, 2), &  %  -6
   s_{10} & = & (1, 7, 2, 4, 1, 3, 0, 6)     %  -3
   \end{array} \]
Determine the relative fitness of these chromosomes using
\begin{enumerate}\itemsep0pt
\item[a)] linear dynamic scaling with $\alpha = 1.2$
\item[b)] $\sigma$-scaling with $\beta = 2$!
\end{enumerate}
Start from the fitness function that was also considered in the lecture
to evaluate chromosomes for the $n$-queens problem (negated number of
collisions, that is, negated number of pairs of queens on the same
file or diagonal).

%-----------------------------------------------------------------------

\subsubsection*{Exercise 15 \quad\rm Stochastic Universal Sampling}

In the lecture the method of {\em stochastic universal sampling\/}
was discussed as a variant of the expected value model. This method
uses a roulette wheel with {\em popsize\/} (population size) markers.
How can this selection method be implemented efficiently? (Give a
code fragment in a programming language of your choice or in
pseudo-code.)

%-----------------------------------------------------------------------

\subsubsection*{Exercise 16 \quad\rm Tournament Selection}

As an alternative to roulette wheel selection we considered in the
initial example of an evolutionary algorithm a solution of the
$n$-queens problem that uses tournament selection.
\begin{enumerate}\itemsep0pt
\item[a)] Compute the probability that the {\em best\/} individual
     in the current population is represented $k$~times in the next
     generation if the individuals of the next generation are determined
     by tournament selection! (The tournament participants are to be
     selected {\em without\/} replacement.)
\item[b)] In analogy, compute the probability for the {\em worst\/}
     individual!
\item[c)] How do the probabilities in a) and b) change if the tournament
     participants are chosen {\em with\/} replacement?
\item[d)] Compute the expected value and the variance of the number
     of descendants of the {\em best\/} individual!
\item[e)] Compute numeric values for the quantities in a), b) and d)
     for a population size $\mbox{\it popsize} = 100$, a tournament size
     $\mbox{\it tmsize} = 2$ (duel selection) and
     $k = 0, 1, 2$ descendants!
\end{enumerate}
(Hint: Note in a) to d) that the quantities to determine depend on the 
population size {\it popsize\/} and the tournament size {\it tmsize\/}.
You may make the simplifying assumption that all individuals have a
different fitness.)

%-----------------------------------------------------------------------
\newpage

\subsubsection*{Additional Exercise \quad\rm
                Timelapse$^{\mbox{\scriptsize\sc tm}}$:
                Double Pyramid and Lizard}

\newsavebox{\pyramid}
\savebox{\pyramid}{\unitlength1mm\footnotesize
\begin{picture}(39,45)
\multiput( 0,28)( 3,3){7}{\line(1,0){3}}
\multiput( 0,25)( 3,3){7}{\line(0,1){3}}
\multiput(36,28)(-3,3){6}{\line(1,0){3}}
\multiput(39,25)(-3,3){7}{\line(0,1){3}}
\multiput(27,16)( 3,3){4}{\line(1,0){3}}
\multiput(27,13)( 3,3){4}{\line(0,1){3}}
\multiput( 0,25)(3,-3){4}{\line(1,0){3}}
\multiput( 3,22)(3,-3){4}{\line(0,1){3}}
\put(12,13){\line(1,0){15}}
\multiput( 0, 0)( 4,0){4}{\line(0,1){8}}
\multiput( 0, 0)( 0,4){3}{\line(1,0){12}}
\put( 2,10){\makebox(0,0){$l_1$}}
\put( 6,10){\makebox(0,0){$l_2$}}
\put(10,10){\makebox(0,0){$l_3$}}
\put( 2, 6){\makebox(0,0){4}}
\put( 6, 6){\makebox(0,0){5}}
\put(10, 6){\makebox(0,0){8}}
\multiput(27, 0)( 4,0){4}{\line(0,1){8}}
\multiput(27, 0)( 0,4){3}{\line(1,0){12}}
\put(29,10){\makebox(0,0){$r_1$}}
\put(33,10){\makebox(0,0){$r_2$}}
\put(37,10){\makebox(0,0){$r_3$}}
\put(29, 6){\makebox(0,0){5}}
\put(33, 6){\makebox(0,0){6}}
\put(37, 6){\makebox(0,0){8}}
\end{picture}}

\hangafter-21\hangindent-45mm\noindent
\hbox to0pt{\vbox to1.5ex{\noindent\hbox to\textwidth{\hss
\unitlength1mm\footnotesize
\begin{picture}(39,101)
%\multiput(0,0)(33,0){2}{\line(0,1){98}}
%\multiput(0,0)(0,98){2}{\line(1,0){33}}
\put(0,52){%
  \put(0,0){\usebox{\pyramid}}
  \put(19.5,47){\makebox(0,0)[b]{$e$}}
  \put( 2, 2){\makebox(0,0){3}}
  \put( 6, 2){\makebox(0,0){5}}
  \put(10, 2){\makebox(0,0){4}}
  \put(29, 2){\makebox(0,0){4}}
  \put(33, 2){\makebox(0,0){3}}
  \put(37, 2){\makebox(0,0){3}}
}
\put(0,0){%
  \put(0,0){\usebox{\pyramid}}
  \linethickness{1mm}
  \put(34.5,22){\circle*{1.7}}
  \put(16.5,43){\circle*{1.7}}
  \put(31.5,35){\makebox(0,0)[b]{$e$}}
  \put( 2, 2){\makebox(0,0){2}}
  \put( 6, 2){\makebox(0,0){4}}
  \put(10, 2){\makebox(0,0){4}}
  \put(29, 2){\makebox(0,0){3}}
  \put(33, 2){\makebox(0,0){3}}
  \put(37, 2){\makebox(0,0){2}}
}
\end{picture}}\vss}\hss}%
In the computer game Timelapse$^{\mbox{\scriptsize\sc tm}}$
(adventure game by Barracuda Inc.) one has to solve, among others,
the following puzzle: on the tip of a double step pyramid sits a
lizard (see picture on the right, the lizard is symbolized by an $e$).
Below the double pyramid 6~switches are located, three to the left
(switches $l_1$, $l_2$ and $l_3$) and three to the right (switches
$r_1$, $r_2$ and $r_3$). With the help of these switches the lizard
can be ordered to move across the double pyramid. If a switch on the
left is pressed, the lizard moves counterclockwise, if a switch on
the right is pressed, the lizard moves clockwise. Each switch is
marked with two numbers (see picture on the right). The upper number
indicates the number of steps the lizard moves if the switch is
pressed. The lower number indicates how often a switch may be pressed.
(That is, one may order the lizard only three times to move four steps
counterclockwise etc.) Each step the lizars stops on gets marked
(in the game: lighted), but if the lizard stops on a step for the
second time, the marking is removed again. (As an example, the bottom
picture on the right shows the state after the switches $r_3$, $l_1$,
$l_2$, $r_1$ have been pressed (in this order). Note the reduced
counters on the switches.) The puzzle is solved if every step of the
double pyramid is marked. That is, we are looking for an order in which
to press the switches, so that the lizard stops on each step once.

In the game Timelapse$^{\mbox{\scriptsize\sc tm}}$ one can find a hidden
scroll, on which the solution to the puzzle is stated. However, one
may also consider to solve it with a computer program (e.g.\ by
backtracking, simulated annealing, or an evolutionary algorithm).
How? If possible, provide a solution to the puzzle. Additional
question: How large is the search space (number of solution candidates)?

%-----------------------------------------------------------------------

\end{document}
