改進遺傳算法在儲位分配優化研究

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

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

關鍵詞：改進遺傳算法；精英保留策略；儲位分配

中圖分類號：F252.13 文獻標識碼：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 研究背景

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

眾多學者認為，當前世界經濟處于經濟危機后深度調整中，我國經濟發展也在轉型中跨入新常態。就物流業當前面臨的形勢來看，物流業的地位正處于快速發展機遇期，也意味著這一時期將是我國物流業發展的完善期和物流發展的拓展期。通過研究該領域的動態，不難發現我國物流業有以下幾種發展趨勢：

（1）物流平臺開始嶄露頭角，合同物流或將逐漸退出

為了追求利益的最大化，物流業勢必面向平臺化整合，以替代合同物流。伴隨著電子商務的蓬勃發展，新的互聯網經濟將傳統的TOB業務變革成TOC業務，這種散碎的物流服務是促進物流平臺建設的有利基礎。

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

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

從小的方面來看，做好倉儲內部調度，合理安排貨物儲位也是適應物流業發展的需要。因此本文利用遺傳算法，研究貨物上下架的優化策略，通過改進遺傳算法的搜索策略，快速實現貨物上下架調度。

2 遺傳算法的基本理論

遺傳解釋了生物能夠延續并不斷進化的內在機理及其規律，而遺傳算法正是誕生于生物科學和計算機科學的交叉點。將遺傳進化的某些特質，融合在計算機編程和算法的設計之中，應用于工業控制、管理優化等諸多方面。

2.1 遺傳算法的基本原理

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

2.1.1 相關概念

（1）染色體

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

（2）基因

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

（3）適應值

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

（4）評價函數

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

（5）選擇算子

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

（6）交叉算子

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

（7）變異算子

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

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

2.2 遺傳算法的基本流程

設計實現遺傳算法，通常有以下幾個比較重要的步驟：

（1）對群體進行初始化：包括選擇適當規模的群體，每個染色體的編碼方式，設計準確的適應度評價函數。

（2）群體適應值評價：用評價函數計算染色體適應值，并按照適應值的優劣，對染色體進行排序。

（3）選擇種群進入下一代：利用設計好的選擇算子，選出適應值較優秀的染色體進入下一代。

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

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

3 遺傳算法的應用于倉儲優化

現代物流的競爭力在于：如何向客戶提供更優質的服務，即服務效率高、物流過程安全。倉儲物流是物流的關鍵環節之一。本文重點研究倉儲物流的優化，將智能算法引入倉儲物流過程中，實現對現有貨位的合理規劃。

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

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

3.1 算法實現

（1）種群初始化

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

5 結 論

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

參考文獻：

[1] 侯景超. 基于改進遺傳算法的倉儲系統動態貨位優化研究[D]. 沈陽：沈陽工業大學（碩士學位論文），2014.

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

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

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

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