基于強化學習的裝箱問題研究?

紀乃華 李祥棟 祝 凱

（青島理工大學信息與控制工程學院 青島 266520）

1 引言

裝箱問題（Packing Problem）是一種典型的組合優(yōu)化問題，且已被證明是一個NP-hard 問題。裝箱問題結合不同的約束條件和目標被廣泛應用于制造業(yè)，運輸業(yè)，計算機行業(yè)中。本文主要討論二維帶裝箱問題2DSP（2D Strip Packing Problem），問題的定義為給定一組n個尺寸為wi×hi，i= 1…n的二維矩形物品；將這一組矩形物品不重疊，不旋轉地放入到寬度為W，高度不限的矩形長板中，其目的是最小化其高度H。

針對裝箱問題，學者們提出了大量基于不同策略的算法，大致可以分為三大類，第一類是精確算法，其中包括樹搜索算法［1］，線性規(guī)劃算法［2］等。第二類為近似算法，包括BL［3］、BF［4］等算法。第三類為啟發(fā)式算法，包括元啟發(fā)式算法中的遺傳算法［5］，模擬退火算法［6］等，還有學者提出的混合式啟發(fā)式算法包括Leung［7］提出的兩階段智能搜索算法，Yang［8］提出的簡單隨機算法都取得了不錯的結果。

近年來伴隨著人工智能的發(fā)展，作為人工智能的一種，強化學習可以直接在數據中提取有用的信息，從而可以潛在地學習更好的啟發(fā)式算法，同時有著更好的通用性。強化學習廣泛應用到組合優(yōu)化問題上，例如旅行商問題（TSP）［9］，車輛路徑問題（VRP）［10］。Bello［11］等提出了一種基于強化學習的神經組合優(yōu)化框架，此框架在旅行商問題和背包問題上獲得了不錯的結果。針對組合優(yōu)化問題的復雜性，強化學習的Q 函數和人工神經網絡相結合的深度Q 網絡（DQN）展現出了其強大的性能，KunDu［12］等提出了一種基于雙DQN 的深度強化學習框架進行了在線二維裝箱問題研究。雖然強化學習在解決組合優(yōu)化問題上有著比啟發(fā)式算法更好的性能，但強化學習的性能受到訓練數據的影響，如何在使用小實例的樣本訓練后能夠適用于較大的問題的實例成為強化學習解決組合優(yōu)化問題的關鍵。

在Deep-Q-Network（DQN）和簡單隨機算法（SRA）的基礎上，本文提出了一種混合啟發(fā)式算法。本文的主要貢獻如下：

1）提出改進了的評分規(guī)則Scorer I。裝箱問題難免出現空間的浪費，按現有的評分規(guī)則進行裝箱問題時浪費較多，本文通過引入了一組松弛因子（relaxation factor）α，β，建立更細致的評分規(guī)則，以最大程度減少空間浪費。

2）提出基于DQN 的評分規(guī)則Scorer II。本文通過強化學習的DQN 建立評價函數Scorer，再利用Scorer 對矩形物品評價得分得到降序排序的序列，將此序列作為啟發(fā)式算法的初始序列，與其他簡單排序（直接按照周長、寬度等）的初始化序列相比，提高了空間利用率。另一個優(yōu)點是有效地避免了啟發(fā)式算法陷入局部最優(yōu)，有效減少算法的迭代次數。

3）算法融合。為克服模擬退火設置的參數較多、通用性較差的缺點，提出DQN 和SRA 相結合得到混合啟發(fā)式算法（RSRA），其中評分規(guī)則為Scor?er I與Scorer II共同確定。

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

2.1 skyline算法

skyline 算法是本文的啟發(fā)式算法所使用的基本框架，skyline 算法用來確定矩形物品的排列規(guī)則。其算法步驟為對于一個給定的矩形序列，重復以下4 個步驟直到所有矩形都被填充：1）找到sky?line 中最低并且最左邊（以最低為優(yōu)先）的線段；2）根據評分規(guī)則從原始序列中依次計算適應度值；3）將適應度值最高的矩形物品放置在此處；4）更新skyline。

2.2 新的skyline評分規(guī)則

本文在高東琛［13］，Leung［7］等的評分規(guī)則基礎上提出了新的評分規(guī)則Scorer I。其評分規(guī)則如下。

如圖1 所示，選擇skyline 中最低和最左邊的線段，記在此線段上的放置空間為S（圖中藍色框內），候選線段為slowy，與slowy相鄰的水平線段的高度差值較大的為h1，較小的為h2，slowy的寬度記為slowy.w，矩形物品的高和寬分別記為r.h，r.w。未放置的矩形物品序列中寬度最小的矩形物品記為rmin，其寬度記為rmin.w。空間S放置矩形物品后所剩余的空間記為A（圖中虛線框內），其寬度為A.w（A.w=slowy-r.w）。

圖1 矩形物品放置空間示例

高東琛提出的評分規(guī)則的不足之處在于：

1）高東琛在Leung［7］基礎上引入“松弛因子”并建立了更詳細的規(guī)則，該規(guī)則考慮了矩形物品高度過大時將適應度值設為較低值，選取高度較低的矩形物品放在slowy后，更新skyline，然而該規(guī)則在公開數據集實際試驗效果并不理想，由于新的slowy位置有可能變?yōu)楦叩奈恢?，較高的矩形物品放置在此處，有可能會導致整體高度增加。鑒于此種情況，本文不將矩形物品的高度作為評分的標準，能夠有效避免整體高度過高。

2）高東琛考慮到很多時候不存在恰好相等的情況，適當的空間浪費是有必要的，通過松弛因子進行比例的控制，優(yōu)先選擇浪費較少的是一個合理的策略，但是根據此松弛因子在實際實驗中并不能確定放入物品后所剩余的空間能否再放入未放置物品中最小的矩形，針對此種情況本文提出在每一次放置物品時，將所剩余空間的寬度與最小的矩形的寬度進行比較。

綜上，關鍵在于最大利用每一個空間，之前都是考慮單步one-step 放置，本文通過對two-step 兩步放置矩形的綜合考慮，并引入一組寬度松弛因子，主要改進如下：

1）本文提出了記錄待放入矩形物品中的最小矩形物品（rmin）的寬度（rmin.w），在裝箱過程中不可避免有浪費空間的情況存在，在此時考慮如果將矩形物品放入之后的寬度是否能夠滿足大于rmin.w，如果大于，則表明在此空間能夠繼續(xù)放入矩形物品，不會造成浪費，否則會造成空間的浪費。

2）當造成空間浪費的情況時，加入了一組松弛因子（α，β，0<α<1，0<β<1），此系數能夠在必須造成空間浪費的情況下，考慮到最小剩余空間思想，選取寬度較大的矩形放置，能夠最大程度減少空間浪費，根據試驗，本文取值α=0.2，β=0.5。

3）本文還對一些細節(jié)進行了優(yōu)化，本文認為當r.w=slowy.w且r.h=h1或r.h=h2，因為能夠減少sky?line 的線段數，并能夠使得空間更加的平整，所以此處更加適合放置。同時r.h=h2時，相比于r.h=h1時更能夠使得空間更加的平整，更有利于接下來的矩形物品放置，所以本文認為前者得分更高。本文還進行了一些細節(jié)的改變。

其詳細的適應度值如圖2（a）~（f）和表1所示。

表1 適應度值（fitness）表

圖2 適應度值示例

2.3 強化學習方法

與監(jiān)督學習不同的是強化學習從沒有可用的數據開始，這些數據是算法在整個過程中動態(tài)收集的。強化學習最常用于需要順序決策的應用中，其目的是做出最大化回報的決策。

2.3.1 DQN

Q-learning算法是強化學習中的基于價值（val?ue based）的算法中的一種，Q（s，a）是表示在狀態(tài)s的情況下執(zhí)行動作a的獎勵值，Q函數選擇獎勵值最大的動作執(zhí)行。Q-learning算法中的Q是一個表格函數，顯然是不適用于2DSP的，于是我們采用將Q-learning 與神經網絡相結合的Deep Q-Network（DQN）。DQN 算法的核心是用一個人工神經網絡來代替Q（s，a），神經網絡有著強大的表達能力，能夠自動尋找特征，神經網絡要比人工尋找特征強大許多。

2.3.2 DQN神經網絡以及數據預處理方法

本文使用的人工神經網絡結構如圖3所示。

圖3 人工神經網絡score

數據預處理過程如表2 所示，其輸入數據hlarge表示待放入矩形物品的高度r.h與h1的高度差，hsmall表示r.h與h2的高度差，w表示r.w與待放入空間的寬度slowy.w的差值，hr表示當前放入的矩形物品r與未放置的矩形物品序列中的高度最大矩形(R-r)hmax的相對高度，wr表示當前放入的矩形物品r與未放置的矩形物品序列中的寬度最大矩形rwmax的相對寬度。

表2 數據預處理過程

人工神經網絡輸出的數據只包含一個數，表示矩形物品r與待放入空間S的匹配度，值越大表示匹配度越高。hlarge，hsmall與w三個屬性一起經過線性變換和激活函數tanh之后得到一個中間值。hr與wr兩個屬性一起經過線性變換和激活函數tanh之后得到一個中間值。在前兩個已得到的中間值先經過一個2×4的線性變換和激活函數tanh，再經過4×1的線性變換和激活函數sigmoid得到最終的結果，其sigmoid的值域為（0，1）。

2.4 基于DQN的啟發(fā)式算法（RSRA）

我們將使用前文提出的DQN 進行評價函數的構建，實驗結果表明此算法與按照寬度，長度，周長的大小排列順序所構建的矩形物品序列相比有著更好的性能。其詳細算法如算法1 所示：在第二行中，使用了Leung［7］提出的局部搜索算法（LS（R）），以獲得更好的解。LS（R）將在給定的序列中依次交換這兩個項，并使用skyline算法以獲得局部最優(yōu)解。算法第7 行使用本文提出的skyline 算法評分規(guī)則Scorer I和Scorer II規(guī)則共同決定，即當使用規(guī)則Scorer I 得到的評分相等的情況下則采用Scorer II 規(guī)則。將DQN 和啟發(fā)式算法相結合能夠使用較少的數據樣本進行訓練，同時又能夠應用到較大的問題實例上，具有較好的通用性。

算法1 基于強化學習的啟發(fā)式算法

基于強化學習的啟發(fā)式算法（RSRA）

Input：矩形物品序列R（r1，rn，…，rn）

Output：矩形長板高度

1：R?Sort（Scorer II（R），descending order）

2：LS（R）

3：while 未超過規(guī)定程序運行時間do

4： fori←1 tondo

5： 在R中隨機選取兩個序列號j和k；

6： 在R中交換j和k的順序獲得新的序列R*；

7： currenth ←skyline（R*，α，Scorer）；

8： if current

9： besth ←currenth；

10： R ←R*；

11： else

12： p ←currenth/（currenth+besth）；

13： if p

14： R ←R*；

15： end if

16： end if

17： end for

18：end while

19：return besth；

3 實驗分析

為了驗證RSRA 的性能，我們將其與目前優(yōu)秀的算法進行比較，其中包括GRASP［14］、SRA［8］、IA［15］和ISH［16］這三個算法。

我 們 所 使 用 計 算 機 為Intel（R）Core（R）i5-4210M CPU 2.60 GHz RAM 8GB，使用python 對RSRA 進行算法實現，其余算法結果來自原文文獻，計算機配置分為Intel（R）Xeon（R）CPU E5405 2.00 GHz 1.99 GB RAM。

圖4~7 為具體實驗數據，Gap%的定義如Leung所示，Gap%=100×（mean-LB）/LB，其中mean 為算法運行10次所得到的平均結果。Ave.Gap%和best.Gap%分別表示算法運行10 次所得到的平均和最佳Gap%。

圖4 和圖5 顯示了Ave.Gap%以及Best.Gap%五種算法的8個數據集。對于Ave.Gap%如圖4所示，與其他四種算法相比，RSRA 算法在所有8 個數據集上都取得了最好的結果。對于Ave.Gap%，RSRA算法比GRASP 算法、SRA 算法、IA 算法和ISH 算法分別降低了45.86%、45.16%、30.89%和20.56%。對于Best.Gap%如圖5 所示，RSRA 算法在8 個數據集中得到了6 個數據集（C、N、CX、NT、NP、BWMV 的數據集）的最小值。Best.Gap%的平均值RSRA 算法比GRASP 算法、SRA 算法、IA 算法和ISH 算法分別降低了48.86%、35.21%、18.76%和9.57%。

圖5 Best.Gap%

圖6 和圖7 顯示了Ave.Gap%以及Best.Gap%五種算法在所有數據集上所得到的最優(yōu)解的數量。對于Ave.Gap%，RSRA 算法分別在6 個數據集（C、CX、NT、2sp、NP、BWMV）獲得的的最優(yōu)解數量最多，且最優(yōu)解總數最多。對于Best.Gap%，RSRA 算法在5 個數據集（C，N，NP，ZDF，BWMV）上獲得了最多的最優(yōu)解數量，并且最優(yōu)解數量的總和最大。

圖6 Ave.Gap%五種算法獲得最優(yōu)解的數量

圖7 Best.Gap%五種算法獲得最優(yōu)解的數量

根據數據集各自的特征進一步分析。如圖4所示，雖然RSRA 的結果比其他四種算法好得多，但與GRASP 和ISH 的結果非常接近。這可能是因為2sp 的數據集太?。ù蠖鄶祵嵗际莕≤50）。對于CX 和ZDF 數據集（包含n≥10000 個實例），RSRA 的性能比其他四種算法要好得多。對于其他5個數據集（C、N、NT、NP、BWMV）中的問題實例數量大多為50 ≤N≤200，RSRA 算法也取得了不錯的結果。因此，我們可以得出結論，RSRA 算法在8 個數據集上的性能優(yōu)于其他4 個算法，尤其是在相對較大的數據集上。

圖4 Ave.Gap%

4 結語

本文提出了一種求解2DSPP 問題的混合啟發(fā)式算法，提出了改進的skyline 評分規(guī)則Scorer I，提出使用DQN 作為啟發(fā)式算法評價函數Scorer II 的構建，Scorer I 和Scorer II 能夠降低空間的浪費，降低啟發(fā)式算法的迭代次數，提高算法的性能。提出Scorer I 和Scorer II 與一個SRA 算法相結合的混合啟發(fā)式算法（RSRA）。實驗結果表明，與其他四種優(yōu)秀的啟發(fā)式算法（GRASP、SRA、IA、ISH）相比，RSRA 在8 個數據集（C，N，CX，NT，2sp，NP，ZDF，BWMV）上取得了最好的性能，并且Ave.Gap%分別比GRASP、SRA、IA、ISH 分 別 降 低 了45.86%、45.16%、30.89%和20.56%。我們可以得出結論，RSRA 算法在8 個數據集上的性能優(yōu)于其他4 個算法，尤其是在相對較大的數據集上。