基于改進(jìn)遺傳算法求解堆垛機(jī)路徑優(yōu)化問題

陳 博，馮無(wú)恙

CHEN Bo1,2,FENG Wu-yang2

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

0 引言

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

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

1 自動(dòng)化立體倉(cāng)庫(kù)模型的建立

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

圖1 立體倉(cāng)庫(kù)貨格表示圖

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

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

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

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

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

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

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

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

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

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

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

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

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

3 路徑規(guī)劃方法

3.1 編碼

采用序號(hào)法。基本順序是從左到右，從下到上。將立體倉(cāng)庫(kù)分為若干個(gè)空格，從立體倉(cāng)庫(kù)的左下角的第一個(gè)格開始，給每一個(gè)空格一個(gè)序號(hào)N，依次延續(xù)，這樣序號(hào)N與立體倉(cāng)庫(kù)的每一個(gè)空格一一對(duì)應(yīng)。

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

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

3.2 初始種群

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

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

3.4 遺傳算子設(shè)計(jì)

3.4.1 選擇算子

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

3.4.2 交叉算子

采用部分匹配交叉法：先隨機(jī)產(chǎn)生兩個(gè) ，定義這兩點(diǎn)間的區(qū)域?yàn)槠ヅ鋮^(qū)域，并用位置操作交換兩個(gè)父代的匹配區(qū)域。如：交叉點(diǎn)為3、6父代A 8721309546 父代B 9835671420，先交換130與567，得出來(lái)的兩個(gè)過(guò)渡代為A’ 8725679546父代B’9831301420.對(duì)于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)變異算子，方法如下：在個(gè)體中隨機(jī)挑選兩個(gè)逆轉(zhuǎn)點(diǎn)，再將兩個(gè)逆轉(zhuǎn)點(diǎn)間的基因反序插入原位置。如個(gè)體A：987654321 ，在第3號(hào)位于第6號(hào)位采用逆轉(zhuǎn)變異算子。新生成的個(gè)體為987456321。

4 仿真分析

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

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

5 結(jié)論

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

圖4 仿真結(jié)果

圖5 各代差異性

[1] 孫樹棟,曲彥賓. 遺傳算法在機(jī)器人路徑規(guī)劃中的應(yīng)用研究[J]. 西北工業(yè)大學(xué)學(xué)報(bào),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ì)算機(jī)工程與應(yīng)用,2010,46(11)： 53-55.

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

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