ハーバード大が最適化アルゴリズムを指数関数的に高速化！タクシーの配送計画を6倍速で生成

セールスマンが複数の都市を1回だけ巡回する際の最短経路を計算する「巡回サラリーマン問題」では、一つひとつの都市について最適経路を求めるため、都市の数が増すほど、計算コストが膨大になっていく。

同じように、最適化問題を解決するために設計された多くのアルゴリズムは、ステップバイステップで処理を進めるため、データ量が増すほど計算コストも増す。つまり、処理が最適解のステップに近づくほど、要するコストの割にプラスして得られる恩恵も少なくなっていく。

そこでハーバード大学の研究者らは、計算の精度の犠牲は最小限にとどめたまま、ステップ数を削減。指数関数的に計算を高速化するアルゴリズムを開発した。

新しいアルゴリズムは、配車サービスの配送計画やレコメンデーションに活用でき、計算時間を劇的に短縮する可能性があるという。

・レコメンドエンジンや配送計画システムを高速化

ニューヨークのタクシー会社やリムジン会社による200万組の走行データセットを使用して、従来のアルゴリズムより6倍速く最大の潜在顧客数をカバーするのに最適な待機スポットを選択できた。

さらに、映画のレコメンド機能に関する実験では、6000人のユーザーから4000万本の映画を1万回評価。計算時間わずか20分で最先端のアルゴリズムと同等の精度を実現している。

従来の最適化アルゴリズムでは、単一方向にステップバイステップで進行することによって問題を解決するが、新しいアルゴリズムでは、さまざまな方向に並行して処理を走らせていく。

これにより、最適解を得るための最も重要な方向を探り不要な方向は破棄していくことで、処理ステップ数の削減につなげる。

・機械学習を高速化し創薬にも活用へ

同アルゴリズムでは、ターゲットに「曲率」と「均質性」と呼ばれるパラメーターが与えられる。

タクシーの配送計画を求める場合、例えばタクシーが30秒以内に顧客をピックアップできる場所などを設定すれば曲率が高いといえる。ここで、ピックアップ可能な時間の範囲を30秒以内から5分以内に広げれば、曲率が低くなり処理の高速化が計れる。

また均質性については、顧客のいる場所が比較的均等だの前提を設定すれば、均質性が高いことになり、高速な処理が可能になる。

この新しいアプローチは、特定ジャンルにおける機械学習の高速化につながり、薬の飲み合わせによる影響を調べたり、医用画像処理システムを開発したりといった幅広い分野で活用されそうだ。

参照元：New Optimization Algorithm Exponentially Speeds Computation/IEEE Spectrum