陳 博，馮無恙

CHEN Bo1,2,FENG Wu-yang2

（1. 蘭州理工大學(xué) 數(shù)字制造技術(shù)與應(yīng)用省部共建教育部重點實驗室， 蘭州 730050；2. 蘭州理工大學(xué) 機(jī)電工程學(xué)院，蘭州 730050）

0 引言

現(xiàn)代化自動化立體倉庫要求作業(yè)迅速、準(zhǔn)確、穩(wěn)定等特點。其作業(yè)周期由出入庫臺的時間、貨物登記時間和堆垛機(jī)在倉庫存取貨物時間等組成。由于現(xiàn)代化立體倉庫的規(guī)模越來越大，其高度達(dá)50多米，長度也達(dá)150米，所以在整個物流周期中堆垛機(jī)的行駛時間占到整個倉庫作業(yè)周期的50%。如果堆垛機(jī)的調(diào)度不當(dāng)或選用效率較低的調(diào)度模式，會嚴(yán)重影響堆垛機(jī)的工作效率，進(jìn)而影響整個倉庫的作業(yè)效率。所以選擇一種較為合理的揀選路徑是提高堆垛機(jī)作業(yè)效率的方法。

自動化立體倉庫堆垛機(jī)在進(jìn)行工作時，要求根據(jù)某一原則，如行走路線總長度最短、能量消耗最少等，堆垛機(jī)在立體倉庫中沿著一條最優(yōu)的路徑行走?？梢赃@樣說堆垛機(jī)的路徑規(guī)劃問題可建模為一個有約束的優(yōu)化問題。在以前的論文中，主要是對堆垛機(jī)在立體倉庫中執(zhí)行多項存取貨物進(jìn)行研究，但通過在實際中的一系列考察，一方面現(xiàn)在企業(yè)中的堆垛機(jī)還是執(zhí)行單項任務(wù)的情況較多，即堆垛機(jī)從倉庫入口處取出貨物，然后運行到倉庫中的某一存放地點，之后再沿原路線返回。另一方面堆垛機(jī)在執(zhí)行一次任務(wù)時，并不是可以經(jīng)過立體倉庫中的任何一個地點，不同性質(zhì)（包括重量、體積、化學(xué)屬性）的貨物要按類分放，這就要求堆垛機(jī)在執(zhí)行存取任務(wù)時要避免經(jīng)過一些貨物存放點。綜上所述，就引出了本文所要解決的問題，堆垛機(jī)在以上兩個方面的約束下，怎樣實現(xiàn)路徑最短。

1 自動化立體倉庫模型的建立

假設(shè)堆垛機(jī)的工作空間(立體倉庫)用二維平面圖形來表示。堆垛機(jī)執(zhí)行一次任務(wù)時所不能通過的貨格的位置已知。用尺寸相同的柵格對立體倉庫進(jìn)行劃分。若某一柵格內(nèi)不含任何障礙物，則稱此柵格為自由柵格；反之，稱之為障礙柵格[2]。如圖1所示。

圖1 立體倉庫貨格表示圖

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

遺傳算法是一種借鑒生物界自然選擇和自然選擇機(jī)制的隨機(jī)化搜索算法，對于用傳統(tǒng)搜索方法難以解決的復(fù)雜和非線性問題具有良好的適應(yīng)性。但還有很多不足，如早熟收斂、易陷入局部最優(yōu)和收斂速度慢等。為此，本文將采用改進(jìn)的自適應(yīng)遺傳算法對堆垛機(jī)的工作環(huán)境進(jìn)行建模，找到堆垛機(jī)路徑優(yōu)化的最佳路徑。

當(dāng)今改進(jìn)遺傳算法的主要措施主要集中于對交叉概率和遺傳概率的選擇與確定，因為它們會影響遺傳算法的收斂性和搜索速度。針對不同的優(yōu)化目標(biāo)需要反復(fù)試驗來確定交叉概率和遺傳概率，而傳統(tǒng)的遺傳算法采用的是固定數(shù)值來代替交叉概率和遺傳概率，這是很難找到最佳優(yōu)化目標(biāo)。

自適應(yīng)遺傳算法(AGA)[2]是由Srinivas提出來的，它的基本思想是交叉概率Pc和變異概率Pm能夠隨著適應(yīng)度的變化而變化。當(dāng)種群各個體適應(yīng)度處于趨于一致或者局部最優(yōu)時，使Pc和Pm增加，從而避免陷入局部最優(yōu)，繼而引發(fā)早熟現(xiàn)象；當(dāng)群體各個體適應(yīng)度比較分散時，使Pc和Pm減少，從而不易破壞優(yōu)良個體，以利于優(yōu)良個體保存下來。同時，對適應(yīng)度高于群體平均適應(yīng)度的個體選擇較小的Pc和Pm，使得個體保存下來；那些低于群體平均適應(yīng)度的個體，選擇較大的Pc和Pm，一方面將一部分差的個體淘汰，另一方面增加新個體[3]。在自適應(yīng)遺傳算法中，交叉概率和變異概率按如下公式進(jìn)行調(diào)整：

fmax表示種群的最大適應(yīng)度，favg表示種群的平均適應(yīng)度，f'表示參與交叉的兩個個體中較大的個體的適應(yīng)度，f表示變異個體的適應(yīng)度。

AGA算法是有缺陷的，從公式中可以看出，當(dāng)個體適應(yīng)度越接近于最大適應(yīng)度（fmaxf'≈0）時，交叉概率和變異概率越小，到接近為零，這種 調(diào)整方法在群體優(yōu)化后期較為合適，因為在后期，要將優(yōu)良個體保存下來，即為全局最優(yōu)解。但是在進(jìn)化初期不利，因為在進(jìn)化初期群體中的較優(yōu)個體幾乎處于一種不發(fā)生變化的狀態(tài)，而此時的優(yōu)良個體不一定是全局最優(yōu)解，增加了進(jìn)化走向局部最優(yōu)解的可能性，就是所謂的早熟現(xiàn)象。

任子武等人在AGA的基礎(chǔ)上，提出了一種改進(jìn)的自適應(yīng)遺傳算法(IAGA)。它除了有AGA的一系列優(yōu)點之外，還彌補了AGA的缺陷。為了保證每一代的優(yōu)良個體不被破壞，采取了精英保留策略：如果下一代的最佳個體適應(yīng)度小于當(dāng)前種群的最佳個體適應(yīng)度，那么將當(dāng)前種群的最佳個體或者多個個體直接復(fù)制到下一代，從而不會被當(dāng)代種群的交叉和變異等遺傳操作破壞[4]。IAGA公式如下：

以上公式中，pc1，pc2分別表示交叉概率的最大值和最小值，pm1，pm2分別表示變異概率的最大值和最小值。

在IAGA算法中，根據(jù)公式，個體的交叉概率和變異概率應(yīng)根據(jù)個體的適應(yīng)度在平均適應(yīng)度和最大適應(yīng)度之間進(jìn)行線性變換。如果種群中存在較大規(guī)模的適應(yīng)度接近平均適應(yīng)度的個體，它的交叉概率最大，幾乎為Pc1和Pm1，若個體適應(yīng)度接近于最大適應(yīng)度，那么它的Pc和Pm很小，為Pc2和Pm2，即IAGA的自適應(yīng)交叉概率和變異概率曲線非常陡峭，導(dǎo)致一部分個體只能擁有較低的Pc和Pm，使進(jìn)化停滯不前，造成局部收斂[5]。

本文所要提出的新的改進(jìn)自適應(yīng)遺傳算法是根據(jù)種群的大小，適應(yīng)值的分布情況，自適應(yīng)變化整個種群的Pc和Pm，使它們的變化曲線為一個從振蕩而逐漸穩(wěn)定的形勢。設(shè)計進(jìn)化前期具有較大的Pc和Pm，以增強(qiáng)搜索能力，在進(jìn)化后期采取相對較低的Pc和Pm，以確定最佳個體。本文將采用正弦形式的自適應(yīng)遺傳算法(SAGA)，其公式如下：

如圖2和圖3所示，兩個公式的圖像均為正弦式圖像，從而保證了交叉概率和變異概率呈一種穩(wěn)定式變化，而不會出現(xiàn)過度陡峭曲線，因為-1〈sina〈1,它可以弱化由于適應(yīng)度接近平均適應(yīng)度或者接近最大適應(yīng)度而造成的Pc和Pm的過大或者過小，也克服了由于種群停滯不前而陷入局部最優(yōu)的現(xiàn)象。

圖2 自適應(yīng)交叉概率正弦曲線

圖3 自適應(yīng)變異概率正弦曲線

3 路徑規(guī)劃方法

3.1 編碼

采用序號法?；卷樞蚴菑淖蟮接?，從下到上。將立體倉庫分為若干個空格，從立體倉庫的左下角的第一個格開始，給每一個空格一個序號N，依次延續(xù)，這樣序號N與立體倉庫的每一個空格一一對應(yīng)。

采用序號法來表示堆垛機(jī)行走的路徑，主要是因為序號法與坐標(biāo)法作比較可節(jié)省內(nèi)存，表達(dá)簡潔清楚，更為重要的是便于以后的遺傳算子（選擇算子、交叉算子、變異算子）的操作。

我們將堆垛機(jī)在立體倉庫的一條運動路徑稱之為一個個體，在這里假設(shè)堆垛機(jī)由起始位置A經(jīng)過這一條路徑最終到達(dá)終點位置B，那么這條路徑可以表示為一個個體。采用序號法，則表示為（0,1,11,13,22,32,34,45,56,66,77,87,88,99）。我們從中可以看出，每條路徑采用序號法具有編碼長度短、簡明、直觀的優(yōu)點。

3.2 初始種群

初始群體是遺傳算法迭代運算的起點，它是由一定數(shù)目的個體所組成。一般情況下，在倉庫空格數(shù)目較大的情況下產(chǎn)生初始群體采用計算機(jī)隨機(jī)生成法，但是我們要求初始群體的所有路徑具有目的性、無障礙性。從起點出發(fā)，利用局部搜索技術(shù)隨機(jī)選取與前一個點相鄰的非障礙物點作為下一路徑點，以此類推，直至找到終點。如路徑 S={x1，x2xn}。

3.3 個體適應(yīng)度函數(shù)

3.4 遺傳算子設(shè)計

3.4.1 選擇算子

采用輪盤賭選擇法和精英保留法相結(jié)合的方法，是個體按照與適應(yīng)度成正比例的概率向下一代群體繁殖。

3.4.2 交叉算子

采用部分匹配交叉法：先隨機(jī)產(chǎn)生兩個 ，定義這兩點間的區(qū)域為匹配區(qū)域，并用位置操作交換兩個父代的匹配區(qū)域。如：交叉點為3、6父代A 8721309546 父代B 9835671420，先交換130與567，得出來的兩個過渡代為A’ 8725679546父代B’9831301420.對于A’、B’中的匹配區(qū)域以外出現(xiàn)的數(shù)碼重復(fù)，要依據(jù)匹配區(qū)域內(nèi)的位置逐一進(jìn)行交換。

5—1,6—3,7—0。子代A 8025679143 子代B 9861305427。

3.4.3 變異算子

在堆垛機(jī)優(yōu)化路徑上屬于典型的TSP問題，其變異算子采用逆轉(zhuǎn)變異算子，方法如下：在個體中隨機(jī)挑選兩個逆轉(zhuǎn)點，再將兩個逆轉(zhuǎn)點間的基因反序插入原位置。如個體A：987654321 ，在第3號位于第6號位采用逆轉(zhuǎn)變異算子。新生成的個體為987456321。

4 仿真分析

采用Matlab遺傳算法工具箱對此進(jìn)行仿真測試。設(shè)種群規(guī)模為40，每個種群的長度為20，交叉概率Pc=0.9，變異概率為Pm=0.01,然后利用SAGA對每一代的交叉概率和變異概率進(jìn)行計算。在Matlab窗口中輸入Gatool,打開、進(jìn)入遺傳算法工具箱。之前必須將適應(yīng)度函數(shù)寫成M文件。輸入遺傳算法工具出啟時的界面。圖為遺傳算法過程中群體中每一代個體最佳適應(yīng)度隨進(jìn)化代數(shù)的變化情況。如圖4所示上圖中較為密集的點為每一代的最佳適應(yīng)度值，而其上的點表示平均適應(yīng)度值。可以看出，算法收斂較快，進(jìn)化到約34代就已經(jīng)搜索到了最優(yōu)解。在早期個代中，當(dāng)個體離理想值較遠(yuǎn)時，最佳值會迅速得到改進(jìn)；在后來各代中，種群越接近最佳點，最佳值改進(jìn)的越慢，以上這些順應(yīng)了SAGA的要求。圖5為代與代平均個體之間的平均距離。

通過圖5所示我們可以清晰的看到自適應(yīng)算法在算完100代之后，這其中的每一代的具體情況，可以看出各代之間的差異性。

5 結(jié)論

本文提出了改進(jìn)的自適應(yīng)遺傳算法(SAGA)，不僅克服了傳統(tǒng)遺傳算法的早熟和收斂速度慢問題，而且大幅度提高遺傳算法的工作效率。此方法應(yīng)用于堆垛機(jī)的路徑規(guī)劃，可以提高堆垛機(jī)的路徑規(guī)劃質(zhì)量和工作效率。通過Matlab遺傳算法工具箱的仿真，進(jìn)一步驗證了此方法的有效性和可行性。

圖4 仿真結(jié)果

圖5 各代差異性

[1] 孫樹棟,曲彥賓. 遺傳算法在機(jī)器人路徑規(guī)劃中的應(yīng)用研究[J]. 西北工業(yè)大學(xué)學(xué)報,1998. 16(1)：79-83.

[2] Srinvas M,Patnaik L M.Adaptive probabilities of crossover and mutation in genetic algorithms[J]. IEEE Trans on Systems,Man and Cybernetics.1992.24(6)： 656-667.

[3] 張京釗,江濤. 改進(jìn)的自適應(yīng)遺傳算法[J]. 計算機(jī)工程與應(yīng)用,2010,46(11)： 53-55.

[4] 任子武,傘冶. 自適應(yīng)遺傳算法的改進(jìn)及在系統(tǒng)辨識中應(yīng)用研究[J]. 系統(tǒng)仿真學(xué)報,2006,18(1)： 41-66.

[5] 張國強(qiáng),彭曉明. 自適應(yīng)遺傳算法的改進(jìn)與應(yīng)用[J]. 艦船電子工程. 2010.1： 83-84.