Stochastic tunneling (STUN) is one approach to global optimization among several others and is based on the Monte Carlo method-sampling of the function to be minimized. Global optimization is a branch of applied mathematics and numerics that deals with the optimization of a function or a set of functions to some criteria. ... Monte Carlo methods are algorithms for solving various kinds of computational problems by using random numbers (or more often pseudo-random numbers), as opposed to deterministic algorithms. ...
Idea
Schematic one-dimensional test function (black) and STUN effective potential (red & blue), where the minimum indicated by the arrows is the best minimum found so far. All wells that lie above the best minimum found are suppressed. If the dynamical process can escape the well around the current minimum estimate it will not be trapped by other local minima that are higher. Wells with deeper minima are enhanced. The dynamical process is accelerated by that.
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 ΔE. The acceptance probability of such a trial jump is in most cases chosen to be (Metropolis criterion) with an appropriate parameter β. Plot of the STUN-transformation in global optimization - subtopic Stochastic tunneling. ... Plot of the STUN-transformation in global optimization - subtopic Stochastic tunneling. ... Monte Carlo methods are algorithms for solving various kinds of computational problems by using random numbers (or more often pseudo-random numbers), as opposed to deterministic algorithms. ...
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. A spin glass is a disordered material exhibiting high magnetic frustration. ...
This goal is achieved by Monte-Carlo-sampling of a transformed function that lacks this slow dynamics. In the "standard-form" the transformation reads where fo is 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.
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. ... Parallel tempering is a simulation method aimed at improving the dynamic properties of Monte Carlo method simulations. ... A genetic algorithm (GA) is a heuristic used to find approximate solutions to difficult-to-solve problems through application of the principles of evolutionary biology to computer science. ...
References
K. Hamacher and W. Wenzel. The Scaling Behaviour of Stochastic Minimization Algorithms in a Perfect Funnel Landscape. Phys. Rev. E, 59(1):938-941, 1999.
W. Wenzel and K. Hamacher. A Stochastic tunneling approach for global minimization. Phys. Rev. Lett., 82(15):3003-3007, 1999.
Stochastic optimization methods are now being used in a multitude of applications, ranging from circuit design on silicon wafers to airline flight schedules.
Stochastic optimization methods successively improve one or several configurations of the underlying model to obtain an approximant of the global optimum of the PES.
An alternate approach to simplify the underlying PES is used in the stochastictunneling method, where the dynamical process explores the transformed potential energy surface.
Feeds |
Contact