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

章 翼， 杜永貴

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

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

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

章 翼， 杜永貴

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

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

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

0 引 言

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

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

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

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

(1)

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

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

(2)

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

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

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

(3)

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

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

(4)

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

(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 基于改進(jìn)型文化算法的問題求解

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

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

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

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

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

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

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

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

(7)

2.3 接受函數(shù)

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

(8)

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

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

2.5 多層信仰空間更新和知識(shí)更新

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

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

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

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

(9)

(10)

(11)

(12)

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

2.6 影響函數(shù)

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

(13)

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

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

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

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

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

2)通過適應(yīng)度函數(shù)對(duì)初始種群中的個(gè)體進(jìn)行評(píng)價(jià)；

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

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

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

6)t=t+1；

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

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

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

3 算法實(shí)例仿真

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

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

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

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

表1 貨物尺寸與運(yùn)行結(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é)束語(yǔ)

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

[1] 李建華，李錦文.多約束三維裝箱問題的研究綜述[J].計(jì)算機(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].自動(dòng)化學(xué)報(bào)，2007,33(10)：1115-1120.

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

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

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

[11] 卜 雷，袁新江，蒲 云，等.基于遺傳算法的集裝箱單箱三維裝載優(yōu)化問題[J].中國(guó)鐵道科學(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

材料強(qiáng)度與結(jié)構(gòu)沖擊山西省重點(diǎn)實(shí)驗(yàn)室開放基金資助項(xiàng)目(4015—04110004)

TP 301.6

A

1000—9787(2014)08—0145—05

章 翼(1989-)，女，山西太原人，碩士研究生，研究方向?yàn)橹悄芸刂评碚撆c應(yīng)用﹑優(yōu)化控制。