王金敏， 朱麗蘋， 甄士剛

(1. 天津市高速切削與精密加工重點實驗室，天津 300222；2. 天津職業(yè)技術(shù)師范大學(xué)機械工程學(xué)院，天津 300222)

一種基于蜜蜂進化選擇算子的布局遺傳算法

王金敏1,2， 朱麗蘋2， 甄士剛2

(1. 天津市高速切削與精密加工重點實驗室，天津 300222；2. 天津職業(yè)技術(shù)師范大學(xué)機械工程學(xué)院，天津 300222)

三維矩形布局問題屬于NP難問題，對于三維矩形布局問題的求解大多依賴于各種啟發(fā)式算法。該文以布局物體體積遞減為定序規(guī)則，結(jié)合布局物體在布局空間中的幾何可行域，以吸引子法為定位規(guī)則，利用蜜蜂進化型遺傳算法優(yōu)化吸引子函數(shù)中的參數(shù)來求解三維矩形布局問題(BEGA)，得到新型布局遺傳算法。最后對不同的算例進行了計算，并與以標(biāo)準(zhǔn)比例選擇作為選擇算子的傳統(tǒng)布局遺傳算法(SPGA)等對比證明了該算法的有效性。

布局問題；啟發(fā)式算法；吸引子；蜜蜂進化

布局問題[1-2]廣泛存在于生產(chǎn)生活實際中，如運輸、下料、剪裁、排版等。解決好布局問題無疑具有巨大的現(xiàn)實意義。布局問題可以定義為給定布局空間和若干布局物體，將布局物體合理地布置到布局空間中并滿足某種最優(yōu)指標(biāo)。這些指標(biāo)通常是使布局空間利用率最大、布局成本最小等。學(xué)術(shù)界已經(jīng)證明布局問題屬于非確定多項式(non-deterministic polynomial，NP)難問題。對于NP難問題，普通的精確性求解算法難以建立合適的數(shù)學(xué)模型及找到問題的全局最優(yōu)解，因此長期以來大多布局問題的求解依賴于各種啟發(fā)式算法。如Zhang等[3]提出了一種分層算法，分別利用深度和廣度優(yōu)先搜索方法來解決布局問題。Leung等[4]提出一種混合模擬退火啟發(fā)式算法，其應(yīng)用適應(yīng)函數(shù)評價準(zhǔn)則動態(tài)地確定一個布局序列，再利用貪心算法確定布局物體的最佳放置位置。Burke等[5]提出了一種基于遺傳算法的超啟發(fā)式算法，它強調(diào)通過搜索空間的辦法來構(gòu)建布局方案而不是直接的尋找一個解決方案，所以它的程序輸出是一種啟發(fā)式算法而不是布局塊的布置信息。Cintra和Miyazawa[6]使用縱列碼遺傳算法和動態(tài)編程方法解決了二維裝填問題。楊林等[7]提出了一種分布式評估算法，該算法是基于概率模型的遺傳算法，它沒有遺傳算法中的交叉、變異運算，后代個體是根據(jù)評估父代種群中個體的概率分布情況而產(chǎn)生的。Bischoff和Ratcliff[8]針對當(dāng)時算法應(yīng)用面狹窄這一事實，提出兩種分別針對均勻和非均勻布局塊的方案，當(dāng)二者結(jié)合使用為解決三維裝載問題提供了強大的通用性工具。Gehring和Bortfeldt[9]通過將三維待布局塊組成互不相連的塔狀，然后結(jié)合遺傳算法來解決三維布局問題。Bortfeldt和Gehring[10]通過將一種改進之后的禁忌搜索算法應(yīng)用在三維布局問題上，來解決此類問題。Lim等[11]通過將三維裝載問題分割為箱體選擇、空間選擇、箱體旋轉(zhuǎn)和新空間的產(chǎn)生四部分，利用設(shè)計好的基礎(chǔ)啟發(fā)式算法和兩種增強啟發(fā)式算法來解決布局問題。Moura和 Oliveira[12]等為了解決容器裝載問題，提出一種砌墻構(gòu)造啟發(fā)式算法，并應(yīng)用智能啟發(fā)式算法(greedy randomized adaptive search procedure，GRASP)優(yōu)化。本文通過蜜蜂進化選擇算子的遺傳算法與吸引子定位函數(shù)相結(jié)合的方法對三維矩形布局問題進行了研究，提出一種新的啟發(fā)式算法，并通過與傳統(tǒng)布局遺傳算法(search packing genetic algorithm，SPGA)等算法對比驗證了它的有效性。

1 三維矩形布局問題

1.1 問題描述

本文對三維矩形布局問題進行研究，布局容器及物體均為長方體(三維矩形)。令布局容器的體積為V，第i個布入的布局物體的長、寬和高分別為li、 wi和 hi，布局空間的體積利用率設(shè)為 f，則其中，n為布入的布局物體塊數(shù)，布局結(jié)果的優(yōu)劣由體積利用率f值的大小來衡量，f值越大說明布局結(jié)果越好。

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

式中，L、W、H分別表示布局容器的長度、寬度和高度；（ xi,yi,zi） 和（ xj,yj,zj）分別為第i個和第j個已布入的布局物體的中心點坐標(biāo)，且i ≠ j。這里布局容器的左下前角為坐標(biāo)原點(0，0，0)；li、wi、 hi和 lj、 wj、 hj分別為第i個和第j個布入的三維矩形塊的長度、寬度和高度。式①~③保證布局物體完全布入到布局空間中，式④~⑥保證兩布入布局物體之間不能發(fā)生干涉。

1.2 基于吸引子法的布局過程

基于吸引子法的布局是布局構(gòu)造啟發(fā)式算法的一種。布局構(gòu)造啟發(fā)式算法主要從定序規(guī)則和定位規(guī)則兩方面來進行考慮。

(1) 定序規(guī)則，即通過比較布局塊的某一項或某幾項屬性來決定布局物體放入的順序。常見的定序規(guī)則主要有按布局物體最長邊遞減、按布局物體體積遞減、按布局物體可行域遞減等順序來對布局物體進行排列。本文采用體積遞減的定序原則，來確定布局物體放入容器的順序。

(2) 定位規(guī)則，即確定布局物體的擺放位置，本文采用吸引子定位函數(shù)結(jié)合布局塊的幾何可行域[13]計算出的數(shù)值來對布局物體進行定位。吸引子法可描述為在空間中設(shè)置一些吸引子，使布局物體由于其“吸引作用”而向吸引子移動，從而對布局物體進行定位。吸引子法具體見文獻(xiàn)[14]。

待布長方體i的定位函數(shù)的具體形式為：

f(xi,yi,zi)為總的定位函數(shù)， ft(xi,yi,zi)為關(guān)于各個吸引子的定位函數(shù)，m為吸引子的個數(shù)，這里t=1、2、3、4表示吸引子分別位于布局空間 4個角點。

定位函數(shù)的參數(shù)有許多可供選擇的參數(shù)值。對于不同的參數(shù)值，定位函數(shù)所得到的結(jié)果會不同，布局物體的布入結(jié)果更會完全不一樣，故參數(shù)值的選擇是布局求解的關(guān)鍵，也是本文的研究重點。顯然，三維矩形布局問題的求解可化為一個 16維函數(shù)的優(yōu)化問題。

2 布局遺傳算法(BEGA)

2.1 算法流程

本文提出了基于蜜蜂進化選擇算子的吸引子布局遺傳算法(BEGA)。算法首先對優(yōu)化的參數(shù)進行相應(yīng)編碼，并隨機產(chǎn)生初始種群，然后計算個體適應(yīng)度。算法以容器利用率達(dá) 100%和最大進化代數(shù)作為停止條件，若滿足停止條件，則停止計算；否則，對個體進行選擇、交叉、變異操作，每一過程都要計算適應(yīng)度值，在整個過程中運用精英保留策略，直到滿足終止條件，輸出優(yōu)化參數(shù)值和布局方案。

具體步驟如下：

Step 1.隨機生成初始種群A(0)。

Step 2.實現(xiàn)布局過程。

Step 3.計算種群中所有個體的適應(yīng)度，將最優(yōu)個體(即第0代蜂王)保存到best中。

Step 4.如果滿足停止準(zhǔn)則，算法輸出結(jié)果并停止運行；否則，繼續(xù)。

Step 5.t = t+1。

Step 6.利用蜜蜂進化選擇算子，從A(t?1)中選出父代個體。

Step 7.父代個體進行交叉運算產(chǎn)生種群B(t)。

Step 8.對B(t)執(zhí)行變異操作，得到種群C(t)。

Step 9.實現(xiàn)布局過程。

Step 10. 計算種群C(t)中所有個體的適應(yīng)度，將適應(yīng)度最大的個體記為newbest。

Step 11.如果newbest的適應(yīng)度值大于best的適應(yīng)值，用 newbest代替 best；否則，用 newbest代替C(t)中最差的個體。得到第t代種群。

Step 12.轉(zhuǎn)Step5。

2.2 算法參數(shù)選擇

遺傳算法由Holland于1975年首次提出，這種求解策略和方法通過選擇、交叉、變異等操作模擬了自然界的生物演化過程。傳統(tǒng)遺傳算法在解決布局問題方面雖然有著較大的優(yōu)勢。但是也存在著一些不足，比如所采用選擇算子產(chǎn)生新解種類較少，容易過早收斂。本文采用蜜蜂進化選擇算子，是對傳統(tǒng)遺傳算法的改進。(本文所講的傳統(tǒng)遺傳算法，是指采用傳統(tǒng)輪盤賭選擇算子的遺傳算法)。

2.2.1 編碼策略

采用實數(shù)編碼的方式，每個染色體是變量為16維的解向量，并且每一個分量都是在有限的區(qū)間上進行定義，編碼向量表示為：Vk(t)=(ω1，ω2，ω3，ω4，α1，α2，α3，α4，β1，β2，β3，β4，γ1，γ2，γ3，γ4)。式中：t為進化代數(shù)，k∈[1,m]且為整數(shù)，m為種群數(shù)。

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

算法的適應(yīng)度函數(shù)取為布局容器的體積利用率f。顯然，適應(yīng)度值越大，布局容器的體積利用率就越大，個體的性能也就越好。

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

(1) 人為指定部分個體的某些參數(shù)。例如，可假設(shè)其中一個個體的 ω1=1，ω2=0，ω3=0，ω4=0，此時相當(dāng)于該個體當(dāng)中就只有一個吸引子在起作用；或者可假設(shè)其中一個個體的α1=1，β1=0，γ1=0，此時相當(dāng)于在第一個吸引子當(dāng)中只有在X軸方向的吸引作用。

(2) 其余的個體由計算機隨機產(chǎn)生。

2.2.3 選擇算子

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

(1) 選取種群中 A(t)的最優(yōu)個體，與上一代蜂王比較，優(yōu)勝者作為第t代蜂王，記為Queen。

與傳統(tǒng)遺傳算法相比，蜜蜂進化型遺傳算法的主要特征有兩個：

(1) 每對父本均包含蜂王(種群中的最優(yōu)個體)。

(2) 在代進化過程中引入了隨機外來種群，這個隨機外來種群的規(guī)模由參數(shù)λ決定。

第一個特征加強了遺傳算法的開采能力，后代主要依賴與最優(yōu)個體的交叉操作產(chǎn)生。這同時降低了算法過早收斂的可能性；第二個特征幫助遺傳算法搜索新的空間，引入隨機種群提高了遺傳算法的勘探能力。這兩個特征使遺傳算法的進化過程加快，并保持了優(yōu)良的解。

2.2.4 交叉算子

交叉操作的具體過程如下：

對于兩父代個體中第i個分量 Xi(k)， Xi(k+1)，通過交叉得到的個體分量為 Xi′(k)， Xi′(k+1)，那么：

其中，α有兩種取值方法：

(1) α為(0,1)之間隨機產(chǎn)生的數(shù)(此為后面算例及分析中所使用交叉方式)。

(2) /tTα= (t)為現(xiàn)在的進化代數(shù)，T為最大進化代數(shù)。

2.2.5 變異算子

對當(dāng)前種群中的個體進行變異操作，是產(chǎn)生新解和維持種群多樣性的有效手段。本算法采用非均勻變異，提供了兩種變異策略。設(shè)新的個體中的分向量為()ikX′，則：

(1) 隨機產(chǎn)生一個變異位，用新產(chǎn)生的(0,1)的數(shù)代替這個基因。

(2) 隨機產(chǎn)生一個變異位，再在[0.5,1)上隨機產(chǎn)生一個數(shù)β。設(shè)變異位處的基因為()ikX ，令用()ikX′代替()ikX (此為后面算例及分析中所使用變異方式)。

2.3 擾動策略

通過算例證明本文所提出算法更適合強異構(gòu)問題。針對弱異構(gòu)問題，本文通過對布局物體布入順序的干擾，來改善算法對弱異構(gòu)問題的解決能力。具體做法如下：

(1) 統(tǒng)計原算法結(jié)果當(dāng)中體積較大布局物體的個數(shù)m；

(2) 將體積較大的布局物體個數(shù)控制在某個范圍內(nèi)，例如m/2；

(3) 當(dāng)體積較大的布局物體的數(shù)目達(dá)到 m/2時，進行下一類型布局物體的布置。

3 算例及分析

算例1.此算例來自文獻(xiàn)[9,16]，算例中所有箱子總體積小于容器體積，但最優(yōu)解并不知道，即不確定是否能把所有箱子裝入容器中。測試數(shù)據(jù)總共有15個類型，每個類型有100個算例，共1500個算例，分別對應(yīng)不同的箱子種類。BR1-BR7是弱異構(gòu)問題，BR8-BR15是強異構(gòu)問題。每個類型當(dāng)中的算例布局物體的種類是相同的。布局物體種類數(shù)3～100不等。BR1當(dāng)中的算例異構(gòu)性最弱，每個算例中只有3個類型布局物體，而BR15當(dāng)中的算例異構(gòu)性最強，每個算例有100個類型的布局物體。

對于這 1500個算例，很多學(xué)者進行了研究測試。這些算法有的只計算了BR1-BR7，有的只計算了BR8-BR15。圖1 所示為BEGA和SPGA對BR算例的最大體積利用率變化圖。(注：本文所有計算過程均在2 GB內(nèi)存，2.79 GHz計算機上進行)

從圖1可以看出，BEGA與SPGA相比變化走勢大體一致。計算結(jié)果中有6組BEGA高于SPGA，6組持平，只有3組低于SPGA，表明BEGA相對SPGA有了改善。

表1給出了各算法對算例BR1-BR7的計算結(jié)果。表2給出了各算法對算例BR8-BR15的計算結(jié)果。表3給出了BEGA的計算結(jié)果(注：表1~2中數(shù)字指每類算例中100個算例的平均利用率)。

表1 各算法對弱異構(gòu)問題的計算結(jié)果

表2 各算法對強異構(gòu)問題的計算結(jié)果

表3 BEGA的計算結(jié)果

通過對表 1~3的數(shù)據(jù)觀察、分析可以看出，BEGA相對其他算法有了提高。BEGA在BR14和BR15這兩類算例中的表現(xiàn)比較出色，得到了最大值。計算可得BR1-BR7最大值項和最小值項方差分別為34.79、127.92，BR8～BR15相應(yīng)方差為6.94和9.8。由此可得，BEGA隨著算例異構(gòu)性的增強，不僅計算結(jié)果越來越好，而且計算結(jié)果的穩(wěn)定性也不斷增加。也就是說本文的BEGA更適合解決強異構(gòu)問題。

考慮到BEGA不太適合解決弱異構(gòu)問題，本文嘗試應(yīng)用擾動策略對其進行改善。BEGA與擾動策略對BR1～BR7算例體積利用率的平均值、最大值及最小值的對比如表4所示。

從表4中可以看出，擾動策略對于弱異構(gòu)問題有了不同程度的改善，證實擾動策略可以提高算法對弱異構(gòu)問題的解決能力。

算例2.本算例是由二維C類算例改進而來，在原有算例的基礎(chǔ)上，對布局空間和布局物體都增加了同樣的高。并與文獻(xiàn)[17]提出的粒子群算法進行了比較，比較結(jié)果如表5所示。

表4 BEGA與擾動策略的對比

表5 C類算例布局利用率的對比(%)

由表5中的數(shù)據(jù)可以看出，BEGA對C類算例的計算結(jié)果有9個算例優(yōu)于文獻(xiàn)[13]、[17]的結(jié)果，有5個算例與文獻(xiàn)[17]中的結(jié)果持平。本文的平均利用率較文獻(xiàn)[17]提高了1.51%。

4 結(jié) 束 語

本文按照體積遞減對布局物體進行定序，然后利用吸引子定位函數(shù)結(jié)合布局塊的幾何可行域?qū)Σ季治矬w進行定位，最后用蜜蜂進化型遺傳算法對基于吸引子法的定位函數(shù)參數(shù)進行優(yōu)化。論文對一些算例進行了計算，通過算例結(jié)果可以看出BEGA更適合于強異構(gòu)布局問題，并且其相對于傳統(tǒng)布局遺傳算法(SPGA)等有了改進。另外，本文提出的一種擾動策略對解決弱異構(gòu)問題有了改善。本文布局物體的定序規(guī)則固定，若改變定序規(guī)則，則可能提高布局利用率空間。因此如何確定合理的定序規(guī)則將是我們今后的研究工作內(nèi)容之一。

[1] Sweeny P E, Paternoster E R. Cutting and packing problems: a categorized, application -orientated research [J]. Journal of Operation Research Society, 1992, 43(7): 691-706.

[2] Dowsland K A, Dowsland W B. Packing problems [J]. European Journal of Operational Research, 1992, 56(1): 2-14.

[3] Zhang Defu, Peng Yu, Leung S C H. A heuristic block-loading algorithm based on multi-layer search for the container loading problem [J]. Computers & Operations Research, 2012, 39(10): 2267-2276.

[4] Leung S C H, Zhang Defu, Zhou Changle, Wu Tao. A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem [J]. Computers & Operations Research, 2012, 39(1): 64-73.

[5] Burke E K, Hyde M, Woodward J. A genetic programming hyper-heuristic approach for evolving two dimensional strip packing heuristics [J]. IEEE Transactions on Evolutionary Computation, 2010, 14(6): 942-958.

[6] Cintra C F, Miyazawa F K. Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation [J]. European Journal of Operational Research, 2008, 191(1): 61-85.

[7] 楊 林, 陶慶云, 全惠云. 求解矩形物體布局問題的分布評估算法[J]. 湖南師范大學(xué)自然科學(xué)學(xué)報, 2007, 30(3): 42-45.

[8] Bischoff E E, Ratcliff M S W. Issues in the development of approaches to container loading [J]. Omega, 1995, 23(3): 377-390.

[9] Gehring H, Bortfeldt A. A genetic algorithm for solving the container loading problem [J]. International Transactions in Operational Research, 1997, 4(5-6): 401-418.

[10] Bortfeldt A, Gehring H. A tabu search algorithm for weakly heterogeneous container loading problems [J]. OR Spectrum, 1998, 20(4): 237-250.

[11] Lim A, Rodrigues B, Yang Y. 3-D container packing heuristics [J]. Applied Intelligence, 2005, 22(2): 125-134.

[12] Moura A, Oliveira J F. A GRASP approach to the container loading problem [J]. IEEE Intelligent Systems, 2005, 20(4): 50-57.

[13] 朱麗蘋, 王金敏. 基于空間分割的求解布局幾何可行域的算法[J]. 天津職業(yè)技術(shù)師范大學(xué)學(xué)報, 2012, 22(2): 30-33.

[14] 王金敏, 楊維嘉. 動態(tài)吸引子在布局求解中的應(yīng)用[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2005, 17(8): 1725-1730.

[15] 孟 偉, 韓學(xué)東, 洪炳熔. 蜜蜂進化型遺傳算法[J].電子學(xué)報, 2006, 34(7): 1294-1300.

[16] Davies A P, Bisschoff E E. Weight distribution considerations in container loading [J]. European Journal of Operational Research, 1999, 114(3): 509-527.

[17] Qi Yang, Wang Jinmin. The particle swarm optimization algorithm for solving rectangular packing problem [J]. Advanced Materials Research, 2011, 186: 479-483.

A Genetic Algorithm for Packing Problems Based on Bee Evolutionary Selection Operator

Wang Jinmin1,2, Zhu Liping2, Zhen Shigang2
(1. Tianjin Key Laboratory of High Speed Cutting & Precision Machining, Tianjin 300222, China; 2. School of Mechanical Engineering, Tianjin University of Technology and Education, Tianjin 300222, China)

Three dimensional rectangular packing is a NP-hard problem, which is often solved by heuristic algorithms. In this paper the sequencing rules is determined by the volume of packing items, the positioning rules are determined by attractor function with the geometry feasible region of packing items in packing space. Then the parameters in the attractor function are optimized by bee evolution genetic algorithm (BEGA), the new packing genetic algorithm is formed. Finally, different benchmarks are carried out, and the paper proves the validity of the algorithm by comparing with the traditional packing genetic algorithm (SPGA) which chooses the standard proportional selection as its operator, etc.

packing problem; heuristic algorithm; attractive factor; bee evolutionary

TP 391

A

2095-302X(2014)05-0690-07

2013-11-21；定稿日期：2013-12-13

國家自然科學(xué)基金資助項目(60975046)

王金敏(1963–)，男，河南舞陽人，教授，博士。主要研究方向為智能布局、計算機圖形學(xué)。E-mail：wang_jin_min@163.com