基于免疫遺傳算法的貨位優(yōu)化研究

劉琪

沈陽工程學院信息學院, 遼寧 沈陽 110136

1 概述

自動化立體倉庫是現(xiàn)代物流倉儲管理模式中，所采用的一種高效的，簡便的，自動化的倉儲模式。使用自動化立體倉庫，可以讓使用者具備以下幾方面特點。

1.1 能夠對物品進行合理的儲存

提高存儲效率。由于自動化立體倉庫使用了計算機和自動控制系統(tǒng)。能夠對貨物的入庫，出庫，以及貨物位置的擺放，進行實時監(jiān)控。使貨物的管理能夠做到信息化，現(xiàn)代化管理[1]。

1.2 節(jié)約存儲空間

自動化立體倉庫能夠有效的利用立體空間，將原有的平面式存儲模式，改變成空間式的立體存儲模式。給企業(yè)以多種選擇倉庫地點的機會。可以在合適的地點進行倉庫的選址，使庫存的周期可以縮短，可以節(jié)約運輸成本，以提升倉儲物流的效率[1]。

1.3 信息化管理

能夠將貨物的信息通過條碼掃描，存儲進計算機。由計算機對自動化立體倉庫進行統(tǒng)一的管理，能夠對庫存，貨物分布的情況，進行合理的管理。提高企業(yè)對貨物管理的準確性和效率性。企業(yè)領導能夠及時，準確的了解貨物庫存的數(shù)目，以便做出對貨物相應的入庫，出庫的調整。能夠及時的為企業(yè)做出正確的決策。

2 貨位優(yōu)化

自動化立體倉庫的一個貨架，可以看作平面上的網格。根據(jù)從離出入庫口最近的貨位開始排列，1,2,3………X排，每個貨位都有自己的一個平面坐標（X,Y），但一個自動化立體倉庫有很多個貨架。所以，一個自動化立體倉庫貨位的坐標，

可以表示成三維坐標（X,Y,Z）。X表示貨位所在的貨架數(shù)，Y表示貨位所在的排數(shù)，Z表示貨位所在的層數(shù)。不同的貨物，要放在不同的貨位，每個貨物可以設置一個向量參數(shù)。（A，B，C），B可以代表一些貨物是否要臨近擺放，C可以代表貨物的重量[2]，A可以代表貨物的出入庫頻率。將要優(yōu)化的貨物的參數(shù)向量組成一個矩陣。再將所有的自動化立體倉庫的貨位組成一個矩陣。最后得出一個總的權值。這是一個多目標優(yōu)化的問題。通過免疫遺傳算法可以很好地解決這個問題。

3 免疫遺傳算法設計

免疫算法是從生物的免疫系統(tǒng)原理總結出來的。生物的免疫系統(tǒng)是防御疾病入侵的主要保衛(wèi)系統(tǒng)。免疫系統(tǒng)由免疫器官，免疫細胞，免疫分子組成。免疫細胞在免疫系統(tǒng)中發(fā)揮著非常重要的作用。抗原是指病毒，細菌，花粉等進入機體內的外來物質。

抗體是抗原刺激機體的免疫系統(tǒng)，由B淋巴細胞和記憶細胞增殖分化成的漿細胞產生的免疫球蛋白，它可與相應抗原發(fā)生特異性結合。免疫記憶是指在獲得性免疫方面，對某抗原發(fā)生反應，下一次相同抗原激勵時，反應會更為強烈。

免疫遺傳算法比遺傳算法具備很多優(yōu)勢，它將免疫算法中的免疫記憶功能，融合到遺傳算法中，并結合遺傳算法中的全局搜索能力，能夠快速的提高抗體的適應度，

免疫遺傳算法按照以下步驟設計：

3.1 隨機生成要解決問題的解的種群

根據(jù)自動化立體倉庫的貨位，來進行貨位優(yōu)化，可以將自動化立體倉庫的貨位按照第幾個貨架，貨架的第幾排，第幾層。作為一個貨位的向量，例如第一個貨架，第一排，第一層，向量表示為(1,1,1)。將每一個貨位，都按照向量表示，這樣就形成了一個解的種群。可以把要解決的問題，看作是抗原。解決問題的解，看作抗體。

3.2 選擇操作

3.3 交叉操作

在生物進化的歷史過程中，兩個染色體可以通過交叉操作，使得染色體可以重新構成，組合。從而形成一個新的染色體。生物中的染色體交叉環(huán)節(jié)是生物學，遺傳學中所描述的生物進化過程中的一個非常重要得環(huán)節(jié)。遺傳算法就是通過兩個解的交叉操作，產生一個新的解。在自動化立體倉庫貨位優(yōu)化的問題中，交叉操作可以是所有自動化立體倉庫貨位向量之間的一次重新組合。根據(jù)種群中適應度的高低，選擇適應度相對高的兩個解。隨機生成交叉點。并以交叉點的貨位為基礎，交換兩個解的某些貨位。交叉操作產生子代，子代繼承了父代的基本優(yōu)點。交叉操作的步驟是如何確定交叉貨位向量的位置，和如何進行部分貨位向量的交換。免疫遺傳算法中的交叉操作，是指對兩個經過輪盤賭算法選擇出來的兩個解按照算法的設計交換解的部分貨位向量。進而組成兩個新的解。遺傳算法中的交叉操作是遺傳算法區(qū)別于其他生物行為算法的一個重要特征。交叉操作是遺傳算法中的一個非常重要的操作，是產生一個新解的主要方法。

3.4 變異操作

遺傳算法中的變異操作，是從染色體變異啟發(fā)出來的。以初始解的變異概率為根本，對交叉之后的解，進行變異運算。在自然界的生物進化與遺傳行為中，生物的細胞的染色體的變異是由多種因素共同作用的結果，例如各種射線，溫度劇變，衰老等。進而變異成新的染色體，呈現(xiàn)出一種新的生命特征。在貨位優(yōu)化的問題中，可以將一個或幾個貨位進行變異操作，從而形成一個新的貨位向量的解。由于變異是小概率事件，所以只能是對交叉操作的一種補充[3]。

3.5 計算種群適應度

在遺傳算法中，應用適應度這個名詞解釋種群中各個解在大范圍搜索計算中接近最有利于解決該問題的解的一個適合程度。適應度大的解，能夠存活并遺傳到下一代的概率相對大一些，而適應度小的解，能夠存活并遺傳到下一代的概率相對小一些。

3.6 免疫記憶

應用到實際問題中就是根據(jù)原來的解，產生一個適應度更高，更為接近最優(yōu)解的解[4][5]。

4 仿真實驗

取八個貨物，每個貨物用一個向量表示，

將向量a1,a2,a3……a7,a8的轉置向量組合成一個矩陣F。選取第1個貨架，3排，4層的所有貨位組成矩陣G。使兩個矩陣相乘，最后算出適應度的總和。分別使用免疫遺傳算法和遺傳算法進行仿真實驗五次，取最佳貨位組合的平均適應度。如下表。

?

從上表得出免疫遺傳算法效率要優(yōu)于遺傳算法。

5 結束語

自動化立體倉庫是今后物流倉儲發(fā)展的必然趨勢。自動化立體倉庫和傳統(tǒng)倉庫相比，能夠節(jié)省更多空間，更為信息化，智能化。而對自動化立體倉庫進行貨位優(yōu)化，也是所有企業(yè)必須做的工作，進行貨位優(yōu)化，能夠節(jié)約經濟成本，人力成本。

[1]劉昌祺，董良. 自動化立體倉庫設計[M].北京：機械工業(yè)出版社,2004

[2]商允偉. 自動化倉庫貨位分配優(yōu)化研究.計算機工程與應用[J],2004.26:16-21

[3]田國會, 張攀等. 基于混合遺傳算法的固定貨架揀選優(yōu)化問題研究[J].機械工報,2004,40(02)

[4]王磊, 潘進,焦李成. 免疫算法.電子學報[J], 2000, 28(7):158-163

[5]亓霞，陳森發(fā)，黃鶴，周振國. 基于免疫算法的物流配送車輛路徑優(yōu)化問題的研究[J].土木工程學報,2003.7