基于社會情感優(yōu)化算法的船舶轉(zhuǎn)向避碰決策

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

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

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

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

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

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

1 問題描述

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

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

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

2 問題的求解空間

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

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

(1)

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

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

行動值為1，是根據(jù)規(guī)則或良好船藝的要求；行動值為-1，是根據(jù)良好船藝確定的，旨在獲取更好的避碰效果；行動值為0，說明按規(guī)則和良好船藝沒有約束。多船避碰時，本船行動值的優(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)向避碰行動矩陣

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 算法的基本原理

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

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

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

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

(2)

式(2)中：

(3)

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

f2(xj)=

(4)

3.3 種群初始化

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

(5)

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

3.4 個體進化

3.4.1計算個體的適應(yīng)值

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

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

(6)

找出進化至當前代的群最優(yōu)個體xgbest(t)為

xgbest(t)=

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

(7)

3.4.2計算個體的情緒值

第j個個體如果不能得到比之前各代更好的社會的評價值，情緒值下降為

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

(8)

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

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

3.4.3進化公式

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

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

(9)

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

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

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

(10)

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

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

(11)

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

3.5 算法的步驟

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

2) 隨機初始化種群。

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

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

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

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

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

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

算法的流程見圖3。

4 實例仿真分析

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

4.1 仿真實例1

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

表3 能見度不良,不在互見中同各目標船的會遇局勢

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

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

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

4.2 仿真實例2

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

表4 能見度良好,互見中同各目標船的會遇局勢

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

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

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

4.3 結(jié)果分析

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

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

5 結(jié)束語

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

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

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