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

王金敏， 朱麗蘋， 甄士剛

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

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

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

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

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

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

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

1 三維矩形布局問題

1.1 問題描述

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

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

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

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

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

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

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

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

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

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

2 布局遺傳算法(BEGA)

2.1 算法流程

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

具體步驟如下：

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

Step 2.實現布局過程。

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

Step 4.如果滿足停止準則，算法輸出結果并停止運行；否則，繼續。

Step 5.t = t+1。

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

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

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

Step 9.實現布局過程。

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

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

Step 12.轉Step5。

2.2 算法參數選擇

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

2.2.1 編碼策略

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

2.2.2 適應度函數及初始化

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

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

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

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

2.2.3 選擇算子

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

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

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

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

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

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

2.2.4 交叉算子

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

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

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

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

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

2.2.5 變異算子

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

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

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

2.3 擾動策略

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

(1) 統計原算法結果當中體積較大布局物體的個數m；

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

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

3 算例及分析

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

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

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

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

表1 各算法對弱異構問題的計算結果

表2 各算法對強異構問題的計算結果

表3 BEGA的計算結果

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

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

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

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

表4 BEGA與擾動策略的對比

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

由表5中的數據可以看出，BEGA對C類算例的計算結果有9個算例優于文獻[13]、[17]的結果，有5個算例與文獻[17]中的結果持平。本文的平均利用率較文獻[17]提高了1.51%。

4 結 束 語

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

[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]. 湖南師范大學自然科學學報, 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]. 天津職業技術師范大學學報, 2012, 22(2): 30-33.

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

[15] 孟 偉, 韓學東, 洪炳熔. 蜜蜂進化型遺傳算法[J].電子學報, 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

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

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