基于改進蟻群算法的路徑規劃算法研究

韋子文

（中鐵第一勘察設計院集團有限公司，西安 710043）

鐵路信號設備的檢修場所主要包括繼電器檢修基地、轉轍機修配基地和駝峰修配基地等，各檢修基地分散配置于不同站段。信號設備的檢修存在資源配置不均、耗費嚴重等問題。隨著鐵路現代化的發展，電務檢修基地按照資源整合、集約化的管理思想將各檢修基地進行整合，以實現生產集約化、規模化，管理智能化、規范化，作業專業化、現代化的目標，可較大幅度地提升勞效和產能［1］。

智能機器人能解決任務繁重、效率低下、資源耗費過大等諸多問題，可發揮舉足輕重的作用。目前智能機器人在鐵路電務檢修基地應用較少，隨著鐵路現代化的不斷發展，它的應用將越來越廣泛。因此，對智能機器人移動路徑規劃的研究在車間調度、智能搬運等領域有著極大應用價值。

為進一步提升智能機器人的智能程度及利用率，國內、外學者從不同角度（包括傳統算法和智能算法）對機器人路徑規劃進行了廣泛研究。Fernandez J A 和Gonzalez J［2］采用圖搜索法確定了移動機器人從起始點到目標點的最短路徑；Qi N，Ma B 和Liu X［3］提出人工勢場法搜索機器人最短行駛路徑；Gu J 和Cao Q［4］采用柵格法規劃路徑。然而，上述傳統算法得到的路徑并不理想且搜索效率較低。智能算法如蟻群算法［5］、免疫算法［6］、神經網絡［7］在移動機器人路徑規劃研究中的應用，雖然性能提升較明顯，但是存在搜索空間大、搜索時間長等問題。

眾多學者又對上述傳統算法進行改進優化，路徑尋優效果得到了提升。徐菱［8］等提出采用16 方向24 鄰域的搜索方式，通過引入轉移概率控制參數調節搜索范圍，以提高蟻群算法在路徑尋優過程中的搜索效率和效果；蔣強［9］等提出一種結合蟻群算法和Dijkstra 算法的多目標路徑規劃方法，同時對尋優路徑進行了平滑處理；M Nazarahari［10］采用改進的遺傳算法按照一定的指標遍歷所有目標點，以尋找一條無碰撞路徑；胡章芳［11］等綜合考慮路徑平滑度和困難度等因素，提出采用Surrounding Point Set 算法改進遺傳算法初始化種群的能力，仿真結果表明該算法在路徑規劃研究中的收斂速度略有提高。

本文針對傳統算法存在收斂速度慢、路徑搜索效率低等問題，綜合考慮智能機器人實際運行過程中多種限制條件，在傳統蟻群算法中引入“分類學習”的思想（各蟻種分別更新其信息素），同時增加搜索范圍。基于此，提出一種多蟻種多鄰域搜索的蟻群算法，以用于各種復雜環境和未知環境下的路徑規劃。

1 建模

環境布局復雜、路徑無碰撞等限制因素，構建以智能機器人行進路徑最短、軌跡最平滑為目標的路徑規劃模型。

首先，建立智能機器人運動的路徑網絡。電務檢修基地中智能機器人工作環境可視為二維靜態環境，各檢修臺（障礙物）均靜止，為此采用柵格法確定工作環境，其中黑色柵格表示由障礙物占據的禁止行進的位置坐標，白色柵格表示可以通行的位置坐標。為便于計算和蟻群算法尋找、存儲路徑，按照從左到右、從上到下的順序對每一個柵格進行編號。柵格示例如圖1所示。

圖1 柵格示例圖

其次，設定好路徑的起點和終點。機器人行進時，每一步都會沿著搜索方向移動一步，并期望機器人能夠以最短的距離從起點移動到終點。

1.1 模型假設及約束

為清晰地表達路徑規劃問題，根據電務檢修基地智能機器人工作狀況的特點做出如下假設和約束：

（1）電務檢修基地路面平整，因此可忽略其行駛路徑的坡度影響，路徑網絡可完全由二維柵格圖體現。

（2）針對不同的工作計劃，智能機器人可避免重復路徑，即不會經過同一坐標點兩次及以上。

（3）機器人運行過程中受運動位姿及路徑限界等因素的影響，目前蟻群算法在求解智能機器人路徑規劃問題時，求解得到的最優路徑可能不符合實際運行路徑。為此，本文對其工作環境中的各障礙物做了膨化處理，即：智能機器人在運行過程中將檢測到障礙物的1.25 倍體積尺寸均視為障礙物進行避讓。

1.2 目標函數

以智能機器人行進路徑最短、轉彎次數（智能機器人方向每轉換一次即視為轉彎一次）最少為目標，構建的目標函數為：

綜合考慮智能機器人在實際運行過程中受到的

式中：dij——螞蟻從i 移動到j 的距離；

N——路徑上轉彎的次數；

w1、w2——2 個子目標函數的權重系數；

Nmax——最大轉彎次數約束；

Lgrid——智能機器人行進步長約束。

2 改進蟻群算法

2.1 傳統蟻群算法

傳統蟻群算法是在1991年由意大利學者Dorigo M等提出的模仿蟻群覓食行為的分布式計算優化算法。其基本原理是每只螞蟻覓食過程中在經過的路徑上釋放“信息素”，并以“信息素”的濃度為指導選擇運動方向，從而搜索最短的覓食路徑。隨著時間的推移，各路徑上的“信息素”會揮發，但其中若干條較短路徑上的“信息素”會逐漸增多，蟻群在此正反饋機制下最終尋找到一條最優路徑。蟻群算法的核心思想包括狀態轉移［12］和信息素［13］更新。

2.1.1 狀態轉移

每只螞蟻根據路徑上的“信息素”濃度計算路徑的選擇概率，并基于這個概率選擇運動方向。狀態轉移概率為：

式中：α——信息素權重；

β——啟發式因子權重；

Jk（i）——第k 只螞蟻下一步可被允許訪問的點的集合；

τij（t）——信息素；

ηij（t）——表示期望程度的啟發因子，表達為：

2.1.2 信息素更新

隨著迭代次數的增加，螞蟻行進的各路徑上的“信息素”以式（7）、式（8）的規律進行更新。

式中：ρ——信息素揮發系數；

m——蟻群數量；

2.2 改進蟻群算法

針對傳統蟻群算法存在收斂速度緩慢、前期信息素匱乏、易陷入早熟等問題，本文在此基礎上對蟻群進行多分類，增加種群多樣性，改進螞蟻的狀態轉移概率公式，通過自適應調整信息素的揮發系數，并插入局部變鄰域搜索操作，以解決其過早陷入局部最優的問題。

2.2.1 多蟻種

為了增加蟻群種群的多樣性，本文引入“分類學習［14］”思想，將蟻群種群按照1：2 的比例分為精英蟻群和普通蟻群兩類。精英蟻群的適應值較好，給予其較低的信息素揮發系數來增強其引導力；而普通蟻群的適應值相對較低，本文算法將普通蟻群平均分配給各精英螞蟻，以擴大精英蟻群的搜索范圍，避免其過早陷入局部最優。

2.2.2 改進狀態轉移規則

本文的算法對狀態轉移規則進行了優化，基于“節約里程法”這一核心思想在狀態轉移規則中引入距離節約因子。基本思想如圖2所示。

圖2 距離節約因子基本思想示意圖

其主要出發點是，根據各螞蟻起點到目標點之間的距離來尋找路徑長度最短的行進方案。由圖2可知，當前所在位置距下一步落腳點橫向、縱向距離分別為doi和doj，至下一步落腳點的直線距離為dij。改進后的狀態轉移概率為：

式中：λ——距離節約值的權重；

μij（t）——距離節約值，表達為式（10）；ηij（t）表達為式（11）。

式中：dmax、dmin——所有下一步待選節點距終點的距離最大值和最小值；

dij——當前位置距終點的距離。

2.2.3 改進信息素更新策略

精英蟻群和普通蟻群的信息素更新方式也不同。若精英蟻群行進路徑上信息素濃度過高，大于一定閾值Mmax，極易陷入局部最優，因此對其信息素更新策略進行改進，表達為式（12）；若普通蟻群行進路徑上信息素濃度過低且低于Mmin，則對其信息素進行補償，補償數量為M2，具體更新策略表達為式（13）。

2.2.4 多鄰域搜索

傳統蟻群算法中，螞蟻搜索方向僅為“前、后、左、右”4 個方向，其有效搜索方向有限。為了提高螞蟻的搜索精度，同時考慮路徑曲線的平滑性，本文算法將其搜索方向擴展到8 個方向，螞蟻視野得到擴展，從而擴大了其搜索范圍，搜索方向如圖3所示。

圖3 蟻群八方向搜索示意圖

2.3 改進蟻群算法流程

本文改進蟻群算法具體流程如下：

步驟1：初始化多蟻種多鄰域搜索蟻群算法的參數。

步驟2：初始化智能機器人所處的柵格環境和行進路徑禁忌表，并確定其行進路徑的起始點和終點。

步驟3：精英蟻群和普通蟻群按式（9）～式（11）計算其狀態轉移概率，以在多個搜索方向中選擇智能機器人下一步行進的點。

步驟4：當智能機器人到達下一行進點時，同步更新禁忌表；檢查是否到達終點，若是則跳轉到步驟5，若不是則跳轉至步驟3。

步驟5：螞蟻個數i=i+1，檢查整個蟻群是否完成路徑搜索任務，若是則跳轉到步驟6，若不是則跳轉至步驟3。

步驟6：記錄當前迭代次數的最佳路徑，并讓精英蟻群和普通蟻群按式（12）、式（13）更新信息素。

步驟7：迭代次數iter=iter+1，檢查迭代次數是否達到最大值N，若是則輸出最佳路徑，若不是則返回步驟3。

算法流程如圖4所示。

圖4 改進蟻群算法流程圖

3 案例仿真實驗

3.1 案例背景

選取某電務檢修基地室內布置搭建環境柵格模型，膨脹化后的障礙物位置如圖5所示。綜合考慮轉彎次數、路徑可行性、路徑少重復性等多種因素，以式（1）為目標函數進行案例仿真分析。

圖5 案例柵格環境圖

算法初、中期主要考慮路徑最短這一目標，算法后期主要考慮路徑的平滑性。因此，隨著迭代次數的增加，w1由大至小自適應遞減，w2由小至大自適應遞增。

本文采用的改進蟻群算法的具體參數設置如表1所示。

表1 參數設置表

3.2 仿真與對比

本文分別采用多蟻種多鄰域搜索的改進蟻群算法（ACO）和排序蟻群算法（RAS）、精英蟻群算法（EAS）仿真10 次，取尋優路徑和仿真結果進行對比，尋優路徑分別如圖6、圖7所示，仿真結果如表2所示。

表2 三種算法仿真結果對照表

圖6 本文算法最優路徑圖

圖7 三種算法對比圖

由圖6、圖7 可知，本文算法（ACO）的路徑尋優效果更理想。雖然本文算法收斂代數略遲于其他兩種算法，但其搜索路徑更平滑（轉彎次數更少）、距離更短。

4 結論

本文以電務檢修基地中智能機器人的工作場景為背景，綜合考慮其實際運行中的各種限制因素，構建路徑最短、最平滑的函數模型。得出主要結論如下：

（1）針對多約束條件下傳統算法在智能機器人路徑尋優過程中存在的“早熟”現象、尋優效果不理想等不足，本文提出了一種基于蟻群算法的多約束條件下多蟻種多鄰域搜索的改進蟻群算法，增加螞蟻種群的種類，并在此基礎上在狀態轉移概率中引入距離節約值、分不同種群改進了信息素更新策略。

（2）在相同環境下，與排序蟻群算法和精英蟻群算法相比較，本文提出的算法有效克服了“早熟”問題，得到的優化路徑更平滑且距離更短，表明了本文提出的算法具有一定的優越性和實用性。

（3）本文未考慮動態障礙物和多智能機器人協同路徑尋優的情況，這是本文的不足，也是未來研究的重點方向。