一種基于評價函數(shù)的三維矩形布局遺傳算法

甄士剛，王金敏

（天津職業(yè)技術師范大學機械工程學院，天津 300222）

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

1 三維矩形布局問題

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

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

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

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

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

2 基于評價函數(shù)的構造啟發(fā)式算法

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

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

2.1 定序規(guī)則

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

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

本文算法先確定α、β、χ、δ這4個參數(shù)值，然后根據(jù)已知矩形塊和布局空間的長寬高計算出每個矩形塊對應的函數(shù)值。當所有矩形塊計算完之后，依據(jù)從大到小的順序對函數(shù)值進行排序。函數(shù)值的排列順序也就是相應矩形塊的布局順序。例如最大函數(shù)值對應標號為5的矩形塊，那么標號為5的矩形塊將首先布局。

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

若是2個或2個以上矩形塊評價函數(shù)函數(shù)值相等，則先計算函數(shù)值的矩形塊先于其他矩形塊布入。

2.2 定位規(guī)則

本文采用吸引子定位評價函數(shù)對矩形塊進行定位。吸引子法可參見文獻[7]。

定位評價函數(shù)的具體形式為：

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

圖1 吸引子位置

類似定序規(guī)則的建立，定位規(guī)則首先確定定位評價函數(shù)的12個參數(shù)。然后通過比較備選布局點的函數(shù)值，將函數(shù)值最小的備選點作為矩形塊的布局位置。

3 布局遺傳算法

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

3.1 遺傳算法

3.1.1 編碼策略

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

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

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

本文在產生初始種群時，采用如下方式進行：

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

3.1.3 選擇算子

在選擇配對個體時采用蜜蜂進化選擇法[9]，其主要步驟：

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

②通過選擇算子從第N代種群中選出（n/2）λ（0≤λ≤1）個個體，隨后隨機產生（n/2）（1- λ）個個體。

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

3.1.4 交叉算子

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

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

（2）雙點交叉。隨機生成2個交叉位點，將兩父代交叉位點之間的基因進行整體交換，被交換基因之間的相對順序不變，從而生成2個新的子代個體。

3.1.5 變異算子

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

3.2 布局遺傳算法流程

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

具體步驟如下：

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

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

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

④N=N+1。

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

⑥利用蜜蜂進化選擇算子，從A（N-1）中選出父代個體。

⑦父代個體進行交叉操作產生種群B（N）。

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

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

⑩計算種群C（N）中所有個體的適應度，將適應度最大的個體記為newbest。

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

?轉到④。

4 算例分析

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

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

表1 各算法計算結果的利用率%

表1中利用率為平均利用率，是將100個算例最終結果相加取平均得到。對于這些算例，很多學者都進行了研究測試。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高出了其他所有算法結果，BR15高出對應最大值1.33%，BR14高出對應最大值0.94%。算例BR10—BR13結果雖然沒能高出其它所有算法，但是均高于上述其余6個算法結果中的4～5個，整體來看算法效果良好。

5 結束語

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

［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］張德富，彭煜，朱文興，等.求解三維裝箱問題的混合模擬退火算法［J］.計算機學報，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］王金敏，楊維嘉.動態(tài)吸引子在布局求解中的應用［J］.計算機輔助設計與圖形學學報，2005，17（8）：1725－1729.

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

［9］孟偉，韓學東，洪炳熔.蜜蜂進化型遺傳算法［J］.電子學報，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.