桂林信息科技學(xué)院電子工程學(xué)院 黃 東

隨著海上智能交通的發(fā)展，國(guó)內(nèi)在自主航行的無(wú)人船方面開(kāi)始發(fā)展起來(lái)。本文針對(duì)是無(wú)人船全局路徑規(guī)劃的研究，提出用柵格—蟻群算法和離散蟻群算法來(lái)進(jìn)行無(wú)人船路徑的規(guī)劃，而且驗(yàn)證了兩種算法在無(wú)人船的全局路徑規(guī)劃的可行性。通過(guò)仿真實(shí)驗(yàn)，在規(guī)劃路徑過(guò)程中，柵格—蟻群算法有較好的魯棒性。而離散蟻群算法在搜索地圖方面比柵格—蟻群算法更加有效，規(guī)劃的路徑長(zhǎng)度更短更平滑，規(guī)劃結(jié)果更加理想。

隨著智能化不斷的發(fā)展，無(wú)人船控制技術(shù)早已不是傳統(tǒng)的遙控技術(shù)，而是通過(guò)算法編程來(lái)實(shí)現(xiàn)自主航行。早期無(wú)人船研究的算法，它的控制方式主要是航向保持模式。如今無(wú)人船的自動(dòng)控制已發(fā)展到了航跡保持模式。這需要無(wú)人船在任何復(fù)雜工作環(huán)境下都能夠保持自動(dòng)航行的能為，并能自主制定一條合適的航線，無(wú)人船根據(jù)此航線前進(jìn)到達(dá)指定目標(biāo)。針對(duì)無(wú)人船路徑規(guī)劃，本文研究在無(wú)人船的路徑規(guī)劃上，分別對(duì)柵格—蟻群算法和離散蟻群算法這兩種算法進(jìn)行討論，并對(duì)這兩種算法進(jìn)行分析以及有效的改進(jìn)，為無(wú)人船自主航行技術(shù)的研究提供新的思路。

1 柵格—蟻群算法

1.1 柵格—蟻群算法

蟻群算法是90年代意大利學(xué)者M(jìn)arco Dorigo在他的博士論文中提出的，受到大自然中螞蟻覓食筑巢的行為影響，而研究發(fā)現(xiàn)螞蟻雖然沒(méi)有視覺(jué)，但是行走時(shí)可以釋放一種生物分泌物，行走這條路徑的螞蟻越多，這條路徑生物分泌物的濃度也越大，從而影響更多的螞蟻選擇這條路徑。蟻群通過(guò)這種生物信息素來(lái)實(shí)現(xiàn)路徑的選擇，受此啟發(fā)，這位學(xué)者提出了一種仿生進(jìn)化算法，也就是蟻群算法。目前該算法廣泛應(yīng)用于路徑規(guī)劃、數(shù)據(jù)挖掘、組合優(yōu)化、函數(shù)優(yōu)化、網(wǎng)絡(luò)路由優(yōu)化等。

1.2 柵格蟻群算法流程

假設(shè)有一群螞蟻，數(shù)量有N只，每只螞蟻都從起發(fā)點(diǎn)開(kāi)始出發(fā)搜尋食物。在柵格示意圖模型中，螞蟻的每一步行走都只能從自己所在柵格旁最近的柵格中選擇一個(gè)柵格前行。如圖1所示，當(dāng)這只螞蟻處在（2,2）這個(gè)柵格位置時(shí)，它可以選擇的柵格就會(huì)有（1,1）、（1,2）、（1,3）、（2,1）、（2,3）、（3,1）、（3,2）、（3,3）總共8個(gè)柵格。假設(shè)（2,3）和（3,3）是存在障礙物的，也就是說(shuō)（2,3）和（3,3）是不可行柵格，那么這只螞蟻就不會(huì)走這兩個(gè)柵格。

圖1 柵格—蟻群算法搜索過(guò)程示意圖模型

假設(shè)這群螞蟻中，第k只螞蟻處在一個(gè)柵格i上，這時(shí)它要選擇到一個(gè)柵格j的概率可以用式(1)表示。

α為信息濃度啟發(fā)因子，它是一個(gè)大于0的常數(shù)。β是期望啟發(fā)因子，也是一個(gè)大于0的常數(shù)，是螞蟻選擇下一個(gè)柵格位置的依據(jù)。G是這只螞蟻k在某一位置時(shí)允許選擇柵格的集合。每只螞蟻會(huì)在其經(jīng)過(guò)的路徑上留下分泌物也就是信息素。第k只螞蟻在其經(jīng)過(guò)的路徑上留下的信息素可以用式(2)表示。

C0是信息素強(qiáng)度，是大于0的常數(shù)。LK是螞蟻尋找到的路徑總長(zhǎng)。當(dāng)所有的螞蟻完成一輪搜索之后需要更新信息素，可以用式(3)表示。

P表示的是信息素的保留率，它的取值范圍是0≤ρ＜1。在更新信息素之后就會(huì)進(jìn)入下一輪循環(huán)的搜索。通過(guò)這種方式經(jīng)過(guò)反復(fù)的迭代之后，路徑距離較短的路徑上的信息素濃度會(huì)越來(lái)越大，信息素的積累也越來(lái)越多。當(dāng)?shù)_(dá)到一定數(shù)量之后，算法會(huì)收斂，也就是螞蟻去搜索食物的路徑會(huì)集中到一條信息素較多，也就是距離較短的路徑上。迭代過(guò)程結(jié)束，也就是算法的結(jié)束。其實(shí)終止的條件是迭代到一定的數(shù)量值，也就是設(shè)定的數(shù)量值，本文采用就是這種方式。

蟻群算法有很多優(yōu)點(diǎn)，比如具有很好的魯棒性和搜索較好解的能力。但也有一些不足之處，當(dāng)柵格模型較大計(jì)算量大時(shí)，不可避免的顯示出搜索效率低下和增加搜索時(shí)間的弊端。

1.3 仿真實(shí)驗(yàn)

仿真實(shí)驗(yàn)用C++面向?qū)ο笳Z(yǔ)言來(lái)實(shí)現(xiàn)算法，并將它存入到動(dòng)態(tài)鏈接庫(kù)中，用LabView 2012軟件來(lái)做程序主界面并利用它來(lái)調(diào)用C++語(yǔ)言庫(kù)。軟件左邊顯示的是環(huán)境和路線圖，路徑規(guī)劃的結(jié)果用直線和曲線顯示在左邊這個(gè)地圖上，右側(cè)可以顯示規(guī)劃路徑中GPS坐標(biāo)和算法計(jì)算所耗用的時(shí)間。

用高校的一個(gè)無(wú)名湖做了仿真實(shí)驗(yàn)，把無(wú)名湖的GPS坐標(biāo)生成柵格模型。柵格模型中每個(gè)柵格的邊長(zhǎng)是5m，仿真柵格模型共70行65列。算法使用的參數(shù)如表1所示。

表1 柵格—蟻群算法參數(shù)

仿真結(jié)果如圖2所示。

圖2 柵格—蟻群算法規(guī)劃路徑仿真實(shí)驗(yàn)

在左側(cè)圖中顯示有路徑規(guī)劃的起始點(diǎn)和目的地。右側(cè)的數(shù)據(jù)表明整個(gè)測(cè)試耗用時(shí)間766ms，圖中的封閉圓圈表示是小島，規(guī)劃的路徑避開(kāi)了湖中的小島?？梢钥闯鲆?guī)劃的是一條近似最佳的路徑。實(shí)驗(yàn)表明柵格—蟻群算法能夠規(guī)劃出一條繞開(kāi)小島的路徑，但還不夠精確，沒(méi)有能夠規(guī)劃出最優(yōu)路徑。

2 離散—蟻群算法

在前面仿真實(shí)驗(yàn)中，可以看到柵格—蟻群算法在無(wú)人船搜索路徑時(shí)由于受到柵格模型的限制，向前只有幾個(gè)方向。達(dá)不到更加準(zhǔn)確地搜索路徑到達(dá)目的地。經(jīng)過(guò)研究，在這里提出了離散蟻群算法。這種離散蟻群算法為了避免柵格模型的限制所以選用了源數(shù)據(jù)模型，讓螞蟻在搜索路徑前行時(shí)有很多方向可以選擇。最后計(jì)算結(jié)果得出的路徑長(zhǎng)度比柵格模型得出的路徑長(zhǎng)度更加短，也更加精確。

離散蟻群算法與柵格—蟻群算法這兩種算法相比較，離散蟻群算法中一條路徑的邊是否可行是不知道的，這只能由螞蟻在搜索路徑的時(shí)候來(lái)發(fā)現(xiàn)其周邊的路徑是否可行。而在柵格—蟻群算法中一條路徑的邊是否可行決定于此位置的柵格是不是可行柵格。另外離散蟻群算法與柵格—蟻群算法有一個(gè)明顯的差別，離散蟻群算法中因?yàn)槲浵伹斑M(jìn)的步長(zhǎng)是隨機(jī)的，所以當(dāng)它搜索兩次路徑時(shí)路徑的邊是基本不會(huì)相同的。也就是說(shuō)，螞蟻搜索路徑分泌的信息素是不會(huì)積累在某些固定的邊上。而柵格—蟻群算法中由于柵格模型的限制必然會(huì)使得可行柵格的邊是確定的。通過(guò)算法分析可以得出，采用柵格—蟻群算法可以把螞蟻搜尋路徑分泌的生物信息素保存在路徑邊上。而采用離散蟻群算法可以將螞蟻搜尋路徑的分泌的生物信息素存儲(chǔ)在路徑點(diǎn)上。而且能夠把蟻群螞蟻經(jīng)過(guò)幾次搜尋的路徑和螞蟻搜尋路徑產(chǎn)生的生物信息素都保存在備份中，這為螞蟻在以后的路徑搜尋過(guò)程中找到保存的備份提供了方便，從而全面了解到此刻位置前方曾經(jīng)走過(guò)的路徑點(diǎn)，依據(jù)路徑點(diǎn)上的生物信息素計(jì)算出選擇前行方向的概率。

2.1 離散蟻群算法流程

假設(shè)蟻群中總共有N個(gè)螞蟻，每個(gè)螞蟻從起始點(diǎn)出發(fā)搜索路徑。螞蟻搜索過(guò)程中前行方向的選擇是由一周離散化成后可成M個(gè)方向。如圖3所示，在此圖中M=18，螞蟻的前進(jìn)方向?yàn)閂■?，此刻位置為P?，F(xiàn)在以y軸為正方向，然后順時(shí)針旋轉(zhuǎn)，那么螞蟻全部可以選擇的方向集合如式(4)表示。

圖3 離散蟻群算法搜索過(guò)程示意圖

螞蟻行走的步長(zhǎng)是等于min Step和max Step之間的隨機(jī)數(shù)，min Step表示是最小步長(zhǎng)，max Step表示是最大步長(zhǎng)。步長(zhǎng)也可以設(shè)為固定值。如式(5)所示。

對(duì)照某一個(gè)方向θ的下一步位置的坐標(biāo)可以用式(6)表示。

為了不讓螞蟻搜索路徑時(shí)打轉(zhuǎn)回頭，陷入不斷轉(zhuǎn)圈的惡性循環(huán)。只有設(shè)置螞蟻前進(jìn)轉(zhuǎn)彎不能大于90°。如圖5.7所示當(dāng)前螞蟻前行時(shí)的所有可以選擇的方向中只有D3、D4…、D11（9個(gè)方向），不能選擇其它D12、D11…、D2（9個(gè)方向）。螞蟻在搜索路徑前進(jìn)的過(guò)程中會(huì)感覺(jué)到曾經(jīng)走過(guò)路徑點(diǎn)上保存的信息素。但這種螞蟻的感覺(jué)范圍是很有限的，一般來(lái)說(shuō)螞蟻會(huì)感覺(jué)到在自己前進(jìn)方向前方；小于自己感覺(jué)距離的半圓形區(qū)域內(nèi)曾經(jīng)走過(guò)的歷史路徑點(diǎn)。如圖5.7所示的陰影部分表示的就是螞蟻的感覺(jué)范圍，A、B和C三點(diǎn)是螞蟻感覺(jué)曾經(jīng)走過(guò)路徑的歷史路徑點(diǎn)。例如路徑點(diǎn)A會(huì)使陰影部分被選擇的D3方向的概率增加，而D2方向因?yàn)榇笥?0°而導(dǎo)致不會(huì)被選擇，D2的被選概率為0；同樣的原理路徑點(diǎn)B使陰影部分被選擇的D7和D8方向的概率增加；路徑點(diǎn)C使陰影部分被選擇的D9和D10的概率增加。蟻群中第k只螞蟻選擇方向θ前進(jìn)的概率的計(jì)算如式(7)表示。

圖5 兩種算法規(guī)劃路徑效果

當(dāng)螞蟻的感覺(jué)距離大于螞蟻和目標(biāo)之間的間隔時(shí)，不論目標(biāo)在哪個(gè)方向，螞蟻會(huì)立刻尋找到目標(biāo)。蟻群中每只螞蟻搜索到一條路徑后，就會(huì)在它所走過(guò)路徑的路徑點(diǎn)上產(chǎn)生一些信息素，那么第k只螞蟻在走過(guò)的路徑點(diǎn)i上產(chǎn)生的信息素的計(jì)算可以用公式(8)計(jì)算。

C1是常數(shù)，而且大于1。LK表示的是螞蟻路徑總的長(zhǎng)度。全部螞蟻完成一輪搜尋路徑后，曾經(jīng)走過(guò)的路徑所保留的信息素會(huì)揮發(fā)一些，剩下的為保留率ρ（0≤ρ＜1）。接著進(jìn)入下一輪迭代，達(dá)到結(jié)束條件后結(jié)束

2.2 仿真實(shí)驗(yàn)

離散蟻群算法的仿真實(shí)驗(yàn)還是將高校的一個(gè)無(wú)名湖作為源數(shù)據(jù)模型。在實(shí)驗(yàn)中，螞蟻的min Step（最小步長(zhǎng)）、max Step（最大步長(zhǎng)）和feel Dist（感知距離）調(diào)整得很合理。實(shí)驗(yàn)中起始點(diǎn)到目的地的距離為D，參數(shù)如表2所示。

表2 離散蟻群算法參數(shù)

仿真結(jié)果如圖4所示。

圖4 離散蟻群算法規(guī)劃路徑仿真實(shí)驗(yàn)

從實(shí)驗(yàn)中可以看出：在無(wú)名湖中的測(cè)試消耗了約43s的時(shí)間，實(shí)驗(yàn)中規(guī)劃的路徑剛好繞過(guò)了湖中的小島。這驗(yàn)證了離散蟻群算法是能夠準(zhǔn)確的規(guī)劃出一條繞開(kāi)障礙物的路徑的。

前面記述了柵格—蟻群算法以及離散蟻群算法的流程，并通過(guò)仿真實(shí)驗(yàn)對(duì)這兩種算法進(jìn)行了驗(yàn)證。雖然算法的真實(shí)運(yùn)行的效果會(huì)受到很多因素的影響，比如受到計(jì)算機(jī)整體的性能，編程所用的語(yǔ)言，實(shí)現(xiàn)算法的方式等。但在相同的測(cè)試條件下進(jìn)行比較還是具有很好的參考性的。在這里再次對(duì)高校的這個(gè)無(wú)名湖進(jìn)行了兩種算法的路徑規(guī)劃，這次兩種算法采用相同起點(diǎn)和目標(biāo)，參數(shù)設(shè)置如表2，評(píng)估的結(jié)果如表3所示。

表3 兩種算法的比較

兩種算法路徑規(guī)劃的效果如圖5所示。

圖4和表3中表明柵格—蟻群算法和離散蟻群算法各有特點(diǎn)，在性能上柵格—蟻群算法較好，在規(guī)劃路徑結(jié)果上離散蟻群算法更好。柵格—蟻群算法本身受柵格模型的限制，得到的最優(yōu)路徑有一些多余的彎路，它跟實(shí)際的最優(yōu)路線比較有一些差距，如圖5(a)所示。離散蟻群算法由于步長(zhǎng)的自適應(yīng)性的特點(diǎn)，所以規(guī)劃的路徑還是彎折小，而且路徑很平滑。離散蟻群算法規(guī)劃的路徑可以說(shuō)是最優(yōu)的路徑，它跟實(shí)際的最優(yōu)路線基本相同。無(wú)人船按照該路徑行駛會(huì)比較平穩(wěn)，對(duì)自動(dòng)控制來(lái)說(shuō)是比較理想的。如圖5(b)所示。但是離散蟻群算法得到的最優(yōu)路徑也是付出代價(jià)的，離散蟻群算法比柵格—蟻群算法更加耗時(shí)?？偟膩?lái)說(shuō)，在實(shí)際使用中到底選用哪種算法，還是要根據(jù)實(shí)際需要來(lái)衡量。