自適應雙邊界約束遺傳算法的儲位分配研究

錢同惠+賴重遠+張仕臻+王波

摘 要： 在采用精英保留策略改進遺傳算法的基礎上，創(chuàng)新性地提出一種自適應雙邊界約束策略來改進遺傳算法，使改進后的算法在提升搜索效率上效果顯著，收斂性增強。實驗數(shù)據(jù)表明，自適應雙邊界約束遺傳算法應用于倉儲管理的儲位分配算法的尋優(yōu)平均效率提升77.8%，尋優(yōu)平均速度提升62.5%。

關鍵詞： 自適應； 雙邊界約束； 遺傳算法； 儲位分配

中圖分類號： TN911.1?34； F251 文獻標識碼： A 文章編號： 1004?373X（2017）17?0127?04

Research on storage distribution based on adaptive dual?boundary

constraints improving genetic algorithm

QIAN Tonghui， LAI Zhongyuan， ZHANG Shizhen， WANG Bo

（Institute for Interdisciplinary Research， Jianghan University， Wuhan 430056， China）

Abstract： On the basis of genetic algorithm improved with elitism?reserved strategy， an adaptive dual?boundary constraint strategy to improve genetic algorithm is put forward innovatively， which can improve search efficiency， and enhance its convergence. Experimental data shows that the adaptive dual?boundary constraint improving genetic algorithm is applied to storage distribution of warehouse management， whose average optimization efficiency is increased by 77.8%， and average optimization speed is increased by 62.5%.

Keywords： self?adaption； dual?boundary constraint； genetic algorithm； storage distribution

1 研究背景

倉儲管理是整個供應鏈管理的一個重要環(huán)節(jié)，近年來倉儲管理的合理化和人性化受到越來越多企業(yè)和管理者的重視，包括管理的系統(tǒng)化、信息化、現(xiàn)代化。其中，倉儲管理的核心之一是倉儲物流技術，包括采用更加柔性的智能制造系統(tǒng)，高度逼真的仿真技術，集成更加智能的倉儲管理軟件以及采用一些人工智能優(yōu)化控制算法等。在倉儲管理方面，儲位分配任務是一個高度復雜的調度任務，它直接決定了倉儲設備進出庫作業(yè)的效率，也是充分利用現(xiàn)有貨架資源的重要保證。在貨物資源快速流轉的現(xiàn)代物流現(xiàn)狀下，在保證貨物流通安全的同時不斷提高物流和倉儲效率是企業(yè)生存的重要競爭力。

2 自適應雙邊界約束遺傳算法應用于儲位分配

2.1 遺傳算法參數(shù)設置

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

貨物的質量和出入庫頻次見表1。設置遺傳算法參數(shù)，見表2。

設計評價函數(shù)：

（1）

式中：分別代表貨架的行、列以及待入庫貨物的序號；為待入庫貨物的質量和出入庫頻次；分別為出入庫規(guī)劃質量的權重以及出入庫頻次在貨架行列上的權重。

2.2 自適應雙邊界約束原理

遺傳算法執(zhí)行到一定階段，在變異算子設計過程中試著改變算法搜索的兩個邊界，并且隨著算法運行不斷將優(yōu)化結果的最優(yōu)個體值反饋到算法之中，這個反饋值作為一個動態(tài)約束邊界，從而實現(xiàn)算法的自適應雙邊界約束。

2.3 算法實現(xiàn)流程圖

自適應雙邊界約束改進策略遺傳算法運行的主要步驟包括：種群的初始化、適應值評價、個體排序（保存最優(yōu)個體——精英保留策略，為增強算法收斂性的可選策略）、選擇下一代個體、交叉操作、變異操作（需要自適應調整變異搜索范圍），迭代直到滿足結束條件。如圖1所示。

2.4 實驗運行結果

重復運行模型10次得到的結果見表3。

選取最早收斂個體適應值結果和最佳收斂個體適應值結果對比，見表4。

通過采用自適應雙邊界約束策略得到的最早收斂與最佳收斂曲線對比圖如圖2，圖3所示。

從圖2，圖3結果來看，貨物入庫狀態(tài)基本呈現(xiàn)出如下特點：

（1） 由于貨架初始狀態(tài)為空，所以算法基本能夠搜索到距離進出口位置最近的貨位。

（2） 貨物是成批（10個一批）入庫貨架，改進算法能夠實現(xiàn)貨物之間不留空貨位，盡可能搜索到離真實最優(yōu)解更近的近似最優(yōu)解。

（3） 貨物在貨架上的排布基本實現(xiàn)質量和進出庫頻次加權值較大的被優(yōu)先安排在貨架底層和進出口外層；貨物進出庫頻次被作為安排貨位的優(yōu)先因素。出現(xiàn)這種現(xiàn)象的原因是：貨物進出庫頻次數(shù)和貨物質量值計量單位不同且未均一化，進出庫頻次數(shù)這個動態(tài)值和貨物質量靜態(tài)值在動態(tài)調度規(guī)劃中不協(xié)調。

自適應雙邊界約束遺傳算法（帶精英保留策略）與精英保留策略改進遺傳算法運行結果對比見表5。

圖4的運行結果直觀展示出通過自適應雙邊界約束改進遺傳算法不僅使種群中個體最佳適應值均值從705.8直接降到397.0，大幅逼近真實最優(yōu)解。同時最佳適應值出現(xiàn)所需迭代次數(shù)（均值）從3 498.1降到了2 151.6；從表5中數(shù)據(jù)來看，采用雙邊界約束遺傳算法的迭代時間會有所延長，原因是雙邊界約束遺傳算法在后期能夠防止算法進入全局無目的搜索，通過自適應調節(jié)邊界范圍，逐步將搜索局域約束在某個動態(tài)邊界值以內，使得算法在自適應調整邊界的同時，加強算法的局部搜索能力。通過控制自適應調節(jié)的時機和步伐，能夠保證了算法優(yōu)化結果的全局最優(yōu)和快速局部搜索。

3 結 論

本文提出一種自適應雙邊界約束策略，算法運行過程中能夠自動調整搜索邊界，在保證算法前期全局搜索的同時，能夠增強算法后期的局部搜索能力和快速收斂性能。從圖2～圖4可以直觀看出，采用該策略前后，算法的尋優(yōu)平均效率提升77.8%，尋優(yōu)平均速度提升62.5%。由此可以看出，自適應雙邊界約束策略改進遺傳算法非常適合解決儲位分配管理優(yōu)化問題。

參考文獻

[1] 龍鋒.基于自適應遺傳算法的W公司倉庫貨位分配與優(yōu)化研究[D].廣州：華南理工大學，2015.

[2] 馬永杰.大型倉儲系統(tǒng)的調度算法研究[D].蘭州：蘭州交通大學，2011.

[3] 黨培.醫(yī)藥冷鏈物流倉儲管理系統(tǒng)關鍵問題研究[D].西安：陜西科技大學，2015.

[4] 孫曉琳.基于云模式的智能倉儲管理系統(tǒng)研究[D].武漢：武漢理工大學，2014.

[5] 黃剛.物流發(fā)展呈現(xiàn)多重新趨勢[J].經(jīng)理人，2014（5）：24?25.

[6] 王健.基于遺傳算法的倉儲貨位優(yōu)化研究[D].西安：西安建筑科技大學，2009.endprint