Deck 14: Metaheuristics

Question 1

Suppose you are applying a simulated annealing algorithm to a certain problem,where T is the parameter that measures the tendency to accept the current candidate to be the next trial solution.You now have come to an iteration where the current value of T is T = 4,the value of the objective function for the current trial solution is 40,and the value of the objective function for the current candidate to be the next trial solution is 36.(a)Using the standard move selection rule,determine the probability of accepting this candidate to be the next trial solution when the objective is maximization of the objective function.(b)What is this probability when the objective is instead minimization of the objective function?

Answer 1

(a)The key to solving this problem is to remember that if Z_c = objective function value for the current trial solution,Z_n = objective function value for the current candidate to be the next trial solution,so Z_c = 40 and Z_n = 36,then the move selection rule under maximization says If Z_n ≥ Z_c ,always accept this candidate; if Z_n < Z_c ,accept the candidate with the following probability: Prob{acceptance} = e^x where x = .Here Z_n = 36 < 40 = Z_c and x = = -1,so Prob{acceptance} = e^-1.(b)With the objective of minimization instead,Z_n and Z_c are reversed in the above formulas.Therefore,since Z_c > Z_n ,the candidate always is accepted,so Prob{acceptance} = 1.