富士通研究所は11月9日、University of Toronto（以下、トロント大学）と共同で、組合せ最適化問題を高速に解く富士通の新アーキテクチャー「デジタルアニーラ」において、メガビット級の大規模問題に対応する新たな並列探索技術を開発したと発表した。

　2018年5月より富士通が提供している「FUJITSU Digital Annealer クラウドサービス」では、現在、第二世代の8,192bitのサービスを提供し様々な分野の最適化問題に適用されている。適用が進むにつれ、実社会での複雑な組合せ最適化問題の解決に向け、さらなる大規模化のニーズが高まってきている。
　そして今回、新たな並列探索技術を適用した「デジタルアニーラ」の大規模求解システムにより、イジングマシンでは世界で初めて1Mbit規模の実用問題での求解を実証した。
　富士通研究所は「本技術を活用したデジタルアニーラの大規模求解システムを様々な分野の組合せ最適化問題に適用することで、実社会の課題解決に貢献する」としている。

開発の背景と課題

　近年、企業ユーザのDXが加速する中、実社会における課題において様々な要因の組合せの中から最適な解をより早く見つけ出したいというニーズが、製造や物流、災害対策、新薬開発などあらゆる分野において高まってきている。「デジタルアニーラ」は、イジングモデルをもとに表現された組み合わせ最適化問題を高速に解く計算機アーキテクチャ。現在、8,192bitのビットサイズまでのサービスを提供しており、様々な分野の最適化問題に適用している。
　実社会の組合せ最適化問題では、様々な分野で更なる大規模な問題を解きたいというニーズが高まってきており、製造分野では、多品種少量生産の現場において、部品ごとに異なる複雑な製造工程を人員・装置などのリソースや納期を考慮して工場全体でスケジューリングするなど、生産効率向上に向けた大規模な最適化が必要とされている。また、物流分野では、配送計画において、県域規模の最適化だけでなく全国規模を対象とした大規模な計画を立案することが求められている。
　今、直面しているこれらの実用的な問題に対応するためには、1Mbit規模の組合せ最適化問題を解く必要があるが、計算量が爆発的に増えるため、限られた時間の中で有効な解を得ることは困難だった。

開発された技術

　今回、「デジタルアニーラ」のアーキテクチャーを拡張し、大規模問題で高い求解性能を実現する新たな並列探索技術が開発された。同技術を適用した「デジタルアニーラ」の大規模求解システムで、1Mbit規模の大規模問題の求解を実証した。開発した技術の特長は次のとおり。

大規模向け適応的並列探索技術
　「デジタルアニーラ」は、ある状態からより最適な状態に遷移するための更新ビット探索を繰り返し行う基本最適化モジュールを高い並列度で構成することにより、高い探索性能を実現している。
　今回、大規模問題に向け、複数ビット更新により、急速なエネルギー降下が期待される初期段階においては複数ビット更新を行い、収束が進んだ段階では解探索精度を高める単一ビット更新に切り替える適応的並列探索技術を開発し、大規模な問題に対しても高効率な探索処理を実現した。

複数サーバ並列での協調探索技術
　サーバ1台では扱えない大規模問題に対して、全体解の一貫性を担保しつつ、複数のサーバで協調して大規模問題を解く技術を開発した。大規模問題を複数の部分問題に分割して複数サーバに割り当て、サーバ間で部分問題の解を共有し全体解の状態を把握しながら各サーバでの局所探索を適切に制御する。同技術を適用した大規模求解システムにより、1Mbit級の大規模問題の求解を可能とした。

効果

　今回開発された1Mbitに対応した大規模求解システムの実用問題への適用として、多品種少量のサーバ生産スケジュールを決定する問題を求解した。この問題を解くには、作業の順序、作業者の技能レベル、休憩時間、設備の利用可能時間などの複雑な制約条件を考慮する必要がある。問題のビット数は、作業数、作業者数、設備数、時間スロット数の積で決定され、非常に大きな規模となる。
　本例では、作業数100、設備数12、作業者数13、時間スロット65の設定で、総ビット数：1,014,000 bitの条件で実証を行った。求解の結果、複雑な制約条件を満足して作業順序や設備利用時間に適切な人員が割当られており、1Mbit級の実用問題の求解の成功が確認できたという(図3)。

今後

　富士通研究所は今後について「今回開発したデジタルアニーラの大規模化技術を、中分子の新薬開発、全国規模の輸配送計画、都市圏の交通渋滞の解消、ニューノーマル時代に適したワークシフト計画など、実社会の様々な大規模組合せ最適化問題に適用していく」との考えを示している。