基于蟻群算法的智能小車路徑規劃

薛 婷，貝紹軼，李 波

(江蘇理工學院機械工程學院，江蘇 常州 213001)

1 引言

近幾年來，國內外針對蟻群算法提出了大量的改進算法，大致可以分為以下兩類：第一種，對算法中的信息素啟發因子、期望啟發式因子、信息素濃度等參數進行改進，在對這些參數進行改進的研究中Dorigo等人改變了信息素的更新方式，提出了Ant-Q System 蟻群算法[1-3]；第二種，將傳統蟻群算法與其它智能算法相結合，黃辰等人明確提出一種基于A*蟻群算法的動態路徑規劃方法[4-6]。目前國內外的研究熱點就是以上兩種方法相結合。

傳統蟻群算法在運算時會出現螞蟻陷入局部最優點、運行時間長、迭代次數多等問題。本文結合了上述兩種改進算法的方式對傳統算法進行了改進。首先，對傳統算法中的參數設置進行了改進：令出發點和目標點之間的信息素略大于其它信息素濃度；全局信息素更新取決于最優螞蟻，并通過自適應來控制信息素揮發因子。其次，在啟發信息中的距離計算中結合勢場法，避免螞蟻陷入局部最優。

2 蟻群算法

2.1 基本原理

螞蟻在一邊尋找食物時一邊釋放一種揮發性分泌物pheromone來吸引其它的螞蟻。然而有些螞蟻可能會另辟蹊徑，如果另開辟的道路較之前螞蟻探索的路徑更短，那么這一條最短的路徑將會被大多數螞蟻重復著[7-9]。

2.2 狀態轉移概率

螞蟻下一步的路徑取決于信息素的濃度，在第t次迭代中，螞蟻k由節點i選擇下一節點j的轉移概率表示為

(1)

(2)

式中：α為信息素啟發因子；β為期望啟發式因子；τij為路徑(i，j)的信息素濃度；allowk表示路徑搜索所有下一可達節點的集合；ηij為啟發信息；dij為當前節點i和待選節點j的歐氏距離。

2.3 信息素揮發與更新

i節點中的信息素會隨著螞蟻從節點i向節點j移動的過程中逐漸揮發，同時j節點的信息素會越來越強烈，則t+1時刻的信息素濃度為

τij(t+1)=(1-ρ)τij(t)+Δτij(t，t+1)

(3)

(4)

式中：ρ為信息素揮發系數，ρ∈(0，1)；Δτij(i，j)表示從節點i向節點j上的信息素增量；Q為信息素強度；Lk表示第k只螞蟻在本次迭代所走路徑的總長度。

3 改進蟻群算法

3.1 初始信息素不均衡分配

傳統蟻群算法中的所有初始信息素都是均勻分布的，因此螞蟻開始搜索路徑時會出現無目的性[10-11]。本文為了解決此問題，提出了令初始信息素不均勻分配的原則，即在有效范圍內增加信息素的初始值，如下所示

(5)

其中：τx為信息素矩陣中的信息素；τ0為未被處理過的初始信息素；C為常數(大于τ0)；x為地圖柵格序號；R為全局路徑規劃的有效范圍。

3.2 啟發信息的改進

在傳統蟻群算法中初始信息素均相同，故路徑的選擇取決于啟發信息，但螞蟻會在選擇第一個節點時選擇偏向終點的方向，但若選擇的第一個節點附近有干擾物時，則說明初始節點選擇不當，那么該路徑也就不是最優路徑[12]。本文通過勢場法算出節點與目標節點之間的距離來調整啟發函數，調整后的啟發函數如下

(6)

其中：dij為節點i到節點j之間的歐氏距離；Ljg為根據勢場算法得出節點j到節點g之間的距離；Ncmax為迭代的最大次數；Nc為當前的迭代次數；ξ為啟發信息遞減函數(ξ>1)。在該式中，啟發函數會隨著迭代次數的增加而減少，改進的啟發信息函數可以有效地避免出現局部最優的問題，提高搜索效率[13-15]。

3.3 信息素更新改進

當螞蟻經過i節點后，i節點處的局部信息素會發生變化，變化規則如下

τij(t)=(1-λ)τij(t)+λτ0

(7)

其中：λ為局部信息素揮發系數(λ∈(0，1))；τ0為一個很小的正常量；當τij(t)超過上限或小于下限值時，就令τij(t)的大小等于上限或下限值，防止算法陷入停滯狀態。

當一次迭代完成之后，會出現有的螞蟻走過的路徑接近于最優路徑，這類螞蟻稱為最優螞蟻；反之，也有螞蟻走過的路徑耗時長、路徑繁瑣，這類螞蟻稱為最差螞蟻[13]。本文根據優質螞蟻規則來更新全局信息素，更新規則如下所示

(8)

其中：ε為該算法引入的一個參數(ε∈(0，1))；Lworst為最差螞蟻走過的路徑長度；Lbest最優螞蟻走過的路徑長度。

信息素揮發因子ρ通過自適應控制來提高全局性，在該算法中，若連續迭代T次，所得的最優結果都一樣，那么該算法便陷入了局部最優解中，此時信息素揮發因子ρ通過下是做自動調整

(9)

其中：ρmin為信息素揮發因子的最小值；γ為全局信息素的遞減因數(γ∈(0，1))。

3.4 二次路徑規劃

螞蟻在第一次路徑規劃中很難規劃出最優路徑，因此本文提出二次路徑規劃，二次路徑規劃是在第一次規劃的路徑基礎上進行改善。

令第一次規劃的路徑上的所有拐彎點為節點，并按順序命名為節點1、節點2、節點3等。依次將節點1與節點3連接起來，若所連路徑安全且無碰撞，則可以省略中間節點2，然后節點1依次與節點4進行比較，直至出現碰撞為止，此時令開始出現碰撞的這個節點為初始點，然后依次與下面的節點進行連接比較，依次反復，直到終點位置，此時所得路徑即為二次規劃所得路徑。二次路徑規劃可以減少轉彎次數，并減少時間，對一次規劃路徑進行了優化。

4 仿真結果與分析

本文為驗證改進后算法的優越性，進行了大量仿真，算法仿真環境為：Windows10 64bit；Matlab R2016b；處理器Intel(R) i5。仿真搭建地圖模型為10*10，20*20和30*30，在該環境下，傳統蟻群算法與改進蟻群算法路徑規劃的參數如表1所示，經仿真的到傳統算法與改進算法路徑規劃圖和收斂圖如圖1所示。

表1 仿真參數設置

1)10*10路徑規劃和收斂對比圖如下圖所示。

圖1 10*10傳統路徑規劃圖

圖2 10*10改進路徑規劃圖

圖3 10*10傳統收斂圖

圖4 10*10改進收斂圖

由傳統算法和改進后算法的對比圖可知，當環境模型較小時，改進后算法有一定優越性，迭代次數從20次減少為8次，迭代次數減少60%，并且路線更加平滑，但最小路徑長度幾乎不變。

2)20*20路徑規劃和收斂對比圖如下圖所示。

圖5 20*20傳統路徑規劃圖

圖6 20*20改進路徑規劃圖

圖7 20*20傳統收斂圖

圖8 20*20改進收斂圖

當環境模型變為20*20時，改進后算法的路徑規劃圖更加平滑，不必要的拐彎點明顯減少，并且迭代次數從50降為15，迭代次數減少70%，規劃的路徑也更為平滑，最小路徑長度也幾乎不變，大大縮短了運行時間，在該環境模型下可以明顯體現出改進后算法的優越性。

3)30*30路徑規劃和收斂對比圖如下圖所示。

圖9 30*30傳統路徑規劃圖

圖10 30*30改進路徑規劃圖

圖11 30*30傳統收斂圖

圖12 30*30改進收斂圖

當環境模型為30*30時，傳統算法路徑圖有很多不合理的拐彎點，并且當迭代次數達到最大值100時，依舊不能達到收斂狀態，而改進后算法只需迭代60次就可以達到最小路徑，迭代次數至少減少50%，并且路線更為平滑。由此可見，環境模型為30*30的狀態下，傳統算法已不能得到最優路徑，反之改進后的算法大大縮短了迭代次數和時間，減少了運行時間。

由3組不同模型的路徑規劃和收斂對比圖可知，改進后的路徑更加平滑趨于直線，減少了拐彎的次數，路線更加合理，故在迭代過程中螞蟻陷入局部最優解的次數大幅度減少；觀察算法收斂圖可得，傳統算法與改進算法最后得到的最優路徑長度都是差不多的，但是改進后算法的迭代次數明顯小于傳統算法的迭代次數，體現了改進后算法的優越性，有效地提高了智能小車的效率。由模型的復雜程度的遞進關系可知，當模型越復雜，改進后算法的優越性就越明顯。

5 結論

本文針對傳統蟻群算法的不足，提出了一種改進蟻群算法。

1)初始信息不均勻分配使螞蟻在初期探索路徑時目的更明確，使產生的優質螞蟻更多，而劣質螞蟻更少，可以有效防止螞蟻陷入局部最優點，提高了螞蟻搜索路徑的效率。

2)結合勢場法調節啟發信息，通過勢場法計算當前節點與目標節點之間的距離可減少算法迭代次數，在不同的環境模型下迭代次數都可以減少60%-70%，減少了運行時間。

3)根據最優螞蟻原則調節全局信息素更新，使得環境模型中的信息素更優質的更新，信息素的有效性提高；通過自適應控制信息素揮發因子，及時調整揮發參數，提高了信息素的時效性，提高了算法的全局搜索能力。

通過結合不同仿真環境模型對改進后算法的實用性和有效性分析表明，改進后規劃的路線更加平滑，無效拐彎點次數減少，迭代次數也明顯減少。本文的環境模量全是已知的，并且障礙物都是靜態的，后續將結合未知環境中的動態障礙物來深入研究，進一步提高該算法的有效性和實用性。