（邦訳：大規模組合せ最適化問題のためのアニーリングプロセッサに関する研究）
| 山本 佳生 （正会員） （株）日立製作所 研究員 |
キーワード
| 組合せ最適化 | イジングモデル | アニーリング |
［背景］大規模データに基づく組合せ最適化問題を解く需要の高まり
［問題］問題規模に対して解の数が指数関数（爆発）的に増加
［貢献］上記の問題を効率良く解くアルゴリズムとハードウェアの提案
スマート社会の実現には，交通網，電力網，人的資源の割り当てや経路といった人と物の最適化が必要不可欠である． これらの問題の多くは，組合せ最適化問題と呼ばれ，現代社会においても非常に重要な問題として位置付けられている． しかし，組合せ最適化問題の多くはNP困難であり，従来のノイマン型コンピュータで効率良く解くのは困難であることが知られている．また，近年コンピュータチップを製造するプロセスの微細化が物理的な限界を迎えようとしている． したがって，特に全探索による求解は，コンピュータの計算速度による速度改善は見込めない．そのような背景から，組合せ最適化問題を専用回路で高速かつ低消費電力で解くアプローチが注目を浴びている．
イジングモデルは，上向き下向きの状態を持つスピンとそのスピン間に生じるスピン間相互作用と各スピンに作用する外部磁場によって表現される統計物理における強磁性体のモデルである．これらのパラメータを用いて，制御対象やコストを表現することで，イジングモデルは組合せ最適化問題を表現することが可能である．
アニーリングプロセッサは，組合せ最適化問題の最適解とイジングモデルを用いて表現された最適化問題の基底状態が一致する性質を利用した汎用組合せ最適化ソルバーであり、一般的に焼きなまし（アニーリング ）と呼ばれる自然現象に習った最適化手法であるシミュレーテッドアニーリングに基づいて， 温度パラメータをゆっくり下げながら，スピンの状態を更新することで，イジングモデルの基底状態を探索し，組合せ最適解の最適解を得る．
アニーリングプロセッサは，再現するイジングモデルの形状によって最近傍型と全結合型の2つに分類される． 最近傍型は，スピン間結合が近接スピン間のみに限定され，全結合型は，任意のスピン間に結合が存在する．最近傍型は，近接スピンを減らすことでシミュレーテッドアニーリングが要請するデータの依存関係を減らすことで高い並列処理を実現する．また，データ転送が隣接スピンに限定されるため，スケーラビリティに優れるという特徴を持つ．しかし，スピン間相互作用が疎であるため，対応可能な組合せ最適化問題のクラスが限定される，あるいは問題をハードウェアのイジングモデルに合うように変形処理を要するという問題点がある．全結合型は，スピン数が許す限りあらゆるクラスの問題を解くことが可能であるが，任意のスピン間を接続する必要があるため，スケーラビリティが低く，すべてのスピンに対して依存関係が存在するため，一度に更新できるスピン数が全スピン数に依らず常に1つのみに限定される．そのため，基底状態への収束時間がかかる．
本研究では，このアニーリングプロセッサに対して，（1）疎結合型をベースにとした空間展開型時分割処理機構アーキテクチャによるスピン数増大手法（2）疎結合型イジングネットワークを利用したより複雑なイジングネットワークへの適用手法と 並列更新可能なアニーリング手法における疎結合型イジングネットワークを完全結合適用するためのアルゴリズム，（3）並列更新なアニーリングにおける全結合型のアニーリング プロセッサのアーキテクチャに関する研究を実施した．
［貢献］上記の問題を効率良く解くアルゴリズムとハードウェアの提案
スマート社会の実現には，交通網，電力網，人的資源の割り当てや経路といった人と物の最適化が必要不可欠である． これらの問題の多くは，組合せ最適化問題と呼ばれ，現代社会においても非常に重要な問題として位置付けられている． しかし，組合せ最適化問題の多くはNP困難であり，従来のノイマン型コンピュータで効率良く解くのは困難であることが知られている．また，近年コンピュータチップを製造するプロセスの微細化が物理的な限界を迎えようとしている． したがって，特に全探索による求解は，コンピュータの計算速度による速度改善は見込めない．そのような背景から，組合せ最適化問題を専用回路で高速かつ低消費電力で解くアプローチが注目を浴びている．
イジングモデルは，上向き下向きの状態を持つスピンとそのスピン間に生じるスピン間相互作用と各スピンに作用する外部磁場によって表現される統計物理における強磁性体のモデルである．これらのパラメータを用いて，制御対象やコストを表現することで，イジングモデルは組合せ最適化問題を表現することが可能である．
アニーリングプロセッサは，組合せ最適化問題の最適解とイジングモデルを用いて表現された最適化問題の基底状態が一致する性質を利用した汎用組合せ最適化ソルバーであり、一般的に焼きなまし（アニーリング ）と呼ばれる自然現象に習った最適化手法であるシミュレーテッドアニーリングに基づいて， 温度パラメータをゆっくり下げながら，スピンの状態を更新することで，イジングモデルの基底状態を探索し，組合せ最適解の最適解を得る．
アニーリングプロセッサは，再現するイジングモデルの形状によって最近傍型と全結合型の2つに分類される． 最近傍型は，スピン間結合が近接スピン間のみに限定され，全結合型は，任意のスピン間に結合が存在する．最近傍型は，近接スピンを減らすことでシミュレーテッドアニーリングが要請するデータの依存関係を減らすことで高い並列処理を実現する．また，データ転送が隣接スピンに限定されるため，スケーラビリティに優れるという特徴を持つ．しかし，スピン間相互作用が疎であるため，対応可能な組合せ最適化問題のクラスが限定される，あるいは問題をハードウェアのイジングモデルに合うように変形処理を要するという問題点がある．全結合型は，スピン数が許す限りあらゆるクラスの問題を解くことが可能であるが，任意のスピン間を接続する必要があるため，スケーラビリティが低く，すべてのスピンに対して依存関係が存在するため，一度に更新できるスピン数が全スピン数に依らず常に1つのみに限定される．そのため，基底状態への収束時間がかかる．
本研究では，このアニーリングプロセッサに対して，（1）疎結合型をベースにとした空間展開型時分割処理機構アーキテクチャによるスピン数増大手法（2）疎結合型イジングネットワークを利用したより複雑なイジングネットワークへの適用手法と 並列更新可能なアニーリング手法における疎結合型イジングネットワークを完全結合適用するためのアルゴリズム，（3）並列更新なアニーリングにおける全結合型のアニーリング プロセッサのアーキテクチャに関する研究を実施した．
（2020年6月16日受付）