大規模な組み合わせ最適化問題を解く確率的計算技術を開発~解収束時間を3桁以上低減し実時間で社会還元できる道を開く~

ad

2022-04-01 東北大学 電気通信研究所,科学技術振興機構

ポイント
  • 大規模な組み合わせ最適化問題を高速に解く確率的計算技術を開発
  • 量子アニーリングマシンと比較して、約16倍の大規模な組み合わせ最適化問題を解くことができる技術を、一般的なパソコン(古典コンピューター)上で実証
  • 従来手法と比較して約1,000倍の高速化が可能となり、複雑な社会問題を効率的に処理できる新たな手法として期待

組み合わせ最適化問題は、膨大なデータの組み合わせから最適解を求める問題として知られています。組み合わせ最適化問題を高速に処理可能な技術として注目されているのがD-Wave Systems社などの量子アニーリングマシンですが、いくつもの難点があり、大規模な組み合わせ最適化問題を解くことは困難です。東北大学 電気通信研究所の鬼沢 直哉 准教授、羽生 貴弘 教授、カナダ・マギル大学のWarren J.Gross 教授らの共同研究チームは、確率的演算に基づく新たなシミュレーテッドアニーリング技術を開発し、量子アニーリングで知られるD-Wave Systems社のマシンと比較して、約16倍の大規模な組み合わせ最適化問題を解くことに成功しました。

今回開発した確率的計算技術は、一般的なパソコン(古典コンピューター)で利用可能なアルゴリズムでありながら最適解への収束率を飛躍的に高めることに成功し、極低温動作を必須とする量子アニーリングマシンを実用性で大幅に上回る性能を実証しました。また、決定論的計算に基づく従来手法と比較して、約1,000倍高速に組み合わせ最適化問題を解くことにも成功しました。多くの点で既存のアニーリング技術を大幅に超える性能を示しており、今後の情報処理技術に新たな展開をもたらし得るものと期待されます。

本研究成果は2022年3月30日付で米国の科学誌「IEEE Transactions on Neural Networks and Learning Systems」でオンライン公開されました。

本研究の一部は、科学技術振興機構・戦略的創造研究推進事業・さきがけ JPMJPR18M5、科学技術振興機構・戦略的創造研究推進事業・CREST JPMJCR19K3、日本学術振興会・科学研究費助成事業・基盤研究(B) JP21H03404などの支援を受けて行われたものです。

詳しい資料は≫

<論文タイトル>
“Fast-Converging Simulated Annealing for Ising Models Based on Integral Stochastic Computing,”IEEE Transactions on Neural Networks and Learning Systems
DOI:10.1109/TNNLS.2022.3159713
<お問い合わせ先>

<研究に関すること>
鬼沢 直哉(オニザワ ナオヤ)
東北大学 電気通信研究所 准教授

<JST事業に関すること>
前田 さち子(マエダ サチコ)
科学技術振興機構 戦略研究推進部 ICTグループ

<報道担当>
東北大学 電気通信研究所 総務係
科学技術振興機構 広報課

ad
1602ソフトウェア工学
ad
ad


Follow
ad
タイトルとURLをコピーしました