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
Stun.jpg
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 loci 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.