研究開発センター

概要

株式会社東芝（以下、東芝）および、東芝デジタルソリューションズ株式会社（以下、TDSL）は、新薬の開発、配送ルート計画や投資ポートフォリオの作成など、様々な社会課題に現れる組合せ最適化問題を解く東芝独自の「シミュレーテッド分岐マシン」の速度・精度・規模を大幅に向上させることができる2つの新アルゴリズムを開発しました。新アルゴリズムは、東芝が2019年4月に発表した「シミュレーテッド分岐アルゴリズム」^(注1)を疑似量子トンネル効果^(注2)などにより発展させたもので、短時間で良解（高精度な近似解）を見つける高速アルゴリズムと、より高精度な解を見つける高精度アルゴリズムの2種類です。
新アルゴリズムにより、発表当時世界最速を記録した従来アルゴリズム^(注1)に比べて約10倍の高速化を達成するともに、より大規模な問題の最適解獲得に成功しました。また、16台のGPU^(注3)から成る世界最大規模の100万変数のマシンを実現し、通常の計算機で約1年2か月かかる大規模な計算を約30分で行うことに成功しました。
本技術は、例えばコロナ禍において必要となる治療薬の開発や医療従事者の最適な勤務シフトの作成など、今まさに求められている社会課題への応用が期待されます。
本技術の成果は、2021年2月3日付（米国東海岸時間）の米国オンライン科学雑誌「Science Advances」に掲載されました^(注4)。

開発の背景

社会や産業における様々な活動を効率的に行うためには、膨大な数の選択肢から最適なものを見つけ出す必要があります。例えば昨今のコロナ禍においては、治療薬に最適な候補物質の選定、医療従事者の最適な勤務シフト作成、患者の最適な搬送先選定などが挙げられます。こうした問題の多くは、数学的には組合せ最適化問題と呼ばれるものに帰着します。組合せ最適化問題は、問題の規模によって解の候補の数が指数関数的に増加する、いわゆる組合せ爆発のために解くことが大変難しい問題として知られており、組合せ最適化専用計算機の研究開発が国内外で活発に行われています。大規模な組合せ最適化問題を高速に解くことができる計算機を開発できれば、より効率的な社会や産業の実現に貢献できるものと期待されています。
東芝は2019年4月、シミュレーテッド分岐アルゴリズムという独自の組合せ最適化アルゴリズムを発表しました^(注1)。本アルゴリズムを搭載した「シミュレーテッド分岐マシン」は、本アルゴリズムが有する高い並列性を活かすことで大規模な組合せ最適化問題の良解を非常に高速に得ることができます。しかし、古典力学における断熱過程^(注5)に基づく従来のアルゴリズム（「断熱的シミュレーテッド分岐アルゴリズム（aSB）^(注6)」）は、大規模問題の最適解（厳密解）が得られない場合がありました。

本技術の特徴

今回、東芝とTDSLは、従来の断熱的シミュレーテッド分岐アルゴリズムを発展させることにより、より高速に、より高精度に組合せ最適化を実行できる2つのアルゴリズムを新たに開発しました。
1つ目は、短時間で良解を見つける高速アルゴリズム「弾道的シミュレーテッド分岐アルゴリズム（bSB）^(注7)」です。従来のaSBで生じるエラーを低減する工夫により、シミュレーテッド分岐マシンの高速化と高精度化を実現しました。これをFPGA^(注8)で高速実装することで、2,000変数問題の良解を従来のシミュレーテッド分岐マシン^(注1)に比べて約10倍高速に得ることができます（図1）。
2つ目は、他のマシンを凌ぐ計算速度でより高精度な解を見つける高精度アルゴリズム「離散的シミュレーテッド分岐アルゴリズム（dSB）^(注9)」です。疑似量子トンネル効果によって古典力学の限界を打破してさらなる高精度化を実現し、同じ2,000変数問題の最適解（厳密解の推定値）を得ることができます。これをFPGAで高速実装した2,048変数対応シミュレーテッド分岐マシンは、最適解を得るのにかかる計算時間で量子アニーラやコヒーレントイジングマシンなど他のマシンを凌駕する高速性を達成しました（図2）。また、16台のGPU^(注3)からなるGPUクラスタを用いることで100万変数という世界最大規模のマシンを実現し、約30分で最適解にほぼ到達できました（図3）。これは、最適化問題を解くための一般的な手法であるシミュレーテッドアニーリングを通常の計算機（CPU）上で実行した場合およそ1年2か月かかる計算を30分という現実的な時間に短縮したこと（約2万倍の高速化）を意味します。
実社会の問題に適用する際は、即時に良解が必要な場合はbSB、時間をかけてでも極めて精度の高い解が必要な場合はdSB等といった用途に応じた使い分けが想定されます。

今後の展望

東芝とTDSLは、今回開発した新たなシミュレーテッド分岐アルゴリズムを活用して、FPGAを用いたオンプレミス版およびGPUを用いたクラウド版のシミュレーテッド分岐マシンを2021年中にサービス提供し、効率的で持続可能な社会の実現に貢献していきます。