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

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

The on-line accompaniment to the book Introduction to Evolutionary Computing