ニュース
富士通研究所、「デジタルアニーラ」でメガビット級の大規模組み合わせ最適化問題に対応する技術を開発
2020年11月9日 12:13
株式会社富士通研究所は9日、カナダのトロント大学と共同で、組み合わせ最適化問題を高速に解く富士通株式会社の新アーキテクチャー「デジタルアニーラ」において、メガビット級の大規模問題に対応する新たな並列探索技術を開発したと発表した。
デジタルアニーラは、イジングモデルをもとに表現された、組み合わせ最適化問題を高速に解く計算機アーキテクチャー。現在、8192bitのビットサイズまでのサービスを提供しており、さまざまな分野の最適化問題に適用している。
一方、実社会の組み合わせ最適化問題では、さらなる大規模な問題を解きたいというニーズが高まってきており、製造分野では、多品種少量生産の現場において、部品ごとに異なる複雑な製造工程を、人員・装置などのリソースや納期を考慮して工場全体でスケジューリングするなど、生産効率向上に向けた大規模な最適化が必要とされていると説明。また、物流分野では、配送計画において、県域規模の最適化だけでなく、全国規模を対象とした大規模な計画を立案することが求められているという。
こうした問題に対応するためには、1Mbit規模の組み合わせ最適化問題を解く必要があるとして、富士通研究所ではデジタルアニーラのアーキテクチャーを拡張し、大規模問題で高い求解性能を実現する新たな並列探索技術を開発した。
デジタルアニーラは、ある状態からより最適な状態に遷移するための更新ビット探索を繰り返し行う基本最適化モジュールを高い並列度で構成することにより、高い探索性能を実現している。 今回、大規模問題に向け、複数ビット更新により、急速なエネルギー降下が期待される初期段階においては複数ビット更新を行い、収束が進んだ段階では解探索精度を高める単一ビット更新に切り替える適応的並列探索技術を開発し、大規模な問題に対しても高効率な探索処理を実現した。
また、サーバー1台では扱えない大規模問題に対して、全体解の一貫性を担保しつつ、複数のサーバーで協調して大規模問題を解く技術を開発した。大規模問題を複数の部分問題に分割して複数サーバーに割り当て、サーバー間で部分問題の解を共有し、全体解の状態を把握しながら各サーバーでの局所探索を適切に制御する。この技術を適用した大規模求解システムにより、1Mbit級の大規模問題の求解を可能とした。
開発した1Mbitに対応した大規模求解システムの実用問題への適用として、多品種少量のサーバー生産スケジュールを決定する問題を求解した。この問題を解くには、作業の順序、作業者の技能レベル、休憩時間、設備の利用可能時間などの複雑な制約条件を考慮する必要がある。問題のビット数は、作業数、作業者数、設備数、時間スロット数の積で決定され、非常に大きな規模となる。
実証は、作業数100、設備数12、作業者数13、時間スロット65の設定で、総ビット数101万4000bitの条件で行った。求解の結果、複雑な制約条件を満足して作業順序や設備利用時間に適切な人員が割り当てられており、1Mbit級の実用問題の求解の成功が確認できたという。
富士通研究所では、今回開発したデジタルアニーラの大規模化技術を、中分子の新薬開発や、全国規模の輸配送計画、都市圏の交通渋滞の解消、ニューノーマル時代に適したワークシフト計画など、実社会のさまざまな大規模組み合わせ最適化問題に適用していくとしている。
