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

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

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

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

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

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

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

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

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

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

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

1 啟發式算法

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

算法1.1.構造性啟發式算法.

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

算法1.2.HHA 框架.

2 強化學習啟發式算法

2.1 強化學習求解框架

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

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

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

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

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

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

算法2.1.強化學習啟發式算法.

2.2 網絡模型

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

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

Fig.3 Network model圖3 網絡模型示意圖

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

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

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

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

2.3 模型訓練

2.3.1 Actor-Critic

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

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

Fig.4 Actor-Critic network structure圖4 Actor-Critic 網絡結構

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

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

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

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

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

2.3.2 探索機制

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

3 計算結果

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

3.1 實驗數據

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

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

算法3.1.數據生成算法1.

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

算法3.2.數據生成算法2.

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

3.2 實驗環境和參數設置

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

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

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

3.3 實驗結果

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

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

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

Table 1 Benchmark data表1 標準數據集

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

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

Table 2 Computational results on benchmark data表2 標準數據集的實驗結果

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

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

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

Table 3 Details on generated data set表3 生成數據集明細

Table 4 Computational results on generated data set表4 生成數據集實驗結果

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

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

3.4 不同初始化方法的影響

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

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

4 結 論

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

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