組み合わせ最適化問題をAWSで高速処理、東芝デジタルが期間限定で無償公開：人工知能ニュース

[松本貴志，MONOist]

　東芝デジタルソリューションズは2019年7月17日、大規模組み合わせ最適化問題を高速に処理するソフトウェア「シミュレーテッド分岐マシン（Simulated Bifurcation Machine）」をAWS（アマゾンウェブサービス）のマーケットプレース上で公開したと発表した。2019年10月末までの期間限定で、PoC（概念検証）版として無償公開されている。

　同ソフトは2019年4月に東芝が公表した技術「シミュレーテッド分岐アルゴリズム」を活用している。このアルゴリズムは、大規模な組み合わせ最適化問題の高精度な近似解（良解）を既存の半導体デジタル計算機を用いて短時間で導出するものとなる。

　組み合わせ最適化問題の処理では、量子アニーリングマシンなど次世代計算機を用いた手法も注目を集めているが、「扱える問題の大規模化や解を見つけるまでの時間の短縮が課題」（東芝）。また、半導体デジタル計算機における従来のアルゴリズムは並列計算による高速化が原理的に困難だった。シミュレーテッド分岐アルゴリズムは、非線形力学系の分岐現象、断熱過程、エルゴード過程の3現象を「うまく利用して」（同社）、既存のコンピュータにおいても大規模な組み合わせ最適化問題の良解を高速に導出する。

シミュレーテッド分岐アルゴリズムの概要（クリックで拡大） 出典：東芝

　FPGAで同アルゴリズムを実行した場合、2000変数で全結合（約200万結合）の問題を0.5ミリ秒で処理する。これは、当時世界最速だったレーザーを用いた量子コンピュータと比べて約10倍高速であるとする。また、8基のGPUクラスタを用いた場合には、10万変数で全結合（約50億結合）の大規模問題も数秒程度で良解を導出するという。東芝は独自に研究を進める量子計算機理論から原理を発見したとし、「量子力学に導かれてなされた古典力学の本発見は、未知の数学の定理をも示唆する学術的にも新しいもの」（同社）としている。

　東芝デジタルソリューションズは同アルゴリズムを用いてシミュレーテッド分岐マシンを開発し、さまざまな分野での社会課題解決に向けて実証実験を開始する。AWS Marketplace上で無償公開されたPoC版は、最大1万変数のイジング問題、MAX-SAT問題、MAX-CUT問題に対応する。

　今後、さらに大規模な問題への対応を進めるとともに、事業化に向け2019年中にパブリッククラウド上でのサービス提供開始を目指す。