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

劉琪

沈陽工程學(xué)院信息學(xué)院, 遼寧 沈陽 110136

1 概述

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

1.1 能夠?qū)ξ锲愤M(jìn)行合理的儲存

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

1.2 節(jié)約存儲空間

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

1.3 信息化管理

能夠?qū)⒇浳锏男畔⑼ㄟ^條碼掃描，存儲進(jìn)計(jì)算機(jī)。由計(jì)算機(jī)對自動化立體倉庫進(jìn)行統(tǒng)一的管理，能夠?qū)齑?，貨物分布的情況，進(jìn)行合理的管理。提高企業(yè)對貨物管理的準(zhǔn)確性和效率性。企業(yè)領(lǐng)導(dǎo)能夠及時(shí)，準(zhǔn)確的了解貨物庫存的數(shù)目，以便做出對貨物相應(yīng)的入庫，出庫的調(diào)整。能夠及時(shí)的為企業(yè)做出正確的決策。

2 貨位優(yōu)化

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

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

3 免疫遺傳算法設(shè)計(jì)

免疫算法是從生物的免疫系統(tǒng)原理總結(jié)出來的。生物的免疫系統(tǒng)是防御疾病入侵的主要保衛(wèi)系統(tǒng)。免疫系統(tǒng)由免疫器官，免疫細(xì)胞，免疫分子組成。免疫細(xì)胞在免疫系統(tǒng)中發(fā)揮著非常重要的作用?？乖侵覆《荆?xì)菌，花粉等進(jìn)入機(jī)體內(nèi)的外來物質(zhì)。

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

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

免疫遺傳算法按照以下步驟設(shè)計(jì)：

3.1 隨機(jī)生成要解決問題的解的種群

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

3.2 選擇操作

3.3 交叉操作

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

3.4 變異操作

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

3.5 計(jì)算種群適應(yīng)度

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

3.6 免疫記憶

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

4 仿真實(shí)驗(yàn)

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

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

?

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

5 結(jié)束語

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

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

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

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

[4]王磊, 潘進(jìn),焦李成. 免疫算法.電子學(xué)報(bào)[J], 2000, 28(7):158-163

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