【東芝】SBMの新アルゴリズムを開発‐成功確率を“カオスの縁”で桁違いに向上

　東芝は7日、新薬の開発、配送ルート計画や投資ポートフォリオの作成など、様々な社会課題に現れる組み合わせ最適化問題を解く同社独自の量子インスパイアード組み合わせ最適化計算機「シミュレーテッド分岐マシン」（SBM）において、組み合わせ最適化技術の能力を評価する重要な指標の一つである、限られた試行回数で最適解または既知最良解を得る確率（成功確率）を桁違いに向上させる新アルゴリズムを開発したと発表した。

　これまでのアルゴリズムにおいても、十分な回数の試行によって最適解または既知最良解を導き出すことは可能だったが、大規模問題になると、解の探索過程において局所最適解に陥る場合があり、少ない試行回数で高確率に解を得ることが課題となっていた。

　同社は、2019年4月に発表した「シミュレーテッド分岐アルゴリズム」（SBアルゴリズム）および、計算速度と計算精度を向上させ21年2月に発表した第2世代SBアルゴリズムを基盤に、SBアルゴリズムの特徴である分岐現象を引き起こすためのパラメータ（分岐パラメータ）を従来の1個から、位置変数ごとに割り当てるように拡張した。

　さらに、各分岐パラメータを対応する位置変数の値に依存して個別に制御させることで、局所最適解から抜け出して大域最適解へ到達しやすいように高度化したのが、今回開発した第3世代のSBアルゴリズムとなる。

　第3世代アルゴリズムは、SBアルゴリズムの特徴である分岐現象を引き起こすための調整パラメータである分岐パラメータを、従来の1個から、位置変数ごとに割り当てるように拡張し、さらに、個々の分岐パラメータを対応する位置変数の非線形関数に依存して個別に制御する非線形制御を導入した。その際、非線形制御の強さを調整する非線形強度パラメータを変えていくと、あるところで成功確率が100％近くまで飛躍的に向上することを発見した。

　さらに、その原理を追求するため、第3世代SBMにおけるダイナミクスを詳しく調べ、非線形強度パラメータが小さいときは規則的な振る舞いを示し、大きいときはカオスとなることを明らかにし、そのちょうど境界にあたる“カオスの縁”において、局所最適解に陥ることなく大域最適解に到達する成功確率の急向上が観測されることを発見した。

この発見は、初め2000スピン・全結合のイジング問題でなされたが、複数の異なる変数の問題においても同様の現象が起こることを確認した。さらに、SBアルゴリズムの特徴である高い並列性は維持されており、FPGAを用いて超並列実装することで、第2世代SBMに比べて10～100倍の高速化を達成した。

　同技術の成果は、6日付（米国東海岸時間）の米国物理学会の学術論文誌「Physical Review Applied」に掲載された。