シミュレーテッドアニーリング

さて，もう一つの重要なパラメータとして (2) 式に現れた温度 $T$ がある． すでに述べたように $T$ が 0 に近づくほど，$f(x)$ の最小値 が強調される凹凸の激しい分布になる． しかしながら，MCMC のように $\cal X$ を渡り歩くような方法にとっては，一般に最適値まで到達するのが 難しくなる． 逆に，$T$ を大きくすれば，そのような問題点は少なくなるが， $f(x)$ とは無関係にランダムウォークするのと変わらなくなってしまう．

そこで，少しずつ温度を下げていきながら上のような問題を解決しようという のがシミュレーテッドアニーリング (SA=Simulated Annealing)である． このとき問題となるのは， どれぐらい速く温度を下げても大丈夫かということである．温度を変えることに よって分布が変わってしまうので，平衡状態への収束は阻害されて しまう． 従って，平衡状態に十分収束させながら少しずつ温度を 下げる必要がある． これについては多くの理論的な成果がある[5,6]．

収束定理

(Hajèk[6]) 有限状態のシミュレーテッアニーリングによる系列 $\{x_t\}$ が最適解に収束するための必要十分条件は，$t$ 回目の繰返し で用いる温度を $T_t$ として，

$$\sum_{t=1}^\infty \exp(-D/T_t)=\infty$$ (6)

となることである． ただし $D$ は問題によって定まる定数．

具体的には $T_t = D / \log t$ はこれを満たすが⁴，実質的には遅すぎるので， 実際の運用では $T_t = \alpha^t T_0$ ( $0<\alpha<1$) のように指数的に 減衰させることが多い． また，ここでは有限状態と書いたが無限状態への 一般化なども研究されている．