QE2013_AC-3_ECE580-1
(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} $
