謝新連，王余寬,2，何 傲，潘 偉，許小衛(wèi)

(1. 大連海事大學(xué) 綜合運(yùn)輸研究所，遼寧 大連 116026； 2. 武漢理工大學(xué) 航運(yùn)學(xué)院，湖北 武漢 430063)

0 引 言

人工智能技術(shù)日益進(jìn)步，船舶業(yè)也向著智能化方向發(fā)展，2016年中國船級社頒布的《智能船舶規(guī)范》中將航線規(guī)劃技術(shù)列為船舶智能化的一項(xiàng)重要途徑。為船舶規(guī)劃航線，尤其當(dāng)面臨海上搜救、海上緝私等對時(shí)間要求緊迫的任務(wù)時(shí)，為巡邏船或執(zhí)法船等規(guī)劃出航行耗時(shí)短的路徑是必要的。另外，海洋氣象環(huán)境會造成船舶失速，此時(shí)考慮海洋氣象環(huán)境的影響智能規(guī)劃航行路徑，則更能提高船舶航行效率，提升船舶智能化水平。

目前，國內(nèi)外已有大量的船舶路徑規(guī)劃研究，主要集中于不考慮海洋氣象環(huán)境的研究上。蔣美芝等[1]考慮海上礙航區(qū)和船舶經(jīng)濟(jì)效益設(shè)計(jì)船舶航線，基于柵格環(huán)境建模和蟻群算法求解路徑；SONG Rui等[2]針對A*算法求解無人水面艇避障路徑不光滑的問題，對A*算法進(jìn)行改進(jìn)并求解獲取了平滑程度較高的路徑；謝新連等[3]將航行經(jīng)驗(yàn)轉(zhuǎn)化為船舶航行規(guī)則，利用強(qiáng)化學(xué)習(xí)和A*算法為受限水域內(nèi)船舶規(guī)劃全局避碰航線；S.M.LEE等[4]考慮船舶排放法規(guī)的約束，以航速優(yōu)化為目標(biāo)求解不同航段的航法；XIE Lei等[5]設(shè)計(jì)了一種全局多方向的A*算法，對海上風(fēng)電場內(nèi)工作的船舶規(guī)劃航線；LIU Yuanchang等[6]應(yīng)用改進(jìn)隨機(jī)樹算法，以距離最短為目標(biāo)為船舶設(shè)計(jì)了平滑性較大的航線；Y. SINGH等[7]考慮了動態(tài)礙航物和水流對船舶航行的影響，設(shè)計(jì)了一種改進(jìn)A*算法求解船舶避障路徑；H.KIM等[8]針對無人水面艇在風(fēng)浪流環(huán)境中避障航行設(shè)計(jì)航線，其獲取的路徑轉(zhuǎn)向點(diǎn)較多不適用于轉(zhuǎn)向慢或回轉(zhuǎn)半徑大的船舶。

多數(shù)研究未考慮海洋氣象環(huán)境或僅考慮海流對船舶航行的影響，綜合考慮風(fēng)、波浪及水流影響對船舶路徑進(jìn)行規(guī)劃的研究尚少。但實(shí)際上，船舶受到風(fēng)、波浪和水流的干擾后，會出現(xiàn)明顯的失速現(xiàn)象，因此，為船舶規(guī)劃能夠避障航行且耗時(shí)最短的航線時(shí)，考慮風(fēng)、波浪及水流的影響是必要的。

筆者從3個(gè)方面設(shè)計(jì)船舶路徑優(yōu)化方案：①分析海洋環(huán)境對船舶航行帶來的干擾，設(shè)計(jì)了考慮風(fēng)、波浪、水流及安全水深影響的路徑規(guī)劃方案；②為提高算法收斂精度和效率，設(shè)計(jì)了交叉變異算子自適應(yīng)的改進(jìn)遺傳算法；③為優(yōu)化算法運(yùn)行耗時(shí)，對改進(jìn)的遺傳算法設(shè)計(jì)主從并行化模型實(shí)現(xiàn)模式。通過方案設(shè)計(jì)和算法優(yōu)化求解，以提高船舶路徑智能規(guī)劃的有效性。

1 風(fēng)浪流影響

1.1 風(fēng)浪流干擾力

船舶航行時(shí)，風(fēng)、波浪和水流作用于船體產(chǎn)生阻力，使得船速和航向發(fā)生改變。通常，將船舶所受海洋環(huán)境阻力分為風(fēng)力、波浪力和水流作用力，由于實(shí)際海況中風(fēng)和波浪存在的不確定性[9]，船舶受力公式一般通過模擬試驗(yàn)獲得，即在風(fēng)洞和水池條件下模擬風(fēng)浪流環(huán)境，計(jì)算船舶航行過程受到風(fēng)浪流的干擾力。

用τwind和τcurrent分別表示船舶所受風(fēng)和水流的干擾力矢量，二者計(jì)算方法為式(1)[10]～式(2)[11]：

(1)

(2)

式中：ρa(bǔ)和ρw分別為空氣和海水密度;AFw和ALw分別為水面以上風(fēng)的正投影和側(cè)投影面積;CXw和CYw分別為X方向和Y方向的風(fēng)力負(fù)荷系數(shù);γrw為風(fēng)向與船艏的夾角;Vrw為風(fēng)對船舶的相對速度;AFc和ALc分別為水面以下水流的正投影和側(cè)投影面積;CXc和CYc分別為水流作用力沿X方向和Y方向的負(fù)荷系數(shù);γrc為水流向與船艏的夾角;Vrc為水流對船舶的相對速度。

實(shí)際應(yīng)用中計(jì)算船舶所受X方向和Y方向的風(fēng)力合力和水流合力，結(jié)合式(1)和式(2)計(jì)算得式(3)：

(3)

波浪可分為規(guī)則波和不規(guī)則波，后者存在較大不確定性和計(jì)算復(fù)雜性[12]，模型僅考慮規(guī)則波產(chǎn)生的干擾力。規(guī)則波干擾力計(jì)算方法中較為常用的是Daidola基于水池船模試驗(yàn)提出的計(jì)算方法如式(4):

(4)

式中：ρa(bǔ)為海水密度;ls為船長；κ2為波浪振幅;γw為波向角;λw為波長;Cw為波浪力負(fù)荷系數(shù)。

1.2 船舶失速

(5)

船舶受海洋氣象環(huán)境影響導(dǎo)致航速變化如圖1，結(jié)合速度矢量運(yùn)算得到船舶受環(huán)境影響后的航速v′，用式(6)表示為：

圖1 船舶受風(fēng)浪流影響示意

(6)

2 路徑規(guī)劃方案設(shè)計(jì)

2.1 方案假設(shè)

船舶路徑規(guī)劃的目標(biāo)是在保證船舶航行安全的前提下規(guī)劃出一條滿足航行要求(如航行距離最短、航行耗時(shí)最短等)的路徑。結(jié)合船舶駕駛操作要求，路徑規(guī)劃應(yīng)考慮船舶吃水深及礙航區(qū)邊界是否規(guī)則等因素。另外考慮到海洋環(huán)境的復(fù)雜性以及船舶本身的特性，建立以下假設(shè)：①水域內(nèi)風(fēng)和波浪分別為恒風(fēng)和規(guī)則波；②風(fēng)浪強(qiáng)度在船舶耐受范圍內(nèi)；③視水域?yàn)槎S平面環(huán)境，船舶運(yùn)動忽略高度條件；④船舶在路徑轉(zhuǎn)向點(diǎn)更改航速不占用時(shí)間。

2.2 安全航行水域提取

通常，航行水域內(nèi)礙航區(qū)邊界并不規(guī)則，采用Graham凸包算法[13]將原始礙航環(huán)境處理為凸多邊形，頂點(diǎn)的數(shù)量取決于地圖的比例和大小。另外，為保證船舶不與航行空間內(nèi)的任何障礙物相撞或過于接近，也不會受水深影響發(fā)生擱淺，將礙航區(qū)的邊界向外延伸hkm，擴(kuò)展后覆蓋的水域?yàn)楹叫斜Ｗo(hù)區(qū)，如圖2，擴(kuò)展區(qū)以外的水域?yàn)榘踩颍拱惴ê屯庋硬僮鬟^程如式(7):

圖2 擴(kuò)展保護(hù)區(qū)示意

(7)

式中:Wk為水域中第k個(gè)礙航區(qū);hmin為考慮安全水深的影響需要外延至少hmin才可獲取安全水域;Sk為第k個(gè)擴(kuò)展保護(hù)區(qū);dr為所有擴(kuò)展保護(hù)區(qū)組成的頂點(diǎn)集合中的第r個(gè)頂點(diǎn)。

2.3 航行網(wǎng)絡(luò)圖構(gòu)建

2.3.1 構(gòu)建Maklink圖

在建立航行水域礙航區(qū)凸多邊形模型的基礎(chǔ)上，應(yīng)用Maklink圖論進(jìn)行航行環(huán)境建模，其步驟為：

步驟1障礙物頂點(diǎn)集合D內(nèi)所有點(diǎn)兩兩相連，所有連線從短到長排序并組成候選鏈接線集合Φ。

步驟2選擇Φ中的最短線段Φmin。

步驟3判斷該線段與障礙區(qū)S是否相交，如果相交則轉(zhuǎn)向步驟8，如果未相交則轉(zhuǎn)向步驟4。

步驟4判斷該線段與相應(yīng)凸多邊形頂點(diǎn)產(chǎn)生的兩個(gè)外角是否都≤180°，若是則轉(zhuǎn)向步驟5，若否則轉(zhuǎn)向步驟6。

步驟5刪除該頂點(diǎn)的其他鏈接線，轉(zhuǎn)向步驟9。

步驟6檢查該頂點(diǎn)的其他鏈接線是否都≤180°，若是則轉(zhuǎn)向步驟7；若否則轉(zhuǎn)向步驟9。

步驟7刪除該頂點(diǎn)的其他候選鏈接線，轉(zhuǎn)向步驟9。

步驟8從集合Φ中刪除該線段。

步驟9判斷是否遍歷Φ內(nèi)所有線段，若是則結(jié)束，集合Φ內(nèi)剩余的線段集合則為生成的Maklink線；若否則轉(zhuǎn)向步驟2。

經(jīng)過以上步驟得到礙航區(qū)環(huán)境，圖3給出2個(gè)示例，Maklink線集合M={Mj,j=1,2,…,J}。

圖3 航行網(wǎng)絡(luò)

2.3.2 路徑轉(zhuǎn)向點(diǎn)表達(dá)

(8)

(9)

式中：θj∈[0,1],j=1,2,…,J。

由式(9)可知，θj任取一個(gè)值則相應(yīng)產(chǎn)生一個(gè)路徑點(diǎn)。因此，即使Maklink線是有限的，但路徑可選擇的轉(zhuǎn)向點(diǎn)是無限的，所以需要建立最優(yōu)化數(shù)學(xué)模型以求解最優(yōu)路徑點(diǎn)。

2.4 初始路徑規(guī)劃

在存在J條Maklink線的航行網(wǎng)絡(luò)圖中，每條Maklink線上的點(diǎn)均為候選轉(zhuǎn)向點(diǎn)，利用 Dijkstra 算法在Maklink圖上生成由點(diǎn)序列集合P={pi,i=1,2,…,I}組成的一條初始船舶避碰路徑，I表示初始路徑點(diǎn)共在I條Maklink線上產(chǎn)生，每個(gè)點(diǎn)均為其所在Maklink線的中點(diǎn)，此時(shí)θj取值為0.5。集合P內(nèi)點(diǎn)的個(gè)數(shù)I小于Maklink線的數(shù)量J，基于集合P再求解最優(yōu)路徑將提升求解效率，用式(10)表示Dijkstra 算法的求解操作：

P={pi,i=1,2,…,I}=Ψ(M,θj),θj=0.5,j=1,2,…,J

(10)

集合P中p1為路徑起始點(diǎn)，pI為目的點(diǎn)，P′={pi,i=2,…,I-1}為所有轉(zhuǎn)向點(diǎn)集合，各轉(zhuǎn)向點(diǎn)順序連接組成的航段集合用L={Lg，g=1,2,…,G}表示。結(jié)合式(10)和式(9)得初始路徑點(diǎn)序列的坐標(biāo)，用式(11)表示:

(11)

式中：i=1,2,…,I。

2.5 路徑優(yōu)化模型

由式(9)和式(10)知(θ1,θ2,…,θI)可以用來映射一組路徑解的位置信息，基于此，考慮風(fēng)、波浪、水流對船舶航行的影響時(shí)，船舶在不同航段的航速發(fā)生改變，此時(shí)滿足路徑避障且航行耗時(shí)最優(yōu)要求的模型目標(biāo)函數(shù)可表示為式(12)：

(12)

式中：Λθ={θi,θi∈[0,1],i=1,2,…,I}。

1)f1(Lg)為無避碰規(guī)則路徑耗時(shí)代價(jià)目標(biāo)函數(shù)。風(fēng)、波浪及水流作用下船舶速度不同于靜水航速，船舶于各個(gè)航段上的耗時(shí)發(fā)生改變，設(shè)計(jì)船舶于航段Lg航行的耗時(shí)代價(jià)函數(shù)為式(13)：

(13)

2)f2(Lg)為船舶路徑碰撞代價(jià)目標(biāo)函數(shù)如式(14)：

(14)

式中：Sk為規(guī)劃海域中的第k個(gè)礙航區(qū)；Lg∩Sk≠?為路徑Lg與Sk有交點(diǎn)，此時(shí)碰撞代價(jià)無窮大，結(jié)合目標(biāo)函數(shù)式(12)相當(dāng)于此航段耗時(shí)代價(jià)無窮大；若無交點(diǎn)則不會發(fā)生碰撞，此時(shí)碰撞代價(jià)取值為1，相當(dāng)于此航段產(chǎn)生的碰撞代價(jià)對航段耗時(shí)不產(chǎn)生影響。

3 算法設(shè)計(jì)

船舶路徑規(guī)劃模型中，每組路徑解對應(yīng)一組實(shí)數(shù)解，求解過程即是在其對應(yīng)的數(shù)值空間上尋找最優(yōu)值的過程。遺傳算法是一種通過模仿自然選擇和自然遺傳學(xué)機(jī)理而發(fā)展起來的隨機(jī)化搜索算法，其實(shí)數(shù)編碼方式也能夠較好地滿足在數(shù)值空間上不斷尋優(yōu)的目標(biāo)。標(biāo)準(zhǔn)遺傳算法存在一個(gè)缺陷，即迭代尋優(yōu)過程中不能有效地將上一代的優(yōu)良信息保留至下一代，為此設(shè)計(jì)了交叉變異概率自適應(yīng)的遺傳算法，并采取并行式機(jī)制實(shí)現(xiàn)遺傳算法，以助于提升算法的求解效率?；诟倪M(jìn)遺傳算法優(yōu)化路徑的算法流程圖如圖4。

圖4 基于并行自適應(yīng)遺傳算法的路徑優(yōu)化流程

3.1 基于初始解的遺傳算法

路徑規(guī)劃模型求解過程中，標(biāo)準(zhǔn)遺傳算法是隨機(jī)生成初始字符串種群，其缺陷是產(chǎn)生大量不可行種群導(dǎo)致種群搜索效率較低。因此，將Dijkstra算法規(guī)劃的結(jié)果作為遺傳算法的初始種群，使所有種群均在可行解的基礎(chǔ)上進(jìn)化，以此提升求解效率。

3.1.1 遺傳編碼

圖5 染色體結(jié)構(gòu)

(15)

3.1.2 評估適應(yīng)度

適應(yīng)度函數(shù)是從目標(biāo)函數(shù)中推導(dǎo)出來的，目標(biāo)函數(shù)是進(jìn)行適當(dāng)映射的必要條件，在每一代新生種群上評估所有個(gè)體的適應(yīng)度，適應(yīng)度函數(shù)約為船舶從出發(fā)點(diǎn)到目的地航行耗時(shí)的倒數(shù)，如式(16)：

(16)

3.2 算子選擇概率自適應(yīng)

遺傳算法在迭代尋優(yōu)時(shí)，染色體之間按照一定概率發(fā)生交叉變異來生成新解，一般設(shè)置染色體發(fā)生交叉和變異的概率為固定值，其缺陷是忽視了染色體之間信息優(yōu)劣差異，使優(yōu)勢信息和劣勢信息以相同概率進(jìn)入到下一代中。因此，設(shè)計(jì)了交叉和變異概率自適應(yīng)調(diào)整辦法，概率自適應(yīng)規(guī)則為當(dāng)該個(gè)體適應(yīng)度值小于均值時(shí)，個(gè)體交叉概率α和變異概率β取較大值，否則按照一定方式求取概率值，這種概率選擇方式提高了優(yōu)勢信息的進(jìn)化概率，有助于提升求解質(zhì)量和效率。概率自適應(yīng)規(guī)則具體如式(17)和式(18)：

(17)

(18)

3.3 AGA算法并行化

算法并行化指利用計(jì)算機(jī)的不同核心單元同時(shí)計(jì)算程序的各部分，以此減少程序運(yùn)行時(shí)間。由于遺傳算法一次迭代過程中每個(gè)染色體的評估都是獨(dú)立的，所以每一代染色體的評估都適合并行化[14]。并行式自適應(yīng)遺傳算法(parallel adaptive genetic algorithm，PAGA)將各個(gè)染色體的適應(yīng)度評估分配到計(jì)算機(jī)的各個(gè)核心上進(jìn)行計(jì)算，這種并行模式也被稱為主從模型并行機(jī)制。

主從模型并行機(jī)制的理想加速比計(jì)算如式(19)：

(19)

式中：γ為并行部分的核心單元數(shù)量；ε為串行運(yùn)算時(shí)適應(yīng)度值計(jì)算一次在程序迭代一次過程中的耗時(shí)占比。

4 算例仿真

4.1 仿真結(jié)果

為驗(yàn)證路徑規(guī)劃方案的有效性，在運(yùn)行內(nèi)存為8GB且CPU為Intel core i5-8265u的計(jì)算機(jī)上仿真。仿真環(huán)境以圖3(a)為例，包含5個(gè)障礙區(qū)，設(shè)置水域內(nèi)風(fēng)級為5級，水流速為2 m/s，風(fēng)、波浪和水流方向?yàn)楸逼珫|45°，靜水船速為10 m/s，環(huán)境負(fù)荷參數(shù)參照文獻(xiàn)[8]、文獻(xiàn)[10]設(shè)置如表1。

表1 算例仿真環(huán)境負(fù)荷參數(shù)

采用并行式自適應(yīng)遺傳算法為船舶規(guī)劃路徑，如圖6可以看出，未對水域內(nèi)礙航區(qū)進(jìn)行處理時(shí)，規(guī)劃的路徑穿越可能存在的淺水區(qū)等不安全水域，船舶按照此路徑航行可能發(fā)生擱淺、觸礁以及與礙航區(qū)邊界發(fā)生碰撞的情況。經(jīng)過對水域內(nèi)礙航區(qū)適當(dāng)處理后獲得安全航行水域，此時(shí)規(guī)劃的路徑完全避開了可能發(fā)生擱淺等危險(xiǎn)的水域。

圖6 安全航行水域規(guī)劃路徑

圖7中給出考慮與未考慮風(fēng)浪流干擾情況下規(guī)劃的路徑?？紤]風(fēng)浪流后路徑航行里程有所增加，但航行耗時(shí)從378.35 s下降到354.80 s，說明優(yōu)化后的路徑一定程度上規(guī)避了環(huán)境帶來的干擾。另外，針對考慮風(fēng)浪流與未考慮風(fēng)浪流兩種情況下，采用可視圖法、蟻群算法(ant clony optimization，ACO)、標(biāo)準(zhǔn)遺傳算法(genetic algorithm，GA)和自適應(yīng)遺傳算法(adaptive genetic algorithm，AGA)分別求解，路徑如圖8，航程耗時(shí)見表2。

圖7 風(fēng)浪流干擾下規(guī)劃路徑對比

圖8 考慮風(fēng)浪流后不同算法規(guī)劃路徑

考慮風(fēng)浪流后，利用可視圖法規(guī)劃出的路徑航程與未考慮風(fēng)浪流求解結(jié)果均為2 425.2 m，結(jié)合路徑結(jié)果對比后發(fā)現(xiàn)與未考慮風(fēng)浪流時(shí)為同一條路徑，分析其原因在于可視圖法不同于其它3種智能優(yōu)化算法，可視圖法的可行路徑解集由安全水域的邊界點(diǎn)之間相互連接組成，可供選擇的路徑有限，而海洋環(huán)境的影響有時(shí)不足以使船舶路徑在有限的可行解中發(fā)生改變。

由表2知，相較于未考慮風(fēng)浪流，考慮風(fēng)浪流后蟻群算法、標(biāo)準(zhǔn)遺傳算法和自適應(yīng)遺傳算法求解結(jié)果在航程上有所增加，但航行耗時(shí)分別減少了5.25%、6.19%和6.22%，這說明考慮風(fēng)浪流的影響后規(guī)劃出的路徑可以幫助船舶縮短航行耗時(shí)。另外，自適應(yīng)遺傳算法規(guī)劃路徑航行耗時(shí)為354.80 s，在4種算法中求解結(jié)果最優(yōu)，說明了文中對標(biāo)準(zhǔn)遺傳算法進(jìn)行的交叉變異算子自適應(yīng)優(yōu)化是有效的。

表2 不同方法求解結(jié)果

4.2 算法耗時(shí)分析

在考慮風(fēng)浪流與未考慮風(fēng)浪流兩種情況下，保證相同求解質(zhì)量時(shí)，分析不同算法的計(jì)算效率，并增加了圖3(b)的環(huán)境進(jìn)行實(shí)驗(yàn)，該環(huán)境下實(shí)驗(yàn)結(jié)果如圖9。另外，PAGA算法采用八核心并行機(jī)制實(shí)現(xiàn)，不同方法分別求解20次的運(yùn)行耗時(shí)平均值如表3。

圖9 多障礙區(qū)環(huán)境路徑規(guī)劃結(jié)果

表3 不同求解算法運(yùn)行耗時(shí)

當(dāng)考慮風(fēng)浪流影響進(jìn)行船舶路徑規(guī)劃時(shí)，相較于串行機(jī)制，主從并行機(jī)制實(shí)現(xiàn)遺傳算法的程序運(yùn)行耗時(shí)更短，且多障礙區(qū)環(huán)境相較于簡單環(huán)境更接近并行化機(jī)制的理想加速比，這說明主從并行自適應(yīng)遺傳算法能夠顯著降低算法運(yùn)行耗時(shí)，有效提升了算法效率。

5 結(jié) 語

船舶智能化已成為船舶業(yè)發(fā)展的趨勢，智能船舶的應(yīng)用優(yōu)勢逐步顯現(xiàn)，而航線規(guī)劃技術(shù)是智能船舶的一項(xiàng)重要功能。針對船舶航線規(guī)劃研究中較少考慮海洋氣象環(huán)境影響的情況，建立了以航行安全為前提、以航行耗時(shí)最短為目標(biāo)的船舶路徑規(guī)劃方法。

綜合考慮海上復(fù)雜環(huán)境因素的影響，考慮航行水域水深限制，計(jì)算風(fēng)、波浪及水流造成的船舶失速，基于Maklink 圖論和改進(jìn)的自適應(yīng)算法求解船舶航行路徑，以幫助船舶更安全、快速地到達(dá)目的地。與標(biāo)準(zhǔn)遺傳算法和蟻群算法和可視圖法對比，在相同迭代次數(shù)下求解航行路徑，改進(jìn)的自適應(yīng)遺傳算法所求路徑船舶航行耗時(shí)更短。另外，在保證一定求解質(zhì)量的情況下，將自適應(yīng)遺傳算法采用主從并行機(jī)制實(shí)現(xiàn)能夠顯著縮短程序運(yùn)行耗時(shí)，有效地提升了船舶路徑規(guī)劃效率。