陳 茜，高軍偉，官 晟

1.青島大學(xué) 自動化學(xué)院，山東 青島266071

2.國家海洋局 第一海洋研究所，山東 青島266061

1 引言

波浪滑翔機(jī)是一種新型的自主海洋環(huán)境監(jiān)測平臺，它的出現(xiàn)對海洋環(huán)境監(jiān)測領(lǐng)域有著劃時代的意義。由于波浪滑翔機(jī)的航行動力來源于海洋波浪，海洋中無窮盡的波浪可以保證波浪滑翔機(jī)持續(xù)航行，波浪滑翔機(jī)的水面浮體上安裝有太陽能板和儲能電池，海洋中白天充足的光照可以保障波浪滑翔機(jī)上的各種儀器用電，具有超長航時、綠色無污染、自主運(yùn)動等特點[1-2]。

由于波浪滑翔機(jī)的自身結(jié)構(gòu)原理，海洋環(huán)境因素的變化對波浪滑翔機(jī)的航行速度和航行路徑有很大的影響，海洋環(huán)境復(fù)雜，暗流、暗礁、海風(fēng)巨浪等不確定因素導(dǎo)致波浪滑翔機(jī)的路徑規(guī)劃一直是一個研究的難點。針對復(fù)雜的海洋環(huán)境和波浪滑翔機(jī)的結(jié)構(gòu)特點，有必要設(shè)計有效的路徑規(guī)劃算法。常規(guī)的移動機(jī)器人路徑規(guī)劃工作環(huán)境較為簡單，動力速度可控，不適用于波浪滑翔機(jī)。在常規(guī)尋路算法的基礎(chǔ)上應(yīng)考慮到波浪滑翔機(jī)的航行速度不可控，盡可能利用海洋環(huán)境。本文以柵格法劃分海洋區(qū)域，一方面方便整合海洋環(huán)境因素，將海洋環(huán)境通過速度預(yù)測模型歸一化為動態(tài)航行速度并引入到狀態(tài)轉(zhuǎn)移規(guī)則中。另一方面，海洋廣闊平坦，單位面積區(qū)域內(nèi)海洋環(huán)境極為相似，柵格法的精度問題對算法性能影響較小。海洋環(huán)境復(fù)雜，常規(guī)蟻群算法極易陷入死鎖，引入人工探路蟻對可行節(jié)點情況提前探索，與文獻(xiàn)[3]中在轉(zhuǎn)移規(guī)則中引入上一節(jié)點數(shù)組來增加逃逸能力和文獻(xiàn)[4]中引入交叉算子來增加逃逸能力相比耗時更短。改進(jìn)后的算法不僅優(yōu)化了自身結(jié)構(gòu)，提高了收斂速度，避免了局部最優(yōu)解，更充分利用了海洋環(huán)境因素，使得波浪滑翔機(jī)能在復(fù)雜的海洋環(huán)境中快速、安全地航行到目標(biāo)點。

2 算法描述

2.1 環(huán)境建模和波浪滑翔機(jī)的數(shù)學(xué)模型

波浪滑翔機(jī)的結(jié)構(gòu)如圖1所示，分為水面浮體和水下翼板兩大部分，中間由一條4 m左右的柔性臍帶纜連接，在波浪的起伏推動下航行[5-6]。

圖1 波浪滑翔機(jī)結(jié)構(gòu)圖

路徑規(guī)劃中首先要考慮的問題是環(huán)境建模，常用的環(huán)境建模方法有柵格法、可視圖法等。本文采用柵格法對波浪滑翔機(jī)的連續(xù)航行環(huán)境進(jìn)行離散化處理，以二維數(shù)據(jù)的形式運(yùn)算更方便高效，每個柵格可以用序號和直角系坐標(biāo)表示，它們之間的換算關(guān)系如下：

在柵格環(huán)境中，波浪滑翔機(jī)可以認(rèn)為是二維平面空間中的粒子，有8種運(yùn)動方向，如圖2所示。由于實際中，波浪滑翔機(jī)的外觀尺寸較大，障礙物的面積應(yīng)該按照波浪滑翔機(jī)的半徑大小膨化，確保波浪滑翔機(jī)沿障礙物邊緣航行時不會撞到障礙物，并且障礙物面積不滿一個柵格時應(yīng)按照一個柵格計算[7]，充分保障航線的安全性。

圖2 10×10柵格建模示意圖

海洋環(huán)境中除了暗礁障礙物外，波浪、風(fēng)速、洋流等因素也應(yīng)該考慮進(jìn)柵格環(huán)境內(nèi)。

Smith等提出了線性回歸模型來預(yù)測波浪滑翔機(jī)的速度[8]。波浪滑翔機(jī)在海面航行的時候，其自身配置是恒定的。通過測量有效浪高、波峰周期、淺層流、表層流、風(fēng)速和方向等海洋環(huán)境因素，線性權(quán)衡6個海洋環(huán)境因素，推導(dǎo)了一個波浪滑翔機(jī)速度的預(yù)測模型[9]。波浪滑翔機(jī)速度預(yù)測模型如下：

其中，ysog是波浪滑翔機(jī)的對地速度；xwht是有效波高；xwpp是波峰周期；xwdir是波浪滑翔機(jī)航向與波向的差值；xwnd是風(fēng)速在航向軸向的分量；xadcp是表層流速在航向軸向的分量；xhfr是淺層流速在航向軸向的分量[9]。因?qū)嶋H中采集到的海洋環(huán)境數(shù)據(jù)有限，僅考慮影響速度的主要因素，將速度預(yù)測模型簡化如下：

將所有海洋環(huán)境因素歸一化為預(yù)測速度來改進(jìn)柵格法，除去黑色障礙物柵格，對白色自由柵格進(jìn)行不同程度的藍(lán)色填充來表示歸一化的波浪滑翔機(jī)預(yù)測速度，從而使其應(yīng)用于波浪滑翔機(jī)進(jìn)行海洋環(huán)境建模。海洋環(huán)境柵格建模如圖3所示。

2.2 常規(guī)蟻群算法簡介和相關(guān)改進(jìn)

蟻群算法是1994年Dorigo提出的一種相對成熟的群體智能優(yōu)化算法，通過模擬自然界螞蟻覓食的行為來尋求最優(yōu)解。根據(jù)外界環(huán)境的變化，蟻群算法可以動態(tài)做出反應(yīng)，且魯棒性能好，被廣泛應(yīng)用于旅行商問題（Traveling Salesman Problem，TSP）、車輛調(diào)度問題、網(wǎng)絡(luò)路由問題等實際問題中[10]。

圖3 海洋環(huán)境速度預(yù)測柵格建模

常規(guī)蟻群算法的節(jié)點選擇方式是根據(jù)節(jié)點之間的信息素濃度和啟發(fā)信息進(jìn)行概率選擇的，在t時刻，螞蟻k從節(jié)點Xi轉(zhuǎn)移到節(jié)點Xj的轉(zhuǎn)移概率公式如下：

其中，τij(t)為t時刻節(jié)點i到節(jié)點j的信息素濃度，α表示信息素濃度的相對重要程度；ηij(t)為t時刻節(jié)點i到節(jié)點j的實際距離的倒數(shù)，β表示啟發(fā)性因子的相對重要程度[11]。

常規(guī)蟻群算法存在收斂速度較慢，搜索范圍小且容易陷入局部最優(yōu)解等缺點。為彌補(bǔ)常規(guī)蟻群算法的缺陷，一方面，研究者通過修改蟻群算法自身參數(shù)結(jié)構(gòu)來避免局部最優(yōu)解，例如修改節(jié)點轉(zhuǎn)移規(guī)則或信息素更新策略；另一方面，研究者通過蟻群算法和其他智能算法相融合來提高收斂速度，避免局部最優(yōu)解，例如遺傳蟻群算法、人工免疫蟻群算法、人工勢場蟻群算法等[12-13]。

3 改進(jìn)蟻群算法

3.1 改進(jìn)啟發(fā)函數(shù)

海洋環(huán)境十分復(fù)雜，暗礁叢生，針對復(fù)雜航行環(huán)境，改進(jìn)算法引入了障礙物復(fù)雜度mark的概念，即在一定區(qū)域范圍內(nèi)，障礙物柵格的分布情況。在螞蟻進(jìn)行路徑搜索時，搜索蟻從起始點S出發(fā)，以節(jié)點間的信息素和啟發(fā)信息搜索前進(jìn)，在進(jìn)行下一節(jié)點選擇時，派出探路蟻，為搜索蟻可能前進(jìn)的方向探索障礙物分布情況，并對此方向的障礙物分布情況進(jìn)行標(biāo)準(zhǔn)評分。當(dāng)此方向的評分較高時，說明該方向海況良好，障礙物分布較少；當(dāng)此方向評分較低時，說明障礙物分布復(fù)雜，海況情況復(fù)雜，在此方向繼續(xù)搜索前進(jìn)的話，可能需要耗費(fèi)更多時間，或使算法陷入死鎖[14]。探路蟻可以讓算法規(guī)避易死鎖的節(jié)點，既節(jié)約了死鎖后逃逸需要的時間，又保證了算法收斂時的穩(wěn)定性，提高了算法收斂速度。

當(dāng)搜索蟻進(jìn)行下一節(jié)點選擇時，假定搜索蟻Mk的當(dāng)前位置為Lk，設(shè)Lp1為搜索蟻Mk的一個可行柵格，則在Lp1柵格放置一只探路蟻。

第一種情況：當(dāng)柵格Lp1不在邊界處時，則探路蟻沿向量LkLp1的方向移動一個柵格，到達(dá)柵格Lr1，探路蟻在以Lr1柵格為中心的（3×3）方形區(qū)域進(jìn)行障礙物復(fù)雜情況探索，計算該區(qū)域的障礙物復(fù)雜度。如圖4所示，紅色圓形為搜索蟻Mk的位置，它的下一可行節(jié)點有Lp1柵格、Lp2柵格等，則對應(yīng)的紅色三角形所在柵格即為對應(yīng)可行節(jié)點探路蟻的位置，對紅色虛線范圍內(nèi)的（3×3）柵格進(jìn)行障礙物分布探索。

圖4 障礙物探索位置示意圖

第二種情況：Lp1柵格位于邊界處，如圖5所示，紅色圓點為搜索蟻Mk的位置，Lp1是它的下一可行點，但Lp1位于邊界位置，不存在沿LkLp1方向的下一節(jié)點，則探路蟻的位置為紅色三角形所在的柵格，探路蟻以紅色三角形柵格為中心進(jìn)行障礙物分布情況探索。

圖5 邊界情況下障礙物探索位置示意圖

第三種情況：若探路蟻最終的位置柵格在邊界的4個角落柵格（柵格序號為1、20、380、400），則該可行節(jié)點的障礙物復(fù)雜度置0。

綜上，每個可行節(jié)點gi的障礙物復(fù)雜度mark(gi)已求出，將距離啟發(fā)信息和障礙物復(fù)雜度線性權(quán)衡，最終得出該可行節(jié)點的綜合評分S(gi)如下：

其中，Dis(gi)是當(dāng)前節(jié)點gi到目標(biāo)節(jié)點的距離，mark(gi)為節(jié)點gi對應(yīng)的障礙物柵格的個數(shù)。因此，新的啟發(fā)式函數(shù)如下：

復(fù)雜障礙物的存在，尤其是U型等陷阱類障礙物分布，不僅對算法的性能造成了影響，更對航線的安全性做出了考驗，人工探路蟻的提前規(guī)避作用，在一定程度上提高了航線的安全性。

3.2 改進(jìn)信息素更新策略

常規(guī)蟻群算法只在迭代時才更新路徑上的信息素，這種更新方式不僅影響了算法的收斂速度，還較容易出現(xiàn)局部最優(yōu)解。為避免上述的缺點，采用局部信息素更新和最優(yōu)最差獎懲機(jī)制迭代信息素更新來改進(jìn)蟻群算法的信息素更新策略[15]。

（1）局部信息素更新

每一代的每一只螞蟻在經(jīng)過某個節(jié)點后都對該節(jié)點的信息素進(jìn)行更新，更新方式如下：

其中，ρ為信息素?fù)]發(fā)因數(shù)，在[0，1]范圍內(nèi)可調(diào)；τ0為信息素初始濃度；τij為節(jié)點i到節(jié)點j路徑上的信息素。螞蟻k經(jīng)過某節(jié)點后，隨時間增加，路徑上的信息素?fù)]發(fā)了一部分，保證了信息素不會殘留太多而湮沒啟發(fā)信息，增加了螞蟻搜索未經(jīng)過節(jié)點的概率，從而避免了局部最優(yōu)解[16-17]。

（2）最優(yōu)最差獎懲機(jī)制全局信息素更新

t代k只螞蟻都完成了路徑搜索，更新路徑的信息素濃度，選擇t代所有螞蟻經(jīng)過路徑中最長的一條路徑Lworst和最短的一條路徑Lbest，對該路徑上的信息素濃度進(jìn)行更新[18]。

如式（7）、（8）、（9）所示，Δτkij(t)為t代螞蟻k在路徑(i,j)上遺留的信息素。

3.3 動態(tài)航行速度

由于波浪滑翔機(jī)的航行動力全部來源于海洋環(huán)境，其中主要是海洋波浪的起伏帶動了波浪滑翔機(jī)的航行，因此，與普通機(jī)器人路徑規(guī)劃只考慮路徑長度不同，波浪滑翔機(jī)還要考慮航行時間。海洋環(huán)境隨所處區(qū)域位置和時間變化而變化，是一個動態(tài)參量。在環(huán)境建模之中，已經(jīng)將環(huán)境因素通過速度預(yù)測模型歸一化為速度，為方便運(yùn)算，本文以相鄰柵格之間為劃分單位，即柵格i到相鄰柵格j的速度為Vij(t)。在螞蟻進(jìn)行下一節(jié)點轉(zhuǎn)移時，應(yīng)考慮到當(dāng)前時間當(dāng)前節(jié)點與下一節(jié)點之間的速度，若路徑長度相同，應(yīng)先考慮速度快的節(jié)點。

綜上，引入人工探路蟻來改進(jìn)啟發(fā)函數(shù)，障礙物復(fù)雜度和距離啟發(fā)信息共同作用形成新的啟發(fā)函數(shù)Hj(t)；整合海洋環(huán)境因素，利用預(yù)測速度模型求出波浪滑翔機(jī)在當(dāng)前時間地點下的航行速度Vij(t)；利用局部信息素更新和最優(yōu)最差獎懲機(jī)制迭代信息素更新改進(jìn)蟻群算法的信息素更新策略，得出新的路徑上的信息素濃度τij(t)。新的節(jié)點狀態(tài)轉(zhuǎn)移規(guī)則如下：

3.4 改進(jìn)蟻群算法的流程

步驟1初始化海洋環(huán)境參數(shù)，包括波浪的有效波高、地下水流等環(huán)境因素；初始化蟻群算法的參數(shù)，包括螞蟻個數(shù)m、迭代次數(shù)k、初始時刻路徑上的信息素濃度、信息素強(qiáng)度Q、信息素?fù)]發(fā)系數(shù)等參數(shù)。

步驟2柵格建模，利用柵格法將海洋環(huán)境離散處理，并根據(jù)海洋環(huán)境數(shù)據(jù)，利用預(yù)測速度模型，將海洋環(huán)境歸一化為動態(tài)速度。

步驟3所有螞蟻開始路徑選擇，依據(jù)節(jié)點狀態(tài)轉(zhuǎn)移規(guī)則選擇下一節(jié)點，并將當(dāng)前節(jié)點加入到禁忌表tabuk中。

步驟4判斷螞蟻是否到達(dá)終點，若某只螞蟻到達(dá)終點，則局部信息素更新；某代所有螞蟻完成從起點到終點的搜索后，選出最優(yōu)局部路徑和最差局部路徑，全局更新路徑上的信息素濃度。

步驟5判斷是否達(dá)到最大迭代次數(shù)，若沒有繼續(xù)迭代循環(huán)，達(dá)到最大迭代次數(shù)后，輸出時間和路徑長度最優(yōu)的路線。

4 仿真驗證

采用Matlab2014a編程平臺進(jìn)行實驗仿真，仿真環(huán)境為20 km×20 km的海洋區(qū)域，障礙物分布已知。算法中的參數(shù)初始化為螞蟻個數(shù)M=50，最大迭代次數(shù)K=80，其他參數(shù)根據(jù)實際仿真效果動態(tài)調(diào)整[19]。

仿真實驗結(jié)果如下：

由于改進(jìn)蟻群算法引入了人工探路蟻，提前對無效或容易使路徑陷入死鎖的節(jié)點進(jìn)行屏蔽，有效提高了算法的收斂速度。圖6為改進(jìn)算法和常規(guī)算法的收斂曲線對比，圖7為改進(jìn)算法和常規(guī)算法的仿真路線對比，可以看出，改進(jìn)算法在第15代左右就收斂并趨于穩(wěn)定，較常規(guī)蟻群算法的25代左右趨于穩(wěn)定有明顯的提升。

圖6 改進(jìn)算法和常規(guī)算法的收斂曲線對比

圖7 改進(jìn)算法和常規(guī)算法仿真路線對比

圖8 常規(guī)算法和改進(jìn)算法仿真路線對比（增加障礙物）

（1）更換仿真環(huán)境，增加障礙物分布的復(fù)雜情況。在新的靜態(tài)環(huán)境中進(jìn)行仿真實驗，如圖8所示，在圖7仿真環(huán)境的基礎(chǔ)上增加了障礙物的復(fù)雜情況。常規(guī)蟻群算法在遇到障礙物阻擋前進(jìn)方向時，繞障礙物移動，沒有提前探索到障礙物，這增加了路徑的長度[20]。而改進(jìn)蟻群算法提前探索到了障礙物的分布，提前舍棄該節(jié)點躲避了障礙物，相較于常規(guī)蟻群，路徑長度較短，安全性更高。

（2）由于單次算法運(yùn)行結(jié)果有偶然性，為驗證改進(jìn)后算法的有效性，選取兩種新的仿真環(huán)境，多次運(yùn)行取平均值。另外，由于節(jié)點之間的航行速度不同，且在路徑節(jié)點選擇時已經(jīng)將速度考慮進(jìn)去，航行時間和航行路徑長度應(yīng)該都是衡量算法優(yōu)劣的性能指標(biāo)。如表1所示，在改進(jìn)算法和常規(guī)算法規(guī)劃出來的路徑長度相近時，改進(jìn)算法的航行時間更短。改進(jìn)蟻群算法的總體性能較常規(guī)蟻群算法有了明顯的提升。

5 結(jié)論

本文針對波浪滑翔機(jī)的路徑規(guī)劃問題，提出一種改進(jìn)的蟻群算法。

表1 改進(jìn)蟻群算法和常規(guī)蟻群算法的性能對比

（1）考慮到海洋環(huán)境障礙物分布復(fù)雜，引入了人工探路蟻，對可行節(jié)點方向的障礙物分布情況提前探索，充分避免了算法易陷入死鎖的問題，減少了收斂振蕩，提高了收斂速度，也提高了航線的安全性。

（2）針對波浪滑翔機(jī)的動力特點，將海洋環(huán)境因素依據(jù)波浪滑翔機(jī)環(huán)境預(yù)測模型歸一化為預(yù)測速度，并將此因素加入蟻群算法的狀態(tài)轉(zhuǎn)移規(guī)則中，在考慮航線長度的同時兼顧航行速度。

（3）針對蟻群算法信息素更新策略的缺點，增加了局部信息素更新方式，利用最優(yōu)最差獎懲機(jī)制改進(jìn)了迭代信息素更新策略，增加了螞蟻的尋優(yōu)能力，增大螞蟻搜索范圍，避免了局部最優(yōu)解。

經(jīng)仿真驗證，改進(jìn)后的蟻群算法完全勝任波浪滑翔機(jī)的路徑規(guī)劃任務(wù)，即使在復(fù)雜的海洋環(huán)境中，也可以快速地規(guī)劃出一條距離短、安全性高的航線。