基于自適應細菌覓食算法的集裝箱裝載

范霽月，高 尚，張曉慶

(江蘇科技大學 計算機科學與工程學院，江蘇 鎮江 212003)

0 引 言

針對集裝箱裝載問題(container loading problem，CLP)[1-3]，現在研究者多使用數學規劃法、圖論法、啟發式算法[4]、遺傳算法[5]、蟻群算法[6]等來解決集裝箱問題，但考慮到裝載中存在的約束條件不全面，裝載率仍有較大提升空間。細菌覓食算法是近年來新起的一種群智能優化算法，它模擬大腸桿菌的覓食行為，對原始數據進行趨化、復制、消亡操作，進而得到最優解[7-9]。該算法并行性高、處理效率高、魯棒性強，能以較小的代價通過算法性能獲得較大的收益，因此是一種很有價值的解決方法。

本文就集裝箱裝載問題，提出基于余弦的自適應步長細菌覓食優化算法的求解新方法，在三空間分割裝載策略[10]的基礎上，使用基于順序表示的遺傳基因編碼方式將不同的裝載方式編碼為適應度函數的解，再通過改進的自適應步長的細菌覓食優化算法[11]得出最優解。相比之前采用的遺傳算法、啟發式算法、蟻群算法等各種優化算法，實驗結果表明，本文中采用的自適應步長的細菌覓食優化算法可以在相對較短的時間內獲得一個合理的裝載方案，并且有較高的裝載率和空間利用率，對實際的裝載過程有一定的指導意義。

1 細菌覓食優化算法(BFOA)基本原理

大腸桿菌在覓食過程中逐步向目標移動并且遠離有毒物質，這在生物學中被稱作覓食方法。細菌在初始位置考量食物的豐富程度后，通過翻滾選擇一個隨機方向并移動固定的距離，隨后再次考量新位置食物的豐富度。一次翻滾和前進過程形成一步趨化。趨化過程中如果下一位置食物更密集，細菌會在同樣方向再次游動，直到達到最大游動次數；反之，細菌會翻滾產生新的方向并前進。最大游動次數代表著細菌的生命周期。在細菌生命周期結束時，一半具有較優健康值的細菌在各自的置將被復制，另一半會死亡，復制的執行次數也固定。在尋優過程中我們可以把待優變量和細菌所在位置匹配。細菌復制次數、趨化步數、前進步長、特定方向上的游動次數要根據特定問題初始化，利用BFOA實現變量的最優化。

細菌覓食優化算法是模擬大腸桿菌在我們食道中的吞噬食物行為而產生的新型群體智能優化算法。概括起來主要有4種行為：趨化行為、聚集行為、復制行為和驅散行為。

1.1 趨化行為

趨化過程是由翻滾和前進實現的，是細菌覓食算法的核心。其設計好壞與否直接影響著算法在解決集裝箱裝載問題上的性能與效果。假設θi(j+1,k,l)表示第i個細菌在第l次驅散、第k次復制、第j+1次趨化的位置，則有

θi(j+1,k,l)=θi(j,k,l)+C(i)φ(j)

(1)

式中：C(i)為翻滾過程中設定的隨機方向上的步長，φ(j)為隨機方向單位向量。

1.2 聚集行為

通常問題期望細菌尋找到食物最優的路徑后能夠快速地吸引其它細菌到目標位置。群游(swarming)能夠讓細菌緊密靠攏，使得細菌在群組中集體移動。群游是所有細菌共同作用的結果，該結果添加到實際目標函數后，表現為變化的目標函數。群游結果的目標函數數學上可表示為

(2)

式中：S是細菌總數量，p是每個細菌需優化的參數個數。吸引劑數值dattract，排斥劑數值hrepellent，吸引劑釋放速度ωattract和排斥劑釋放速度ωrepellent是待調系數。

1.3 復制行為

為了在優勝劣汰，種群進化的同時，保證種群規模的相對穩定，一部分覓食能力強、健康狀況好的細菌，在同樣的位置分裂為兩個相同個體；健康狀況最差的細菌被淘汰。通過復制操作，種群中的優良個體得以保留并得到保護，這樣大大提高了尋找最優解的速度，且保持了種群的完整性。

1.4 驅散行為

細菌在局部環境下常受到養料消耗或是環境突變的影響，導致其消亡或者被驅散到別處。這種現象可能破壞趨化過程，但細菌也可能被驅散到好的食物源附近。驅散行為加強BFOA全局尋優能力，降低細菌陷入局部極小現象的可能性。

2 集裝箱問題應用

基于BFOA具有容易陷入局部極值、收斂速度慢等缺點，所以本文采用自適應細菌覓食優化算法(ABFOA)解決集裝箱裝在問題，使用改進的基于余弦的自適應規則的步長替代固定步長，自適應步長隨著迭代次數的降低而減小，更好地對細菌進行趨化操作，顯著提升算法的尋優質量，在求解CLP上取得滿意的效果。

2.1 問題描述

設定集裝箱的長、寬、高分別為Lj,Wj,Hj，質量為Mj，容積為Vj待裝的n類貨物的長、寬、高分別為li,wi,hi，質量為mj。ki為每類貨物的總數量。則問題的目標函數為

(3)

即：k1*所有裝載的貨物體積總和占集裝箱體積的比例+k2*所有裝載物品的質量總和占集裝箱最多可承受的質量比例，其中k1，k2為比例系數，一般取值k1+k2=1，參見2.4章節。

式(3)中,F為目標函數；φi為第i類已裝貨物件數，0≤φi≤ki，為第i類貨物總件數，k1和k2為比例系數，兩者范圍在0-1之間。

裝載貨物時的約束條件為：

(1)貨物的裝載容積約束：所有裝載的貨物體積之和小于集裝箱可容納的最大體積；

(2)貨物的裝載質量約束：所有裝載的貨物質量之和小于集裝箱可承受的最大質量，公式表示如下

(4)

2.1.1 待裝載貨物擺放方式

假定待擺放物品是規則的六面體，并且重心在六面體幾何中心位置，因此貨物在集裝箱中產生6種不同的擺放方式。每種待裝貨物擺放方式的編號分別對應的該貨物在集裝箱中某種特定的旋轉方向，表1是兩者之間關系的說明。

表1 待裝貨物擺放方式編號和集裝箱位置對應的關系

2.1.2 空間劃分和歸并策略

從每個長方體平行但不與HL重合的面裝入貨物，每當一個貨物進入集裝箱放置好之后，該貨物將整個空間分為除自身以外的3個子空間：上空間、前空間、右空間，如圖1所示。而后已放置貨物的空間被去除，剩余3個形狀為長方體的新的空間。放入下一個的貨物時，按照上空間、前空間、右空間的順序對子空間進行填充。每放入新的貨物，則其又產生3個新的子空間。

圖1 集裝箱三維分割

2.1.3 定位規則和定序規則

定位規則中占角策略是指將貨物首先擺放在集裝箱空間的某一角，通過分析，占角策略是大多集裝箱裝載問題選擇的較好的策略。在定序過程中充分考慮體積和重量綜合因素的影響，參照式(3)中k1，k2值，按體積和質量由大到小的定序規則裝載貨物。

2.2 個體編碼和解碼

通常，BFOA對解的編碼方案大多采用二維或三維空間坐標編碼形式，但是對于集裝箱裝載排序問題顯然不采能用該編碼方式。原因有二個：①空間坐標可以用于排列質點，但是對于待裝載的三維物品很容易在空間上產生交叉現象，為避免該現象不能不引入復雜的計算；②細菌的空間坐標在空間維度上有具體的坐標值，但是不能很好地將其和適應度函數相配，導致算法不宜執行。為此，本文采用基于順序表示的遺傳基因編碼方式。將n種待裝載物品按照體積和質量由大到小的原則、按自然數由小到大的方式排序編號，并且按照種類編號依次排列編碼，則第i個細菌編碼形式

Pi=(p1,p2,…,pn,pn+1,pn+2,…,p2n)

(5)其中，i=1,2,…,S，S為細菌種群規模，p1,p2,…,pn為待裝貨物種類編號，pn+1，pn+2，…,p2n為前n個種類編號對應貨物的旋轉方向，其值取1,2,…,6。含義見上文。

式(5)中pi和pn+i值相互對應，即第pi種貨物以pn+i表示的旋轉方向放入集裝箱中。利用該解碼方式，原有的初始解Pi可以被轉化為一個與之相對應的可行解

Qi={q1,q2,…qm,qm+1,qm+2,…,q2m}

(6)

式中：m為待裝貨物總數量，qi表示等待裝載的第i個貨物。所有貨物根據當前裝載狀態選擇性裝入集裝箱，貨物的編碼在可行解中記為1表示其被裝入，可行解中為0時表示不裝入集裝箱。

2.3 自適應步長調整策略

前進步長C(i)對收斂速度和輸出誤差起著決定性作用。研究發現，BFOA中固定的C(i)會帶來兩個問題：①若前進步長過大，細菌到達優質點區域的速度雖有所增加，但是會導致尋優精度降低，使得細菌在之后趨化過程中的極值附近來回移動；②若前進步長過小，就會導致細菌到達優質點區域的趨化步數增加。此時收斂速度會降低，迭代步數較少可能使得細菌不能到達最優位置。本文采用特殊的編碼和解碼方式，將細菌前、后兩步趨化坐標Pi中每一維度之差視為前進步長，因此前進步長必須為整數。所以本文改進了文獻[11]中的趨向性步長的計算方法，提出新的基于余弦規則的自適應步長，其具有以下特點：

(7)

式中：C(i)和Pi維度一致，C(i)是下取整函數；Cimax為最小步長，Cimax為最大步長，則Cimin≤C(i)≤Cimax；gen為當前迭代次數，genm為最大迭代次數。

2.4 適應度函數

適應度函數是考量個體在目標問題中適應度的函數，它對ABFOA效果起著至關重要的作用。ABFOA中使用適應度這個概念來度量群體中每個細菌所代表裝箱方案的優良程度。適應度較高時，代表細菌生命力越強，即種群中的優良細菌，利于存活和復制；而適應度較低的細菌生命力弱，存活概率大大降低。根據2.1節，ABFOA在求解CLP過程中主要考慮到容積率和承載效率，適應度函數形式

(8)

式中：λ為集裝箱裝載容積率和承載效率的權衡因子，取值范圍為[0，1]。

2.5 終止條件

從待裝集合Q中取出編號為qi的貨物，記錄該貨物標記，為1表示可以裝入集裝箱中，無法裝入標0：

(1)貨物裝入時，集裝箱空間被分割為上、右、前子空間(如圖1所示)，放置貨物的空間被標記為已用，從空余空間隊列中刪除，空余空間隊列中為3個形狀為長方體的新空間。

(2)直到第i個的貨物放置時，發現最大的空間仍無法放入，則在貨物隊列中取i+1貨物進行放置，直到可以放入空間內，重復(1)。

(3)當空閑隊列中每一個子空間的體積都小于貨物隊列中體積最小的貨物時，則程序停止，跳出。

2.6 算法流程

自適應細菌覓食優化算法求解集裝箱貨物裝載問題流程如下：

步驟1 對每種裝載貨物按照體積和重量由大到小原則排序并編號，輸入每種貨物的參數li，wi，hi，mi。

步驟2 初始化權衡因子λ，ABFOA細菌規模S，細菌i的初始位置Pi，驅散次數lmax、復制次數kmax、趨化步

數jmax、特定方向上的游動次數和長度，方向概率PC，吸引劑數值dattract、排斥劑數值hrepellent、吸引劑釋放速度ωattract和排斥劑釋放速度ωrepellent,j=k=l=0。

步驟3 執行驅散操作，l=l+1，若驅散次數l>lmax，則執行步驟6。

步驟4 執行復制操作，k=k+1，若復制次數k>kmax，則執行步驟3。

步驟5 使用式(1)進行趨化操作，j=j+1，更新并保存適應度函數值。若趨化次數j>jmax，則執行步驟4。

步驟6 選取具有最大適應度函數值的細菌，對其對應的編碼進行解碼，輸出結果，結束。

3 集裝箱裝載算例和結果分析

實驗中算例采用國際上通常使用的標準20尺貨柜，尺寸大小為232*92.5*94cm。實驗比較了在相同集裝箱大小，對相同的貨物批次進行裝載。待裝貨物種類20種，每種貨物各3-10件不等，貨物參數由某物流公司裝箱貨物尺寸中隨機抽取，如表2所示，其長、深、高分別為li，wi，hi，單位為mm，質量為m。

表2 待裝貨品參數

為評價算法的性能及優越性，采用啟發式算法[4]、多目標多種群的隨機遺傳算法[5]、混合二元蟻群算法[6]和本文中提出的文中提出的基于自適應細菌覓食算法相比較。其中，文獻[4]中提出來包含樹型搜索子算法和貪心子算法的啟發式算法進行空間布局，但是未考慮到裝載的約束條件；文獻[5]中提出了三維空間切割模型，但為考慮到重量，承載等約束條件；文獻[6]中提出了混合二元蟻群算法求解，先用二元蟻群算法確定預備裝入貨物集，再用啟發式算法決定裝入優先級順序，雖大大提升裝載率，但算法復雜，時間復雜度較高。實驗對3個不同的裝箱訂單進行裝箱實驗三維仿真，圖2～圖4為3次裝箱效果，表3為3次裝箱的平均計算結果，且各對比算法中的參數設置與原文一致。

裝箱訂單1中，每種貨物取20件，最后共裝入貨物190件，裝載率達到94.76%，結果如圖2所示。

圖2 訂單1三維裝箱結果

裝箱訂單2中，每種貨物隨機取1-30件不等，結果共裝入貨物105件，裝載率達到93.69%，結果如圖3所示。

圖3 訂單2三維裝箱結果

裝箱訂單3中，每種貨物隨機取1-10件不等，結果共裝入貨物68件，裝載率達到91.76%，結果如圖4所示。

實例表明，在細菌趨化過程中極大地降低了細菌游動的復雜性，提升了算法性能，降低了時間復雜度，說明該算法在解決此類三維空間復雜問題上具有優勢。與此同時，自適應步長的設置，改善了傳統細菌覓食優化算法行進過程中易陷入局部極值的缺陷。在收斂時間上相較啟發式算法和蟻群算法也有優勢。實驗結果中的平均空間利用率為92.07%，和其它3種算法相比較，有了較明顯的提升。

圖4 訂單3三維裝箱結果

平均空間利用率/%算法平均收斂時間/s質量/kg標準差啟發式算法90.2014.90163.550.170蟻群算法91.0915.68166.300.162遺傳算法92.1613.47173.260.168自適應細菌覓食算法93.0713.53175.960.161

4 結束語

本文采用了基于順序表示的遺傳基因編碼方式，將動態裝載問題的各參數與及細菌覓食算法相結合，很好地規避了空間坐標編碼的缺陷，在集裝箱這類復雜度較高的問題上應用結果良好。改變細菌覓食算法中的固定步長，采用改進了的基于余弦的自適應步長算法，在前期步長大，區域搜索速度快，后期步長小利于局部尋優。在考慮裝箱過程中的其它因素，本文對于更復雜的多種類和多約束條件，這也是后續研究的一個方向。

[1]Ramos AG,Oliveira JF,Gon?alves JF,et al.Dynamic stabi-lity metrics for the container loading problem[J].Transportation Research Part C:Emerging Technologies,2015,60(6):480-497.

[2]CHENG Zhongwen.Solving three dimension container loading problem based on space-dividing genetic algorithm[J].Microcomputer Information,2012,54(10):286-287(in Chinese).[程中文.基于空間分割的遺傳算法解決三維裝載問題[J].微計算機信息,2012,54(10):286-287.]

[3]Liu S,Tan W,Xu Z,et al.A tree search algorithm for the container loading problem[J].Computers & Industrial Engineering,2014,75(2):20-30.

[4]Sheng L,Hongxia Z,Xisong D,et al.A heuristic algorithm for container loading of pallets with infill boxes[J].European Journal of Operational Research,2016,252(3):728-736.

[5]Zheng JN,Chien CF,Gen M.Multi-objective multi-population biased random-key genetic algorithm for the 3-D container loading problem[J].Computers & Industrial Engineering,2015,89(9):80-87.

[6]DU Lining,ZHANG Dezhen,CHEN Shifeng.Solution to complex container loading problem based on ant colony algorithm[J].Journal of Computer Application,2011,31(8):2275-2278(in Chinese).[杜立寧,張德珍,陳世峰.蟻群算法求解復雜集裝箱裝載問題[J].計算機應用,2011,31(8):2275-2278.]

[7]Peng J,El-Latif AAA,Li Q,et al.Multimodal biometric authentication based on score level fusion of finger biometrics[J].Optik-International Journal for Light and Electron Optics,2014,125(23):6891-6897.

[8]Reddy CHV,Siddaiah P.Bacterial foraging optimization algorithm(BFOA) optimized adaptive hybrid DWT-SVD watermarking with encryption[J].International Journal of Applied Engineering Research,2014,9(24):30911-30933.

[9]Huang YH,Hwang FJ,Lu HC.An effective placement method for the single container loading problem[J].Compu-ters & Industrial Engineering,2016,97(5):212-221.

[10]ZUO Xianliang,GUO Lili,GAO Shang.Improved estimation of distribution algorithm for solving multi-constrained container loading problem[J].Science Technology and Enginee-ring,2014,14(11):216-220(in Chinese).[左先亮,郭莉莉,高尚.改進分布估計算法解決多約束集裝箱裝載問題[J].科學技術與工程,2014,14(11):216-220.]

[11]LIU Zhen,SUN Jinghao.An improved bacterial foraging optimization algorithm[J].Journal of East China University of Science and Technology(Natural Science Edition),2016,42(2):225-232(in Chinese).[劉珍,孫京誥.一種改進的細菌覓食優化算法[J].華東理工大學學報(自然科學版),2016,42(2):225-232.]