日本音響学会

音のなんでもコーナー

Q and A (058)

Q:

最近最適化手法の一つとしてSimulated Annealingという方法を耳にしますが,どのような原理に基づいた手法なのでしょうか?

A:

Simulated Annealingは,モンテカルロ法的な最適化手法であり,1983年にKirkpatrickらによって提案されました。アニーリング(焼き鈍し)とは,固体の温度を十分高くして液状にした後,温度をゆっくり下げることにより,その固体の単結晶を得るという物理的なプロセスのことであり,Simulated Annealingは,計算機中でこのアニーリングを行うことで,与えられた問題に対して設定されたコスト関数の大局的最小点を見つける手法です。 それではまず,最適化問題と実際の物理系とを対比させながらSimulated Annealingの原理について説明しましょう。 与えられた最適化問題における変数{χi}と最適化を評価する関数Ε(通常コスト関数と呼びます)を,それぞれある物理系における粒子及び系のエネルギーにたとえます。今,このコスト関数Eがn個の変数により与えられるとすると, E=E(χ1,χ2,?,χn)(1) と書くことができます。画像復元の問題では,{χi}は各ピクセル値になり,このEの値を最小にするような{χi}の組を見つけだすことで最適化問題を解くことができます。実際の物理系においてエネルギーが最低の状態というのは,整然とした結晶構造に対応します。 実際の物理系においては,系の温度がTであるとき,多数の粒子はそれぞれの自由エネルギーが最も低い状態で熱平衡となり,そのとき系が基底状態より⊿Eだけエネルギーの高い状態になる確率は,ボルツマン分布 P(⊿E)=exp(−⊿E/κT)(2) になることが知られています。ここでκはボルツマン定数と呼ばれる定数です。このことは言い換えると,各粒子の状態が熱的に揺らいでいることを意味します。そこで,粒子と同じように,各変数の値に(2)式で与えられる揺らぎを与えます。次に熱平衡状態になった系の温度を下げることで,各粒子の揺らぎを押さえ,系のエネルギーを減少させていきますが,単に温度を低くしていくだけでは十分ではありません。なぜならば,一般に,固体を高温から低温に急激に冷やすと固体中に欠陥が生じてしまったり,しばしばエネルギーの低い結晶格子構造でない,準安定のアモルファスになることが知られているためです。これは,系がエネルギーの局所最小点に落ち込んだことに対応しています。低温で局所最小点に落ち込んでしまうと,熱による揺らぎが小さいため,そこからエネルギーの山を乗り越えられず,結果として大局的最小点までたどり着くことができなくなります。従って,複雑な形をしたコスト関数を用いる最適化問題においては,系の温度を十分注意深く制御し,準熱平衡状態の連続として冷却を行うことが必要になるわけです。系の温度を制御するアニーリングスケジュールは,大局的な最小点へ到達するために極めて重要ですが,その方法についてはここでは省略します。詳しくは専門書をご参照下さい。実際の最適化プロセスでは,はじめに求める解{χi}に,初期推定として適当な値を与えます。そして,各パラメータに対して順番に微小な変化⊿χ(この量はグレインと呼ばれ,その符号はランダムに選ばれます)を加え,与えられたコスト関数の変化量⊿Εを計算します。このとき,⊿Εが負であれば,この微小変化は解を最適解に近づけるものとして受け入れます。一方⊿Εが正の場合には,この微小変化は系のエネルギーを増加させますが,これを局所的な最小点から抜け出すために必要な揺らぎと考えて,ボルツマンの確率に従って受け入れることとします。このような微小変化をすべてのパラメータに対して繰り返し行うことで,計算機内に擬似的な熱平衡状態を作り上げることができます。次に,系の温度を少し下げると,エネルギーを上昇させる微小変化の受け入れ確率が下がるため,系は非平衡状態となり,新たな熱平衡状態へと変化していくことになります。 以上のことを,系のエネルギーが十分小さくなるまで実行することで与えられた問題の最適解を得ることができます。本手法が持つ利点としては,コスト関数の形をかなり自由に設定できるため,拘束条件の導入を容易にすることや,並列処理の可能性を持つこと等が挙げられます。Kirkpatrick等は,組み合わせ論的最適化問題,具体的には,VLSI内の配線問題や巡回セールスマン問題に対して以上の方法を適用し,その有効性を示しました。しかし、アルゴリズム自体は組み合わせ最適化問題に限らず広く一般的に応用できる能力を有しているため、画像処理の分野でも、Smith等による符号化開口像法を用いた画像再構成問題やNiet-Vesperinats等による位相回復問題、更には羽石等による心臓血管像の3次元再構成に対する応用例などが報告されています。

執筆者:大山永昭(東工大)