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

韋子文

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

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

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

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

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

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

1 建模

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

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

圖1 柵格示例圖

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

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

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

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

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

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

1.2 目標(biāo)函數(shù)

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

綜合考慮智能機(jī)器人在實(shí)際運(yùn)行過(guò)程中受到的

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

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

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

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

Lgrid——智能機(jī)器人行進(jìn)步長(zhǎng)約束。

2 改進(jìn)蟻群算法

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

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

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

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

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

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

Jk（i）——第k 只螞蟻下一步可被允許訪問(wèn)的點(diǎn)的集合；

τij（t）——信息素；

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

2.1.2 信息素更新

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

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

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

2.2 改進(jìn)蟻群算法

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

2.2.1 多蟻種

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

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

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

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

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

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

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

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

dij——當(dāng)前位置距終點(diǎn)的距離。

2.2.3 改進(jìn)信息素更新策略

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

2.2.4 多鄰域搜索

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

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

2.3 改進(jìn)蟻群算法流程

本文改進(jìn)蟻群算法具體流程如下：

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

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

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

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

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

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

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

算法流程如圖4所示。

圖4 改進(jìn)蟻群算法流程圖

3 案例仿真實(shí)驗(yàn)

3.1 案例背景

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

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

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

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

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

3.2 仿真與對(duì)比

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

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

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

圖7 三種算法對(duì)比圖

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

4 結(jié)論

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

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

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

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