文章編號：1002-3100（2016）06-0131-06

摘 要：文章將遺傳算法應(yīng)用于倉儲管理調(diào)度系統(tǒng)的儲位分配過程，分析了基本遺傳算法應(yīng)用于儲位分配的優(yōu)缺點。通過采用精英保留策略，保證了基本遺傳算法設(shè)計的多樣性，實現(xiàn)了算法搜索的快速收斂和最優(yōu)性能保持，克服了基本遺傳算法的“返祖”現(xiàn)象。

關(guān)鍵詞：改進(jìn)遺傳算法；精英保留策略；儲位分配

中圖分類號：F252.13 文獻(xiàn)標(biāo)識碼：A

Abstract： This thesis applies genetic algorithm into the storage allocation process of warehouse management dispatching system， and analyzes the advantages and disadvantages of applying genetic algorithm into storage allocation. By adopting elitism-reserved strategy， it has ensured the diversity of the basic genetic algorithm design， realized the fast convergence and optimal performance of algorithmic search， and has overcome the“atavism”phenomenon of basic genetic algorithm.

Key words： improved genetic algorithm； elitism-reserved strategy； storage allocation

1 研究背景

隨著經(jīng)濟(jì)的全球化，給很多跨國公司帶來前所未有的發(fā)展機遇，也給物流行業(yè)帶來新的發(fā)展契機。在國內(nèi)，電商企業(yè)如雨后春筍般的發(fā)展勢頭一個比一個好，也帶動物流業(yè)快速發(fā)展，與電商發(fā)展亦步亦趨，相輔相成。倉儲是物流的關(guān)鍵環(huán)節(jié)之一，只有擁有先進(jìn)的倉儲管理系統(tǒng)，具備完善的倉儲調(diào)度策略，才能在當(dāng)前激烈的市場競爭中不斷發(fā)展壯大。

眾多學(xué)者認(rèn)為，當(dāng)前世界經(jīng)濟(jì)處于經(jīng)濟(jì)危機后深度調(diào)整中，我國經(jīng)濟(jì)發(fā)展也在轉(zhuǎn)型中跨入新常態(tài)。就物流業(yè)當(dāng)前面臨的形勢來看，物流業(yè)的地位正處于快速發(fā)展機遇期，也意味著這一時期將是我國物流業(yè)發(fā)展的完善期和物流發(fā)展的拓展期。通過研究該領(lǐng)域的動態(tài)，不難發(fā)現(xiàn)我國物流業(yè)有以下幾種發(fā)展趨勢：

（1）物流平臺開始嶄露頭角，合同物流或?qū)⒅饾u退出

為了追求利益的最大化，物流業(yè)勢必面向平臺化整合，以替代合同物流。伴隨著電子商務(wù)的蓬勃發(fā)展，新的互聯(lián)網(wǎng)經(jīng)濟(jì)將傳統(tǒng)的TOB業(yè)務(wù)變革成TOC業(yè)務(wù)，這種散碎的物流服務(wù)是促進(jìn)物流平臺建設(shè)的有利基礎(chǔ)。

（2）在大數(shù)據(jù)的作用下，物流數(shù)據(jù)將成為新的價值點

從馬云對菜鳥的定位來看，“菜鳥”通過利用和整合獲得的數(shù)據(jù)和信息，找到新的物流成本壓縮點。合理分配存儲區(qū)域，去除物流發(fā)展資源利用不充分的大屏障。

從小的方面來看，做好倉儲內(nèi)部調(diào)度，合理安排貨物儲位也是適應(yīng)物流業(yè)發(fā)展的需要。因此本文利用遺傳算法，研究貨物上下架的優(yōu)化策略，通過改進(jìn)遺傳算法的搜索策略，快速實現(xiàn)貨物上下架調(diào)度。

2 遺傳算法的基本理論

遺傳解釋了生物能夠延續(xù)并不斷進(jìn)化的內(nèi)在機理及其規(guī)律，而遺傳算法正是誕生于生物科學(xué)和計算機科學(xué)的交叉點。將遺傳進(jìn)化的某些特質(zhì)，融合在計算機編程和算法的設(shè)計之中，應(yīng)用于工業(yè)控制、管理優(yōu)化等諸多方面。

2.1 遺傳算法的基本原理

遺傳算法（Genetic Algorithm，GA）是由美國密歇根（Michigan）大學(xué)心理學(xué)教授、電子工程和計算機科學(xué)教授Holland提出的一種隨機自適應(yīng)全局搜索算法。這種算法模擬的自然界生物遺傳進(jìn)化過程，對優(yōu)化問題的最優(yōu)解（近似解）進(jìn)行不斷的迭代搜索。算法在維護(hù)一個潛在解的集合（群體），對群體進(jìn)行優(yōu)化，在優(yōu)化過程中，算法引入了選擇、交叉、變異等遺傳算子。而遺傳算法在搜索全局最優(yōu)解過程中，是一個不斷迭代的過程（每次迭代相當(dāng)于自然界生物遺傳的一次進(jìn)化），直到算法滿足終止條件為止。

2.1.1 相關(guān)概念

（1）染色體

一個染色體是問題的一個有效解。相對于生物群體中的一個個體。遺傳算法的每個染色體，又由多個基因組成。如果將求解問題簡化稱一個y=fx的函數(shù)，那么染色體就可以看作變量x的取值。

（2）基因

可以認(rèn)為是問題的一個有效解的某一維的值。它的改變會改變一個染色體的適應(yīng)值，但一般不會引起整個種群發(fā)生太大變化。如果x的值由一段編碼組成，那么一個編碼序列可以看作是一個基因。

（3）適應(yīng)值

適應(yīng)值是用來表征一個染色體在群體中的優(yōu)劣程度。一般來說，一個染色體的值越大，該染色體離最優(yōu)解就越“近”。適應(yīng)值就可以看作是這個函數(shù)y=fx的應(yīng)變量y。

（4）評價函數(shù)

評價函數(shù)是用來計算一個染色體的適應(yīng)值的大小，判斷染色體優(yōu)劣的一個手段。對應(yīng)一個函數(shù)y=fx的對應(yīng)法則f。

（5）選擇算子

在對群體中若干個染色體進(jìn)行篩選時，需要依據(jù)一定的規(guī)則，選出一些適應(yīng)值較好的染色體進(jìn)入下一代。那么如何選擇，才能讓更多、（適應(yīng)值）更好的染色體從當(dāng)前過度到下一代，同時保證染色體分布不失均勻，這就取決于選擇算子。

（6）交叉算子

在對兩個染色體作用時，交換兩個染色體的部分基因，希望交換后，能從新的得到的染色體中能產(chǎn)生適應(yīng)值更好的一個或兩個染色體。為此而設(shè)計染色體概率性的交換基因片段的一個過程，使得算法能具備良好的全局搜索最優(yōu)解的能力。

（7）變異算子

對比交叉算子，那么使染色體的某個基因發(fā)生變化，可以讓算法具備較好的具備搜索最優(yōu)解的能力。

通常，傳統(tǒng)方法在求解某類優(yōu)化問題采用的都是分析問題的某些特質(zhì)，簡化問題的約束，針對該問題的特質(zhì)來求解。而Holland教授提出的遺傳算法的基本思想，卻不是去分析待求解問題的特質(zhì)，而是采用一種泛化的求解原則。

2.2 遺傳算法的基本流程

設(shè)計實現(xiàn)遺傳算法，通常有以下幾個比較重要的步驟：

（1）對群體進(jìn)行初始化：包括選擇適當(dāng)規(guī)模的群體，每個染色體的編碼方式，設(shè)計準(zhǔn)確的適應(yīng)度評價函數(shù)。

（2）群體適應(yīng)值評價：用評價函數(shù)計算染色體適應(yīng)值，并按照適應(yīng)值的優(yōu)劣，對染色體進(jìn)行排序。

（3）選擇種群進(jìn)入下一代：利用設(shè)計好的選擇算子，選出適應(yīng)值較優(yōu)秀的染色體進(jìn)入下一代。

（4）交叉操作產(chǎn)生新的染色體：利用交叉算子，產(chǎn)生一些新的染色體。一個染色體通過評價函數(shù)的計算，會對應(yīng)一個適應(yīng)值。而交叉操作一般設(shè)計成不定向的，故交叉操作等可能產(chǎn)生適應(yīng)值更差的染色體。

（5）變異操作產(chǎn)生新的染色體：利用變異算子，產(chǎn)生一些新的染色體，但是相比較交叉操作，變異后的新染色體，其適應(yīng)值可能變化不是特別大。

3 遺傳算法的應(yīng)用于倉儲優(yōu)化

現(xiàn)代物流的競爭力在于：如何向客戶提供更優(yōu)質(zhì)的服務(wù)，即服務(wù)效率高、物流過程安全。倉儲物流是物流的關(guān)鍵環(huán)節(jié)之一。本文重點研究倉儲物流的優(yōu)化，將智能算法引入倉儲物流過程中，實現(xiàn)對現(xiàn)有貨位的合理規(guī)劃。

現(xiàn)假設(shè)需將10個貨物堆放至一個規(guī)格為10×20的空貨架中，堆垛機事先通過3D標(biāo)簽獲得了各類貨物的進(jìn)出庫頻次和各個貨物的質(zhì)量。通常來說，我們在貨物入庫時會考慮一些因素：如質(zhì)量較大的貨物放置在貨架的底層，有利于貨架重心保持穩(wěn)定。進(jìn)出庫頻次較高的貨物放置在靠近出入巷道的位置，同時盡量放置在貨架的底層。

貨物的質(zhì)量和出入庫頻次如表1所示。

3.1 算法實現(xiàn)

（1）種群初始化

初始化產(chǎn)生一個擁有40個個體的種群pop，每個個體的特點就是10個貨物隨機散落在該10×20的貨架中。

5 結(jié) 論

對比采用精英保留策略和未采用該策略的10次運行結(jié)果，重復(fù)10次，計算最佳適應(yīng)值個體的平均值分別為705.8和765.4，平均減小7.78%。從圖5也能直觀看出，采用精英保留策略得到的最佳適應(yīng)值個體的優(yōu)化值基本優(yōu)于策略使用前的結(jié)果值。因此，通過采用精英保留策略來改進(jìn)遺傳算法，不僅能使得算法在運行過程中絕對收斂（單調(diào)趨優(yōu)），也能改進(jìn)算法的搜索性能。

參考文獻(xiàn)：

[1] 侯景超. 基于改進(jìn)遺傳算法的倉儲系統(tǒng)動態(tài)貨位優(yōu)化研究[D]. 沈陽：沈陽工業(yè)大學(xué)（碩士學(xué)位論文），2014.

[2] 張飛超. 基于微遺傳算法的倉儲布局優(yōu)化方法研究[D]. 錦州：遼寧工業(yè)大學(xué)（碩士學(xué)位論文），2015.

[3] 侯秋琚. 基于遺傳算法的中小型倉儲配送車輛路徑優(yōu)化策略[J]. 物流技術(shù)，2014（11）：210-211，243.

[4] 王健. 基于遺傳算法的倉儲貨位優(yōu)化研究[D]. 西安：西安建筑科技大學(xué)（碩士學(xué)位論文），2009.

[5] 趙建文. 遺傳算法在倉儲物流系統(tǒng)中的應(yīng)用研究[J]. 信息與電腦（理論版），2014（9）：139-141.