文章編號(hào)：1002-3100（2016）06-0131-06

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

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

中圖分類號(hào)：F252.13 文獻(xiàn)標(biāo)識(shí)碼：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ā)展機(jī)遇，也給物流行業(yè)帶來新的發(fā)展契機(jī)。在國內(nèi)，電商企業(yè)如雨后春筍般的發(fā)展勢(shì)頭一個(gè)比一個(gè)好，也帶動(dòng)物流業(yè)快速發(fā)展，與電商發(fā)展亦步亦趨，相輔相成。倉儲(chǔ)是物流的關(guān)鍵環(huán)節(jié)之一，只有擁有先進(jìn)的倉儲(chǔ)管理系統(tǒng)，具備完善的倉儲(chǔ)調(diào)度策略，才能在當(dāng)前激烈的市場(chǎng)競(jìng)爭(zhēng)中不斷發(fā)展壯大。

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

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

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

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

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

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

2 遺傳算法的基本理論

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

2.1 遺傳算法的基本原理

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

2.1.1 相關(guān)概念

（1）染色體

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

（2）基因

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

（3）適應(yīng)值

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

（4）評(píng)價(jià)函數(shù)

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

（5）選擇算子

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

（6）交叉算子

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

（7）變異算子

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

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

2.2 遺傳算法的基本流程

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

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

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

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

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

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

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

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

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

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

3.1 算法實(shí)現(xiàn)

（1）種群初始化

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

5 結(jié) 論

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

參考文獻(xiàn)：

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

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

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

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

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