首頁(yè) > 科技要聞 > 科技> 正文

基于昇騰算力突破AI求解，最高加速100倍！

量子位 整合編輯：太平洋科技 發(fā)布于：2024-12-17 15:10

基于昇騰算力的矩陣運(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ì)錄，在部分算例上相對(duì)于基準(zhǔn)結(jié)果改進(jìn)幅度達(dá)6%，是繼英偉達(dá)cuOPT刷新Li&Lim 23項(xiàng)基準(zhǔn)記錄后，基于NPU/GPU算力AI求解的另一技術(shù)突破。

其中，基于昇騰加速，最快可加速100倍，達(dá)到在搜索范圍大幅提升的同時(shí)，保證性能也不受影響。

矩陣化改進(jìn)傳統(tǒng)求解框架

帶時(shí)間窗口的取貨和配送問(wèn)題（PDPTW）是路徑優(yōu)化問(wèn)題（VRP）的重要變體，是一類非常經(jīng)典的強(qiáng)組合優(yōu)化難題，在供應(yīng)鏈、物流、網(wǎng)絡(luò)規(guī)劃調(diào)度等領(lǐng)域有廣泛的應(yīng)用。

該問(wèn)題中，每個(gè)請(qǐng)求指定了要運(yùn)輸?shù)呢浳锏拇笮∫约皟蓚�(gè)位置：裝貨點(diǎn)和卸貨點(diǎn)。此類問(wèn)題的主要目標(biāo)是最小化總成本，包括車輛固定成本和行駛成本，同時(shí)確保滿足所有客戶的需求。

PDPTW的復(fù)雜性主要來(lái)源于極大的求解空間和時(shí)間窗約束&取送貨配對(duì)約束&容量限制等約束的交織，這類問(wèn)題很難使用精確算法來(lái)解決大型問(wèn)題，在當(dāng)前學(xué)/業(yè)界，一類經(jīng)典標(biāo)桿為Memetic&LNS的融合求解技術(shù)，其算法框架如下：

Memetic&LNS可以在很多組合優(yōu)化難題取得很好平均效果，然后如何有效跳出Local Optimum仍然是這類算法的一大局限性，搜索過(guò)程的早期可能會(huì)達(dá)到了一個(gè)相對(duì)較好的解，后續(xù)的搜索過(guò)程停滯不前，無(wú)法進(jìn)一步改進(jìn)，收斂到局部最優(yōu)。

為了解決該難題，研究團(tuán)隊(duì)設(shè)計(jì)并實(shí)現(xiàn)了一種創(chuàng)新性的技術(shù)框架。

首先，對(duì)傳統(tǒng)的求解架構(gòu)進(jìn)行調(diào)整，在路徑生成的時(shí)候采取更大范圍搜索策略，提升跳出Local Optimum概率；

其次，引入SPP子模型提升每一代solution質(zhì)量。與此同時(shí)，路徑評(píng)估和SPP求解也進(jìn)行矩陣化轉(zhuǎn)化，基于昇騰加速，最快可加速100倍，達(dá)到在搜索范圍大幅提升的同時(shí)，保證性能也不受影響，極大地提升了跳出Local Optimum的能力。

矩陣化可行性和目標(biāo)函數(shù)評(píng)估，NPU加速極大提升路徑探索能力

該研究團(tuán)隊(duì)提出的最新算法框架，專門為高耗時(shí)的路徑和解評(píng)估設(shè)計(jì)了一項(xiàng)創(chuàng)新技術(shù)，核心思路是將傳統(tǒng)可行性和成本評(píng)估轉(zhuǎn)化成矩陣運(yùn)算，并調(diào)用昇騰NPU算子，從而實(shí)現(xiàn)路徑和解的高效評(píng)估，如下圖所示，將solution、距離、時(shí)間等屬性矩陣化。

距離的評(píng)估：

Capacity約束的違反度評(píng)估

時(shí)間窗約束的違反度評(píng)估

通過(guò)以上技術(shù)能夠?qū)鹘y(tǒng)約束可行性、目標(biāo)評(píng)估等高耗時(shí)環(huán)節(jié)極大的加速，部分可達(dá)100倍加速比，極大地提升了路徑探索能力。

引入SPP子模型，NPU加速搜索高質(zhì)量路徑組合，提升每一代solution質(zhì)量

為了更好的提升每一代solution的質(zhì)量，該研究團(tuán)隊(duì)設(shè)計(jì)引入一種高效的面向集合劃分子模型（Set Partitioning Problem, SPP），搜索路徑組合，提升子代solution質(zhì)量，同時(shí)將傳統(tǒng)SPP的求解過(guò)程轉(zhuǎn)化為矩陣運(yùn)算，利用NPU的強(qiáng)大算力實(shí)現(xiàn)了顯著的加速效果，提升每一代迭代效率，下面是算法的核心思路：

為了矩陣化上述的組合操作，該團(tuán)隊(duì)將該問(wèn)題的屬性建立成一個(gè)0、1矩陣，其中0表示節(jié)點(diǎn)不在該路徑上，1表示點(diǎn)在該路徑上，如下圖所示，

此過(guò)程中還參考分支定界算法中基于bound的剪枝思路，引入多個(gè)昇騰算子實(shí)現(xiàn)了帶約束的組合能力。

基于NPU算力，SPP的求解相比傳統(tǒng)求解器方法，求解速度提升60+倍。該技術(shù)可以快速求解得到最優(yōu)解，更高性能搜索高質(zhì)量solution。

最終效果

該研究團(tuán)隊(duì)在公開數(shù)據(jù)集（由 Sartori 和 Buriol 于 2020 年提出，基于實(shí)際工業(yè)場(chǎng)景的數(shù)據(jù)集）上對(duì)所提出的技術(shù)進(jìn)行了全面的實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)結(jié)果顯示，這一方法在多個(gè)算例中實(shí)現(xiàn)了顯著的性能提升，共刷新了榜單中的57項(xiàng)世界紀(jì)錄，在部分算例上相對(duì)于基準(zhǔn)結(jié)果改進(jìn)幅度達(dá)6%。

榜單鏈接： https://github.com/cssartori/pdptw-instances/tree/master/solutions

本文來(lái)源：量子位

網(wǎng)友評(píng)論

聚超值•精選

推薦 手機(jī) 筆記本 影像 硬件 家居 商用 企業(yè) 出行 未來(lái)
    • 二維碼 回到頂部