改進遺傳算法在AGV路徑規劃的應用

白云飛，胡大裟，蔣玉明，馮魯波

(1. 四川大學計算機學院，成都 610065；2. 四川省大數據分析與融合應用技術工程實驗室，成都 610065)

0 前言

隨著全球工業自動化時代的到來，自動導引小車(Automated Guided Vehicle，AGV)在工業生產中起到了中流砥柱的作用。AGV對于提高工業生產效率、減少工作人員負擔和降低生產成本具有重要意義。而路徑規劃是AGV完成工業生產過程中物料配送的前提。在過去的幾十年里，研究人員做了許多工作。其中重要的算法有Dijkstra算法、A*算法等經典方法，以及智能優化算法，如蟻群算法和遺傳算法[1]。

由于遺傳算法在路徑規劃問題中，可以通過需求設定不同的編碼方式，具有更好的魯棒性和全局搜索能力，因此被廣泛的應用到AGV路徑規劃中。但算法本身卻有易陷入局部最優和收斂速度慢等缺點，不少學者對此進行了一些改進。如文獻[2]利用自整定優化策略改進雙交叉算子，并引入靜態路徑繁忙程度改進適應度函數，使規劃后的路徑更符合實際情況。文獻[3]優化傳統遺傳算法中的雙交叉算子和變異算子，提出一種利用地圖特征信息的改進型遺傳算法；文獻[4]利用退火算法提高種群差異性，通過自整定策略提高算法收斂速度；文獻[5]通過隨機交叉的方式維持種群多樣性，從而防止算法早熟。綜上所述，雖然對傳統遺傳算法加以改進，但是算法仍然存在一些缺點需要優化：首先，還是使用傳統的雙交叉方式；其次對于適應度的改進依舊停留在靜態環境中[6-8]，而不能對每次迭代的解進行動態修正；而且并未考慮多AGV規劃可能會導致擁堵，路徑轉彎數過多導致運行耗時過長，降低工作效率。

本文結合AGV路徑規劃的特點，使用拓撲法建立地圖模型；采用三啟發交叉算子獲得更多父代信息保證個體多樣性，提高算法收斂速度，防止陷入局部最優解；為了提高AGV的運行效率，減少其轉彎次數，對規劃的路徑進行平滑判斷；為了減少AGV間的碰撞和擁堵概率，根據路徑上AGV數量，進行擁堵程度判斷；利用路徑平滑程度描述轉彎次數，擁堵系數表達路徑的擁堵程度。然后將二者作為規劃指標加入到適應度函數中，對每代最優路徑進行獎勵，最差路徑進行懲罰，從而尋找到符合實際的路徑。

1 改進的遺傳算法路徑規劃

1.1 環境建模

本文采用拓撲法建立地圖環境，采用符號編碼方式，將拓撲節點的序號對應染色體的基因值。拓撲地圖如圖1所示[10]

圖1 AGV環境模擬拓撲圖

集合{V|V1，V2，V3，…，V9}為節點，表示現實工廠的工作機臺，M表示為接貨點。節點之間的數據是路徑權重，表示運行路徑上的具體信息。擁堵系數由Dis_Jam(S，P)的形式表達，其中Dis_Jam為兩點之間的距離，S為路徑平滑程度，P為擁堵系數。

1.2 三交換啟發式交叉算子

傳統的雙交叉方式只繼承父代的基本特征，使得子代多樣性較低，無法繼承過多父代的優良基因。導致交叉的概率減小，進化受阻，收斂速度緩慢。而且當子類多樣性偏低時，也會導致變異的概率減少，不易產生新樣本，從而陷入局部最優解。

三交換啟發式交叉算子利用三個父代染色體間產生一個子代。與傳統的雙交叉方式相比，增加了產生子代染色體的信息，提高子代多樣性。

而對于四交叉、五交叉的情況，如圖2所示。在同樣目標下，雖然父代染色體的增多，提高了繼承雙親優良性狀的可能性，但交叉次數過多，會導致收斂速度過慢。

圖2 交叉次數對比圖

1.3 適應度函數

為了使規劃路徑符合實際，充分考慮真實路況和多AGV的影響，引入路徑平滑程度和擁堵系數優化適應度函數。

計算公式如下：

(1)

公式(1)中：f為目標函數；dis(vk，vk+1)表示個體vk和個體vk+1之間的距離；Pk和S分別為的擁堵系數和路徑平滑程度。

其中若目標函數越小，代表所耗路徑越短，規劃的路徑越優秀。反之，目標函數越大，代表所耗路徑越長，規劃的路徑越差。

1.3.1 路徑平滑程度

由于AGV易受到動力學和運動學的約束，拐彎幅度不宜過大，且相對平滑的路徑更適合運行。為保證規劃路徑的合理性，利用路徑平滑程度描述AGV的轉彎次數及轉彎的角度大小。

為方便計算，根據拐角大小對AGV的轉彎情況做4個層次劃分。假設AGV的正常轉彎速度為vr，arc為拐角角度，引入懲罰系數α。α計算公式如下：

路徑平滑程度計算公式如下：

(2)

其中vt為直線速度，vr為轉彎速度，速度勻速不變；R為轉彎半徑；num為整條路徑上拐角的個數。α為懲罰系數；

結合公式(1-2)可看出，若路徑平滑程度越高，表示懲罰越大，使得目標函數f增大。根據遺傳算法輪盤賭機制，易拋棄f值較大路徑，從而防止算法得到轉彎次數過多的路徑。

1.3.2 擁堵系數

由于運行過程中可能發生多AGV擁堵或者碰撞的情況，通過定義擁堵系數，對擁堵程度較高的路徑懲罰，避開較擁堵路段。其中擁堵系數是表達T時段內，該節點經過的次數對于總節點數的比重。擁堵系數計算流程圖如圖3。

圖3 擁堵系數計算流程圖

計算公式如下：

(3)

(4)

n為節點號；k為已使用的節點號；HK表示時間周期T內k節點使用頻率；集合M表示節點k出現的次數；集合A為當前節點AGV出現的次數；MAX為小車總數。Pk表示路段k的擁堵系數。

結合公式(1)、(4)可看出，若擁堵系數越大，表示懲罰程度越大，導致目標函數f增大。

2 實驗與分析

利用軟件VS2015和C#語言對圖1所示的地圖環境進行路徑規劃測試，運行速度：vt=0.5m/s，vr=0.2m/s；小車數量：4輛；為增加合理性對比驗證，分別對傳統遺傳算法、Dijkstra、蟻群算法和本文改進遺傳算法進行多次實驗。

2.1 遺傳算法和改進遺傳算法的對比

基本遺傳算法中，選擇方式為輪盤賭選擇，使用二交換啟發交叉算子，適應度只考慮路徑長度。終止條件為迭代次數500次；耗時：242.5813；路徑長度：147.9752；

利用三交換啟發算子改進的遺傳算法中，選擇方式為輪盤賭選擇，使用三交換啟發交叉算子，適應度考慮路徑長度。終止條件為迭代次數500次；耗時：126.7127；路徑長度：120.9981；

利用三交換啟發算子，并引入路徑平滑程度和動態擁堵系數改進的遺傳算法中，選擇方式為輪盤賭選擇，使用三交換啟發交叉算子，適應度考慮路徑長度，路徑平滑程度，動態擁堵系數。終止條件為迭代次數500次；耗時：116.7127；路徑長度：118.9981；

在不同的初始化種群條件下進行多次仿真，通過分析遺傳算法收斂曲線，最終得到如圖4、5所示的結果。

從圖4可以看出利用三交換啟發算子和適應度優化的遺傳算法和傳統的遺傳算法對比，迭代次數少，且加快了收斂速度；

圖4 對比收斂曲線

原因在于傳統遺傳算法受自身的交叉變異機制，很容易造成種群差異性小，且相對于其他群智能算法收斂速度較慢。再加上使用輪盤賭的方法，有極高的概率破壞優良個體，使算法易陷入局部最優。而改進的遺傳算法采用三交叉方式提高了子代多樣性，降低了輪盤賭的不良影響。從而使算法能較快收斂且不易“早熟”。

在僅改進交叉算子和同時優化適應度和交叉算子的對比中，如圖5可以看出，同時優化適應度和交叉算子的曲線能較快收斂。原因是采用三交叉算法雖然能使種群差異性提高，但同時增加了較差子代的概率。而且傳統算法的適應度設計過于簡單，對于較差子代也能擁有很高的適應度，從而使算法不能較快收斂。通過對適應度的優化可以融入更多的信息，加強適應度函數的判斷能力，加快算法收斂。

圖5 對比收斂曲線

2.2 蟻群算法和改進遺傳算法的對比

將傳統蟻群算法與改進的遺傳算法進行比較，實驗結果如圖6所示。從圖中可以明顯看出，雖然蟻群

圖6 對比收斂曲線

算法能更快地找到最優解，有較好的收斂性。但蟻群算法具有正反饋的特點，初始時刻環境中的信息素完全相同，算法幾乎按隨機方式完成解的構建，這些解必然會存在優劣之分，且容易陷入局部最優。而在迭代數20～60之間，改進遺傳算法曲線發生波動，證明此時種族差異性大，跳出局部最優解的可能性增大。

2.3 多AGV路徑規劃比較

將Dijkstra算法、蟻群算法、傳統的遺傳算法和改進的遺傳算法的搜索結果進行對比，并加入路徑平滑和擁堵系數，測試在多AGV和考慮道路狀況的情況下三種算法的計算效率。

通過表1算法仿真結果對比，改進的遺傳算法所規劃的路徑長度更短，耗時更少。而且對于路徑平滑程度的考慮，改進的遺傳算法選擇到了最優路徑，而Dijkstra和傳統遺傳算法并未選擇到平滑程度最高的路線，即轉彎次數最少。對于蟻群算法，雖然耗時很短，但很容易陷入局部最優解。

表1 算法仿真結果對比

3 結語

針對遺傳算法在規劃AGV路徑時，存在易陷入局部最優，收斂速度慢的問題，將路徑的長度，路徑平滑程度，擁堵系數，作為評價指標對適應度函數進行改進；采用三交叉啟發式算子代替傳統的二交叉模式，使子類個體獲得更多的父類信息。根據仿真結果證明，改進的遺傳算法和傳統遺傳算法相比具有全局搜索能力強、收斂性能好的優點；與其他路徑規劃算法相比，能獲得更優秀的解。