基于改進蟻群算法的船舶避碰路徑規劃決策支持

江冠超 肖英杰 徐笑鋒

上海海事大學商船學院

0 引言

隨著航運業的發展，船舶逐漸大型化和專業化，航行速度越來越快，并且海上交通環境日益復雜、交通密度日益增大[1]。種種變化帶來一個嚴峻的問題，即避碰決策時間縮短，增加了駕駛員的壓力導致作出錯誤的決策，進而釀成海上事故。解決這些問題有兩種途徑：一是加強對船員的技術和心理培訓，提高船員的素質和技術；二是提高避碰決策的自動化程度，通過實現自動避碰，避免船員主觀判斷的錯誤[2,3]。通過技術提高避碰手段，實現船舶自動避碰，減少對主觀判斷的依賴是解決人為因素問題的有效途徑。因此，船舶避碰決策支持系統的研究對船舶安全具有十分重要的意義。

避碰決策支持系統不僅考慮相關的危險和避碰措施，還需要考慮偏離原航線的情況，即船舶避碰路徑。船舶避碰路徑規劃是一個多準則、非線性規劃問題，必須在航行安全與經濟之間尋求平衡。馬文耀等[4,5]提出以船舶避碰轉向后至復航回到原航向的航行距離為目標函數，通過算法求出最優的避碰路徑。于家根等[6]提出將最近會遇距離和轉向角度作為兩個目標函數，通過賦予權重構成單一目標函數，通過算法尋找最優路徑。曾勇等[7]提出轉向角度、航行距離及最近會遇距離構成三個目標函數，賦予權重構成單目標函數。劉冬冬等[8]提出以偏航時間、避碰水域寬度和總航行距離為目標函數的最短避碰路徑。劉仁偉等[9]提出考慮風、流及岸壁淺水等環境因素的船舶碰撞危險度量化模型。趙舟等[10]提出以碰撞危險度和轉向角度值的負函數表示能夠反映決策中避碰安全、路徑優化的目標函數。目前大多數避碰路徑規劃模型沒有對安全性經濟性量化或者沒有考慮復航。蟻群算法在路徑規劃問題中的應用，需要將規劃區域網格化產生坐標點進而轉化成類似旅行商的問題[11-15]。在現有的蟻群算法應用中，還不能直接將蟻群算法應用于非線性函數尋優問題。

本文綜合考慮前人的研究，分析不足，對以最近會遇距離衡量碰撞危險度和航行距離兩個指標進行綜合考慮，提出構建隨最近會遇距離增大而函數值增大的歸一化目標函數和隨航行距離減小而函數值增大的歸一化目標函數，并量化賦予權重進而構成單目標函數。針對在路徑規劃中蟻群算法不能直接用于非線性函數尋優問題，提出改進蟻群算法的轉移概率公式及信息素更新公式。通過改進的蟻群算法對目標函數模型尋優，得到最優避碰路徑參數：避碰轉向角度、復航轉向角度、復航時間。

1 兩船會遇態勢

根據《1972年國際海上避碰規則》（以下簡稱規則），兩艘機動船相遇時，其會遇態勢分為三種，分別為對遇、交叉相遇、追越，如圖1所示。

圖1 會遇態勢

對遇，即兩船船首向正在相反或接近相反的航向上，一般解釋為左右偏差不超過6°（A 區域）。此時，本船應向右轉向。交叉相遇，即當兩船船首向交叉時，來船處于本船航向左右大于6°且小于112．5°的方位（區域B、C、E、F）。交叉相遇根據交叉角度，又分為小角度交叉、大角度交叉。區域B、F為小角度交叉，區域C、E 為大角度交叉。根據規則“讓紅不讓綠”，有它船在區域B、C 時且兩船構成碰撞危險時，本船應為讓路船。追越，即一船從它船正橫后大于22．5°的某一方向趕上它船時（D 區域）。此時，追越船應讓路給被追越船。

2 轉向避碰路徑規劃模型

當本船需采取行動避碰時，一般通過轉向來達到避碰效果。船舶執行轉向避碰行動之前會考慮碰撞危險度和航行距離等指標。碰撞危險度與很多因素有關，比如最近會遇距離dCPA、最近會遇時間tCPA、船舶操縱性能以及環境因素等。本文僅考慮最近會遇距離dCPA和最近會遇時間tCPA，忽略船舶操縱性能和外界環境對轉向避碰的影響。設避碰決策的目標函數模型為：f=(f1, f2, ．．． , fn)，表示避碰決策與避碰危險度及航行距離等多個子目標函數有關。當目標函數模型取最大值時所對應的參數即為最優避碰路徑的參數。

2.1 碰撞危險度目標函數模型

綜合考慮國際海上避碰規則和船東利益，船舶最優避碰路徑是一條既安全又經濟的避碰路徑。在安全性及經濟性中，安全又是極為重要的因素，因此，首先考慮關于避碰路徑的安全因素。衡量船舶避碰后碰撞危險度指標可以用轉向后的最近會遇距離dCPA和最近會遇時間tCPA衡量，其值越大避碰效果就越好。如圖2 所示，船舶在采取避碰措施時兩船會遇距離為D，由劉德新等[16]提出的決策模型可得：

圖2

其中，θ 為轉向后兩船相對運動線與目標船方位線夾角，A為轉向后兩船相對運動線與本船船首向夾角，△C0t為轉向后兩船航向線夾角，△C0為本船轉向角度，Vr為轉向后兩船相對運動速度，D 為兩船轉向后的距離，V0為本船速度，Vt為目標船速度。

由公式（1）～（5）可以計算得到dCPA及tCPA。

由公式（1）可見，船舶轉向避碰后最大的最近會遇距離maxdCPA=D，即θ=90°時。從安全角度考慮，dCPA越大安全性越高，構建兩船碰撞危險度目標函數f1：

式（6）中，f1值域為[0,1]，且最近會遇距離越大，其函數值越大。

2.2 航行距離目標函數模型

航行距離指船舶避碰轉向后到復航回到原航線上所行駛的路程d。這段路程分為兩部分：避碰轉向到復航轉向的路程d1和復航轉向至回到原航向的路程d2。因避碰行動只轉向而沒有改變速度，設避碰轉向角度△C0，復航轉向角度△Cr，避碰轉向到復航轉向時間為T0。則

根據規則第16 條規定，讓路船應該大幅度行動，綜合考慮環境因素以及人為因素，限制以下約束條件：△C0=[30°, 90°]，△Cr=[30°, 60°]，T0=[tCPA1,60 min]，tCPA1為轉向后的最近會遇時間。構建本船航行距離目標函數f2：

式（8）中，f2值域為(0,1]，且d 越小，其函數值越大。

2.3 總目標函數模型

所構建的碰撞危險度目標函數及航行距離目標函數的值域都為[0,1],且取值越優函數值越大。若對兩個目標函數分別賦予權重α、β（α+β=1），則多目標函數構成單目標函數f：

對f 求最大值，其最大值所對應的參數即為最優避碰路徑的參數：避碰轉向角度、復航轉向角度、復航時間。

3 蟻群算法

3.1 蟻群算法模型

蟻群算法是一種模擬螞蟻覓食過程的概率型算法，它具有啟發式搜索及正反饋信息的特征[10]。它能夠求得從原點出發，途經若干個需求點回到原點的最短路徑，被廣泛應用在旅行商問題。設螞蟻數量m，點數為n，點與點之間的距離為dij(i,j=1,2,．．．,n)，t時刻i與j連線上信息素為τij(t)、距離啟發函數為ηij(t)，由所參考的文獻[17,18]可得，t 時刻第k 只螞蟻從i到j的轉移概率為：

3.2 改進蟻群算法

本文所構造的目標函數模型是非線性函數極值尋優問題。從所參考的文獻上發現，蟻群算法較多用于TSP 問題及其衍生問題上，即問題需要有坐標點，通過網格化坐標點得到轉移概率，進而求出最短路徑。受式（10）轉移概率公式的啟發，在非線性函數尋優問題中，可行解轉移概率為：

式（13）中，rand為[-1,1]之間的隨機數，p0為概率常數，當pi＜p0時，x(t+1)進行局部搜索；當pi≥p0，x(t+1)進行全局搜索。由式（11）信息素更新的啟發，在非線性函數求極值問題中，信息素更新為：

由式（12）、（13）、（14）構造出可用于非線性函數尋優的蟻群算法。

3.3 算法流程

步驟1：將參數初始化。蟻群規模，最大迭代次數，信息素揮發因子，信息素釋放因子，轉移概率常數，本船與來船航向航速，來船方位等。

步驟2：建立解空間。初始時，對螞蟻隨機分散置于不同位置，然后根據轉移概率對每個螞蟻確定下一個位置。

步驟3：信息素更新。根據信息素更新公式對每個位置信息素進行更新，同時記錄當前計算中的最大值。

步驟4：終止判斷。若當前迭代次數達到最大迭代次數，結束算法，輸出最大值；否則，返回步驟2。如圖3所示。

4 仿真實驗結果

設本船航速為12 kn，航向000°，目標船航速為12 kn。綜合考慮安全與經濟的重要性，取α=0．6，β=0．4。根據規則，通過模擬對遇、小角度交叉相遇、大角度交叉相遇三種態勢驗證避碰模型。為驗證算法有效性，避免隨機性，重復執行20次算法過程。

對遇：目標船航向180°，方位000°，距離5 nm，其matlab仿真結果顯示，除個別值外其目標函數值的范圍為[0．581 2, 0．598 3]，最優值迭代過程如圖4所示；小角度交叉相遇：目標船航向240°，方位040°，距離5 nm，仿真結果顯示，除個別值外其目標函數值的范圍為[0．527 1, 0．543 0]，最優值迭代過程如圖5 所示；大角度交叉相遇：目標船航向280°，方位050°，距離5 nm，仿真結果顯示，除個別值外其目標函數值的范圍為[0．415 9, 0．432 1]，最優值迭代過程如圖6 所示。三種會遇態勢仿真結果，最優目標函數值所對應的避碰轉向角度、復航轉向角度、避碰轉向到復航轉向時間、最短航行距離見表1。

圖3 基于改進蟻群算法的目標函數尋優模型

表1 基于改進蟻群算法的最優避碰路徑參數

分析仿真結果，此目標函數模型能夠在綜合考慮安全性與經濟性權重后給出最優避碰路徑。改進后用于非線性函數尋優的蟻群算法結果可以在迭代50 次內收斂于某一固定值，收斂速度較快；算法運行時間3～6 s，計算速度較快；重復執行20 次算法后，除個別值外，目標函數值穩定在很小的范圍內：對遇態勢下范圍[0．581 2,0．598 3]，小角度交叉態勢下范圍[0．527 1, 0．543 0]，大角度交叉態勢下范圍[0．415 9,0．432 1]，此算法可行。

圖4 對遇目標函數最優值

圖5 小角度目標函數最優

圖6 大角度目標函數最優

5 結束語

在開闊水域兩船不同會遇態勢下避碰路徑規劃問題中，本文提出一種基于改進蟻群算法的避碰路徑規劃決策方法。以最近會遇距離指標及航行距離指標建立歸一化的非線性目標函數模型，改進蟻群算法的概率轉移公式及信息素更新公式。結果表明，改進的蟻群算法在非線性函數尋優中應用效果較佳，迭代過程收斂較快，計算速度較快；綜合考慮安全性及經濟性權重后，目標函數模型可以規劃出最優的避碰路徑。此路徑規劃決策如果能應用在電子海圖顯示及信息系統中，將有效減輕船員壓力，減少海上碰撞事故。