基于天牛須搜索算法的多船避碰決策方法

劉 朝 黃立文 張 可 郝國柱

(武漢理工大學(xué)航運(yùn)學(xué)院 武漢 430063)

0 引 言

在航海實(shí)踐中，駕駛員通常是依靠自身經(jīng)驗(yàn)來制定船舶的避碰決策，但當(dāng)處于比較復(fù)雜的多船會遇局面時，駕駛員很難保證可以做出最優(yōu)的避碰決策[1].因此，許多專家學(xué)者應(yīng)用智能優(yōu)化算法來研究船舶的避碰策略問題，并取得了很多的成果.文獻(xiàn)[2]將社會情感優(yōu)化算法應(yīng)用到船舶轉(zhuǎn)向避碰的決策中，以便求解出船舶最佳轉(zhuǎn)向，但系數(shù)調(diào)節(jié)較為復(fù)雜.文獻(xiàn)[3]基于改進(jìn)的免疫粒子群算法，給出了一種求解多船會遇局面下計(jì)算最佳轉(zhuǎn)向幅度的方案.文獻(xiàn)[4]通過結(jié)合前景理論和多指標(biāo)灰關(guān)聯(lián)決策，建立了考慮駕駛員風(fēng)險(xiǎn)態(tài)度的避碰決策優(yōu)化模型，結(jié)果表明：該模型可幫助駕駛員在不同風(fēng)險(xiǎn)偏好下選取最優(yōu)避碰方案.文獻(xiàn)[5]以船舶最近會遇距離和最近會遇時間建立碰撞危險(xiǎn)度模型，綜合考慮轉(zhuǎn)向幅度和航行時間，構(gòu)建了避碰決策模型，并提出了一種使用粒子群-遺傳優(yōu)化算法求解該決策模型的方案.然而，這些算法大多在于模擬動物的群體性活動，無法從個體中獲取有效的決策，求解過程也較為繁瑣.

天牛須搜索(beetle antennae search，BAS)是一種類似于遺傳算法、粒子群算法、模擬退火等算法的智能優(yōu)化算法[6].該算法不需要知道函數(shù)的具體形式，也不需要求解函數(shù)的梯度，就可以實(shí)現(xiàn)全局高效尋優(yōu).相比較粒子群算法，BAS算法僅需要一個個體，極大地降低了尋優(yōu)過程的運(yùn)算量.目前該算法已經(jīng)被應(yīng)用于機(jī)器故障診斷、電網(wǎng)優(yōu)化調(diào)度、選址、圖像修復(fù)及路徑規(guī)劃等多個領(lǐng)域，并表現(xiàn)出算法在解決優(yōu)化問題中的有效性及優(yōu)越性[7-10].本文利用船舶碰撞危險(xiǎn)度并考慮船舶在進(jìn)行避碰操作時的損失函數(shù)來確立符合航海實(shí)際的避碰決策目標(biāo)函數(shù)，并利用BAS算法研究多船會遇局面下最優(yōu)避碰轉(zhuǎn)向幅度以及復(fù)航時間，并通過仿真實(shí)驗(yàn)驗(yàn)證該避碰決策方案.

1 船舶會遇態(tài)勢的劃分

海上實(shí)踐表明，對會遇態(tài)勢的認(rèn)識不一致是造成船舶間避碰行動不協(xié)調(diào)乃至碰撞的重要原因之一[11].根據(jù)《國際海上避碰規(guī)則》對追越、對遇和交叉相遇的定義以及相關(guān)規(guī)定，以本船為中心，將他船相對于本船的方位劃分為五個區(qū)域[12]，見圖1.

圖1 船舶會遇態(tài)勢劃分

根據(jù)避碰規(guī)則，若互見中兩船之間存在碰撞風(fēng)險(xiǎn)，對于E、A區(qū)域的來船，本船是讓路船，需要進(jìn)行相應(yīng)的避碰操作，一般通常是進(jìn)行右轉(zhuǎn)向操作；若來船位于B區(qū)域，則本船為讓路船，一般來說本船可以通過降低船速或者是進(jìn)行左轉(zhuǎn)向操作進(jìn)行避碰；若來船處于C、D區(qū)域，那么本船為直航船，來船需要進(jìn)行相應(yīng)避碰操作.

2 船舶碰撞危險(xiǎn)度

船舶碰撞危險(xiǎn)度(collision risk index，ICR)是對船舶之間發(fā)生碰撞的可能大小的一個度量，其取值范圍是[0,1].目前對于船舶碰撞危險(xiǎn)度的計(jì)算模型有很多，文中以船舶之間距離(D)、船速比(K)、他船與本船之間相對方位(B)、最近會遇距離(DCPA)，以及最近會遇時間(TCPA)等五個指標(biāo)為主要參數(shù)，并綜合考慮航行水域狀況、能見度情況、操船者技術(shù)、船舶操縱性能等因素，確定他船與本船之間的碰撞危險(xiǎn)度[13].

設(shè)uDi、uKi、uBi、uDCPAi、uTCPAi分別為與本船會遇的目標(biāo)船i各主要參數(shù)的危險(xiǎn)隸屬度，取值范圍為[0,1]，i=1,2,…,n.那么本船與目標(biāo)船i之間的碰撞危險(xiǎn)度ICRi即為

ICRi=aDuDi+aKuKi+aBuBi+

aDCPAuDCPAi+aTCPAuTCPAi

(1)

式中：aD，aK，aB，aDCPA，aTCPA為五個主要參數(shù)的危險(xiǎn)隸屬度的權(quán)重，取值范圍為[0,1]，且滿足

aD+aK+aB+aDCPA+aTCPA=1

(2)

船舶之間的距離越小，碰撞危險(xiǎn)度就越大.船舶之間距離的隸屬度函數(shù)為

(3)

式中：D1為最晚避讓距離；D2為可采取避讓措施距離，由航行水域狀況、能見度，以及人為因素等決定.取值為

D1=H1×H2×H3×DLA

(4)

D2=H1×H2×H3×Ri

(5)

Ri=1.7cos(Bi-19°)+

(6)

式中：H1取決于能見度；H2由航行水域狀況決定；H3取決于操船者經(jīng)驗(yàn)、技術(shù)、反應(yīng)能力等人為因素，DLA為最晚施舵距離，通常取12倍的船舶長度.

(7)

式中：W為常數(shù)，這里取值為2；C為碰角(0°≤C≤180°).

(8)

(9)

式中：d1為船舶碰撞距離；d2為船舶注意距離.

(10)

d2=2d1

(11)

(12)

式中：t1為船舶碰撞時間；t2為船舶注意時間，并且

(13)

(14)

式中：vri為目標(biāo)船i與本船之間相對速度.

3 基于天牛須搜索算法的多船避碰決策方法

3.1 天牛須搜索算法基本原理

天牛須搜索也被稱為甲殼蟲須搜索，搜索過程的簡化模型見圖2.

圖2 天牛搜索過程簡化模型

那么該簡化模型的尋優(yōu)策略即為

1) 天牛的左右兩須應(yīng)位于天牛質(zhì)心的兩邊；

2) 天牛行動的步長step與左右兩須之間的距離d0比值應(yīng)該是一個固定的常數(shù)，即step=c·d0，其中c為常數(shù).也可以理解為體型較大的天牛(兩須之間的距離長)行走的步長較大，體型較小的天牛行走的步長較小.

3) 天牛每次行動之后，它的頭部朝向應(yīng)該是隨機(jī)的.

3.2 BAS算法建模

假設(shè)要求解一個n維的空間中目標(biāo)函數(shù)f的最小值，現(xiàn)設(shè)天牛的質(zhì)心坐標(biāo)為x，左須坐標(biāo)為xl，右須坐標(biāo)為xr，左右兩須之間的距離為d0.由尋優(yōu)策略(3)可知，天牛的頭部朝向是隨機(jī)的，所以由右須指向左須的向量的方向也是隨機(jī)的，在此用隨機(jī)向量dir=rands(n,1)來表示右須指向左須的向量.對其進(jìn)行歸一化處理，即

(15)

由此，可以得到

xl-xr=d0×dir

(16)

(17)

對于目標(biāo)函數(shù)f，首先求取天牛當(dāng)前位置左右兩須的值，即fl=f(xl)，fr=f(xr).

如果fl

x=x+step×dir

(18)

如果fl>fr，為了尋找目標(biāo)函數(shù)的最小值，此時天牛應(yīng)該朝著右須的方向飛行step的距離，即

x=x-step×dir

(19)

為了簡化形式，使用符號函數(shù)sign對式(18)和(19)進(jìn)行簡寫

x=x-step×dir×sign(fl-fr)

(20)

此外，對于天牛行動的步長，本文將使用變步長的方式代替固定步長.在每次的迭代過程中，將步長設(shè)置為step=eta·step，其中：eta∈[0,1]且接近于1，這里取eta=0.95.

3.3 避碰決策目標(biāo)函數(shù)

當(dāng)船舶之間存在碰撞危險(xiǎn)時，一般來說，常用的避碰操作是采取變速、轉(zhuǎn)向或者同時進(jìn)行轉(zhuǎn)向和變速等方式.由文獻(xiàn)[13]可知，通常情況下，即使是處于多船避碰的局面，船舶也可以通過一次轉(zhuǎn)向或者變速來實(shí)現(xiàn)避碰，并且轉(zhuǎn)向避讓是使用頻率最高的一種方法，很少會同時進(jìn)行轉(zhuǎn)向和變速操作.所以，本文將主要研究船舶避碰操作中的轉(zhuǎn)向避碰操作.

當(dāng)會遇的船舶之間存在碰撞危險(xiǎn)時，需要根據(jù)本船與他船之間的會遇態(tài)勢，合理的選取轉(zhuǎn)向幅度，此時應(yīng)滿足：

1) 轉(zhuǎn)向后，應(yīng)使得會遇船舶之間的碰撞危險(xiǎn)度盡可能的減小.

2) 在滿足避碰規(guī)則“大幅度”要求的前提下，轉(zhuǎn)向幅度應(yīng)盡可能的小，以減少資源的損耗.

3) 船舶轉(zhuǎn)向后，在保證航行安全的前提下，在新航向上的航行時間要盡可能的短，以降低復(fù)航的難度.

基于以上三點(diǎn)，在多船會遇時，船舶的避碰決策目標(biāo)函數(shù)為

minf(x)=w1f1(xi)+w2f2(xi)

(21)

式中：f1(xi)為目標(biāo)船i與本船之間的碰撞危險(xiǎn)目標(biāo)函數(shù)，f2(xi)為航程損失的目標(biāo)函數(shù)，w1、w2為權(quán)重系數(shù)，為了便于尋優(yōu)計(jì)算，w1取0.7，w2取0.3.

碰撞危險(xiǎn)目標(biāo)函數(shù)為

(22)

式中：n為目標(biāo)船個數(shù).

航程損失的目標(biāo)函數(shù)為

(23)

式中：xi為轉(zhuǎn)向幅度，航程損失函數(shù)的取值范圍為[0,1].同理，損失函數(shù)的值越小，轉(zhuǎn)向幅度和復(fù)航時間應(yīng)越短.

4 仿真分析

假設(shè)在開闊水域中能見度良好，駕駛者技術(shù)水平良好，船舶的操縱性能良好，即H1=1，H2=1，H3=1.本文以三船會遇局面為仿真對象，本船的初始位置為(0,-4)，航速為16 kn，航向?yàn)?°；目標(biāo)船1的初始位置為(2,1.5)，航速為16 kn，航向?yàn)?20°；目標(biāo)船2的初始位置為(2,-3)，航速為17 kn，航向?yàn)?00°.船舶間的初始會遇態(tài)勢見圖3.

圖3 船舶間初始會遇態(tài)勢

由船舶間的初始會遇態(tài)勢，以及表1中船舶間的相關(guān)參數(shù)可知，本船與目標(biāo)船1、目標(biāo)船2之間的碰撞危險(xiǎn)度都很大，存在很高的碰撞風(fēng)險(xiǎn).根據(jù)避碰規(guī)則，此時兩目標(biāo)船為直航船，本船應(yīng)及早采取合適的避碰行動，以降低本船與兩目標(biāo)船之間的碰撞風(fēng)險(xiǎn).同時對于目標(biāo)船2和目標(biāo)船1來說，兩船之間也存在碰撞風(fēng)險(xiǎn)，根據(jù)避碰責(zé)任，目標(biāo)船2也要采取合適的避碰操作來降低與目標(biāo)船1之間的碰撞風(fēng)險(xiǎn).因此，對于圖3的會遇局面，本船需要選取合適的轉(zhuǎn)向幅度以降低與兩目標(biāo)船之間的碰撞風(fēng)險(xiǎn)；而目標(biāo)船2也要找到最優(yōu)的轉(zhuǎn)向幅度.

表1 初始會遇船舶間相關(guān)數(shù)據(jù)

在圖3的多船會遇局面中，使用BAS算法為本船規(guī)劃一個合適的避碰方案，以降低碰撞風(fēng)險(xiǎn).使用BAS算法對式(21)的目標(biāo)函數(shù)進(jìn)行尋優(yōu)計(jì)算，同時為了避免計(jì)算結(jié)果的偶然性，對該尋優(yōu)過程進(jìn)行10次重復(fù)操作，每次的迭代次數(shù)均為100次，最終求得平均最優(yōu)轉(zhuǎn)向幅度為32.185 6°本船恢復(fù)原航向的時間約為8.34 min.即本船的最佳轉(zhuǎn)向幅度是右轉(zhuǎn)向32.185 6°，在該航向上航行大概8.34 min之后可以完成避碰操作.同時為了驗(yàn)證BAS算法的有效性，使用粒子群算法對避碰決策目標(biāo)函數(shù)進(jìn)行求解.算法的尋優(yōu)過程見圖4.

圖4 本船的PSO和BAS算法迭代過程

使用BAS算法對目標(biāo)船2的轉(zhuǎn)向幅度進(jìn)行尋優(yōu)求解.在經(jīng)過10次重復(fù)計(jì)算之后，得到的平均最優(yōu)轉(zhuǎn)向幅度為43.090 3°，恢復(fù)航向使用的時間為11.14 min.算法的迭代過程見圖5.

圖5 目標(biāo)船2的PSO和BAS算法迭代過程

表2將BAS算法對多船會遇局面避碰策略的求解結(jié)果與粒子群算法進(jìn)行了簡單的對比.從表中可以看出，BAS算法的收斂速度快，求解出來的最優(yōu)轉(zhuǎn)向幅度比粒子群算法要小，但復(fù)航時間要稍微長一點(diǎn)，這與實(shí)際情況是相符合的.同時本文所用的碰撞危險(xiǎn)度模型綜合考慮了船舶的操縱性能、人為因素、航行環(huán)境等因素，使得BAS算法求得的結(jié)果也更符合航海實(shí)際.

表2 算法對比

5 結(jié) 束 語

本文通過分析船舶的會遇態(tài)勢，結(jié)合避碰規(guī)則對避碰責(zé)任進(jìn)行了劃分，在綜合考慮航行水域情況、能見度、操船者技術(shù)、船舶操縱性能等因素的基礎(chǔ)上，使用船舶之間距離、船速比、方位角、最近會遇距離以及最近會遇時間等五個指標(biāo)確定了比較符合航海實(shí)際的碰撞危險(xiǎn)度模型，通過對避碰操作過程中轉(zhuǎn)向幅度的分析，建立了避碰策略目標(biāo)函數(shù)，利用BAS算法的全局搜索能力強(qiáng)、尋優(yōu)速度快、魯棒性強(qiáng)的特點(diǎn)，求得了多船會遇下最優(yōu)避碰轉(zhuǎn)向幅度以及復(fù)航時間.通過三船會遇的仿真實(shí)驗(yàn)，驗(yàn)證了算法的有效性.