Simulated Annealing - A Optimisation Technique

Simulated Annealing

1. SIMULATED ANNEALING (Global Optimization Search Techniques ) PRESENTED BY – S AUSTIN MOSES 1

2. MAIN PROBLEM -> OPTIMIZATION 2 TABU SEARCH , GREEDY APPROACH , ETC SIMMULATED ANNEALING, PARTICLE SWARM OPTIMIZATION (PSO), GRADIENT DESCENT ETC

3. Difficulty in Searching Global Optima 3 starting point descend direction local minima global minima barrier to local search

4. Background: Annealing Simulated annealing is so named because of its analogy to the process of physical annealing with solids,. A crystalline solid is heated and then allowed to cool very slowly until it achieves its most regular possible crystal lattice configuration (i.e., its minimum lattice energy state), and thus is free of crystal defects. If the cooling schedule is sufficiently slow, the final configuration results in a solid with such superior structural integrity. Simulated annealing establishes the connection between this type of thermodynamic behaviour and the search for global minima for a discrete optimization problem. 4

5. Simulated Annealing(SA) SA is a global optimization technique. SA distinguishes between different local optima. SA is a memory less algorithm, the algorithm does not use any information gathered during the search SA is motivated by an analogy to annealing in solids. Simulated Annealing – an iterative improvement algorithm. 5

6. Simulated Annealing 6 Local Search Solution space Cost function ?

7. Analogy Slowly cool down a heated solid, so that all particles arrange in the ground energy state At each temperature wait until the solid reaches its thermal equilibrium Probability of being in a state with energy E : Pr { E = E } = 1/Z(T) . exp (-E / k B .T ) E Energy T Temperature k B Boltzmann constant Z(T) Normalization factor (temperature dependant ) 7

8. Simulation Of Cooling (Metropolis 1953) At a fixed temperature T : Perturb (randomly) the current state to a new state E is the difference in energy between current and new state If E < 0 (new state is lower), accept new state as current state If E  0 , accept new state with probability Pr (accepted) = exp (- E / k B .T ) Eventually the systems evolves into thermal equilibrium at temperature T . When equilibrium is reached, temperature T can be lowered and the process can be repeated 8

9. Relationship Between Physical Annealing And Simulated Annealing Thermodynamic Simulation Combinatorial Optimization System states Solutions Energy Cost Change of State Neighbouring Solutions Temperature Control Parameter T Frozen State Heuristic Solution 9

10. Simulated Annealing Same algorithm can be used for combinatorial optimization problems: Energy E corresponds to the Cost function C Temperature T corresponds to control parameter c Pr { configuration = i } = 1/Q(c) . exp (-C( i ) / c) C Cost c Control parameter Q(c) Normalization factor (not important) 10

11. Ball On Terrain Example – SA Vs. Greedy Algorithms 11

12. 12 Advantages Can deal with arbitrary systems and cost functions. Statistically guarantees finding an optimal solution. Is relatively easy to code, even for complex problems. Generally gives a ``good'' solution This makes annealing an attractive option for Optimization problems where heuristic ( specialized or problem specific) methods are not available.

13. Disadvantages 13 Repeatedly annealing with a 1/log k schedule is very slow, especially if the cost function is expensive to compute. For problems where the energy landscape is smooth, or there are few local minima, SA is overkill - simpler, faster methods (e.g., gradient descent) will work better. But generally don't know what the energy landscape is for a particular problem. The method cannot tell whether it has found an optimal solution. Some other complimentary method (e.g. branch and bound) is required to do this.

14. Conclusions Simulated Annealing algorithms are usually better than greedy algorithms, when it comes to problems that have numerous locally optimum solutions. 14

15. References 15 P.J.M. van Laarhoven , E.H.L. Aarts , Simulated Annealing: Theory and Applications, Kluwer Academic Publisher, 1987. A. A. Zhigljavsky , Theory of Global Random Search, Kluwer Academic Publishers, 1991.

16. Thank You