Midterm-2022-sol

ECE 788 Midterm Name: ____________ 1. Please describe at least two key operations in genetic algorithm, along with an example to illustrate each operation. (2 points) ANS: crossover and mutation. 2. Please describe the key advantage of simulated annealing over the simple hill climbing. (2 points) ANS: SA can probabilistically accept a worse solution, so that it will not always get trapped at a local optimum. 3. We went over the following example in class. Please explain why the string no. in the right table is 1, 2, 2, and 4. (4 points) ANS: From the left table, the counts of string 1, 2, 3, and 4 are 1, 2, 0, 1, respectively, based upon the fitness (and in turn the prob.). 4. Please state whether the following statements are correct and explain why if incorrect . (21 points) a. Genetic algorithm is a global search algorithm. Correct . b. In Bees algorithm, suppose there are n scout bees and among them, m sites will be chosen for neighborhood search due to their high fitness. Therefore, n-m sites will be sent with more bees than the m sites to further improve the fitness. Incorrect . The n-m sites will do random search without being sent with more bees. c. In simulated annealing, the algorithm is guaranteed to converge to the global optima in all cases. Incorrect . It is guaranteed to converge when the temperature is lowed gradually. d. Simulated annealing accepts a candidate solution with a higher fitness deterministically and rejects a candidate solution with a lower fitness with a probability, which is a constant across iterations. Incorrect . The probability will change across iterations. e. In Bees algorithm, the neighborhood size is kept static across the run, while in simulated annealing, the temperature is lowered in every iteration. Incorrect . The neighborhood size can change based upon the improvement of fitness. f. Bees algorithm focuses on neighborhood search without involving global search. Incorrect . It involves global search as well. g. Simulated annealing focuses on neighborhood search with global search.

Correct . 5. Please show the result of Child 2 , using precedence preservative crossover (PPX) in Paper 1. (5 points) Parent 1 : 2871063954, +x −z −x +x +y +y +z −y −z −z, NNDNDD, DDNN, 1101022011, SPPSASSPPP Parent 2 : 1276340859, +x +x −x +y +z −z +y −z −z −y, NNDDDN, DNND, 1102210110, SSPSSPAPPP Mask for Child 1 : 2 2 2 1 1 2 2 2 1 2 Mask for Child 2 : 2 1 1 2 1 2 2 1 2 2 Child 2 : ANS: see P.5 in paper 1. 1287063945, +x +x −z −z +y +y +z −y −z −z, NNNDDD, DDNN, 1110022011, SSPPASSPPP 6. Please point out at least two differences between genetic algorithm and simulated annealing. (5 points) Ans: 1) SA is guaranteed to converge if the temperature is lowered gradually, while GA is not 2) GA is population based, while SA uses a single solution. 3) Many portions of GA are more suitable for implementation on parallel architectures, while SA is an inherently serial algorithm. 7. For f(x)=sin(x) - cos(x), where 0 ≤ x ≤ 2  . Please show the steps of using simulated annealing to find the global minima. In particular  The initial temperature is 10, and after each iteration the temperature is reduced by half.  The initial x is 0, and after each iteration x is incremented by  /4.  If the acceptance probability is greater than 0.7, we accept the solution. Otherwise, we reject it.  Please show the details of 8 iterations. (20 Points) ANS: Step 1: x=0, x’=  /4, T=10, f(x)=sin(0)-cos(0)=-1, f(x’)=sin(  /4)-cos(  /4)=0, f(x)- f(x’)=-1<0, Conditional accept: P=exp[(f(x)- f(x’))/T]=0.90, Accept Step 2: x=  /4, x’=  /2, T=5, f(x)=sin(  /4)-cos(  /4)=0, f(x’)=sin(  /2)-cos(  /2)=1, f(x)- f(x’)=-1<0, Conditional accept: P=exp[(f(x)- f(x’))/T]=0.82, Accept Step 3: x=  /2, x’=  3/4, T=2.5 f(x)=sin(  /2)-cos(  /2)=1, f(x’)=sin(  3/4)-cos(  3/4)=1.414, f(x)- f(x’)=-0.414<0, Conditional accept: P=exp[(f(x)- f(x’))/T]=0.84, Accept Step 4: x=  3/4, x’=  , T=1.25, f(x)=sin(  3/4)-cos(  3/4)=1.414, f(x’)=sin(  )-cos(  )=1 f(x)- f(x’)=0.414>0, Accept Step 5: x=  , x’=  5/4, T=0.625, f(x)=sin(  )-cos(  )=1, f(x’)=sin(  5/4)-cos(  5/4)=0 f(x)- f(x’)=1>0, Accept Step 6: x=5  /4, x’=  3/2, T=0.3125, f(x)=sin(  5/4)-cos(  5/4)=0, f(x’)=sin(  3/2)-cos(  3/2)=-1 f(x)- f(x’)=1>0, Accept

11. In genetic algorithms, we learned how to map real values to bit strings. (15 points) 1) Please explain the equation. Ans: The term y-x is the range and 2^L-1 is the number of quantization intervals. Therefore, the term (y-x)/( 2^L-1) is the length of each quantization interval. It is further multiplied by the value calculated from its binary representation - this represents the offset from x. 2) Please explain why a high precision requires long chromosomes. Please do that through an example . Ans: a high precision requires a small quantization interval (y-x)/( 2^L-1), and therefore L needs to be large. 3) Explain why long chromosomes can lead to slow evolution. Ans: long chromosomes require more operations to be done for mutation. 12. (Bonus Question) Please answer the following questions for Paper 2. (10 points) 1) Please show a schematic (i.e., an example) of the following algorithm for two iterations. Show at least two resident solutions in each iteration. You may implement your own crossover_mutation () and select ().

2) Please explain the key difference versus simulated annealing for the following algorithm. Ans: it is deterministic while the selection in SA is probabilistic.