求解二維裝箱問題的強化學習啟發(fā)式算法*

陽名鋼,陳夢煩,楊雙遠,張德富

(廈門大學 信息學院,福建 廈門 361005)

二維帶形裝箱問題是指將一組矩形小物品裝入一個具有給定寬度、但是高度無限的矩形箱子中,這些矩形只能按照固定方向放置,不能相互重疊,且必須完全裝入箱子中.問題的目標是使得使用的高度盡可能的低.

二維裝箱問題是經(jīng)典的組合優(yōu)化問題,在各行各業(yè)中都有著非常廣泛的應用.如在石材切割中,物品是小塊的石材,箱子則對應待切割的完整石板,目標是使石材的利用率更高.由于裝箱問題廣泛地存在于各個領域,高效的求解算法有助于公司節(jié)省材料和減少資源浪費,提高生產(chǎn)和工作效率,幫助更合理利用有限的資源.多年來,二維帶形裝箱問題(2DSPP)被眾多國內(nèi)外學者研究以獲得更快更優(yōu)的解決方案.與其他組合優(yōu)化問題一樣,2DSPP 可通過精確算法、近似算法(啟發(fā)式和元啟發(fā)式)或者混合算法等來求解[1].

精確算法可以找到問題的最佳解決方案,但在較大的問題實例上通常需要花費大量的時間.Hifi[2]基于分支定界過程提出了一種精確算法用于解決帶狀切割和包裝問題,該算法在可接受的執(zhí)行時間內(nèi)解決一些中小規(guī)模問題實例.Martello 等人[3]提出了一種新的松弛方法,該方法可產(chǎn)生良好的下界,基于此下界構造出較好的啟發(fā)式算法.Kenmochi 等人[4]設計了一個基于分支規(guī)則和邊界操作的分支定界算法.C?té 等人[5]提出了一種基于Bender 分解的精確算法,該方法可以在有限的計算時間內(nèi)解決中小規(guī)模的基準實例.大多數(shù)精確算法都是基于分支定界策略或者混合整數(shù)線性規(guī)劃,但是因為裝箱問題的復雜性,當問題實例增大的時候,不可避免地導致計算量的指數(shù)級增長,耗時增加.故大部分精確算法僅在小規(guī)模的數(shù)據(jù)集上表現(xiàn)良好,對于解決大規(guī)模的問題實例,更多的研究重點則傾向于使用近似算法來解決.

啟發(fā)式算法雖然無法保證獲得的解是最優(yōu)的,但是它能在合理的時間范圍內(nèi)給出良好的解.啟發(fā)式被認為是解決大規(guī)模組合優(yōu)化問題的有效解決方案,因此在裝箱領域中十分流行.大多數(shù)啟發(fā)式算法都包含構造性過程,即每次將一塊添加到現(xiàn)有的部分解決方案中.1980 年,Baker 等人[6]為了構造合理的裝填順序,就提出了左下(bottom-left,簡稱BL)啟發(fā)式算法.該算法每次取出列表中的第1 個矩形,放入容器最左最低的可用空間.Chazelle等人[7]對BL 算法進行了改進,提出了左下填充算法(BLF).算法首先確定即將被放入的矩形合適的所有位置,然后選擇其中最低位置.Huang 和Liu[8]提出了基于歐氏距離的確定性啟發(fā)式求解算法.Burke 等人[9]提出了最佳填充算法(BF),該算法會動態(tài)地在列表中搜索放入可用空間的最佳候選矩形.Leung 等人[10]提出了適合度策略,該策略用于決定哪個矩形要填充到指定位置.

元啟發(fā)式算法常見的有模擬退火(SA)、遺傳算法(GA)、蟻群算法(AC)和禁忌搜索算法(TS)等,大多數(shù)研究者會結合構造性啟發(fā)式和元啟發(fā)式算法來解決二維帶形裝箱問題.Jakobs[11]在提出的遺傳算法中,使用一個特定的交叉算子和變異算子來交換某些元素的位置,并使用BL 算法解碼解決方案.Hopper 和Turton[12]混合BL 方法與3 種元啟發(fā)算法(遺傳算法(GA)、模擬退火算法(SA)、樸素演化(NE))和局部搜索啟發(fā)式算法.其他作者[13,14]也提出了多種結合遺傳算法的方法來解決2DSPP.He 等人[15]提出了動態(tài)歸約算法求解面積最小的裝箱問題.Wei 等人[16]開發(fā)了一種基于配置文件的構造啟發(fā)式算法的禁忌搜索算法.Alvarez-Valdés[17]提出了一種針對帶狀包裝問題的貪婪隨機自適應搜索程序(GRASP).Zhang 等人[18]提出了基于隨機局部搜索的二分搜索啟發(fā)式算法.Leung 等人[19]提出了兩階段智能搜索算法(ISA),該算法基于簡單的評分規(guī)則選擇矩形放入,該評分策略中設置了5 個分值(0~4).在簡單隨機算法(SRA)[20]中使用了具有8 個分值的評分規(guī)則,并引入了最小浪費優(yōu)先策略.Chen 等人[21]提出了新的算法框架CIBA,提出了角增量的概念,只包含了4 個評分值,用于在選擇矩形的時候評價矩形.Chen 等人[22]基于評分規(guī)則以及角增量的基礎上,再結合分層搜索的思想,提出了一種混合啟發(fā)式算法.這些不同的評分規(guī)則設計的大致思路都是想實現(xiàn)更平坦平滑的布局,以此來減少空間的浪費.值得注意的是: Chen 等人[22]研究了解的不同初始化策略,如貪心策略,最后在6 種貪心策略中選擇最好的初始序列,取得了不錯的效果.

深度學習算法在分類、回歸任務和圖像識別等方面取得了非凡的成功,但是將機器學習用于組合優(yōu)化問題的求解,進展仍然緩慢.1985 年,就有學者在組合優(yōu)化問題中使用神經(jīng)網(wǎng)絡用于優(yōu)化決策,該論文使用Hopfield 網(wǎng)絡解決小規(guī)模的旅行商問題(TSP)[23].組合優(yōu)化問題大部分都是序列的決策問題,例如旅行商問題就是求解訪問城市順序的問題.Vinyals 等人[24]設計了一種非常適合用于求解組合優(yōu)化問題的神經(jīng)網(wǎng)絡,指針網(wǎng)絡(PointerNetwork,Ptr-Net),該模型使用注意力機制[25]作為指針來選擇輸入序列中的某一個元素輸出.作者將該模型應用在解決旅行商問題上.Bello 等人[26]采用了Actor-Critic 算法來訓練Ptr-Net 并在多達100 個節(jié)點的TSP問題上獲得最佳結果.受到Bello 等人[26]工作的啟發(fā),Nazari 等人[27]提出了一個強化學習解決車輛路徑問題的端到端框架,該框架中簡化了指針網(wǎng)絡,采用Actor-Critic 算法訓練模型.Kool 等人[28]提出了基于注意力機制的模型,并用該模型求解了各類型的TSP 和VRP,以及其他組合優(yōu)化問題.Hu 等人[29]提出了新型的3D 裝箱問題,受到深度強化學習(DRL),尤其是指針網(wǎng)絡在組合優(yōu)化問題上的應用啟發(fā),使用DRL 方法來優(yōu)化要裝填的物品的順序,結合啟發(fā)式算法,將網(wǎng)絡的輸出序列轉(zhuǎn)換成解決方案,用于計算獎勵信號,實驗結果優(yōu)于之前精心設計的啟發(fā)式算法.

可以看到,強化學習在組合優(yōu)化問題上的研究和應用處于初步研究階段,性能還不是很好,但是新的思路不斷涌出,研究人員也都在嘗試能設計更好的模型來解決組合優(yōu)化問題.目前,強化學習框架的研究大多只在小規(guī)模的數(shù)據(jù)集上獲得較為良好的解,如果問題規(guī)模增大,信息量爆炸,網(wǎng)絡存儲能力有限,可能無法獲得理想的解.

本文研究了如何利用強化學習來生成一個好的初始解,最終提出了強化學習啟發(fā)式算法,計算結果表明,提出的方法超過了當前最優(yōu)秀的算法.最后,也研究了不同初始化策略的影響.

1 啟發(fā)式算法

由于強化學習需要獎勵機制,本文利用構造性算法獲得的高度作為獎勵機制.矩形的選擇方法是整個構造性啟發(fā)式算法的關鍵.本文采用文獻[22]提出的矩形選擇策略——δ評分規(guī)則.算法1.1 詳細地介紹了基于δ評分規(guī)則和紅黑樹的構造性啟發(fā)式算法的過程.算法中將迭代放置所有的矩形,在每次選擇一個放置空間時,會先判斷放置空間是否可用,否則會進行cave smooth 操作,將不可使用的空間合并到y(tǒng)坐標差異較小的相鄰cave.詳細的構造性啟發(fā)式算法的介紹見文獻[22].

算法1.1.構造性啟發(fā)式算法.

文獻[22]提出的混合啟發(fā)式算法HHA 取得了不錯的結果,但是需要一個好的初始解.本文用強化學習幫助HHA 找到一個更好的初始解.在此給出 HHA 的算法流程,見算法 1.2.其中涉及的函數(shù)如構造性算法ConstructiveHeuristic、分層搜索HierachicalSearch 等,見文獻[22].

算法1.2.HHA 框架.

2 強化學習啟發(fā)式算法

2.1 強化學習求解框架

啟發(fā)式算法通常會存在冷啟動的問題,每次運行算法都需要重新開始緩慢的爬山搜索來尋找最優(yōu)解,無論算法運行過多少次,并不能對后續(xù)的運行和搜索產(chǎn)生任何幫助.傳統(tǒng)的啟發(fā)式算法不存在學習或者保存原先經(jīng)驗的能力,而強化學習則可以做到.強化學習是機器學習的一個重要分支,它的算法框架如圖1 所示:Agent 是智能體,它會根據(jù)所接收的環(huán)境狀態(tài)(state)采取相應的動作(action),環(huán)境會根據(jù)采取動作給予Agent 不同的反饋(reward);然后,Agent 根據(jù)反饋的情況調(diào)整和修正自己的行為.Agent 會反復地與環(huán)境互動進行探索和學習,目的是使獲得的獎勵最大.因此,我們考慮使用強化學習的方法,通過訓練模型來學習裝箱經(jīng)驗,為啟發(fā)式算法尋找一個較優(yōu)的初始序列,從而優(yōu)化冷啟動的問題.那么這就需要一個網(wǎng)絡模型,能夠?qū)W習根據(jù)輸入的物品序列輸出一個初始裝箱序列.

Fig.1 Reinforcement learning graph圖1 強化學習示意圖

指針網(wǎng)絡非常適合解決輸出序列強依賴輸入序列的問題.而二維裝箱問題也可以看成是序列到序列的問題,它的裝箱序列完全來自輸入的物品,因此可以利用指針網(wǎng)絡來學習輸出一個合適的裝箱初始序列.對于訓練好的網(wǎng)絡模型,其優(yōu)勢在于當輸入全新的數(shù)據(jù)時,模型可以根據(jù)學習到的經(jīng)驗給出一個較理想的初始序列,好的初始序列不僅可以加快啟發(fā)式搜索算法的響應速度,還可以節(jié)省爬山消耗的時間,提高算法性能.

2DSPP 主要有兩個決策變量:(1) 矩形物品放入箱子的順序;(2) 物品擺放的位置.算法1.1 可以用于解決輸入物品的序列如何放置物品的問題,而提出的強化學習方法用于優(yōu)化物品的放入順序.

本文提出的框架是使用強化學習訓練好的模型為啟發(fā)式方法提供初始的裝箱序列,改善冷啟動問題.具體的框架圖2 所示.強化學習方法是一種自我學習驅(qū)動的過程,該過程僅依賴輸出序列所計算獲得的獎勵值來訓練網(wǎng)絡.網(wǎng)絡模型(即圖 2 中的 Net)采用簡化版的指針網(wǎng)絡輸出一個初始的裝箱序列,然后調(diào)用ConstructiveHeuristic(即算法1.1)計算該裝箱序列所獲得的解,將該解獲得的高度值作為獎勵信號來驗證網(wǎng)絡的可行性,根據(jù)獎勵值不斷的調(diào)整網(wǎng)絡,使網(wǎng)絡能以最大的概率輸出較好的裝箱序列.訓練好的模型將為HHA提供初始序列,整體的算法本文稱為強化學習啟發(fā)式算法(reinforcement learning heuristic algorithm,簡稱RLHA),詳細的算法流程見算法2.1.

Fig.2 Reinforcement learning heuristic algorithm framework圖2 強化學習啟發(fā)式算法框架

算法2.1.強化學習啟發(fā)式算法.

2.2 網(wǎng)絡模型

網(wǎng)絡模型使用的是簡化版的指針網(wǎng)絡,該模型結構與Nazari 等人[27]使用的結構一致,其框架考慮了靜態(tài)和動態(tài)的元素.針對二維裝箱問題,我們僅考慮了靜態(tài)元素,因為裝箱問題與VRP 不同,2DSPP 不存在動態(tài)的元素,比如VRP 的配送點除了坐標,還有配送點的貨物量,這個值是會動態(tài)改變的.模型由循環(huán)神經(jīng)網(wǎng)絡(GRU)和注意力機制組成,每一步把輸入元素的嵌入(embedding)直接作為解碼器的輸入,解碼器的輸出會傳遞給注意力機制,獲得輸出的概率分布.Nazari 等人[27]認為: 循環(huán)神經(jīng)網(wǎng)絡編碼器增加了額外的復雜性,因為只有當輸入需要傳遞順序信息的時候才需要循環(huán)神經(jīng)網(wǎng)絡.比如文本翻譯,需要知道詞的先后順序才能準確翻譯.但是在組合優(yōu)化中輸入集并沒有順序之說,任何隨機排列都包含與原始輸入相同的信息.因此在簡化版指針網(wǎng)絡中,忽略了編碼器,直接使用了嵌入層(embedding layer)代替編碼器.本文同樣使用了簡化版指針網(wǎng)絡,因為通過這種修改減少了計算的復雜性,提高了性能.

本文的網(wǎng)絡模型如圖3 所示,該模型由兩個部分組成.首先,嵌入層(embedding)對輸入的序列嵌入映射成D維的向量空間,使用的是一維卷積層對輸入進行嵌入;右邊是解碼器保存序列的信息,它將利用注意力機制將解碼器的隱藏狀態(tài)和嵌入的輸入指向一個輸入元素.

Fig.3 Network model圖3 網(wǎng)絡模型示意圖

設輸入集為X={xi,i=1,…,N},其中,xi=(wi,hi)是個元組,表示每個物品的寬度和高度.Xt表示在t時刻所有輸入的狀態(tài)集合.從任意的輸入X0開始,使用指針y0指向該輸入,每一次解碼時刻t,yt+1將指向當前可用的輸入Xt中的一個,并將其作為下一個解碼器的輸入.如此重復,直到所有的序列都被輸出.整個過程將產(chǎn)生一個裝箱序列,高度同輸入相等為N,Y={yt,t=1,…,N}.模型是要找到隨機策略π,使得在滿足問題約束的同時最小化損失目標的方式生成序列Y.我們要做的就是:使得π盡量的接近最優(yōu)解π′,盡量以百分百的概率生成最優(yōu)解.使用概率鏈規(guī)則分解生成序列Y的概率P(Y|X0)表示如下:

在解碼器的每一步,使用注意力機制生成下一個輸入的概率分布.設是嵌入式輸入i,ht是解碼器在t時刻隱藏層的狀態(tài),對齊向量ait表示輸入的序列在下一個解碼時刻t中的相關程度,公式如下:

這里的對齊模型采用concat 映射,“;”表示拼接兩個向量.上下文向量ct計算公式如下:

結合ct和嵌入式輸入,然后使用softmax函數(shù)歸一化結果可得:

2.3 模型訓練

2.3.1 Actor-Critic

為了訓練網(wǎng)絡模型,本文采用強化學習的方法.我們使用基于策略梯度的強化學習來優(yōu)化網(wǎng)絡參數(shù)θ.策略梯度的思路是:使獎勵越大的動作出現(xiàn)的概率變大,通過反復訓練,不斷地調(diào)整網(wǎng)絡參數(shù).本文選擇Actor-Critic的方法來訓練網(wǎng)絡,相比傳統(tǒng)的策略梯度下降方法,它有以下優(yōu)點:(1) Actor-Critic 使用了策略梯度的方法,可以在連續(xù)動作或者高維的動作空間中選擇適合的動作,采用值函數(shù)的方法是做不到的;(2) Actor-Critic 相比單純的策略梯度的方法,它結合Q-learning 的做法,使得Actor-Critic 可以做到單步更新,比起單純的策略梯度的回合更新效率更高.

Actor-Critic 是由兩個網(wǎng)絡Actor(執(zhí)行者網(wǎng)絡)和Critic(評論者網(wǎng)絡)組成,如圖4 所示.Actor 網(wǎng)絡是基于概率選擇動作,Critic 網(wǎng)絡基于Actor 網(wǎng)絡選擇的動作評價動作的優(yōu)劣,Actor 網(wǎng)絡根據(jù)Critic 網(wǎng)絡的評價修改行為的概率.它將值函數(shù)和策略梯度兩種強化學習算法優(yōu)點結合,使得算法可以處理連續(xù)和離散的問題,還可以進行單步更新.

Fig.4 Actor-Critic network structure圖4 Actor-Critic 網(wǎng)絡結構

設Actor 網(wǎng)絡為π(s),則其網(wǎng)絡參數(shù)θ的梯度公式表示如下:

其中,ω是Critic 網(wǎng)絡V(s)的網(wǎng)絡參數(shù),它的網(wǎng)絡參數(shù)梯度公式如下:

在公式(7)和公式(8)中:N是樣本實例,Rn表示第n個樣本實例獲得的獎勵值,表示第n個樣本實例所有輸入的狀態(tài)集合,是Critic 網(wǎng)絡的輸出.Rn是當前獲得的獎勵值,由啟發(fā)式算法根據(jù)網(wǎng)絡輸出序列計算獲得.是優(yōu)勢函數(shù),它表示在的狀態(tài)下采取動作的優(yōu)劣.如果優(yōu)勢函數(shù)的結果是正的,則會增加 該動作出現(xiàn)的概率,否則降低概率.

Actor-Critic 的算法流程如算法2.2 所示,我們使用θ和ω分別表示是Actor 和Critic 的網(wǎng)絡參數(shù).在第4 行,我們將樣本分成N輸入網(wǎng)絡; 第7 行~第10 行是使用簡化的指針網(wǎng)絡以及注意力機制獲得下一個輸出的概率分布,每次選擇一個物品,停止的條件是當所有物品都被輸出.第11 行計算該輸出的獎勵值,R(·)是獎勵計算函數(shù),也就是算法1.1 計算裝箱的高度將作為獎勵信號Rn.第12 行、第13 行將計算相應的獎勵以及策略梯度.最后,根據(jù)計算的梯度更新兩個網(wǎng)絡.Critic 網(wǎng)絡將使用Actor 網(wǎng)絡輸出的概率分布來計算嵌入式輸入的加權和.該網(wǎng)絡具有兩個隱藏層:第1 層是使用relu 激活函數(shù)的稠密層,另一個是具有單個輸出的線性層.最后對兩個網(wǎng)絡進行更新.

算法2.2.Actor-Critic 算法流程.

2.3.2 探索機制

強化學習的探索機制會直接影響采樣的性能,本文在模型的訓練階段,會通過根據(jù)概率分布按概率進行隨機采樣下一步作為輸出.在測試期間采用的是貪婪的方法,選擇概率分布中概率最高的輸出.

3 計算結果

為了驗證強化學習啟發(fā)式算法并評估其有效性,本小節(jié)將進行一系列實驗分析.首先闡述了實驗數(shù)據(jù)的生成方法,然后對實驗環(huán)境和參數(shù)設置進行說明,最后對實驗結果進行分析.

3.1 實驗數(shù)據(jù)

由于現(xiàn)有的標準數(shù)據(jù)集都是較為零散且實例的數(shù)量較少,目前缺少較大量的裝箱問題的數(shù)據(jù)集來用于強化學習模型的訓練,因此本文采用了Bortfeldt 和Gehring[30]提出的裝箱數(shù)據(jù)生成算法以及Wang 和Valenzela[31]提出的裝箱數(shù)據(jù)生成算法.

Bortfeldt 和Gehring[30]生成數(shù)據(jù)的思路是:通過一些參數(shù),控制生成的矩形的數(shù)量、大小、寬高比以及面積比等.該算法生成的數(shù)據(jù)是非零浪費率的,因此我們無法知道生成的數(shù)據(jù)的最優(yōu)解.算法3.1 是該算法的流程,該算法需要輸入6 個參數(shù):wC表示矩形條的寬度;n表示矩形總個數(shù);nt表示要生成的矩形的種類; Δg和ρg這兩個參數(shù)是用于計算矩形的最大邊長和最小邊長;最后,seed是隨機種子.γ是異質(zhì)性比,等于nt/n.首先,算法根據(jù)輸入的參數(shù)計算生成矩形的邊長范圍[dming,dmaxg],然后根據(jù)隨機種子初始化隨機數(shù)生成器.再循環(huán)nt次生成nt個類型的矩形rects,矩形長寬的范圍介于[dming,dmaxg].最后,循環(huán)n次生成n個矩形rect_list,rect_list依照rect_list[i]=rects[i%nt],0≤i

算法3.1.數(shù)據(jù)生成算法1.

Wang 和Valenzela[31]生成數(shù)據(jù)的算法思路是: 通過將一個大的矩形不斷地進行分割,分割成滿足一定面積比(γ)和寬高比(ρ)的小矩形.這種思路生成的數(shù)據(jù)集是屬于零浪費類型的,裝箱的最優(yōu)解由輸入?yún)?shù)控制.具體的算法流程如算法3.2 所示.該算法輸入的參數(shù)有4 個:n表示生成小矩形個數(shù),H表示待分割矩形的高度,γ和ρ控制生成矩形的面積比和寬高比.算法一開始根據(jù)輸入的參數(shù)隨機選擇寬度W,然后在第3 行~第18 行進行n-1次切割,生成n個矩形.首先,隨機選擇滿足面積小于2m/γ的矩形進行切割,m是矩形序列中最大矩形的面積.在第7 行~第13 行,根據(jù)不同的條件選擇切割方向.第13 行~第18 行根據(jù)不同的切割方向,在可切割的范圍內(nèi)隨機選擇切割點,并把生成的兩個新矩形加入列表中.

算法3.2.數(shù)據(jù)生成算法2.

本文使用算法3.1 和算法3.2 共生成1 000 000 組的數(shù)據(jù)用于訓練模型,共3 種矩形塊數(shù):(1) 矩形塊數(shù)為200生成400 000 組數(shù)據(jù);(2) 矩形塊數(shù)為100 生成300 000 組數(shù)據(jù);(3) 矩形塊數(shù)為50 的塊數(shù)共生成300 000 組數(shù)據(jù).同時生成100 000 組數(shù)據(jù)集作為測試樣本.通過隨機種子生成較大的訓練數(shù)據(jù)集,是為了能盡可能地涵蓋不同的樣本,使得模型能學習到豐富的樣本.

3.2 實驗環(huán)境和參數(shù)設置

強化學習模型主要通過pytorch 實現(xiàn),實驗運行環(huán)境如下:Ubuntu 16.04 LST,處理器為Intel Core E5-2620 v4,處理器頻率2.10GHz,內(nèi)存62G,顯卡為NVIDIAGeForceRTX2080Ti,顯存為11G.

在實驗中,我們使用了1 000 000 組的訓練數(shù)據(jù)和100 000 組的測試數(shù)據(jù).在實驗過程中,每批訓練的樣本量是128,解碼器中GRU 的隱層單元數(shù)量為128,輸入數(shù)據(jù)也將被嵌入到128 的向量中.本文使用Xavier[38]初始化方法對Actor 和Critic 網(wǎng)絡進行初始化,使用Adam 優(yōu)化器,學習速率為0.0001,同時,為了防止過擬合的問題,使用了L2 范數(shù)對梯度進行裁剪.在解碼器中使用了0.1 的dropout,dropout 可以比較有效地緩解過擬合的產(chǎn)生.模型在單個GPU 上訓練1 000 個時期.

訓練好的模型將為HHA 提供初始解,接下來,我們將把RLHA 和目前優(yōu)秀的啟發(fā)式算法GRASP[17],SVC[32],ISA[19],SRA[20],CIBA[21]和HHA[22]算法進行實驗對比,驗證算法的效果.每個算法將在所有的數(shù)據(jù)集上運行10次,每個實例的運行時間限制為60s,部分大規(guī)模數(shù)據(jù)集運行時間會超過60s.對比算法的實驗結果直接取自原文獻(原文獻中的參數(shù)設置都是原作者通過實驗選擇的最優(yōu)參數(shù)),以保證算法對比的公平性.

3.3 實驗結果

為了驗證RLHA 的有效性,我們將訓練好的模型框架同當前著名的啟發(fā)式算法進行對比分析.本節(jié)進行對比分析的實驗數(shù)據(jù)一部分來自標準的數(shù)據(jù)集,為了更合理地說明RLHA 的性能,另一部分是由算法3.1 和算法3.2 生成的數(shù)據(jù).由于訓練的數(shù)據(jù)集與強化學習的算法性能還是存在一定關聯(lián)的,因此另一部分實驗分析將在數(shù)據(jù)生成算法生成的數(shù)據(jù)上進行,可以更客觀的展現(xiàn)算法的性能.

(1) 標準數(shù)據(jù)集的對比分析

我們將在C[12],N[9],NT[33],2SP[17],BWMV[34,35]和Nice&Path[36]這6 個標準數(shù)據(jù)集上進行實驗(見表1),對比7個算法的實驗效果,用粗體標出最佳解的數(shù)據(jù).之所以沒有考慮標準數(shù)據(jù)集ZDF[37]的原因在于:這個數(shù)據(jù)集存在大規(guī)模的實例,目前強化學習模型在處理大規(guī)模的實例時,運行時間會過長.由于計算能力和運行時間的限制,這兩個包含大規(guī)模問題實例的數(shù)據(jù)集就不做實驗分析.

Table 1 Benchmark data表1 標準數(shù)據(jù)集

從表2 的實驗結果可以看出,RLHA 在N 數(shù)據(jù)集上的表現(xiàn)同HHA 表現(xiàn)一樣.N 數(shù)據(jù)集是一個零浪費率的數(shù)據(jù)集,我們的算法在大部分實例上都已經(jīng)取得最優(yōu)解,因此兩個算法在這個數(shù)據(jù)集上表現(xiàn)并無差別.RLHA 在2SP 數(shù)據(jù)集上的表現(xiàn)與HHA 獲得的結果持平.出現(xiàn)這個情況的原因可能與該數(shù)據(jù)的特點有關系,該數(shù)據(jù)矩形個數(shù)較少且存在一些比較特殊的實例,需要更精細的策略來改善.我們的啟發(fā)式設計的規(guī)則在這個數(shù)據(jù)集上的表現(xiàn)可能陷入了瓶頸,因此并沒有取得更優(yōu)的結果.對其余數(shù)據(jù)集,RLHA 均超過了 HHA,在所有數(shù)據(jù)集的表現(xiàn),RLHA 均顯著超過了其他5 個算法.

RLHA 在C,NT,BWMV,Nice 和Path 上的表現(xiàn)都比HHA 略提升了一些,雖然提升的幅度不大,但是可以看到,強化學習模型的加入的確提升了實驗結果.這也可以說明強化學習模型能有效地改進啟發(fā)式獲得解的質(zhì)量.

Table 2 Computational results on benchmark data表2 標準數(shù)據(jù)集的實驗結果

值得注意的是:由于目前現(xiàn)有的針對組合優(yōu)化問題提出的神經(jīng)網(wǎng)絡模型[26-28]在解決TSP、VRP、裝箱等問題時,其數(shù)據(jù)集規(guī)模大部分都是針對少于200 個節(jié)點的問題實例.這是由于處理大規(guī)模實例的數(shù)據(jù)集時會導致模型訓練的時間過長.由于實驗條件等限制,本文訓練數(shù)據(jù)集的矩形塊數(shù)分別是50,100,200.本文的強化學習模型與解決問題的規(guī)模是無關的,也就是說,可以把訓練好的模型用于不同規(guī)模的數(shù)據(jù)集上.我們將訓練的模型用于處理矩形塊數(shù)為1000~5000 的數(shù)據(jù)集Nice 和Path,從表2 中Nice 和Path 的實驗結果可以看出:雖然模型并沒有訓練過矩形塊數(shù)大于200 塊的數(shù)據(jù)集,但是訓練之后的模型在中小規(guī)模的數(shù)據(jù)集上的表現(xiàn)也有一定的提升.這也說明模型可以根據(jù)保存的裝箱經(jīng)驗,為啟發(fā)式算法提供一個有效的初始解序列,幫助算法更好地運行,提高算法性能.

(2) 生成數(shù)據(jù)集的對比分析

表3 是生成數(shù)據(jù)集的明細,分別生成矩形塊數(shù)為50,100,200 以及1 000 的數(shù)據(jù)集各100 組,用于對比實驗的數(shù)據(jù)集.由于算法3.1 生成的數(shù)據(jù)集的最優(yōu)解不確定,因此這里分別將算法在這4 組數(shù)據(jù)上運行,將獲得的最優(yōu)解的裝箱高度的平均值作為比較指標.表4 為實驗的結果,avg_height表示裝箱高度的平均值,更優(yōu)的解將用粗體標出.

Table 3 Details on generated data set表3 生成數(shù)據(jù)集明細

Table 4 Computational results on generated data set表4 生成數(shù)據(jù)集實驗結果

上節(jié)實驗結果表明,HHA 和RLHA 顯著的超過了其他7 個算法.這節(jié)只將兩個最好的HHA 和RLHA 算法進行對比.表4 是HHA 和RLHA 在4 組數(shù)據(jù)集上獲得的平均裝箱高度的數(shù)據(jù),從中可以看出:在數(shù)據(jù)集Test50上,HHA 和RLHA 獲得平均裝箱高是一樣的.這是因為在較小的數(shù)據(jù)集上,兩個算法框架的搜索能力都足夠,因此實驗表現(xiàn)一樣.在數(shù)據(jù)集Test100,Test200 和Test1000 上,RLHA 的表現(xiàn)均優(yōu)于HHA 的表現(xiàn),說明了訓練的強化學習模型能使HHA 獲得更好的性能.

圖5 是Test200 某個實例上分別運行RLHA 和HHA 的結果,兩個算法分別運行240 秒,每秒鐘輸出當前獲得最優(yōu)解的值.圖中橫坐標是時間(s),縱坐標是最優(yōu)解的值,也就是裝箱的高度.從圖中曲線趨勢我們可以觀察到:RLHA 獲得的初始解比HHA 獲得的初始解更好,雖然開始優(yōu)勢并不是特別明顯,但經(jīng)過一段時間的運行,RLHA 能較快地朝更好的解方向發(fā)展,這也說明輸入序列對啟發(fā)式算法的影響.中間部分RLHA 同HHA 一樣,都處在一個較為緩慢的搜索狀態(tài).在運行后期,RLHA 獲得的裝箱高度不斷地下降,雖然HHA 也取得了一些不錯的進步,但是RLHA 的效果優(yōu)于HHA.因此也可以看出:RLHA 能較有效地改善啟發(fā)式冷啟動的問題,并能提高算法的搜索性能.

3.4 不同初始化方法的影響

RLHA 是使用強化學習獲得初始序列,而HHA 是使用6 種排序方法[39](見表5 中的方法1~方法6),并選擇最好的序列,表2 和表4 的計算結果表明,RLHA 的性能超過了HHA.為進一步研究初始化方法的影響,我們再增加了一種隨機初始序列方法.為測試不同初始化方法的影響效果,我們采用典型的BWMV 數(shù)據(jù)(該數(shù)據(jù)包含500個實例).表5 給出了8 種產(chǎn)生初始序列方法的計算結果,從中可以看出:隨機初始序列方法效果最差,使用強化學習獲得初始序列,效果明顯超過其他7 種方法.

Table 5 Computational results on different initialize methods for BWMV表5 不同初始化方法計算BWMV 的結果

4 結 論

強化學習啟發(fā)式算法框架中,我們創(chuàng)新性地使用強化學習的方法來改善啟發(fā)式算法冷啟動問題.強化學習模型僅使用了啟發(fā)式算法計算的裝箱值作為獎勵信號,來訓練網(wǎng)絡,最后輸出給定分布中最優(yōu)的序列.使用簡化版的指針網(wǎng)絡來輸出裝箱序列,該網(wǎng)絡簡化編碼器部分的網(wǎng)絡,節(jié)省了一大部分的計算能力,提高了效率.采用Actor-Critic 算法來訓練網(wǎng)絡,由于Actor-Critic 可以單步更新,比起單純的策略梯度的回合更新效率更高.實驗部分,本文通過數(shù)據(jù)生成算法生成了訓練模型的數(shù)據(jù)集.在714 個標準問題實例和400 個生成的問題實例上測試RLHA,實驗結果顯示,RLHA 獲得了比當前著名啟發(fā)式算法更好的解.這也表明了訓練的強化學習模型能為HHA 提供更好的初始的裝箱序列,有效地改善冷啟動的問題.將來的工作就是在改進框架的基礎上對啟發(fā)式算法進行進一步的改進.同時,將強化學習應用于別的NP 難問題的求解,總結出一般性的求解框架,并進行更多的應用.

Fig.5 Comparison of running time圖5 同時間運行對比