近日，華為云企業(yè)智能(EI)創(chuàng)新孵化實(shí)驗(yàn)室OROAS與華為諾亞決策推理實(shí)驗(yàn)室聯(lián)合團(tuán)隊(duì)(以下簡(jiǎn)稱“華為聯(lián)合團(tuán)隊(duì)”)參加了由人工智能頂級(jí)學(xué)術(shù)會(huì)議NeurIPS 2021承辦的Machine Learning for Combinatorial Optimization(ML4CO)競(jìng)賽，并斬獲求解器超參優(yōu)化賽道冠軍，成績(jī)大幅度領(lǐng)先于第二名。

　　該競(jìng)賽聚焦特定問(wèn)題與歷史數(shù)據(jù)信息，與參賽者共同探討如何通過(guò)機(jī)器學(xué)習(xí)方法來(lái)提升求解器的性能。在華為供應(yīng)鏈算法工作組的支持下，華為聯(lián)合團(tuán)隊(duì)針對(duì)“增強(qiáng)通用求解器在特定混合整數(shù)規(guī)劃(MIP)問(wèn)題上的求解性能”，提出了離線參數(shù)整定、在線參數(shù)推薦兩大解決方案，在三類問(wèn)題上均實(shí)現(xiàn)了最佳性能。華為聯(lián)合團(tuán)隊(duì)在本次賽事中沉淀的技術(shù)將對(duì)幫助行業(yè)客戶高效計(jì)算最優(yōu)方案、提升資源利用率和運(yùn)轉(zhuǎn)效率、突破業(yè)界運(yùn)籌優(yōu)化極限有重要意義。

NeurIPS 2021(ML4CO)競(jìng)賽榜單

　　混合整數(shù)規(guī)劃(Mixed Integer Programming, MIP)問(wèn)題(如資源調(diào)度、生產(chǎn)排產(chǎn)、路徑優(yōu)化、運(yùn)營(yíng)管理、研發(fā)設(shè)計(jì)、財(cái)經(jīng)管理等)是企業(yè)運(yùn)籌優(yōu)化時(shí)面臨的最常見(jiàn)的問(wèn)題類型，覆蓋商業(yè)決策優(yōu)化的大部分流程，在求解器應(yīng)用場(chǎng)景中的占比超75%。混合整數(shù)規(guī)劃求解器(MIP Solver)是數(shù)學(xué)規(guī)劃(mathematical programming)算法的集大成者，內(nèi)嵌原/對(duì)偶單純形、內(nèi)點(diǎn)法等線性規(guī)劃(LP)算法、分支定界算法、各類割平面算法、各類原啟發(fā)算法、各類預(yù)處理算法、各類域傳播算法等。這些算法在MIP求解器內(nèi)的實(shí)現(xiàn)涉及到大量超參數(shù)，如開(kāi)源MIP求解器中性能最為強(qiáng)勁的SCIP求解器提供了2617個(gè)超參數(shù)，其中超過(guò)2000個(gè)超參數(shù)與求解過(guò)程中的決策強(qiáng)相關(guān)。

　　通常，這些超參數(shù)由求解器開(kāi)發(fā)者依據(jù)人工經(jīng)驗(yàn)整定，面向通用問(wèn)題提供一套適用性最為廣泛的參數(shù)作為默認(rèn)值。但面向細(xì)分行業(yè)特定場(chǎng)景，首先，默認(rèn)參數(shù)難以發(fā)揮求解器的最佳性能。第二，求解器使用門檻相對(duì)較高，要求用戶對(duì)組合優(yōu)化、數(shù)學(xué)規(guī)劃算法和場(chǎng)景問(wèn)題本身有較為深入的理解。第三，即使是行業(yè)領(lǐng)域的專家，在求解器的海量參數(shù)組合中為特定場(chǎng)景問(wèn)題選擇最佳參數(shù)的過(guò)程中，也存在著人工調(diào)參耗時(shí)耗力的挑戰(zhàn)。

　　NeurIPS 2021(ML4CO)競(jìng)賽的超參優(yōu)化賽道直面上述痛點(diǎn)，號(hào)召全球研究者探索機(jī)器學(xué)習(xí)在求解器參數(shù)整定、參數(shù)推薦中的應(yīng)用，以“多維背包問(wèn)題、流量均衡問(wèn)題、面向?qū)嶋H問(wèn)題且包含多種類型問(wèn)題的匿名問(wèn)題集”為研究對(duì)象，征集SCIP求解器的最佳參數(shù)推薦方案，從而幫助提升通用求解器在細(xì)分行業(yè)特定場(chǎng)景問(wèn)題上的性能。

　　華為聯(lián)合團(tuán)隊(duì)認(rèn)為該任務(wù)可被解耦為“離線參數(shù)整定”與“在線參數(shù)推薦”兩個(gè)步驟。“離線參數(shù)整定”步驟是針對(duì)每一類同質(zhì)問(wèn)題整定出一套最佳性能的參數(shù)，即調(diào)參;“在線參數(shù)推薦”步驟是訓(xùn)練一個(gè)機(jī)器學(xué)習(xí)模型來(lái)完成從問(wèn)題用例特征到問(wèn)題用例類別的映射關(guān)系學(xué)習(xí)，即匹配。兩個(gè)步驟的關(guān)系如下圖所示：

　　華為聯(lián)合團(tuán)隊(duì)在NeurIPS 2021(ML4CO)競(jìng)賽中提出兩大解決方案

　　應(yīng)用“離線參數(shù)整定”技術(shù)，實(shí)現(xiàn)綜合BO調(diào)參

　　求解器調(diào)參是一類“單次性能評(píng)估的時(shí)間、資源代價(jià)昂貴”的黑箱優(yōu)化問(wèn)題。針對(duì)這一類問(wèn)題的常用技術(shù)方案是貝葉斯優(yōu)化(Bayesian Optimization，BO)，但將該技術(shù)直接落地應(yīng)用于求解器調(diào)參面臨以下三方面的挑戰(zhàn)：

　　l 參數(shù)空間規(guī)模大。參數(shù)空間的規(guī)模與參數(shù)維數(shù)構(gòu)成指數(shù)關(guān)系，即存在維數(shù)災(zāi)問(wèn)題。常規(guī)的BO方法通常適用于參數(shù)維數(shù)在30維以內(nèi)的問(wèn)題，如神經(jīng)網(wǎng)絡(luò)調(diào)參。面對(duì)2000多維的求解器參數(shù)空間，百余次BO采樣如在浩渺宇宙中探索地球，難以建立起有效的代理模型。

　　l 參數(shù)依賴關(guān)系強(qiáng)。常規(guī)的調(diào)參問(wèn)題中，各維度上的參數(shù)相互獨(dú)立，構(gòu)成正交的參數(shù)空間;而求解器參數(shù)構(gòu)成樹(shù)狀空間，子級(jí)參數(shù)的作用依賴于父級(jí)參數(shù)的狀態(tài)，如原啟發(fā)的優(yōu)先級(jí)參數(shù)依賴于其開(kāi)關(guān)參數(shù)。若忽視這種層級(jí)關(guān)系則會(huì)產(chǎn)生大量無(wú)效采樣，甚至引入觀測(cè)噪聲。

　　l 參數(shù)性能分布正偏。求解器在不同參數(shù)上的性能分布呈現(xiàn)出正偏趨勢(shì)，即好參數(shù)帶來(lái)的性能提升幅度遠(yuǎn)小于壞參數(shù)帶來(lái)的性能惡化幅度，進(jìn)而在隨機(jī)種子引起的觀測(cè)噪聲上表現(xiàn)出較顯著的異方差特性，不符合高斯過(guò)程代理模型的前提假設(shè)，最終影響了代理模型的擬合效果。

　　針對(duì)上述挑戰(zhàn)，華為聯(lián)合團(tuán)隊(duì)整合了在華為供應(yīng)鏈供需雙向模擬和多工廠排產(chǎn)引擎等實(shí)際場(chǎng)景積累的多項(xiàng)關(guān)鍵技術(shù)，形成了一套面向求解器參數(shù)整定場(chǎng)景的綜合BO調(diào)參解決方案。

　　首先，依據(jù)團(tuán)隊(duì)內(nèi)華為云天籌(OptVerse)AI求解器開(kāi)發(fā)者的專家經(jīng)驗(yàn)，并結(jié)合XGBoost擬合隨機(jī)觀測(cè)的參數(shù)-性能對(duì)的代理模型所得到的Gini系數(shù)信息，完成海量參數(shù)的預(yù)篩選，實(shí)現(xiàn)關(guān)鍵參數(shù)辨識(shí)目的。

　　然后，從參數(shù)類型、參數(shù)作用、依賴關(guān)系等多個(gè)維度對(duì)這些關(guān)鍵參數(shù)進(jìn)行分層組合，將高維正交的參數(shù)空間轉(zhuǎn)換為若干低維樹(shù)狀參數(shù)空間的嵌入。在每個(gè)參數(shù)子空間的BO搜索中，首先對(duì)已觀測(cè)樣本應(yīng)用Box-Cox Transform實(shí)現(xiàn)自適應(yīng)分布變換，解決偏態(tài)分布中潛在的異方差問(wèn)題;在擬合代理模型環(huán)節(jié)，基于集成學(xué)習(xí)思想，使用高斯過(guò)程、隨機(jī)森林等方法，實(shí)現(xiàn)廣泛參數(shù)類型下的精準(zhǔn)擬合;在采集函數(shù)優(yōu)化環(huán)節(jié)，打破常規(guī)BO實(shí)現(xiàn)中單一采集函數(shù)的限制，集成UCB、PI、EI等多種采集函數(shù)進(jìn)行多目標(biāo)優(yōu)化，并從Pareto前沿中采樣推薦參數(shù)，實(shí)現(xiàn)期望與方差的更優(yōu)平衡。

　　基于“在線參數(shù)推薦”，完成從特征到類別的映射關(guān)系學(xué)習(xí)

　　對(duì)已知樣本的精確類別劃分與匹配是為未知樣本推薦正確參數(shù)的先決條件。華為聯(lián)合團(tuán)隊(duì)基于天籌AI求解器開(kāi)發(fā)的技術(shù)積累，從MIP問(wèn)題用例中抽取出上百個(gè)參數(shù)特征，并結(jié)合MIP問(wèn)題三部圖的圖卷積特征，建立起MIP問(wèn)題的精確畫(huà)像。基于這些特征，應(yīng)用無(wú)監(jiān)督學(xué)習(xí)方法對(duì)匿名數(shù)據(jù)集實(shí)現(xiàn)類別劃分，進(jìn)一步結(jié)合賽方完全公開(kāi)的Item Placement和Load Balancing數(shù)據(jù)集，為訓(xùn)練問(wèn)題類別匹配模型提供海量有效樣本。最后執(zhí)深度學(xué)習(xí)方法之矛，實(shí)現(xiàn)MIP問(wèn)題從用例到類別再到參數(shù)的準(zhǔn)確映射。

　　根據(jù)NeurIPS 2021(ML4CO)競(jìng)賽主辦方公布的榜單結(jié)果所示，SCIP求解器的默認(rèn)參數(shù)在Item Placement和Load Balancing兩個(gè)非匿名數(shù)據(jù)集上的平均性能指標(biāo)分別約為17000和25000。華為聯(lián)合團(tuán)隊(duì)推薦的參數(shù)性能指標(biāo)則分別達(dá)到了8741和7856，性能提升幅度分別達(dá)到了2倍和3倍。

　　華為云一站式AI開(kāi)發(fā)平臺(tái)ModelArts為“離線參數(shù)整定”和“在線參數(shù)推薦”技術(shù)方案的實(shí)現(xiàn)提供了強(qiáng)有力的軟、硬件支持：ModelArts為華為聯(lián)合團(tuán)隊(duì)提供了高效、穩(wěn)定的大規(guī)模服務(wù)器集群、千余顆CPU核心與TB級(jí)內(nèi)存，保證了大量MIP用例的并行性能評(píng)估;此外，ModelArts預(yù)置的主流機(jī)器學(xué)習(xí)框架與便捷靈活的自定義鏡像環(huán)境極大地加速了上述方案的部署與落地。

　　當(dāng)前，運(yùn)籌優(yōu)化技術(shù)已在華為供應(yīng)鏈多工廠排產(chǎn)引擎等多個(gè)場(chǎng)景落地，不僅幫助實(shí)現(xiàn)系統(tǒng)底層完全自研，而且實(shí)現(xiàn)了分工廠計(jì)劃準(zhǔn)確率、回流調(diào)撥比例、計(jì)劃自動(dòng)執(zhí)行比例等一系列業(yè)務(wù)關(guān)鍵指標(biāo)的顯著提升，并大幅提高了業(yè)務(wù)的作業(yè)效率。同時(shí)，華為聯(lián)合團(tuán)隊(duì)在比賽當(dāng)中突破的前沿技術(shù)及求解能力也已集成在天籌AI求解器和ModelArts等華為云AI服務(wù)中，并計(jì)劃對(duì)外開(kāi)放給更多AI開(kāi)發(fā)者使用。

　　未來(lái)，華為聯(lián)合團(tuán)隊(duì)將持續(xù)優(yōu)化天籌AI求解器中的MIP求解性能，面向不同的業(yè)務(wù)場(chǎng)景，不斷創(chuàng)造更大價(jià)值。