Stochastic tunneling

Stochastic tunneling

Stochastic tunneling (STUN) is an approach to global optimization based on the Monte Carlo method-sampling of the function to be minimized.

Idea

Monte Carlo method-based optimization techniques sample the objective function by randomly "hopping" from the current solution vector to another with a difference in the function value of Delta E. The acceptance probability of such a trial jump is in most cases chosen to be minleft(1;expleft(-etacdotDelta E ight) ight) (Metropolis criterion) with an appropriate parameter eta.

The general idea of STUN is to circumvent the slow dynamics of ill-shaped energy functions that one encounters for example in spin glasses by tunneling through such barriers.

This goal is achieved by Monte Carlo sampling of atransformed function that lacks this slow dynamics. In the "standard-form"the transformation reads f_{STUN}:=1-expleft(-gammacdotleft( f(x)-f_o ight) ight) where f_ois the lowest function value found so far. This transformation preserves the loci of the minima.

The effect of such a transformation is shown in the graph.

Other approaches

* Simulated annealing
* Parallel tempering
* Genetic algorithm
* Differential evolution

References

* Cite journal
author = K. Hamacher
title = Adaptation in Stochastic Tunneling Global Optimization of Complex Potential Energy Landscapes
journal = Europhys. Lett.
volume = 74
issue = 6
pages = 944
year = 2006
doi = 10.1209/epl/i2006-10058-0
* Cite journal
author = K. Hamacher and W. Wenzel
title = The Scaling Behaviour of Stochastic Minimization Algorithms in a Perfect Funnel Landscape
journal = Phys. Rev. E
volume = 59
issue = 1
pages = 938–941
year = 1999
doi = 10.1103/PhysRevE.59.938
* Cite journal
author = W. Wenzel and K. Hamacher
title = A Stochastic tunneling approach for global minimization
journal = Phys. Rev. Lett.
volume = 82
issue = 15
pages = 3003–3007
year = 1999
doi = 10.1103/PhysRevLett.82.3003
* Cite journal
author = Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller and Edward Teller
title = Equation of State Calculations by Fast Computing Machines
journal = The Journal of Chemical Physics
volume = 21
number = 6
month = June
pages = 1087–1092
year = 1953
doi = 10.1063/1.1699114
url = http://scienze-como.uninsubria.it/bressanini/montecarlo-history/mrt2.pdf


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Global optimization — is a branch of applied mathematics and numerical analysis that deals with the optimization of a function or a set of functions to some criteria. General The most common form is the minimization of one real valued function f in the parameter space …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Simulated annealing — (SA) is a generic probabilistic meta algorithm for the global optimization problem, namely locating a good approximation to the global optimum of a given function in a large search space. It is often used when the search space is discrete (e.g.,… …   Wikipedia

  • Stochastisches Tunneln — (STUN) ist eine Methode zur globalen Optimierung, in der die zu minimierende Funktion mit der Monte Carlo Methode abgetastet wird. Prinzip Schematische eindimensionale Testfunktion (Schwarz) und effektives STUN Potential (Rot und Blau), wobei das …   Deutsch Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • Optimization (mathematics) — In mathematics, the term optimization, or mathematical programming, refers to the study of problems in which one seeks to minimize or maximize a real function by systematically choosing the values of real or integer variables from within an… …   Wikipedia

  • List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… …   Wikipedia

  • Globale Optimierung — Das Gebiet der Optimierung in der angewandten Mathematik beschäftigt sich damit, optimale Parameter eines meist komplexen Systems zu finden. „Optimal“ bedeutet, dass eine Zielfunktion minimiert oder maximiert wird. Optimierungsprobleme stellen… …   Deutsch Wikipedia

  • Optimierung (Mathematik) — Das Gebiet der Optimierung in der angewandten Mathematik beschäftigt sich damit, optimale Parameter eines – meist komplexen – Systems zu finden. „Optimal“ bedeutet, dass eine Zielfunktion minimiert oder maximiert wird. Optimierungsprobleme… …   Deutsch Wikipedia

  • Optimierungsalgorithmus — Das Gebiet der Optimierung in der angewandten Mathematik beschäftigt sich damit, optimale Parameter eines meist komplexen Systems zu finden. „Optimal“ bedeutet, dass eine Zielfunktion minimiert oder maximiert wird. Optimierungsprobleme stellen… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”