章 翼， 杜永貴

(太原理工大學(xué) 信息工程學(xué)院，山西 太原 030024)

應(yīng)用技術(shù)

改進型文化算法在三維空間裝載中的應(yīng)用*

章 翼， 杜永貴

(太原理工大學(xué) 信息工程學(xué)院，山西 太原 030024)

為提高倉儲貨運空間利用率，降低成本，提高效率，提出基于改進型文化算法的三維空間最優(yōu)裝載方法。根據(jù)裝載問題的特點，兼顧各項約束條件建立起一個多約束多目標(biāo)的數(shù)學(xué)模型，并且將文化算法單一的信仰空間改進為多層。該算法通過對多層信仰空間擇優(yōu)選取，用其中的經(jīng)驗來提高進化速度和計算性能，同時保持搜索范圍廣等優(yōu)良性。仿真結(jié)果表明：該算法有良好的結(jié)果，與傳統(tǒng)算法相比，能夠更有效快速地解決三維集裝箱裝載問題，可應(yīng)用性好。

文化算法； 三維裝載； 約束優(yōu)化； 智能算法； 多層空間

0 引 言

三維裝載問題是一個典型的組合優(yōu)化問題，通常被人們認為在多項式時間內(nèi)無法獲得最優(yōu)解，所以,在此研究領(lǐng)域內(nèi)的學(xué)者們都在研究用各種優(yōu)化算法來解決此類問題，例如:啟發(fā)式算法、傳統(tǒng)進化計算，或者將兩者相融合的算法等[1]，雖然這些算法在多約束問題上可以取得一個較好的解，但其研究成果只是集中在種群自然進化選擇這一層面，結(jié)果仍然不理想，而文化算法(culture algorithms)則用一種顯性機制來提取、保存和整合被求解問題的知識經(jīng)驗，使種群進化速度超越單純依靠種群基因遺傳的進化速度，搜索的范圍和速度也更優(yōu)良，在一些問題上，文化算法取得比傳統(tǒng)進化計算更好的結(jié)果[2,3]，此外，還有文獻[4,5]中將傳統(tǒng)進化算法與文化算法相結(jié)合，但都是單層信仰空間指導(dǎo)進化過程，且單層的信仰空間前后沒有優(yōu)劣之分，在遇到后一代信仰空間比前一代差時容易陷入局部極值，限制了性能的提升。

本文提出一種基于多層信仰空間的文化算法解決三維裝載問題，提高算法的性能和產(chǎn)品裝箱配載率，優(yōu)化過程不受限制性條件的約束，不僅在實際應(yīng)用中滿足目前工作的需求，提高解決問題的效率，減少工作時間，對提高物流效率、增加企業(yè)收益、減少產(chǎn)品損耗均有意義。

1 三維裝載問題模型構(gòu)建

三維裝載問題定義為：對于確定的空間，在待裝貨物數(shù)量無限，滿足空間體積、重量、重心、方向等約束情況下裝載最多體積的貨物。假設(shè)所有貨物均為規(guī)則長方體，待裝貨物i的長、寬、高分別為li，wi和hi，集裝箱空間尺寸為：L(長)，W(寬)，H(高)，則目標(biāo)函數(shù)表示如下

(1)

根據(jù)三維裝載問題的屬性和特點，及實際配載中遇到的問題，求解過程中需滿足如下幾個約束條件：

1)方向約束：貨物的放置一般有3種：可任意旋轉(zhuǎn)、僅水平旋轉(zhuǎn)和不能旋轉(zhuǎn)。為提高效率，本文設(shè)貨物可任意旋轉(zhuǎn)，相鄰方向序號之間貨物旋轉(zhuǎn)90°

(2)

式中 di為擺放方向系數(shù)。

2)質(zhì)量約束：裝載貨物的質(zhì)量之和不可超過集裝箱最大載重量

文中基于核稀疏表示的多模人臉人耳融合識別算法是在基于稀疏表示的識別算法（MSRC）的基礎(chǔ)上引入核方法得到。

(3)

式中 gi為第i件貨物質(zhì)量，集裝箱最大載重量為G。

3)體積約束：被裝載貨物的體積之和小于集裝箱的容積

(4)

4)重心約束：貨物完全裝載后整體與單件貨物的重心在安全范圍內(nèi)，確保運輸安全

(5)

設(shè)裝載完成后重心坐標(biāo)為(X，Y，Z)，則重心安全范圍為X∈[f1,f2]，Y∈[f3,f4]，Z∈[0,f5][6]，(xi,yi,zi)為貨物i擺放位置坐標(biāo)。

5)承載力約束：貨物所能承受的重量有限，避免被上層貨物損壞

(6)

式中 ∑gk為壓在貨物i上的重量和，bir為貨箱i承重量閾值上限。

2 基于改進型文化算法的問題求解

三維裝箱問題屬于不確定多項式問題，隨著問題規(guī)模的不斷擴大，難以在有限的時間中找到最優(yōu)解。改進文化算法可以對進化信息進行有效的提取和管理，將單一的信仰空間改進為多層信仰空間，有效地避免了經(jīng)驗的倒退[7]，從多層空間中選擇最優(yōu)的信仰空間來指導(dǎo)進化搜索，優(yōu)質(zhì)的個體與信息得以獲得更大的生存概率，信仰空間與種群空間雙層進化方法融合了進化搜索和局部搜索策略，既具有全局搜索范圍大的優(yōu)點，又具有局部搜索的深度優(yōu)勢，雙層進化的結(jié)構(gòu)使種群的進化速度大大超越單純依靠生物基因遺傳的進化速度，具有良好的全局優(yōu)化性能。且優(yōu)化過程不受約束條件的限制，具有很強的魯棒性，搜索效率也比傳統(tǒng)進化算法更快，是解決工程優(yōu)化問題的一種高效的優(yōu)化方法[8]。

2.1 文化算法構(gòu)架

文化算法是Reynolds在1994年提出的一種雙層進化機制，這種算法通過模擬人類社會的演進過程來完成高效尋優(yōu)的過程，文明社會中，文化是人類所擁有經(jīng)驗的集合，可以供后人直接學(xué)習(xí)，并用于指導(dǎo)每個個體的行為。文化算法除種群進化空間外還通過-個獨立于種群空間的信仰空間，來獲取和保存并加以整合解決問題的知識，并且2個空間通過特定的協(xié)議進行信息交換，算法構(gòu)架如圖1所示。

圖1 文化算法構(gòu)架Fig 1 Framework of cultural algorithm

其中，接受函數(shù)():收集群體中被選擇的經(jīng)驗，傳遞至信仰空間；更新函數(shù)():更新信仰空間，形成種群經(jīng)驗；影響函數(shù)():利用經(jīng)驗知識對種群空間進行指導(dǎo)；種群操作():對種群進行交叉、變異等操作，生成下一代個體；選擇函數(shù)():選擇優(yōu)良個體；目標(biāo)函數(shù)():得到每個個體適應(yīng)值，性能評價。

2.2 個體編碼與適應(yīng)度函數(shù)

為更好地解決裝載問題，編碼時考慮貨物裝載的先后順序和放置方向，設(shè)置長度為2n的數(shù)字串S=(s1,s2，…,sn,sn+1,…,sn+1,…,s2n)對應(yīng)不同的裝載方案。其中，基因s1～sn表示貨物裝載順序編號，由[1,n]間產(chǎn)生的任意整數(shù)排列組成，且整數(shù)無重復(fù)，基因s1～sn所在位置1,2，…，n與貨物編號相對應(yīng)，基因sn+1～s2n表示貨物方向約束的編號，由集合[1,2,3,4,5,6]中隨機產(chǎn)生的任意整數(shù)組成，sn+1～s2n中的整數(shù)可重復(fù)，數(shù)字分別代表貨物的6種擺放方向[10]?；騭1～sn與基因sn+1～s2n之間的對應(yīng)關(guān)系為：sn+i代表貨物si的裝載擺放方向[11]，不裝載均為0。

以個體適應(yīng)值大小來評價群體中個體所對應(yīng)裝載方案的優(yōu)劣，較優(yōu)個體有更大的生存機會。裝載優(yōu)化問題屬于最大化問題，填充率越高解越優(yōu)質(zhì)，函數(shù)表示為

(7)

2.3 接受函數(shù)

接受函數(shù)accept()在群體空間內(nèi)按照一定比例選擇可以影響當(dāng)前信仰空間的個體，在文化算法中標(biāo)準(zhǔn)化的經(jīng)驗和約束知識被不同個體影響。accept()按照適應(yīng)度函數(shù)值選擇前20 %的個體融入信仰空間，接受函數(shù)如下

(8)

其中,P為種群規(guī)模；α為接受比率，本文取α=0.2；t為進化代數(shù)。

2.4 多層信仰空間結(jié)構(gòu)

2.5 多層信仰空間更新和知識更新

多層信仰空間同時保存前幾代評價值最優(yōu)的信仰空間，每次指導(dǎo)種群進化時從多層空間中通過評價值函數(shù)篩選出最優(yōu)一層來操作，如圖2所示。只需要對信仰空間進行評價就能有效地避免優(yōu)質(zhì)經(jīng)驗被劣質(zhì)經(jīng)驗所迭代的危險，優(yōu)質(zhì)的信仰空間知識有更大的概率生存，多層信仰空間的策略比僅有單層信仰空間指導(dǎo)的進化更加完備。

圖2 多層信仰空間文化算法構(gòu)架Fig 2 Framework of multilayer belief space cultural algorithm

新一層信仰空間由更新函數(shù)update()在上一代信仰空間基礎(chǔ)上進行知識更新。

標(biāo)準(zhǔn)知識N更新規(guī)則如下

(9)

(10)

(11)

(12)

最新產(chǎn)生的信仰空間與前幾代信仰空間通過評價值函數(shù)選出最優(yōu)層和最差層，最優(yōu)一層信仰空間指導(dǎo)種群空間進化過程，刪除最差的一層，信仰空間層數(shù)保持不變。

2.6 影響函數(shù)

影響函數(shù)influence()根據(jù)標(biāo)準(zhǔn)知識設(shè)定，以調(diào)整變量變化方向和步長，函數(shù)定義如下

(13)

其中，N(0,1)為標(biāo)準(zhǔn)正態(tài)分布變量，size()為信仰空間中變量i調(diào)整區(qū)間的長度，λ為變量變化步長因子。

文化算法通過函數(shù)對信仰空間進行更新，并且實現(xiàn)群體空間與信仰空間之間的通信，2個空間是兩個相互獨立的進化過程，但是又相互影響促進，對進化信息進行有效的提取和管理。

2.7 算法實現(xiàn)流程

根據(jù)上述文化算法各種函數(shù)和準(zhǔn)則定義，將改進型文化算法應(yīng)用于三維集裝箱裝載問題的具體實現(xiàn)中，算法流程如下：

1)初始化各項參數(shù)，初始化種群空間，初始化信仰空間，根據(jù)參數(shù)取值，生成改進文化算法初始種群空間；

2)通過適應(yīng)度函數(shù)對初始種群中的個體進行評價；

3)根據(jù)初始種群評價值，提取優(yōu)秀個體，由接受函數(shù)accept()選擇這些評價值高的優(yōu)良個體進入信仰空間，生成初始信仰空間；

4)根據(jù)式(9)～式(12)更新當(dāng)前信仰空間，對多層信仰空間進行評價，從中選擇生成最優(yōu)信念空間；

5)根據(jù)影響函數(shù)influence()，對種群空間中的個體進行影響和變異，父代根據(jù)最優(yōu)層信仰空間知識產(chǎn)生子代，對每個個體進行評價；

6)t=t+1；

7)通過接受函數(shù)accept()從種群空間中選出優(yōu)秀個體；

8)判斷是否滿足終止條件，若不滿足終止條件，則轉(zhuǎn)至步驟(4)循環(huán)，若滿足，即達到最大迭代次數(shù)，則結(jié)束；

9)輸出裝載問題的最佳裝載方案。

3 算法實例仿真

用Matlab編程仿真，采用3層信仰空間，群體規(guī)模100，最大迭代次數(shù)500，以20ft(1ft=304.80mm)標(biāo)準(zhǔn)集裝箱為例，尺寸為2 352mm×2 388mm×5 899mm，30件不同類貨物尺寸和改進型文化算法運行結(jié)果如表1。

將3種不同方法的運行結(jié)果，包括所得的平均解、空間利用率和運算時間列于表2，改進文化算法的空間利用率為90.72 %，裝入84 %的貨物，運算時間均在90s以內(nèi)。

由表2可見，采用改進型文化算法得到的最優(yōu)解比采用遺傳算法(GA)和啟發(fā)式算法(HA)得到的最優(yōu)解更好，由于改進文化算法在進化計算的過程中將求解多約束問題的約束知識提取出來，根據(jù)優(yōu)秀的區(qū)域?qū)M化過程進行指導(dǎo)，有效地避免了對不可行解和不良的個體的無效搜索，對適應(yīng)值函數(shù)的計算量大大減少，少走“彎路”，從而提高搜索效率，節(jié)約大量時間，圖3列出了4種方法的收斂曲線，改進文化算法迭代至158代開始趨于平穩(wěn)。

由表2和圖3可以看出：利用改進型文化算法能夠達到比單層信仰空間文化算法、遺傳算法和傳統(tǒng)啟發(fā)式算法更高的空間利用率，有效地減少了布局空間浪費，穩(wěn)定性也有所改善，多層信仰空間有效地避免了經(jīng)驗知識的倒退和易陷入局部最優(yōu)的缺陷，性能得到充分的發(fā)揮，當(dāng)貨物數(shù)量增大時，多層信仰空間文化算法的優(yōu)勢更為明顯。

表1 貨物尺寸與運行結(jié)果表Tab 1 Size of cargo and operating result

表2 3種算法結(jié)果比較Tab 2 Comparison of results by three kinds of algorithms

圖3 算法搜索過程Fig 3 Search process of algorithms

4 結(jié)束語

本文構(gòu)建了一個解決三維集裝箱裝載問題的數(shù)學(xué)模型，全面地分析三維集裝箱裝載問題，并運用基于多層信仰空間的改進型文化算法對問題進行求解，通過仿真來驗證，結(jié)果表明：運用改進文化算法求解三維集裝箱裝載問題具有較好的結(jié)果和相對少的計算量，克服了傳統(tǒng)進化算法效率不高和易陷入局部最優(yōu)的缺點，多層信仰空間保證了指導(dǎo)種群進化的經(jīng)驗知識的質(zhì)量，確保種群空間的發(fā)展，更加準(zhǔn)確地接近最優(yōu)解，雙層進化機制擴大了解的搜索空間，并且節(jié)省計算資源和時間，改進文化算法對裝載問題具有良好的適用性和全局優(yōu)化性能。

[1] 李建華，李錦文.多約束三維裝箱問題的研究綜述[J].計算機光盤軟件與應(yīng)用，2012,17：1-3.

[2] Yuan X H,Yuan Y B.Application of cultural algorithm to generation scheduling of hydrothermal system [J].Energy Conversion and Management,2006,47:2192-2201.

[3] Coello C A,Becerra R I.Evolutionary multi-objective optimization using a cultural algorithm[C]∥Proceedings of 2003 IEEE Swarm Intelligence Symposium,Indianapolis,Indiana,IEEE Service Center,2003：6-13.

[4] Ricardo L B,Carlos A,Coello C A.Cultural algorithm with diffe-rential evolution to solve constrained optimization problems[J].Lecture Notes in Computer Science,Springer,2004,3315:881-890.

[5] Gao F,Cui G,Liu H W.Integration of genetic algorithm and culture algorithms for constrained optimization[J].Lecture Notes in Computer Science,Springer,2006,4234:817-825.

[6] He Chuan,Zhang Yuanbiao,Wu Jianwen,et al.Research of three-dimensional container-packing problems based on discrete particle swarm optimization algorithm[C]∥International Conference on Test and Measurement：[s.n.],2009:425-428.

[7] 黃海燕，顧幸生，劉漫丹.求解約束優(yōu)化問題的文化算法研究[J].自動化學(xué)報，2007,33(10)：1115-1120.

[8] 劉漫丹.文化基因算法(memetic algorithm)研究進展[J].控制理論與應(yīng)用，2007,26(11)：1-4.

[9] 王友釗，彭宇翔，潘芬蘭.基于貪心算法和遺傳算法的倉儲車輛調(diào)度算法[J].傳感器與微系統(tǒng)，2012，31(10)：125-128.

[10] 許光濘，俞金壽.改進遺傳算法求解三維集裝箱裝載問題[J].華東理工大學(xué)學(xué)報:自然科學(xué)版，2007，33(3)：425-428.

[11] 卜 雷，袁新江，蒲 云，等.基于遺傳算法的集裝箱單箱三維裝載優(yōu)化問題[J].中國鐵道科學(xué)，2004，25(4)：108-111.

Application of modified cultural algorithm in 3D space loading*

ZHANG Yi， DU Yong-gui

(College of Information Engineering,Taiyuan University of Technology,Taiyuan 030024，China)

To improve utilization of space of logistic distribution,reduce costs and improve efficiency,modified cultural algorithm for 3D space optimal loading method is proposed.According to characteristics of loading problems,take multiple constraints into account,a multi-constrained and multi-objective mathematical model is established,the single belief space of cultural algorithm is improved to multilayer.This algorithm improves computing performance and speed of evolution through the experience selected from multi-layer belief space,and keep good performance of wide searching range.Simulation result proves that the algorithm produces better result,more efficient and faster than traditional algorithms in solving 3D container loading problem,applicability is good.

cultural algorithm; 3D loading; constrained optimization; intelligent algorithm; multilayer spaces

10.13873/J.1000—9787(2014)08—0145—05

2014—01—06

材料強度與結(jié)構(gòu)沖擊山西省重點實驗室開放基金資助項目(4015—04110004)

TP 301.6

A

1000—9787(2014)08—0145—05

章 翼(1989-)，女，山西太原人，碩士研究生，研究方向為智能控制理論與應(yīng)用﹑優(yōu)化控制。