# Exercises for Chapter 16: Theory

1. Let S1={*0**11***0**} and S2={*****0*1****} be two schemata.
1. Give the order and the defining length of S1 and S2.
2. What is the probability for one-point crossover with crossover
rate pc that crossover breaks S1, or S2? (i.e., the probability that the child created by the operator does not belong to the given schema.)
3. What is the probability that mutation with mutation rate pm
breaks S1, or S2?
4. What is the probability that S1 or Ssurvives the application of both crossover and mutation?
5. Is it correct to call one of these two schemata a
“building block”? Explain why, or why not.
2. Whilst optimising a three-bit problem, you notice that your
population, of size 100, consists of 25 copies each of strings
100 (with fitness 10), 111 (with fitness 20), 011 (with fitness
15), and 010 (with fitness 15).

1. What is the estimated fitness of schema 1\#\# ?
2. Assuming fitness proportionate selection with no
crossover or mutation, show one way by which you could
calculate the estimated fitness of that schema in the
next generation.
3. In a simple two-dimensional model of protein structure
prediction, a solution consists of a sequence of moves
(north/east/west/south) on a square grid. The amino acid
residues, which compose the protein, are then mapped onto this
path, giving the structure of the folded protein. Good solutions
typically exhibit a high degree of local structure. That is to
say that they can be seen as the concatenation of secondary
structure “motifs”. Explain how this domain knowledge may be
used to guide the choice of recombination operators for this
problem.