全2072文字
PR

 NTTデータは2021年10月29日、様々な組み合わせ最適化問題を高速に解く「アダプティブ・バルク・サーチ」の実行環境を無料で公開した。広島大学と共同で開発した計算手法である。現実世界に存在する様々な問題を多数のユーザーに解いてもらうことで、同手法が役に立つ領域を探す狙いがある。

 NTTデータが広島大学大学院先進理工系科学研究科の中野浩嗣教授らの研究チームと共同で開発したアダプティブ・バルク・サーチは、二次非制約二値最適化(QUBO)問題の解を複数のGPU(Graphics Processing Unit)を使って並列で検索する計算手法。米NVIDIA(エヌビディア)製のGPU「GeForce RTX 2080 Ti」を4基使って、1秒間に1兆を超える解を探索できる。

 QUBO問題とは、n個の0または1の値をとる変数の積和が最小になる組み合わせを求める問題だ。複雑な物流配送ルートの最適化や金融商品ポートフォリオの最適化といった、様々な最適化問題をQUBO問題に落とし込んで解くことができる。

量子アニーリングなどと同じ「汎用アルゴリズム」

 一般に組み合わせ最適化問題は、「巡回セールスマン問題」など問題の種類に応じた専用のアルゴリズムを使って解く。それに対してアダプティブ・バルク・サーチは、様々な組み合わせ最適化問題をQUBO問題に落とし込んで解く汎用アルゴリズム(メタアルゴリズム)だ。同じようにQUBO問題に落とし込んで問題を解く汎用アルゴリズムとしては「焼きなまし法(SA)」や「量子アニーリング(QA)」などがある。

 今回、NTTデータがアダプティブ・バルク・サーチの実行環境を無料で公開した背景には、汎用アルゴリズムにつきまとう「ノー・フリー・ランチ定理」という課題がある。ノー・フリー・ランチ定理とは「あらゆる問題で性能の良い汎用最適化戦略は理論上不可能である」(広島大学の中野教授)というもの。言い換えれば、汎用アルゴリズムは専用アルゴリズムに性能ではかなわない、ということになる。

 例えばQUBO問題に落とし込む汎用アルゴリズムだと、組み合わせ最適化問題の中でも「MAXCUT問題」は比較的高速に解ける。一方で巡回セールスマン問題は苦手にする。巡回セールスマン問題は「コンコルド法」のような既存の専用アルゴリズムを使った方がより良い近似解を高速に得られる。

汎用アルゴリズムが役立つ場面を探す

 しかしNTTデータの先進コンピューティング技術センタに所属する矢実貴志シニアエキスパートは、専用アルゴリズムにも弱点があるという。例えば「巡回セールスマン問題に対して現実にありそうな制約を加えると、専用アルゴリズムを適用できなくなるケースがある」(矢実シニアエキスパート)。アダプティブ・バルク・サーチは汎用のアルゴリズムなので、制約が加わった巡回セールスマン問題でも適用でき、比較的高速に解ける。

 つまりノー・フリー・ランチ定理と向き合いながら、アダプティブ・バルク・サーチのような汎用アルゴリズムを使いこなすには「専用アルゴリズムの適用が難しく、汎用アルゴリズムであれば解けそうな問題」を見つけ出し、そのような問題で汎用アルゴリズムを活用する必要がある。そうした汎用アルゴリズムに向いた問題を探し出すために、NTTデータと広島大学はアダプティブ・バルク・サーチの実行環境を一般に公開した。