融合粒子群與改進(jìn)蟻群算法的AUV路徑規(guī)劃算法

朱佳瑩，高茂庭

上海海事大學(xué) 信息工程學(xué)院，上海 201306

海洋資源已經(jīng)成為人類開發(fā)的重點，但復(fù)雜的海洋環(huán)境對人類水下作業(yè)有著極大的限制，水下機(jī)器人正在成為海洋作業(yè)的主角，自主式水下機(jī)器人（Autonomous Underwater Vehicle，AUV）依靠自身攜帶的能源進(jìn)行水下作業(yè)。由于在整個過程中無法補(bǔ)充能源，因此利用路徑規(guī)劃與安全避障技術(shù)對AUV 導(dǎo)航控制，是其能否精確、安全和完整地完成水下作業(yè)的關(guān)鍵。AUV路徑規(guī)劃問題已經(jīng)成為了一個研究熱點[1]，主要涉及兩方面問題：一是對海洋環(huán)境進(jìn)行三維建模；二是選取合適的算法進(jìn)行全局路徑規(guī)劃。

海洋環(huán)境建模主要有兩類方法：一類是規(guī)則地形模型，主要利用正方形、矩形等規(guī)則形狀進(jìn)行組合來表示海底表面；另一類是不規(guī)則地形模型，將三角形、多邊形等不規(guī)則形狀作為模型單元的基礎(chǔ)[2]。文獻(xiàn)[3]使用Voronoi圖法簡化三維水下環(huán)境，生成全局路線圖；文獻(xiàn)[4]將Delaunay 三角模型應(yīng)用于被測地標(biāo)，建立拓?fù)淠Ｐ?。文獻(xiàn)[5]利用八叉樹模型來反映AUV 工作環(huán)境，但主要應(yīng)用于較大障礙物之間的路徑規(guī)劃，不適合存在許多小障礙物的環(huán)境；文獻(xiàn)[6-7]不考慮水深，將三維空間簡化為二維柵格模型，節(jié)省了空間，但卻丟失了環(huán)境信息；文獻(xiàn)[8-9]將三維空間劃分為若干平面，然后利用二維柵格模型將每個平面柵格化，有效實現(xiàn)三維柵格建模。綜上，文獻(xiàn)[3-4]使用不規(guī)則地形模型，雖然能夠真實地反映環(huán)境信息，但計算較復(fù)雜，占用較多空間。文獻(xiàn)[5-9]采用規(guī)則地形模型，簡單、計算量小，適用于三維路徑規(guī)劃問題，其中的柵格模型更適合與各種智能算法相結(jié)合。

路徑規(guī)劃算法可以歸納為以下四類：基于幾何模型搜索的算法（Dijkstra、A*等）、基于概率采樣的算法（概率路線圖、快速拓展隨機(jī)樹等）、人工勢場算法和智能算法（粒子群算法、蟻群算法、遺傳算法、模擬退火算法、人工神經(jīng)網(wǎng)絡(luò)等）[2]。文獻(xiàn)[10]使用A*算法求解最短路徑規(guī)劃問題，能在規(guī)劃過程中及時中斷和恢復(fù)，但其空間復(fù)雜度是指數(shù)級別的，不適合大規(guī)模復(fù)雜環(huán)境；文獻(xiàn)[11]采用RRT*（Rapidly-exploring Random Trees）算法在線進(jìn)行二維AUV 路徑搜索，但隨機(jī)性強(qiáng)，往往難以得到全局最優(yōu)路徑；文獻(xiàn)[12]將人工勢場算法與速度合成算法相結(jié)合，實現(xiàn)準(zhǔn)確避障，但容易陷入局部最優(yōu)解。文獻(xiàn)[13]提出一種混合自適應(yīng)蟻群算法（Ant Colony Optimization，ACO），有很強(qiáng)的全局搜索能力，但缺乏早期信息，收斂速度慢；文獻(xiàn)[14]將粒子群算法（Particle Swarm Optimization，PSO）應(yīng)用于路徑規(guī)劃問題，算法簡單、初期收斂速度快，將它與蟻群算法相結(jié)合能夠有效改善蟻群算法的不足。

近年來，AUV 路徑規(guī)劃與安全避障技術(shù)得到了快速的發(fā)展，但仍存在一些急待解決的問題，一是為簡化處理，現(xiàn)有的水下機(jī)器人路徑規(guī)劃研究大部分沒有考慮海拔信息，將三維環(huán)境簡化為二維環(huán)境，無法滿足海洋勘探的實際需要；二是現(xiàn)有的AUV 三維路徑規(guī)劃算法在面對復(fù)雜的實際問題時還存在計算復(fù)雜度大、路徑規(guī)劃效果不理想、不穩(wěn)定等問題。

針對上述問題以及國內(nèi)外研究現(xiàn)狀，本文對AUV三維路徑規(guī)劃問題展開研究，采用三維柵格模型對真實海洋環(huán)境進(jìn)行建模，將粒子群算法與改進(jìn)蟻群算法相融合實現(xiàn)三維海洋環(huán)境中的AUV 全局路徑規(guī)劃，找出一條從給定起點到終點的最優(yōu)或近似最優(yōu)的無碰撞路徑。

1 相關(guān)模型

實現(xiàn)水下路徑規(guī)劃包括兩方面的基礎(chǔ)：一是對AUV 所處的海洋環(huán)境建模，將水下環(huán)境信息轉(zhuǎn)化為一種計算機(jī)能夠識別的表達(dá)方式；二是對AUV 三維路徑規(guī)劃問題建立路徑評價模型，用來衡量路徑的好壞，也可以看作本文優(yōu)化問題的目標(biāo)函數(shù)。

1.1 海洋環(huán)境模型

建立海洋環(huán)境模型是實現(xiàn)AUV路徑規(guī)劃的前提條件，下面先介紹本文真實海洋環(huán)境數(shù)據(jù)的獲取方式；再介紹基于空間分層思想建立三維柵格模型并進(jìn)行海洋環(huán)境建模；最后介紹如何在該環(huán)境模型中實現(xiàn)路徑規(guī)劃任務(wù)。

1.1.1 真實海洋環(huán)境數(shù)據(jù)的獲取

目前有多種海洋環(huán)境開源數(shù)據(jù)庫，本文使用的海底地形數(shù)據(jù)來源于全球海陸數(shù)據(jù)庫（General Bathymetric Chart of the Oceans，GEBCO）。在 GEBCO 地圖上選取某海域進(jìn)行采樣，形成采樣矩陣，下載可以得到采樣矩陣中各點的海拔數(shù)據(jù)，并使用環(huán)境建模方法對獲取的環(huán)境數(shù)據(jù)進(jìn)行建模。

1.1.2 真實海洋環(huán)境數(shù)據(jù)三維柵格建模

海洋環(huán)境模型需要在采樣得到的海洋環(huán)境上建立三維空間坐標(biāo)系，如圖1所示。

圖1 三維柵格環(huán)境模型示意圖

其中，X軸、Y軸分別表示水域的長度和寬度，Z軸表示海拔高度，OABC 表示AUV 整個工作區(qū)域。沿X軸將三維空間等距離切片分層，每個YOZ平面都是一個二維柵格平面，對平面上的每個柵格進(jìn)行考察，小于等于該處海底海拔值的柵格為障礙柵格，標(biāo)記為0，其余為自由柵格，標(biāo)記為1。通過若干層二維柵格，最后組成三維柵格來表示整個海洋環(huán)境。除海底山脈外，本文還隨機(jī)產(chǎn)生了若干懸浮球形障礙來模擬真實海洋環(huán)境，并將對應(yīng)位置處的柵格標(biāo)記為障礙柵格。最終，AUV 工作環(huán)境由一個三維0-1矩陣表示。

1.1.3 路徑規(guī)劃算法在三維柵格模型中的實現(xiàn)

三維柵格模型中引入了空間分層的思想，將整個AUV 工作空間均勻劃分為N個二維柵格平面。令起點和終點分別設(shè)置在第一層和最后一層平面上，則一條完整的路徑必定與每一層平面都會有一個交點，由此，AUV 路徑規(guī)劃問題可以轉(zhuǎn)化為在N-2 個中間柵格平面上分別求一個最優(yōu)中間路徑點的問題。

若要將路徑規(guī)劃算法應(yīng)用于該三維柵格模型中，也必須融入這種空間分層思想。本文路徑規(guī)劃算法均為智能算法，先在中間每層平面上隨機(jī)選取一個中間路徑點的位置，再通過多輪迭代的不斷學(xué)習(xí)，最終依靠群集智能收斂到最優(yōu)中間路徑點附近，將所有路徑點相連即為求得的最優(yōu)路徑。

1.2 路徑評價模型

從給定起點P1開始，經(jīng)過若干中間路徑點P2,…,PN-1,最后到達(dá)給定終點PN，將這些路徑點相連，得到一條完整路徑path，即為一個可行解，解的形式如式（1）所示：

對于所有可行解，必須建立一個路徑評價模型來評估路徑好壞[15]。本文綜合考慮路徑長度、崎嶇性和危險性等指標(biāo)。

1.2.1 路徑長度

路徑長度是路徑規(guī)劃問題首要考慮的一個因素，其計算如式（2）所示：

式（2）中，Pi表示第i層?xùn)鸥衿矫嫔下窂近c的坐標(biāo)(i,yi,zi)；‖Pi+1-Pi‖ 表示Pi與其下一路徑點Pi+1之間的距離，其距離度量采用歐氏距離計算；N為路徑點總數(shù)。對所有路徑段距離求和得到總的路徑長度，該值越小則路徑越短。

1.2.2 路徑崎嶇性

由于AUV 攜帶能源有限，過多的起伏會導(dǎo)致能源的快速消耗，因此希望規(guī)劃的路徑盡可能平滑。路徑崎嶇性通過式（3）計算：

式（3）中，|zi+1-zi|表示Pi到下一路徑點Pi+1深度方向的位移，為簡化計算，將所有求和，近似表示路徑的崎嶇程度。該值越小則路徑越平緩。

1.2.3 路徑危險性

由于AUV 在實際的航行過程中難免存在誤差，路徑越貼近障礙物則潛在的風(fēng)險就越大，所以將路徑周圍的危險性也作為一個評價因素，主要考察距離路徑兩個柵格范圍內(nèi)的障礙物情況，其余較遠(yuǎn)的障礙物假定不會威脅到AUV。路徑危險性的計算如式（4）所示：

式

（4）中，Obstacle_Num(Pi)表示距離Pi兩個柵格范圍內(nèi)的障礙物總數(shù)；Fdanger(path)表示一條路徑上每個路徑點周圍平均存在的障礙物個數(shù)，該值越小則路徑越安全。

在環(huán)境建模階段可以預(yù)先計算每個柵格周圍的障礙物數(shù)量，存儲在一個三維矩陣中，在路徑規(guī)劃階段直接調(diào)用，可以減少算法的運(yùn)行時間，提高運(yùn)行效率。

針對上述三個評價指標(biāo)，為了將多目標(biāo)的優(yōu)化問題轉(zhuǎn)化為單目標(biāo)問題進(jìn)行求解，先使用min-max標(biāo)準(zhǔn)化方法對求得的三個指標(biāo)值分別做歸一化處理，再對三者加權(quán)求和得到總的路徑評價值，該值越小則說明規(guī)劃出來的路徑越好，將其作為路徑評價函數(shù)，并求其最小化，具體計算如式（5）所示：

2 PSO-ACO路徑規(guī)劃算法

本章將具體介紹本文所提出的AUV三維路徑規(guī)劃算法（PSO-ACO），先使用粒子群算法預(yù)搜索路徑，其結(jié)果用來優(yōu)化蟻群算法的初始信息素；然后再對蟻群算法的狀態(tài)轉(zhuǎn)移規(guī)則、信息素更新方式作出進(jìn)一步改進(jìn)，并加入獎懲機(jī)制，實現(xiàn)AUV全局路徑規(guī)劃。

PSO-ACO路徑規(guī)劃算法流程如圖2所示。

圖2 PSO-ACO算法流程圖

2.1 粒子群算法預(yù)搜索路徑

傳統(tǒng)蟻群算法將每個路徑點上的初始信息素設(shè)定為一個常值，螞蟻在搜索初期將等概率地從周圍可行點集中選擇一個路徑點走，螞蟻需要迭代更多次，才能在不斷嘗試中找到一條完整路徑，這也是傳統(tǒng)蟻群算法初期收斂速度慢的主要原因之一。

為解決初期收斂速度慢的問題，引入粒子群算法，利用其初期收斂速度快的特點，與蟻群算法互補(bǔ)。先使用粒子群算法快速預(yù)搜索路徑，再將每個粒子路徑上的初始信息素提高，從而加強(qiáng)蟻群算法初期的搜索能力。

2.1.1 粒子群算法路徑預(yù)搜索原理

粒子群算法用粒子表示可行解，一個粒子表示一條路徑。一開始，粒子群初始化為一組隨機(jī)解，每個粒子有速度、位置兩個屬性。每一輪迭代中，通過計算每個粒子的路徑評價值來更新個體最優(yōu)解和全體最優(yōu)解，然后再依據(jù)這兩個變量不斷更新自己的速度和位置。通過多輪迭代，最終粒子群將聚集到最優(yōu)路徑四周，實現(xiàn)路徑預(yù)搜索任務(wù)。

假定粒子群規(guī)模為m，則第t輪迭代粒子群的位置、速度矩陣如式（6）、式（7）所示：

由式（6）、式（7）可知，第t輪迭代中粒子i在第j層?xùn)鸥衿矫娴奈恢米鴺?biāo)和速度向量分別為和。

粒子i的速度、位置更新分別如式（8）、式（9）所示：

式（8）、式（9）中，表示粒子i在第t輪迭代的個體最優(yōu)解；gbestt表示第t輪迭代的全體最優(yōu)解；w為非負(fù)的慣性因子，其值越大表示全局搜索能力越強(qiáng)；c1和c2為學(xué)習(xí)因子；r1和r2為介于( 0,1) 之間的隨機(jī)數(shù)。

個體與全體最優(yōu)解的更新分別如式（10）、式（11）所示：

式（10）、式（11）中，i=1,2,…,m，m為粒子群規(guī)模。

2.1.2 粒子群算法路徑預(yù)搜索策略

粒子群算法預(yù)搜索路徑時，仍需考慮以下幾點：第一，粒子在更新位置過程中很有可能會導(dǎo)致路徑穿越障礙物，所以在計算路徑評價值時要加入一定懲罰；第二，為了簡化算法，在預(yù)搜索過程中，暫時不考慮懸浮障礙物；第三，該算法最后并不是輸出一個最優(yōu)解，而是輸出所有粒子最終所在的路徑，以提高這些位置的初始信息素。因此對于粒子群規(guī)模和它們最后的收斂程度也有一定要求，粒子群規(guī)模按照環(huán)境規(guī)模進(jìn)行調(diào)整，粒子群最后的收斂程度通過調(diào)整參數(shù)來控制，既不能使粒子群幾乎完全收斂于最優(yōu)路徑附近，又不能使粒子群太過發(fā)散。

通過PSO 路徑預(yù)搜索，使蟻群算法在開始前，其初始信息素已有較好分布，算法初期尋徑能力極大加強(qiáng)。且由于PSO算法執(zhí)行速度快，加上路徑預(yù)搜索無需等到算法完全收斂，因此，將ACO 與PSO 相結(jié)合，算法的收斂速度反而更快，算法的復(fù)雜性也不會很高。

2.2 改進(jìn)蟻群算法全局路徑規(guī)劃

螞蟻走過的路徑點集合代表一個解，路徑越優(yōu)則螞蟻在該路徑上留下的信息素就越多。隨著迭代次數(shù)的增加，越好的路徑上累積的信息素越高，螞蟻走這條路的幾率就越大，最終在正反饋的作用下，螞蟻會逐漸收斂到最優(yōu)路徑上。

PSO-ACO 的蟻群算法部分，除了導(dǎo)入優(yōu)化后的初始信息素之外，還對傳統(tǒng)蟻群算法做出三方面改進(jìn)，具體改進(jìn)措施將在下面三小節(jié)進(jìn)行介紹。

2.2.1 狀態(tài)轉(zhuǎn)移規(guī)則改進(jìn)

螞蟻根據(jù)狀態(tài)轉(zhuǎn)移規(guī)則來選擇下一路徑點，傳統(tǒng)狀態(tài)轉(zhuǎn)移規(guī)則的思想是先確定下一步所有可行點并計算它們的轉(zhuǎn)移概率，然后根據(jù)輪盤賭原則，從所有可行點中選擇一個點作為下一路徑點?？尚悬c轉(zhuǎn)移概率的計算如式（12）所示：

式（12）中，表示螞蟻k從Pi移動到Pj的概率；τ(Pj)表示Pj上存儲的信息素濃度；η(Pi,Pj)表示Pi到Pj的啟發(fā)信息；allowk表示螞蟻k的可行點集合；α和β分別表示信息素和啟發(fā)信息在螞蟻尋徑中的重要程度，本文令α=β=1。易知，信息素和啟發(fā)信息加權(quán)乘積越大的可行點被選擇的概率就越大。

雖然這種輪盤賭的選擇方式能有效保證路徑的多樣性，但也存在著一些弊端。實驗發(fā)現(xiàn)，由于每個可行點的信息素和啟發(fā)信息加權(quán)乘積的差距沒有那么大，以至于輪盤賭只有小概率會選擇當(dāng)前最優(yōu)的可行點，導(dǎo)致算法收斂速度緩慢。為此，對狀態(tài)轉(zhuǎn)移規(guī)則做出改進(jìn)，具體如式（13）所示：

式（13）中，Pj表示下一個被訪問的路徑點；J表示根據(jù)式（12）按概率選擇出來的下一路徑點；q0為( 0,1) 之間的一個給定閾值，以此來調(diào)節(jié)算法對新路徑的探索能力，本文令q0=0.1。

改進(jìn)后，算法有更大的機(jī)會選擇信息素和啟發(fā)信息加權(quán)乘積最大的點作為下一路徑點，加快了算法的收斂速度。通過實驗驗證，在本文設(shè)定的閾值下，不會妨礙算法對新路徑的探索能力，仍保證了路徑的多樣性，不會導(dǎo)致算法易陷入局部最優(yōu)。

2.2.2 信息素更新方式改進(jìn)

信息素更新方式主要有兩種：一種是信息素全局更新，在每輪迭代結(jié)束時進(jìn)行。好路徑上的信息素將越來越高，壞路徑上的信息素將越來越低，以此提高螞蟻往好路徑上走的概率；另一種是信息素局部更新，螞蟻每走一步就對該路徑點上的信息素做揮發(fā)處理。通過降低螞蟻走過路徑上的信息素，來保證同一輪迭代中螞蟻不會集中在某條路徑上，而會嘗試走不同路徑，保證當(dāng)輪迭代中路徑的多樣性。

信息素全局更新公式如式（14）、式（15）所示：

信息素局部更新公式如式（16）所示：

式（14）～式（16）中，τ(Pt)表示Pt上的信息素濃度；ρ表示信息素?fù)]發(fā)因子；Δτk(Pt)表示螞蟻k對Pt的信息素增量；Q為常數(shù)；pathk表示螞蟻k的路徑。

在這里，兩個變量是動態(tài)變化的：

第一，信息素增量動態(tài)變化。由式（15）可知，令Δτk(Pt)隨路徑評價值變化，路徑越好，增量越大。

第二，信息素?fù)]發(fā)因子ρ也是動態(tài)變化的，如式（17）所示：

式（17）中，T表示當(dāng)前迭代次數(shù)；Tmax表示最大迭代次數(shù)。根據(jù)信息素在路徑規(guī)劃不同階段的重要程度，可以分成三部分：規(guī)劃初期，由于PSO 預(yù)搜索已經(jīng)得到了較好的初始信息素分布，此時螞蟻主要依靠初始信息素尋徑，令ρ取較小值；規(guī)劃中期，令ρ變大，加強(qiáng)算法對新路徑的探索能力，讓信息素不會堆積在個別路徑上而導(dǎo)致螞蟻只往這些路徑走；規(guī)劃后期，路徑基本探索完畢，為盡早收斂，所以ρ再取較小值。

2.2.3 加入獎懲機(jī)制

定義能夠順利到達(dá)終點的螞蟻為活螞蟻；不能順利到達(dá)終點的螞蟻為死螞蟻。對死螞蟻加入懲罰，降低其路徑上的信息素，降低后面螞蟻選擇該路徑的概率；對活螞蟻加入獎勵，提高其路徑上的信息素，增加后面螞蟻選擇該路徑的概率。

通過加入獎懲機(jī)制，可以很大程度上避免后續(xù)螞蟻陷入死區(qū)，提高每輪迭代中螞蟻的存活率，即每輪迭代中產(chǎn)生有效解的個數(shù)，這樣就更可能找到更優(yōu)的路徑去不斷刷新全局最優(yōu)解。

3 實驗結(jié)果分析

為驗證本文改進(jìn)算法在解決AUV三維路徑規(guī)劃問題上的可行性和有效性，本章選取了兩個不同規(guī)模、不同地形的海洋環(huán)境進(jìn)行實驗。通過PSO-ACO與其他智能算法的對比，分析幾種算法在本文問題上的表現(xiàn)及PSO-ACO算法的改進(jìn)效果。

3.1 實驗數(shù)據(jù)及實驗環(huán)境

從GEBCO全球海陸數(shù)據(jù)庫中選取的兩個海域分別為：一個為較小規(guī)模平緩海域，坐標(biāo)（Lng：27.512 5，Lat：123.000 0），采樣矩陣大小為50 km×50 km；另一個為較大規(guī)模復(fù)雜海域，坐標(biāo)（Lng：40.050 0，Lat：154.000 0），采樣矩陣大小為100 km×100 km。令海域最深的點作為Z=0 處，其他位置的Z值依據(jù)這個確定。起點和終點分別取在兩個對角。

實驗的硬件環(huán)境為Intel Core i7 處理器，8 GB 內(nèi)存，操作系統(tǒng)為Windows 10，算法使用Matlab實現(xiàn)。

3.2 較小規(guī)模平緩海域仿真實驗

本節(jié)的實驗環(huán)境為較小規(guī)模平緩地形，主要考察算法在簡單環(huán)境下是否能達(dá)到預(yù)期效果。

PSO-ACO算法的參數(shù)設(shè)置如表1、表2所示。其粒子群算法部分，由于實驗環(huán)境規(guī)模較小，將粒子群規(guī)模設(shè)為500，v的范圍設(shè)為[-10,10]。通過實驗不斷調(diào)整其余參數(shù)，最終選取c1=c2=2，w=0.6，最大迭代次數(shù)為100；其蟻群算法部分，同樣因為較小規(guī)模的實驗環(huán)境，將螞蟻規(guī)模設(shè)置為50。實驗發(fā)現(xiàn)ACO 總能在150次迭代之前收斂完全，因此，將150 定為最大迭代次數(shù)。通過實驗驗證，將權(quán)值α和β設(shè)為1。ρ和τ0由于算法的改進(jìn)，這里不再為一個常值。

表1 較小規(guī)模實驗PSO-ACO中粒子群算法參數(shù)設(shè)置

表2 較小規(guī)模實驗PSO-ACO中蟻群算法參數(shù)設(shè)置

將PSO-ACO 算法與蟻群算法、粒子群算法和遺傳算法進(jìn)行對比實驗，結(jié)果如圖3所示。

其具體的仿真結(jié)果數(shù)據(jù)如表3所示。表3中第二到第四列為路徑評價模型的三個指標(biāo)，F(xiàn)值為綜合下來的路徑評價值，本文通過多次實驗，確定三個評價指標(biāo)的權(quán)重如下：w1=0.5、w2=0.2 和w3=0.3。從實驗結(jié)果可以發(fā)現(xiàn)：GA算法由于交叉變異等操作，使得有些相鄰的路徑點之間水平和垂直方向變化較大，路徑崎嶇程度明顯大于其他算法，且算法運(yùn)行時間14 s 之久，它需要迭代更多次才能找到較優(yōu)解；PSO算法雖然收斂運(yùn)行時間最短，但多次實驗表明，該算法不夠穩(wěn)定，易早熟收斂、陷入局部最優(yōu)；ACO 算法全局搜索能力良好，但收斂迭代次數(shù)較多，算法運(yùn)行時間較長；本文算法規(guī)劃的路徑在三個指標(biāo)上都是較好的，且收斂迭代次數(shù)和運(yùn)行時間也有優(yōu)勢，綜合性能最佳。

圖3 較小規(guī)模實驗四種智能算法規(guī)劃的路徑

表3 較小規(guī)模實驗四種智能算法的仿真結(jié)果

為了更好地展示PSO-ACO 算法對ACO 算法的優(yōu)化效果，這里進(jìn)一步提取了兩種算法在仿真實驗中的收斂曲線，對比如圖4所示。

圖4 較小規(guī)模實驗PSO-ACO與ACO的收斂曲線

除了改進(jìn)后動態(tài)變化的部分，PSO-ACO和ACO算法的參數(shù)設(shè)置保持一致。從圖4 可以發(fā)現(xiàn)，規(guī)劃初期，PSO-ACO 算法尋徑能力明顯提高，迭代25 次就能找到第一條完整路徑，而ACO 算法要迭代58 次。這主要是因為PSO-ACO 的初始信息素得到了優(yōu)化，其粒子群算法的預(yù)搜索結(jié)果如圖5所示。

而規(guī)劃中期，PSO-ACO 算法能更頻繁地找到更優(yōu)解；規(guī)劃后期，PSO-ACO 算法也能更早收斂，且最終找到的路徑比ACO算法的更優(yōu)。綜上，PSO-ACO算法對ACO算法的改進(jìn)是可行、有效的。

3.3 較大規(guī)模復(fù)雜海域仿真實驗

圖5 較小規(guī)模實驗PSO-ACO中粒子群算法預(yù)搜索結(jié)果

為了考察上述算法是否能適應(yīng)不同環(huán)境，這里選取了規(guī)模更大、地形更復(fù)雜的海洋環(huán)境做進(jìn)一步實驗。

PSO-ACO算法的參數(shù)設(shè)置如表4、表5所示。其粒子群算法部分，由于實驗環(huán)境變大，將粒子群規(guī)模調(diào)整為1 000，v的范圍調(diào)整為[-20,20]。通過實驗驗證，其余參數(shù)保持不變；其蟻群算法部分，在較小規(guī)模實驗參數(shù)設(shè)置的基礎(chǔ)上，通過實驗發(fā)現(xiàn)ACO總能在500次迭代之前收斂完全，因此，將最大迭代次數(shù)調(diào)整為500。

表4 較大規(guī)模實驗PSO-ACO中粒子群算法參數(shù)設(shè)置

表5 較大規(guī)模實驗PSO-ACO中蟻群算法參數(shù)設(shè)置

四種算法在較大規(guī)模實驗中的規(guī)劃結(jié)果如圖6所示。

圖6 較大規(guī)模實驗四種智能算法規(guī)劃的路徑

其具體的仿真結(jié)果數(shù)據(jù)如表6所示，這里同樣通過多次實驗確定了路徑評價模型的三個權(quán)重，分別為：w1=0.5、w2=0.2 和w3=0.3。

表6 較大規(guī)模實驗四種智能算法的仿真結(jié)果

通過實驗，發(fā)現(xiàn)GA 算法局部搜索能力較弱，在較大規(guī)模復(fù)雜環(huán)境下需要430 s 才能得到較優(yōu)解，明顯慢于其他算法，且得到的路徑也不佳；PSO 算法執(zhí)行速度依然較快，但是它對初始粒子群有一定依賴性，在較大規(guī)模復(fù)雜環(huán)境中更容易陷入局部最優(yōu)，算法效果并不夠穩(wěn)定；ACO算法在復(fù)雜環(huán)境中相較于其他智能算法，其綜合表現(xiàn)良好；PSO-ACO 在較大規(guī)模復(fù)雜環(huán)境中表現(xiàn)更加突出，算法穩(wěn)定，規(guī)劃的路徑最優(yōu)且耗時最短。

PSO-ACO與ACO的收斂曲線對比如圖7所示。

圖7 較大規(guī)模實驗PSO-ACO與ACO的收斂曲線

PSO-ACO的粒子群預(yù)搜索結(jié)果如圖8所示。

圖8 較大規(guī)模實驗PSO-ACO中粒子群算法預(yù)搜索結(jié)果

由圖7、圖8可知，PSO路徑預(yù)搜索在復(fù)雜環(huán)境中依然有效。PSO-ACO 的尋徑能力、算法收斂速度等各方面都有了明顯的提高，PSO-ACO算法對ACO算法的優(yōu)化在較大規(guī)模復(fù)雜環(huán)境下依然有效，且更加突出。

4 結(jié)束語

本文研究AUV 三維路徑規(guī)劃問題，提出粒子群與改進(jìn)蟻群算法相融合的AUV路徑規(guī)劃算法。使用三維柵格模型對海洋環(huán)境建模，綜合考慮路徑長度、崎嶇性、危險性三方面來衡量路徑好壞來建立路徑評價模型。采用粒子群算法預(yù)搜索路徑優(yōu)化初始信息素，再使用改進(jìn)蟻群算法進(jìn)行全局路徑規(guī)劃。實驗結(jié)果表明，本文的改進(jìn)算法比起蟻群算法和其他智能算法具有更良好的全局搜索能力，迭代次數(shù)更少，收斂更快，耗時更短，最終得到的路徑更優(yōu)。但由于算法基于空間分層思想，在每個二維柵格平面選取一個中間路徑點，從而導(dǎo)致規(guī)劃得到的路徑拐點較多，且為折線，對AUV來說會產(chǎn)生更大的能耗。

下一步，可以對規(guī)劃出來的路徑去除冗余拐點并進(jìn)行平滑處理。其次，可以對環(huán)境模型做進(jìn)一步優(yōu)化，使其更大程度上接近真實海洋環(huán)境。