2020-11-09 株式会社富士通研究所
株式会社富士通研究所（注1）（以下、富士通研究所）は、University of Toronto（注2）（以下、トロント大学）と共同で、組合せ最適化問題を高速に解く富士通株式会社（以下、富士通）（注3）の新アーキテクチャー「デジタルアニーラ」において、メガビット級の大規模問題に対応する新たな並列探索技術を開発しました。
2018年5月より富士通が提供している「FUJITSU Digital Annealer クラウドサービス」では、現在、第二世代の8,192bit（ビット）のサービスを提供し様々な分野の最適化問題に適用されています。適用が進むにつれ、実社会での複雑な組合せ最適化問題の解決に向け、さらなる大規模化のニーズが高まってきています。
今回、新たな並列探索技術を適用した「デジタルアニーラ」の大規模求解システムにより、イジングマシン（注4）では世界で初めて1Mbit（メガビット）規模の実用問題での求解を実証しました。
富士通研究所は、本技術を活用した「デジタルアニーラ」の大規模求解システムを様々な分野の組合せ最適化問題に適用することで、実社会の課題解決に貢献します。
開発の背景と課題
近年、企業のお客様のDXが加速する中、実社会における課題において様々な要因の組合せの中から最適な解をより早く見つけ出したいというニーズが、製造や物流、災害対策、新薬開発などあらゆる分野において高まってきています。「デジタルアニーラ」は、イジングモデル（注5）をもとに表現された組み合わせ最適化問題を高速に解く計算機アーキテクチャーです。現在、8,192bitのビットサイズまでのサービスを提供しており、様々な分野の最適化問題に適用しています。
実社会の組合せ最適化問題では、様々な分野で更なる大規模な問題を解きたいというニーズが高まってきており、製造分野では、多品種少量生産の現場において、部品ごとに異なる複雑な製造工程を人員・装置などのリソースや納期を考慮して工場全体でスケジューリングするなど、生産効率向上に向けた大規模な最適化が必要とされています。また、物流分野では、配送計画において、県域規模の最適化だけでなく全国規模を対象とした大規模な計画を立案することが求められています。
今、直面しているこれらの実用的な問題に対応するためには、1Mbit規模の組合せ最適化問題を解く必要がありますが、計算量が爆発的に増えるため、限られた時間の中で有効な解を得ることは困難でした。
図1 実用問題とビット規模
開発した技術
今回、「デジタルアニーラ」のアーキテクチャーを拡張し、大規模問題で高い求解性能を実現する新たな並列探索技術を開発しました。本技術を適用した「デジタルアニーラ」の大規模求解システムで、1Mbit規模の大規模問題の求解を実証しました。開発した技術の特長は以下のとおりです。
- 大規模向け適応的並列探索技術「デジタルアニーラ」は、ある状態からより最適な状態に遷移するための更新ビット探索を繰り返し行う基本最適化モジュールを高い並列度で構成することにより、高い探索性能を実現しています。 今回、大規模問題に向け、複数ビット更新により、急速なエネルギー降下が期待される初期段階においては複数ビット更新を行い、収束が進んだ段階では解探索精度を高める単一ビット更新に切り替える適応的並列探索技術を開発し、大規模な問題に対しても高効率な探索処理を実現しました。
- 複数サーバ並列での協調探索技術サーバ1台では扱えない大規模問題に対して、全体解の一貫性を担保しつつ、複数のサーバで協調して大規模問題を解く技術を開発しました。大規模問題を複数の部分問題に分割して複数サーバに割り当て、サーバ間で部分問題の解を共有し全体解の状態を把握しながら各サーバでの局所探索を適切に制御します。本技術を適用した大規模求解システムにより、1Mbit級の大規模問題の求解を可能としました。
図2 新技術の概要
効果
今回開発した1Mbitに対応した大規模求解システムの実用問題への適用として、多品種少量のサーバ生産スケジュールを決定する問題を求解しました。この問題を解くには、作業の順序、作業者の技能レベル、休憩時間、設備の利用可能時間などの複雑な制約条件を考慮する必要があります。問題のビット数は、作業数、作業者数、設備数、時間スロット数の積で決定され、非常に大きな規模となります。
本例では、作業数100、設備数12、作業者数13、時間スロット65の設定で、総ビット数：1,014,000 bitの条件で実証を行いました。求解の結果、複雑な制約条件を満足して作業順序や設備利用時間に適切な人員が割当られており、1Mbit級の実用問題の求解の成功が確認できました(図3)。
図3 生産スケジュール問題の概要と求解結果
拡大イメージ
今後
富士通研究所は、今回開発した「デジタルアニーラ」の大規模化技術を、中分子の新薬開発、全国規模の輸配送計画、都市圏の交通渋滞の解消、ニューノーマル時代に適したワークシフト計画など、実社会の様々な大規模組合せ最適化問題に適用していきます。
商標について
記載されている製品名などの固有名詞は、各社の商標または登録商標です。
以上
注釈
- 注1 株式会社富士通研究所：
- 本社 神奈川県川崎市、代表取締役社長 原 裕貴。
- 注2 University of Toronto：
- 所在地 カナダ オンタリオ州トロント市、学長 Meric S. Gertler。
- 注3 富士通株式会社：
- 本社 東京都港区、代表取締役社長 時田 隆仁。
- 注4 イジングマシン：
- イジングモデルで表現された組み合わせ最適化問題を解くマシン。
- 注5 イジングモデル：
- 統計物理学の分野で使われる強磁性体の振る舞いを、スピンの上向き下向きの状態と隣接するスピン間の相互作用を用いて説明する物理モデルのこと。組合せ最適化問題はスピン状態を0か1の情報と見ることでイジングモデルを用いて表現することが出来ます。この時、イジングモデルのエネルギーが最小となるスピン状態が組合せ最適化問題の最適解と対応しています。
本件に関するお問い合わせ
株式会社富士通研究所
ICTシステム研究所
