一種基于改進(jìn)的蟻群優(yōu)化算法的三維空間路徑搜索算法

李浩宇, 呂梅柏

(西北工業(yè)大學(xué) 航天學(xué)院, 陜西 西安 710072)

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

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

1 改進(jìn)的蟻群優(yōu)化算法模型

1.1 環(huán)境模型建立

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

1.2 符號(hào)描述與定義

由于傳統(tǒng)的蟻群優(yōu)化算法在每只螞蟻搜索路徑時(shí)對(duì)其所有的鄰近點(diǎn)進(jìn)行搜索，直至搜索到目標(biāo)點(diǎn)，這種方法雖然可以在全域內(nèi)搜索可行的路徑，但是會(huì)造成收斂速度慢，路徑不平滑等問(wèn)題，在三維空間情況下更為嚴(yán)重。本文引入搜索主方向，可視域以及可行域等定義將上述問(wèn)題得到了有效抑制，并應(yīng)用于三維空間的搜索問(wèn)題，其定義如下：

定義1 為了保證螞蟻在搜索路徑時(shí)盡量減少橫向的跨越，以起始點(diǎn)與終點(diǎn)差距大的坐標(biāo)軸方向?yàn)槿S路徑規(guī)劃的主方向，其可以是橫向、縱向、高度之一，記為MD。若MD為縱軸(x軸)的正方向(序號(hào)增加)，則值為1，負(fù)方向值為-1；橫軸(y軸)正方向值為2，負(fù)方向值為-2；豎軸(z軸)正方向值為3，負(fù)方向值為-3。若主方向上終點(diǎn)的坐標(biāo)值大于起點(diǎn)的坐標(biāo)值，即終點(diǎn)的序號(hào)大于起點(diǎn)的，則螞蟻每次在主方向上前進(jìn)一格(序號(hào)加1)；若主方向的坐標(biāo)值小于起點(diǎn)的，則相反。

定義2 假設(shè)MD為x軸正方向(MD=1)，則對(duì)于任意一個(gè)柵格空間R中的點(diǎn)gi,j,k，有V(gi,j,k)∈R?？啥x可視域V(gi,j,k)，滿足

(1)

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

圖1 可視域示意圖

當(dāng)可視域范圍過(guò)小，螞蟻在主方向上達(dá)到終點(diǎn)時(shí)，有可能由于橫向移動(dòng)范圍不足使得螞蟻無(wú)法到達(dá)搜索終點(diǎn)，所以可視域須大于某一范圍，同時(shí)需保證搜索空間的連通性，這里?。?/p>

(2)

式中:Nx、Ny、Nz分別為起始點(diǎn)和終點(diǎn)之間在3個(gè)軸方向的節(jié)點(diǎn)個(gè)數(shù),NM為主方向上的節(jié)點(diǎn)個(gè)數(shù),ceil為向上取整函數(shù)。

定義3 設(shè)tn時(shí)刻,螞蟻k處于g(tn),簡(jiǎn)記為gn,設(shè)此處的可視域?yàn)閂(gn),則設(shè)螞蟻k的可行后續(xù)節(jié)點(diǎn)集Ak(tn)={g|g∈V(gn),且g≠“1”}。

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

設(shè)在時(shí)刻tn,螞蟻s處在gi,j,k∈R,則對(duì)當(dāng)前點(diǎn)的可行后續(xù)點(diǎn)集As(tn)中節(jié)點(diǎn)的選擇概率計(jì)算如下:

(3)

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

(4)

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

1.4 蟻群信息素更新規(guī)則

信息素矩陣τ與環(huán)境建模得到的地圖矩陣相對(duì)應(yīng),每一個(gè)點(diǎn)的值代表相應(yīng)地圖上節(jié)點(diǎn)gi,j,k的信息素,信息素?cái)?shù)值大表示螞蟻經(jīng)過(guò)此點(diǎn)的次數(shù)多。在初始化時(shí),每一個(gè)點(diǎn)上的信息素值相同,均令其為1,表示信息素對(duì)選擇路徑點(diǎn)的影響都一樣。

在每次迭代過(guò)程蟻群中各螞蟻經(jīng)過(guò)的點(diǎn)進(jìn)行局部更新,目的是為了增加搜索未經(jīng)過(guò)點(diǎn)的概率,達(dá)到全局搜索的目的,局部更新規(guī)則如下

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

(5)

式中:ζ為衰減系數(shù);τi,j,k為螞蟻選擇的后續(xù)節(jié)點(diǎn)。

全局信息素更新是對(duì)每次迭代中的最優(yōu)路徑進(jìn)行更新。更新信息素矩陣中相對(duì)應(yīng)最優(yōu)路徑節(jié)點(diǎn)的值,是為了將每次迭代過(guò)程中按照指標(biāo)函數(shù)得到的最優(yōu)路徑p0,p1,…pn的節(jié)點(diǎn)上的值增加,從而在下次迭代中以更大的概率選擇此條路徑上的節(jié)點(diǎn)。在多次迭代之后,路徑就會(huì)逐漸收斂到全局最優(yōu)路徑。

全局信息素更新規(guī)則如下式計(jì)算:

(6)

(7)

式中:ρ為揮發(fā)系數(shù);Q為常數(shù);τi,j,k為每次迭代中最優(yōu)路徑上的信息素值;fk為最優(yōu)路徑適應(yīng)度值,一般取為路徑的長(zhǎng)度。

1.5 基于柵格法的三維空間蟻群優(yōu)化算法步驟

根據(jù)定義的符號(hào)描述,基于柵格法的蟻群優(yōu)化算法在三維空間的路徑搜索流程如圖2所示,其步驟可以總結(jié)如下:

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

2) k=1;

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

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

5) 計(jì)算出此時(shí)螞蟻的Ak,若Ak為空,則宣告這只螞蟻死亡,k=k+1,轉(zhuǎn)第3)步;否則,按狀態(tài)轉(zhuǎn)移規(guī)則計(jì)算螞蟻選擇任意gn+1∈Ak的概率,按輪盤(pán)賭的方式選擇某一gn+1,并設(shè)置此柵格點(diǎn)為螞蟻k的當(dāng)前位置,轉(zhuǎn)第6)步;

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

7) 進(jìn)化代數(shù)計(jì)數(shù)器count遞增1;

8) 若count>max,則算法停止,否則按信息素更新規(guī)則對(duì)蟻群信息素進(jìn)行更新處理,轉(zhuǎn)第2)步。

圖2 改進(jìn)的蟻群搜索算法流程

2 仿真結(jié)果及分析

表1規(guī)定了仿真時(shí)需要用到的一些基本搜索參數(shù),本文后面的仿真結(jié)果均以此參數(shù)設(shè)置得出,并且均為仿真計(jì)算90次的統(tǒng)計(jì)值。其中信息素?fù)]發(fā)系數(shù)ρ表示每次迭代信息素在最優(yōu)路徑上的揮發(fā)速度;局部信息素衰減系數(shù)ζ表示每次迭代中每只螞蟻所選路徑上的信息素衰減速度;信息素和啟發(fā)函數(shù)的重要程度α和β均為1,表明兩者的重要程度一樣。

表1 仿真基本參數(shù)

算法模擬仿真時(shí)使用52×60×50的柵格地圖模擬地形,起點(diǎn)坐標(biāo)為(50,4,1.925),終點(diǎn)坐標(biāo)為(3,57,2.353),由改進(jìn)的蟻群優(yōu)化搜索算法搜索的三維路徑表示如圖3所示:

圖3 路徑規(guī)劃結(jié)果

當(dāng)選擇信息素?fù)]發(fā)系數(shù)ρ=0.2,局部衰減系數(shù)ζ=0.2而蟻群種群數(shù)量不同時(shí),規(guī)劃的路徑長(zhǎng)度隨迭代次數(shù)的變化趨勢(shì)如圖4所示。從圖中可以看出隨著迭代次數(shù)的增加路徑的長(zhǎng)度趨于最優(yōu),且隨著種群數(shù)量的增加改進(jìn)方法的優(yōu)勢(shì)更加明顯。圖5所示為不同種群數(shù)量規(guī)劃的每次迭代結(jié)果的平均方差變化趨勢(shì),從對(duì)比可以看出改進(jìn)方法的平均方差遠(yuǎn)小于傳統(tǒng)方法,且波動(dòng)幅度比傳統(tǒng)方法小,說(shuō)明改進(jìn)方法的穩(wěn)定性明顯優(yōu)于傳統(tǒng)方法。

圖4 改進(jìn)方法與傳統(tǒng)方法的規(guī)劃結(jié)果隨迭代次數(shù)變化規(guī)律

圖5 改進(jìn)方法與傳統(tǒng)方法的規(guī)劃結(jié)果方差的變化規(guī)律

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

表2 規(guī)劃結(jié)果隨揮發(fā)系數(shù)變化規(guī)律

表3 規(guī)劃結(jié)果隨衰減系數(shù)變化規(guī)律

總體上講,改進(jìn)的蟻群算法在規(guī)劃路徑的長(zhǎng)度、平均方差和計(jì)算時(shí)間上均明顯比傳統(tǒng)方法占優(yōu)。

3 結(jié) 論

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

參考文獻(xiàn)：

[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] 李士勇. 蟻群算法及其應(yīng)用[M]. 哈爾濱：哈爾濱工業(yè)大學(xué)出版社，2004

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

[3] 伍祥紅. 基于蟻群優(yōu)化的自主水下機(jī)器人路徑?jīng)Q策方法研究[D]. 哈爾濱：哈爾濱工程大學(xué)，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個(gè)安例分析[M]. 北京：北京航空航天大學(xué)出版社，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] 王曉林. 基于柵格法的仿生機(jī)器魚(yú)路徑規(guī)劃研究[D]. 天津：天津大學(xué)，2010

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