日立、GPUで組み合わせ最適化を大規模・高速に計算する「モメンタム・アニーリング」を発表 10万変数・全結合問題を1秒未満で計算（1/2 ページ）

[井上輝一，ITmedia]

　日立製作所は8月30日、組み合わせ最適化問題を高速に計算できるアルゴリズム「モメンタム・アニーリング」を発表した。同アルゴリズムをNVIDIAのGPU4台で実装したところ、「10万変数・全結合」という大規模な問題の近似解を1秒未満で計算できたという。

組み合わせ最適化問題を高速に計算できるアルゴリズム「モメンタム・アニーリング」

　モメンタム・アニーリング（MA）は、組み合わせ最適化問題を表す「イジングモデル」を従来のコンピュータで近似的に解くアルゴリズムの一つ。組み合わせ最適化計算は、交通渋滞や金融ポートフォリオ最適化など、社会問題やビジネス課題への応用が見込まれている。

　イジングモデルを解くアプローチには、量子効果を用いた「量子アニーリング」や、量子アニーリングを従来のコンピュータ上でまねる「シミュレーテッド・アニーリング」（SA）などがある。東芝が4月に発表した、従来のコンピュータ上で「量子コンピュータよりも高速・大規模に組み合わせ最適化問題を解ける」とする「シミュレーテッド分岐アルゴリズム」も、イジングモデルを解くためのものだ。

日立製作所の奥山拓哉さん

　MAはSAを改変し、全結合の並列計算を可能にしたアルゴリズム。MAの開発者の一人である奥山拓哉さんは、「並列処理が可能になったことで、問題規模が大きくなっても計算量を抑えられる」と話す。

「全結合か、並列計算か」──従来の問題点を克服

　日立が従来SAで行っていたアプローチには、2つの問題点があった。「全結合ではない」ということと、「SAは原理的に並列処理が困難」ということだ。

　イジングモデルは、＋1もしくは−1を示すスピン（変数）同士を、「相互作用」を表す変数で掛け合わせる。その値を全て足し合わせた和が小さくなるほど、組み合わせの最適解に近くなる。イジングモデルを解く各アルゴリズムは、総和が小さくなるようなスピンの値をうまく定めるよう計算していく。

イジングモデルによる組み合わせ最適化問題の表現　イジングモデルを高速に解くさまざまなアルゴリズムが開発されている

　「SAでは原理的に、つながりを持つスピン同士を同時に更新できない」と奥山さんは話す。つまり、全てのスピン同士に相互作用がある「全結合問題」では、SAで並列化による高速計算は不可能ということだ。

全結合のSAでは、原理的に並列計算ができない

　逆に、相互作用がないスピン同士は同時に更新できる。このため、日立は隣り合うスピン同士のみに相互作用がある「隣接結合」のイジングモデルを解ける、アニーリング専用のCMOS回路を作り、大規模な変数の問題にアプローチしてきた。

　しかし、隣接結合の回路で全結合問題を解くには、「埋め込み」という変数のマッピング操作が必要になる。奥山さんは、「全結合問題を隣接結合の回路に埋め込むと、スピンが2乗のオーダーで増えてしまう」と問題点を明かす。

全結合の問題を格子状の隣接結合モデルに変換すると、スピンが2乗で増えてしまう

　日立のCMOSアニーリングは10万変数・隣接結合の問題を扱えるが、全結合問題を扱おうとすると約300変数まで減ってしまうことになる。

　そこで、奥山さんらは全結合のイジングモデルと同等ながら、スピン同士を切り離せるモデルを考案した。

「2部グラフ」で全結合を表現　2ステップで全ての変数を更新

　奥山さんらは、全結合のイジングモデルを「2部グラフ」と呼ばれるグラフに変換した。例えば7変数の全結合モデルを2部グラフに変換すると、左右に7つの変数が並んだ計14変数のグラフになる。