東芝、組合せ最適化で成功確率を大幅に高める新アルゴリズムを開発

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

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

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

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

今回の新アルゴリズムでは、位置変数に依存した分岐パラメータの制御を行うことにより、条件によって解探索過程が規則的な振る舞いや不規則な振る舞い（カオス）を示す。

この規則的振る舞いとカオスの境界となる「カオスの縁」でのカオスを有効利用することによって、局所最適解から抜け出しやすくなり、大域最適解に到達する成功確率を100％近くまで押し上げることに成功したという。

こうして、最適解または既知最良解を得るために要する時間で比較すると、第2世代のSBMに対し、約100倍の高速化を実現した。

組合せ最適化問題は、問題の規模によって解の候補数が指数関数的に増加する、いわゆる組合せ爆発から解くことがきわめて難しい問題として知られ、組合せ最適化に特化した計算機の研究開発は国内外で活発に行われている。

そうした中での今回の新アルゴリズム開発は、大いに注目されるものだ。東芝ではこの第3世代SBアルゴリズムを用い、提供する量子インスパイアード最適化ソリューションの「SQBM＋」を強化し、効率的で持続可能な社会実現に貢献していきたいとした。

物流の最適・最短配送ルートの選定や、金融市場における収益性の高い投資ポートフォリオの作成、創薬における新たな分子設計の特定など、社会や産業に利活用できるシーンは非常に多い。今後の活用に期待が高まる。

（画像はプレスリリースより）




株式会社東芝　プレスリリース
https://www.global.toshiba/