Stochastic tunneling
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.
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 <math>\Delta E<math>. The acceptance probability of such a trial jump is in most cases chosen to be
<math> \min\left(1;\exp\left(-\beta\cdot\Delta E\right)\right)
<math> (Metropolis criterion) with an appropriate parameter <math>\beta<math>.
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 a
transformed function that lacks this slow dynamics. In the "standard-form"
the transformation reads <math>f_{STUN}:=1-\exp\left(
-\gamma\cdot\left( f(x)-f_o\right) \right)<math> where <math>f_o<math>
is the lowest function value found so far. This transformation preserves the locii of the minima.
The effect of such a transformation is shown in the graph.
Other approaches
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.
- Metropolis et al., J.Chem.Phys. 1954.
