基于改進蟻群算法的路徑規(guī)劃算法研究

韋子文

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

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

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

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

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

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

1 建模

環(huán)境布局復(fù)雜、路徑無碰撞等限制因素，構(gòu)建以智能機器人行進路徑最短、軌跡最平滑為目標的路徑規(guī)劃模型。

首先，建立智能機器人運動的路徑網(wǎng)絡(luò)。電務(wù)檢修基地中智能機器人工作環(huán)境可視為二維靜態(tài)環(huán)境，各檢修臺（障礙物）均靜止，為此采用柵格法確定工作環(huán)境，其中黑色柵格表示由障礙物占據(jù)的禁止行進的位置坐標，白色柵格表示可以通行的位置坐標。為便于計算和蟻群算法尋找、存儲路徑，按照從左到右、從上到下的順序?qū)γ恳粋€柵格進行編號。柵格示例如圖1所示。

圖1 柵格示例圖

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

1.1 模型假設(shè)及約束

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

（1）電務(wù)檢修基地路面平整，因此可忽略其行駛路徑的坡度影響，路徑網(wǎng)絡(luò)可完全由二維柵格圖體現(xiàn)。

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

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

1.2 目標函數(shù)

以智能機器人行進路徑最短、轉(zhuǎn)彎次數(shù)（智能機器人方向每轉(zhuǎn)換一次即視為轉(zhuǎn)彎一次）最少為目標，構(gòu)建的目標函數(shù)為：

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

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

N——路徑上轉(zhuǎn)彎的次數(shù)；

w1、w2——2 個子目標函數(shù)的權(quán)重系數(shù)；

Nmax——最大轉(zhuǎn)彎次數(shù)約束；

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

2 改進蟻群算法

2.1 傳統(tǒng)蟻群算法

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

2.1.1 狀態(tài)轉(zhuǎn)移

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

式中：α——信息素權(quán)重；

β——啟發(fā)式因子權(quán)重；

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

τij（t）——信息素；

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

2.1.2 信息素更新

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

式中：ρ——信息素揮發(fā)系數(shù)；

m——蟻群數(shù)量；

2.2 改進蟻群算法

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

2.2.1 多蟻種

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

2.2.2 改進狀態(tài)轉(zhuǎn)移規(guī)則

本文的算法對狀態(tài)轉(zhuǎn)移規(guī)則進行了優(yōu)化，基于“節(jié)約里程法”這一核心思想在狀態(tài)轉(zhuǎn)移規(guī)則中引入距離節(jié)約因子。基本思想如圖2所示。

圖2 距離節(jié)約因子基本思想示意圖

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

式中：λ——距離節(jié)約值的權(quán)重；

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

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

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

2.2.3 改進信息素更新策略

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

2.2.4 多鄰域搜索

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

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

2.3 改進蟻群算法流程

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

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

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

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

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

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

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

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

算法流程如圖4所示。

圖4 改進蟻群算法流程圖

3 案例仿真實驗

3.1 案例背景

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

圖5 案例柵格環(huán)境圖

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

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

表1 參數(shù)設(shè)置表

3.2 仿真與對比

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

表2 三種算法仿真結(jié)果對照表

圖6 本文算法最優(yōu)路徑圖

圖7 三種算法對比圖

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

4 結(jié)論

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

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

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

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