フジサンケイビジネスアイ賞

大規模最適化問題を高速に解く
CMOS アニーリングマシンの先駆的開発

12（株）
日立製作所研究開発グループ、（株）
日立製作所 IT プロダクツ統括本部
34（株）
日立ソリューションズ、（株）
日立超 LSI システムズ

林 真人 1 山岡 雅直 1 吉村 地尋 1 林 茂樹 2
太田 充男 2 依田 和夫 2 安孫子 健太 3 嘉村 英敏 4

要旨

計算量が膨大になるために、従来のコンピュータでは解けない最適化問題を、高速、高効率で解くために、半導体を活用した CMOS アニーリング法を考案し、CMOS アニーリングマシンを開発した。これをクラウド上で研究者に開放し、先端技術の普及活動を行っている。

1 ．緒

言

配送の最適化や交通渋滞の軽減、都市の省エネといった社会問題を解決しようとすると、大規模な組合せ最適化問題を実時間で解かなければらない。こうした問題では、配送経路や信号機のタイミング等、制御すべき変数の組合せが膨大であり、大規模な問題になると、組合せをすべて列挙することは不可能である。このため、最適解を効率良く探索する方法が必要である。
候補者らは、半導体を用いることで、最適解を求めるためのコンピュータが実現できることや、大量生産が可能であること、また、幅広い温度環境で使用できること等のメリットが得られることに、世界に先駆けて着眼し、これを実装した半導体チップを 2015 年に製作した［1, 2, 3, 4］。さらに、2018 年には、解きたい問題の規模に応じて、必要なだけ複数チップを接続する技術を確立し［5］、大規模な組合せ最適化問題になるほど汎用コンピュータに対して計算速度が向上することを示した。
現在、この技術をもとに構成した CMOS アニーリングマシンを、クラウド環境として研究者等に開放し、CMOS アニーリング法のさらなる可能性を広げる開発に貢献している。
現在、8 つの企業と 6 つの大学を含む 3000 名以上のユーザが利用しており、ユーザと連携して社会課題解決に資するアプリケーションの開発を、国家プロジェクトで推進している。

2 ．従来の最適化問題の解法とその課題組合せ最適化問題は図 1 に示すように、評価指標（縦軸）を最小にするような変数値の組合せ（横軸）を求めるものである。最良の変数値の組合せを求めるには全ての組合せを調べる必要があるが、膨大な数になる。例えば、配送経路の最適化等に用いられる巡回セールスマン問題では、複数の目的地を 1 回ずつ訪問する最短経路を求めるが、わずか 30 か所でも 2.7 ×1032 という大きな組み合わせ数となる。
そこで、すべての組合せを調べずに、評価指標が小さくなりそうな変数値を探索する方法が必要となる。それが、アニーリング法である。アニーリングとは、金属における焼きなましであり、金属を加熱することで、安定な状態に推移するとともに、特有の特性が発現する現象である。この安定状態への変化と最適解探索の類似性から、この計算手法にアニーリン
グという名前が付けられている。これは、適当な変数の組合せを初期値として、変数の値を少しずつ変えながら評価関数を小さくしてゆくアルゴリズムである。図 1 にアニーリングの経過を図示した。現在の変数の値を少し変えて、評価指標が小さくなった場合はその値を採用する（図 1 の実線矢印に対応）。ただし、これだけでは局所解と呼ばれる評価指標のくぼみに捕まってしまい、それ以上良い変数値の組合せを探せない。そこで、評価指標があえて大きくなるような変数値の組合せも確率的に採用する（図 1 の二重線矢印に対応）ことで、より― 94 ―

多くの組合せを探索することができるようになり、最適状態に到達しやすくなる。

図 1 ．アニーリング法の概念図

2.1 シミュレーテッドアニーリング法
1983 年に Kirkpatrick らによってシミュレーテッドアニーリングと呼ばれるアルゴリズムが提案された［6］。
この手法は、配送経路の最適化や電子回路設計における配線長の最適化等、幅広い問題に適用できる点が特長であり、現在も使われている。このアルゴリズムが提案されて以来、長らく汎用コンピュータ（CPU）を用いたシミュレーションで実行されてきた。
効率的なアルゴリズムとはいえ、大規模な問題に対しては計算時間がかかりすぎる課題があった。
2.2 量子アニーリング法
上記の問題を解決する手段の一つとして、専用コンピュータを用いる方式が提案された。
2011 年に登場した、超電導素子を使った量子アニーリングコンピュータがその典型的な例である［7］。量子的な特徴である重ね合わせの状態を活用して、変数値の組合せを同時に探索することで、高速・高精度な答えが得られると期待されている。しかし、超電導素子を利用するために極低温が必要であり、コンピュータの大規模化が容易ではなく、大規模な組合せ最適化問題には適用できないという課題があった。

3 ．CMOS アニーリング法の提案
候補者らは、最適化問題を解く必要性の高い社会課題は、道路網や電力網といった規則的な構造を持つネットワークが関連しているケースが多いと考えた。それらは、図 2（a）に示したように、単純なグラフで表現できる［8］。図 2（a）において、σは最適化問題における変数を、J は同様に、変数間の関係を表すものである。このグラフにおいて、隣接するσの値とその間の J の値の積で局所的な評価指標を算出できる。具体的には、σ1 とσ2 の間の局所的な評価指標は J 12 ×σ1 ×σ2 である。これをグラフ中の全ての辺に関して合算したものが全体の評価指標となる。例えば、このグラフ表現を用いて巡回セールスマン問題を解く場合、訪問する目的地の順序が変数としてσに対応し、目的地間の距離が変数間の関係として J に― 95 ―

対応する。
候補者らは、図 2（a）の規則的な構造は、コンピュータにおける、メモリ（記憶装置）（図 2（b））の構造そのものであることに気付いた。しかし、通常のメモリは、データを格納する機能しか持たないのでこのままではアニーリングが実現できない。そこで、候補者らは、図 2（c）に示すように、個々のメモリに、演算器をそれぞれ設けるというアイデアで、アニーリングの計算が並列で行えるようにした。しかし、2 章で説明したように局所解に陥る問題が残る。
そこで、候補者らは局所解脱出回路を発案した。これを実現するために、変数の値をランダムに更新するかどうかを示す乱数値が入力されている［1］。
この方式では、全てのメモリが演算器を持っているので、情報のやり取りが最小となり、電力効率の高いコンピュータが構成できる。
コンピュータのメモリは、CMOS（Complementary Metal Oxide Semicondutor）で構成されているので、候補者らは、この方式を使う最適化問題の解法を、CMOS アニーリング法と名付けた。

図 2 ．組合せ最適化問題とメモリ構造の対応［3］

候補者らは 2015 年に上記の構造に基づく CMOS アニーリングチップを開発した（図 3）。
MAXCUT 問題と呼ばれる組合せ最適化問題を汎用コンピュータと同等の処理時間で、消費電力 1800 分の 1 で計算できることを確認し、CMOS アニーリング法の有効性を示した。
MAXCUT 問題はアニーリング法のベンチマークによく用いられる問題で、回路設計の最適化等の応用がある［9］。
さらに、候補者らは複数チップを接続して仮想的に 1 枚の大きなチップを構成できる技術をも開発した。2018 年には、これを実証するため 25 チップを搭載した CMOS アニーリングマシンを先駆的に開発した（図 4）。同様のベンチマークで大規模な問題になるほど汎用コンピュータに対して計算性能が高くなることを確認した（図 5）［4］。この技術はさらに多数のチップを接続できるため、社会課題に対応するような大規模な組合せ最適化問題に対してもCMOS アニーリングマシンが適用できることを示した。
本章で述べたアニーリング方式の比較を表 1 に示す。候補者らが提案した CMOS アニー
リング法は社会課題の解決に向けて組合せ最適化問題を解くことを目指しており、従来方式の課題であった大規模な問題を高速に解ける点が特長である。

― 96 ―

図 3 ．開発した CMOS アニーリングチップ

図 4 ．25 チップを搭載した CMOS アニーリングマシン― 97 ―

図 5 ．要素数 102,400 の CMOS アニーリングマシンにおける組合せ最適化問題の計算性能表 1 ．組合せ最適化問題解法の比較

発表年
狙い

シミュレーテッドアニー
リング
1983 年特徴

汎用的な最適化問題の解法
汎用的課題

計算時間がかかる

量子アニーリング

CMOS アニーリング

アルゴリズム：1998 年
コンピュータ：2011 年
量子効果（重ね合わせ）の活用による高速解法
高速かつ高精度2015 年

大規模化が難しい（2,048 要素数）
最適化問題のモデル化

大規模な最適化問題の高速・高効率解法計算規模に対する柔軟性（102,400 要素数以上）
最適化問題のモデル化

4 ．本技術の普及活動
3 章で述べた通り、大規模な問題を処理するためのハードウェア技術を開発したが、CMOS アニーリング法の実用化に向けて、ソフトウェア開発を含めた取り組みが不可欠である。これに向けて、候補者らは 2 つのクラウド環境を整備し、提供している（図 6）。一つはパートナーとともに実社会の課題を解決すること、もう一つは、CMOS アニーリング法を普及させるために、ユーザの裾野を広げることを目的としている。以下、それぞれについて説明する。

― 98 ―

図 6 ．CMOS アニーリングマシンのクラウド環境

4.1 エキスパート向けクラウド環境の構築と提供
前者に向けては、CMOS アニーリングチップ 25 枚を搭載した大規模なコンピュータをインターネット経由で使用するためのクラウド環境を構築し、2018 年 10 月から運用を開始した。この環境は事業化を見据えた価値実証を主なターゲットとしており、エキスパート用として共同で検討するパートナー向けに無償で公開している。この環境では、Web サイトおよび Web API を通じて、ユーザが作成した組合せ最適化問題を投入し、結果を確認することができる。現在、パートナーと密に連携して、具体的な組合せ最適化問題を図 2（a）で示した規則的な構造に変換するモデル化技術を中心に技術開発を進めている。
このクラウド環境は 2019 年 2 月現在、8 つの企業と 6 つの大学で利用されており、既に4000 ジョブを超える計算を実行している。アプリケーション領域としては、金融や工場における生産計画の最適化等を含んでいる。ジョブ数でみると 8 割強が金融分野のものであり、CMOS アニーリング法活用に強い関心があることが伺える。
4.2 チュートリアル用クラウド環境の構築と提供
ユーザの裾野を広げるため、誰もが自由に CMOS アニーリング法を体験できる、もう一つのクラウド環境を構築し、2018 年 9 月から運用を開始し、無償で提供している［10］。この環境では、Web サイトを通じて CMOS アニーリング法の動作を体験できるほか、アニーリング法に関する基礎知識が学べるチュートリアルも充実させ、将来的なユーザ育成の拠点としての役割を果たしている。この環境は NEDO 委託研究の成果である。
2019 年 1 月現在で、24,000 件のアクセスと 3,312 名のユーザを集めており、関心の高さが伺える。また、本サイトでは Web API の公開やチュートリアルの追加など、コンテンツを継続的に追加してユーザの利便性向上を図っており、今後もさらなる機能拡張を予定している。

― 99 ―

5 ．結言

社会課題の解決に向けて必須でありながら、計算量が膨大になるために、従来のコンピュータでは解けなかった組合せ最適化問題を高速に解くために半導体を活用した CMOS アニーリングマシンを先駆的に開発した。現在、クラウド環境を活用したユーザとの連携により、より多くの組合せ最適化問題を解くために必要なソフトウェア技術の開発を進めている。
CMOS アニーリング法ならではの大規模な問題を高速に解く能力を活かして社会課題を解決する所存である。

6 ．謝

辞

本成果の一部は、国立研究開発法人新エネルギー・産業技術総合開発機構（NEDO）の委託業務の結果得られたものです。

参考文献［1］ Masato Hayashi, Masanao Yamaoka, Chihiro Yoshimura, Takuya Okuyama, Hidetaka Aoki, andHiroyuki Mizuno, An accelerator chip for ground-state search of the Ising model with
asynchronous random pulse distribution, 6 th International Workshop on Advances inNetworking and Computing（WANC 15）
, December 2015
［2］ Chihiro Yoshimura, Masanao Yamaoka, Hidetaka Aoki, and Hiroyuki Mizuno, Spatial
computing architecture using randomness of memory cell stability under voltage control, 21stEuropean Conference on Circuit Theory and Design（ECCTD 2013）, September 2013.
［3］ Masanao Yamaoka, Chihiro Yoshimura, Masato Hayashi, Takuya Okuyama, Hidetaka Aoki, andHiroyuki Mizuno, 20k-spin Ising chip for combinational optimization problem with CMOS
annealing, IEEE International Solid-State Circuits Conference（ISSCC 2015）, February 2015.
［4］【ニュースリリース】約 1 兆の 500 乗通りの膨大なパターンから瞬時に実用に適した解を導く室温動作可能な新型半導体コンピュータを試作（2015/2/23）
http://www.hitachi.co.jp/rd/news/2015/0223.html［5］【ニュースリリース】
実社会の複雑な問題の高速処理を実現し、問題規模に応じてスケーラブルに構成可能な世界最大規模の CMOS アニーリングマシンを開発（2018/6/15）
http://www.hitachi.co.jp/rd/news/2018/0615.html/［6］ S. Kirkpatrick, C.D. Gelatt, and M.P. Vecchi, Optimization by Simulated Annealing, Science,Vol.220, No.4598, pp.671-680. 1983
［7］ W. Johnson et al., Quantum annealing with manufactured spins, Nature, vol. 473, pp. 194198, May 2011［8］ Vicky Choi, Minor-embedding in adiabatic quantum computation：I. The parameter setting
problem , Quantum Information Processing, October 2008, Volume 7, Issute 5, pp. 193-209［9］ Francisco Barahona, An Application of Combinatorial Optimization to Statistical Physics andCircuit Layout Design , Operations Ressearch, Volume 36, No.3,1988［10］Annealing Cloud Web
https://annealing-cloud.com/― 100 ―