甄士剛，王金敏

（天津職業(yè)技術(shù)師范大學(xué)機(jī)械工程學(xué)院，天津 300222）

布局問(wèn)題廣泛存在于生產(chǎn)生活實(shí)際中，例如貨物的運(yùn)輸、機(jī)械零部件的分布、車(chē)間廠房的布置等，對(duì)布局問(wèn)題的有效解決，具有極大的現(xiàn)實(shí)意義。長(zhǎng)期以來(lái)，人們主要通過(guò)啟發(fā)式算法[1]解決布局問(wèn)題。例如張德富等[2]將構(gòu)造啟發(fā)式算法與模擬退火算法結(jié)合，提出一種求解三維布局問(wèn)題的混合模擬退火算法；Bortfeldt等[3]將多線程搜索應(yīng)用于禁忌搜索算法，提出一種并行禁忌搜索算法；Gehring等[4]提出了解決三維布局問(wèn)題的并行遺傳算法；Parreno等[5]基于最大空間概念的構(gòu)造堆算法，進(jìn)一步發(fā)展和改進(jìn)了一種貪心隨機(jī)自適應(yīng)搜索算法；He等[6]基于古語(yǔ)“金角銀邊草肚皮”提出一種針對(duì)三維矩形布局問(wèn)題的高效定位啟發(fā)式算法。本文針對(duì)三維矩形布局問(wèn)題，通過(guò)將構(gòu)造啟發(fā)式算法的定位和定序結(jié)合，提出一種基于評(píng)價(jià)函數(shù)的布局遺傳算法。

1 三維矩形布局問(wèn)題

三維矩形布局問(wèn)題的數(shù)學(xué)模型描述如下：

設(shè)布局空間的體積為V，布局空間的體積利用率為f，則目標(biāo)函數(shù)

式中：lk、wk、hk分別為第k個(gè)已布入矩形塊的長(zhǎng)、寬、高；n為布入的矩形塊塊數(shù)。布局結(jié)果由體積利用率f來(lái)衡量，f值越大布局結(jié)果越好。約束條件

式中：L、W、H分別表示布局容器的長(zhǎng)、寬、高；（xi，yi，zi）和（xj，yj，zj）分別為第i個(gè)和第j個(gè)已布入物體的中心點(diǎn)坐標(biāo)，且i≠j，i、j∈k。這里布局容器的左下前角為坐標(biāo)原點(diǎn)（0，0，0）。li、wi、hi和lj、wj、hj分別為第i個(gè)和第j個(gè)已布入矩形塊的長(zhǎng)、寬、高。式（2）（3）（4）保證物體完全布入到布局空間中，式（5）（6）（7）保證兩布入物體之間不發(fā)生干涉。

另外，本文算法中矩形空間以及矩形塊的長(zhǎng)>寬>高，矩形塊的長(zhǎng)寬高尺寸不做交換，即矩形塊滿(mǎn)足方向約束，在布局過(guò)程中不可以旋轉(zhuǎn)。

2 基于評(píng)價(jià)函數(shù)的構(gòu)造啟發(fā)式算法

構(gòu)造啟發(fā)式算法通過(guò)一個(gè)一個(gè)地增加解的構(gòu)造元素來(lái)求得可行解，它的循環(huán)次數(shù)與問(wèn)題解的構(gòu)造元素個(gè)數(shù)成正比，而與解空間的大小無(wú)關(guān)，因此，計(jì)算速度很快。

布局問(wèn)題中的構(gòu)造啟發(fā)式算法主要由定序規(guī)則和定位規(guī)則所決定，不同的定序規(guī)則和定位規(guī)則可以產(chǎn)生不同的構(gòu)造布局算法。定序規(guī)則確定每一個(gè)矩形塊放入布局空間中的先后順序；定位規(guī)則確定每一個(gè)矩形塊在布局空間中的擺放位置。定序和定位規(guī)則一旦確定，布局過(guò)程也就確定。本文所采用的定序規(guī)則和定位規(guī)則介紹如下。

2.1 定序規(guī)則

通常，人們通過(guò)比較矩形塊的某一項(xiàng)或某幾項(xiàng)屬性（如體積、面積等）來(lái)建立定序規(guī)則。本文提出一種基于評(píng)價(jià)函數(shù)的定序規(guī)則。評(píng)價(jià)函數(shù)為：

式中：vi、li、wi、hi分別為第i個(gè)布局塊的體積、長(zhǎng)、寬、高；v、l、w、h分別為布局空間的體積、長(zhǎng)、寬、高；α、β、χ、δ均為參數(shù)，且α+β+χ+δ=1。

本文算法先確定α、β、χ、δ這4個(gè)參數(shù)值，然后根據(jù)已知矩形塊和布局空間的長(zhǎng)寬高計(jì)算出每個(gè)矩形塊對(duì)應(yīng)的函數(shù)值。當(dāng)所有矩形塊計(jì)算完之后，依據(jù)從大到小的順序?qū)瘮?shù)值進(jìn)行排序。函數(shù)值的排列順序也就是相應(yīng)矩形塊的布局順序。例如最大函數(shù)值對(duì)應(yīng)標(biāo)號(hào)為5的矩形塊，那么標(biāo)號(hào)為5的矩形塊將首先布局。

該定序規(guī)則包含了一般情況下人們所使用的定序規(guī)則。在式（8）所示評(píng)價(jià)函數(shù)中取α=1，其余參數(shù)得0。這時(shí)按照評(píng)價(jià)函數(shù)函數(shù)值遞減布局，也就是按照體積遞減布局。在式（8）中，當(dāng)取β=1，其余參數(shù)得0。結(jié)果恰好是按照最長(zhǎng)邊遞減布局。

若是2個(gè)或2個(gè)以上矩形塊評(píng)價(jià)函數(shù)函數(shù)值相等，則先計(jì)算函數(shù)值的矩形塊先于其他矩形塊布入。

2.2 定位規(guī)則

本文采用吸引子定位評(píng)價(jià)函數(shù)對(duì)矩形塊進(jìn)行定位。吸引子法可參見(jiàn)文獻(xiàn)[7]。

定位評(píng)價(jià)函數(shù)的具體形式為：

式中：f（xi，yi，zi）為總的定位評(píng)價(jià)函數(shù)；fi（xi，yi，zi）為關(guān)于各個(gè)吸引子的定位評(píng)價(jià)函數(shù)；m為吸引子的個(gè)數(shù)，這里m=4；t=1、2、3、4表示吸引子分別位于布局空間4個(gè)角點(diǎn)，如圖1中4個(gè)黑點(diǎn)所示；xot、yot、zot代表吸引子在布局空間中的3個(gè)坐標(biāo)；ωt為各個(gè)吸引子定位函數(shù)之間的權(quán)重為每個(gè)吸引子定位函數(shù)內(nèi)部權(quán)重，αt+ βt+ γt=1。

圖1 吸引子位置

類(lèi)似定序規(guī)則的建立，定位規(guī)則首先確定定位評(píng)價(jià)函數(shù)的12個(gè)參數(shù)。然后通過(guò)比較備選布局點(diǎn)的函數(shù)值，將函數(shù)值最小的備選點(diǎn)作為矩形塊的布局位置。

3 布局遺傳算法

基于評(píng)價(jià)函數(shù)的構(gòu)造啟發(fā)式算法共有15個(gè)可供選擇的參數(shù)。參數(shù)值不同，布局過(guò)程不同，布局結(jié)果也不同。要想使布局空間利用率最大，需要找到與之對(duì)應(yīng)的15個(gè)參數(shù)的參數(shù)值。顯然，三維矩形布局問(wèn)題的求解可化為一個(gè)15維的函數(shù)優(yōu)化問(wèn)題。本文采用遺傳算法[8]來(lái)優(yōu)化參數(shù)?；谠u(píng)價(jià)函數(shù)的構(gòu)造啟發(fā)式算法加上遺傳算法優(yōu)化構(gòu)成布局遺傳算法。

3.1 遺傳算法

3.1.1 編碼策略

采用實(shí)數(shù)編碼的方式，每個(gè)染色體是變量為20維的解向量。編碼向量表示為：S=（B1，B2，…，B20）。各個(gè)分向量分別對(duì)應(yīng)算法的20個(gè)參數(shù)。

3.1.2 適應(yīng)度函數(shù)及初始化

算法的適應(yīng)度函數(shù)取布局空間的體積利用率f。適應(yīng)度值越大，布局空間的利用率就越大，個(gè)體的性能也就越好。

本文在產(chǎn)生初始種群時(shí)，采用如下方式進(jìn)行：

首先由計(jì)算機(jī)隨機(jī)產(chǎn)生，然后再做歸一化處理得到具體參數(shù)值。例如，隨機(jī)之后B1=0.7，B2=0.6，B3=0.4，B4=0.3；為保證參數(shù)之和等于1，分別用各個(gè)參數(shù)除以4個(gè)參數(shù)之和，結(jié)果對(duì)應(yīng)定序評(píng)價(jià)函數(shù)α=0.7/（0.7+0.6+0.4+0.3）=0.35，同理 β=0.3，χ=0.2，δ=0.15。

3.1.3 選擇算子

在選擇配對(duì)個(gè)體時(shí)采用蜜蜂進(jìn)化選擇法[9]，其主要步驟：

①選取第N代種群中的最優(yōu)個(gè)體與上一代蜂王（適應(yīng)度最好值）比較，優(yōu)勝者作為第N代蜂王，記為Queen。

②通過(guò)選擇算子從第N代種群中選出（n/2）λ（0≤λ≤1）個(gè)個(gè)體，隨后隨機(jī)產(chǎn)生（n/2）（1- λ）個(gè)個(gè)體。

③上述（n/2）個(gè)個(gè)體和第N代蜂王作為配對(duì)交叉的父本。

3.1.4 交叉算子

令選擇算子中的Queen分別與上述（n/2）個(gè)個(gè)體交叉配對(duì)。具體交叉策略為：

（1）單點(diǎn)交叉。隨機(jī)生成一個(gè)交叉位點(diǎn)，將兩父代中交叉位點(diǎn)之前的基因進(jìn)行整體交換，被交換基因之間的相對(duì)順序不變，從而生成2個(gè)新的子代個(gè)體；

（2）雙點(diǎn)交叉。隨機(jī)生成2個(gè)交叉位點(diǎn)，將兩父代交叉位點(diǎn)之間的基因進(jìn)行整體交換，被交換基因之間的相對(duì)順序不變，從而生成2個(gè)新的子代個(gè)體。

3.1.5 變異算子

對(duì)當(dāng)前種群中的個(gè)體進(jìn)行變異操作，是產(chǎn)生新解和維持種群多樣性的有效手段。本算法采用均勻變異：設(shè)新的個(gè)體中的分向量為Xk；k∈N且k∈[1，20]，隨機(jī)產(chǎn)生一個(gè)變異位，用新產(chǎn)生的[0，1]之間的數(shù)代替這個(gè)基因。

3.2 布局遺傳算法流程

算法首先設(shè)定進(jìn)化代數(shù)N、交叉概率PXOVER、變異概率PMUTATION以及蜜蜂進(jìn)化選擇算子比例系數(shù)λ，然后隨機(jī)產(chǎn)生初始種群，計(jì)算個(gè)體適應(yīng)度。算法以最大進(jìn)化代數(shù)作為停止條件，若滿(mǎn)足停止條件，則停止計(jì)算；否則，對(duì)個(gè)體進(jìn)行選擇、交叉、變異操作。當(dāng)滿(mǎn)足終止條件時(shí)，輸出優(yōu)化參數(shù)值和布局方案。

具體步驟如下：

①設(shè)定最大進(jìn)化代數(shù)、交叉變異概率以及蜜蜂進(jìn)化選擇算子系數(shù)，隨機(jī)生成初始種群。

②基于初始種群確定的20個(gè)參數(shù)的參數(shù)值，計(jì)算出各個(gè)矩形塊的評(píng)價(jià)函數(shù)值，得出相應(yīng)的定序和定位規(guī)則，實(shí)現(xiàn)布局過(guò)程。

③計(jì)算種群中所有個(gè)體的適應(yīng)度，將最優(yōu)個(gè)體（即第N=0代蜂王）保存到best中。

④N=N+1。

⑤如果滿(mǎn)足停止條件，算法輸出結(jié)果并停止運(yùn)行；否則，繼續(xù)。

⑥利用蜜蜂進(jìn)化選擇算子，從A（N-1）中選出父代個(gè)體。

⑦父代個(gè)體進(jìn)行交叉操作產(chǎn)生種群B（N）。

⑧對(duì)B（N）執(zhí)行變異操作，得到種群C（N）。

⑨基于種群C（N）確定的20個(gè)參數(shù)的參數(shù)值，計(jì)算出各個(gè)矩形塊的評(píng)價(jià)函數(shù)值，得出相應(yīng)的定序和定位規(guī)則，實(shí)現(xiàn)布局過(guò)程。

⑩計(jì)算種群C（N）中所有個(gè)體的適應(yīng)度，將適應(yīng)度最大的個(gè)體記為newbest。

?如果newbest的適應(yīng)度值大于best的適應(yīng)值，用newbest代替best；否則，用newbest代替C（N）中最差的個(gè)體；得到第N代種群。

?轉(zhuǎn)到④。

4 算例分析

本文的基于評(píng)價(jià)函數(shù)的布局遺傳算法采用C++實(shí)現(xiàn)，計(jì)算環(huán)境為：Pentium D C-PU，2 GB內(nèi)存，2.79 GHz PC機(jī)。在以下計(jì)算中，算法進(jìn)化代數(shù)、交叉概率、變異概率以及蜜蜂選擇算子的比例系數(shù)分別取N=20，PXOVER=0.85，PMUTATION=0.15，λ =0.8。具體計(jì)算中，每組數(shù)據(jù)計(jì)算10次，選取最好的計(jì)算結(jié)果作為最終結(jié)果。

本文采用文獻(xiàn)[10]的后6組數(shù)據(jù)。每組有100個(gè)算例。所有矩形塊的尺寸均為整數(shù)，矩形塊的長(zhǎng)寬高尺寸區(qū)間分別為[30，120]、[25，100]和[20，80]。具體的算例計(jì)算和比較結(jié)果見(jiàn)表1。

表1 各算法計(jì)算結(jié)果的利用率%

表1中利用率為平均利用率，是將100個(gè)算例最終結(jié)果相加取平均得到。對(duì)于這些算例，很多學(xué)者都進(jìn)行了研究測(cè)試。Bischoff等[10]提出啟發(fā)式算法H_BR；Gehring等[11]提出GA_GB算法；Bortfeld等[12－13]提出禁忌搜索法TS_BG和混合遺傳算法HGA_BG以及并行遺傳算法PGA_GB[4]；Moura等[14]提出GRASP算法。

從表1可以看出，BR14、BR15高出了其他所有算法結(jié)果，BR15高出對(duì)應(yīng)最大值1.33%，BR14高出對(duì)應(yīng)最大值0.94%。算例BR10—BR13結(jié)果雖然沒(méi)能高出其它所有算法，但是均高于上述其余6個(gè)算法結(jié)果中的4～5個(gè)，整體來(lái)看算法效果良好。

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

本文針對(duì)三維矩形布局問(wèn)題，通過(guò)提出基于評(píng)價(jià)函數(shù)的定序和定位規(guī)則，創(chuàng)造性地將決定定序和定位規(guī)則的參數(shù)編碼于同一個(gè)基因向量中，從而將布局問(wèn)題轉(zhuǎn)化為參數(shù)優(yōu)化問(wèn)題。經(jīng)過(guò)算例測(cè)試和分析，本文算法取得了良好的計(jì)算結(jié)果。另外，算法也存在一些需要解決的問(wèn)題，例如，如何通過(guò)初始化參數(shù)的方法進(jìn)一步優(yōu)化布局結(jié)果，如何通過(guò)將本文基于評(píng)價(jià)函數(shù)的定序規(guī)則與分割空間策略結(jié)合來(lái)進(jìn)一步優(yōu)化布局結(jié)果，這將是今后的工作內(nèi)容。

［1］SWEENEY P E，PATEMOSTER E R.Cutting and packing problems：A categorized，application－oriented research bibliography[J].TheJournalofOperational Research Socitey，1992，43（7）：691－706.

［2］張德富，彭煜，朱文興，等.求解三維裝箱問(wèn)題的混合模擬退火算法［J］.計(jì)算機(jī)學(xué)報(bào)，2009，32（11）：2147－2156.

［3］BORTFELD T A，GEHRING H，MACK D.A parallel tabu search algorithm for solving the container loading problem［J］.Parallel Computing，2003，29（5）：641－662.

［4］GEHRING H，BORTFELD T A.A parallel genetic algorithm for solving the container loading problem ［J］.International Trasactions in Operational Research，2002，9（4）：497－511.

［5］PARRENO F，ALVAREZ－VALDES R，OLIVEIRA J F，et al.A maximal－space algorithm for the container loading problem［J］.INFORMS Journal on Computing，2007，20（3）：412－422.

［6］HE K，HUANG W.An efficient placement heuristic for threedimensional rectangular packing［J］.Computers&Operations Research，2011，38（1）：227－233.

［7］王金敏，楊維嘉.動(dòng)態(tài)吸引子在布局求解中的應(yīng)用［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2005，17（8）：1725－1729.

［8］王小平，曹立明.遺傳算法—理論、應(yīng)用與軟件實(shí)現(xiàn)［M］.西安：西安交通大學(xué)出版社，2002.

［9］孟偉，韓學(xué)東，洪炳熔.蜜蜂進(jìn)化型遺傳算法［J］.電子學(xué)報(bào)，2006，7（34）：1294－1300.

［10］BISCHOFF E E，RATCLIFFB S W.Issues in the development of approaches to container loading［J］.Omega，1995，23（3）：377－390.

［11］GEHRING H，BORTFELDTA.A genetic algorithm for solving the container loading problem［J］.International Transactions in Operational Research，1997，4（6）：401－418.

［12］BORTFELD T A，GEHRING H.A tabu search algorithm for weakly heterogeneous container loading problems［J］.OR Spectrum，1998，20（4）：237－250.

［13］BORTFELD T A，GEHRING H.A hybrid genetic algorithm for the container loading problem［J］.European Journal of Operational Research，2001，131（1）：143－161.

［14］MOURA A，OLIVEIRA J F.A GRASP approach to the container loading problem［J］.IEEE Intelligent Systems，2005，20（4）：50－57.