Contents

Stochastic tunneling

Idea[edit]

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 ${\displaystyle \Delta E}$. The acceptance probability of such a trial jump is in most cases chosen to be ${\displaystyle \min \left(1;\exp \left(-\beta \cdot \Delta E\right)\right)}$ (Metropolis criterion) with an appropriate parameter ${\displaystyle \beta }$.

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 ${\displaystyle f_{STUN}:=1-\exp \left(-\gamma \cdot \left(E($x)-E_{o}\right)\right)} where ${\displaystyle E_{o}}$ is the lowest function value found so far. This transformation preserves the loci of the minima.

${\displaystyle f_{STUN}}$ is then used in place of ${\displaystyle E}$ in the original algorithm giving a new acceptance probability of ${\displaystyle \min \left(1;\exp \left(-\beta \cdot \Delta f_{STUN}\right)\right)}$

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

Dynamically adaptive stochastic tunneling[edit]

A variation on always tunneling is to do so only when trapped at a local minimum. ${\displaystyle \gamma }$ is then adjusted to tunnel out of the minimum and pursue a more globally optimum solution. Detrended fluctuation analysis is the recommended way of determining if trapped at a local minimum.

Other approaches[edit]

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

References[edit]

• K. Hamacher (2006). "Adaptation in Stochastic Tunneling Global Optimization of Complex Potential Energy Landscapes". Europhys. Lett. 74 (6): 944–950. Bibcode:2006EL.....74..944H. doi:10.1209/epl/i2006-10058-0. S2CID 250761754.
• K. Hamacher & W. Wenzel (1999). "The Scaling Behaviour of Stochastic Minimization Algorithms in a Perfect Funnel Landscape". Phys. Rev. E. 59 (1): 938–941. arXiv:physics/9810035. Bibcode:1999PhRvE..59..938H. doi:10.1103/PhysRevE.59.938. S2CID 119096368.
• W. Wenzel & K. Hamacher (1999). "A Stochastic tunneling approach for global minimization". Phys. Rev. Lett. 82 (15): 3003–3007. arXiv:physics/9903008. Bibcode:1999PhRvL..82.3003W. doi:10.1103/PhysRevLett.82.3003. S2CID 5113626.
• Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller and Edward Teller (June 1953). "Equation of State Calculations by Fast Computing Machines" (PDF). The Journal of Chemical Physics. 21 (6): 1087–1092. Bibcode:1953JChPh..21.1087M. doi:10.1063/1.1699114. OSTI 4390578. S2CID 1046577.{{cite journal}}: CS1 maint: multiple names: authors list (link)
• Mingjie Lin (December 2010). "Improving FPGA Placement with Dynamically Adaptive Stochastic Tunneling". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 29 (12): 1858–1869. doi:10.1109/tcad.2010.2061670. S2CID 8706692.