アニーリングは最適解の探索を行う汎用アルゴリズムです。前のページ ではシミュレーテッドアニーリングと量子アニーリングがどのようなプロセスで最適解を探索するのかを模式的に紹介しました。ここでは、量子に限らず一般のアニーリングアルゴリズムがどのような原理で「計算」を行うのかについて触れ、アニーリングマシンの「計算モデル」であるイジング模型について説明します。
アニーリングアルゴリズム #
組合せ最適化問題を解くためには、最適となる組合せを何らかの方法で特定しなくてはなりません。組合せの評価は最小にしたいエネルギー関数(目的関数やコスト関数とも呼ばれます)で計算されます。これは変数値の組合せベクトルを入力に持つ、例えば以下のような形で与えられます。
\[ 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) に対するパラメータとなる
- マシンのユーザは解きたい問題をイジング模型に変換する必要がある