鄧見凱，王 磊，尹愛華

(1.武漢科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,湖北 武漢 430065;2.智能信息處理與實(shí)時(shí)工業(yè)系統(tǒng)湖北省重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430065;3.江西財(cái)經(jīng)大學(xué)軟件與通信工程學(xué)院，江西 南昌 330013)

1 引言

二維矩形Packing問題是指：在二維歐氏空間中，給定1個(gè)矩形容器和n個(gè)矩形塊。矩形容器和矩形塊的長(zhǎng)、寬為已知的正實(shí)數(shù)。在滿足三個(gè)約束條件的前提下，要求將這些矩形塊放入矩形容器內(nèi)，使得矩形容器的面積利用率最大化。約束條件為：第一，小矩形塊須完全在矩形容器內(nèi)。第二，矩形塊的每條邊均和矩形容器的某條邊平行或重合。第三，每?jī)蓚€(gè)小矩形塊相互不重疊。三個(gè)約束條件可簡(jiǎn)稱為：“不出界、不傾斜、不重疊”。

W和H表示矩形容器的長(zhǎng)度和寬度。wi和hi表示矩形塊Ri的長(zhǎng)度和寬度。(xli,yli)和(xri,yri)分別表示矩形塊Ri被放入矩形容器后，其左下角和右上角的坐標(biāo)。若矩形塊Ri已被放入矩形容器中，則邏輯變?cè)猵i值為1；否則pi值為0。矩形容器位于第一象限，并且其左下角位于坐標(biāo)原點(diǎn)(如圖1所示)。二維矩形Packing問題的形式化描述如下：

subject to

pi=0∨(0≤xli

(1)

pi=0∨(xri-xli=wi∧yri-yli=hi)∨(xri-xli=hi∧yri-yli=wi)

(2)

pi=0∨pj=0∨(xli≥xrj∨xlj≥xri∨yli≥yrj∨ylj≥yri)

(3)

pi∈{0,1}

(4)

其中，i,j=1,2,…,n，并且i≠j。公式(1)表示每個(gè)小矩形塊須完全在容器內(nèi)。公式(2)表示小矩形塊的每條邊均和矩形容器的某條邊平行或重合。公式(3)表示每?jī)蓚€(gè)小矩形塊相互不重疊[1]。

二維矩形Packing問題已被證明為NP難度問題。工商業(yè)、運(yùn)輸、物流領(lǐng)域的諸多問題可歸結(jié)為二維矩形Packing問題。例如，在板材切割加工過程中，需要合理布局以提高材料利用率；在集成電路設(shè)計(jì)中如何布置以提高布局空間利用率[2]。

算法可分為完整算法和啟發(fā)式算法兩類。完整算法能保證找到最優(yōu)布局，但是所花時(shí)間太長(zhǎng)，僅可用于計(jì)算較小規(guī)模的問題實(shí)例[3]。啟發(fā)式算法又可分為非隨機(jī)型算法和隨機(jī)型算法。

非隨機(jī)型算法著力于提出選擇放置動(dòng)作的優(yōu)先序，并在其基礎(chǔ)上進(jìn)行樹搜索，包括底部左齊擇優(yōu)匹配算法[4]、分支限界[5]、擬人算法[6-10]。文獻(xiàn)[6]提出基于動(dòng)作空間的基本算法和增強(qiáng)算法。動(dòng)作空間定義的引入便于計(jì)算出合理的占角動(dòng)作?；舅惴ㄔ诙鄠€(gè)占角動(dòng)作中選擇時(shí)，優(yōu)先選取與當(dāng)前動(dòng)作空間相貼邊多、對(duì)剩余空間損害小、與其它已放入塊關(guān)系更緊密的動(dòng)作。增強(qiáng)算法在每一步考察優(yōu)先序中排名前N名的占角動(dòng)作，通過向前看并回溯的方法選擇一個(gè)動(dòng)作。

隨機(jī)型算法以矩形塊優(yōu)先序作為高維空間中的點(diǎn)，設(shè)計(jì)各種鄰域結(jié)構(gòu)，結(jié)合了各種緊密放置矩形塊的策略以及搜索策略，包括貪心隨機(jī)適應(yīng)搜索算法[11]、模擬退火和貪心局部搜索算法[12]、禁忌搜索算法[13]、隨機(jī)局部搜索[14,15]、變鄰域搜索[16]。

為實(shí)現(xiàn)全局優(yōu)化，本文中的算法主要采用兩種方法。第一是采用三階段優(yōu)化，結(jié)合了目前文獻(xiàn)中非隨機(jī)型和隨機(jī)型算法的優(yōu)點(diǎn)。第二是提出跳坑策略將搜索引向有希望的區(qū)域。

2 擬人算法策略

2.1 基本定義

定義1(格局) 矩形容器內(nèi)已放入一些矩形塊，每個(gè)矩形塊的位置、方向已知，容器外尚有矩形塊待放，這稱為一個(gè)格局。初始格局中，所有矩形塊均在容器外。終止格局中，所有矩形塊均在容器內(nèi)，或者雖有塊在容器外但已經(jīng)不可能再放入。圖1為一個(gè)格局[17]。

Figure 1 Configuration and corner areas圖1 格局及角區(qū)

定義2(角區(qū)) 矩形容器中由塊或者矩形容器本身形成的直角形狀的空白區(qū)域被稱為角區(qū)。分為90°角區(qū)和270°角區(qū)。圖1中有10個(gè)角區(qū)，其中角區(qū)1、3、5、6、7、8、10為90°，角區(qū)2、4、9為270°。角區(qū)的定義來自于人們裝箱的實(shí)際經(jīng)驗(yàn)。將物體放在角區(qū)，在格局中腹部留出大片相對(duì)完整的空白區(qū)域，有利于后續(xù)矩形塊的布局。本文與文獻(xiàn)[17]中的角區(qū)定義有所不同。本文中的角區(qū)全部為“實(shí)角”。也就是說，角區(qū)的頂點(diǎn)一定是某個(gè)小矩形塊(或矩形容器)的頂點(diǎn)。這樣設(shè)計(jì)的優(yōu)點(diǎn)是布局更為緊密。

定義3(占角動(dòng)作) 在滿足三個(gè)約束條件的前提下，將一個(gè)矩形塊按照指定方向(站或躺)放在指定的位置(用塊左下角坐標(biāo)表明)，使得矩形塊的一角正好與90°角區(qū)的角重合。這稱為一個(gè)占角動(dòng)作。圖2中A、B、C、D、E、F、G均為占角動(dòng)作。

Figure 2 Corner-occupying action圖2 占角動(dòng)作

定義4(動(dòng)作空間) 在當(dāng)前格局下，若往矩形容器內(nèi)放入一個(gè)虛擬的矩形塊(滿足三個(gè)約束條件)，使得該塊的上下左右四條邊均與其它已放入的塊或容器的邊相貼(重合的長(zhǎng)度大于0)，則該虛擬塊所占的空間稱為當(dāng)前格局下的一個(gè)動(dòng)作空間[9,11]。初始格局下，恰有一個(gè)動(dòng)作空間，當(dāng)放入一個(gè)矩形以后，形成兩個(gè)動(dòng)作空間，如圖3所示。動(dòng)作空間的定義有助于計(jì)算矩形塊的合理動(dòng)作。

Figure 3 Action space圖3 動(dòng)作空間

定義5(剩余空間平整度) 平整度計(jì)算公式為e4-m，其中m為剩余空間的角區(qū)數(shù)(包括90°和270°角區(qū))。剩余空間的角區(qū)數(shù)越少，其平整度越高，有利于放置后續(xù)矩形塊。圖4a中，將矩形塊放在位置A，剩余空間m值為8。圖4b中，將同一個(gè)矩形塊放在位置B，則剩余空間m值為10。因此,圖4a中的剩余空間平整度較高。本文對(duì)文獻(xiàn)[6]中的平整度定義作了簡(jiǎn)化。

Figure 4 Degree of planeness圖4 剩余空間平整度

定義6(占角動(dòng)作的重疊度) 一個(gè)占角動(dòng)作所對(duì)應(yīng)的矩形塊與其所在動(dòng)作空間的貼邊數(shù)，稱為其重疊度。重疊度高的動(dòng)作，與所在動(dòng)作空間貼合較好，對(duì)剩余空間損害較小，有利于放置后續(xù)矩形塊[7]。圖5a和圖5b中動(dòng)作重疊度分別為3和2。

Figure 5 Degree of overlapping of the corner-occupying action圖5 占角動(dòng)作重疊度

Figure 6 Degree of cave of the corner-occupying action圖6 占角動(dòng)作穴度

定義8(占角動(dòng)作面積利用率) 占角動(dòng)作面積利用率的計(jì)算公式為(wihi)/(WjHj)(參見圖6)。

定義9(占角動(dòng)作的浪費(fèi)度) 當(dāng)一個(gè)占角動(dòng)作做完后，在其占據(jù)的動(dòng)作空間中最多可能生成兩個(gè)新的動(dòng)作空間(參見圖7)。若一個(gè)新的動(dòng)作空間過小，放不下矩形容器外的任何一個(gè)小矩形塊，則稱其為被浪費(fèi)的動(dòng)作空間。占角動(dòng)作做完后新生成的被浪費(fèi)的動(dòng)作空間的數(shù)量，稱為此占角動(dòng)作的浪費(fèi)度。觀察圖7a和圖7b中的兩個(gè)新生成的動(dòng)作空間。若兩個(gè)動(dòng)作空間均為被浪費(fèi)的動(dòng)作空間，則占角動(dòng)作的浪費(fèi)度為2；若其中恰有一個(gè)動(dòng)作空間被浪費(fèi)，則占角動(dòng)作的浪費(fèi)度為1；否則占角動(dòng)作的浪費(fèi)度為0。

Figure 7 Degree of waste of the corner-occupying action圖7 占角動(dòng)作浪費(fèi)度

定義10(矩形塊優(yōu)先級(jí)) 假定n個(gè)矩形塊分為k種形狀大小兩兩不等的類型，矩形塊的優(yōu)先級(jí)是1～k的正整數(shù)。對(duì)于形狀大小相同的矩形塊，其優(yōu)先級(jí)相等。不妨令k級(jí)為最高優(yōu)先級(jí)，1級(jí)為最低優(yōu)先級(jí)。w(Ri)表示矩形塊Ri的優(yōu)先級(jí)，1≤w(Ri)≤k。

定義11矩形塊排序的3項(xiàng)指標(biāo)：(1) 矩形塊的周長(zhǎng)，大優(yōu)先；(2) 矩形塊的長(zhǎng)邊長(zhǎng)，大優(yōu)先；(3)矩形塊的序號(hào)，小優(yōu)先。對(duì)矩形塊排序后，在查找時(shí)可利用折半查找，提高速度。

定義12占角動(dòng)作排序的9項(xiàng)指標(biāo)：(1) 動(dòng)作做完后，矩形容器內(nèi)剩余空間的平整度，大優(yōu)先；(2) 動(dòng)作的重疊度，大優(yōu)先；(3) 矩形塊的優(yōu)先級(jí)，大優(yōu)先；(4) 動(dòng)作的穴度，大優(yōu)先；(5) 動(dòng)作的浪費(fèi)度，小優(yōu)先； (6) 矩形塊的序號(hào)，小優(yōu)先；(7) 矩形塊左下頂點(diǎn)的y坐標(biāo)，小優(yōu)先；(8) 矩形塊左下頂點(diǎn)的x坐標(biāo)，小優(yōu)先；(9) 矩形塊的方向，躺優(yōu)先。

定義13動(dòng)作空間排序的4項(xiàng)指標(biāo)：(1) 動(dòng)作空間左下角的x坐標(biāo)，小優(yōu)先；(2) 動(dòng)作空間左下角的y坐標(biāo)，小優(yōu)先；(3)動(dòng)作空間的長(zhǎng)度，小優(yōu)先；(4)動(dòng)作空間的寬度，小優(yōu)先。

如果某個(gè)動(dòng)作空間放不下任何一個(gè)容器外的矩形塊，則在動(dòng)作空間序列中刪去此動(dòng)作空間。對(duì)動(dòng)作空間排序后，為節(jié)省計(jì)算時(shí)間，本文僅考慮排序前M位的動(dòng)作空間。M取值為200。

2.2 基本算法

基本算法命名為A1算法。其步驟如下：

Step1初始格局：所有矩形塊均在矩形容器外，矩形容器是空的。依字典序按照矩形塊排序的3項(xiàng)指標(biāo)(見定義11)對(duì)所有矩形塊排序。

Step2在當(dāng)前格局下，依字典序按9項(xiàng)指標(biāo)(見定義12)選擇最優(yōu)先的占角動(dòng)作來做，動(dòng)作做完以后，演化到新格局。

Step3對(duì)動(dòng)作空間序列做如下三步操作。第一，更新占角動(dòng)作所在的動(dòng)作空間。第二，檢查所放入的矩形塊是否與動(dòng)作空間序列中其它動(dòng)作空間重疊。若有重疊，則更新重疊的動(dòng)作空間。第三，刪去被其它動(dòng)作空間包含的動(dòng)作空間。

依此類推，循環(huán)做Step 2～Step 3，直到終止格局為止。

2.3 擬人型全局優(yōu)化算法(A1B1)整體框架

整個(gè)擬人型全局優(yōu)化算法由三個(gè)優(yōu)化階段組成(參見圖8)。擬人型全局優(yōu)化算法基于基本算法A1和優(yōu)美度枚舉子程序B1，因此本文將擬人型全局優(yōu)化算法命名為A1B1算法。

Figure 8 Sketch of the whole algorithm圖8 算法總體框圖

(1)在第一優(yōu)化階段中生成初始點(diǎn)(2.4節(jié))。初始點(diǎn)記為Q0，它表示所有矩形塊的初始優(yōu)先級(jí)。給定Q0后，從初始格局出發(fā)，運(yùn)用基本算法A1可唯一確定一個(gè)終止格局。這個(gè)終止格局記為C(A1,Q0)。

(2)在第二優(yōu)化階段中，交替循環(huán)調(diào)用鄰域搜索子程序(2.5節(jié))和跳坑策略子程序(2.6節(jié))，針對(duì)所有矩形塊的優(yōu)先級(jí)進(jìn)行優(yōu)化。調(diào)用鄰域搜索子程序。若發(fā)現(xiàn)矩形塊已全部進(jìn)入矩形容器，則成功停機(jī)。若搜索遇到局部最優(yōu)點(diǎn)，則調(diào)用跳坑策略子程序跳出局部最優(yōu)點(diǎn)，得到新的起點(diǎn)。從新起點(diǎn)開始，又循環(huán)調(diào)用鄰域搜索子程序。如此反復(fù)，直到滿足第二階段計(jì)算停止條件為止。

第二優(yōu)化階段結(jié)束時(shí)，得到一個(gè)優(yōu)化后的所有矩形塊的優(yōu)先級(jí)，記為Q+。根據(jù)Q+，從初始格局出發(fā)，運(yùn)用基本算法A1可唯一確定一個(gè)終止格局。這個(gè)終止格局記為C(A1,Q+)。

(3)在第三優(yōu)化階段中調(diào)用優(yōu)美度枚舉子程序(2.7節(jié))。優(yōu)美度枚舉子程序命名為B1算法。B1算法是一種樹搜索程序，針對(duì)占角動(dòng)作的選擇進(jìn)行優(yōu)化。從初始格局出發(fā)，按照優(yōu)先級(jí)Q+，B1算法可唯一確定一個(gè)終止格局。這個(gè)終止格局記為C(B1,Q+)。

每個(gè)優(yōu)化階段的計(jì)算停止條件均為兩個(gè)：第一個(gè)條件是當(dāng)矩形塊已全部進(jìn)入矩形容器，則輸出布局，成功停機(jī)。第二個(gè)條件是計(jì)算達(dá)到本階段的計(jì)算時(shí)間上限，則停止，轉(zhuǎn)入下一個(gè)優(yōu)化階段。本文中三個(gè)優(yōu)化階段的時(shí)間上限相等。

若三個(gè)優(yōu)化階段結(jié)束，仍未將所有矩形塊放入矩形容器，則輸出計(jì)算歷史上所生成的最優(yōu)布局，停機(jī)。

小規(guī)模實(shí)例(矩形塊數(shù)小于或等于200)、中規(guī)模實(shí)例(矩形塊數(shù)大于200且小于或等于500)、大規(guī)模實(shí)例(矩形塊數(shù)大于500且小于或等于10 000)、對(duì)超大規(guī)模實(shí)例(矩形塊數(shù)大于10 000)的計(jì)算時(shí)間上限分別為360 s、600 s、1 200 s和15 000 s。

2.4 初始點(diǎn)的生成

所謂生成初始點(diǎn)，是指對(duì)所有矩形塊指派優(yōu)先級(jí)。本文按照大矩形塊優(yōu)先的策略指派優(yōu)先級(jí)，有“周長(zhǎng)大者優(yōu)先”“面積大者優(yōu)先”“長(zhǎng)邊長(zhǎng)大者優(yōu)先”三種具體做法。第一種做法：首先按照定義11對(duì)所有矩形塊排序，然后依次指派優(yōu)先級(jí)，這是“周長(zhǎng)，大優(yōu)先”的做法。第二種做法：將定義11中的第1項(xiàng)指標(biāo)改為“矩形塊的面積，大優(yōu)先”。第三種做法：刪去定義11中的第1項(xiàng)指標(biāo)，這是“長(zhǎng)邊長(zhǎng)，大優(yōu)先”的做法。三種做法各有其優(yōu)缺點(diǎn)，本文在其中均勻地隨機(jī)取一種，生成初始點(diǎn)。

2.5 鄰域搜索子程序

Q=(q(R1),q(R2),…,q(Ri),…,q(Rn))表示所有矩形塊的優(yōu)先級(jí)。用Q表示n維空間中的一個(gè)點(diǎn)。只要指定Q值，從初始格局出發(fā)，運(yùn)用基本算法A1可唯一確定一個(gè)終止格局。這個(gè)終止格局記為C(A1,Q)。

以A1算法為基礎(chǔ)進(jìn)行適當(dāng)?shù)泥徲蛩阉?屬于局部搜索)，期望尋找更優(yōu)的矩形塊的優(yōu)先級(jí)。本文提出兩種鄰域結(jié)構(gòu)，一定程度上避免單一型鄰域結(jié)構(gòu)的局限性。

定義14(交換式鄰域) 任意給定所有矩形塊的優(yōu)先級(jí)Q，不妨將矩形塊按照優(yōu)先級(jí)從高到低的順序排列。考慮優(yōu)先級(jí)為k1和k2的矩形塊，將它們的優(yōu)先級(jí)互換，保持其余矩形塊的優(yōu)先級(jí)不變。從而得到一個(gè)新優(yōu)先級(jí)Q′,Q′的集合構(gòu)成Q的交換式鄰域。其中1≤k1

定義15(插入式鄰域) 任意給定所有矩形塊的優(yōu)先級(jí)Q，將矩形塊按照優(yōu)先級(jí)從高到低的順序排列?？紤]所有優(yōu)先級(jí)大于或等于k1并且小于或等于k2的矩形塊，插入式鄰域有兩種方式：第一種是將原優(yōu)先級(jí)為k2的矩形塊降為k1級(jí)，然后將原優(yōu)先級(jí)嚴(yán)格小于k2并且大于或等于k1的矩形塊均升1級(jí)。第二種是將原優(yōu)先級(jí)為k1的矩形塊升為k2級(jí)，然后將原優(yōu)先級(jí)嚴(yán)格大于k1并且小于或等于k2的矩形塊均降1級(jí)。其余矩形塊的優(yōu)先級(jí)不變。

例1已知6個(gè)矩形塊的優(yōu)先級(jí)：q(R2)=4,q(R4)=3,q(R5)=3,q(R3)=2,q(R1)=1,q(R6)=1。首先討論交換式鄰域。例如考慮優(yōu)先級(jí)為1和3的矩形塊，互換其優(yōu)先級(jí)。q(R1)=3,q(R6)=3,q(R4)=1,q(R5)=1，其余矩形塊的優(yōu)先級(jí)不變。

然后討論插入式鄰域。例如考慮優(yōu)先級(jí)從2到4的矩形塊?？蓪?yōu)先級(jí)為4的矩形塊降為2級(jí)，然后優(yōu)先級(jí)為3和2的矩形塊均升1級(jí)。新的優(yōu)先級(jí)為：q(R4)=4,q(R5)=4，q(R3)=3,q(R2)=2。也可以將優(yōu)先級(jí)為2的矩形塊升為4級(jí)，然后優(yōu)先級(jí)為4和3的矩形塊均降1級(jí)。新的優(yōu)先級(jí)為：q(R3)=4,q(R2)=3,q(R4)=2,q(R5)=2。其余矩形塊的優(yōu)先級(jí)不變。

進(jìn)行鄰域搜索時(shí)采用“見好就收”的策略以節(jié)約計(jì)算時(shí)間。迭代的一步為：依次考慮當(dāng)前點(diǎn)Q的全部鄰點(diǎn)，對(duì)于鄰點(diǎn)按照基本算法A1計(jì)算出對(duì)應(yīng)的布局。一旦發(fā)現(xiàn)某個(gè)鄰點(diǎn)所對(duì)應(yīng)的布局面積利用率更高，立刻用此鄰點(diǎn)取代當(dāng)前點(diǎn),一步迭代完成。若所有鄰點(diǎn)對(duì)應(yīng)的布局的面積利用率均不高于當(dāng)前點(diǎn)對(duì)應(yīng)的布局，則當(dāng)前點(diǎn)為局部最優(yōu)點(diǎn)，停止本次鄰域搜索子程序的運(yùn)行。

與現(xiàn)有求解矩形Packing問題的文獻(xiàn)中的鄰域搜索程序[16]相比，本文增加了插入式鄰域，使得搜索范圍擴(kuò)大，有利于找到更優(yōu)布局。

2.6 跳坑策略子程序

當(dāng)鄰域搜索遇到局部最優(yōu)點(diǎn)時(shí)，調(diào)用跳坑策略子程序跳出局部最優(yōu)點(diǎn)，得到新的起點(diǎn)。從新的起點(diǎn)出發(fā)繼續(xù)進(jìn)行鄰域搜索。如此反復(fù)，有望找到更優(yōu)布局。現(xiàn)有文獻(xiàn)主要采用模擬退火、禁忌搜索等方法跳出局部最優(yōu)。本文采用的是擬人途徑跳出局部最優(yōu)陷阱。

起跳點(diǎn)的選擇有兩種方式：第一種是回到歷史最好點(diǎn)。在第二優(yōu)化階段所發(fā)現(xiàn)的歷史最好點(diǎn)(對(duì)應(yīng)的布局面積利用率最高)的信息可以利用。為避免搜索總是圍繞在歷史最好點(diǎn)附近，第二種起跳方式是從當(dāng)前點(diǎn)起跳。本文在兩種起跳方式中均勻地隨機(jī)選擇一種。

跳坑方法是對(duì)起跳點(diǎn)進(jìn)行隨機(jī)擾動(dòng)。具體做法為R步迭代，每一步迭代是在起跳點(diǎn)的所有鄰點(diǎn)中均勻地隨機(jī)選取1個(gè)鄰點(diǎn)，將此點(diǎn)作為新的起跳點(diǎn)，從而完成1步迭代。在第4節(jié)的實(shí)驗(yàn)中，R是在[10,20]內(nèi)均勻分布的隨機(jī)整數(shù)。

2.7 優(yōu)美度枚舉子程序

定義16(占角動(dòng)作優(yōu)美度) 在當(dāng)前格局下，定義占角動(dòng)作的優(yōu)美度：占角動(dòng)作做完后，按照基本算法計(jì)算到終止格局，終止格局中矩形塊的面積之和稱為此占角動(dòng)作的優(yōu)美度。

優(yōu)美度枚舉子程序采用了棋類游戲中“向前看并回溯”的思路，其具體步驟如下：

Step1初始格局。所有矩形塊均在矩形容器外。

Step2進(jìn)行一輪計(jì)算：在當(dāng)前格局下，首先依字典序按照定義12中的9項(xiàng)指標(biāo)對(duì)所有占角動(dòng)作排序，取排名前N名的占角動(dòng)作為候選。然后調(diào)用A1算法依次計(jì)算這N個(gè)動(dòng)作的優(yōu)美度。最后選擇其中優(yōu)美度最大的動(dòng)作。若優(yōu)美度最大的動(dòng)作有多個(gè)，則按照定義12取其中最優(yōu)先的動(dòng)作。動(dòng)作做完后，演化到新格局。

Step3更新動(dòng)作空間序列。

循環(huán)執(zhí)行Step 2和Step 3，直到算法停機(jī)。

停機(jī)條件有兩個(gè)：第一，所有矩形塊均已放入矩形容器。第二，優(yōu)美度枚舉子程序的執(zhí)行時(shí)間已經(jīng)達(dá)到所設(shè)定的上限。

2.8 擬人型全局優(yōu)化算法族

基本算法A1按照定義12中的9項(xiàng)指標(biāo)來選取排序第一的占角動(dòng)作。對(duì)定義12中的9項(xiàng)指標(biāo)略作修改，可得到基本算法族。

基本算法A2：從算法A1修改而來。將定義12中的第(4)項(xiàng)指標(biāo)和第(5)項(xiàng)指標(biāo)互換。

基本算法A3：從算法A1修改而來。將定義12中的原第(5)項(xiàng)指標(biāo)改為第(3)項(xiàng)指標(biāo)，再將原第(3)、第(4)項(xiàng)指標(biāo)改為第(4)、第(5)項(xiàng)指標(biāo)。

基本算法A4：從算法A1修改而來。將定義12中的第(7)項(xiàng)指標(biāo)和第(8)項(xiàng)指標(biāo)互換。

基本算法A5：從算法A2修改而來。將定義12中的第(7)項(xiàng)指標(biāo)和第(8)項(xiàng)指標(biāo)互換。

基本算法A6：從算法A3修改而來。將定義12中的第(7)項(xiàng)指標(biāo)和第(8)項(xiàng)指標(biāo)互換。

基本算法A7～A12分別從算法A1～A6修改而來：將“動(dòng)作的穴度，大優(yōu)先”這項(xiàng)指標(biāo)改為“動(dòng)作的面積利用率，大優(yōu)先”。

優(yōu)美度枚舉子程序B1調(diào)用基本算法A1進(jìn)行樹搜索。將優(yōu)美度枚舉子程序所調(diào)用的基本算法分別替換成Ai，可以得到一個(gè)優(yōu)美度枚舉子程序族Bi，其中1≤i≤12。

對(duì)于2.3節(jié)中的擬人型全局優(yōu)化算法A1B1來說，它基于基本算法A1和優(yōu)美度枚舉子程序B1，將A1和B1分別替換成Ai和Bi，可得到一個(gè)擬人型全局優(yōu)化算法族AiBi，其中1≤i≤12。

3 算法優(yōu)度的理論分析

定義17(布局優(yōu)度) 布局優(yōu)度是指在矩形容器內(nèi)的矩形塊的面積和。

定理1(優(yōu)度定理1) 優(yōu)美度枚舉子程序第i+1輪計(jì)算所得最優(yōu)布局的優(yōu)度高于或等于第i輪計(jì)算所得最優(yōu)布局的優(yōu)度。

證明從略。

定理2(優(yōu)度定理2) 第三優(yōu)化階段所得布局的優(yōu)度高于或等于第二優(yōu)化階段所得布局的優(yōu)度。

證明從略。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 二維矩形Strip Packing問題

本文算法是針對(duì)二維矩形Packing問題而設(shè)計(jì)的，也可用于求解二維矩形Strip Packing問題。Strip Packing問題是指：矩形容器的長(zhǎng)度W固定，在滿足“不出界、不傾斜、不重疊”三個(gè)約束條件的前提下，要求用寬度H盡可能小的矩形容器將所有矩形塊裝入。

除了“不出界、不傾斜、不重疊”以外，很多文獻(xiàn)中還可能考慮另外兩個(gè)約束條件：第一個(gè)約束條件是“一刀切”約束；第二個(gè)約束條件是關(guān)于矩形塊的方向：可旋轉(zhuǎn)90°或者方向固定。根據(jù)這兩個(gè)約束條件將二維矩形Strip Packing問題分為如下四個(gè)子類：第一，RF子類：矩形塊的方向可旋轉(zhuǎn)90°，不考慮“一刀切”約束。第二，RG子類：矩形塊的方向可旋轉(zhuǎn)90°，考慮“一刀切”約束。第三，OF子類：矩形塊的方向固定，不考慮“一刀切”約束。第四，OG子類：矩形塊的方向固定，考慮“一刀切”約束。

本文算法用于計(jì)算OF子類。算法計(jì)算了6組benchmark問題實(shí)例：(1)C組(21個(gè)實(shí)例)，由Hopper和Turton[18]提出；(2)N組(13個(gè)實(shí)例)，由Burke[19]等人提出；(3)NT組(70個(gè)實(shí)例)，由Hopper和Turton[18]提出；(4)CX組(7個(gè)實(shí)例)，由Ferreira和Oliveira[20]提出；(5)2SP組(38個(gè)實(shí)例)，其中cgcut1-cgcut3由Christofides和Whitlock[21]提出，gcut1-gcut13和ngcut1-ngcut12由Beasley[22]提出，beng1-beng10由Bengtsson[23]提出；(6)ZDF組(16個(gè)實(shí)例)，由Riff等人[24]、Leung和Zhang[12]提出。

4.2 擬人型全局優(yōu)化算法族求解Strip Packing問題

本文使用擬人型全局優(yōu)化算法族來計(jì)算二維矩形Strip Packing問題。思路為：首先依次調(diào)用AiBi算法族按照跳躍式查找的方式計(jì)算，直到將所有矩形塊放入矩形容器為止，然后用折半查找的方式進(jìn)一步縮小矩形容器的寬度，其中1≤i≤12。

具體計(jì)算步驟用偽C語(yǔ)言表示如下。

Step2調(diào)用AiBi算法族作跳躍式查找：

for(l=LB； ；l+=d){

finish_flag=0；

將矩形容器的寬度設(shè)定為l；

/*循環(huán)，依次調(diào)用算法族中的12個(gè)算法*/

for(i=1；i<=12；i++){

/*循環(huán)，依次選取不同的N值*/

for(N=5；N<=205；N+=100){

調(diào)用AiBi算法計(jì)算；

若矩形塊已全部放入矩形容器，則UB=l,finish_flag=1，break；}

if(finish_flag==1) break；}

if(finish_flag==1) break；}

if(UB==LB) 轉(zhuǎn)Step 4；

else 轉(zhuǎn)Step 3；

Step3調(diào)用AiBi算法族作折半查找：

head=UB-d+1；tail=UB-1；

while(head<=tail){

finish_flag=0；

mid=(head+tail)/2；

將矩形容器的寬度設(shè)定為mid；

for(i=1；i<=12；i++){

for(N=5；N<=205；N+=100){

調(diào)用AiBi算法計(jì)算；

若矩形塊已全部放入矩形容器，則UB=mid,finish_flag=1，break；}

if(finish_flag==1) break；}

if(finish_flag==1)tail=mid-1；

elsehead=mid+1；

}

Step4輸出UB值以及對(duì)應(yīng)的布局。

對(duì)上述算法步驟補(bǔ)充說明：N值是優(yōu)美度枚舉子程序的重要參數(shù)。N值較小時(shí)，計(jì)算時(shí)間較少，但可能漏掉好的占角動(dòng)作；N值較大時(shí)，花時(shí)間較多，可能發(fā)現(xiàn)更好的布局。本文設(shè)定N值從5開始，每次遞增100，到205為止。

4.3 算法計(jì)算結(jié)果

本文提出的擬人型全局優(yōu)化算法族AiBi用C語(yǔ)言實(shí)現(xiàn)，在CPU為3.0 GHz的個(gè)人電腦上做了測(cè)試。計(jì)算結(jié)果如表1～表5所示所示。

Table 1 Comparison of the computational results on the instances (OF)

AiBi與當(dāng)前文獻(xiàn)中幾種較先進(jìn)的算法做了比較。除了QH(Quasi-Human )算法[25]是一種非隨機(jī)型算法以外，GRASP(Greedy Randomized Adaptive Search Procedure)[11]、ISA(Intelligent Search Algorithm)[12]、IDBS(Iterative Doubling Binary Search)[13]、SRA(Simple Randomized Algorithm )[14]、HA(Hybrid Algorithm )[16]和AiBi算法均為隨機(jī)型算法。對(duì)每個(gè)問題實(shí)例，非隨機(jī)型算法只需計(jì)算一次，隨機(jī)型算法計(jì)算10次。

表1～表5中的符號(hào)含義列舉如下：對(duì)于一個(gè)問題實(shí)例(Instance)來說，n表示矩形塊數(shù)，W表示矩形容器的長(zhǎng)度(固定值)，H*表示矩形容器的寬度的最小值或最小值的下界，H表示非隨機(jī)型算法所算出的矩形容器寬度，T表示計(jì)算時(shí)間，單位為s。對(duì)于隨機(jī)型算法來說，AH和BH分別表示10次計(jì)算所得到的矩形容器寬度的算術(shù)平均值和最小值。AT則表示10次計(jì)算時(shí)間的算術(shù)平均值。

表1給出了算法計(jì)算6組共165個(gè)benchmark實(shí)例的平均相對(duì)誤差，AiBi的平均相對(duì)誤差為1.05，在參加比較的7個(gè)算法中最小。

表2給出了算法計(jì)算C組實(shí)例的結(jié)果。AiBi的計(jì)算時(shí)間略長(zhǎng)于QH算法，但所生成解的質(zhì)量較高。除了C19和C21兩個(gè)實(shí)例以外，對(duì)本組其它19個(gè)實(shí)例均能算出最優(yōu)解。

表3給出了算法計(jì)算N組實(shí)例的結(jié)果。AiBi算法生成了全部實(shí)例的最優(yōu)解。

表4給出了算法計(jì)算CX組實(shí)例的結(jié)果。AiBi算法所生成布局的優(yōu)度與QH算法相當(dāng)。

表5給出了算法計(jì)算ZDF組實(shí)例的結(jié)果。除zdf6和zdf7以外，對(duì)本組其它19個(gè)實(shí)例均能算出最優(yōu)解。算法對(duì)zdf6和zdf7所生成的布局刷新了當(dāng)前文獻(xiàn)中已報(bào)道的記錄。

Table 2 Computational results on the instances C (OF)

Table 3 Computational results on the instances N(OF)

Table 4 Computational results on the instances CX(OF)

Table 5 Computational results on the instances ZDF(OF)

GRASP、ISA、IDBS、SRA、HA算法的每次計(jì)算的時(shí)間上限均為60 s。

AiBi算法計(jì)算所需時(shí)間總體上較長(zhǎng)，生成布局的質(zhì)量較高。在對(duì)布局質(zhì)量要求高且計(jì)算時(shí)間限制較寬松的應(yīng)用場(chǎng)景有其實(shí)用價(jià)值。

5 結(jié)束語(yǔ)

以占角式基本算法為基礎(chǔ)，本文提出了一種三階段擬人型全局優(yōu)化算法，由鄰域搜索、跳坑策略、優(yōu)美度枚舉組成。對(duì)benchmark問題實(shí)例的測(cè)試結(jié)果表明，算法生成布局的優(yōu)度較高。

[1] Huang Wen-qi,Chen Duan-bing,Xu Ru-chu.A new heuristic algorithm for rectangle packing [J].Computers & Operations Research,2007,34(11):3270-3280.

[2] He Kun,Ji Peng-li,Li Chu-min.Dynamic reduction heuristics for the rectangle packing area minimization problem [J].European Journal of Operational Research,2015,241(3):674-685.

[3] Alvarez-Valdes R, Parreno F, Tammrit J M.A branch and bound algorithm for the strip packing problem [J].OR Spectrum,2009,31(2):431-459.

[4] Jiang Xing-bo, Lü Xiao-qing,Liu Cheng-cheng.Lowest-level left align best-fit algorithm for the 2D rectangular strip packing problem[J].Journal of Software,2009,20(6):1528-1538.(in Chinese)

[5] Cui Yao-dong, Yang Yu-li, Cheng Xian,et al.A recursive branch-and-bound algorithm for the rectangular guillotine strip packing problem[J].Computers & Operations Research,2008,35(4):1281-1291.

[6] He Kun, Huang Wen-qi,Jin Yan.Efficient algorithm based on action space for solving the 2D rectangular packing problem[J].Journal of Software,2012,23(5):1037-1044.(in Chinese)

[7] Wang Lei, Yin Ai-hua. A beauty degree enumeration algorithm for the 2D rectangular packing problem[J].Scientia Sinica Informationis,2015,45(9):1127-1140.(in Chinese)

[8] Huang Wen-qi,Chen Duan-bing.An efficient heuristic algorithm for rectangle-packing problem[J].Simulation Modelling and Practice Theory,2007,15(10):1356-1365.

[9] He Kun,Huang Wen-qi.An efficient place heuristic for three-dimensional rectangular packing[J].Computers & Operations Research,2011,38(1):227-233.

[10] Huang Wen-qi,He Kun.A pure quasi-human algorithm for solving the cuboid packing problem[J].Science in China Series F:Information Sciences,2009,52(1):52-58.

[11] Alvarez-Valdes R, Parreno F,Tammrit J M.Reactive GRASP for the strip-packing problem[J].Computers & Operations Research,2008,35(4):1065-1083.

[12] Leung S C H, Zhang De-fu.A two-stage intelligent search algorithm for the two-dimensional strip packing problem[J].European Journal of Operational Research,2011,215(1):57-69.

[13] Wei Li-jun,Oon Wee-chong, Zhu Wen-bin, et al. A skyline heuristic for the 2D rectangular packing and strip packing problems[J].European Journal of Operational Research,2011,215(2):337-346.

[14] Yang Shuang-yuan, Han Shui-hua, Ye Wei-guo.A simple randomized algorithm for two-dimensional strip packing[J].Computers & Operations Research,2013,40(1):1-8.

[15] Wei Li-jun, Qin Hu, Cheang B, et al.An efficient intelligent search algorithm for the two-dimensional rectangular strip packing problem[J].International Transactions in Operational Research,2016,232(1-2):65-92.

[16] Zhang De-fu,Che Yu-xin,Ye Fu-rong,et al.A hybrid algorithm based on variable neighborhood for the strip packing problem[J].Journal of Combinatorial Optimization,2016,32(2):513-530.

[17] He Kun,Huang Wen-qi,Jin Yan.An efficient deterministic heuristic for two-dimensional rectangular packing[J].Computers & Operations Research,2012,39(7):1355-1363.

[18] Hopper E,Turton B.An empirical investigation of metaheuristic and heuristic algorithms for a 2D packing problem[J].European Journal of Operational Research,2001,128(1):34-57.

[19] Burke E,Kendall G,Whitwell G.A new placement heuristic for the orthogonal stock-cutting problem[J].Operations Research,2004,52(4):655-671.

[20] Ferreira E P, Oliveira J F.Algorithm based on graphs for the non-guillotinable two-dimensional packing problem[C]∥Proc of the 2nd ESICUP Meeting,2005:131-135.

[21] Christofides N, Whitlock C.An algorithm for two-dimensional cutting problem[J].Operations Research,1977,25(1):30-44.

[22] Beasley J. An exact two-dimensional non-guillotine cutting tree search procedure[J].Operations Research,1985,33(1):49-64.

[23] Bengtsson B E.Packing rectangular pieces-a heuristic approach[J].Computer Journal,1982,25(3):253-257.

[24] Riff M C,Bonnaire X,Neveu B.A revision of recent approaches for two-dimensional strip-packing problems[J].Engineering Applications of Artificial Intelligence,2009,22(4-5):823-827.

[25] Wang Lei,Yin Ai-hua.A quasi-human algorithm for the two dimensional rectangular strip packing problem:in memory of Prof.Wenqi Huang[J].Journal of Combinatorial Optimization,2016,32(2):416-444.

附中文參考文獻(xiàn)：

[4] 蔣興波,呂肖慶,劉成城.二維矩形條帶裝箱問題的底部左齊擇優(yōu)匹配算法[J].軟件學(xué)報(bào),2009,20(6):1528-1538.

[6] 何琨,黃文奇,金燕.基于動(dòng)作空間求解二維矩形Packing問題的高效算法[J].軟件學(xué)報(bào),2012,23(5):1037-1044.

[7] 王磊,尹愛華.求解二維矩形Packing問題的一種優(yōu)美度枚舉算法[J].中國(guó)科學(xué)(信息科學(xué)),2015,45(9):1127-1140.