NTT DATA

DATA INSIGHT

NTT DATAの「知見」と「先見」を社会へ届けるメディア

キーワードで探す
カテゴリで探す
サービスで探す
業種で探す
トピックで探す
キーワードで探す
カテゴリで探す
サービスで探す
業種で探す
トピックで探す
2020.9.14技術トレンド/展望

組合せ最適化問題の新解法「アダプティブ・バルク・サーチ」

近年、組合せ最適化問題を高速に解く手法の研究開発が活発に行われている。NTTデータは2020年8月17日に広島大学と共同で「アダプティブ・バルク・サーチ」を公開した(※1)。本稿では、これらの技術に注目が集まる背景と、公開した手法の特徴について説明を行う。

量子アニーリングやGPU/FPGAを用いて、組合せ最適化問題を高速に解くアーキテクチャーに注目が集まっています。組合せ最適化問題という言葉は、あまり聞きなれないかもしれませんが、金融、交通、物流、製造、素材開発など様々な分野の裏に潜んでおり、高速化が困難な問題として知られています。そのため、この組合せ最適化の高速計算手法を開発することは、大きな技術革新につながります。 このような背景を受けて、NTTデータと広島大学は「アダプティブ・バルク・サーチ」という手法を公開しました。本稿では、「アダプティブ・バルク・サーチ」に関する3つの特徴を、わかりやすく説明します。

図1:「アダプティブ・バルク・サーチ」の動作イメージ

図1:「アダプティブ・バルク・サーチ」の動作イメージ

1秒間に1兆を超える解探索速度

組合せ最適化問題は、様々な選択肢の中から最も良い選択肢を探す問題です。従って、どれだけ高速に良い解を探索できるかが勝負になります。「アダプティブ・バルク・サーチ」では、NVIDIA GPU(※2)を4基搭載した計算サーバー(※3)を用いて、1秒間に1兆を超える解を探索する計算速度を実現しています。

効率的な探索アルゴリズム

どんなに高速な探索速度を実現しても、同じ解を何度も探索したり、最適な解が無さそうな範囲ばかり探索したりしていては、良い解は得られません。「アダプティブ・バルク・サーチ」では、ホストCPUによるグローバルサーチ(俯瞰した視点での探索)と、GPUによるローカルサーチ(より良い解が暫定解の近くにないかつぶさに探索)を組み合わせることで、探索速度を最大限に活かした効率的な求解処理を実現しています。

さらなる計算速度向上を想定した設計

業務要件によっては、非常に複雑な組合せ最適化問題を解く必要があり、先述した1秒間に1兆を超える探索速度でも不十分な可能性があります。「アダプティブ・バルク・サーチ」は、このような厳しい性能要件への対応も考慮して、GPU台数に比例した計算速度の向上が可能な設計となっています。

「アダプティブ・バルク・サーチ」の具体的な評価結果については、論文(※4)で公開しており、最大カット問題、巡回セールスマン問題、ランダム問題に対する高速性を定量的に確認することができます。

最後に

NTTデータでは、今回得られた研究結果を基に、流通、金融、製造分野などの諸問題や、AI・機械学習の高性能化に取り組んでいきます。また、これまで解くことが困難であった問題を効率的に解くことで、エネルギー利用の効率化やスマートな物流網などの、社会課題解決に向けた適用可能性を拡大するとともに、広島大学と共同で本手法のさらなる改善に取り組んでいきます。
(※1)「GPUの計算性能を最大限活用する組合せ最適化問題の新解法を公開」

https://www.nttdata.com/jp/ja/news/release/2020/081701/

(※2)NVIDIA GeForce RTX 2080 Ti GPU
(※3)現状の構成では、32,768変数の問題まで扱うことができます。
お問い合わせ