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

甄士剛，王金敏

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

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

1 三維矩形布局問題

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

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

式中：lk、wk、hk分別為第k個已布入矩形塊的長、寬、高；n為布入的矩形塊塊數。布局結果由體積利用率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）保證兩布入物體之間不發生干涉。

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

2 基于評價函數的構造啟發式算法

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

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

2.1 定序規則

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

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

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

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

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

2.2 定位規則

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

定位評價函數的具體形式為：

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

圖1 吸引子位置

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

3 布局遺傳算法

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

3.1 遺傳算法

3.1.1 編碼策略

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

3.1.2 適應度函數及初始化

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

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

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

3.1.3 選擇算子

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

①選取第N代種群中的最優個體與上一代蜂王（適應度最好值）比較，優勝者作為第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]之間的數代替這個基因。

3.2 布局遺傳算法流程

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

具體步驟如下：

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

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

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

④N=N+1。

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

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

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

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

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

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

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

?轉到④。

4 算例分析

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

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

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

表1中利用率為平均利用率，是將100個算例最終結果相加取平均得到。對于這些算例，很多學者都進行了研究測試。Bischoff等[10]提出啟發式算法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 結束語

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

［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］王金敏，楊維嘉.動態吸引子在布局求解中的應用［J］.計算機輔助設計與圖形學學報，2005，17（8）：1725－1729.

［8］王小平，曹立明.遺傳算法—理論、應用與軟件實現［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.