中国科学院オートメーション研究所による寄稿

パブリックアカウント QbitAI

確率的計画問題を解くのにかかる時間はわずか 15 秒で、これは従来の方法よりも 1440 倍高速です。

中国科学院オートメーション研究所の新しい研究では、GCN を使用してこのような問題の新たなブレークスルーを達成しました。この論文は、AI のトップカンファレンスである ICML 2024 に選ばれました。

これは、不確実な状況下でも効率的な意思決定が可能であることを意味します。

不確実性の下での意思決定は、意思決定の問題の重要なタイプであり、意思決定者はあらゆるランダムな状況を十分に考慮し、最も合理的な決定を下す必要があります。

数学の分野では、一般的に使用される解決策は確率的計画法です。これには、数理計画法モデルに確率変数が含まれます。

中でも、二段階確率計画法 (2SP) は、このような意思決定の問題をモデル化するのに効果的な手法であり、広く使用されています。

中国科学院オートメーション研究所のこの成果である HGCN2SP モデル (HGCN は Hierarchical Graph Convolution Network の略) は、まさに 2SP 手法と写真このモデルを畳み込みネットワークと組み合わせると、このような問題をより効率的に解決するために使用できます。

論文の筆頭著者は同研究所の博士課程学生であるウー・ヤン氏で、研究者のチャン・イーファン氏が責任著者となっている。

2段階確率計画法とは何ですか?

確率的計画の基本的な考え方は、問題の起こり得る将来の状況をいくつかのサンプル シナリオに変換し、次に各サンプル シナリオを最適化し、最後にすべてのシナリオの最適化結果を統合して現在の意思決定をガイドすることです。

その応用分野には、サプライチェーン管理、金融投資、エネルギー派遣、災害緊急管理などが含まれます。

2 段階の確率的計画は、その名前が示すように、プロセスを 2 つの段階に分割します。

具体的には、これら 2 つの段階では、総コストを最小化するか、総利益を最大化するために、それぞれマクロとミクロの決定を行う必要があります。

最初の段階での決定は、将来起こり得るさまざまなシナリオに適応するために最初の決定を最適化することを目的として、不確実性が顕在化する前に行われます。

第 2 段階の決定は不確実性が生じた後に行われ、全体的な結果を最適化するために第 1 段階での決定と実際に起こったことに基づいて調整されます。

2SP モデルを通じて、意思決定者は意思決定プロセス中に発生する可能性のあるさまざまなシナリオの影響を十分に考慮する必要があるため、意思決定の堅牢性と柔軟性が向上し、より科学的で効率的な意思決定が可能になります。

たとえば、周囲 20 地域のニーズを満たす倉庫を建設するために 10 の候補地からいくつかを選択するとします。

最初の段階で決定する必要があるのは、これら 10 か所の候補地のうちどれを選択するかです。

第 2 段階では、倉庫と地域の配分関係を決定する必要があります。このとき、決定変数の数は 200 個もあります (つまり、倉庫 i が地域 j に配分されるかどうか)。

△DALL・E生成画像

数学的には、2SP 問題は通常次のように表現されます。

このうち、Q(x,ξ) は、第 1 段階の決定 x とシナリオ ξ が与えられた場合の第 2 段階の最適化問題を表し、その形式は次のとおりです。

実際のソリューションでは、通常、N 個のシーンがサンプリングされ、対応する Q 値が計算され、期待値に近似されます。

明らかに、N が大きいほど近似の信頼性は高くなりますが、シナリオの数が増えると問題のサイズは急速に拡大し、解決時間の大幅な増加につながります。

この倉庫の場所の問題を例にして説明してみましょう。より適切な場所の決定を行うには、需要、天候、人の流れ、交通量などの不確実な要因を考慮する必要があり、各要因の変化はシナリオに対応します。

これは、実際の状況をできるだけ正確にシミュレートするには、N 個の異なるシナリオを幅広くサンプリングする必要があることを意味します。このとき、第 2 段階の決定変数の総数は 200N にもなり、解決時間が非常に長くなります。

実際、N が 500 の場合、最先端の商用ソルバー Gurobi を使用した場合でも、最適な決定を下すには少なくとも 6 時間かかります。

従来の方法では、通常、ランダム サンプリングまたはクラスタリング技術を使用して、少数のシナリオ (10 または 20 など) を選択して近似解を求めます。時間は短縮されますが、結果として得られる決定の品質は理想的ではないことがよくあります。

これに基づいて、サンプリング シーンの数を減らしながら、可能な限り正確な結果を取得するという HGCN2SP モデルの設計思想が導き出されます。

グラフ畳み込みネットワークを使用して 2SP 問題を解決する

研究チームは、2段階の確率計画問題を解決するために、階層グラフ畳み込みネットワークに基づくHGCN2SPモデルを提案しました。

具体的には、アルゴリズム設計の観点から、チームは階層グラフを構築することによって 2SP 問題を特徴づけました。このグラフでは、下のグラフが各シーンの特性を表すために使用され、上のグラフがシーン間の関係を表すために使用されました。

次に、階層グラフ畳み込みネットワーク (HGCN) を使用して、基礎となるシーンのサブグラフの埋め込み情報とトップレベルのシーン空間の構造情報をマイニングし、シーン表現を抽出します。

アテンションメカニズムに基づくデコーダは、シーンを順番に選択するために使用され、問題を単純化するために代表的なシーンを見つけるだけでなく、シンプレックス法で問題を解くときの順序を最適化することにより、最初のベースの選択を改善します。シーンの解決時間を大幅に短縮します。

△HGCN2SPモデルフレームワーク

また、チームは強化学習 (RL) を組み合わせて意思決定の品質と解決時間を包括的に調査し、モデル パラメーターを最適化し、問題解決の効率と品質を大幅に向上させました。

上記の倉庫位置問題では、HGCN2SP は 10 個のシナリオしか選択しませんでしたが、その決定結果と、Gurobi ソルバーが 6 時間で下した決定との差はわずか 1.7% であり、解決時間はわずか 15 秒であり、速度と同等です。改善率は 1440 倍であり、この方法の有効性が十分に反映されています。

さらに、ネットワーク設計問題 (NDP) の実験において、HGCN2SP は既存の手法の半分以下の時間で同様の意思決定効果を達成しました。

特に大規模なインスタンスや多数のシナリオにおいて、HGCN2SP は強力な汎用化機能を維持します。

HGCN2SP の提案は、複雑な 2SP 問題を解決するための新しいアイデアとツールを提供し、幅広い応用の可能性を秘めています。

研究チームは、モデルをさらに最適化し、トレーニングコストを削減し、より現実的な問題への応用を検討する予定です。

用紙のアドレス:
https://openreview.net/forum?id=8onaVSFTEj