最高提速1440倍！15秒用GCN搞定隨機(jī)規(guī)劃，中科院自動(dòng)化所新成果入選ICML 24
同樣效果傳統(tǒng)算法要算6個(gè)小時(shí)
中科院自動(dòng)化研究所 投稿
量子位 | 公眾號 QbitAI
僅需15秒即可搞定隨機(jī)規(guī)劃問題，速度比傳統(tǒng)方法快了1440倍！
中科院自動(dòng)化研究所的新研究，利用GCN在此類問題上取得了新突破，論文已入選AI頂會(huì)ICML 2024。
這意味著，在條件不確定的情況下，也能實(shí)現(xiàn)高效決策。
不確定性下的決策是一類重要的決策問題，它要求決策者能夠充分考慮到所有的隨機(jī)情況并做出最合理的決策。
在數(shù)學(xué)領(lǐng)域，一種常用的解決方式是隨機(jī)規(guī)劃，也就是把隨機(jī)變量包含在數(shù)學(xué)規(guī)劃模型當(dāng)中。
其中，兩階段隨機(jī)規(guī)劃（Two-Stage Stochastic Programming, 2SP）作為建模此類決策問題的有效方法，應(yīng)用十分廣泛。
中科院自動(dòng)化所的這項(xiàng)成果——HGCN2SP模型（HGCN代表分層圖卷積網(wǎng)絡(luò)），正是將2SP方法與圖卷積網(wǎng)絡(luò)結(jié)合，利用模型更高效地實(shí)現(xiàn)了此類問題求解。
論文第一作者為該所博士生吳洋，張一帆研究員是通訊作者。
什么是兩階段隨機(jī)規(guī)劃
隨機(jī)規(guī)劃的基本思想是將問題的未來可能情況轉(zhuǎn)化為若干個(gè)樣本場景，然后對每個(gè)樣本場景進(jìn)行優(yōu)化，最后綜合所有場景的優(yōu)化結(jié)果來指導(dǎo)當(dāng)前決策。
其應(yīng)用領(lǐng)域包括供應(yīng)鏈管理、金融投資、能源調(diào)度、災(zāi)害應(yīng)急管理等。
而兩階段隨機(jī)規(guī)劃，顧名思義就是把這個(gè)過程分成了兩個(gè)階段。
具體來說，這兩個(gè)階段分別要做出宏觀和微觀決策，以最小化總成本或最大化總收益。
第一階段的決策是在不確定性顯現(xiàn)之前做出的，目標(biāo)是優(yōu)化初始決策以適應(yīng)未來可能發(fā)生的多種情況。
第二階段的決策是在不確定性顯現(xiàn)之后進(jìn)行的，根據(jù)第一階段的決策和實(shí)際發(fā)生的情況進(jìn)行調(diào)整，以優(yōu)化整體結(jié)果。
通過2SP模型，決策者需要在決策過程中充分考慮可能發(fā)生的不同場景的影響，從而提高決策的魯棒性和靈活性，做出更為科學(xué)和高效的決策。
舉個(gè)例子，假設(shè)我們要從10個(gè)候選地點(diǎn)中選擇一些建立倉庫，以滿足周邊20個(gè)區(qū)域的需求。
第一階段需要決策的是，在這10個(gè)候選地點(diǎn)中應(yīng)該選擇哪些；
第二階段則要確定倉庫和區(qū)域間的配送關(guān)系，此時(shí)的決策變量數(shù)量多達(dá)200個(gè)（即倉庫i是否配送區(qū)域j）。
△圖像由DALL·E生成
數(shù)學(xué)上，2SP問題通常表示為：
其中，Q(x,ξ)表示在給定第一階段決策x和場景ξ下的第二階段優(yōu)化問題，其形式為：
在實(shí)際的求解中，一般會(huì)采樣N個(gè)場景計(jì)算對應(yīng)的Q值來近似期望。
顯然N越大則近似值越可信，但隨著場景數(shù)量的增加，問題規(guī)模迅速膨脹，會(huì)導(dǎo)致求解時(shí)間大幅提高。
還是用這個(gè)倉庫選址的問題來說明，為了能做出更好的選址決策，需要將需求、天氣、人流、交通等不確定因素考慮在內(nèi)，而每一個(gè)因素的變化都對應(yīng)著一個(gè)場景。
這意味著，需要廣泛采樣N個(gè)不同場景來盡可能模擬真實(shí)情況。這時(shí)，第二階段總決策變量數(shù)會(huì)高達(dá)200N個(gè)，使得求解時(shí)間極為漫長。
事實(shí)上，當(dāng)N取500時(shí)，即使使用最先進(jìn)的商用求解器Gurobi，也至少需要6個(gè)小時(shí)才能做出最優(yōu)的決策。
傳統(tǒng)方法通常利用隨機(jī)采樣或聚類技術(shù)來挑選少量的場景（如10或20）以進(jìn)行近似求解，雖然減少了時(shí)間，但得到的決策質(zhì)量卻往往不理想。
基于此，也就有了HGCN2SP模型的設(shè)計(jì)思路——在減少采樣場景個(gè)數(shù)的同時(shí)，盡可能近似得到準(zhǔn)確結(jié)果。
用圖卷積網(wǎng)絡(luò)解決2SP問題
研究團(tuán)隊(duì)針對兩階段隨機(jī)規(guī)劃問題求解，提出了基于層次化圖卷積網(wǎng)絡(luò)的HGCN2SP模型。
具體的在算法設(shè)計(jì)方面，團(tuán)隊(duì)通過構(gòu)建層次圖來表征2SP問題，其中底層的圖用來表征每個(gè)場景的特性，而頂層的圖則用于表征場景之間的關(guān)系。
然后，再利用層次化圖卷積網(wǎng)絡(luò)（HGCN），分別挖掘底層場景子圖的嵌入信息和頂層場景空間的結(jié)構(gòu)信息，以提取場景表示。
基于注意力機(jī)制的解碼器被用于按序挑選場景，不僅能找到具有代表性的場景來簡化問題，還可以通過優(yōu)化場景的排列順序來改善單純形法求解問題時(shí)對初始基的選取，進(jìn)而顯著提升求解時(shí)間。
△HGCN2SP模型框架
團(tuán)隊(duì)還結(jié)合強(qiáng)化學(xué)習(xí)（RL），綜合考察決策質(zhì)量和求解時(shí)間來優(yōu)化模型參數(shù)，顯著提高了問題求解的效率和質(zhì)量。
在上述的倉庫選址問題中，盡管HGCN2SP只選取了10個(gè)場景，但其決策結(jié)果與Gurobi求解器用6個(gè)小時(shí)做出的決策差距僅為1.7%，而求解時(shí)間僅為15秒，相當(dāng)于速度提升了1440倍，充分體現(xiàn)了該方法的有效性。
另外，在網(wǎng)絡(luò)設(shè)計(jì)問題（Network Design Problem, NDP）的實(shí)驗(yàn)中，HGCN2SP僅用已有方法不到一半的時(shí)間得到了相近的決策效果。
尤其在大規(guī)模實(shí)例和大量場景情況下，HGCN2SP依然保持了強(qiáng)大的泛化能力。
HGCN2SP的提出為解決復(fù)雜的2SP問題提供了一種新的思路和工具，具有廣泛的應(yīng)用前景。
研究團(tuán)隊(duì)計(jì)劃進(jìn)一步優(yōu)化模型，降低訓(xùn)練成本，并探索其在更多實(shí)際問題中的應(yīng)用。
論文地址：
https://openreview.net/forum?id=8onaVSFTEj
相關(guān)閱讀
