一種基于改進的蟻群優化算法的三維空間路徑搜索算法

李浩宇, 呂梅柏

(西北工業大學 航天學院, 陜西 西安 710072)

蟻群優化算法 (ant colony optimization，簡稱ACO)是由意大利學者Dorigo等人于1991年創立，是一種啟發式搜索算法。螞蟻能在其經過的路徑上釋放一種特有的分泌物外激素(pheromone)，使得一定范圍內的其他螞蟻能夠感覺到且傾向于朝著外激素濃度高的方向移動。因此，蟻群的集體行為表現為一種信息正反饋現象，蟻群這種選擇路徑的過程被稱之為自催化行為(autocatalytic behavior)。初步研究結果己顯示出該方法在求解復雜優化問題(特別是離散優化問題)方面具有優勢。

近年來隨著啟發式智能算法得到廣泛的關注，尤其是隨機搜索算法，蟻群優化算法也得到了深入發展。文獻[1-2]對蟻群優化算法原理進行了詳細闡述，并介紹了蟻群優化算法的各種改進方式。文獻[3]將蟻群算法應用于水下自主機器人的路徑規劃問題，取得了很好的仿真結果。文獻[4]中用MATLAB語言實現了基本的蟻群優化算法。文獻[5-6]提出了一種基于梯度計算的方法將算法推廣至三維或更高維數，本文在此基礎上對該方法進行了改進，使得算法可以在三維空間的任意點向任意方向搜索路徑，并提高了計算效率和收斂速度，并通過引入定向搜索方法解決了收斂速度慢且搜索結果不平滑的問題。

1 改進的蟻群優化算法模型

1.1 環境模型建立

本文使用柵格法[7](grid representation methods)建立環境空間模型，柵格法用大小相同的柵格劃分搜索空間，并用柵格數組來表示環境，每個柵格點標以2種狀態之一，在自由空間中的節點值為0，在障礙空間中節點值為1，最短路徑通過搜索這張柵格地圖得到。這種方法的表示效率雖然不高，但其簡單性為路徑規劃器的實現帶來了諸多方便，如表示不規則障礙物的能力，適用于大規模并行處理機實現的特點等。

1.2 符號描述與定義

由于傳統的蟻群優化算法在每只螞蟻搜索路徑時對其所有的鄰近點進行搜索，直至搜索到目標點，這種方法雖然可以在全域內搜索可行的路徑，但是會造成收斂速度慢，路徑不平滑等問題，在三維空間情況下更為嚴重。本文引入搜索主方向，可視域以及可行域等定義將上述問題得到了有效抑制，并應用于三維空間的搜索問題，其定義如下：

定義1 為了保證螞蟻在搜索路徑時盡量減少橫向的跨越，以起始點與終點差距大的坐標軸方向為三維路徑規劃的主方向，其可以是橫向、縱向、高度之一，記為MD。若MD為縱軸(x軸)的正方向(序號增加)，則值為1，負方向值為-1；橫軸(y軸)正方向值為2，負方向值為-2；豎軸(z軸)正方向值為3，負方向值為-3。若主方向上終點的坐標值大于起點的坐標值，即終點的序號大于起點的，則螞蟻每次在主方向上前進一格(序號加1)；若主方向的坐標值小于起點的，則相反。

定義2 假設MD為x軸正方向(MD=1)，則對于任意一個柵格空間R中的點gi,j,k，有V(gi,j,k)∈R。可定義可視域V(gi,j,k)，滿足

(1)

式中：i、j、k為三維坐標軸方向上的節點序號值,r為一正整數，則稱V(gi,j,k)為gi,j,k的可視域或是螞蟻在gi,j,k處的可視域。如圖1所示：

圖1 可視域示意圖

當可視域范圍過小，螞蟻在主方向上達到終點時，有可能由于橫向移動范圍不足使得螞蟻無法到達搜索終點，所以可視域須大于某一范圍，同時需保證搜索空間的連通性，這里取：

(2)

式中:Nx、Ny、Nz分別為起始點和終點之間在3個軸方向的節點個數,NM為主方向上的節點個數,ceil為向上取整函數。

定義3 設tn時刻,螞蟻k處于g(tn),簡記為gn,設此處的可視域為V(gn),則設螞蟻k的可行后續節點集Ak(tn)={g|g∈V(gn),且g≠“1”}。

2.3 狀態轉移規則

設在時刻tn,螞蟻s處在gi,j,k∈R,則對當前點的可行后續點集As(tn)中節點的選擇概率計算如下:

(3)

ηi,j,k=λexp(ln,e-ln+1,e)

(4)

式中：τi,j,k為信息素值;ηi,j,k為啟發函數值;α為信息素的重要程度;β為啟發函數的重要程度;ln,e和ln+1,e分別為當前點和下一點距離終點的直線距離;λ為比例系數。

1.4 蟻群信息素更新規則

信息素矩陣τ與環境建模得到的地圖矩陣相對應,每一個點的值代表相應地圖上節點gi,j,k的信息素,信息素數值大表示螞蟻經過此點的次數多。在初始化時,每一個點上的信息素值相同,均令其為1,表示信息素對選擇路徑點的影響都一樣。

在每次迭代過程蟻群中各螞蟻經過的點進行局部更新,目的是為了增加搜索未經過點的概率,達到全局搜索的目的,局部更新規則如下

τi,j,k=(1-ζ)τi,j,k

(5)

式中:ζ為衰減系數;τi,j,k為螞蟻選擇的后續節點。

全局信息素更新是對每次迭代中的最優路徑進行更新。更新信息素矩陣中相對應最優路徑節點的值,是為了將每次迭代過程中按照指標函數得到的最優路徑p0,p1,…pn的節點上的值增加,從而在下次迭代中以更大的概率選擇此條路徑上的節點。在多次迭代之后,路徑就會逐漸收斂到全局最優路徑。

全局信息素更新規則如下式計算:

(6)

(7)

式中:ρ為揮發系數;Q為常數;τi,j,k為每次迭代中最優路徑上的信息素值;fk為最優路徑適應度值,一般取為路徑的長度。

1.5 基于柵格法的三維空間蟻群優化算法步驟

根據定義的符號描述,基于柵格法的蟻群優化算法在三維空間的路徑搜索流程如圖2所示,其步驟可以總結如下:

1) 根據輸入的柵格離散化地圖及起始點(gsi,sj,sk)終點(gei,ej,ek)位置初始化信息素矩陣τ,給它賦一個較小正數(可取為1),計算得到MD,進化代數計數器count=0,最大進化代數為max,它標志算法的結束,每代螞蟻總數為m;

2) k=1;

3) 如果k>m,轉第7)步;否則轉下一步;

4) 螞蟻k放置在起始位置gsi,sj,sk上;

5) 計算出此時螞蟻的Ak,若Ak為空,則宣告這只螞蟻死亡,k=k+1,轉第3)步;否則,按狀態轉移規則計算螞蟻選擇任意gn+1∈Ak的概率,按輪盤賭的方式選擇某一gn+1,并設置此柵格點為螞蟻k的當前位置,轉第6)步;

6) 若主方向MD所表示的軸方向上,當前位置gn的下標序號與終點gei,ej,ek的下標一樣(若MD等于1或-1,即x軸方向上的節點序號相同,其余主方向上以此類推),則將gei,ej,ek設為當前位置,k=k+1,轉第3)步,否則轉第5)步;

7) 進化代數計數器count遞增1;

8) 若count>max,則算法停止,否則按信息素更新規則對蟻群信息素進行更新處理,轉第2)步。

圖2 改進的蟻群搜索算法流程

2 仿真結果及分析

表1規定了仿真時需要用到的一些基本搜索參數,本文后面的仿真結果均以此參數設置得出,并且均為仿真計算90次的統計值。其中信息素揮發系數ρ表示每次迭代信息素在最優路徑上的揮發速度;局部信息素衰減系數ζ表示每次迭代中每只螞蟻所選路徑上的信息素衰減速度;信息素和啟發函數的重要程度α和β均為1,表明兩者的重要程度一樣。

表1 仿真基本參數

算法模擬仿真時使用52×60×50的柵格地圖模擬地形,起點坐標為(50,4,1.925),終點坐標為(3,57,2.353),由改進的蟻群優化搜索算法搜索的三維路徑表示如圖3所示:

圖3 路徑規劃結果

當選擇信息素揮發系數ρ=0.2,局部衰減系數ζ=0.2而蟻群種群數量不同時,規劃的路徑長度隨迭代次數的變化趨勢如圖4所示。從圖中可以看出隨著迭代次數的增加路徑的長度趨于最優,且隨著種群數量的增加改進方法的優勢更加明顯。圖5所示為不同種群數量規劃的每次迭代結果的平均方差變化趨勢,從對比可以看出改進方法的平均方差遠小于傳統方法,且波動幅度比傳統方法小,說明改進方法的穩定性明顯優于傳統方法。

圖4 改進方法與傳統方法的規劃結果隨迭代次數變化規律

圖5 改進方法與傳統方法的規劃結果方差的變化規律

表2為種群數量為5、ζ=0.2的情況下改進算法與傳統算法時間消耗隨揮發系數的變化對比關系。表3為種群數量為5、ρ=0.2的情況下改進算法與傳統算法時間消耗隨信息素衰減系數的變化對比關系。從表2中可以看到,由于揮發系數的引入,收斂速度變慢,使得傳統方法規劃時間相對變長;而改進方法的規劃時間只取決于搜索起始點與終點之間的節點數,所以其規劃時間基本保持不變。從表3中可以看到衰減系數的引入使得兩種方法規劃的路徑長度都有相應的減小,平均方差增大,說明衰減系數的引入提高了算法在極值點附近的搜索能力,但降低了算法的穩定性;同時傳統方法的計算時間有一定的減少。表2和表3都顯示出改進的蟻群算法明顯比傳統算法節省計算時間,為實時規劃提供了可能。

表2 規劃結果隨揮發系數變化規律

表3 規劃結果隨衰減系數變化規律

總體上講,改進的蟻群算法在規劃路徑的長度、平均方差和計算時間上均明顯比傳統方法占優。

3 結 論

文中通過引入搜索主方向、可視域以及可行域等定義,將傳統的二維蟻群搜索算法改進,并擴展至三維情況。并給出了算法的流程及步驟,然后通過Matlab進行了仿真分析。通過仿真得出該改進方法與傳統方法相比,運行效率大大提高,收斂速度加快,具有更好的穩定性。

參考文獻：

[1] Dorigo M, Stützle T. The Ant Colony Optimization Metaheuristic: Algorithms, Applications and Advances∥Handbook of Metaheuristics[M]. Glover F, Kochenberger G. MA: Kluwer, 2002

[2] 李士勇. 蟻群算法及其應用[M]. 哈爾濱：哈爾濱工業大學出版社，2004

Li Shiyong. Ant Colony Algorithms with Applications[M]. Harbin: Harbin Institute of Technology Press, 2004 (in Chinese)

[3] 伍祥紅. 基于蟻群優化的自主水下機器人路徑決策方法研究[D]. 哈爾濱：哈爾濱工程大學，2007

Wu Hongxiang. Research on Path Decision Making Method for AUV Based on ACO[D]. Harbin, Harbin Egineering University, 2007 (in Chinese)

[4] 史峰，王輝，胡斐,等. MATLAB智能算法30個安例分析[M]. 北京：北京航空航天大學出版社，2011：229-236

Shi Feng, Wang Hui, Hu Fei, et al. 30 Intelligent Algorithm Cases Analysis in MATLAB[M]. Beijing: Beihang University Press, 2011: 229-236 (in Chinese)

[5] Christian Blum, Marco Dorigo. The Hyper-Cube Framework for Ant Colony Optimization[J]. IEEE Trans Syst Man Cybern B, 2004, 34(2): 1161-1172

[6] Blum C, Roli A, Dorigo M. HC-ACO: the Hyper-Cube Framework for ant Colony Optimization[C]∥Proc MIC’2001——Metaheuristics Int Conf, 2001: 399-403

[7] 王曉林. 基于柵格法的仿生機器魚路徑規劃研究[D]. 天津：天津大學，2010

Wang Xiaolin. Path Planning of the Biomimetic Robotic Fish Based on the Grid Method[D]. Tianjin, Tianjin University, 2010 (in Chinese)