Question 2: Simulated Annealing [25 points] Consider a state space consisting of integers. Suppose that the successors of a state z include all integers in r 10,10, ncluding r itself. Consider the score function f()max14 -rl,2 - r - 6,2 - 6| It has three peaks with one forming a unique global maximum. Recall that a random successor y is generated on each iteration of simulated annealing. If this successor is better than the current state r, it is always accepted. If it is not better, it will still be accepted with ex Recall that to do something with probability p, you generate a random number z E [0, 1 uniformly and if z p you do it Use the temperature cooling scheme T(i) 2(0.9) where i is the iteration number. E.g., for the first iteration, the temperature will be T(1) 2(0.9)| 1.8 Perform 8 iterations of simulated annealing using r-2 as your starting point. We already "randomly picked a successor y at each iteration for you, and also generated a "random number" z at that iteration for you to decide whether to go to an inferior successor, should you need it. These are listed in Table 1 Use these numbers. For each iteration, write down (1) the current point, (2) the temperature (rounded to the nearest thousandth), and (3) the probability of moving to the successor given the successor and the temperature. Iteration NumberRandom Successor y Random Number z 0.102 0.223 0.504 0.493 0.312 0.508 0.982 0.887 2 Table 1: Successor States and Random Numbers Question 2: Simulated Annealing [25 points] Consider a state space consisting of integers. Suppose that the successors of a state z include all integers in r 10,10, ncluding r itself. Consider the score function f()max14 -rl,2 - r - 6,2 - 6| It has three peaks with one forming a unique global maximum. Recall that a random successor y is generated on each iteration of simulated annealing. If this successor is better than the current state r, it is always accepted. If it is not better, it will still be accepted with ex Recall that to do something with probability p, you generate a random number z E [0, 1 uniformly and if z p you do it Use the temperature cooling scheme T(i) 2(0.9) where i is the iteration number. E.g., for the first iteration, the temperature will be T(1) 2(0.9)| 1.8 Perform 8 iterations of simulated annealing using r-2 as your starting point. We already "randomly picked a successor y at each iteration for you, and also generated a "random number" z at that iteration for you to decide whether to go to an inferior successor, should you need it. These are listed in Table 1 Use these numbers. For each iteration, write down (1) the current point, (2) the temperature (rounded to the nearest thousandth), and (3) the probability of moving to the successor given the successor and the temperature. Iteration NumberRandom Successor y Random Number z 0.102 0.223 0.504 0.493 0.312 0.508 0.982 0.887 2 Table 1: Successor States and Random Numbers
