基于改進遺傳算法的AGV路徑規(guī)劃

孫 波，姜 平+，周根榮，董殿永

(1.南通大學 電氣工程學院，江蘇 南通 226019；2.南通大學 圖書館，江蘇 南通 226019)

0 引 言

隨著自動引導運輸車(automated guided vehicle，AGV)[1]在工業(yè)生產(chǎn)中的廣泛應用，其路徑規(guī)劃也成為目前的熱點問題之一。路徑規(guī)劃算法主要有傳統(tǒng)算法(如Dijkstra算法[2,3]、A*算法[4,5])和智能優(yōu)化算法(如蟻群算法[6,7]、粒子群算法[8]和遺傳算法[9-12]等)之分。由于遺傳算法具有較好的并行性和魯棒性，被廣泛應用于AGV路徑規(guī)劃中，但算法本身卻有早熟收斂和局部搜索能力較弱等缺點。針對遺傳算法的這些缺點，已經(jīng)有不少的改進方案被提出，如文獻[9]提出了一種將障礙物凸化處理的地圖模型建立法，方便了遺傳算法的初始種群生成；文獻[10]對自適應算子進行新的修改，提高了算法初期進化的能力；文獻[11]提出了一種結合禁忌搜索算法的初始種群生成方法；文獻[12]提出了一種多次隨機交叉法來維持種群的多樣性。雖然上面的各種改進操作提升了遺傳算法的部分性能，但是算法仍然存在一些缺點需要優(yōu)化：首先，算法的選擇操作并沒有實質(zhì)性的改進；其次，算法的設計沒有結合實際運行環(huán)境。

本文結合AGV路徑規(guī)劃的特點，對基本遺傳算法進行了相關改進操作，首先將模擬退火思想引入到算法的種群選擇操作中，并對交叉、變異的方法進行改進優(yōu)化，增加了種群中個體的差異性，讓算法可以更好跳出局部最優(yōu)解。此外，在建立適應度函數(shù)時，引入路徑曲折度、繁忙度和車輛負重度等規(guī)劃指標，使得規(guī)劃出來的路徑更符合實際情況。

1 環(huán)境模型的建立

在路徑規(guī)劃前，首先要對AGV的運行環(huán)境進行合理的地圖建模，本文采用拓撲地圖法對AGV的運行空間進行環(huán)境建模。圖1為本文采用的地圖模型，其中S，V2，…，V20，G等稱為節(jié)點，表示實際工廠中的AGV工作站；節(jié)點之間的數(shù)據(jù)稱為路徑權值，表示AGV行走路徑的相關信息，采用Dis(α,β) 的形式表示，其中Dis為兩節(jié)點間的實際距離，α表示路徑的曲折度等級(最大為10級)，β表示路徑的繁忙度等級(最大為10級)；S為路徑規(guī)劃起始點，G為路徑規(guī)劃的目標點。

圖1 AGV路徑規(guī)劃地圖模型

2 路徑規(guī)劃算法

2.1 編碼方式

在AGV的路徑規(guī)劃中，可以將AGV自起始點到目標點的運行路徑作為遺傳算法中的一條染色體。由于本文的環(huán)境模型為拓撲地圖模型，故采用變長度的符號編碼方式[13]，將地圖模型中的節(jié)點號對應于染色體中的基因，當然相鄰的基因必須是地圖中的相連節(jié)點。如圖1中，一條可行路徑可以表示為：S→V5→V8→V12→V14→V19→G。

2.2 適應度函數(shù)

為提高AGV在運行過程中的安全性，減少AGV間或AGV與障礙物間碰撞的發(fā)生，本文引入AGV負重度、路徑曲折度和路徑繁忙度等規(guī)劃指標，對AGV的運行速度進行如下制約

(1)

其中，Vt為小車在無規(guī)劃指標下的運行速度(本文默認為0.5 m/s)，μ為AGV的負重系數(shù)(1≤μ≤2，無負載時為1，滿負載時為2)，α為路徑曲折度等級(等級數(shù)為1-10級，等級數(shù)越大，路徑越曲折)，β為路徑繁忙度等級(等級數(shù)為1-10級，等級數(shù)越大，路徑中可能同時存在的車輛數(shù)越多)，D為最大等級數(shù)(本文取10)。

本文把路徑規(guī)劃的評價依據(jù)設定為AGV從起始點行駛到目標點所花費的時間，在車輛負重度、路徑曲折度和路徑繁忙度等規(guī)劃指標下，結合式(1)，可得適應度函數(shù)為

(2)

式中：Dis(Xij) 為個體Mt中節(jié)點i和節(jié)點j之間的路徑長度，μij為AGV在該段路徑中的負重系數(shù)，αij為該段路徑的曲折度等級，βij為該段路徑的繁忙度等級，D為最大等級數(shù)。從式(2)中可以看出：規(guī)劃出的最優(yōu)路徑對應的適應度函數(shù)值也將最小。

2.3 初始種群

在初始種群的產(chǎn)生過程中，生成的個體不能存在斷路和環(huán)路狀況，并且初始種群中，應該盡量避免重復的個體產(chǎn)生，初始種群的具體產(chǎn)生步驟如下：

(1)將起始點S放在集合C中；

(2)隨機選取與起始點相連的一個節(jié)點按順序放在集合C中；

(3)判斷集合C中最后一個節(jié)點是否為目標點，如果是則執(zhí)行步驟(7)，否則執(zhí)行步驟(4)；

(4)取出與集合C最后一個節(jié)點相連的所有節(jié)點于集合N中；

(5)去掉集合N中與集合C重復的節(jié)點；

(6)隨機選取集合N中的一個節(jié)點按順序放在集合C中，執(zhí)行步驟(3)進行判斷；

(7)判斷種群中與本個體重復個體數(shù)量，如果重復個體少于2個，則本個體生成成功(即為集合C內(nèi)容)，執(zhí)行步驟(8)，否則執(zhí)行步驟(1)，重新生成一個新個體；

(8)判斷是否達到種群規(guī)模，如果達到種群規(guī)模則初始種群生成成功，否則執(zhí)行步驟(1)，進行新一輪的個體產(chǎn)生。

2.4 遺傳操作

2.4.1 選擇操作

由于輪盤賭選擇方式會使后代產(chǎn)生的個數(shù)與父代個體的適應度大小成正比，容易造成“早熟”現(xiàn)象[14]。為了兼顧種群的多樣性和避免優(yōu)秀個體被破壞，在進行選擇操作時，不采用傳統(tǒng)的輪盤賭選擇法，改引用模擬退火算法的選擇思想進行種群選擇，然后對新產(chǎn)生的種群執(zhí)行改進后的精英保留策略，即按一定比例淘汰種群中較差個體，同時復制一些優(yōu)秀個體并使它們不經(jīng)過交叉和變異操作而直接保留到下一代，以保證種群個體的合理性。

模擬退火算法來源于固體的物理退火原理，給定固體一個較高的初始溫度，讓其按一定的降溫速率衰減，在降溫過程中結合概率選擇特性，在解空間中尋找最優(yōu)解，直到溫度降到設定的最低溫度時退火結束。模擬退火操作主要采用式(3)的形式來確定算法產(chǎn)生新解的接收概率，由于其可以很好跳出局部最優(yōu)，被廣泛地應用于其它算法的改進工作之中[15]

(3)

式中：f(m)、f(n) 分別為進化前和進化后的適應度函數(shù)值，T為系統(tǒng)的當前溫度值，并隨時間衰減。其計算公式如下

T=T0×qt

(4)

式中：T0、q和t分別為系統(tǒng)的起始溫度、降溫速率和迭代的次數(shù)。

2.4.2 交叉操作

交叉操作采用單點交叉法，具體步驟如下：

(1)取出父代個體V1和V2中除起始點和目標點外的共同節(jié)點于集合Nc中，如果集合Nc非空則執(zhí)行下一步，否則執(zhí)行第(5)步；

(2)任選集合Nc中一節(jié)點i作為交叉點；

至此，矩陣Φ中的每個向量都是非標準正交的，需使這些向量除以對應的得到標準正交基函數(shù){φ1,φ2,…,φN}，即POD模態(tài)。將瞬態(tài)速度場投影到POD基函數(shù)上，求出各模態(tài)的系數(shù)。通過計算得到所有POD模態(tài)及對應的模態(tài)系數(shù)，可線性重構任意時刻的速度場，有

(3)對V1和V2執(zhí)行關于i節(jié)點的交叉操作，其過程如圖2所示；

(4)判斷交叉后的兩個子個體中節(jié)點i前后是否存在相同節(jié)點，如果不存在則本次交叉完成，否則執(zhí)行下一步；

(5)若兩個父代個體沒有交叉點或交叉操作生成的新個體不是一個完整的路徑，則認為本次交叉失敗，此時將父代個體中較優(yōu)的一個作為子個體1，而子個體2則重新生成。

圖2 交叉操作

2.4.3 變異操作

變異操作的具體過程為：

(1)從待變異父個體V中隨機選取一個節(jié)點i(不包括起始點和目標點)作為變異節(jié)點，將父個體V分成兩條路徑r1和r2；

(2)按類似于初始種群產(chǎn)生的方法生成兩條路徑，一條為從起始點S到節(jié)點i的路徑R1(要求R1中不包含r2的其它節(jié)點)，一條為從節(jié)點i到目標點G的路徑R2(要求R2中不包括r1的其它節(jié)點)；

(3)若步驟(2)可以實現(xiàn)，則將R1和r2，r1和R2組成兩個新的個體，否則執(zhí)行步驟(5)；

(4)計算步驟(3)產(chǎn)生的兩個個體的適應度函數(shù)，選取較優(yōu)的一個個體作為變異操作產(chǎn)生的子個體，變異操作完成，如圖3所示；

(5)生成的子個體存在斷路或環(huán)路情況，視為變異操作失敗，按交叉失敗中子個體2產(chǎn)生法重新生成一個新個體。

圖3 變異操作過程

2.4.4 交叉和變異算子自適應調(diào)整

在遺傳算法中，算法的收斂速度和搜索結果很大情況下會受到交叉概率Pc和變異概率Pm的影響。如果交叉概率Pc較大，則可以很快地產(chǎn)生新個體，但適應度較高的個體可能會被破壞，若Pc值取的較小，則會拖慢系統(tǒng)的進化速度；如果變異概率Pm的取值太大，則不利于算法的收斂，Pm取的值太小，則新個體的產(chǎn)生困難，種群多樣性變差[16]。在文獻[17]中Srinvivas等提出一種自適應遺傳算法，其表達式如下

(5)

(6)

式中： 0

從公式分析中可以看出，這種調(diào)節(jié)方法不利于進化初期時種群中較優(yōu)個體的變化，容易導致進化出現(xiàn)早熟收斂現(xiàn)象，又加上該調(diào)整方式是針對求最大適應度值的方法，所以按式(7)和式(8)進行修改，使種群中最小適應度的個體的交叉變異率不為0，分別提高到了Pc2和Pm2，提高了種群中較優(yōu)個體的交叉概率和變異概率，加快了進化的進行[18]

(7)

(8)

式中：fmin、favg、f′、f分別為最小適應度值、平均適應度值、交叉操作中小的適應度值以及變異個體的適應度值，由于在種群選擇中采用了模擬退火法的選擇操作和改進后的精英保留策略，所以這里的交叉、變異概率可以取較大值，Pc1=0.9，Pc2=0.6，Pm1=0.3，Pm2=0.1。

2.5 算法流程圖

算法流程圖如圖4所示，算法的終止條件為：最優(yōu)解在連續(xù)40次的進化中都沒有改變或進化的次數(shù)達到系統(tǒng)預設的上限。式(4)所示的為系統(tǒng)最大的進化次數(shù)計算公式

(9)

式中：T0為初始溫度，q為降溫速率，Tend為終止溫度。在本文中，取初始溫度T0=5000℃，終止溫度Tend=0.0005℃，降溫速率q=0.9，則最大進化次數(shù)tmax=153。

圖4 算法流程

3 仿真結果分析

3.1 仿真結果對比

采用MATLAB軟件對圖1所示的地圖模型進行路徑規(guī)劃的編程驗證，適應度函數(shù)為式(2)，運行速度Vt=0.5 m/s，負重系數(shù)μ=1。為增加合理性對比驗證，分別對基本遺傳算法、自適應遺傳算法和本文改進遺傳算法進行多次實驗，最后用Dijkstra算法規(guī)劃出最短路徑進行實際驗證，得最優(yōu)路徑為：S→V2→V4→V7→V17→V18→V19→V16→G，適應度函數(shù)值為46.74 s。

在基本遺傳算法中，種群規(guī)模、交叉概率和變異概率分別選擇為：M=10、Pc=0.6、Pm=0.1，選擇方式為輪盤賭選擇，終止條件為進化次數(shù)達到tmax或連續(xù)40代最優(yōu)解不變，找到的最優(yōu)路徑為：S→V3→V6→V10→V13→V15→V16→G，進化曲線如圖5所示。

圖5 基本遺傳算法進化曲線

自適應遺傳算法在基本遺傳算法的基礎上按式(7)、式(8)進行交叉和變異概率自整定，為保證優(yōu)良個體不被破壞，加入改進后精英保留策略，其它條件不變，找到的最優(yōu)路徑為：S→V2→V4→V7→V17→V18→V19→G，進化曲線如圖6所示。

圖6 自適應遺傳算法最優(yōu)解進化曲線

本文改進遺傳算法在自適應遺傳算法的基礎上引入模擬退火的選擇思想，退火參數(shù)如式(9)中所示，其它條件不變，得到最優(yōu)路徑為：S→V2→V4→V7→V17→V18→V19→V16→G，進化曲線如圖7所示。

圖7 改進遺傳模擬退火算法最優(yōu)解進化曲線

從圖5到圖7可以看出，平均值曲線波動越大，說明種群的差異性越大，算法跳出局部最優(yōu)解的可能性就越大。最優(yōu)解收斂速度越快，說明算法的執(zhí)行效率越高。基本遺傳算法不僅種群差異性非常小，算法收斂的速度也非常慢，并且因為沒有應用精英策略，導致種群中的優(yōu)良個體遭到破壞，使算法陷入局部最優(yōu)，不利于算法的運行。自適應遺傳算法相較于基本遺傳算法，種群差異性和算法的收斂速度都有明顯改善，但是由于輪盤賭的選擇方式會使后代產(chǎn)生的個數(shù)與父代個體的適應度大小成正比，導致種群中個體的多樣性被破壞，容易造成“早熟”現(xiàn)象。本文改進的遺傳算法采用Metrolpis接收準則來接收交叉、變異后的新解，所以種群中不同個體的數(shù)量比較多，易跳出局部最優(yōu)解。如圖7所示，即使初始產(chǎn)生的最優(yōu)解不是很好(比圖5、圖6的初始最優(yōu)解都要差)，但是由于種群差異性大，算法也可以很快找到最優(yōu)解。

為驗證本算法的通用性，把本算法應用于5種不同的自制地圖，每張地圖各進行1000次仿真，為對比本文改進算法的有效性，分別與基本遺傳算法，自適應遺傳算法(加入精英保留策略)進行平均搜索速度和搜索成功率的比較。對比結果見表1和表2。

表1 平均搜索時間對比

5張自制地圖信息如下：地圖1有16個節(jié)點，24條路徑；地圖2即為本文地圖，21個節(jié)點，36條路徑；地圖3有30個節(jié)點，55條路徑；地圖4有40個節(jié)點，77條路徑；

表2 3種算法的搜索成功率對比

地圖5有50個節(jié)點，102條路徑。對于算法的相關參數(shù)，除種群規(guī)模改為20外，其它參數(shù)保持不變。

從表1和表2中可以看出：隨著節(jié)點數(shù)的增加，改進遺傳算法的搜索速度和搜索成功率比基本遺傳算法和傳統(tǒng)自適應遺傳算都有很大的提高。在地圖3的設計上，故意設計了多條干擾路徑，但本算法仍能較為準確地規(guī)劃出最優(yōu)路徑，改進后的算法在實際應用中有很好的通用性。

3.2 不同指標下的規(guī)劃結果

圖8所示的分別是：在AGV小車速度Vt=0.5 m/s，負重系數(shù)μ=1的情況下，不考慮路徑曲折度和繁忙度規(guī)劃出的路徑L1，路徑為：S→V5→V8→V11→V18→V19→V16→G；只將路徑曲折度作為規(guī)劃指標規(guī)劃出來的路徑L2，路徑為：S→V3→V6→V10→V13→V15→V16→G；路徑曲折度和繁忙度都作為規(guī)劃指標規(guī)劃出來的路徑L3，路徑為：S→V2→V4→V7→V17→V18→V19→V16→G。

圖8 不同規(guī)劃指標下的最優(yōu)路徑

3條路徑在不同指標參數(shù)下的適應度值見表3。從圖8和表3中我們可以看出：在不同參數(shù)下，本文改進后的遺傳算法均能正確規(guī)劃出系統(tǒng)的最優(yōu)路徑；在路徑規(guī)劃過程中需考慮到諸多環(huán)境因素，這樣規(guī)劃出的路徑才更高效，也更貼近實際情況，如表3中，無規(guī)劃指標，一個規(guī)劃指標和兩個規(guī)劃指標規(guī)劃出的路徑是不同的，雖然AGV負重系數(shù)μ的改變不會影響規(guī)劃出路徑的結果，但可以較為準確的規(guī)劃出AGV從起始點到目標點的運行時間，這樣對多AGV系統(tǒng)的調(diào)用，輸送系統(tǒng)的時間規(guī)劃都有非常重要的意義。

表3 3條路徑在不同規(guī)劃指標下的適應度值

4 結束語

針對AGV在路徑規(guī)劃存在的問題，對自適應遺傳算法進行相關修改優(yōu)化，在多次實驗對比驗證后，表明了本算法在AGV路徑規(guī)劃方面的應用是高效的。其主要特點如下：

(1)對交叉、變異方法進行相關改進，提高了種群中新個體的產(chǎn)生能力，加大了種群個體的差異性。

(2)對自適應交叉、變異算子進行改進，同時將精英保留策略應用于選擇操作中，提高了算法的求解效率。

(3)引入模擬退火思想，使得初期種群個體差異性大，易于跳出局部最優(yōu)解。

(4)適應度函數(shù)中引入路徑曲折度、路徑繁忙度以及車輛負重度等評價指標，使得規(guī)劃出的最優(yōu)路徑更安全可靠、更切合實際。

本算法若要實際應用到工業(yè)生產(chǎn)中，還需考慮一些問題：首先是搜索速度和穩(wěn)定性，仍有待提高；其次是本算法只是靜態(tài)路徑規(guī)劃，對AGV運行過程中的突發(fā)情況沒有考慮，所以靜態(tài)和動態(tài)的組合路徑規(guī)劃也是進一步的研究方向。