Experience the CMOS Annealing Machine

イジングエディタ

このチュートリアルは、「イジングエディタ」でアニーリングマシンが行っている処理を解説したものです。

イジングエディタの使い方

イジングエディタでは、イジングモデルを直接入力してアニーリング処理を実行することができます。

画面右側の格子状の図はこのサイトのCMOSアニーリングマシンで表現できるイジングモデルのグラフ構造を表しています。これはKing’s Graphと呼ばれるグラフ構造で、端にあるスピンを除いて、各スピンは上下左右と斜めの合計8方向のスピンと相互作用することができます。

基礎知識の「イジングモデルとは」に以下のようなイジングモデルのハミルトニアンが記載されていますが、この式で $(i,j)∈E$ と書かれている部分の $E$ がKing’s graphを構成する辺の集合となります。

$$ E (\lbrace s _i \rbrace) = \sum _ { i \in V } h _ { i } s _ { i } + \sum _ { ( i , j ) \in E } J _ { i j } s _ { i } s _ { j } $$

イジングエディタでイジングモデルを入力するには、まず「値を設定の欄」で、係数として設定したい値を選択します。続いて、グラフ上の辺をクリックすることで、クリックした辺に選択中の相互作用係数 $J_{ij}$ を設定する事ができます。また、頂点をクリックすると、その頂点に対応するスピンの外部磁場係数 $h_i$ を設定する事ができます。ここで、相互作用係数値を0に設定するとスピン間の相互作用が存在しないことになります。これは、グラフ上でスピン間がつながっていないことと同じ意味です。

グラフ上の辺や頂点にマウスカーソルを合わせることで、相互作用係数や外部磁場係数が表示されます。外部磁場がない場合には表示されません。

実行が完了すると、アニーリングの結果得られたスピンの値が上下矢印の形で表示されます。上向き矢印はスピンの値が+1に、下向き矢印はスピンの値が−1に対応します。アニーリング結果は、「パラメーターを設定」欄のアニーリング回数で指定した回数分だけ別々に得られます。グラフ上のスライダーを動かすとそれぞれのアニーリング結果を確認する事が出来ます。

「パラメーターを設定」欄の詳細設定をクリックするとアニーリングスケジューラと呼ばれるパラメータを設定する事が出来ます。これについては以下で詳しく説明します。

イジングエディタに向けた温度スケジュール関連の説明

CMOSアニーリングマシンはイジングモデルの基底状態探索という演算に特化した計算機と言うことができます。
このため、アニーリングマシンを使用する際には、基底状態探索を行いたいイジングモデルを記述するための相互作用係数や外部磁場係数といったパラメータを入力する必要があります。
しかし、実際に計算を行う際には計算の所要時間や解の精度をコントロールするためのパラメータも同時に入力する必要があります。
このチュートリアルでは、このようなパラメータについて説明します。

イジングモデルの基底状態探索を実行するためには、様々なアルゴリズムを用いることができますが、CMOSアニーリングマシンでは名前の示すとおりアニーリング(特にシミュレーテッドアニーリング)という考え方に基づいて計算を行います。
アニーリングでは、スピンの初期値を適当に定めた初期状態から計算をスタートして、各時間ステップにおいてスピンの値を更新する動作を繰り返していきます。
基底状態はイジングモデル全体のエネルギーが最も低くなるスピンの状態なので、スピンの更新を行う際は基本的に更新したいスピンとその周囲のスピンの値から、エネルギーが低くなるように次のスピンの値を計算します。
しかし、この動作だけではイジングモデル全体でエネルギーが下がる方向しか向かわないため、局所解と呼ばれるローカルに存在するエネルギーの谷にトラップされ、それ以上エネルギーが低い状態を探索することが困難となります。そこで、局所解を脱出してよりエネルギーの低いスピン値の組合せを探索するため、スピンの値を更新する際にエネルギーの上昇をある確率で許容することにします。
ただし、エネルギーの上昇を許容する確率が高すぎるといつまでたっても全体のエネルギーが下がらず、逆にエネルギーの上昇を許容する確率が低すぎると局所解を脱出できなくなってしまいます。
このため、アニーリングの際はこの確率を適切に定めることが重要であり、これが冒頭で述べたCMOSアニーリングマシンを使用する際のパラメータになります。

シミュレーテッドアニーリングでは、上述のようなエネルギーの上昇を許容する確率を制御するため、一般に温度と呼ばれるパラメータを用います。
温度が高いほどエネルギーの上昇を積極的に受け入れ、温度が下がるほど受け入れにくくなり、温度0ではエネルギーの上昇を決して受け入れない状態となります。
ここでは計算過程での温度の推移の仕方を温度スケジュールと呼ぶことにします。通常、温度スケジュールは計算開始時には温度を高くし、徐々に下げていくように決めます。これは、計算開始時は解空間の広い範囲を探索するために温度を高くし、計算が進むにつれてよりエネルギーの低い状態に向かうことで局所解を回避しより良い解を得やすいためです。
具体的な温度スケジュールの決め方は様々なものが考えられますが、CMOSアニーリングマシンでは幾何冷却と呼ばれる冷却スケジュールを用います。これは、ある初期温度からスタートし、所定のステップ数だけスピンの値を更新したら現在の温度の値に1より小さい係数を乗算して温度を下げていくシンプルな方法で、広く使われているものです。

幾何冷却に基づく冷却スケジュールを定めるために、本サイトのCMOSアニーリングマシンでは、以下の4つのパラメータを用います。

  • 初期温度:アニーリング開始時の温度
  • 最終温度:アニーリング終了時の温度
  • ステップ長:温度の値を更新するまでのスピンの更新回数
  • ステップ数:初期温度から最終温度に至るまでの温度の更新回数

なお、前述の冷却係数は4つのパラメータ値をもとに算出されます。

一般的に、ステップ数を増やしてアニーリング時間を長くとる方がよい解が得られやすいですが、その分所要時間が伸びることにもなります。
また、対象のイジングモデルの係数値によっても適切なアニーリングスケジュールは異なるため、ある程度試行錯誤してみることも有効です。

ACWスキルロードマップ

未読

後で学びなおすときは未読にスライドしておくことができます。

シェアする/フィードバックする