\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 2018.01.18

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

\vskip3ex
\centerline{\bf Exercise Sheet 5}

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

\subsubsection*{Exercise 17 \quad\rm Genetic Operators}

\begin{enumerate}\itemsep0pt
\item[a)] Consider the two chromosomes
          \[ [3, 9, 1, 6, 8, 8, 5, 7, 1, 5, 5, 4]
             \qquad\mbox{and}\qquad
             [4, 6, 4, 9, 2, 7, 9, 0, 8, 8, 6, 5]. \]
          Construct two children of these chromosomes with the help
          of shuffle crossover using the permutation
          $(3, 1, 6, 7, 4, 11, 8, 12, 5, 10, 2, 9)$
          and a cut between the fifth and the sixth gene! \\
          How may shuffle crossover be implemented efficiently? \\
          (Hint: Is it actually necessary to execute the
          shuffling and unshuffling explicitly?)
\item[b)] Consider the two chromosomes
          \[ [8, 3, 5, 7, 0, 4, 11, 1, 9, 6, 10, 2]
             \qquad\mbox{and}\qquad
             [2, 8, 0, 1, 6, 10, 9, 3, 5, 7, 4, 11]. \]
          Construct two children of these chromosomes with the help of
          uniform order-based crossover using the bit mask
          $[1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1]$!
\item[c)] Consider the two chromosomes
          \[ [5, 1, 6, 7, 0, 8, 9, 3, 10, 11, 2, 4]
             \qquad\mbox{and}\qquad
             [7, 11, 8, 0, 10, 1, 5, 4, 9, 3, 6, 2]. \]
          Construct one child of these chromosomes with the help
          of the method of edge recombination!
\end{enumerate}

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

\subsubsection*{Exercise 18 \quad\rm Interpretation of a Schema}

In the lecture schemata were illustrated in two different ways:
as hyperplanes in a unit hypercube and as ``stripe patterns''
of a one-dimensional function, which indicated the regions of captured
argument values. The latter illustration assumed a standard binary
encoding of the numbers. In this exercise, however, we want to consider
a Gray code instead. Represent the schemata
\begin{enumerate}\itemsep0pt
\item[a)] 0 * * * ... *
\item[b)] * * 1 * ... *
\item[c)] * 1 * 0 * ... *
\end{enumerate}
for Gray codes and a one-dimensional function in the interval $[0,1]$!\\
(In order to compute Gray codes, use the method that was discussed
in the lecture.)

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

\subsubsection*{Exercise 19 \quad\rm Defining Length of a Schema}

In the schema theorem the {\em defining length\/} of a schema~$h$
is used to measure the probability that a chromosome that fits a
schema~$h$ before crossover, no longer fits this schema after crossover.
For this we assumed in the definition of the defining length that
one-point crossover is used. How does one have to change the definition
of the defining length if
\begin{enumerate}\itemsep0pt
\item[a)] two-point crossover
\item[b)] uniform crossover
\end{enumerate}
are used instead? (Hint: How can one measure the distance of genes in
the two parts that end up in the same child with two-point crossover?)

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

\subsubsection*{Exercise 20 \quad\rm Order of a Schema}

In the schema theorem the {\em order\/} of a schema~$h$ is used to
measure the probability that a chromosome that fits a schema~$h$ before
mutation, no longer fits this schema after mutation. Which corresponding
quantities may one use for the one-parent genetic operators
\begin{enumerate}\itemsep0pt
\item[a)] pair swap
\item[b)] moving a subsequence (of genes)
\end{enumerate}
in order to assess their effect on the fit to a schema?

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

\end{document}
