Simulated Annealing PDF

Chapter 3: Simulated Annealing 1 / 39  3.1 Motivations I Simulated annealing (SA): SA is a metaheuristics introduced by Kirkpatrick et al. in 1983 I Taking inspiration from the physical annealing process in metallurgy I Annealing: is a slow...

Chapter 3: Simulated Annealing 1 / 39  3.1 Motivations I Simulated annealing (SA): SA is a metaheuristics introduced by Kirkpatrick et al. in 1983 I Taking inspiration from the physical annealing process in metallurgy I Annealing: is a slow cooling process in metallurgy that improves ductility and facilitates the work of metals ) yields a global minimum (recuit en français) I Quenching: is a rapid cooling process in metallurgy that improves hardness of the metal while making it more fragile ) yields a local minimum (trempe en français) 2 / 39  Illustration local minimum Global minimum of of energy. Energy. 3 / 39  Intuition about the inner workings of SA fitness your energy) (Fictitious I Natural processes tend to minimize the energy of systems I At high temperature, the system explores a wider range of I available states s "Fictitious" temperature. I Whenever, a system stumbles upon a low-energy state, it will stay there unless it is provided with sufficient energy to overcome the neighboring energy barriers I As the temperature is decreased (i.e., cooling), the system will be constrained to exploit ever lower energy jumps to eventually settle in a state, which hopefully is the global minimum 4 / 39  3.2 Principles of the SA Algorithm I SA seeks the minimum of a given objective function akin to energy and therefore denoted as E I SA follows the basic principles of all metaheuristics: 1. Selects an arbitrary admissible initial solution (initial configuration) 2. An initial “temperature” is selected (specificity of SA; more about this later) 3. Moves from the current configuration to reach its neighbors with probability p: ( E /T ) p = min(1, e ), (1) where E = Enew Eold This is the so-called Metropolis rule: the move is accepted if ( E /T ) Random(0, 1) < e Hence, xnew is rejected with probability 1 p ! then generate another xnew. 5 / 39  ¥¥ E initial → E current E new neighborho od the of current configuratio D E= E new-E current n 4 " e.AT#,Not " ° ii. Hhatbad= " localsearch. D E EO D E >0 e-DEH p = < I EnowE Ecurrent Enew>Earn, → pining, ↳ Fitnessdegradation enablingexploration configuratio newn alwaysaccepted.  'EH * why e- ? (inspiration from Statistical Physics ¥ 5 Boltzmann constant Boltzmann factor →  Choice of the temperature T (1/2) #operating:L I Specificity of SA as a metaheuristics I T can be seen as a dynamic guiding parameter I We start by chosing an initial temperature (more about that later) I If T is large, SA easily accepts a fitness degradation of the configuration (i.e., energy increase) I But as E increases, the move acceptance decreases I During this process, we will progressively decrease the temperature according to a temperature/cooling schedule (more about that later too) I In summary: We start by a high-amplitude exploration (high temperature), and we slowly reduce exploration to promote exploitation/intensification at lower temperatures 6 / 39  Choice of the temperature T (1/2) 2 1 ¥ 4 1µ§¥¥} T=1 be Metropolis Probability T=0.3 1 E - seamen. 0 -2 'affiliation. µie"% Rule?'"- ∆E 2 Metropolis Ey p = min(1, exp( E /T ) 7 / 39  Flow diagram of SA Start initiation, → initial configuration Generate initial state S_current Set initial temperature T → select T o= initial temperature iterationcount N_iter=0; N_accept=0 ) 2 counters→ → acceptancecount tiko.at#9rea- ±::::.. Generate S_new N_iter ++ reduce temperature IF rand(0,1)