于家根， 劉正江， 卜仁祥， 李偉峰， 高孝日

(大連海事大學(xué) 航海學(xué)院， 遼寧 大連 116026)

多船會(huì)遇在海上實(shí)踐中屬于復(fù)雜的會(huì)遇局勢，船舶避碰決策是智能避碰技術(shù)研究的關(guān)鍵。為此，研究者嘗試將群智能優(yōu)化算法應(yīng)用于船舶避碰決策中，并取得了一定的研究成果[1-5]。

文獻(xiàn)[1]應(yīng)用人工魚群算法，主要研究單船會(huì)遇的3種局勢(互見中的追越、對遇、交叉相遇)下的最優(yōu)避碰路徑問題，屬于非多船會(huì)遇的避碰決策。文獻(xiàn)[2]應(yīng)用蟻群算法，針對多船會(huì)遇，重點(diǎn)考慮最危險(xiǎn)船舶的單船會(huì)遇情況，研究3種局勢下避碰路徑問題。文獻(xiàn)[3]基于蟻群算法在避碰決策上全局考慮所有的會(huì)遇船舶，但未劃分船舶會(huì)遇局勢。文獻(xiàn)[4]應(yīng)用粒子群算法，重點(diǎn)研究多船會(huì)遇的轉(zhuǎn)向避碰決策，將問題的可行解空間取為[10,180]，卻未考慮大幅度避碰要求和某些局勢下可能左轉(zhuǎn)避碰的情況。文獻(xiàn)[5]基于粒子群算法，側(cè)重研究無人艇的避障問題，僅考慮規(guī)則中的3種局勢。

然而，傳統(tǒng)的群智能優(yōu)化算法大多模擬動(dòng)物群體的社會(huì)行為，由于這些算法模擬的動(dòng)物群體只具有較低的智能，個(gè)體難以進(jìn)行有效的決策，所以這些算法易陷入局部極值點(diǎn)[6]。人類是一個(gè)具有高智能行為的群體，社會(huì)情感優(yōu)化算法[7-8](Social Emotional Optimization Algorithm，SEOA)能夠模擬具有較高智能的人類群體的社會(huì)行為。在SEOA中引入個(gè)體情感因素，利用個(gè)人的情緒值控制進(jìn)化策略，以提高算法的性能來改善其多樣性和靈活性[9]。

在國際海上避碰規(guī)則(簡稱規(guī)則)和良好船藝的框架下, 本文針對船舶會(huì)遇的多種局勢，分別建立互見和不在互見兩種情況下的船舶轉(zhuǎn)向避碰行動(dòng)矩陣，限定問題的求解空間，基于SEOA全局快速尋優(yōu)能力，選擇考慮船舶碰撞危險(xiǎn)度和航程損失的目標(biāo)函數(shù)，最終獲取多船會(huì)遇時(shí)船舶轉(zhuǎn)向避碰決策的最優(yōu)轉(zhuǎn)向角。

1 問題描述

規(guī)則部分條款在船舶轉(zhuǎn)向避碰行動(dòng)上做了限制性規(guī)定(規(guī)則14，規(guī)則15， 規(guī)則17，規(guī)則19)。結(jié)合規(guī)則8對避免碰撞的行動(dòng)要求，充分運(yùn)用良好的船藝，限定船舶轉(zhuǎn)向避碰的方向和范圍，即問題的求解空間。

評價(jià)船舶轉(zhuǎn)向避碰決策的好壞，要考慮轉(zhuǎn)向后各目標(biāo)船的安全駛過距離和本船的航程損失要素，即船舶轉(zhuǎn)向避碰的目標(biāo)。

由此，借鑒群智能優(yōu)化算法尋找最優(yōu)解問題，可以將多船會(huì)遇船舶轉(zhuǎn)向避碰決策問題抽象為：在限定的問題求解空間中，針對避碰目標(biāo)函數(shù)，全局范圍內(nèi)尋找最優(yōu)避碰轉(zhuǎn)向角。

2 問題的求解空間

以普通機(jī)動(dòng)船(Power-Driven Vessel, PDV)作為研究對象，帆船會(huì)遇條款(規(guī)則12)暫不考慮。考慮互見中的追越、對遇、交叉相遇和不同種類的船舶會(huì)遇(本船與失控船(Vessel not under Command, NUC)、操限船(Vessel Restricted in Her Ability to Maneuver, RAM)、從事捕魚船(Vessel Engaged in Fishing, VEF)和帆船(Sailing Vessel, SV)的會(huì)遇)的情況和不在互見中的船舶會(huì)遇的情況。

與文獻(xiàn)[10]確定重點(diǎn)避讓目標(biāo)船的做法不同，所進(jìn)行的研究全局考慮所有會(huì)遇船舶，建立船舶轉(zhuǎn)向避碰行動(dòng)矩陣為

(1)

式(1)中：矩陣的行為目標(biāo)船的相對方位(Relative Bearing,RB)，矩陣的列為目標(biāo)船(Target Ship,TS)的類型;amn為本船對處在第m行的RB范圍內(nèi)，第n種類型的目標(biāo)船應(yīng)采取的轉(zhuǎn)向避碰行動(dòng)值;矩陣中的值用-1,0,1表示,-1為本船向左轉(zhuǎn)向避碰;0為本船左、右轉(zhuǎn)向避碰均可;1為本船向右轉(zhuǎn)向避碰。

根據(jù)各目標(biāo)船的RB和船舶類型，構(gòu)建本船轉(zhuǎn)向避碰的行動(dòng)向量A7=[A1,A2,…,AN]，AN為對第N個(gè)目標(biāo)船的行動(dòng)值。

行動(dòng)值為1，是根據(jù)規(guī)則或良好船藝的要求；行動(dòng)值為-1，是根據(jù)良好船藝確定的，旨在獲取更好的避碰效果；行動(dòng)值為0，說明按規(guī)則和良好船藝沒有約束。多船避碰時(shí)，本船行動(dòng)值的優(yōu)先級按1>-1>0順序，即：AT中如果出現(xiàn)1值，限定為右轉(zhuǎn)避碰；否則，檢測是否出現(xiàn)-1值，如果是，則限定為左轉(zhuǎn)避碰；如果只出現(xiàn)0值，雖然表示左、右轉(zhuǎn)向避碰均可，但考慮良好船藝和協(xié)調(diào)避碰，限定為右轉(zhuǎn)避碰(海上常見)。

求解空間的限定：考慮規(guī)則中大幅度的轉(zhuǎn)向避碰要求[11]，如果根據(jù)AT限定為右轉(zhuǎn)避碰，求解空間限定在[30,180]；如果限定為左轉(zhuǎn)避碰，則限定在[-180,-30]。

2.1 互見中的轉(zhuǎn)向避碰行動(dòng)矩陣

互見中，基于規(guī)則和良好船藝，參照互見中的局勢(見圖1)，轉(zhuǎn)向避碰行動(dòng)需要考慮下列約束：

1) 追越：若目標(biāo)船為被追越船A，左轉(zhuǎn)、右轉(zhuǎn)避碰均可；若目標(biāo)船為追越船B，緊迫局面形成時(shí)，左轉(zhuǎn)、右轉(zhuǎn)避碰均可，考慮避碰的協(xié)調(diào)性，目標(biāo)船很有可能右轉(zhuǎn)，所以本船應(yīng)左轉(zhuǎn)避碰。

2) 對遇：本船和目標(biāo)船C應(yīng)各自右轉(zhuǎn)避碰。

3) 交叉相遇：若目標(biāo)船為直航船D，避讓時(shí)應(yīng)避免橫越他船前方，應(yīng)該向右轉(zhuǎn)向避碰；若目標(biāo)船為讓路船E，緊迫局面形成時(shí)，本船可以行動(dòng)，應(yīng)避免橫越他船前方，應(yīng)該向右轉(zhuǎn)向避碰。

4) 不同種類船舶會(huì)遇：由于不構(gòu)成對遇或交叉相遇(非兩艘機(jī)動(dòng)船會(huì)遇)，本船左轉(zhuǎn)、右轉(zhuǎn)避碰均可。如構(gòu)成追越，則參照1)執(zhí)行。

5) 良好船藝：對正橫附近來船F(xiàn)，避免朝其轉(zhuǎn)向更有助于避碰。

為研究問題方便，將PDV類型的目標(biāo)船按照在轉(zhuǎn)向行動(dòng)上的要求不同劃分為：PDV1(被追越機(jī)動(dòng)船)和PDV2(非被追越機(jī)動(dòng)船)，PDV1的判定用目標(biāo)船的航向CTS判定，即：CTS在[TB-67.5,TB+67.5]范圍內(nèi)(視覺可見目標(biāo)艉燈光??；(TB，True Bearing))，且兩船距離越來越近。目標(biāo)船RB在[67.5,292.5]時(shí),CTS在[TB-67.5, TB+67.5]內(nèi)，兩船距離會(huì)越來越遠(yuǎn)，構(gòu)不成追越，因此,在行動(dòng)上不予考慮，其行動(dòng)值取0。

基于上述約束，針對多船會(huì)遇，建立互見中的轉(zhuǎn)向避碰行動(dòng)矩陣(見表1)。

表1 互見中的轉(zhuǎn)向避碰行動(dòng)矩陣

2.2 不在互見中的轉(zhuǎn)向避碰行動(dòng)矩陣

能見度不良、不在互見中(規(guī)則19)存在碰撞危險(xiǎn)時(shí)，任何船舶都負(fù)有同等避讓責(zé)任，會(huì)遇局勢見圖2。規(guī)則19對轉(zhuǎn)向避碰行動(dòng)約束如下：

1) 除對被追越(指追越態(tài)勢，下同)船舶A外，對正橫前的船舶B和船舶C，避免向左轉(zhuǎn)向。

2) 對正橫船舶D或正橫后船舶E，避免朝著它轉(zhuǎn)向。

據(jù)此，研究將目標(biāo)船的類型只劃分為被追越船(Overtaken Vessel)和其他船(Other Vessel)兩種。同理，目標(biāo)船RB在[67.5,292.5]內(nèi)，構(gòu)不成追越，在行動(dòng)上不予考慮，其行動(dòng)值取0。

基于上述約束，針對多船會(huì)遇，建立不在互見中的轉(zhuǎn)向避碰行動(dòng)矩陣(見表2)。

表2 不在互見中的轉(zhuǎn)向避碰行動(dòng)矩陣

3 基于SEOA的轉(zhuǎn)向避碰決策

3.1 算法的基本原理

SEOA模擬人類群體的社會(huì)行為，每個(gè)個(gè)體代表一個(gè)虛擬的人，每個(gè)個(gè)體X都希望得到較高的社會(huì)評價(jià)，并根據(jù)其情緒值選擇下一步(進(jìn)化)行為。對進(jìn)化后的個(gè)體進(jìn)行社會(huì)評價(jià):若能得到較好的社會(huì)評價(jià)值，個(gè)體情緒值變高;若得到較差的社會(huì)評價(jià)值，則個(gè)體情緒值降低。情緒值決定下一代的進(jìn)化行為，直到指定代數(shù)，獲得社會(huì)評價(jià)最優(yōu)的個(gè)體。

3.2 決策的目標(biāo)函數(shù)

決策的目標(biāo)函數(shù)即SEOA的社會(huì)評價(jià)。多船會(huì)遇，且存在碰撞危險(xiǎn)，好的轉(zhuǎn)向避碰決策應(yīng)能使最小DCPA的目標(biāo)船的DCPA值較大，且航程損失相對較小。為此，目標(biāo)函數(shù)為

f(xj)=0.7f1(xj)+0.3f2(xj)

(2)

式(2)中：

(3)

f1(xj)為碰撞危險(xiǎn)度函數(shù);DCPAjr為第j個(gè)個(gè)體與第r個(gè)目標(biāo)船的DCPA值；N為目標(biāo)船的數(shù)目；目標(biāo)函數(shù)值越小，碰撞危險(xiǎn)度越小。

f2(xj)=

(4)

3.3 種群初始化

初始化種群數(shù)量：Npop為最大迭代代數(shù)：Maxiter，限定問題的求解空間[xmin,xmax],情緒值Ej(0)∈[0,1]，初始代內(nèi)情緒值均設(shè)為1，情緒值最大即個(gè)體情緒飽滿，個(gè)體認(rèn)為他們在初始代的行為是正確的，并選擇下一步行為：

(5)

式(5)中:xj(0)為初始化階段的個(gè)體j，其值即轉(zhuǎn)向避碰的航向變化值；xj(1)為進(jìn)化后第1代的個(gè)體j；k1為控制系數(shù)；rand1為服從均勻分布的隨機(jī)數(shù)；xs(0)初始代中社會(huì)評價(jià)最差的L個(gè)個(gè)體。

3.4 個(gè)體進(jìn)化

3.4.1計(jì)算個(gè)體的適應(yīng)值

根據(jù)目標(biāo)函數(shù)，計(jì)算個(gè)體的適應(yīng)值，找出社會(huì)評價(jià)最差的L個(gè)個(gè)體xs(t)；找出第j個(gè)個(gè)體進(jìn)化至當(dāng)前代的最優(yōu)個(gè)體值xjbest(t)為

xjbest(t)=argmin{f(xj(h))|1≤h≤t}

(6)

找出進(jìn)化至當(dāng)前代的群最優(yōu)個(gè)體xgbest(t)為

xgbest(t)=

argmin{f(xj(h))|1≤h≤t,1≤j≤Npop}

(7)

3.4.2計(jì)算個(gè)體的情緒值

第j個(gè)個(gè)體如果不能得到比之前各代更好的社會(huì)的評價(jià)值，情緒值下降為

Ej(t+1)=Ej(t)-Δ

(8)

式(8)中：Δ值取0.05[7]，如果Ej(t+1)<0，則Ej(t+1)=0。

第j個(gè)個(gè)體如果能夠得到比之前各代更好的社會(huì)評價(jià)值，情緒值大增，設(shè)Ej(t+1)=1。

3.4.3進(jìn)化公式

設(shè)定情緒值閾值m1、m2。如果Ej(t+1)

xj(t+1)=xj(t)+k2·rand2·(xgbest(t)-xj(t))

(9)

如果m1≤Ej(t+1)≤m2，個(gè)體的情緒平和，個(gè)體學(xué)習(xí)時(shí)會(huì)對各種經(jīng)驗(yàn)進(jìn)行選擇，既學(xué)習(xí)其他個(gè)體的成功經(jīng)驗(yàn)，還考慮自身的經(jīng)驗(yàn)進(jìn)行學(xué)習(xí)，同時(shí)規(guī)避一些不好的經(jīng)驗(yàn)。進(jìn)化的方式為

xj(t+1)=xj(t)+k3·rand3·(xjbest(t)-xj(t))+

k2·rand2·(xgbest(t)-xj(t))-

(10)

如果Ej(t+1)>m2，個(gè)體的情緒高昂，個(gè)體學(xué)習(xí)時(shí)更傾向于考慮自身的經(jīng)驗(yàn)，同時(shí)規(guī)避不好的經(jīng)驗(yàn)，進(jìn)化的方式為

xj(t+1)=xj(t)+k3·rand3·(xjbest(t)-xj(t))-

(11)

式(9)～式(11)中：k為控制系數(shù);rand為服從均勻分布的隨機(jī)數(shù)。

3.5 算法的步驟

1) 初始化各參數(shù)：Npop、Maxiter、xmin、xmax、m1、m2、L、Ej。

2) 隨機(jī)初始化種群。

3) 計(jì)算個(gè)體的適應(yīng)值f(xj)(式(2))，選出最差L個(gè)個(gè)體值xs(t)。

4) 更新個(gè)體最優(yōu)值xjbest(t)(式(6))。

5) 更新群體最優(yōu)值xgbest(t)(式(7))。

6) 判定是否滿足結(jié)束條件。若滿足，輸出最優(yōu)個(gè)體值和最優(yōu)個(gè)體適應(yīng)值；否則，進(jìn)入步驟7)。

7) 個(gè)體情緒值調(diào)節(jié)(式(8))。

8) 根據(jù)情緒值選擇進(jìn)化行為(式(5)。式(9)式(10)。式(11))，返回至步驟3)。

算法的流程見圖3。

4 實(shí)例仿真分析

仿真實(shí)例中的種群數(shù)量Npop為30，最大迭代代數(shù)Maxiter設(shè)置為2 000，最差個(gè)體數(shù)L為10，為控制進(jìn)化的步幅，控制系數(shù)K1為0.01，K2、K3為0.1。情緒值閾值m1為0.3，m2為0.7。

4.1 仿真實(shí)例1

能見度不良，不在互見中。本船初始航向000，航速15 kn，同時(shí)會(huì)遇多艘船舶(TS1, TS2, …,TS5)，存在碰撞危險(xiǎn)，會(huì)遇局勢見表3[12]。目標(biāo)船過本艏部，DCPA為正值，過艉則為負(fù)值。

表3 能見度不良,不在互見中同各目標(biāo)船的會(huì)遇局勢

從圖4可以判定：各目標(biāo)船均不是被船追越(態(tài)勢)的情況，依據(jù)行動(dòng)矩陣如表2所示，可得行動(dòng)向量AT=(1,1,-1,1,1)，其中含1值，故向右轉(zhuǎn)向避碰，問題的求解空間限定在[30,180]。

仿真結(jié)果見圖5和圖6。圖5為各代最優(yōu)個(gè)體值，即船舶轉(zhuǎn)向避碰決策應(yīng)轉(zhuǎn)向的幅度。圖6為各代最優(yōu)個(gè)體的適應(yīng)值。

仿真圖示表明，最優(yōu)個(gè)體值收斂于某一值，即轉(zhuǎn)向避碰決策的解。為驗(yàn)證算法的可行性及有效性，執(zhí)行算法30次，可得個(gè)體最優(yōu)值的范圍是[39.96,40.12]，最優(yōu)個(gè)體適應(yīng)值范圍是[0.434 6,0.434 7]，最優(yōu)個(gè)體值的均值是40.0，對應(yīng)的適應(yīng)值是0.434 7，即最佳轉(zhuǎn)向避碰行動(dòng)為右轉(zhuǎn)40.0°。

4.2 仿真實(shí)例2

能見度良好、互見中時(shí)，本船初始航向000°，航速14.3 kn，同時(shí)會(huì)遇5艘船舶(TS1(PDV)，TS2(SF)，TS3(VEF)，TS4(PDV)，TS5(RAM))，存在碰撞危險(xiǎn)。會(huì)遇局勢見表4。

表4 能見度良好,互見中同各目標(biāo)船的會(huì)遇局勢

TS1和TS4都是PDV，需要進(jìn)一步劃分類別。從見圖7可看出,目標(biāo)船TS1相對方位不在[67.5,292.5]內(nèi)，且航向CTS1在[TB1-67.5,TB1+67.5]內(nèi)，故TS1是PDV1。目標(biāo)船TS4在相對方位[67.5,292.5]，且航向CTS4不在[TB4-67.5,TB4+67.5]內(nèi)，故TS4是PDV2。

依據(jù)行動(dòng)矩陣如表1所示，可得行動(dòng)向量AT=(0,0,-1,-1,0)，不含1值，含-1值，故向左轉(zhuǎn)向避碰，問題的求解空間限定在[-180,-30]。

仿真結(jié)果見圖8和圖9。圖8為各代最優(yōu)個(gè)體值，即船舶轉(zhuǎn)向避碰決策應(yīng)轉(zhuǎn)向的幅度。圖9為各代最優(yōu)個(gè)體的適應(yīng)值。執(zhí)行算法30次，得個(gè)體最優(yōu)值的范圍是[-51.64,-51.29]，最優(yōu)個(gè)體適應(yīng)值范圍是[0.318 6,0.318 7]，最優(yōu)個(gè)體值的均值是-51.3，對應(yīng)的適應(yīng)值是0.318 6，即最佳轉(zhuǎn)向避碰行動(dòng)為左轉(zhuǎn)51.3°。

4.3 結(jié)果分析

仿真實(shí)例可看出，應(yīng)用SEOA，500代內(nèi)即能夠收斂于某一固定值，收斂速度快，能夠快速給出船舶轉(zhuǎn)向避碰決策，且算法適用于“能見度不良不在互見中”和“互見中”兩種情況。算法執(zhí)行30次，最優(yōu)個(gè)體值限定在某一范圍，說明應(yīng)用SEOA能夠得到滿意的一致最優(yōu)解。

對上述兩個(gè)獲取的結(jié)果進(jìn)行驗(yàn)證，實(shí)例1中，向右轉(zhuǎn)向40.0°后，本船同各目標(biāo)船的DCPA向量值為[2.16,1.38,-2.42,-1.63,-1.58]。實(shí)例2中，向左轉(zhuǎn)向51.3°后，本船同各目標(biāo)船的DCPA值向量為[4.48,-2.43,-4.05,-3.02,2.62]，既滿足規(guī)則中的大幅度避碰要求，又可確保安全駛過，且航程損失不大，結(jié)果滿意。

5 結(jié)束語

1) 基于規(guī)則和良好船藝，按互見和不在互見中兩種情況，對多船會(huì)遇局勢進(jìn)行劃分，建立了轉(zhuǎn)向避碰行動(dòng)矩陣，通過目標(biāo)船的相對方位和目標(biāo)船的類型構(gòu)建轉(zhuǎn)向避碰行動(dòng)量，限定問題的求解空間。

2) 提出一種基于SEOA的多船會(huì)遇轉(zhuǎn)向避碰決策方法，應(yīng)用SEOA全局快速尋優(yōu)的能力，在限定的求解空間內(nèi)，針對船舶碰撞危險(xiǎn)度和航程損失的目標(biāo)函數(shù)，獲得最佳轉(zhuǎn)向避碰決策,仿真結(jié)果滿意。

3) 決策中的避碰行動(dòng)矩陣和目標(biāo)函數(shù)是關(guān)鍵，其中航程損失函數(shù)的系數(shù)可調(diào)，后續(xù)研究中可通過自學(xué)習(xí)方式調(diào)整。優(yōu)化船舶復(fù)航?jīng)Q策，實(shí)現(xiàn)船舶點(diǎn)到點(diǎn)的避碰路徑規(guī)劃將是下一步的研究工作。