基于人工魚(yú)群- 蟻群算法的UUV三維全局路徑規(guī)劃

胡致遠(yuǎn)， 王征， 楊洋， 尹洋

(海軍工程大學(xué) 電氣工程學(xué)院, 湖北 武漢 430033)

0 引言

水下無(wú)人航行器(UUV)具有體積小、機(jī)動(dòng)能力強(qiáng)、智能化程度高、隱身性能好、作業(yè)風(fēng)險(xiǎn)低等特點(diǎn)，在海洋領(lǐng)域得以廣泛應(yīng)用。路徑規(guī)劃作為控制技術(shù)之一，能夠保證UUV在具有障礙物環(huán)境的作業(yè)空間內(nèi)，尋找到一條從起始點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)路徑。按照對(duì)環(huán)境的知曉程度，可以分為局部路徑規(guī)劃和全局路徑規(guī)劃。其中，全局路徑規(guī)劃適用于已知的海洋環(huán)境，為UUV的安全性和可靠性提供重要的支撐。

總體上看，路徑規(guī)劃算法可以分為傳統(tǒng)算法和智能算法。相比于傳統(tǒng)算法，智能算法具有簡(jiǎn)單、高效、適應(yīng)性強(qiáng)、魯棒性好等特點(diǎn)，被廣泛應(yīng)用于路徑規(guī)劃問(wèn)題。應(yīng)用較為廣泛的有蟻群(ACO)算法、粒子群優(yōu)化(PSO)算法、蜂群算法、人工魚(yú)群算法(AFSA)等。除此之外，部分學(xué)者將螢火蟲(chóng)算法、煙花算法等用于路徑規(guī)劃問(wèn)題，也得到了較好的研究成果。

ACO算法是意大利學(xué)者Dorigo等提出的一種新的模擬進(jìn)化算法，是基于生物界群體啟發(fā)行為的一種隨機(jī)搜索尋優(yōu)方法，在解決優(yōu)化組合的問(wèn)題上有良好的適應(yīng)性，比較適合于求解三維路徑規(guī)劃問(wèn)題。

圍繞ACO算法的優(yōu)化問(wèn)題，文獻(xiàn)[9]將告警信息素概念引入至ACO算法，減少了螞蟻的無(wú)用搜索，提升了算法的整體收斂速度，但同時(shí)增加了算法的計(jì)算量；文獻(xiàn)[10]將遺傳算法的交叉操作結(jié)合到蟻群系統(tǒng)的路徑尋優(yōu)過(guò)程中，加強(qiáng)了蟻群系統(tǒng)的路徑尋優(yōu)能力；文獻(xiàn)[11]將PSO算法與ACO算法相結(jié)合，利用PSO算法進(jìn)行路徑預(yù)搜索，優(yōu)化了初始信息素配置，改善整體算法性能，但對(duì)于ACO算法的全局尋優(yōu)能力缺乏考慮。

AFSA與ACO算法均屬于智能仿生算法，在種群優(yōu)化方面具有很多相似之處。圍繞兩者之間的融合問(wèn)題，文獻(xiàn)[12]計(jì)算了當(dāng)前路徑上的信息素和所有信息素累加和的比值，通過(guò)對(duì)比擁擠度因子與上述比值的關(guān)系，決定ACO算法是否依靠轉(zhuǎn)移概率選取下一路徑點(diǎn)。文獻(xiàn)[13]在文獻(xiàn)[12]的基礎(chǔ)上，以AFSA搜索到的最優(yōu)值更新ACO算法的初始信息素，解決了帶時(shí)間窗的車(chē)輛路徑問(wèn)題。文獻(xiàn)[14]中交替使用AFSA和ACO算法，不斷地進(jìn)行信息素更新和全局搜索，在解決工件數(shù)目較多的批調(diào)度問(wèn)題時(shí)，具有較高的效率。因此對(duì)于兩個(gè)算法的融合問(wèn)題值得進(jìn)一步研究。

本文采用柵格法對(duì)下載的真實(shí)海洋環(huán)境進(jìn)行建模。考慮到傳統(tǒng)ACO算法存在的初期搜索的盲目性、較為依賴(lài)初始信息素分布、易于陷入“早熟”等問(wèn)題，將AFSA與ACO算法進(jìn)行融合和改進(jìn)，并通過(guò)仿真實(shí)驗(yàn)加以驗(yàn)證。

1 海洋環(huán)境獲取和處理

1.1 海底地形獲取

全局路徑規(guī)劃適用于已知的海洋環(huán)境。獲取實(shí)際的海洋環(huán)境數(shù)據(jù)直接關(guān)系到UUV全局路徑規(guī)劃結(jié)果的有效性。

目前關(guān)于海底地形的數(shù)據(jù)庫(kù)較多，數(shù)據(jù)的開(kāi)源性便于用戶(hù)根據(jù)需要下載對(duì)應(yīng)的數(shù)據(jù)庫(kù)數(shù)據(jù)。全球海陸數(shù)據(jù)庫(kù)(GEBCO)包含2.9億個(gè)海水深度的探測(cè)數(shù)據(jù)，數(shù)據(jù)精度能夠滿(mǎn)足路徑規(guī)劃研究的需要。

GEBCO提供了全球地圖的顯示插件，如圖1所示。在插件上選取指定的海域框格，便可以下載對(duì)應(yīng)的采樣矩陣，用于后續(xù)的全局路徑規(guī)劃研究。

圖1 GEBCO插件顯示圖Fig.1 GEBCO image

1.2 柵格法環(huán)境建模

目前針對(duì)環(huán)境建模方法主要包含柵格法、八叉樹(shù)法和切線圖環(huán)境表示法等。其中，柵格法建模具有操作簡(jiǎn)單、易于編程實(shí)現(xiàn)、與路徑規(guī)劃算法結(jié)合緊密等特點(diǎn)，能夠?qū)?fù)雜的三維環(huán)境轉(zhuǎn)換為計(jì)算機(jī)可以處理的數(shù)據(jù)文件。針對(duì)三維環(huán)境特點(diǎn)，采取等柵格平面法進(jìn)行環(huán)境建模。

如圖2所示，起始點(diǎn)和目標(biāo)點(diǎn)之間的區(qū)域：-為路徑規(guī)劃區(qū)域，點(diǎn)位于平面，點(diǎn)位于平面。將點(diǎn)設(shè)為坐標(biāo)原點(diǎn)，UUV的主航行方向設(shè)為軸，水平面內(nèi)與軸垂直的方向設(shè)為軸，軸為深度方向，與水平面垂直。

沿軸方向，進(jìn)行等距離切分，從而形成+1個(gè)垂直于軸并且平行于的柵格平面～+1。對(duì)任一平面沿著軸等分次，沿著軸方向等分次，從而在每個(gè)柵格平面中形成×個(gè)柵格。

為保證UUV航行的安全性，在每個(gè)柵格平面中，規(guī)定只要柵格中含有低于海洋深度或障礙物等情況的柵格均視為不可行柵格，圖中用深色表示，其余柵格視為可行柵格，圖中用淺色表示。

圖2 柵格法建模示意圖Fig.2 Schematic diagram of the grid model

通過(guò)柵格法建模后，三維路徑規(guī)劃問(wèn)題可以轉(zhuǎn)換為在多個(gè)垂直于主航行方向上的柵格平面中依次選取可行路徑點(diǎn)～的問(wèn)題。由于柵格平面沿軸方向均勻分布，因此研究中只需保存各路徑點(diǎn)沿軸和軸方向的坐標(biāo)信息，減小了計(jì)算機(jī)的存儲(chǔ)量。各路徑點(diǎn)之間連線形成的路徑～便構(gòu)成完整的三維路徑。

1.3 搜索框設(shè)置

路徑點(diǎn)搜索過(guò)程中，如果對(duì)下一柵格平面中的每個(gè)柵格點(diǎn)進(jìn)行遍歷搜索，將會(huì)導(dǎo)致搜索過(guò)程較為復(fù)雜，增加了算法的計(jì)算量。與此同時(shí)，UUV沿主航行方向航行時(shí)，受到其本身機(jī)動(dòng)性限制，不可能在縱向和橫向上有過(guò)大的位移，部分路徑點(diǎn)將無(wú)法到達(dá)，失去研究意義。

綜合考慮算法的計(jì)算成本和UUV的實(shí)際機(jī)動(dòng)性能，進(jìn)行搜索框設(shè)置如圖3所示，進(jìn)一步篩選可行路徑點(diǎn)。搜索框由UUV的最大縱移距離和最大橫移距離構(gòu)成。當(dāng)位于平面中的路徑點(diǎn)搜索下一平面+1中的路徑點(diǎn)+1時(shí)，只需要對(duì)搜索框中的可行路徑點(diǎn)進(jìn)行搜索即可。

圖3 搜索框設(shè)置示意圖Fig.3 Schematic diagram of the search box

2 融合算法設(shè)計(jì)

2.1 融合算法思路

ACO算法模擬自然界螞蟻的覓食行為，通過(guò)信息素濃度的變化，指引螞蟻尋找最優(yōu)路徑。ACO算法作為智能啟發(fā)式搜索算法的一種，具有較強(qiáng)的適應(yīng)性、魯棒性、自組織性和分布式計(jì)算特性。但是，初始信息素的均勻分布使得算法初期具有一定的盲目性，算法的收斂速度因此降低。

AFSA是李曉磊博士于2002年提出的基于生物群體行為的智能算法。該算法模擬魚(yú)群的覓食、聚群、追尾、隨機(jī)等行為進(jìn)行搜索尋優(yōu)，具有簡(jiǎn)單、魯棒性強(qiáng)、收斂速度快、初始參數(shù)選擇不敏感等特點(diǎn)。因此，可以考慮將AFSA算法與ACO算法相結(jié)合，形成魚(yú)群蟻群融合優(yōu)化AFACO算法。

在算法初始階段，利用AFSA進(jìn)行路徑預(yù)搜索，形成若干條可行路徑。增加可行路徑對(duì)應(yīng)路徑點(diǎn)的初始信息素分布，形成優(yōu)化后的初始信息素分布。將優(yōu)化后的初始信息素分布傳遞至ACO進(jìn)行三維路徑規(guī)劃，從而降低ACO算法前期搜索的盲目性，提升整體算法的收斂速度。

2.2 融合算法流程

根據(jù)融合算法思路，制定算法流程，算法流程圖如圖4所示。主要步驟如下：

圖4 融合算法流程圖Fig.4 Flow chart of the fusion algorithm

1)使用GEBCO插件，下載路徑規(guī)劃研究所需的海域數(shù)據(jù)庫(kù)，并進(jìn)行環(huán)境地圖的繪制；

2)設(shè)定起始點(diǎn)目標(biāo)點(diǎn)信息，進(jìn)行柵格法建模，確定劃分的平面?zhèn)€數(shù)、柵格數(shù)量等；

3)設(shè)定AFSA相關(guān)參數(shù)，初始化人工魚(yú)群分布；

4)分別以聚群和追尾為主要行為方式，穿插進(jìn)行覓食和隨機(jī)行為，形成新的人工魚(yú)群分布，得到對(duì)應(yīng)的食物濃度，根據(jù)食物濃度大小選擇相應(yīng)的魚(yú)群分布；

5)若未達(dá)到魚(yú)群算法最大迭代次數(shù)則繼續(xù)循環(huán)，反之，增加當(dāng)前魚(yú)群對(duì)應(yīng)路徑點(diǎn)的初始信息素值，形成優(yōu)化后的初始信息素分布；

6)設(shè)定ACO算法的相關(guān)參數(shù)，利用優(yōu)化后的初始信息素，進(jìn)行ACO算法的路徑搜索；

7)計(jì)算路徑適應(yīng)度值，進(jìn)行局部信息素和全局信息素更新；

8)判斷是否達(dá)到了ACO算法的最大迭代次數(shù)。當(dāng)達(dá)到最大迭代次數(shù)后，保存仿真結(jié)果，并進(jìn)行結(jié)果的分析與處理。

3 AFSA的路徑預(yù)搜索

3.1 基本的AFSA

人工魚(yú)群的當(dāng)前狀態(tài)為，包含條人工魚(yú)，則該狀態(tài)下對(duì)應(yīng)的食物濃度可以通過(guò)目標(biāo)函數(shù)計(jì)算，并表示為：=()，在考慮路徑長(zhǎng)度最短問(wèn)題時(shí)，目標(biāo)函數(shù)即為路徑的長(zhǎng)度值。每條人工魚(yú)的感知范圍為，感知范圍內(nèi)其他人工魚(yú)的數(shù)量為，移動(dòng)步長(zhǎng)為，擁擠度為。人工魚(yú)與之間的距離,=‖-‖。

1)覓食行為

人工魚(yú)在其感知范圍內(nèi)，隨機(jī)選擇另一狀態(tài)，其對(duì)應(yīng)的食物濃度若優(yōu)于，則表明狀態(tài)優(yōu)于狀態(tài)，人工魚(yú)需要往該方向前進(jìn)一步，狀態(tài)更新為

(1)

如果并不優(yōu)于，則重新隨機(jī)選取狀態(tài)進(jìn)行比較。設(shè)置最大嘗試次數(shù)為_(kāi)。當(dāng)嘗試次數(shù)達(dá)到_時(shí)，若仍不滿(mǎn)足覓食行為移動(dòng)條件，則執(zhí)行隨機(jī)行為。

2)聚群行為

以人工魚(yú)為中心，搜尋其感知范圍內(nèi)其他人工魚(yú)的數(shù)量及中心位置。當(dāng)>時(shí)，表明當(dāng)前附近食物較為充足且不太擁擠，人工魚(yú)向中心位置前進(jìn)一步，否則執(zhí)行覓食行為。狀態(tài)更新公式為

(2)

3)追尾行為

以人工魚(yú)為中心，搜尋其感知范圍內(nèi)其他人工魚(yú)的數(shù)量及擁有最大食物濃度的人工魚(yú)。當(dāng)>時(shí)，表明當(dāng)前附近食物較為充足且不太擁擠，人工魚(yú)向前進(jìn)一步，否則執(zhí)行覓食行為。狀態(tài)更新公式為

(3)

4)隨機(jī)行為

人工魚(yú)在感知范圍內(nèi)隨機(jī)選取一個(gè)方向進(jìn)行移動(dòng)，狀態(tài)更新公式為

=+*

(4)

3.2 AFSA設(shè)計(jì)

AFSA中，每一條人工魚(yú)對(duì)應(yīng)一種可行解，因此在三維路徑規(guī)劃問(wèn)題中，可以將每條人工魚(yú)視為一條可行路徑。條人工魚(yú)在第階段的狀態(tài)可表示為

(5)

由于起始點(diǎn)和目標(biāo)點(diǎn)均已確定，即每條人工魚(yú)表示的路徑中起始點(diǎn)和目標(biāo)點(diǎn)坐標(biāo)固定不變。假設(shè)路徑起始點(diǎn)坐標(biāo)為(1,,)，目標(biāo)點(diǎn)坐標(biāo)為(+1,,)，人工魚(yú)狀態(tài)可以?xún)?yōu)化為

(6)

受到搜索框的限制，人工魚(yú)的步長(zhǎng)和最大橫移距離和最大縱移距離存在的關(guān)系為

≤min (,)

(7)

4 ACO算法的路徑規(guī)劃

4.1 基本的ACO算法

傳統(tǒng)ACO算法中，信息素通常分布在節(jié)點(diǎn)之間的連接上。對(duì)于三維路徑規(guī)劃問(wèn)題，路徑點(diǎn)即對(duì)應(yīng)ACO算法的節(jié)點(diǎn)。由于路徑點(diǎn)數(shù)量較多，節(jié)點(diǎn)之間的連接較為復(fù)雜，若將信息素存儲(chǔ)于各路徑點(diǎn)之間的連接上，勢(shì)必增加了算法的空間復(fù)雜度。因此，考慮將信息素分布于各離散的路徑點(diǎn)上，任意路徑點(diǎn)對(duì)應(yīng)一個(gè)信息素值。各路徑點(diǎn)所包含信息素含量代表了對(duì)螞蟻的吸引程度。

411 啟發(fā)值大小

啟發(fā)值關(guān)系到ACO算法的收斂性、穩(wěn)定性以及求解的優(yōu)化性。第個(gè)平面路徑點(diǎn)，坐標(biāo)(,,)到第+1個(gè)平面路徑點(diǎn)+1，坐標(biāo)(+1,+1,+1)的啟發(fā)值,+1為

(8)

式中：、、為加權(quán)參數(shù)；,+1表示(,,)和(+1,+1,+1)之間的距離，計(jì)算公式為

(9)

+1,表示(+1,+1,+1)與目標(biāo)點(diǎn)(,,)之間的距離，計(jì)算公式為

(10)

+1表示(+1,+1,+1)所在平面中可行路徑點(diǎn)數(shù)量+1與總路徑點(diǎn)數(shù)量的比值，

(11)

為路徑深度方向變化值，通過(guò)相鄰節(jié)點(diǎn)的深度坐標(biāo)和+1進(jìn)行計(jì)算，

(12)

按照實(shí)際求解問(wèn)題，取1，取當(dāng)前節(jié)點(diǎn)與目標(biāo)點(diǎn)橫坐標(biāo)之間的差值，達(dá)到距離最短的設(shè)計(jì)原則；取正數(shù)，表示期望下一節(jié)點(diǎn)選擇上要多考慮其可行性，保證UUV的航行安全。

412 轉(zhuǎn)移概率

螞蟻在路徑搜索時(shí)，會(huì)依據(jù)路徑點(diǎn)所含的啟發(fā)值和信息素值計(jì)算轉(zhuǎn)移概率。轉(zhuǎn)移概率計(jì)算公式為

(13)

式中：+1表示路徑點(diǎn)(+1,+1,+1)的信息素值；,+1表示兩平面路徑點(diǎn)之間的啟發(fā)值；為信息素重要程度因子，其值越大，表示信息素在轉(zhuǎn)移過(guò)程中作用越大；為啟發(fā)值重要程度因子，其值越大，表示啟發(fā)值在轉(zhuǎn)移過(guò)程中作用越大。

413 信息素更新

為避免ACO算法陷入局部最優(yōu)解，當(dāng)螞蟻搜尋到一個(gè)路徑點(diǎn)或者尋找到一條可行路徑后，需要進(jìn)行信息素的局部更新和全局更新。

局部信息素更新目的是減小螞蟻已通過(guò)節(jié)點(diǎn)的信息素值，增加未通過(guò)節(jié)點(diǎn)的被選擇概率，實(shí)現(xiàn)全局搜索的目的。

局部信息素更新公式為

=(1-)

(14)

式中：為平面路徑點(diǎn)的信息素；為局部信息素的衰減系數(shù)。

全局信息素更新在螞蟻完成一條路徑規(guī)劃后，選擇最佳路徑，增加該路徑上的信息素值，提高被選擇的概率。信息素的局部更新和全局更新共同保證了ACO算法的成功搜索能力。

全局信息素更新公式為

=(1-)+Δ

(15)

(16)

式中：()為第只螞蟻經(jīng)過(guò)點(diǎn)路徑長(zhǎng)度；為全局信息素更新系數(shù)；為常量系數(shù)。

414 適應(yīng)度函數(shù)

通過(guò)適應(yīng)度函數(shù)判斷路徑規(guī)劃結(jié)果的優(yōu)劣程度。針對(duì)路徑最短問(wèn)題，當(dāng)前路徑的長(zhǎng)度與適應(yīng)度值密切相關(guān)。適應(yīng)度函數(shù)設(shè)置為

(17)

式中：(path)表示路徑path的總長(zhǎng)度，可以通過(guò)累加相鄰路徑點(diǎn)坐標(biāo)+1、的二范數(shù)求得。

4.2 改進(jìn)ACO算法

ACO算法與AFSA具有一定的相似性：在不考慮信息素指導(dǎo)因素前提下，螞蟻的搜索行為和AFSA中的覓食行為類(lèi)似；螞蟻優(yōu)先選擇信息素濃度高的路徑與人工魚(yú)的聚群和追尾行為類(lèi)似。

但是，AFSA設(shè)置了擁擠度參數(shù)，在算法的初期可以避免個(gè)體過(guò)早地聚集到信息素較高的路徑上，克服了“早熟”現(xiàn)象，提高了算法的全局尋優(yōu)能力。

鑒于上述分析，將擁擠度因子思想引入傳統(tǒng)ACO算法，將轉(zhuǎn)移概率更新為

(18)

式中：+1表示當(dāng)前選擇的路徑點(diǎn)擁擠度約束系數(shù)，根據(jù)路徑點(diǎn)所含信息素濃度大小進(jìn)行設(shè)定。假設(shè)+1平面中所有路徑點(diǎn)所含的最大信息素濃度為，借鑒文獻(xiàn)[12]中的思想，將擁擠度約束系數(shù)設(shè)置為

(19)

傳統(tǒng)ACO算法路徑點(diǎn)選取依照轉(zhuǎn)移概率，按照輪盤(pán)賭的方法進(jìn)行選擇。由于各路徑點(diǎn)之間的轉(zhuǎn)移概率相差不大，如果依照輪盤(pán)賭的方法選擇下一節(jié)點(diǎn)，不一定能完全保證具有較優(yōu)轉(zhuǎn)移概率的節(jié)點(diǎn)被選取。因此選取的路徑點(diǎn)+1：

(20)

考慮到融合算法已經(jīng)優(yōu)化了初始信息素分布，因此在算法前期全局信息素更新系數(shù)選取較小的值，從而保證螞蟻主要依靠初始信息素尋找路徑；算法中期選取較大的值，避免信息素的堆積，增強(qiáng)算法的全局搜索能力；算法后期，由于較優(yōu)路徑基本搜索完畢，為了避免算法后期發(fā)散，選取較小的值。假設(shè)算法的最大迭代次數(shù)為，參考文獻(xiàn)[21]，將的大小選取如下：

(21)

5 仿真結(jié)果分析

5.1 仿真實(shí)驗(yàn)環(huán)境

從GEBCO下載經(jīng)度122.85°E～123.10°E，緯度24.15°N～24.40°N的海域數(shù)據(jù)集，數(shù)據(jù)沿經(jīng)度和緯度方向每隔1 km采樣，采樣矩陣大小為30×30，UUV的主航行方向?yàn)檠亟?jīng)度方向。利用MATLAB軟件對(duì)采樣矩陣處理后，可以繪制采樣的三維海洋環(huán)境，繪制出的海底地形圖如圖5所示。

圖5 三維海底環(huán)境圖Fig.5 Three-dimension submarine environment

依照柵格法建模，將研究海域沿經(jīng)度方向切分30個(gè)柵格平面，并將起始點(diǎn)設(shè)置在第一個(gè)平面，目標(biāo)點(diǎn)設(shè)置在最后一個(gè)平面。

仿真平臺(tái)配置為Windows 7系統(tǒng)，Intel Core i5處理器，8 GB內(nèi)存，算法利用MATLAB 2017A編程實(shí)現(xiàn)。

5.2 相關(guān)仿真結(jié)果

仿真中需要對(duì)算法相關(guān)參數(shù)進(jìn)行設(shè)置。依據(jù)仿真實(shí)驗(yàn)環(huán)境設(shè)定，將柵格法參數(shù)設(shè)置記錄于表1中。參照文獻(xiàn)[12]和文獻(xiàn)[16]中，關(guān)于AFSA和ACO算法的參數(shù)設(shè)置，將算法對(duì)應(yīng)的參數(shù)列于表2和表3中。

表1 柵格法參數(shù)設(shè)置

表2 AFSA部分參數(shù)設(shè)置

表3 ACO算法部分參數(shù)設(shè)置

按照融合算法的流程及參數(shù)設(shè)置，進(jìn)行MATLAB編程仿真，經(jīng)過(guò)AFSA預(yù)處理后結(jié)果如圖6所示。

圖6 AFSA預(yù)處理結(jié)果圖Fig.6 Preprocessed results after AFSA

增加已搜索到的可行路徑上路徑點(diǎn)的信息素量，形成優(yōu)化后的初始信息素分布。將優(yōu)化后的初始信息素分布傳遞至ACO算法，進(jìn)行仿真實(shí)驗(yàn)。為驗(yàn)證算法的有效性，在仿真中進(jìn)行傳統(tǒng)ACO算法、PSO算法和本文融合(AFACO)算法的對(duì)比實(shí)驗(yàn)。所得路徑規(guī)劃結(jié)果圖、路徑俯視圖及適應(yīng)度值變化趨勢(shì)圖如圖7～圖9所示。

圖7 路徑規(guī)劃結(jié)果圖Fig.7 Path planning results

圖8 路徑結(jié)果俯視圖Fig.8 Top view of path planning results

圖9 適應(yīng)度值變化趨勢(shì)圖Fig.9 Variation trend of fitness value

傳統(tǒng)ACO算法在270次迭代時(shí)，達(dá)到最佳適應(yīng)度值為41.398 1，PSO算法在267次迭代時(shí)，達(dá)到最佳適應(yīng)度值為40.730 6，而本文融合算法在174次迭代時(shí)，達(dá)到最佳適應(yīng)度值為40.033 8。

對(duì)算法連續(xù)仿真10次，將所得仿真結(jié)果的平均值記錄于表4中。

表4 仿真結(jié)果(平均值)

5.3 仿真結(jié)果分析

從圖6中可以看出，通過(guò)AFSA的預(yù)搜索，部分可行路徑已經(jīng)被找到，能夠?yàn)槌跏夹畔⑺胤植继峁﹨⒖肌?/p>

圖7和圖8表明傳統(tǒng)ACO算法、PSO算法及本文的AFACO算法均能實(shí)現(xiàn)UUV的三維路徑規(guī)劃。結(jié)合圖9的對(duì)比可以得到以下結(jié)論：

1)相比于傳統(tǒng)ACO算法，AFACO算法和PSO算法在迭代初期的適應(yīng)度值曲線能夠較快的收斂，收斂速度較快；

2)與PSO算法不同，AFACO算法在算法后期仍具有較強(qiáng)的局部尋優(yōu)能力，能夠找到具有較優(yōu)適應(yīng)度值的路徑，即具有較優(yōu)路徑長(zhǎng)度的路徑。

為了避免算法隨機(jī)性帶來(lái)的誤差，表4計(jì)算了連續(xù)10次仿真結(jié)果的平均值?？梢钥闯觯珹FACO算法在達(dá)到最小迭代次數(shù)時(shí)的耗時(shí)最小，與此同時(shí)，在最佳適應(yīng)度值和最小迭代次數(shù)方面，較傳統(tǒng)ACO算法及PSO算法均有一定的提升。

6 結(jié)論

本文充分利用了AFSA和ACO算法的特點(diǎn)，進(jìn)行了人工魚(yú)群- 蟻群融合算法的深入研究。通過(guò)對(duì)三維海洋環(huán)境的建模、融合算法的設(shè)計(jì)、ACO算法的改進(jìn)等實(shí)現(xiàn)了UUV的三維路徑規(guī)劃。仿真結(jié)果表明，融合算法能夠在保證獲取最優(yōu)路徑的前提下，使用較少的迭代次數(shù)，收斂速度更快，算法的有效性得以驗(yàn)證。

[1] 鐘宏偉.國(guó)外無(wú)人水下航行器裝備與技術(shù)現(xiàn)狀及展望[J].水下無(wú)人系統(tǒng)學(xué)報(bào), 2017, 25(3): 215-225.

ZHONG H W. Review and prospect of equipment and techniques for unmanned undersea vehicle in foreign countries[J]. Journal of Unmanned Undersea Systems, 2017, 25(3): 215-225. (in Chinese)

[2] 嚴(yán)浙平,趙玉飛,陳濤,等.一種基于導(dǎo)航誤差空間的無(wú)人水下航行器路徑規(guī)劃方法[J].兵工學(xué)報(bào), 2014, 35(8): 1243-1250.

YAN Z P, ZHAO Y F, CHEN T, et al. A novel method of uuv path planning based on navigation error space [J]. Acta Armamentarii, 2014, 35(8): 1243-1250. (in Chinese)

[3] 曹曉明,魏勇,衡輝,等. 海流擾動(dòng)下無(wú)人水下航行器的動(dòng)態(tài)面反演軌跡跟蹤控制[J].系統(tǒng)工程與電子技術(shù), 2021, 43(6): 1664-1672.

CAO X M, WEI Y, HENG H, et al. Dynamic surface backstepping trajectory tracking control of unmanned underwater vehicles with ocean current disturbances[J]. Systems Engineering and Electronic, 2021, 43(6): 1664-1672. (in Chinese)

[4] AGHABABA M P, AMROLLAHI M H, BORJKHANI M. Application of GA, PSO, and ACO algorithms to path planning of autonomous underwater vehicles[J]. Journal of Marine Science and Application, 2012, 11(3): 378-386.

[5] 杜映峰, 陳萬(wàn)米, 范彬彬. 群智能算法在路徑規(guī)劃中的研究及應(yīng)用[J]. 電子測(cè)量技術(shù), 2016, 39(11): 65-70.

DU Y F, CHEN W M, FAN B B. Research and application of swarm intelligence algorithm in path planning[J]. Electronic Measurement Technology, 2016, 39(11): 65-70. (in Chinese)

[6] PANDEY P, SHUKLA A, TIWARI R. Three-dimensional path planning for unmanned aerial vehicles using glowworm swarm optimization algorithm[J]. International Journal of System Assurance Engineering and Management, 2018, 9(4): 836-852.

[7] 馬焱,肖玉杰,陳軼,等.基于改進(jìn)煙花- 蟻群算法的海流環(huán)境下水下無(wú)人潛航器的避障路徑規(guī)劃[J].導(dǎo)航與控制, 2019, 18(1): 51-59.

MA Y, XIAO Y J, CHEN Y, et al. Obstacle avoidance path planning of unmanned underwater vehicle in ocean current environment based on improved fireworks-ant colony algorithm[J]. Navigation and Control, 2019, 18(1): 51-59. (in Chinese)

[8] PU X, XIONG C, JI L, et al. 3D path planning for a robot based on improved ant colony algorithm[J/OL]. Evolutionary Intelligence, 2020(2020-04-13) [2021-03-30]. https:∥link.springer.com/article/10.1007/s12065-020-00397-6.

[9] MA Y N, GONG Y J, XIAO C F, et al. Path planning for autonomous underwater vehicles: An ant colony algorithm incorporating alarm pheromone[J]. IEEE Transactions on Vehicular Technology, 2018, 68(1): 141-154.

[10] 潘昕,吳旭升,侯新國(guó),等.基于遺傳螞蟻混合算法的AUV全局路徑規(guī)劃[J].華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版), 2017, 45(5): 45-49，76.

PAN X, WU X S, HOU X G, et al. Global path planning based on genetic-ant hybrid algorithm for AUV[J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2017, 45(5): 45-49，76. (in Chinese)

[11] 朱佳瑩, 高茂庭. 融合粒子群與改進(jìn)蟻群算法的AUV路徑規(guī)劃算法[J].計(jì)算機(jī)工程與應(yīng)用, 2021, 57(6): 267-273.

ZHU J Y, GAO M T. AUV path planning based on particle swarm optimization and improved ant colony optimization[J]. Computer Engineering and Applications, 2021, 57(6): 267-273. (in Chinese)

[12] 修春波, 張雨虹. 基于蟻群與魚(yú)群的混合優(yōu)化算法[J].計(jì)算機(jī)工程, 2008, (14): 206-207，218.

XIU C B, ZHANG Y H. Hybrid optimization algorithm based on ant colony and fish school[J]. Computer Engineering, 2008, (14): 206-207，218. (in Chinese)

[13] 鄒挺. 基于蟻群和人工魚(yú)群混合群智能算法在物流配送路徑優(yōu)化問(wèn)題中的應(yīng)用研究[D]. 蘇州：蘇州大學(xué), 2011.

ZOU T. A study on the issue of vehicle route optimization upon ant colony algorithm, artificial fish swarm algorithm and hybrid swarm intelligence algorithm[D]. Suzhou：Soochow University, 2011. (in Chinese)

[14] 呂順風(fēng). 蟻群魚(yú)群混合算法在差異工件批調(diào)度中的應(yīng)用[D].合肥：中國(guó)科學(xué)技術(shù)大學(xué), 2017.

Lü S F. Application of hybrid algorithms based on ant colony optimization and artificial fish swarm for batch processing machine with non-identical job sizes[D]. Hefei: University of Science and Technology of China, 2017. (in Chinese)

[15] MAYER L, JAKOBSSON M, ALLEN G, et al. The nippon foundation-GEBCO seabed 2030 project: The quest to see the world’s oceans completely mapped by 2030[J]. Geosciences, 2018, 8(2):63.

[16] 劉利強(qiáng), 于飛, 戴運(yùn)桃. 基于蟻群算法的水下潛器三維空間路徑規(guī)劃[J]. 系統(tǒng)仿真學(xué)報(bào), 2008, 20(14): 3712-3716.

LIU L Q, YU F, DAI Y T. Path planning of underwater vehicle in 3D space based on ant colony algorithm[J]. Journal of System Simulation, 2008, 20(14): 3712-3716. (in Chinese)

[17] 丑強(qiáng). 虛擬環(huán)境中基于八叉樹(shù)的碰撞檢測(cè)問(wèn)題[D].長(zhǎng)春：吉林大學(xué), 2007.

CHOU Q. Collision detection in virtual environment based on octree[D]. Changchun：Jilin University, 2007. (in Chinese)

[18] 王磊. 海洋環(huán)境下水下機(jī)器人快速路徑規(guī)劃研究[D].哈爾濱：哈爾濱工程大學(xué), 2007.

WANG L. Research on fast path planning for AUV in ocean environment[D]. Harbin: Harbin Engineering University, 2007. (in Chinese)

[19] DORIGO M, DI CARO G, GAMBARDELLA L M. Ant algorithms for discrete optimization[J]. Artificial Life, 1999, 5(2): 137-172.

[20] 李曉磊. 一種新型的智能優(yōu)化方法- 人工魚(yú)群算法[D]. 杭州：浙江大學(xué), 2003.

LI X L. A new intelligent optimization method-artificial fish school algorithm[D]. Hangzhou：Zhejiang University, 2003. (in Chinese)

[21] 陳雄, 袁楊. 一種機(jī)器人路徑規(guī)劃的蟻群算法[J]. 系統(tǒng)工程與電子技術(shù), 2008, 30(5): 952-955.

CHEN X, YUAN Y. Novel ant colony optimization algorithm for robot path planning[J]. Systems Engineering and Electronics, 2008, 30(5): 952-955. (in Chinese)