基于遺傳算法的軍隊被裝物資貨位優(yōu)化研究?

（陸軍勤務(wù)學(xué)院 重慶 401331）

1 引言

被裝是軍隊裝備的常服、禮服、作訓(xùn)防護服、標(biāo)志服飾、臥具、裝具的總稱，是軍人作戰(zhàn)、訓(xùn)練、生活的重要物質(zhì)基礎(chǔ)[1]。貨位優(yōu)化是指給儲存的各種物資分配合適的貨位，使總體儲存效益達到最優(yōu)[2]。被裝物資的貨位分配問題影響著揀選效率和出入庫效率，與被裝保障水平緊密聯(lián)系。貨位優(yōu)化以提升倉儲作業(yè)效率和空間利用率、降低成本、增加貨架穩(wěn)定性為目標(biāo)。因此，貨位優(yōu)化問題通常是多目標(biāo)優(yōu)化問題，需要通過建立數(shù)學(xué)模型，并運用算法求得最優(yōu)解。本文將建立被裝物資貨位優(yōu)化的模型，并使用遺傳算法求解模型，得到最優(yōu)的貨位分配方案。

2 貨位優(yōu)化模型的建立

2.1 問題描述與條件假設(shè)

分配貨位要遵循兩條重要的原則[3～4]：1）周轉(zhuǎn)率原則，將周轉(zhuǎn)率高的物資安排在離出口較近的貨位上。2）重心原則，考慮貨架在垂直和水平方向上的穩(wěn)定性，將重量大的物資儲存在低層，在水平方向上的擺放也要盡量均勻。根據(jù)這兩條原則，將優(yōu)化目標(biāo)定為縮短物資出庫時間和增加貨架穩(wěn)定性，模型假設(shè)以自動化立體庫為背景，但對于采用貨架儲存物資的普通倉庫也有借鑒作用[5]。

現(xiàn)假設(shè)某座庫房中有n排貨架，每個貨架有m列貨格和l層，那么這座庫房總的貨位數(shù)為nml個 。 用 x，y，z（x∈[1 ，n]，y∈[1 ，m]，z∈[1 ，l]，x，y，z∈Z）分別表示貨位所在的排、列、層，每個貨位的坐標(biāo)可以表示為（x，y，z），比如（2，5，6）就表示第2排第5列第6層的貨位。此外，假設(shè)每個貨位只存放一個托盤，每個托盤上只儲存一箱物資。同時，為方便計算，忽略堆垛機在取貨時伸縮機械臂所耗費的時間，且在每排貨架的同一側(cè)作業(yè)。一些涉及到計算的其他參數(shù)的假設(shè)情況如表1所示。

表1 各參數(shù)的值

2.2 建立模型

第一個優(yōu)化目標(biāo)是減少出庫時間，在堆垛機運行速度一定的情況下，要減少出庫時間就要縮短所有物資出庫移動距離之和[6]。為了簡化計算，假設(shè)只有一臺堆垛機。堆垛機從原點（0，0，0）出發(fā)，先沿x軸方向水平運行，到達目標(biāo)貨位所在排時，進入巷道內(nèi)沿y軸水平運行，到達目標(biāo)貨位所在列時，再沿z軸垂直運行，最終到達目標(biāo)貨位（x，y，z）。堆垛機在x軸方向運行時，要經(jīng)過（x-1）個貨格，同時考慮到每兩排貨架間的距離，即巷道的寬度為S0，假設(shè)堆垛機運行到巷道口中心位置再進入，則所經(jīng)過的巷道數(shù)為（x-1-1/2）個。堆垛機進入巷道后，首先運行到目標(biāo)貨位所在列的第一層貨格的底部中心位置，然后再開始上升。因此，在前往目標(biāo)貨位所在列的過程中，堆垛機要經(jīng)過的貨格數(shù)為（y-1/2）個。到達目標(biāo)貨位所在列后，堆垛機在上升過程中要經(jīng)過的貨格數(shù)為（z-1）個。堆垛機在水平方向和垂直方向上的運行速度分別為Vh和VV，因此貨位坐標(biāo)為（x，y，z）的物資從貨位到出口的移動時間ti為

將貨架上所儲存的物資搬運到出口所耗費的總時間還與各種物資的周轉(zhuǎn)率Pi有關(guān)，即，因此，物資出庫效率優(yōu)化的目標(biāo)函數(shù)可表示為

第二個優(yōu)化目標(biāo)是提高貨架穩(wěn)定性。貨架的穩(wěn)定性由其垂直重心和水平重心決定，假設(shè)質(zhì)量為G1、G2……Gn的物資被分別存放在高度為H1、H2……Hn的貨位上，那么此貨架的垂直重心位置為

一個貨格的重心通常在其幾何中心，要使整個貨架在水平方向上的穩(wěn)定性達到最佳，就要盡量讓其水平重心靠近水平方向的中心位置，即mL0/2（貨架長度的1/2）處。因此，貨架水平重心位置Gy可表示為

為了優(yōu)化貨架整體穩(wěn)定性，要使Gz和Gy之加權(quán)和取最小值，假設(shè)兩者的權(quán)重c1和c2均為0.5。綜上，貨架穩(wěn)定性優(yōu)化的目標(biāo)函數(shù)可表示為

綜上，建立貨位優(yōu)化的多目標(biāo)模型如下：

其中，1≤x≤n，1≤y≤m，1≤z≤l，且均為整數(shù)。

3 運用遺傳算法求解模型

根據(jù)多目標(biāo)優(yōu)化問題的本質(zhì)，各個目標(biāo)函數(shù)之間是存在相互沖突的關(guān)系的，不存在使所有目標(biāo)函數(shù)都達到最優(yōu)狀態(tài)的解，因此只能取得一組折中解，即帕累托最優(yōu)解[7]。在解決多目標(biāo)優(yōu)化問題上，遺傳算法具有獨特的優(yōu)勢：1）可廣泛地對可行解進行表示，直接對問題的結(jié)構(gòu)對象進行操作。2）群體搜索。不同于許多傳統(tǒng)的算法，遺傳算法可以同時處理多個個體并對解進行評估。3）限制條件較少。遺傳操作的基礎(chǔ)是適應(yīng)度函數(shù)值，不受函數(shù)連續(xù)性的約束。4）不易陷入局部最優(yōu)，找到全局最優(yōu)解的能力較強。因此，遺傳算法適用于解決被裝物資貨位優(yōu)化問題。

3.1 遺傳算法基本原理

遺傳算法（Genetic Algorithm，GA）是一種模擬生物的遺傳和進化機制的自適應(yīng)概率優(yōu)化技術(shù)，這個概念最早在1967年由美國密歇根大學(xué)的學(xué)生Bagley首次提出，Bagley的老師Holland教授在1975年提出了遺傳算法的系統(tǒng)論述。生物通過染色體的交叉和變異完成進化，遺傳算法通過特定的編碼方法產(chǎn)生“染色體”，并對“染色體”上的基因進行選擇、交叉、變異，通過對個體進行評價篩選，最后找到最好的“染色體”。它從一個隨機的初始種群出發(fā)，對其中的個體進行選擇、交叉、變異，形成新一代種群。通過數(shù)次迭代，種群不斷進化，最后收斂得到適應(yīng)能力最強的種群，即得到問題的最優(yōu)解[8]。遺傳算法的主要運行步驟如下。

第一步，編碼。確定所要解決的問題的變量及相關(guān)參數(shù)后，變量x即可作為個體的“表現(xiàn)型”，用特定的編碼方式對x進行處理后得到的字符串即為它的“基因型”，編碼就是表現(xiàn)型與基因型之間的映射，它是遺傳算法識別個體的基礎(chǔ)。例如，采用二進制編碼方法時，將十進制數(shù)1850轉(zhuǎn)化為二進制數(shù)11100111010的過程就是編碼，十進制數(shù)是表現(xiàn)型，二進制數(shù)是基因型。

第二步，產(chǎn)生初始種群。隨機生成n個初始個體，即特定的結(jié)構(gòu)數(shù)據(jù)，可以是二進制串，也可以是實數(shù)結(jié)構(gòu)，由這些個體構(gòu)成初始種群。遺傳算法以初始種群為起點進行迭代，迭代次數(shù)根據(jù)問題復(fù)雜程度確定，對于比較簡單的問題，通常經(jīng)過50至200次迭代就可找到最優(yōu)解；對于一些很復(fù)雜的問題，迭代次數(shù)可達到數(shù)千次甚至上萬次。

第三步，計算個體的適應(yīng)度。適應(yīng)度值表明個體的優(yōu)劣程度[9]。將個體代入到目標(biāo)函數(shù)中進行計算，得到目標(biāo)函數(shù)值。通常目標(biāo)函數(shù)是求得最小解，若優(yōu)化問題的目標(biāo)是求最小解，則無需轉(zhuǎn)化。若優(yōu)化問題的目標(biāo)是求最大解，則需對目標(biāo)函數(shù)值進行轉(zhuǎn)化，獲得個體的適應(yīng)度值。

第四步，選擇。根據(jù)個體的適應(yīng)度值，通過特定的方法從當(dāng)前種群中選擇適應(yīng)度值較高的個體，這些個體將成為父代參與產(chǎn)生子代個體。適應(yīng)能力強的個體為下一代提供優(yōu)良基因的概率更大，體現(xiàn)出了達爾文進化學(xué)說中適者生存的思想。

第五步，交叉。以設(shè)定好的交叉概率Pc對不同父代個體的染色體片段進行交換，這樣子代個體將擁有父代個體的組合特性。交叉操作是將父代優(yōu)良基因遺傳給子代的關(guān)鍵，能提高種群的適應(yīng)能力。

第六步，變異。以設(shè)定好的變異概率Pm對隨機選中的個體的結(jié)構(gòu)數(shù)據(jù)進行隨機的改變，即對某個體染色體上隨機位置的基因值進行改變，例如將二進制串11100111010中第3位上的1變異為0，其對應(yīng)的表現(xiàn)型就由十進制數(shù)1850變成了1594。自然界中變異概率很低，但變異能增加種群基因的多樣性。

經(jīng)過上述操作后得到的群體進入下一次迭代，當(dāng)?shù)螖?shù)達到設(shè)定的上限值時，遺傳算法終止，輸出最適應(yīng)的個體，得到最優(yōu)解[10]。

3.2 貨位優(yōu)化的相關(guān)數(shù)據(jù)

以自動化立體庫為例，選取其中一個區(qū)域的貨架作為優(yōu)化樣本，在這個區(qū)域中有3排貨架，每排貨架有5列、6層。同時，選取10種品名的被裝作為儲存在這一區(qū)域貨架上的物資，這10種被裝物資的初始貨位分配情況如表2所示。在這10種被裝物資中，囊括了軍服、軍鞋、裝具等多個品種，在周轉(zhuǎn)率、重量方面跨度較大，具有很好的代表性，適于作為貨位優(yōu)化的樣本。這些被裝物資的初始貨位是隨機分配的。

表2 被裝物資初始貨位分配情況

3.3 算法設(shè)計

1）編碼。本文采用實數(shù)編碼，一條染色體表示一種貨位分配結(jié)果，從左至右依次包含一個貨位的坐標(biāo)、儲存在該貨位上的物資的周轉(zhuǎn)率、物資的質(zhì)量，其結(jié)構(gòu)為xyzpiGi。例如，染色體1 2 1 0.2 18就是一個解，表示周轉(zhuǎn)率為0.2，質(zhì)量為18kg的被裝品種被分配到坐標(biāo)為（1，2，1）的貨位上進行儲存。

2）生成初始種群。確定編碼方法就得到了個體的表示方法。染色體1 2 1 0.2 18代表一種貨位分配結(jié)果，10條染色體組成一個個體，即一個包含全部10種被裝物資貨位分配結(jié)果的方案，初始種群就是由若干個個體組成的[11]。初始種群大小設(shè)定為50個，即隨機產(chǎn)生50個貨位分配方案。將x、y、z進行排列組合，產(chǎn)生n*m*l（n=3，m=5，l=6）種貨位坐標(biāo)，即90種貨位坐標(biāo)，將其儲存在一個90×3的矩陣A中。然后，生成[1，90]之間的隨機整數(shù)，取前10個數(shù)作為矩陣A的行向量序號，例如前10個數(shù)為 8，2，10，7，4，3，6，9，5，1，就取矩陣A的第8，2，10，7，4，3，6，9，5，1行為10種被裝物資的貨位坐標(biāo)，與它們的周轉(zhuǎn)率和質(zhì)量結(jié)合起來，成為一個10×5的矩陣，每一個行向量代表一個貨位分配結(jié)果，整個矩陣表示一個個體，這樣就生成了一個初始個體：

將這個方法循環(huán)運行50次，就得到了含有50個個體的初始種群。

3）計算目標(biāo)函數(shù)。前文已建立了被裝物資貨位優(yōu)化模型，可直接將個體代入模型進行計算，得到該個體的目標(biāo)函數(shù)值。個體的目標(biāo)函數(shù)值越小，則表示該個體適應(yīng)度越大，即貨位分配結(jié)果更優(yōu)。

4）遺傳操作。（1）選擇：先使用RANKING函數(shù)對個體進行適應(yīng)度值的分配，然后用根據(jù)適應(yīng)度值大小FitnVi進行選擇。若總共有u個個體，一個個體被選擇的概率為

適應(yīng)度值較大的個體可能被多次選擇。（2）交叉：對當(dāng)前種群中的個體進行重組，每個矩陣中奇數(shù)行和偶數(shù)行進行配對重組，得到新的個體。由于本文要解決的問題是組合優(yōu)化問題，被裝物資的周轉(zhuǎn)率和質(zhì)量是一一對應(yīng)的，不能改變，因此只有它們的貨位坐標(biāo)進行交叉，本文把交叉概率pc設(shè)定為0.6。（3）變異：先將貨位坐標(biāo)轉(zhuǎn)化為二進制數(shù)，再使用變異函數(shù)對其進行變異。變異完成后，再將二進制數(shù)轉(zhuǎn)化為十進制數(shù)，獲得變異后的貨位坐標(biāo)。

5）迭代。設(shè)定迭代次數(shù)為50，當(dāng)上述操作完成一次后，進入下一次迭代，直到迭代次數(shù)滿50次為止。在迭代過程中，目標(biāo)函數(shù)會逐漸收斂，最后得到最優(yōu)解。

4 使用Matlab運行遺傳算法

以Matlab7.1作為實現(xiàn)遺傳算法的軟件，加載由英國謝菲爾德大學(xué)開發(fā)的遺傳算法工具箱GAT?BX，這個工具箱中包含了實現(xiàn)遺傳算法所需的多種函數(shù)，能夠很好地解決多目標(biāo)優(yōu)化問題。將表1中的參數(shù)寫入到一個M文件中[12]，編寫被裝物資貨位優(yōu)化問題的遺傳算法程序，然后運行程序，得到貨位優(yōu)化結(jié)果并進行分析。

4.1 貨位優(yōu)化結(jié)果

運行Matlab程序，可獲得模型的求解結(jié)果，包括各目標(biāo)函數(shù)的最小值、模型的帕累托最優(yōu)解、目標(biāo)函數(shù)圖像等。最優(yōu)解如表3所示，其中的貨位坐標(biāo)是優(yōu)化后的結(jié)果。效率優(yōu)化目標(biāo)函數(shù)在50次迭代過程中的圖像如圖1所示，其中，位于上方的曲線表示解的平均值的變化過程，下方的曲線表示最優(yōu)解的變化過程。貨架穩(wěn)定性優(yōu)化目標(biāo)函數(shù)的圖像如圖2所示。

表3 優(yōu)化后的貨位分配情況

4.2 結(jié)果分析

由圖1可以看出，迭代開始時，效率優(yōu)化目標(biāo)函數(shù)值最高處于22左右的水平。在運行到第1代和第10代之間時，函數(shù)值在19～22之間浮動。此后，函數(shù)值基本穩(wěn)定在19左右，其平均值也呈明顯下降趨勢。從圖2可以看出，目標(biāo)函數(shù)值經(jīng)過15次迭代，由17.9左右下降到17.4左右，此后基本收斂在17.4，其平均值也在18.1左右收斂。表4中列舉了優(yōu)化前后的貨位分配方案的目標(biāo)函數(shù)值，可以看出，效率優(yōu)化目標(biāo)函數(shù)值下降了29.9%，物資出庫效率得到顯著提升。同時，貨架穩(wěn)定性優(yōu)化目標(biāo)函數(shù)值下降了6.0%，兩目標(biāo)函數(shù)之和下降了20.1%，說明模型整體優(yōu)化效果較好。

圖1 效率優(yōu)化目標(biāo)函數(shù)迭代過程

圖2 貨架穩(wěn)定性優(yōu)化目標(biāo)函數(shù)迭代過程

表4 優(yōu)化前后效果比較

綜上所述，遺傳算法全局搜索、并行運算的特點使它能高效地求解多目標(biāo)優(yōu)化問題，并且能直觀地展現(xiàn)出優(yōu)化過程，具有很強的實用性。本文建立的被裝物資貨位優(yōu)化模型基本達到了預(yù)期目標(biāo)，在物資出庫效率和貨架穩(wěn)定性兩個方面取得了較好的優(yōu)化效果。由此可見，根據(jù)貨位分配原則設(shè)定明確的貨位優(yōu)化目標(biāo)，建立相應(yīng)的數(shù)學(xué)模型，然后運用適當(dāng)?shù)墓ぞ哌M行求解，根據(jù)實際情況將得到的優(yōu)化結(jié)果進行調(diào)整和應(yīng)用，就能取得儲存規(guī)劃的優(yōu)化效果，提高被裝倉儲作業(yè)的效率。

5 結(jié)語

通過運用遺傳算法在MATLAB中模擬被裝物資貨位優(yōu)化，驗證了這個多目標(biāo)組合優(yōu)化問題的一種有效解決方案，同時也為解決類似問題提供參考。物流行業(yè)正處在上升期，軍事物流建設(shè)還有很長的路要走。要保障打贏未來戰(zhàn)爭以及保障非戰(zhàn)爭軍事任務(wù)，軍事物流信息化建設(shè)有至關(guān)重要的作用?；ヂ?lián)網(wǎng)技術(shù)和人工智能發(fā)展迅猛，軍事物流信息化建設(shè)也充滿機遇。通過理念創(chuàng)新與技術(shù)融合，讓軍事物流信息化的進步為強軍事業(yè)提供全方位的有力保障。