Simulated annealing-global optimization algorithm

1. Simulated Annealing Algorithm for Seismic Inversion By: Akhil Prabhakar 5yr Integrated M.Tech . Geophysical Technology IIT Roorkee * Please view in ‘Slideshow’

2. Introduction to seismic inversion Generally most seismic/petro-physical inversion techniques are model based inversions. They start with an initial guess model. Then, Compute the synthetic response for the guess model. C ompare it with the observed data to evaluate misfit between the observed and synthetic. Keep on doing this till they find a model which gives the least or acceptable misfit. Thus, these inversion algorithms are mainly search algorithms which search for minimum misfit model. Different models give different misfit Misfit Objective: search for minimum misfit model

3. Simulated Annealing is one of the search algorithms…! Local search techniques, such as steepest descend method, are very good in finding local minima . However, difficulties arise when the global minima is different from the local minima . Since all the immediate neighboring points around a local minima have worse misfit than it, local search can not proceed once trapped in a local minima point. We need some mechanism that can help us escape the trap of local minima . And the simulated annealing is one of such methods. starting point descend direction local minima global minima barrier to local search Misfit

4. Simulated Annealing Process The name of simulated annealing origins from the simulation of annealing process of heated solids. Annealing denotes a physical process in which a solid in a heat bath is heated up by increasing the temperature of the heat bath to a maximum value at which all particles of the solid randomly arrange themselves in the liquid phase, followed by cooling through slowly lowering the temperature of the heat bath. In this way, all particles arrange themselves in the low energy ground state of a corresponding lattice. In global optimization problems, we make an analogy to the aforementioned process. The basic idea is that by allowing the search process to proceed in an unfavorable direction occasionally, we might be able to escape the trap of local min ima and reach the global minima .

5. Simulated Annealing Algorithm ‘Misfit’= (Observed-Synthetic) 2 Let ‘Misfit’ be an Evaluating function to evaluate quality of a model Lesser the misfit better the model Evaluate Misfit for starting model Now choose a neighboring point Evaluate Misfit for this neighboring model Accept this model with some Probability (P) Expression of Probability (P) for accepting a solution is derived from the process of Annealing. This probabilistic approach will allow us to accept a neighboring ‘bad’ model ( ie . with greater misfit) and hence escape one valley of local minimum local minima starting point barrier to local search Probability expression from annealing will help jump this barrier

6. Algorithm-Details Probability of accepting a neighboring model is given by: P = Value of max(T) is changed with each iteration. Initially T is very large, say 10 10 If new objective misfit > old objective misfit, then ∆>0 Exponential term becomes exp (1/infinity) = 1 Thus, P = ½ Hence, There is a probability (of ½) that neighboring ‘bad’ model giving a higher misfit is accepted. This will enable us escape the ‘local barrier’ as discussed earlier. T – a control parameter analogous to ‘Temperature’ in Thermodynamics equation of Annealing ∆ is Change in misfit as we go from initial model to neighboring model which is analogous to change in energy in Annealing Now cooling is done ie . Value of T is reduced slowly to 0 When T reaches 0 Exponential term becomes exp (∆/0) = (infinity) if ∆> 0 & -(infinity) if ∆<0 Thus , P = 0 when ∆> 0 and P=1 when ∆<0 Therefore, only ‘good’ models with lesser misfit will be accepted now.

7. Algorithm details… This algorithm helps to search for a global minimum misfit giving model . It initially searches for global minima by jumping valleys, but later (when T=0) gets trapped in the valley with global minima. But it is a double edged sword. Help escaping the local min ima . desired effect Might pass global min ima after reaching it adverse effect

8. Algorithm- Advantages and Disadvantages Strengths can deal with highly nonlinear models, chaotic and noisy data and many constraints. is a robust and general technique. main advantages over other local search methods are its flexibility and its ability to approach global optimality . is quite versatile since it does not rely on any restrictive properties of the model Weaknesses: a lot of choices are required to turn it into an actual algorithm. t here is a clear tradeoff between the quality of the solutions and the time required to compute them. d elicate tailoring work is required to account for different classes of constraints and to fine-tune the parameters of the algorithm. the precision of the numbers used in implementation can have a significant effect upon the quality of the outcome.