求解二維矩形件裝箱問題的布谷鳥算法*

馮文健

(柳州鐵道職業(yè)技術(shù)學(xué)院， 廣西 柳州 545616)

0 引言

二維矩形裝箱問題(2D rectangular strip packing problem, 2DRSPP)是將一組長度、寬度不等的矩形互不重疊的裝入給定寬度、長度不限的矩形條帶箱中，使得箱子被矩形占用的高度最小。該類問題是NP難問題，在工業(yè)領(lǐng)域被廣泛應(yīng)用，因此對此類問題的求解有重要的研究價值。目前對2DRSPP的研究主要集中于算法設(shè)計，可分為精確算法、啟發(fā)式算法和混合智能算法，由于精確算法求解時間較長，只適合較小規(guī)模算例。而后兩者成為求解2DRSPP的主流算法[1-4]。近年來，相關(guān)學(xué)者提出一些更有效的啟發(fā)式算法和混合智能算法，尚正陽等[5]設(shè)計一種啟發(fā)式最優(yōu)剩余空間算法，提出求解二維矩形裝箱問題的啟發(fā)式算法；鄧見凱等[6]提出一種求解二維矩形Packing問題的擬人型全局優(yōu)化算法；羅強(qiáng)等[7]提出求解矩形件排樣問題的十進(jìn)制狼群算法；江林燕[8]提出基于化學(xué)反應(yīng)優(yōu)化算法的裝箱問題研究；車玉馨[9]提出裝箱問題的啟發(fā)式算法研究；高東琛[10]提出二維裝箱問題的啟發(fā)式算法。

本文設(shè)計了算法1并結(jié)合布谷鳥算法求解二維矩形裝箱問題，通過多組測試算例的仿真實(shí)驗，結(jié)果表明本文設(shè)計的算法對部分測試算例效果較好，對部分測試算例效果較差。

1 二維矩形裝箱問題描述

圖1 矩形件裝箱示意圖

假設(shè)第i個小矩形pi的長度和寬度分別表示為wi和hi，排放在寬度為W、高度不限的大矩形帶箱strip上，矩形件i排放后左上角的橫坐標(biāo)、縱坐標(biāo)和寬度分別為xi、yi和wi。排放的過程中矩形件之間不重疊、矩形件不超出strip的邊界和矩形件底邊與strip邊平行3個約束條件。H為n個矩形件排放完后的最大高度，Y為矩形件面積之和與排樣最大高度之下的面積比。為了便于對2DRSPP進(jìn)行數(shù)學(xué)描述，以左下角0為坐標(biāo)原點(diǎn)建立如圖1所示的二維坐標(biāo)系，每一個item用左上角的橫坐標(biāo)、縱坐標(biāo)和寬度來表示，比如矩形1則表示為(0,6,2)，4個item放置strip中形成3條水平線(圖中a,b,c所示)，2DRSPP的目標(biāo)如下：

(1)

s.t.?pi:0≤xi≤W,0≤xi+wi≤W,yi≥0

(2)

?pi,pj:xi≤xj≤xi+wi

(3)

?pi,pj:yi≤yj≤yi+wi

(4)

其中式(3)和(4)保證所有矩形件互不重疊和不超出strip的邊界，本文研究的2DRSPP是矩形件不可旋轉(zhuǎn)。

2 算法描述

應(yīng)用智能算法求解2DRSPP的關(guān)鍵點(diǎn)在于編碼和解碼，本文采用浮點(diǎn)數(shù)編碼方式，然后對其排序得到十進(jìn)制整數(shù)，每一個整數(shù)即為矩形件的唯一標(biāo)識；解碼即運(yùn)用算法對有序的整數(shù)序列轉(zhuǎn)化為排樣圖。

2.1 算法1

算法1過程描述如下：

(1)初始化最低水平線及strip的寬度；

(2)按面積從大到小排序，得到排序序號集set；

在選購機(jī)械設(shè)備的過程中，要將效益放在首要位置，爭取企業(yè)的效益能夠?qū)崿F(xiàn)最大化，選擇設(shè)備時需要按照經(jīng)濟(jì)實(shí)惠的原則。

(3)如果集合set不為空；循環(huán)執(zhí)行步驟4～6；

(4)統(tǒng)計所有未放入strip中的矩形newdata；

(5)判斷newdata中是否存在能夠放入strip中的矩形；

(6)如果存在，則將矩形放入strip中，求解新的水平線并刪除寬度為0的水平線，再判斷最低水平線是否可以合并，如果可以則合并最低水平線并更新最低水平線，然后從集合set中刪除相應(yīng)的矩形；如果不存在，則將此時最低水平線提升至與其相鄰矩形中最低高度齊平，然后合并最低水平線寬度。

(7)直至集合set為空退出循環(huán)，輸出最大高度。

2.2 布谷鳥算法

布谷鳥算法(cuckoo search algorithm，CS)是YANG Xin-she和DEB Suash于2009年提出[11]，該算法結(jié)構(gòu)簡單、容易實(shí)現(xiàn)，其全局搜索過程依靠Levy飛行選擇鳥巢，其迭代式如下：

(5)

局部搜索過程則以一定概率pa拋棄鳥巢和新建鳥巢。

(6)

2.3 策略1

由于在棄巢過程中未利用群體的最佳位置，可能會導(dǎo)致收斂速度和精度不高，因此將式(6)改為下式：

(7)

其中，r1,r2∈[0,1]之間的隨機(jī)數(shù)，m1，m2，m3表示n個不重復(fù)的隨機(jī)整數(shù)。

2.4 策略2

為了增強(qiáng)局部搜索能力，對當(dāng)前鳥巢執(zhí)行輪盤賭選擇(參見遺傳算法)、交叉(隨機(jī)選擇兩個鳥巢和隨機(jī)選擇兩個位置進(jìn)行交叉)和逆序(隨機(jī)選擇兩個位置進(jìn)行倒序)操作。

2.5 改進(jìn)布谷鳥算法

改進(jìn)布谷鳥算法(improved cuckoo search algorithm，ICS)求解過程如下：

(1)初始化種群數(shù)目、最大迭代次數(shù)、棄巢率和邊界等參數(shù)。

(2)在邊界范圍內(nèi)隨機(jī)初始化種群并降序排列，按算法1求解目標(biāo)值(高度)，求解當(dāng)前種群最優(yōu)值(最小高度)及最優(yōu)解。

(3)開始循環(huán)迭代，按式(5)獲得新鳥巢然后評估最優(yōu)值及最優(yōu)解，若較之前的優(yōu)越則替換；按式(7)建立新鳥巢并重新評估最優(yōu)值及最優(yōu)解，若較之前的優(yōu)越則替換。

(4)執(zhí)行N=5次數(shù)策略2并重新評估最優(yōu)值及最優(yōu)解，若較之前的優(yōu)越則替換。

(5)判斷循環(huán)是否結(jié)束，如果是輸出最優(yōu)值及最優(yōu)解，對最優(yōu)解降序排列得到的序列即為矩形件的排樣順序，否則跳轉(zhuǎn)至步驟(3)。

3 仿真實(shí)驗

為了驗證ICS的性能，本文實(shí)驗1數(shù)據(jù)來源于文獻(xiàn)[12]，實(shí)驗2的數(shù)據(jù)來源于http://people.brunel.ac.uk/～mastjjb/jeb/info.html；所有實(shí)驗基于windows平臺使用matlab語言編寫實(shí)現(xiàn)，硬件環(huán)境為i7-9750H 2.60GHz CPU,8G內(nèi)存。算法的參數(shù)設(shè)置：種群規(guī)模為20，棄巢率為0.25，交叉率為0.85，最大迭代次數(shù)為100。

表1 算例N的比較結(jié)果

3.1 實(shí)驗1

實(shí)驗1采用經(jīng)典的N算例對本文算法進(jìn)行測試，并與GA+BLF，SA+BLF，GA+IHR算法進(jìn)行比較，統(tǒng)計結(jié)果見表1，排樣效果如圖2、圖3所示。表1中的n，w，hopt分別表示矩形個數(shù)、strip寬度和已知最優(yōu)高度。

圖2 N4排樣圖 圖3 N7排樣圖

表2 ngcut和beng算例的統(tǒng)計結(jié)果

從表2可知，本文算法在N4、N6和N7算例上求解的最優(yōu)值均優(yōu)于GA+BLF、SA+BLF和GA+IHR算法；本文算法在N3～N9算例上求解的最優(yōu)值均優(yōu)于GA+BLF和SA+BLF算法，在N10,11算例上求解的最優(yōu)值與其一致，僅在N2算例上求解的最優(yōu)值較其差；與GA+IHR算法相比，求解結(jié)果優(yōu)于的有算例N1、N2、N4和N7；求解結(jié)果一致的有N3和N6；求解結(jié)果較差的有算例N5、N8、N9、N10和N11。通過11個N類算例驗證了本文的有效性。

3.2 實(shí)驗2

實(shí)驗2的ngcut算例共有12個子算例，均屬于小規(guī)模問題。beng算例共有10個子算例。矩形為20～200個。采用相對距離來評價計算結(jié)果，gap=(h*-hopt)/hopt×100 ，h*表示計算的最優(yōu)值，hopt為已知最優(yōu)值，gap越小表示算法越好。并與文獻(xiàn)[13～17]、DWPA算法進(jìn)行比較，統(tǒng)計結(jié)果見表2，部分排樣效果如圖4、圖5所示。表2中的n，w，hopt分別表示矩形個數(shù)、strip寬度和已知最優(yōu)高度。

圖4 beng4排樣圖 圖5 beng7排樣圖

從表2可知，對ngcut小規(guī)模的測試算例，本文的求解效果與GRASP效果一致，優(yōu)于ISA、SRA、文獻(xiàn)[16]、文獻(xiàn)[17]算法，差于DWPA算法，但對ngcut 5算例，本文和其他算法均優(yōu)于DWPA算法。對于beng測試算例，本文的求解效果差于其他算法。因此，從所有的測試算例來看，本文設(shè)計的算法對N類和ngcut類裝箱問題求解效果較好，但對beng類裝箱問題求解效果差于其他算法。

4 結(jié) 語

本文在布谷鳥算法基礎(chǔ)之上設(shè)計算法1，并改進(jìn)局部搜索迭代公式，同時為增強(qiáng)局部勘探能力，對鳥巢進(jìn)行輪盤賭選擇、交叉和逆序操作，采用浮點(diǎn)數(shù)編碼方式求解二維矩形裝箱問題，應(yīng)用多組測試算例對算法進(jìn)行仿真實(shí)驗，并與其他智能算法進(jìn)行比較，結(jié)果表明對N類和ngcut類裝箱問題求解效果較好，但對beng類裝箱問題求解效果較差，如何進(jìn)一步提高裝箱效果是下一步研究方向。