基于改進(jìn)自適應(yīng)遺傳算法的入庫貨位優(yōu)化研究

劉瑋瑋

摘 要： 探討了基于Srinivas M提出的線性自適應(yīng)遺傳算法，在此基礎(chǔ)上，從種群多樣性的表示上，對算法進(jìn)行了改進(jìn)，得出了一種新型自適應(yīng)遺傳算法。根據(jù)基本入庫原則和庫存現(xiàn)狀，將入庫時(shí)庫位選擇歸納為一個(gè)多目標(biāo)優(yōu)化問題，建立對應(yīng)的數(shù)學(xué)模型。將改進(jìn)的算法用于入庫貨位模型求解，結(jié)果表明，該算法能夠較好的解決入庫問題，選擇出最佳貨位，從而證明了算法的有效性。

關(guān)鍵詞： 倉儲效率； 貨位優(yōu)化； 改進(jìn)的自適應(yīng)遺傳算法； 多目標(biāo)優(yōu)化

中圖分類號：TP393.09 文獻(xiàn)標(biāo)志碼：A 文章編號：1006-8228（2018）08-57-04

Study on the warehousing slotting optimization based on

improved adaptive genetic algorithm

Liu Weiwei

（Faculty of Informatics， Fujian Vocational College of Agriculture， Fuzhou， Fujian 350001， China）

Abstract： This paper discusses the linear adaptive genetic algorithm which is presented by Srinivas M， on this basis， improves the algorithm from the representation of population diversity， and proposes a new adaptive genetic algorithm. According to the basic principle of warehousing and the status of inventory， the storage location selection is summarized as a multi-objective optimization problem， and a corresponding mathematical model is established. Using the improved algorithm to solve the storage location model， the result indicates that the algorithm can better work out the problem of warehousing and choose the best location， and then the validity of the algorithm is proved.

Key words： storage efficiency； slotting optimization； the improved adaptive genetic algorithm； multi objective optimization

0 引言

貨位優(yōu)化的目的是將倉庫黃金區(qū)域分給高頻撿取的貨物，從而實(shí)現(xiàn)最大化揀選效率以及最小化揀選成本， 還可方便補(bǔ)貨及平衡各工作區(qū)的工作量，這些能為倉儲管理提供有效的支撐并提高揀選的準(zhǔn)確性。當(dāng)前世界各物流管理公司推出了許多貨位優(yōu)化軟件，大致分為兩種，一種是與WMS綁定，另一種是適合中小規(guī)模倉庫使用并與WMS分離的。在貨位分配時(shí)考慮的原則一般包括[1]：貨架承載均勻，上輕下重；加快周轉(zhuǎn)，先入先出；提高可靠性，分巷道存放；提高效率，就近出入庫及產(chǎn)品相關(guān)性等。存儲位置的分配和實(shí)現(xiàn)策略[2]有分類存儲策略；改進(jìn)的先進(jìn)先出策略；隨機(jī)存儲策略；貨物相關(guān)性策略；共享存儲策略等。

1 入庫貨位分配模型的建立

入庫貨位優(yōu)化問題可描述如下。

已知：參見表1數(shù)據(jù)和擬入庫貨物的相關(guān)數(shù)據(jù)。

約束：⑴ 貨位分配原則；

⑵ 當(dāng)前倉庫貨位存儲狀況。

目標(biāo)：優(yōu)化貨位，提高貨位利用率及倉儲運(yùn)作效率。

本文的入庫分配模型由五個(gè)子模型組成，在貨物入庫對庫位進(jìn)行選擇時(shí)，需要綜合考慮這五個(gè)模型的值來選擇最優(yōu)貨位，根據(jù)商允偉等[3]、鄭凌鶯等[4]、邰世文[5]等人的研究成果，將貨位分配歸結(jié)為多目標(biāo)優(yōu)化問題，建立入庫貨位分配模型見式⑴，相關(guān)變量說明見表1。

2 改進(jìn)的自適應(yīng)遺傳算法

遺傳算法（Genetic Algorithm，GA）是一種基于生物進(jìn)化機(jī)制的隨機(jī)搜索算法，能夠有效地進(jìn)行概率意義下的全局搜索[6]。目前常見的自適應(yīng)遺傳算法有：線性自適應(yīng)遺傳算法、余弦自適應(yīng)遺傳算法、指數(shù)自適應(yīng)遺傳算法，本文改進(jìn)算法基于Srinivas M的線性自適應(yīng)遺傳算法[7]，見公式⑵：

當(dāng)個(gè)體適應(yīng)度較大而接近種群適應(yīng)度最大值時(shí)，Pc和Pm都會變的很小。在種群中個(gè)體適應(yīng)值為最優(yōu)值時(shí)，其變異概率為零，對最優(yōu)個(gè)體不進(jìn)行交叉和變異操作。Srinivas M以fmax-favg為標(biāo)準(zhǔn)來衡量種群多樣性，在整個(gè)種群適應(yīng)值水平較為平均時(shí)是可行的，但在種群最優(yōu)個(gè)體的適應(yīng)值是一個(gè)離群值，即其值是遠(yuǎn)離序列的一般水平極大值和極小值的情況下，再使用fmax-favg衡量種群多樣性就會失去意義。為防止此情況出現(xiàn)，使用種群個(gè)體適應(yīng)度的標(biāo)準(zhǔn)差代替fmax-favg，得出改進(jìn)的自適應(yīng)遺傳算法，即自適應(yīng)變異交叉概率公式[8]，即見式⑶，其中Pc1=0.7， Pc2=0.1，Pm1=0.1，Pm2=0.001：

⑶

為驗(yàn)證該改進(jìn)遺傳算法的性能，本文選取一個(gè)含有四個(gè)局部最優(yōu)解的函數(shù)作為測試函數(shù)， 因全局最優(yōu)解常被最差解包圍，如果遺傳算法的種群收斂性不好，則極易陷入局部最優(yōu)[9]。同時(shí)引用線性自適應(yīng)遺傳算法（LAGA）[7]、余弦自適應(yīng)遺傳算法（CAGA）[10]、冪指數(shù)自適應(yīng)遺傳算法（IAGA）[11]與本文算法進(jìn)行性能上的比較，本文改進(jìn)算法因使用了反三角函數(shù)故簡稱為AAGA[8]。測試函數(shù)f說明見表2所示。

可以看到在平均適應(yīng)度方面，本文算法的種群比其他自適應(yīng)遺傳算法的種群擁有更多的優(yōu)良個(gè)體和相對較強(qiáng)的自適應(yīng)能力，無論求解最大值還是最小值，該算法都有一定的優(yōu)勢。在最優(yōu)適應(yīng)度方面，本文算法也能更快地達(dá)到最優(yōu)解，且有較強(qiáng)的自適應(yīng)能力，從局部最優(yōu)走向全局最優(yōu)；且在收斂次數(shù)、平均收斂代數(shù)和平均收斂值三個(gè)方面，本文算法也具有一定優(yōu)勢。

3 入庫貨位分配模型求解

貨位優(yōu)化問題實(shí)際上是一個(gè)多目標(biāo)求解問題，多目標(biāo)優(yōu)化問題沒有絕對意義上的最優(yōu)，而只能平衡、協(xié)調(diào)多個(gè)目標(biāo)達(dá)到Pareto最優(yōu)解[12]。目前有許多使用遺傳算法對多目標(biāo)求解的方法，其中常用的有權(quán)重系數(shù)法、并列選擇法、排列選擇法等， 本文使用并列選擇法對前文所建立貨位分配模型求解。求解過程主要由四個(gè)部分組成：編碼機(jī)制、控制參數(shù)、適應(yīng)度函數(shù)和遺傳算子[6]，流程圖如圖3所示。

⑴ 編碼使用二進(jìn)制。假設(shè)倉庫有16*32個(gè)貨位，每個(gè)貨位可以使用橫縱坐標(biāo)（i，j）（i=1，2，3…16；j=1，2，3…32）進(jìn)行標(biāo)定，因使用二進(jìn)制編碼方式，橫坐標(biāo)使用四位二進(jìn)制編碼1111表示，縱坐標(biāo)使用五位二進(jìn)制編碼11111表示，標(biāo)識貨位的坐標(biāo)形式為（iiii，iiiii）（i=0，l）形式。為更好提高效率，將橫縱坐標(biāo)組合成為一體（iiii， iiiii）→iiiiiiii進(jìn)行編碼。

⑵ 解碼：根據(jù)編碼中規(guī)定的橫縱坐標(biāo)二進(jìn)制串的長度，將整個(gè)染色體劃分為兩部分，將橫縱坐標(biāo)當(dāng)中的二進(jìn)制子串轉(zhuǎn)換為對應(yīng)的十進(jìn)制，再根據(jù)十進(jìn)制數(shù)字得到具體貨位。

⑶ 初始化種群：交叉和變異概率分別為Pc1=0.8，Pc2=0.5，Pm1=0.04，Pm2=0.001，種群規(guī)模100，最大演化代數(shù)3000。

⑷ 適應(yīng)度函數(shù)設(shè)計(jì)：適應(yīng)度值的計(jì)算需要用到表1中的數(shù)據(jù)和入庫貨物的相關(guān)數(shù)據(jù)，包括貨位訂單號、貨物ID號、貨物數(shù)量和每件貨物的高度等。確定以上數(shù)據(jù)后，可使用建立的入庫貨位分配模型的五個(gè)數(shù)學(xué)模型計(jì)算倉庫當(dāng)中所有貨位的適應(yīng)度值，得到五個(gè)16*32的適應(yīng)度值矩陣，在遺傳算法的遺傳操作當(dāng)中，查表即可知某個(gè)貨位在某個(gè)函數(shù)下的適應(yīng)度值。

⑸ 遺傳操作：使用改進(jìn)自適應(yīng)遺傳算法計(jì)算個(gè)體發(fā)生交叉和變異的概率。算法的選擇算子采用無放回式隨機(jī)余數(shù)算法獲得，交叉算子采用單點(diǎn)交叉算法獲得，變異算子采用離散變異算法獲得，貨位高度參考企業(yè)提供限高信息，應(yīng)用時(shí)根據(jù)實(shí)際情況修改貨位限定高度即可。

表5列出了入庫時(shí)一些關(guān)鍵未知數(shù)據(jù)，其中倉庫入庫口坐標(biāo)和倉庫中最大坐標(biāo)為常量值，據(jù)每個(gè)倉庫的實(shí)際規(guī)劃獲得。

為1時(shí)表示以（i，j）為坐標(biāo)的貨位上有同一訂單的貨物；為0時(shí)表示該貨位上沒有同一訂單的貨物

決策變量。為1時(shí)表示以（i，j）為坐標(biāo)的貨位上有同一種貨物； 為0時(shí)表示該貨位上沒有同一種貨物 ]

圖4和圖5是本文算法AAGA求解入庫貨位分配模型最優(yōu)解的仿真過程，圖4為初始狀態(tài)的倉庫，其中方塊表示高度已經(jīng)高于250厘米不能再放置的貨位；菱形表示其高度在[100，250）之間的貨位；下三角表示其高度在[50，100）之間的貨位；上三角表示其高度在[0，50）之間的貨位，圖5為經(jīng)過本文算法標(biāo)記過的倉庫，其中用五角星標(biāo)記的坐標(biāo)（8，18）貨位是推薦的最優(yōu)貨位。

在具體的倉儲系統(tǒng)中，參照入庫貨位分配模型，本文算法可用Java等高級編程語言實(shí)現(xiàn)。進(jìn)行入庫操作時(shí)，倉庫管理員通過Android客戶端掃描貼在貨物上的二維碼，獲得貨物信息，輸入入庫數(shù)量， 信息提交給服務(wù)器端后， 服務(wù)器端根據(jù)傳遞的參數(shù)和算法進(jìn)行運(yùn)算，得出推薦入庫貨位后返回給客戶端顯示。

4 結(jié)論

本文首先根據(jù)基本的入庫原則和庫存現(xiàn)狀分析了影響倉儲運(yùn)營效率的入庫操作，將入庫時(shí)庫位選擇問題歸納為一個(gè)多目標(biāo)優(yōu)化問題，建立貨位分配數(shù)學(xué)模型；接下來闡述一種在自適應(yīng)函數(shù)對種群多樣性的表示上進(jìn)行改進(jìn)的遺傳算法，其在平均適應(yīng)度和最優(yōu)適應(yīng)度等方面，較之其他自適應(yīng)遺傳算法有一定優(yōu)勢；最后采用遺傳算法的并列選擇法對該貨位分配模型進(jìn)行求解，解決多目標(biāo)優(yōu)化問題。結(jié)果表明，這種改進(jìn)的自適應(yīng)遺傳算法用于所建立的貨位分配模型，能夠較好的解決入庫問題，選擇出最佳貨位。

參考文獻(xiàn)（References）：

[1] 左生龍，劉軍.現(xiàn)代倉儲作業(yè)管理[M].中國物資出版社，2006.

[2] 馬永杰，蔣兆遠(yuǎn)，楊志民.基于遺傳算法的自動(dòng)化倉庫的動(dòng)態(tài)

貨位分配[J].西南交通大學(xué)學(xué)報(bào)，2008，3（43）：415-420.

[3] 商允偉，裘聿皇，劉長有.自動(dòng)化倉庫貨位分配優(yōu)化問題研究[J].

計(jì)算機(jī)工程與應(yīng)用，2004.26：16-17

[4] 鄭凌鶯，張欣，言勇華.物流中心倉庫貨位優(yōu)化系統(tǒng)的設(shè)計(jì)研

究[J].物流技術(shù)，2006.6：33-34

[5] 邰世文.汽車零部件物流中心設(shè)施布局優(yōu)化研究[D].大連理

工大學(xué)，2013.

[6] 王雄志.配送中心配貨作業(yè)方法研究[M].中國經(jīng)濟(jì)出版社，

2008.

[7] Srinivas M，Patnaik L M. Adaptive probabilities of crossover

and mutation in genetic algorithms[J]. Systems， Man and Cybernetics， IEEE Transactions on，1994.24（4）：656-667

[8] 楊志龍.基于遺傳算法的倉庫管理系統(tǒng)的研究與實(shí)現(xiàn)[D].中

國海洋大學(xué)，2014.

[9] 韓瑞鋒.遺傳算法原理與應(yīng)用實(shí)例[M].兵器工業(yè)出版社，

2010.

[10] 石山，勵(lì)慶孕，王興華.基于自適應(yīng)遺傳算法的無刷直流電

機(jī)的優(yōu)化設(shè)計(jì)[J].西安交通大學(xué)學(xué)報(bào)，2002.12：1215-1218

[11] 金晶，蘇勇.一種改進(jìn)的自適應(yīng)遺傳算法[J].計(jì)算機(jī)工程與應(yīng)

用，2005.18：64-69

[12] Carlos F M， Peter F J. An overview of evolutionary

algorithms in multiobjective optimization[J]. Evolutionary Computation，1995.3（1）：1-16