numerical analysis Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of numerical methods ...

, stochastic tunneling (STUN) is an approach to

global optimization Global optimization is a branch of applied mathematics and numerical analysis that attempts to find the global minima or maxima of a function or a set of functions on a given set. It is usually described as a minimization problem because the max ...

based on the

Monte Carlo method Monte Carlo methods, or Monte Carlo experiments, are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. The underlying concept is to use randomness to solve problems that might be determi ...

- sampling of the function to be objective minimized in which the function is nonlinearly transformed to allow for easier tunneling among regions containing function minima. Easier tunneling allows for faster exploration of sample space and faster convergence to a good solution.

Idea

image:stun.jpg, 400px, 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 Potential well, 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.

-based optimization techniques sample the

objective function In mathematical optimization and decision theory, a loss function or cost function (sometimes also called an error function) is a function that maps an event or values of one or more variables onto a real number intuitively representing some "cost ...

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

\min\left(1;\exp\left(-\beta\cdot\Delta E\right)\right)

(

Metropolis A metropolis () is a large city or conurbation which is a significant economic, political, and cultural center for a country or region, and an important hub for regional or international connections, commerce, and communications. A big ci ...

criterion) with an appropriate parameter

\beta

. The general idea of STUN is to circumvent the slow dynamics of ill-shaped energy functions that one encounters for example in

spin glass In condensed matter physics, a spin glass is a magnetic state characterized by randomness, besides cooperative behavior in freezing of spins at a temperature called 'freezing temperature' ''Tf''. In ferromagnetic solids, component atoms' magne ...

es by tunneling through such barriers. This goal is achieved by Monte Carlo sampling of a transformed function that lacks this slow dynamics. In the "standard-form" the transformation reads

f_:=1-\exp\left(
-\gamma\cdot\left( E(x)-E_o\right) \right)

where

E_o

is the lowest function value found so far. This transformation preserves the loci of the minima.

f_

is then used in place of

E

in the original algorithm giving a new acceptance probability of

\min\left(1;\exp\left(-\beta\cdot\Delta f_\right)\right)

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

Dynamically adaptive stochastic tunneling

A variation on always tunneling is to do so only when trapped at a local minimum.

\gamma

is then adjusted to tunnel out of the minimum and pursue a more globally optimum solution.

Detrended fluctuation analysis In stochastic processes, chaos theory and time series analysis, detrended fluctuation analysis (DFA) is a method for determining the statistical self-affinity of a signal. It is useful for analysing time series that appear to be long-memory proces ...

is the recommended way of determining if trapped at a local minimum.

Other approaches

Simulated annealing Simulated annealing (SA) is a probabilistic technique for approximating the global optimum of a given function. Specifically, it is a metaheuristic to approximate global optimization in a large search space for an optimization problem. ...

Parallel tempering Parallel tempering in physics and statistics, is a computer simulation method typically used to find the lowest free energy state of a system of many interacting particles at low temperature. That is, the one expected to be observed in reality ...

* Genetic algorithm *

Differential evolution In evolutionary computation, differential evolution (DE) is a method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. Such methods are commonly known as metaheuristics as ...

References

* * * * * {{Cite journal , author = Mingjie Lin , title = Improving FPGA Placement with Dynamically Adaptive Stochastic Tunneling , journal =

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems ''IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems'' (sometimes abbreviated ''IEEE TCAD'' or ''IEEE Transactions on CAD'') is a monthly peer-reviewed scientific journal covering the design, analysis, and use of computer ...

, volume = 29 , date=December 2010 , pages = 1858–1869 , issue = 12 , ref = lin , doi=10.1109/tcad.2010.2061670 , url = https://zenodo.org/record/1232243 Stochastic optimization