基于改進遺傳算法求解堆垛機路徑優化問題

陳 博，馮無恙

CHEN Bo1,2,FENG Wu-yang2

（1. 蘭州理工大學 數字制造技術與應用省部共建教育部重點實驗室， 蘭州 730050；2. 蘭州理工大學 機電工程學院，蘭州 730050）

0 引言

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

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

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

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

圖1 立體倉庫貨格表示圖

2 改進的自適應遺傳算法

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

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

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

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

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

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

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

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

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

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

圖2 自適應交叉概率正弦曲線

圖3 自適應變異概率正弦曲線

3 路徑規劃方法

3.1 編碼

采用序號法。基本順序是從左到右，從下到上。將立體倉庫分為若干個空格，從立體倉庫的左下角的第一個格開始，給每一個空格一個序號N，依次延續，這樣序號N與立體倉庫的每一個空格一一對應。

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

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

3.2 初始種群

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

3.3 個體適應度函數

3.4 遺傳算子設計

3.4.1 選擇算子

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

3.4.2 交叉算子

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

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

3.4.3 變異算子

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

4 仿真分析

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

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

5 結論

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

圖4 仿真結果

圖5 各代差異性

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

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

[5] 張國強,彭曉明. 自適應遺傳算法的改進與應用[J]. 艦船電子工程. 2010.1： 83-84.