QE2013_AC-3_ECE580-1

Part 1,2,3,4,5

(i)
Solution:
The conditions for a chromosome from H to be destroyed are: 1. It is chosen for crossover. Probability = $ \frac{1}{2} $. 2. The crossover position is not the last symbol. Otherwise only the last symbol can potentially change and the chromosome will still be in schema H. Probability = $ \frac{5}{6} $. 3. The other chromosome to crossover has a structure such that the chromosome from H will be destroyed after crossover. For example: if the other chromosome is * * * * * 1 *. This probability cannot be determined from the given information, as it depends on the distribution of other chromosomes. Therefore it has an upperbound of 1.

A chromosome from H is destroyed if and only if the 3 conditions above all occur. Therefore

$ P(destroyed)\le \frac{1}{2} \times \frac{5}{6} \times 1 = \frac{5}{12} $

The upper bound is $ \frac{5}{12} $

(ii)
Solution:

      Final Range: 1.0; Initial Range: 20.

      $  \frac{2}{F_{N+1}} \le \frac{1.0}{20} $, or $  F_{N+1} \ge 40 $ 

      So, N + 1 = 9

      Therefore, the minimal iterations is N-1 or 7.

Solution 2:

Since the final range is $ 1.0 $ and the initial range is $ 20 $, we can say $ \frac{2}{F_{N+1}} \le \frac{1.0}{20} or equivalently F_{N+1}} \ge 40 $ From the inequality, we get $ F_{N+1} \ge 40 , so N+1=9 $. Therefore the minimum number of iteration is N-1=7

$ \color{blue}\text{Related Problem: } $ $ \text{Find the final uncertainty range using the Fibonacci method after 6 iterations } $ $ \text{Assume the last step has the form: } 1-\rho_{N-1}=\frac{F_2}{F_3}=\frac{2}{3} \text{The initial range is 10} $

Solution: $ \text{The reduction factor is } \frac{F_{2}}{F_{7+1}} =\frac{1}{34} \text{, So the final range is } 10 \frac{F_{2}}{F_{7+1}}= \frac{5}{17} $

Back to QE2013 AC-3 ECE580