確率的計画問題をわずか 15 秒で解決できます。これは従来の方法よりも 1440 倍高速です。

中国科学院自動化研究所の新しい研究では、GCN を使用してこの種の問題に画期的な進歩が達成され、その論文がトップ AI カンファレンス ICML 2024 に選出されました。

つまり、不確実な状況でも効率的な意思決定が可能になります。

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

数学の分野では、この問題を解決するための一般的なアプローチは確率計画法であり、これはランダム変数を数学的計画モデルに組み込むことを伴います。

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

中国科学院自動化研究所によるこの成果である HGCN2SP モデル (HGCN は階層的グラフ畳み込みネットワークの略) は、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?...