確率的トンネル

数値解析において、確率的トンネリング(STUN) は、モンテ カルロ法に基づくグローバル最適化のアプローチです。モンテ カルロ法は、目的関数をサンプリングして最小化するもので、関数が非線形に変換され、関数の最小値を含む領域間でのトンネリングが容易になります。トンネリングが容易になると、サンプル空間の探索が高速化され、適切なソリューションへの収束が速くなります。

モンテカルロ法に基づく最適化手法では、現在の解ベクトルから関数値の差が である別の解ベクトルにランダムに「ホッピング」することで目的関数をサンプリングします。このような試行ジャンプの受け入れ確率は、ほとんどの場合、 適切なパラメータ で(メトロポリス基準) になるように選択されます。 ${\displaystyle \デルタE}$${\displaystyle \min \left(1;\exp \left(-\beta \cdot \Delta E\right)\right)}$${\displaystyle \beta}$

STUN の基本的な考え方は、たとえばスピン グラスで発生する異常なエネルギー関数の遅いダイナミクスを、そのような障壁をトンネルすることによって回避することです。

この目標は、この遅いダイナミクスを欠く変換された関数のモンテ カルロ サンプリングによって達成されます。「標準形式」では、変換は、これまでに見つかった関数の最小値であるところを読み取ります 。この変換は、最小値の 軌跡を保存します。${\displaystyle f_{STUN}:=1-\exp \left(-\gamma \cdot \left(E(x)-E_{o}\right)\right)}$${\displaystyle E_{o}}$

${\displaystyle f_{STUN}}$を元のアルゴリズムの の代わりに使用して、新しい受理確率を与える。${\displaystyle E}$${\displaystyle \min \left(1;\exp \left(-\beta \cdot \Delta f_{STUN}\right)\right)}$

このような変換の効果はグラフに表示されます。

常にトンネリングを行うバリエーションとして、局所的最小値に陥った場合にのみトンネリングを行う方法があります。その後、最小値から抜け出して、よりグローバルに最適なソリューションを追求するように調整されます。局所的最小値に陥ったかどうかを判断するには、 トレンド除去変動分析が推奨されます。${\displaystyle \gamma}$

• シミュレーテッドアニーリング
• 平行焼戻し
• 遺伝的アルゴリズム
• 差異的進化

• K. Hamacher (2006). 「複雑なポテンシャルエネルギーランドスケープの確率的トンネリンググローバル最適化における適応」。Europhys . Lett. 74 (6): 944–950. Bibcode :2006EL.....74..944H. doi :10.1209/epl/i2006-10058-0. S2CID  250761754.
• K. Hamacher & W. Wenzel (1999). 「完全なファネルランドスケープにおける確率的最小化アルゴリズムのスケーリング挙動」. 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). 「グローバル最小化のための確率的トンネリングアプローチ」. 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、Edward Teller (1953 年 6 月)。「高速コンピューティング マシンによる状態方程式の計算」(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: 複数の名前: 著者リスト (リンク)
• Mingjie Lin (2010 年 12 月)。 「動的適応型確率的トンネリングによる FPGA 配置の改善」。IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems。29 ( 12): 1858–1869。doi : 10.1109 /tcad.2010.2061670。S2CID  8706692。