一種改進的蟻群路徑規劃算法

王天生，張 峰

（1.上汽通用五菱汽車股份有限公司，廣西 柳州 545000；2.武漢理工大學機電工程學院，湖北 武漢 430070）

0 引言

近年來隨著移動機器人技術的大量應用，作為其重要分支的路徑規劃技術也受到了學者的廣泛關注。所謂路徑規劃即是在充滿障礙物的規劃空間中找到一條從起點到終點的最優、最短路徑，并且能夠無碰撞地成功地繞開環境中所有的障礙物。目前，在路徑規劃領域中應用的比較多的算法主要分為兩類，一類是可視圖法[1]、自由空間法[2]、拓撲圖法等傳統的求解方法；另一類則是采用遺傳算法、蟻群算法、神經網絡法等智能算法。雖然上述的各種方法為路徑規劃問題提供了不同的解決方案，但是各種方法在執行上總是存在著不同的缺點與優點，并沒有一種方法能夠完全適應各種環境條件下的任何系統。

蟻群算法是一種模擬螞蟻群體覓食行為的仿生優化算法，該算法具有較強的魯棒性、優良的分布式計算機制、易于與其他算法相結合等優點[3]。因此，自意大利的Dorigo[4]學者提出蟻群算法以來，如今已經在各行各業得到了廣泛的應用。但傳統的蟻群算法由于其復雜性往往需要很長的搜索時間，而算法搜索初期的盲目性也容易造成算法收斂速度慢等缺點[5]。針對上述缺點，許多學者也提出了相應的改進方法，如Stutzle[6]為了避免蟻群算法趨于停滯、陷于局部最優，對信息素的更新范圍進行了限定，從而提出了搜索效果更好的最大最小螞蟻系統（MMAS）。黃震等[7-9]學者則是將蟻群算法與其他表現較好優化算法如遺傳算法、A*算法等相結合，從而提出了收斂性較好的混合蟻群算法。大量的文獻[10]也表明，多數學者對蟻群算法的改進主要聚焦于信息素的更新方式以及怎樣提高種群的多樣性，很少有學者關注螞蟻的搜索方向以及啟發函數信息的更新。因此，本文基于傳統的蟻群算法加入了自適應調整啟發函數，局部最優方向引導機制，并在此基礎上提出了一種改進的蟻群路徑規劃算法，該算法具有較高的收斂速度。

1 傳統的蟻群路徑規劃算法

雖然蟻群算法的提出是著眼于解決旅行商問題（TSP），但其基本思想卻可以應用于許多其他問題的求解，路徑規劃問題便是其中之一。因此，基于蟻群算法的路徑規劃也得到了大量的發展，蟻群算法中最重要的是螞蟻對下一步節點的概率的選擇以及各節點之間的信息素的更新。

1.1路徑選擇概率

螞蟻 k（k=1，2，…，m）在運動過程中，根據各路徑上的信息素量來決定下一步的轉移節點，其中用禁忌表tabuk表示螞蟻k所走過的節點集合，禁忌表會在螞蟻移動過程中做動態調整，在路徑搜索過程中，螞蟻根據各路徑上的信息量以及路徑的啟發信息來計算狀態轉移概率。表示t時刻螞蟻k由節點i轉移到節點j的狀態轉移概率，其公式如式（1）所示。

否則式中，allowedk＝{C-tabuk}表示螞蟻k下一步允許選擇的節點，α為信息啟發式因子，表示各節點間信息的相對重要性，反映了螞蟻在運動過程中所累積的信息在螞蟻運動時所起到的作用，其值越大，則螞蟻越傾向于其他螞蟻所走過的路徑，螞蟻之間的協作性也就越強，但過大的信息啟發因子也會限制蟻群算法的全局搜索能力。β為期望式啟發因子，反映了啟發信息在螞蟻選擇路徑中受重視的程度，其值越大，則蟻群算法越接近于貪心算法。ηij（t）為啟發函數，在路徑規劃中，一般其表達式如式（2）：

式中，dij表示兩節點之間的歐式距離。

1.2信息素的更新

蟻群算法中螞蟻群體的協作離不開信息素，但無限量的累加各節點上的信息素量不僅不符合螞蟻群體的自然規律，也會造成信息素過多而淹沒啟發信息，因此，當所有螞蟻到達終點后就要對全局信息素進行更新。其更新不僅包含信息素的累加，也包含信息素的揮發。各節點之間的信息素可按如公式（4）（5）執行：

式中，ρ表示信息素揮發系數，用于衡量信息素的衰減程度，其取值范圍一般為ρ∩（0，1）表示本次循環中路徑（i，j）上的信息素增量表示螞蟻群體中第k只螞蟻在本次循環中留在路徑（i，j）上的信息量，如式（6）所示：

否則式中，Q表示信息素強度，其值大于0，Lk表示第k只螞蟻在本次循環中所走路徑的總長度。

2 改進的蟻群路徑規劃算法

2.1自適應調整啟發函數

在傳統的蟻群算法中，由于啟發函數ηis（t）對終點的指向性較差，從而導致算法搜索時間長，收斂速度慢，因此，考慮在算法搜索初期以待選節點與終點之間歐式距離的倒數作為新的啟發函數，如式（7）所示。

式中，djd表示節點j與終點d的歐式距離。

在實際的路徑規劃中，由于搜索空間中各種障礙物的影響，以歐式距離作為待選節點與終點之間的最短可行路徑并不利于散發后期的快速收斂，故將式（7）中的啟發函數應用于算法搜索于初期階段，隨著算法迭代次數的增加，各代中的最優路徑也就更加接近實際的最短路徑，此時，啟動啟發函數更新機制，以算法每代的最優線路為基礎對啟發函數進行更新。啟發函數的更新公式如（8）（9）（10）所示。

當 i=start時，則公式（9）變為如下公式（10）所示。

式中，NC表示算法迭代次數；djd（t，NC）表示在算法迭代NC次時，節點j與終點d之間的最短可行路徑；η″ij（t，NC）表示更新后的啟發函數，R_best（NC）表示在NC中的最優線路；i，j分別表示R_best（NC）中相鄰的兩節點，其中i節點在前，j節點在后；start表示起始點；dsj表示起始點與節點j之間的歐式距離；dij表示相鄰節點i，j之間的歐式距離。在動態調整啟發函數后，螞蟻搜索過程中的狀態轉移概率如公式（11）所示。

否則式中，const為一常數，其值大于0；NC為算法迭代次數。

2.2局部方向引導機制

在傳統的蟻群算法中，螞蟻的狀態轉移概率的主要影響因素是信息素與啟發函數，但路徑規劃問題最大的不同是在路徑規劃前有事先可知的起始點與終點。因此，處在當前節點i的螞蟻在搜索轉移節點時，則可認為當前節點i與目標點d的連線方向為最優的搜索方向。轉移節點j的優劣以當前節點i分別與轉移節點j和目標點d連線向量的夾角θijd來衡量。θijd越小，則轉移節點越靠近最優的搜索方向。在綜合考慮信息素，自適應的啟發函數以及局部最優的搜索方向后，改進的路徑選擇概率如公式（12）所示。

否則式中，λ表示局部方向因素強度系數，其值大于0.γ表示局部方向因素衰減系數，其值大于1.θijd表示i與終點d的連線向量與i到j連線向量的夾角。從公式（12）可知，γ值的大小影響著局部方向因素的衰減程度。由于在蟻群算法的初級階段，各節點之間信息素差異較小，轉移概率隨機性較大，算法收斂速度較低，這時可通過加大局部方向因素的影響，使螞蟻更多的向最優路線聚集，算法的后期，則應逐漸降低局部方向因素的影響，從而讓信息素和啟發函數成為轉移概率選擇的主導因素，因此，合理的選擇參數λ，γ的值非常的重要。

3 仿真測試

為了驗證改進的蟻群算法在機器人路徑規劃中的有效性，本文利用Matlab2010仿真軟件在如圖1所示的兩種復雜度不同的柵格環境下進行了路徑規劃的仿真（柵格中黑色代表障礙物），并記錄了對應的最優路徑迭代收斂曲線。從圖中可以看出，環境1為的柵格環境，環境中的障礙物也較少，環境2則為的柵格環境，規劃空間也更為復雜。在記錄各算法在各環境下的最優路徑迭代曲線時，考慮到蟻群算法的隨機性，選取了各算法的20次試驗的平均值作為參考數據。算法中各參數的取值分別為螞蟻數m=30，α ＝ 1，β ＝ 6，ρ＝ 0.1，Q ＝ 14，λ ＝ 3，γ ＝ 4，const=10，柵格環境1中算法的最大循環次數NCmax1=50，柵格環境2中算法的最大循環次數NCmax1=100.

圖1 不同的仿真測試柵格環境

圖2為兩種算法在環境1下的最優規劃路徑，圖3分別為傳統算法與改進算法在環境1下的最優路徑迭代收斂曲線。從圖中可以看出，兩種算法雖然都環境1下找到了最優的規劃路徑，但改進算法在迭代9次時收斂，而傳統算法則是23次。因此改進的蟻群算法較傳統的算法在收斂速度上具有不小的優勢，收斂速度更快。

圖2 環境1下的最優規劃路徑

圖3 環境1下兩算法的最優路徑迭代收斂曲線

圖4為兩種算法在環境2下的最優規劃路徑，圖5則分別為傳統算法與改進算法在環境2下的最優路徑迭代收斂曲線。從圖中可以看出改進的算法在迭代38次時收斂，傳統算法則要迭代75次才收斂。因此，改進算法較傳統算法收斂更快。從上述的仿真測試可以看出，改進的蟻群路徑規劃算法不僅適應簡單的規劃環境，在復雜的環境中較傳統算法也有較快的收斂速度。

圖4 環境2下的最優規劃路徑

（續下圖）

（接上圖）

圖5 環境2下兩算法的最優路徑迭代收斂曲線

4 結束語

針對將傳統的蟻群算法應用到機器人路徑規劃中易出現搜索時間長，收斂速度慢等問題，本文提出了一種改進的蟻群路徑規劃算法。改進的蟻群算法能自適應的調整啟發函數，并加入了動態衰減的局部方向引導機制。在算法搜索初期，以搜索節點與終點的歐式距離的倒數表示取法函數，在算法迭代到一定階段后，以各代的最優路徑信息動態地更新啟發函數信息。以搜索節點與終點連線的方向為最優的搜索方向，并引入了局部方向因素強度系數、局部方向因素衰減系數，并借此構建了新的路徑選擇概率表達式。仿真測試表明，改進的蟻群路徑規劃算法在各種不同的規劃環境中都有較快的收斂速度。

參考文獻：

[1]李善壽，方潛生，肖本賢，等.全局路徑規劃中基于改進可視圖法的環境建模[J].華東交通大學學報，2008，25（06）：73-77.

[2]熊 菡.移動機器人全局路徑規劃及軌跡跟蹤研究[D].武漢：武漢科技大學，2014.

[3]金 弟，楊 博，劉 杰，等.復雜網絡簇結構探測——基于隨機游走的蟻群算法[J].軟件學報，2012（03）：451-464.

[4]Dorigo M，Gambardella L M.Ant colony system：A coopera tive learning approach to the traveling salesman problem[J].IEEE Trans on Evolutionary Computation，1997，1（1）：53-66.

[5]馬金財.基于蟻群算法的機器人路徑規劃問題研究[D].昆明：昆明理工大學，2014.

[6]Thomas Stutzle T，Holger H Hoos.Max-min ant system[J].Future Generation Computer Systems， 2000，16（8）：889-914.

[7]蘇海鋒，許道林，李汶江，等.基于改進蟻群A～*算法的輸電線路路徑搜索[J].河北大學學報（自然科學版），2017，37（01）：92-100.

[8]黃 震，羅中良，黃時慰.一種帶時間窗車輛路徑問題的混合蟻群算法[J].中山大學學報（自然科學版），2015，54（01）：41-46.

[9]薛冰冰.基于改進型遺傳算法的足球機器人路徑規劃研究[D].長春：長春工業大學，2012.

[10]朱顥東，孫 振，吳 迪.基于改進蟻群算法的移動機器人三維路徑規劃[J].華中師范大學學報（自然科學版），2016，50（06）：812-817.