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

MCMCを応用して確率的に最適化を行なう方法であるシミュレーテッドアニーリングを解説する。

確率分布と「温度」 MCMCと温度焼鈍法メトロポリス法による実装アニーリングスケジュール

ここで、 $P(\bm x)$ に従う乱数列 $\{\bm x^{(i)}\}_{i=1}^n$ をMCMCで生成する状況を考えよう。MCMCで生成される乱数列はマルコフ連鎖の実現値であった。そのため、 $\bm x^{(t+1)}$ がどのような値であるかは $\bm x^{(t)}$ にのみ依存し、その遷移のしやすさは、 $P(\bm x^{(t+1)})$ が $P(\bm x^{(t)})$ に比べてどれほど大きいかに依存する。

より端的に表すと、提案された $\bm y$ について

確率分布の値 $P(\bm y)$ が $P(\bm x^{(t)})$ よりも大きいのであれば、確実に受理 $\bm x^{(t+1)} \gets \bm y$ される
そうでなければ、 $P(\bm y)$ が $P(\bm x^{(t)})$ よりも小さいほど受理されにくくなる

ということである。

ここに「逆温度」 $\beta$ と「エネルギー」 $E(\bm x)$ を導入してみよう。先ほど確認したように、逆温度 $\beta$ が大きいほど、 $E(\bm x)$ の変化に関して $P(\bm x)$ の値の変化は敏感になる。すなわち、

逆温度 $\beta$ が大きいほど、提案 $\bm y$ におけるエネルギー $E(\bm y)$ が大きくても、それが受理されやすい
逆に、逆温度が小さいほど、提案 $\bm y$ におけるエネルギー $E(\bm y)$ が大きい場合に、それが受理されにくい

焼鈍法

ここでさらに、次のようなことを行なう。

まず乱数生成の初期では、逆温度 $\beta$ をできるだけ小さくしておく。そして漸次逆温度を大きくしていき、終期では十分に逆温度が大きいような状況を作る。

すると、初期では多少エネルギーが大きくなっても $\bm y$ が受理されて次々と遷移していくが、徐々にエネルギーが低い状態にとどまるようになる。終期では、常に1つ次の状態のほうがエネルギーが低くなるような振る舞いを見せるようになり、勾配法に似た挙動を示す。

こうすることにより、非常に広大な範囲 $\mathcal X$ から局所解 $x^\ast \in \mathcal X$ を探索するようなアルゴリズムができあがる。このようなアルゴリズムを、シミュレーテッドアニーリング (simulated annealing, SA; 焼きなまし法) という。この名は、金属材料の加工工程で内部に発生した残留応力や加工硬化などを取り除くため、金属を一旦高温にしてから再び冷却することによって、金属にエネルギーの壁を乗り越えさせてより低エネルギーな状態に導くという処理 (焼きなまし) に由来する。

SAの基本的なアルゴリズムは以下の通りである。

Algorithm: Simulated Annealing.
$\begin{darray}{rl} 1. & X \gets \{\} \\ 2. & \text{for } t \in \{1, 2, \dots, n\} : \\ 3. & \qquad \beta \gets \operatorname{temperature}(t) \\ 4. & \qquad \bm x \gets \operatorname{MCMC}(\bm x, \beta) \\ 5. & \qquad X \gets X \cap \{\bm x\} \\ 6. & \text{return } \min_{\bm x} X \\ \end{darray}$

メトロポリス法による実装

温度を伴うMCMCとして、例えばメトロポリス法を使用してみよう。メトロポリス法は以下のようなアルゴリズムであった。

目標となる確率分布が $P(\bm x) = \dfrac{1}{Z} \exp(-\beta E(\bm x))$ で表されているなら、次のように書ける。

Algorithm: Metropolis algorithm.
$\begin{darray}{rl} 1. & X \gets \{\} \\ 2. & \text{for } t \in \{1, 2, \dots, n\} : \\ 3. & \qquad \text{for } i \in \{1, 2, \dots, N\} : \\ 4. & \qquad \qquad \Delta x_i \sim {\cal U}(\Delta x_i | -c_i, c_i) \\ 5. & \qquad \Delta E \gets E(\bm x + \Delta \bm x) - E(\bm x) \\ 6. & \qquad r \sim {\cal U}(r | 0, 1) \\ 7. & \qquad \text{if } \exp(-\beta \Delta E) \gt r : \\ 8. & \qquad \qquad \bm x \gets \bm x + \Delta \bm x \\ 9. & \qquad X \gets X \cup \{\bm x\} \\ 10. & \operatorname{return} X \end{darray}$

これを用いてSAを実装するには、単に途中に $\mathop\mathrm{temperature}(t)$ を挟めばよい。

Algorithm: Simulated Annealing.
$\begin{darray}{rl} 1. & X \gets \{\} \\ 2. & \text{for } t \in \{1, 2, \dots, n\} : \\ 3. & \qquad \beta \gets \operatorname{temperature}(t) \\ 4. & \qquad \text{for } i \in \{1, 2, \dots, N\} : \\ 5. & \qquad \qquad \Delta x_i \sim {\cal U}(\Delta x_i | -c_i, c_i) \\ 6. & \qquad \Delta E \gets E(\bm x + \Delta \bm x) - E(\bm x) \\ 7. & \qquad r \sim {\cal U}(r | 0, 1) \\ 8. & \qquad \text{if } \exp(-\beta \Delta E) \gt r : \\ 9. & \qquad \qquad \bm x \gets \bm x + \Delta \bm x \\ 10. & \qquad X \gets X \cup \{\bm x\} \\ 11. & \operatorname{return} X \end{darray}$

アニーリングスケジュール

関数 $\mathop\mathrm{temperature}$ によって規定される逆温度の変化をアニーリングスケジュールという。SAをきちんと動かすには、アニーリングスケジュールの設計が重要である。

もっとも基本的なのは、温度 $T = \dfrac{1}{\beta}$ が $\dfrac{1}{t}$ に比例するように設計する方法である。逆温度 $\beta$ は温度の逆数であるから、これはすなわち逆温度を線形的に増大させていくものと説明することができる。初期逆温度を $\beta_{\rm init}$ 、終期逆温度を $\beta_{\rm end}$ 、時刻を $t = 1, 2, \dots, n$ とすれば、次のように書ける。

\mathop\mathrm{temperature}(t) = \beta_\mathrm{init} + \frac{t-1}{n-1} (\beta_\mathrm{end} - \beta_\mathrm{init})

きちんと $\mathop\mathrm{temperature}(1) = \beta_\mathrm{init}, \mathop\mathrm{temperature}(n) = \beta_\mathrm{end}$ となることを確認しておこう。

なお実際には各温度において $10 \sim 100$ 回程度MCMCを用いて遷移を繰り返したりする (num_sweeps_per_temperature) などの方法も用いられる。