基于粒子群-遺傳優化算法的船舶避碰決策

曾 勇， 張金奮， 張明陽， 張 笛

(1.武漢理工大學 a.智能交通系統研究中心； b.國家水運安全工程技術研究中心，武漢 430063； 2.阿爾托大學工程學院 應用力學系, 芬蘭 艾斯堡 02270)

船舶智能避碰決策是《智能船舶發展行動計劃(2019—2021年)》的八大關鍵技術之一，為解決船舶避碰問題，許多專家學者將啟發式算法應用到船舶避碰決策研究中。倪生科等[1]利用多種群的遺傳算法(Genetic Algorithm，GA)對船舶進行避碰輔助決策，用算法中精英種群內最優個體的最少保持代數作為算法的終止條件來評價所建立的適應度函數，仿真結果顯示多種群的GA可有效地為船舶避碰提供輔助決策。馬文耀等[2-3]利用細菌覓食算法(Bacterial Foraging Algorithm，BFA)與人工魚群算法(Artificial Fish Swarm Algorithm，AFSA)對船舶避碰進行航線優化，結果表明：BFA與AFSA算法能得到避碰路徑和避碰參數，可為船舶規劃出合理的避碰航線，但研究僅考慮單一目標船舶的避讓。田雨波等[4]將免疫粒子群算法(Immune Particle Swarm Algorithm，IPSA)應用到船舶避碰研究中，仿真結果證明該算法可找到船舶避碰的最優轉向幅度。XU[5]和白一鳴等[6]基于危險模式下的人工免疫算法(Danger Immune Algorithm，DIA)對船舶的避碰策略進行優化，仿真實例顯示DIA能夠在船舶會遇的情況下為駕駛員提供一定的避碰決策支持。于家根等[7-8]利用擬態物理學優化算法(Artificial Physics Optimization Algorithm，APOA)與社會情感優化算法(Social Emotional Optimization Algorithm，SEOA)來研究分析船舶在特定會遇情形下的轉向避碰決策問題。楊柏丞等[9]對傳統的模擬退火算法(Simulated Annealing，SA)進行改進，并將之應用到多船會遇的轉向避碰決策中，結果證明改進的SA算法能滿足避碰決策的實時性。

粒子群優化(Particle Swarm Optimization, PSO)算法與GA是經常被使用的啟發式算法，但PSO算法在計算函數極值時，常常出現早熟現象，導致求解函數極值存在一定的誤差，而GA算法對于函數尋優采用選擇、交叉、變異的操作，直接以概率化的尋優方法將目標函數作為搜索信息。綜合運用粒子群優化-遺傳(PSO-GA)算法的特點，可增強全局尋優能力、加快算法的進化速度和提高收斂精度。本文利用PSO-GA的混合優化算法對避碰決策進行研究，同時對算法生成的避碰路徑分別從安全性和經濟性進行分析，綜合考慮國際海上避碰規則(Convention on the International Regulations for Prerenting Collisions at Sea, COLREGs)和船員良好船藝的要求，利用船舶碰撞危險度模型和避碰的目標函數模型評價路徑的安全性與經濟性，通過設計的PSO-GA算法，不斷地進行自適應調整，從而獲得滿足要求的避碰路徑。算法過程見圖1。

圖1 避碰路徑算法過程

1 船舶會遇局面劃分

根據COLREGs的規定，首先根據會遇態勢確定船舶之間的避讓責任。船舶之間的會遇局面可分為交叉相遇(他船位于區域A、區域B和區域D)，追越(他船位于區域C)，對遇(他船位于區域E)等3種。船舶會遇局面劃分見圖2。

圖2 船舶會遇局面劃分

依據避碰規則第13～15條的規定:當船舶之間有碰撞風險，如果他船位于區域A、區域B或E時，本船為讓路船舶，要進行避碰操作；而當他船位于區域C或區域D時，本船為直航船舶，只有當讓路船舶沒有進行避碰操作或形成緊迫局面時，本船才需要進行避碰操作;當他船位于區域A或區域E時，本船舶通常要右轉向進行避碰操作，盡可能地從他船的艉部穿過；當他船位于區域B時，本船可減少船舶速度或左轉向進行避碰。

2 船舶碰撞危險度

船舶碰撞危險度(Collision Risk Index，ICR)是船舶之間可能發生碰撞事故的度量[10-11]，其值域為[0,1]，當ICR=0，說明船舶之間不存在碰撞風險，可自由航行；當ICR=1,說明船舶必然會發生碰撞；當ICR達到或超過某個閾值時，本船或目標船就必須要采取避碰行動，否則將會發生碰撞事故。ICR通常具有不確定性和模糊性等特點，目前還沒有公認的計算方法或模型。影響ICR大小的因素有很多個，本文采用最近會遇距離(Distance of Close Point of Approaching,dCPA)和最近小會遇時間(Time to Close Point of Approaching,tCPA)來確定ICR，從而確定避碰時機。

船舶在會遇與避碰階段，可通過船舶自動識別系統(Automatic Identification System,AIS)、自動雷達標繪儀(Automatic Radar Plotting Aid,ARPA)等獲得船舶的速度、位置坐標、航向、相對位置等避碰數據。假設本船的初始位置為(x0,y0)、船速為v0、航向為θ0，目標船的初始位置為(xT,yT)、航速為vT、航向為θT：

令

Δx=xT-x0,Δy=yT-y0

(1)

A=vTsin(θT)-v0sin(θ0)

(2)

B=vTcos(θT)-v0cos(θ0)

(3)

則任意時刻t兩艘船舶之間的距離可表示為

[d(t)]2=[(xT-x0)+(vTsinθT-v0sinθ0)t]2+

[(yT-y0)+(vTcosθT-v0cosθ0)t]2

(4)

再代入Δx、Δy、A、B可得

(5)

式(5)為關于時間t的二次方程，其最小值就是dCPA的數值，再對時間t求一階導數為

(6)

將其代入(5)中，就可求出dCPA。使用此方法可與船舶上的助航儀器銜接，并可依據求得的tCPA的數值確定本船與目標船是否存在碰撞風險，如求得tCPA<0，說明船舶之間的距離越來越大，船舶之間不存在碰撞風險。

將dCPA與tCPA作為數據輸入，采用模糊綜合評判建立ICR的計算方法[12-13]為

(7)

式(7)中：u(dCPA)與u(tCPA)分別為dCPA與tCPA所采用的隸屬度函數，其表達式為

u(dCPA)=

(8)

(9)

式(8)和(9)中：d1和d2分別為船舶最小安全會遇距離和安全通過距離，通常d2=2d1,t1和t2分別為船舶碰撞時間和注意時間。[13]

當船舶做出避碰決策時，最重要的就是對避碰決策的安全性進行分析，而最有效的辦法就是計算本船與所有會遇船舶的ICR值，當所有的ICR值在可接受的區間內，可認為決策是安全的。

3 基于PSO-GA混合優化算法的船舶避碰決策研究

3.1 PSO算法與GA算法概述

PSO算法起源于鳥類的覓食行為，將問題的搜索空間類比成鳥類的飛行空間，將每只鳥抽象成一個無質量與體積的微粒，用以表示問題的一個候選解，而鳥類尋找食物的過程則是優化所需要尋找最優解的過程。

在PSO算法中，粒子i在N維空間里的速度和位置都表示成一個矢量。N維目標搜索空間中第i個粒子的速度與位置分別表示成vi=[vi1,vi2,…,vid]與向量Xi=[xi1,xi2,…,xid]。在搜索迭代過程中，用目標函數評價各粒子，以確定t時刻每個粒子的最佳位置Pbest和群體所找到的最佳位置gbest，更新粒子的位置與速度為

vij(t+1)=vij(t)+c1r1(pi-xij(t))+

c2r2(pgj-xij(t)),j=1,2,…,d

(10)

xij(t+1)=xij(t)+vij(t+1),j=1,2,…,d

(11)

式(10)和式(11)中：c1和c2為學習因子；r1和r2為0到1均勻分布的隨機數。在PSO算法中還需要設置粒子的速度范圍[vmin,vmax]和位置區間[xmin,xmax]，從而對粒子的移動進行限制。

GA是一種借鑒生物進化規律(適者生存，優勝劣汰)演化而來的隨機優化搜索技術。GA的主要特點是不存在求導和函數連續性的限定，而是直接對參數進行編碼運算。為防止陷入局部最優的陷阱，GA會沿著多種路線進行平行搜索，從而具有內在的隱并行性和更好的全局尋優能力。GA的全局搜索能力強，可克服PSO算法容易陷入局部最優的缺點，基于PSO-GA的混合優化算法對于函數尋優具有加速的作用。

本文對PSO算法中粒子群尋優過程中引入GA中的交叉和變異操作。[14]交叉時，先隨機確定一個位置進行交叉，然后比較新舊個體的適應值。若適應值好于原個體，則進行替換；否則保持原個體。而變異操作采用正態變異，首先確定一個要變異的位置，然后產生一個服從正態分布的點來取代原來的位置。因為正態分布變異是小概率變異，所以不會引起優勢個體的丟失。

3.2 PSO-GA算法的參數編碼

PSO-GA算法的參數空間是用編碼空間來代替的，然后以適應度函數作為評價依據來完成種群的不斷更新，從而建立起一個搜索尋優的過程，最終通過不斷的迭代找到問題的最優解。

當船舶存在碰撞風險而進行避碰操作時，船舶可采用變速、轉向以及兩者相結合等3種避碰方式。據文獻[15]的研究分析，在大多數情況下，即使是多船之間的會遇避碰，船舶都能夠采用一次轉向或變速的操作來成功完成避碰，而且使用最多的避碰操縱是轉向，一般較少采用同時轉向和變速的避碰操作措施。因此，本文采用轉向避碰操縱來完成船舶避碰。為提高尋優速度，本文對轉向避碰操作中的2個重要參數進行編碼。

3.2.1船舶的轉向幅度θ

為滿足避碰規則“大幅度”的要求，轉向的幅度通常要求至少為30°。但轉向幅度過大，會使船舶大范圍的偏離原始航線，增加不必要的能源消耗。可將轉向幅度設定為[30°, 60°]。在轉向避碰過程中，讓路船舶通常通過右轉向來避免碰撞，一般不建議船舶左轉向。[16]因此,在PSO-GA算法避碰優化過程中右轉向為優先操縱。因研究的范圍是互見中的開闊水域，當船舶完成轉向的避碰操縱后，船舶將返回原來的航向，但不會回到初始的航線上。

3.2.2船舶在新航向上的航行時間t

船舶在新航線上的航行時間，若過短會使其他目標船無法正確地判斷本船下一步會讓行動，同時也會增加船舶的操縱難度；若時間過長，則會使船舶嚴重的偏離原始航線，增加復航的難度,因此將其限定在區間[tmin,tmax] 。船舶在新航向上航行時間t后就執行復航操作，回到原始航向上。

3.3 初始種群的產生

根據COLREGs的要求和船員與專家的先驗知識隨機產生初始種群，并在速度約束和位置范圍內初始化種群。

3.4 適應度函數

3.4.1安全性目標函數

在船舶決策過程中，決策的目標是在COLREGs的要求下，找到一條安全經濟的避碰航線，而安全性是最重要的影響因素。在船舶會遇中，船舶可先確定dCPA值最小的目標船舶，采用避讓重點船舶的方式進行避碰，即希望船舶在避碰的過程中能以相對較大的dCPA完成避碰。由此，可設安全性目標函數為

(12)

式(12)中：f1為種群中個體i的安全性目標函數值；N為目標船數目；dCPAir為種群中個體i與目標船舶r的最近會遇距離，安全性目標函數的值越大，碰撞風險也越就小。由式(4)和式(5)可知：dCPA為關于轉向幅度與航行時間的函數。

3.4.2經濟性目標函數

為降低經濟損失，要求在新航向上的里程不能過長，并且船舶在轉向避碰操縱中的幅度不能過大，但又要盡量保證避碰路徑的平滑，可設經濟性目標函數為

(13)

(14)

式(13)和式(14)中：f2、f3為種群中個體i的經濟性目標的函數值；θi為轉向幅度，將轉向幅度設定為[30°, 60°] ,v0為船舶速度。由于上述3個適應度函數的值域相同，可將3個多目標函數分配權重化簡為以下的單目標函數為

minf(x)=af1+bf2+cf3

(15)

式(15)中：a、b、c都為權重系數，a取0.6，b與c都取0.2。

3.4.3PSO-GA算法步驟

(1) 船舶相關數據初始化，獲取本船舶與目標船舶的相關信息，如航向、航速、相對距離和相對速度等。

(2) 根據船舶運動與避碰的數學模型，分析船舶會遇情況，如果本船舶周圍沒有與之會遇的船舶，則本船舶保持原來的航速和航向自由航行，否則轉步驟(3)。

(3) 計算ICR值，確定重點避讓船并結合COLREGs的要求，分析船舶之間的避讓責任：如果是直航船舶，則進行保向保速；如果是讓路船舶，則轉步驟(4)。

(4) 當船舶之間的ICR≥0.5時，船舶進入避碰程序，啟動優化算法。

(5) 設置算法的相關參數，根據經驗或規則要求產生初始種群。

(6) 計算每個粒子的適應值；根據粒子的適應值，得到粒子的個體最優位置和全局最優位置。

(7) 引入GA的變異交叉操作，對全部粒子進行變異交叉操作，再把每個粒子將其個體最優位置和全局最優位置進行比較，若較好，則作為當前全局最好位置。

(8) 更新粒子的速度和位置，同時為保證避碰路徑的平滑，將船舶避碰路徑的搜索中心區域的范圍限定在個體粒子和全局粒子所找到的個體最優值與全體最優值的最大距離的中間位置，以此為依據完成對船舶避碰路徑的智能搜索以獲得最優避碰操作策略。

(9) 船舶避碰行動完結進行復航，回到初始航向。

4 仿真案例研究

4.1 數值仿真驗證

為驗證PSO-GA算法的有效性，選用經典的Ackley函數與Schaffer函數進行算法驗證。這兩類函數存在非常多的局部最優陷阱，搜索全局最優位置較為困難。兩類函數圖形形狀與最優解情況見表1，其三維圖見圖3。

表1 經典測試函數

a) Ackley函數

b) Schaffer函數

設置種群數量為100個，粒子的更新速度范圍為[-1,1]，學習因子c1與c2均設為2，交叉概率設為0.70，變異概率設置成0.01，算法的迭代次數設為50次。分別運用GA、PSO、PSO-GA算法對Ackley函數與Schaffer函數進行尋優計算，得到適應度曲線分別見圖4。

a) Ackley函數的算法優化過程

b) Schaffer函數的算法優化過程

對比圖4適應度曲線，相對于單純的GA與PSO算法，基于PSO-GA混合優化算法的尋優在迭代收斂性、穩定性、精度上都是最佳的，能夠以較快的速度與較少的種群規模進化得到最優解。

4.2 多船避碰仿真

本文對3艘船舶之間的會遇展開研究，每艘船舶的初始位置、航行速度、航行方向見表2，船舶的初始會遇態勢見圖5。

表2 船舶會遇態勢設置

圖5 船舶初始會遇態勢

由表2和圖5可知：假設3艘船舶都遵守COLREGs，則本船OS需要給兩艘目標船都讓路，而TS2要優先避讓TS1，則問題轉化為：當船舶之間達到一定的碰撞危險度(這里當ICR≥0.5)，啟動PSO-GA算法，為本船找到一條最優避碰路徑，使其成功避讓目標船舶TS1和TS2；為目標船TS2找到一條最優避碰路徑，使其成功避讓本船OS與目標船舶TS1。3艘之間的相關數據見表3。

表3 船舶會遇相關數據

啟動PSO-GA算法對本船OS與目標船TS2進行避碰路徑規劃，為保證算法的可行性和有效性，執行15次運算，得到本船舶OS的平均最優值為(30, 0.15)，即本船的最優避碰操作是：右轉向30°，在新航向上航行0.15 h完成避碰，然后恢復到初始航向繼續航行。算法的迭代過程與結果見圖6。在此避碰路徑下本船舶與目標船舶TS1、TS2的ICR值向量是(0.039, 0.023)，避碰效果良好，算法得到的結果可行。將PSO-GA得到的結果與PSO、GA進行對比見表4。

圖6 本船OS算法迭代過程

表4 3種算法的最優解迭代比較

從得到的結果可看出:PSO-GA算法能夠在約束條件下迅速地找到函數的極值點，全局搜索能力快，而且沒有陷入局部最優，在50次內就能夠收斂于最優值。同理，算法經過仿真得到目標船TS2平均最優值為(41, 0.18)，即TS2最佳轉向幅度為右轉41°，在新航向上航行0.18 h。在此轉向幅度下TS1與本船OS、目標船舶TS2的ICR值向量是(0.033，0.057)，見圖7。

圖7 目標船TS2算法迭代過程

5 結束語

在綜合考慮COLREGs和良好船藝要求的基礎上，通過dCPA和tCPA來計算船舶碰撞危險度。對避碰操作過程中的轉向幅度與在新航向航行時間2個重要參數進行編碼，建立基于轉向幅度與航行時間的避碰目標函數，利用PSO-GA算法能夠有效地提高收斂精度和加速全局尋優速度的特點，獲得最佳轉向幅度及在新航向上所需的航行時間。仿真結果表明：PSO-GA算法能夠得到滿意的最優解，為船舶駕駛人員提供一定的避碰決策參考，有助于提升船舶駕駛員在機器輔助下的避碰決策化水平。假設所有船舶都遵守避碰規則，并且認為船舶之間都會實時地獲得周圍船舶的避讓行動，但在實際海上多船會遇局面下可能會出現人為失誤或會遇船舶之間避碰措施不協調等情況。因此，在未來的工作中，將進一步考慮COLREGs和船員良好船藝的要求，設置會遇船舶避碰措施不協調的場景，對避碰決策進行訓練與學習，提高對避碰決策失誤的認識水平，提升避碰決策算法的可靠性。[17-18]