富士通研究所は、トロント大学と共同で富士通の新アーキテクチャー「デジタルアニーラ」においてメガビット級の大規模問題に対応する新たな並列探索技術を開発したと発表した。新たな並列探索技術を適用した「デジタルアニーラ」の大規模求解システムにより、イジングマシンでは世界で初めて1Mbit規模の実用問題での求解を実証したという。
イジングマシンは、イジングモデルで表現された組み合わせ最適化問題を解くマシン。イジングモデルは、統計物理学で使われる強磁性体の振る舞いをスピンの上向き下向きの状態と隣接するスピン間の相互作用を用いて説明する物理モデル。組み合わせ最適化問題はスピン状態を0か1の情報と見ることで、イジングモデルを用いて表現することができる。
デジタルアニーラは、イジングモデルを基に表現された組み合わせ最適化問題を高速に解く計算機アーキテクチャー。2018年5月から富士通が提供する「FUJITSU Digital Annealer クラウドサービス」では、第2世代の8192bitのサービスを提供しさまざまな分野の最適化問題に適用されている。
実用問題とビット規模
実社会の組み合わせ最適化問題では、さまざまな分野でさらなる大規模な問題を解きたいというニーズが高まってきているが、実用的な問題に対応するためには、1Mbit規模の組み合わせ最適化問題を解く必要があった。しかし計算量が爆発的に増えるため、限られた時間の中で有効な解を得ることは困難だった。
新技術の概要
今回開発した新たな並列探索技術を適用した「デジタルアニーラ」の大規模求解システムで1Mbit規模の大規模問題の求解を実証した。大規模求解システムでは、複数ビット更新により、急速なエネルギー降下が期待される初期段階においては複数ビット更新を行い、収束が進んだ段階では解探索精度を高める単一ビット更新に切り替える適応的並列探索技術を開発した。
さらに、サーバー1台では扱えない大規模問題に対して、全体解の一貫性を担保しつつ、複数のサーバーで協調して大規模問題を解く技術を開発した。これにより、大規模問題を複数の部分問題に分割して複数サーバーに割り当て、サーバー間で部分問題の解を共有し全体解の状態を把握しながら各サーバーでの局所探索を適切に制御する。
生産スケジュール問題の概要と求解結果
同システムを利用して多品種少量のサーバー生産スケジュールを決定する問題を求解した例では、作業数100、設備数12、作業者数13、時間スロット65の設定で、総ビット数が101万4000bitの条件で実証を行った。この問題を解くには、作業の順序、作業者の技能レベル、休憩時間、設備の利用可能時間などの複雑な制約条件を考慮する必要があり、問題のビット数は、作業数、作業者数、設備数、時間スロット数の積で決定され、非常に大きな規模となる。
その中で、求解の結果、複雑な制約条件を満足して作業順序や設備利用時間に適切な人員が割当られており、1Mbit級の実用問題の求解の成功が確認できたという。
富士通研究所は、今回開発したデジタルアニーラの大規模化技術を、中分子の新薬開発、全国規模の輸配送計画、都市圏の交通渋滞の解消、ニューノーマル時代に適したワークシフト計画など、実社会のさまざまな大規模組合せ最適化問題に適用しいく。
