基于昇騰算力的矩陣運(yùn)算改進(jìn)求解器框架,大幅提升Local Optimum跳出能力。 深圳市大數(shù)據(jù)研究院與華為GTS運(yùn)籌優(yōu)化實(shí)驗(yàn)室聯(lián)合提出基于矩陣運(yùn)算的Memetic&LNS求解技術(shù)。 結(jié)果刷新了Sartori&Burial PDPTW榜單中的57項(xiàng)世界紀(jì)錄,在部分算例上相對于基準(zhǔn)結(jié)果改進(jìn)幅度達(dá)6%,是繼英偉達(dá)cuOPT刷新Li&Lim 23項(xiàng)基準(zhǔn)記錄后,基于NPU/GPU算力AI求解的另一技術(shù)突破。 其中,基于昇騰加速,最快可加速100倍,達(dá)到在搜索范圍大幅提升的同時,保證性能也不受影響。 矩陣化改進(jìn)傳統(tǒng)求解框架 帶時間窗口的取貨和配送問題(PDPTW)是路徑優(yōu)化問題(VRP)的重要變體,是一類非常經(jīng)典的強(qiáng)組合優(yōu)化難題,在供應(yīng)鏈、物流、網(wǎng)絡(luò)規(guī)劃調(diào)度等領(lǐng)域有廣泛的應(yīng)用。 該問題中,每個請求指定了要運(yùn)輸?shù)呢浳锏拇笮∫约皟蓚位置:裝貨點(diǎn)和卸貨點(diǎn)。此類問題的主要目標(biāo)是最小化總成本,包括車輛固定成本和行駛成本,同時確保滿足所有客戶的需求。 PDPTW的復(fù)雜性主要來源于極大的求解空間和時間窗約束&取送貨配對約束&容量限制等約束的交織,這類問題很難使用精確算法來解決大型問題,在當(dāng)前學(xué)/業(yè)界,一類經(jīng)典標(biāo)桿為Memetic&LNS的融合求解技術(shù),其算法框架如下: Memetic&LNS可以在很多組合優(yōu)化難題取得很好平均效果,然后如何有效跳出Local Optimum仍然是這類算法的一大局限性,搜索過程的早期可能會達(dá)到了一個相對較好的解,后續(xù)的搜索過程停滯不前,無法進(jìn)一步改進(jìn),收斂到局部最優(yōu)。 為了解決該難題,研究團(tuán)隊設(shè)計并實(shí)現(xiàn)了一種創(chuàng)新性的技術(shù)框架。 首先,對傳統(tǒng)的求解架構(gòu)進(jìn)行調(diào)整,在路徑生成的時候采取更大范圍搜索策略,提升跳出Local Optimum概率; 其次,引入SPP子模型提升每一代solution質(zhì)量。與此同時,路徑評估和SPP求解也進(jìn)行矩陣化轉(zhuǎn)化,基于昇騰加速,最快可加速100倍,達(dá)到在搜索范圍大幅提升的同時,保證性能也不受影響,極大地提升了跳出Local Optimum的能力。 矩陣化可行性和目標(biāo)函數(shù)評估,NPU加速極大提升路徑探索能力 該研究團(tuán)隊提出的最新算法框架,專門為高耗時的路徑和解評估設(shè)計了一項(xiàng)創(chuàng)新技術(shù),核心思路是將傳統(tǒng)可行性和成本評估轉(zhuǎn)化成矩陣運(yùn)算,并調(diào)用昇騰NPU算子,從而實(shí)現(xiàn)路徑和解的高效評估,如下圖所示,將solution、距離、時間等屬性矩陣化。 距離的評估: Capacity約束的違反度評估 時間窗約束的違反度評估 通過以上技術(shù)能夠?qū)鹘y(tǒng)約束可行性、目標(biāo)評估等高耗時環(huán)節(jié)極大的加速,部分可達(dá)100倍加速比,極大地提升了路徑探索能力。 引入SPP子模型,NPU加速搜索高質(zhì)量路徑組合,提升每一代solution質(zhì)量 為了更好的提升每一代solution的質(zhì)量,該研究團(tuán)隊設(shè)計引入一種高效的面向集合劃分子模型(Set Partitioning Problem, SPP),搜索路徑組合,提升子代solution質(zhì)量,同時將傳統(tǒng)SPP的求解過程轉(zhuǎn)化為矩陣運(yùn)算,利用NPU的強(qiáng)大算力實(shí)現(xiàn)了顯著的加速效果,提升每一代迭代效率,下面是算法的核心思路: 為了矩陣化上述的組合操作,該團(tuán)隊將該問題的屬性建立成一個0、1矩陣,其中0表示節(jié)點(diǎn)不在該路徑上,1表示點(diǎn)在該路徑上,如下圖所示, 此過程中還參考分支定界算法中基于bound的剪枝思路,引入多個昇騰算子實(shí)現(xiàn)了帶約束的組合能力。 基于NPU算力,SPP的求解相比傳統(tǒng)求解器方法,求解速度提升60+倍。該技術(shù)可以快速求解得到最優(yōu)解,更高性能搜索高質(zhì)量solution。 最終效果 該研究團(tuán)隊在公開數(shù)據(jù)集(由 Sartori 和 Buriol 于 2020 年提出,基于實(shí)際工業(yè)場景的數(shù)據(jù)集)上對所提出的技術(shù)進(jìn)行了全面的實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)結(jié)果顯示,這一方法在多個算例中實(shí)現(xiàn)了顯著的性能提升,共刷新了榜單中的57項(xiàng)世界紀(jì)錄,在部分算例上相對于基準(zhǔn)結(jié)果改進(jìn)幅度達(dá)6%。 榜單鏈接: https://github.com/cssartori/pdptw-instances/tree/master/solutions 本文來源:量子位 |
原創(chuàng)欄目
IT百科
網(wǎng)友評論
聚超值•精選