Simulated Annealing for global optimization

50 %
50 %
Information about Simulated Annealing for global optimization

Published on June 27, 2014

Author: akhilprabhakar


Simulated Annealing Algorithm for Seismic Inversion: Simulated Annealing Algorithm for Seismic Inversion By: Akhil Prabhakar 5yr Integrated M.Tech . Geophysical Technology IIT Roorkee *Please view in ‘Slideshow’ Introduction to seismic inversion: 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 Simulated Annealing is one of the search algorithms…!: 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 Simulated Annealing Process: 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 minima and reach the global minima. Simulated Annealing Algorithm: 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 Algorithm-Details: 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. Algorithm details… : 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 Algorithm- Advantages and Disadvantages: 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.

Add a comment

Related presentations

Related pages

Generalized Simulated Annealing for Global Optimization ...

CONTRIBUTED RESEARCH ARTICLES 13 Generalized Simulated Annealing for Global Optimization: The GenSA Package An Application to Non-Convex Optimization in ...
Read more

Simulated annealing - Wikipedia

Simulated annealing (SA) is a probabilistic technique for approximating the global optimum of a given function. Specifically, it is a ...
Read more

Global optimization - Wikipedia

Global optimization is distinguished from regular optimization by its focus on finding the ... For simulated annealing: S. Kirkpatrick, C.D ...
Read more

Numerical Nonlinear Global Optimization—Wolfram Language ...

... and simulated annealing. ... Global optimization problems can be solved exactly using Minimize or numerically using NMinimize.;
Read more

Simulated Annealing - MATLAB & Simulink

Learn how to find global minima for nonlinear problems using simulated annealing. ... problems using simulated annealing, see Global Optimization ...
Read more

Global Optimization Toolbox - MATLAB -

Global Optimization Toolbox Solve multiple maxima, multiple minima, and ... pattern search, genetic algorithm, and simulated annealing solvers.
Read more

Simulated Annealing -- from Wolfram MathWorld

Simulated Annealing. There are certain optimization problems that ... it cannot get from there to the global minimum. Simulated annealing improves this ...
Read more


GLOBAL OPTIMIZATION OF STATISTICAL FUNCTIONS WITH SIMULATED ANNEALING* William L. Goffe University of North Carolina at Wilmington, Wilmington, NC 28403
Read more


THE THEORY AND PRACTICE OF SIMULATED ANNEALING Darrall Henderson ... considerable interest in using simulated annealing for global optimization over regions
Read more

Simulated Annealing – Wikipedia

Simulated Annealing ... (global) tiefsten Punkt. ... Simulated Annealing Beats Metropolis in Combinatorial Optimization. In: ...
Read more