基于帶電粒子搜索的無(wú)人潛航器航路規(guī)劃方法

趙云欽，蔡 超，王厚軍，李東武

(1.多譜信息處理技術(shù)國(guó)家級(jí)重點(diǎn)實(shí)驗(yàn)室(華中科技大學(xué) 自動(dòng)化學(xué)院)，武漢 430074；2.國(guó)家海洋技術(shù)中心，天津 300112； 3.天津航天中為數(shù)據(jù)系統(tǒng)科技有限公司，天津 300450)(*通信作者電子郵箱caichao@hust.edu.cn)

0 引言

無(wú)人潛航器(Unmanned Underwater Vehicle, UUV)是一種能在水下自主遠(yuǎn)程航行的智能化裝置，它能夠完成水下搜尋、偵察，甚至是軍事上的進(jìn)攻防守等任務(wù)[1-2]。如今海洋開(kāi)發(fā)日益加快，無(wú)人潛航器得到了各個(gè)國(guó)家的重視，不管是在軍事領(lǐng)域還是在民用領(lǐng)域都發(fā)揮著越來(lái)越重要的作用。航路規(guī)劃是UUV研究領(lǐng)域中的熱點(diǎn)問(wèn)題之一，它是指在綜合考慮航行器自身性能、能量損耗、威脅以及航行區(qū)域限制的情況下，在起始點(diǎn)和目標(biāo)點(diǎn)之間規(guī)劃出一條最優(yōu)或可行的航路[3]。

UUV航路規(guī)劃具有規(guī)劃區(qū)域廣闊、環(huán)境復(fù)雜、約束條件多等特點(diǎn)，這就對(duì)航路規(guī)劃算法的收斂速度、內(nèi)存空間需求都有比較高的要求。國(guó)內(nèi)外學(xué)者在航路規(guī)劃算法方面作了許多研究工作，也提出了多種航路規(guī)劃算法。Kanehara等[4]通過(guò)采用地圖格網(wǎng)化的方法將航路規(guī)劃問(wèn)題離散化，然后采用A*算法找到最短路徑；但是A*算法作為一種確定性算法，它的計(jì)算復(fù)雜度和規(guī)劃時(shí)間將隨著規(guī)劃區(qū)域的增大也將大幅上升。也有學(xué)者采用隨機(jī)性算法進(jìn)行航路規(guī)劃，如Khelchandra等[5]提出一種基于隨機(jī)采樣的航路規(guī)劃方法，該方法雖然能夠以比較高的概率在短時(shí)間內(nèi)規(guī)劃出一條路徑，但是也有可能規(guī)劃出一條不可行的路徑；Tarokh等[6]采用的遺傳算法，但是由于各種約束的存在，該方法會(huì)出現(xiàn)早熟而導(dǎo)致得不到最優(yōu)解；Englot等[7]也提出了基于蟻群算法的航路規(guī)劃方法，但對(duì)于連續(xù)的規(guī)劃空間，算法收斂速度慢，規(guī)劃用時(shí)長(zhǎng)；而粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法[8]參數(shù)設(shè)置比較復(fù)雜，局部搜索能力不佳，收斂速度慢。

帶電粒子搜索算法最早在2010年由Kaveh等[9]提出，它源于物理學(xué)中庫(kù)倫定律和牛頓定律的啟發(fā)，通過(guò)搜索空間中帶電粒子的相互作用，進(jìn)而達(dá)到尋優(yōu)的目的。該算法對(duì)于優(yōu)化問(wèn)題在保證解質(zhì)量的同時(shí)可以得到更快的收斂速度。自帶電粒子搜索(Charged System Search, CSS)算法提出以來(lái)，已經(jīng)在多個(gè)領(lǐng)域得到了應(yīng)用。Kaveh等[10]將CSS算法離散化并將其用于框架結(jié)構(gòu)優(yōu)化問(wèn)題的求解；?zy?n等[11]將該算法用于電力調(diào)度問(wèn)題，以減少傳輸消耗和NOx等有毒化學(xué)物質(zhì)的釋放；Precup等[12]將該算法用于模糊控制器的優(yōu)化。

本文將帶電粒子搜索算法與航路規(guī)劃問(wèn)題相結(jié)合，提出一種基于帶電粒子搜索的航路規(guī)劃方法。本文對(duì)航行器航路規(guī)劃問(wèn)題進(jìn)行建模，采用標(biāo)準(zhǔn)矢量電子海圖作為搜索空間，使用實(shí)數(shù)編碼的帶電粒子來(lái)表示航路，通過(guò)建立代價(jià)函數(shù)將多約束、復(fù)雜海洋環(huán)境下航路規(guī)劃的多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)換為單目標(biāo)優(yōu)化問(wèn)題，并用該方法對(duì)最終的單目標(biāo)問(wèn)題進(jìn)行優(yōu)化求解。實(shí)驗(yàn)分析表明該方法在保證規(guī)劃出的航路質(zhì)量的同時(shí)，收斂速度快、規(guī)劃耗時(shí)短。

1 UUV航路規(guī)劃問(wèn)題及模型建立

1.1 UUV航路規(guī)劃問(wèn)題

UUV航行在復(fù)雜的海洋環(huán)境中，為了保證航行器的安全航行不僅要考慮到海洋自然環(huán)境約束(如：洋流、風(fēng)浪、海底地形等)，還需考慮導(dǎo)航區(qū)域約束、戰(zhàn)場(chǎng)環(huán)境約束等。航路規(guī)劃要在綜合考慮多種因素的條件下，為航行器規(guī)劃出一條安全的，能夠順利完成目標(biāo)任務(wù)的航路，因此航路規(guī)劃問(wèn)題實(shí)質(zhì)上是一個(gè)帶約束的多目標(biāo)優(yōu)化問(wèn)題：

目標(biāo)函數(shù) minfit(X)=[f1(X),f2(X),…,fn(X)]T

約 束gi(X)≤0;i=1,2,…,p

hj(X)=0;i=1,2,…,q

Xl

決策變量X={X1,X2,…,Xm}

其中：Xl、Xu分別為決策變量X的下界和上界，決策變量的邊界值就構(gòu)成了目標(biāo)問(wèn)題的決策空；fi(X)(i=1,2,…,n)表示n個(gè)需要被同時(shí)優(yōu)化的目標(biāo)函數(shù)；gi(X)≤0(i=1,2,…,p)表示p個(gè)不等式約束函數(shù)；而hj(X)=0(i=1,2,…,q)表示q個(gè)等式約束函數(shù)。

多目標(biāo)優(yōu)化問(wèn)題往往包含了多個(gè)相互耦合的目標(biāo)函數(shù)，它可能沒(méi)有唯一的最優(yōu)解，而是一個(gè)包含無(wú)窮多個(gè)解的解集。最后，決策者需要對(duì)Pareto解集中的解作比較并進(jìn)行選擇，因此，UUV航路規(guī)劃中的模型建立和代價(jià)函數(shù)設(shè)計(jì)就是其中尤為關(guān)鍵的兩個(gè)部分。

1.2 模型建立

UUV在海洋環(huán)境中航行時(shí)，會(huì)受到自身物理性能限制[13]，主要有以下幾個(gè)方面：

1)航行器轉(zhuǎn)彎約束：UUV轉(zhuǎn)彎時(shí)，最大轉(zhuǎn)彎角度不能超過(guò)θmax，最小轉(zhuǎn)彎半徑不能小于Rmin：

2)安全航行深度約束：為了保證UUV的航行安全，其航行深度h應(yīng)該小于當(dāng)前位置海洋深度hsea，0

3)最大航程約束：UUV由于機(jī)載能耗有限，所以航路距離l不能超過(guò)其最大航程lmax，l

4)上浮約束：UUV在沒(méi)有海洋浮標(biāo)的海域中，為了能夠及時(shí)校正航路偏差，可以采用讓UUV上浮與衛(wèi)星進(jìn)行通信的方法，因此，航路需要在除風(fēng)浪區(qū)以外的位置每隔一定時(shí)間設(shè)置一個(gè)上浮點(diǎn)使UUV完成衛(wèi)星通信。

海洋環(huán)境復(fù)雜且范圍廣，合適的地圖環(huán)境描述與存儲(chǔ)方式對(duì)規(guī)劃精度和速度都有重要的影響。本文采用的是標(biāo)準(zhǔn)的矢量電子海圖來(lái)描述環(huán)境信息，它將海域中的每個(gè)要素都以點(diǎn)、線、面等幾何元素的形式存儲(chǔ)下來(lái)，相比柵格電子海圖具有存儲(chǔ)量小、精度高等優(yōu)點(diǎn)，并且當(dāng)環(huán)境發(fā)生改變時(shí)，用戶可以方便地在基礎(chǔ)數(shù)據(jù)上進(jìn)行修改更新。

由于海洋環(huán)境復(fù)雜，而環(huán)境因素對(duì)UUV航路規(guī)劃影響很大。為了便于算法的模擬計(jì)算，本文將海洋環(huán)境表達(dá)為以下幾種約束區(qū)域模型。

1)限制區(qū)：島嶼、禁飛區(qū)、暗礁等航行器不可達(dá)的區(qū)域，在本文中用凸多邊形來(lái)描述限制區(qū)。

2)威脅區(qū)：在某些區(qū)域，敵方在一些區(qū)域會(huì)部署雷達(dá)、防御武器等，這對(duì)航行器的安全性產(chǎn)生威脅，在航路規(guī)劃時(shí)應(yīng)盡量避開(kāi)這些區(qū)域。本文用橢圓來(lái)描述威脅區(qū)，當(dāng)航行器進(jìn)入這類(lèi)區(qū)域時(shí)，航行器有一定可能被攔截摧毀。穿過(guò)的威脅區(qū)的威脅等級(jí)越高，航行器被攔截的概率越大。

3)海流區(qū)：在海洋中的不同區(qū)域、不同深度海流的大小和方向是不同的，這對(duì)航行器的速度矢量產(chǎn)生影響，因此，在航路規(guī)劃時(shí)必須考慮到海流因素的影響，航行器在海流區(qū)中的航行速度是正常巡航速度與海流速度的矢量疊加。

4)風(fēng)浪區(qū)：在某些海域表面，由于風(fēng)的作用會(huì)引起海水的波動(dòng)。航行器在這類(lèi)區(qū)域上浮將會(huì)對(duì)自身安全性造成影響，因此在風(fēng)浪區(qū)航行器不能進(jìn)行上浮以及與衛(wèi)星進(jìn)行通信操作。由于在此區(qū)域無(wú)法進(jìn)行通信進(jìn)而對(duì)當(dāng)前航線進(jìn)行誤差矯正，這就會(huì)使航行器偏離既定航路。為了保證航行器的安全準(zhǔn)確航行，需要繞過(guò)風(fēng)浪區(qū)航行。

1.3 航路表示與代價(jià)計(jì)算

根據(jù)不同的實(shí)際要求、不同抽象層次，航行器的航路可以表達(dá)成多種形式。Capozzi[14]提出幾種典型的航路表達(dá)形式：

1)航行器空間位置點(diǎn)序列；

2)航行器速度和方向的時(shí)間序列；

3)航行器機(jī)動(dòng)動(dòng)作的時(shí)間序列；

4)任務(wù)級(jí)的抽象航路。

這四種航路表達(dá)方式抽象程度依次增加。無(wú)論采用什么表達(dá)形式，都應(yīng)以有利于航路規(guī)劃計(jì)算與航路的準(zhǔn)確表達(dá)為首要目標(biāo)。本文采用空間位置點(diǎn)序列表示航行器航路，例如：S表示起始點(diǎn)位置，T表示目標(biāo)點(diǎn)位置，X1,X2,…,Xm為中間航路點(diǎn)位置，航路就可以表示為：

{S,X1,X2,…,Xm,T}

因此航路規(guī)劃問(wèn)題實(shí)質(zhì)上是在規(guī)劃空間中找到一個(gè)滿足要求的m維的解向量。

本文綜合考慮了UUV的航程、海流、威脅等因素，將代價(jià)評(píng)估函數(shù)設(shè)置如下：

(1)

其中,f(xi)表示航路段xi的代價(jià)，它由時(shí)間代價(jià)ft和威脅代價(jià)fs組成。

2 基于帶電粒子搜索的航路規(guī)劃方法

2.1 CSS算法描述

帶電粒子搜索算法受到庫(kù)倫定律和牛頓定律的啟發(fā)，利用帶電粒子之間的相互作用來(lái)進(jìn)行尋優(yōu)，是一種具有全局搜索能力的智能算法。與蟻群算法、粒子群算法等智能算法相比，該算法中每個(gè)帶電粒子之間有更多的信息交流，它具有較強(qiáng)的全局搜索能力和更快的收斂速度等特點(diǎn)。

該算法首先會(huì)在規(guī)劃空間中隨機(jī)初始化一組初始解(稱為初始帶電粒子群)P={p1,p2,…,pn}，每個(gè)帶電粒子pi都被看成為一個(gè)半徑為a的帶電球體，其所帶電荷量qi由代價(jià)函數(shù)值確定，它將會(huì)在其周?chē)鷧^(qū)域產(chǎn)生一定強(qiáng)度的電場(chǎng)，如圖1所示。在電磁場(chǎng)中帶電粒子的電荷量越大，該帶電粒子對(duì)其他帶電粒子的吸引力就越大，通過(guò)電場(chǎng)力的影響，每個(gè)帶電粒子在規(guī)劃空間中進(jìn)行尋優(yōu)。在本方法中，利用代價(jià)值來(lái)間接表征帶電粒子的電荷量大小，電荷量越大則對(duì)其他帶電粒子的吸引力就越強(qiáng)，其他帶電粒子從該粒子繼承信息的繼承度就越高。

圖1 電場(chǎng)強(qiáng)度示意圖

根據(jù)庫(kù)倫定律，帶電粒子在電場(chǎng)中會(huì)受到電場(chǎng)力的作用，如下式所示：

其中：Eij表示電場(chǎng)強(qiáng)度；qj表示帶電粒子j的電荷量；ri和rj分別表示帶電粒子i，j的空間位置，因此在搜索空間中，帶電粒子會(huì)受到其他粒子產(chǎn)生的電場(chǎng)的影響，進(jìn)而在空間中進(jìn)行移動(dòng)尋優(yōu)。在每次迭代時(shí)，帶電粒子根據(jù)如下式進(jìn)行位置、速度更新：

Xj,old

Vj,new=(Xj,new-Xj,old)/Δt

其中:ka是加速度系數(shù)，kv是速度系數(shù)；Fj是帶電粒子j所受電場(chǎng)力合力;Δt是時(shí)間步長(zhǎng);Xj,new、Vj,new分別為位置和速度矢量；randj1和randj2都是均勻分布在(0，1)上的隨機(jī)數(shù)。該方法通過(guò)計(jì)算其他帶電粒子施加給當(dāng)前粒子的合力來(lái)確定該帶電粒子更新后的位置、速度等。重復(fù)迭代過(guò)程，直至滿足定義的算法終止條件后，停止迭代并得到優(yōu)化問(wèn)題的解。

2.2 基于CSS的航路規(guī)劃方法

由1.3節(jié)的分析，航路規(guī)劃問(wèn)題最終目標(biāo)是要在規(guī)劃空間中得到滿足要求的一個(gè)m維的解向量；因此在本文方法中，每個(gè)帶電粒子都被視為規(guī)劃空間中的一個(gè)解，并且解代表的航路的優(yōu)劣程度由上文航路代價(jià)部分描述方法來(lái)進(jìn)行度量。通過(guò)代價(jià)值再對(duì)每個(gè)帶電粒子自適應(yīng)更新其所帶電荷量，提高算法的收斂速度和自適應(yīng)能力。記帶電粒子集合為P，它由n個(gè)帶電粒子組成：P={p1,p2,…,pn}，帶電粒子pi代表規(guī)劃空間中的一條航路。對(duì)于任意帶電粒子pi，可以由式(1)計(jì)算得到該帶電粒子所代表航路的代價(jià)函數(shù)值fiti，故帶電粒子集合的代價(jià)為：

fit=[fit1,fit2,…,fitn]

因而可以根據(jù)代價(jià)函數(shù)值得到該帶電粒子群中的最優(yōu)帶電粒子pbest和最差帶電粒子pworst，以及它們分別的代價(jià)函數(shù)fitbest和fitworst：

pbest=min(fit1,fit2,…,fitn)

pworst=max(fit1,fit2,…,fitn)

較優(yōu)的帶電粒子相比較差的粒子應(yīng)該在搜索尋優(yōu)過(guò)程中發(fā)揮更重要的作用，因此，帶電粒子電荷量大小可以和代價(jià)函數(shù)值關(guān)聯(lián)起來(lái)。

在迭代過(guò)程中每個(gè)帶電粒子的電荷量、電場(chǎng)力以及位置速度計(jì)算方法定義如下：

1)電荷量。對(duì)于帶電粒子pi，將其電荷量qi通過(guò)上文定義的代價(jià)函數(shù)值，采用歸一化的方法來(lái)進(jìn)行定義：

(2)

可以看出越優(yōu)的帶電粒子其代價(jià)函數(shù)值越小，而所帶電荷量越大。這使得該帶電粒子對(duì)其他的粒子產(chǎn)生更大的電場(chǎng)力，進(jìn)而使較差的粒子朝著較優(yōu)的粒子運(yùn)動(dòng)。

2)帶電粒子間距離。本文所考慮優(yōu)化問(wèn)題的解空間是一個(gè)m維空間，其中任意兩個(gè)帶電粒子pi、pj的距離采用如式(3)進(jìn)行計(jì)算：

(3)

其中：Xi、Xj分別是帶電粒子pi和pj的位置，都是一個(gè)m維的向量；Xbest是當(dāng)前最優(yōu)粒子pbest的位置;ε是個(gè)極小正數(shù)，防止分母為0。

3)電場(chǎng)力。帶電粒子所受電場(chǎng)力合力的計(jì)算可將當(dāng)前帶電粒子所獲得的局部和全局信息有效地結(jié)合起來(lái)，為航路規(guī)劃算法優(yōu)化搜索提供依據(jù)。帶電粒子pj在維度k上所受電場(chǎng)力合力：

(4)

其中i1、i2為：

pij表示帶電粒子pj受到粒子pi電場(chǎng)力的概率：

其中rand是在(0，1)范圍內(nèi)均勻分布的隨機(jī)數(shù)。根據(jù)矢量疊加，最終可以得到帶電粒子pj所受到的電場(chǎng)力合力Fj：

Fj=[Fj1,Fj2,…,Fjm]

在最初的迭代搜索過(guò)程中，帶電粒子彼此之間離得都比較遠(yuǎn)，而此時(shí)庫(kù)侖力反比于帶電粒子距離的平方。在這種情況下，早期的迭代過(guò)程中帶電粒子會(huì)進(jìn)行更多的全局搜索，因此算法具有較強(qiáng)的探索能力。對(duì)于隨機(jī)性算法而言，在算法開(kāi)始的時(shí)候增強(qiáng)全局搜索能力，隨著迭代的進(jìn)行減小這種全局搜索是必要的。經(jīng)過(guò)一系列的迭代搜索過(guò)后，帶電粒子聚集在一個(gè)小的區(qū)域，故而帶電粒子間的距離變小，此時(shí)帶電粒子所受到的電場(chǎng)力合力正比于帶電粒子距離，開(kāi)始進(jìn)行精細(xì)的局部搜索，并且，這個(gè)階段帶電粒子所受電場(chǎng)力合力始終正比于其電荷量。較優(yōu)的帶電粒子具有較小的代價(jià)函數(shù)值，故而帶有較高的電荷量，在它的周?chē)鷮?huì)有較大的電場(chǎng)強(qiáng)度；也就相對(duì)于較差的帶電粒子而言，它對(duì)其他的粒子將會(huì)產(chǎn)生較大的吸引力，所以帶電粒子朝著好的粒子運(yùn)動(dòng)的趨勢(shì)將會(huì)大于朝著差的粒子運(yùn)動(dòng)的趨勢(shì)。

4)位置、速度更新。根據(jù)庫(kù)倫定律和牛頓運(yùn)動(dòng)定律，每次迭代規(guī)劃空間中的帶電粒子pj的每個(gè)維度k的位置速度分量將按如下公式進(jìn)行更新：

(5)

vjk(t+1)=xjk(t+1)-xjk(t)

(6)

其中：ka是加速度系數(shù)，用來(lái)調(diào)控其他帶電粒子對(duì)位置更新的影響；kv是速度系數(shù)，用來(lái)調(diào)控先前帶電粒子速度的影響；randj1和randj2都是均勻分布在(0，1)上的隨機(jī)數(shù)。ka與帶電粒子的電場(chǎng)力合力相關(guān)聯(lián)，較大的取值將會(huì)導(dǎo)致過(guò)快的收斂；較小的取值將會(huì)使收斂速度變慢，增加計(jì)算時(shí)間。而kv則平衡著全局搜索能力與局部搜索能力，kv較大則全局搜索能力強(qiáng)局部搜索能力弱，反之則全局搜索能力弱、局部搜索能力強(qiáng)。在算法開(kāi)始階段，全局搜索能力較強(qiáng)，隨著迭代搜索的進(jìn)行，全局搜索能力減弱、局部搜索能力增強(qiáng)，這樣才能達(dá)到好的尋優(yōu)效果，因此，本文將ka和kv設(shè)置如下：

(7)

(8)

其中：iter是當(dāng)前迭代次數(shù)；itermax是算法最大迭代次數(shù)。由式(3)和(4)可知，kv從初始值1開(kāi)始，隨著迭代次數(shù)iter的增加，非線性遞減；ka則隨著迭代次數(shù)增加，非線性單調(diào)遞增。隨著搜索算法進(jìn)入迭代后期局部搜索階段kv減小，ka增大速度變快，這避免了帶電粒子因速度過(guò)快而使算法無(wú)法在當(dāng)前最優(yōu)區(qū)域進(jìn)行更加精細(xì)的搜索。通過(guò)這種方法來(lái)平衡全局搜索與收斂速度，可以有效地避免算法的早熟收斂。

2.3 方法流程

基于CSS的航路規(guī)劃算法的流程如圖2所示，方法的具體步驟描述如下：

1)根據(jù)實(shí)際問(wèn)題設(shè)置合適的帶電粒子個(gè)數(shù)m，最大迭代次數(shù)itermax，算法終止條件；

2)根據(jù)航路規(guī)劃任務(wù)的要求，設(shè)置每個(gè)帶電粒子的維數(shù)；

3)初始化整個(gè)帶電粒子群，每個(gè)帶電粒子代表規(guī)劃空間中的一條航路，初始化每個(gè)帶電粒子的位置、速度；

4)根據(jù)設(shè)定的代價(jià)函數(shù)，計(jì)算出每個(gè)帶電粒子的電荷量；

5)計(jì)算帶電粒子所受電場(chǎng)力合力，更新帶電粒子的位置及速度；

6)更新每個(gè)帶電粒子的代價(jià)函數(shù)值；

7)確定是否達(dá)到終止條件，如果沒(méi)有，返回到步驟4)，否則算法結(jié)束；

8)輸出全局最優(yōu)代價(jià)函數(shù)值的帶電粒子所代表的航路。

圖2 基于CSS的航路規(guī)劃方法流程

3 實(shí)驗(yàn)結(jié)果及分析

本文在Intel Core i5- 3230M CPU、2.60 GHz、4 GB內(nèi)存的PC上進(jìn)行仿真實(shí)驗(yàn)，運(yùn)行環(huán)境為Windows 7，編程環(huán)境為VS2005。

相關(guān)實(shí)驗(yàn)參數(shù)設(shè)置為：帶電粒子群規(guī)模m為30。約束條件設(shè)置為：航行器最大轉(zhuǎn)彎角度60°，最小轉(zhuǎn)彎半徑200 m，上浮時(shí)間間隔為4 h。算法終止條件為：連續(xù)兩次迭代最優(yōu)代價(jià)值相差小于0.01，則算法終止。

本實(shí)驗(yàn)采用的是矢量電子海圖，地圖范圍為116.2°E～132.5°E，21.5°N～41.2°N，約為1 793 km×2 167 km的矩形區(qū)域。記號(hào)“”表示航行器的起始點(diǎn)，“▲”表示目標(biāo)點(diǎn)，其中限制區(qū)標(biāo)注為“A”，海流區(qū)標(biāo)注為“B”,風(fēng)浪區(qū)標(biāo)注為“C”，威脅區(qū)標(biāo)注為“D”。

實(shí)驗(yàn)中對(duì)本文方法與A*算法、粒子群算法和蟻群算法進(jìn)行多組對(duì)比實(shí)驗(yàn)，每次對(duì)比實(shí)驗(yàn)以上四種方法均在同樣的起始點(diǎn)、目標(biāo)點(diǎn)以及相同海域環(huán)境下進(jìn)行實(shí)驗(yàn)，記錄每種方法每次實(shí)驗(yàn)規(guī)劃得到的航路代價(jià)、實(shí)驗(yàn)耗時(shí)和占用內(nèi)存。其中：蟻群算法設(shè)置為迭代5次終止，信息素?fù)]發(fā)因子為0.3，螞蟻數(shù)為20；粒子群算法種群數(shù)目設(shè)置為30，終止條件設(shè)置為連續(xù)兩次迭代最優(yōu)代價(jià)值相差小于0.01，則算法終止。在不同海域環(huán)境下得到的航路規(guī)劃實(shí)驗(yàn)結(jié)果如圖3、圖4所示。

從表1、表2實(shí)驗(yàn)數(shù)據(jù)可以看出，航路規(guī)劃算法用時(shí)上從小到大依次為：基于帶電粒子搜索的航路規(guī)劃方法、粒子群算法、A*算法、蟻群航路規(guī)劃算法。為了對(duì)本文方法與粒子群航路規(guī)劃方法作進(jìn)一步比較，本文對(duì)每組實(shí)驗(yàn)記錄了這兩種方法最優(yōu)航路代價(jià)的收斂曲線，如圖5、圖6所示。在相同的實(shí)驗(yàn)條件下，本文方法得到的航路的代價(jià)值與粒子群算法航路代價(jià)值相差不大；但收斂速度比粒子群算法收斂速度快。這是因?yàn)樵诹Ｗ尤核惴ㄖ校Ｗ拥倪\(yùn)動(dòng)僅由局部最優(yōu)和全局最優(yōu)來(lái)決定，這樣大部分其他粒子所攜帶的信息都被忽略。這也是本文方法與粒子群算法的一個(gè)本質(zhì)不同，在本方法中，每個(gè)帶電粒子的運(yùn)動(dòng)是由其他帶電粒子對(duì)其電場(chǎng)力合力來(lái)確定的，每次迭代尋優(yōu)是綜合了其他帶電粒子影響的結(jié)果，帶電粒子之間有更多的信息交流。這一特點(diǎn)就使得帶電粒子能夠以一定概率更新到遠(yuǎn)離當(dāng)前局部最優(yōu)的位置，而這個(gè)位置可能比當(dāng)前全局最優(yōu)粒具有更好的適應(yīng)度，因此該算法相比粒子群算法具有更強(qiáng)的全局搜索能力；并且本文提出的非線性調(diào)整速度和加速度系數(shù)的方法平衡了全局搜索與局部搜索，在提高了算法收斂速度的同時(shí)，避免了算法的早熟。

圖3 繞島嶼航路規(guī)劃實(shí)驗(yàn)

圖4 復(fù)雜環(huán)境航路規(guī)劃實(shí)驗(yàn)

方法算法耗時(shí)/s航路長(zhǎng)度/km航路代價(jià)內(nèi)存占用/KB基于CSS航路規(guī)劃算法1.786292.8869632.82670234A?算法6.314291.5927332.681645646蟻群算法213.804313.2360134.3441802361粒子群算法3.598294.3106432.89878133

表2 復(fù)雜環(huán)境航路規(guī)劃實(shí)驗(yàn)結(jié)果比較

從以上兩組實(shí)驗(yàn)結(jié)果看，本文方法與確定性算法A*算法相比，A*算法最終規(guī)劃出的航路代價(jià)略優(yōu)；但是本文方法規(guī)劃用時(shí)間明顯少于A*算法。在規(guī)劃空間環(huán)境比較復(fù)雜的情況下，A*算法會(huì)占用大量?jī)?nèi)存。從表1、表2實(shí)驗(yàn)結(jié)果可以看出，當(dāng)規(guī)劃空間變得相對(duì)復(fù)雜時(shí)A*算法在第二組實(shí)驗(yàn)中內(nèi)存消耗比第一組實(shí)驗(yàn)提高了28.3%，而本文方法內(nèi)存消耗沒(méi)有太大變化，并且A*算法在復(fù)雜環(huán)境下尋優(yōu)過(guò)程中可能會(huì)產(chǎn)生回退，這會(huì)使算法耗時(shí)增大，而本文方法則不存在該問(wèn)題。

圖5 繞島嶼航路規(guī)劃實(shí)驗(yàn)CSS與PSO最優(yōu)航路代價(jià)收斂曲線

圖6 復(fù)雜環(huán)境航路規(guī)劃實(shí)驗(yàn)CSS與PSO最優(yōu)航路代價(jià)收斂曲線

蟻群算法也是一種隨機(jī)性算法，它基于螞蟻信息素這種間接交流方式，是一種離散的優(yōu)化方法。該算法本質(zhì)上是一種正反饋機(jī)制，最優(yōu)路徑上的螞蟻增多，留下的信息素強(qiáng)度變大，導(dǎo)致后面的螞蟻通過(guò)輪盤(pán)賭更大的概率會(huì)選擇到該路徑，最優(yōu)路徑上的螞蟻數(shù)量更多，最后收斂到這條路徑上。對(duì)于離散的搜索空間(如Voronoi圖等)，蟻群算法耗時(shí)和優(yōu)化結(jié)果都有較好的效果；但是對(duì)于連續(xù)的搜索空間，信息素的擴(kuò)散等操作將會(huì)使得算法耗費(fèi)的時(shí)間大幅度增加，信息素圖也會(huì)占用大量?jī)?nèi)存，而本文提出的方法對(duì)于連續(xù)問(wèn)題的求解則沒(méi)有這一問(wèn)題。從表1、表2也可以看出，本文方法與蟻群算法解的質(zhì)量相差無(wú)幾，但是該方法所用時(shí)間以及占用內(nèi)存都遠(yuǎn)小于蟻群算法。

4 結(jié)語(yǔ)

本文提出了基于帶電粒子搜索的航路規(guī)劃方法，并成功地將該方法運(yùn)用于無(wú)人潛航器的航路規(guī)劃，有效地解決了多約束復(fù)雜海洋環(huán)境下的航路規(guī)劃問(wèn)題。通過(guò)實(shí)驗(yàn)表明，該方法能夠快速為航行器規(guī)劃出可行航路，并通過(guò)對(duì)比實(shí)驗(yàn)表明，該方法與A*算法、蟻群算法、粒子群航路規(guī)劃算法相比，在保證解的質(zhì)量的同時(shí)，算法耗時(shí)較少，收斂速度更快。本文航路規(guī)劃方法對(duì)于特定的任務(wù)帶電粒子的維數(shù)是固定的，因此下一步可以將本方法中的帶電粒子的維數(shù)引入模糊性，而不是設(shè)置為固定的維數(shù)，這會(huì)使得本方法在適應(yīng)高維問(wèn)題的同時(shí)，優(yōu)化效果進(jìn)一步提高。