紀(jì)乃華 李祥棟 祝 凱

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

1 引言

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

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

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

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

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

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

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

2 基于強(qiáng)化學(xué)習(xí)的啟發(fā)式算法

2.1 skyline算法

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

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

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

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

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

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

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

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

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

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

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

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

其詳細(xì)的適應(yīng)度值如圖2（a）~（f）和表1所示。

表1 適應(yīng)度值（fitness）表

圖2 適應(yīng)度值示例

2.3 強(qiáng)化學(xué)習(xí)方法

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

2.3.1 DQN

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

2.3.2 DQN神經(jīng)網(wǎng)絡(luò)以及數(shù)據(jù)預(yù)處理方法

本文使用的人工神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)如圖3所示。

圖3 人工神經(jīng)網(wǎng)絡(luò)score

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

表2 數(shù)據(jù)預(yù)處理過程

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

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

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

算法1 基于強(qiáng)化學(xué)習(xí)的啟發(fā)式算法

基于強(qiáng)化學(xué)習(xí)的啟發(fā)式算法（RSRA）

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

Output：矩形長板高度

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

2：LS（R）

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

4： fori←1 tondo

5： 在R中隨機(jī)選取兩個序列號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 實(shí)驗(yàn)分析

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

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

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

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

圖5 Best.Gap%

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

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

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

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

圖4 Ave.Gap%

4 結(jié)語

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