Simulated AnnealingSimulated AnnealingSimulated AnnealingInterpretation of the Algorithm - SAInterpretation of the Algorithm - SAAdvantages of Simulated AnnealingDisadvantages of Simulated AnnealingSimulated Annealing•Simulated Annealing•Simulated Annealing•Interpretation of the Algorithm - SA•An essential feature of simulated annealing that it can climb out from a local minimum, since it can accept worse neighbors as the next step. Such an acceptance happens with a probability that is smaller if the neighbor's quality is worse. That is, with larger ΔE the acceptance probability gets smaller. At the same time, with decreasing temperature all acceptance probabilities get smaller. This means, initially the system is “hot”, makes more random movement, it can relatively easily jump into worse states, too. On the other hand, over time it “cools down”, so that worsening moves are accepted less and less frequently. Finally, the system gets “frozen”.Interpretation of the Algorithm - SA•This process can be interpreted such that initially, when the achieved quality is not yet too good, we are willing to accept worse positions in order to be able to climb out of local minimums, but later, with improving quality we tend to reject the worsening moves more and more frequently. These tendencies can be balanced and controlled by the choice of the cooling schedule. If it is chosen carefully, then convergence to a global optimum can be guaranteed (proven mathematically).Advantages of Simulated Annealing•Improves greedy local search by avoiding getting trapped in a local optimum.•With appropriately chosen cooling schedule the algorithm converges to the global optimum.Disadvantages of Simulated Annealing•Convergence to the optimum can be slow.•There is no general way of estimating the number of iterations needed for a given problem, so we cannot easily guarantee that the result is within a certain error bound of the global
View Full Document
Unlocking...