アニーリングは最適解の探索を行う汎用アルゴリズムです。前のページ ではシミュレーテッドアニーリングと量子アニーリングがどのようなプロセスで最適解を探索するのかを模式的に紹介しました。ここでは、量子に限らず一般のアニーリングアルゴリズムがどのような原理で「計算」を行うのかについて触れ、アニーリングマシンの「計算モデル」であるイジング模型について説明します。
アニーリングアルゴリズム #
組合せ最適化問題を解くためには、最適となる組合せを何らかの方法で特定しなくてはなりません。組合せの評価は最小にしたいエネルギー関数(目的関数やコスト関数とも呼ばれます)で計算されます。これは変数値の組合せベクトルを入力に持つ、例えば以下のような形で与えられます。
\[ E(\mathbf{X})=\sum_{i} C_{i}(\mathbf{X}) \qquad \text { where } \qquad \mathbf{x}=\left\{x_{0}, x_{1}, \cdots, x_{N}\right\} \]この時、この関数の最適値(最小値または最大値)を与える入力を知りたいというのが、組合せ最適化問題です。入力要素の数とその取りうる値の場合の数が膨大だと、全通りを評価するのに指数関数的な時間がかかるという困難性があります。
そこで、全通り調べ上げるのを諦めて、適当な解の候補を初期状態とし、これを何らかのルールで変化させていくことで、最終的に最適解近傍に到達するように仕向けるのがアニーリングアルゴリズムの概念です。
シミュレーテッドアニーリングの場合には、適当な初期値から始めて組合せを少しずつ変化させていきます。別の解の候補に変化させるかどうかは、変化先と現在を比較して確率的に決定します。アニーリングの初期には広く探索させるのですが、時間とともに解の候補を絞っていき、最終的に解を確定させます。
量子アニーリングの場合には、解の候補全通りの重ね合わせ状態からスタートします。通常のコンピュータアルゴリズムの言葉で説明するのは難しいのですが、徐々に重ね合わせの力 (量子的効果) を弱くしていくことで、最終的に最適解近傍の状態に確定させます。
どちらの場合でも、解の候補の確からしさの指標として上記エネルギー関数の値を用いています。また、確率的要素を含むため乱択アルゴリズムの一種とも言えるように思います。シミュレーテッドアニーリングでは乱数を用いてますし、量子アニーリングの場合には最終的な出力が確率的に解釈されるためです。
局所最適解と大域最適解 #
組合せ最適化問題が何故難しいかというと、通常と逆方向の計算が必要なためです。つまり、エネルギー関数の計算自体は比較的簡単に行えるのに対し、最適化問題はどのような入力値が最適値を与えるのかという逆問題になっています。この難しさをもたらしている要因として局所最適化が必ずしも大域最適化になっていないというのが挙げられます。
例えば2変数 \(A, B \in \{0,1\}\) による下記の式の最小化を行ってみることにします。
\[ E=-(A+B)+2 A B \]この問題を局所化して、 \(-\left(A + B \right)\) と \(2 AB\) に分けてみます。最初に \(-\left(A + B \right)\) を最適化すると、当然 \(A = 1, \quad B = 1\) が良さそうというのがわかります。しかし一方で \(2 AB\) を調べてみると、 \(A = 1, \quad B = 1\) は逆に最悪値となってしまいました。
こういう状況が起こると、最初に最適化した結果は意味を持たないことになります。関係する変数を含む全ての式との間で調停を行い、どの値を取ることが全体的に相応しいかを判断する必要が出てきます。最悪ケースにおいては全ての式とすべての変数が関係するような状況です。こうなるとうまく枝切りをすることが出来ず、全通り確かめなくてはならなくなります。
シミュレーテッドアニーリングに代表される乱択アルゴリズムは、必ずしも局所的な非最適解を捨てないところに特徴があります。通常の計算は入力を決めれば一意に出力が決まりますが、アニーリングでは出力を見て入力が何であったかをエネルギー関数の値を基準に推論します。つまり、出力値を見て決定的に入力を選択するのではなく、あくまで出力の値は最適解の確からしさと解釈します。こうすると複数の式それぞれにおいて自動的に確率的な調停が働き、全体として最もエネルギーの低い状態が最も実現確率が高いという状況を作り出せます。
アニーリングではエネルギー関数の値とその組合せの確からしさ (つまり確率) の関係を時間とともに変化させます。シミュレーテッドアニーリングでも量子アニーリングでも、初期状態はエネルギーの値はほとんど考慮せずに、どの組合せも等確率とします。そこから、エネルギー値が低いほどその状態が選択されるように変化させ、最終的に状態を確定させます。
アニーリングアルゴリズムの長所は、問題の詳細な性質に依らず適用することが出来る、「汎用アルゴリズム」という点が挙げられます。ベストな解法は問題に適した戦略のアルゴリズムを用いること (ノーフリーランチ定理) ですが、十分に戦略を練る必要なく適用できるということや、また問題の縮小化を行った後の最後の段階でアニーリングアルゴリズムを適用させるなどの使い方もできると思われます。
アニーリングマシンと計算モデル #
アニーリングマシンはハードウェアの実装としてアニーリングを高速に実行し近似最適解を出力します。アルゴリズムの長所は上で述べたようにその汎用性にあります。もちろん特定の問題に適した形のアニーリングマシンを作成することも出来ると思われますが、一般的なアニーリングマシンでは汎用的に問題を受け付けられるような計算モデルを用いています。
この汎用計算モデルがイジング模型と呼ばれるモデルです。もともとは統計物理学において磁石を説明するために導入された模型でしたが、その汎用性はニューラルネットワーク、ボルツマンマシン、そしてアニーリングマシンなど情報科学への応用へ広がっています。
イジング模型 #
アニーリングマシンは通常内部で動作する計算モデルであるイジング模型のパラメータを入力して持ちます。そのためマシンのユーザは解きたい問題をイジング模型に変換する必要が出てきます。その足がかりとして、まずはイジング模型について説明します。
イジング模型は下記のエネルギー関数で表される模型です。
\[H=\sum_{i \neq j} J_{i j} \sigma_{i} \sigma_{j}+\sum_{i} h_{i} \sigma_{i} \qquad(\sigma=\pm 1)\]ここで \(\sigma_{i}\) は入力変数を表し、 \(\sigma \in\{-1,+1\}\) です。 \(J_{ij}\) は(二体の)相互作用パラメータ、 \(h_i\) は (一体の) パラメータとして磁場と呼ばれます。 (符号は分野やマシンによって定義が異なるので注意してください。統計物理学では通常マイナスがつきます。)
アニーリングマシンへの入力は \(J_{ij}, \quad h_i\) を与えることそれだけです。これらのパラメータを与えるとマシンがアニーリングを実行し、エネルギーが最小となる組合せ \(\mathbf{\sigma}\) の近似解を出力します。
余談ですが、最近は \(\sigma \in \left\{-1, +1\right\}\) の代わりにビットと相性の良い \(q \in \left\{0,1\right\}\) に変数変換したQUBO (Quadratic unconstrained binary optimization)と呼ばれる模型も扱われます。両者は単に変数変換 \(\sigma = 2 q - 1\) または \(q = \left(\sigma + 1 \right)/ 2\) しただけで等価です。そのため扱いやすい方を選べば良いです。
相互作用パラメータの性質 #
なぜアニーリングマシンの入力にイジング変数を用いているのかというと、組合せ最適化問題を汎用的に表現する上でも、ハードウェア的な実装 (特に量子アニーリングマシン) の数理モデルとなっているという点においても、非常に相性が良いからです。これはどのような計算も最終的にはビットの論理式に帰着するのと似ています。この意味ではイジング模型はアニーリングマシンの最も基礎的な表現ですが、解きたい組合せ最適化問題をイジング模型に帰着させるところはユーザが行う必要が有ることを意味します。
まずは一体の項 (磁場) のパラメータについて見てみます。最も単純化して \[H = h \sigma\] という式で考えると、次のようにエネルギーが評価されます。
これは
\(h < 0\)
の時には
\(\sigma = +1\)
でエネルギーが下がり、
\(h > 0\)
の時には
\(\sigma = -1\)
でエネルギーが下がることを意味しています。無理やりこじつけると、NOT回路またはバッファ回路のような振る舞いと解釈できるかもしれません。図では変数の値を
\(+1,-1\)
をそれぞれ上向き、下向きと表現しました。
次に二体の項を見てみます。同様に単純化して
\[H = J \sigma_A \sigma_B\]
という式を評価してみます。
こちらも、相互作用
\(J\)
の符号に応じて
\(J < 0\)
なら同じ値を取るときにエネルギーが下がり、
\(J > 0\)
なら別々の値を取るときにエネルギーが下がるという結果になりました。無理やりですが、XOR または XNOR ゲート的な振る舞いとみなせるかもしれません。
局所的にはこれら二種類のパタメータが変数(間)に与えられていますが、組合せ最適化問題としてみた場合には、個々の局所エネルギーを足し合わせたときに、全体としてエネルギーが最小となる変数の組合せを求める問題になります。
グラフ上のイジング模型 #
二体の相互作用に着目した時に、 \(J \ne 0\) の変数の間を「繋がっている」、 \(J = 0\) の変数間を「繋がっていない」、と解釈することでグラフを考えることが出来ます。例えば次のようなグラフのイジング模型の組合せ最適化をしてみます。
強磁性イジング模型 #
最初の問題は三角形の頂点に並んだ次のエネルギー式で表されるイジング模型です。
全ての相互作用が \(J < 0\) なので、先程の表を参照すると同じ方向のときにエネルギーが下がることになります (このような性質を「強磁性的」と呼びます)。そのため、もし \(\sigma_1 = 1\) と仮定すると、 \(\sigma_2 = 1\) のときに右辺の第一項はエネルギーが下がり、そして連鎖的に \(\sigma_3 = 1\) とすると第二項と第三項も負になります。よって最適解の組合わせの一つは、
\[ \sigma_1 = \sigma_2 = \sigma_3 = 1 \] と求まります。
反強磁性イジング模型 #
次の問題は
\(J\)
の符号を変えて、
\(J > 0\)
とします。
全ての相互作用が \(J > 0\) なので、先程の表を参照すると別々の方向のときにエネルギーが下がることになります (このような性質を「反強磁性的」と呼びます)。先程と同様に、まず \(\sigma_1 = 1\) と仮定すると、 \(\sigma_2 = -1\) の時に右辺第一項が負になりエネルギーが下がります。同様に \(\sigma_3 = 1\) とすると第二項も負になります。しかし、第三項は \(\sigma_3 \sigma_1 = 1\) なのでエネルギーが上がってしまいました。最初の \(\sigma_1\) の仮定を逆にしてみたり、 \(\sigma_2\) や \(\sigma_3\) から初めても同様の結果になります。つまり、どこかの相互作用のエネルギーが上がってしまう結果になってしまいました。
このようにどこかの相互作用のエネルギーが上がってしまっても、下記の組合わせ
\[ \sigma_1 = 1,\quad\sigma_2 = -1,\quad\sigma_3 = 1 \]は全体としては最もエネルギーの低くなる最適解の一つになっています。
この例はどの相互作用も同じ値なので、どの変数ペアにエネルギーの上昇を押しつけても全エネルギーは同じ値になりました。しかし、下記の例ではどうでしょうか？
\[ H_\mathbf{AF'} = + \sigma_1 \sigma_2 + \sigma_2 \sigma_3 + \frac{1}{2} \sigma_3 \sigma_1 \]エネルギー最小の組合わせを見つけるには、どの相互作用に我慢を押しつけると全体として得になるかを調べる必要があります。上の例では第三項に押しつけると良さそうです。
イジング模型の一般化 #
相互作用 \(J_{ij}\) や磁場 \(h_i\) が場所によって正負の様々な値をとるイジング模型の最適解を調べるのはとても難しいことが知られています。最も一般的な表現は、すべての変数が結合して相互作用や磁場のパラメータが任意の値をとれる、完全グラフ上のイジング模型です。
変数が \(N\) 個ある場合、相互作用の数は \(n\left( n - 1\right) / 2\) になります。制約無く与えられた相互作用や磁場のパラメータに対し、イジング模型の変数を最適化する問題はNP困難な問題です。そのため効率的 ( \(N\) の多項式オーダー) なアルゴリズムは今のところ知られていません。
一方で、基底状態のエネルギーの値がある値より小さいかを判定する決定問題はNP完全問題として知られています。クラス NP に属する問題は多項式時間でNP完全問題に帰着されるため、原理的には多くの難しい組合せの問題 (とそれに対応する最適化問題) は一般化されたイジング模型に変換できるはずです。
これはアニーリングマシンがイジング模型を計算モデルとして使用している理由の一つになっています。別の言い方をすると、アニーリングマシンのユーザは、マシンを使用するためには何とかして最適化したい問題をイジング模型に変換する必要があるということです。
原理的には可能であっても、問題やマシンの制約に応じて適切な変換を考える必要があります。問題自身の変換が必要なだけでなく、実はマシンによってはイジング模型のグラフに対する制約もあります。このような作業が、アニーリングマシンに対する「プログラミング」に相当します。
次頁以降では、より具体的にマシンを意識して、アニーリングマシンに対するプログラミングがどのようなステップで行われるかについて説明したいと思います。
まとめ #
- アニーリングアルゴリズムでは確率的に最適解の近傍を探索する
- アニーリングマシンはハードウェア実装としてアニーリングアルゴリズムを実行する
- マシンへの入力はイジング模型 (または QUBO) に対するパラメータとなる
- マシンのユーザは解きたい問題をイジング模型に変換する必要がある