基于克隆選擇優化的多船轉向避碰決策

胥 文，胡江強，尹建川，李 可

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

0 引 言

國際海事組織一直致力于解決船舶碰撞和安全問題。盡管這樣，仍有大量數據表明，國際上每年失事船舶中有超過40%是因為碰撞導致的，且其中近80%的事故是人為原因造成的[1–3]。日益擁擠的海上交通環境、快速發展的航海技術以及與人為失誤有關的海難事故，促使船舶避碰的研究進一步深入，而自動避碰決策是其中的核心和難點問題，一個較成熟的自動避碰決策系統要求在滿足避碰規則（對于港口水域既包括“國際海上避碰規則”也包括“地方規則”）的前提下，適時自動避讓來船（可能是多艘船舶）以及其他障礙物，保證駛過讓清后選擇安全經濟的航線復航。

海上環境復雜多變，因此決策的實時性要求較高，此外還需要考慮對避碰規則的嚴格遵守、能見度、水域受限情況以及船舶類型、操縱性能等，滿足以上條件的自動避碰決策系統將非常復雜，且在未完全感知的環境中進行多船避讓，且規則未對避碰行為進行要求，本身就屬于NP困難問題，最優解難以保證，因此航海界一直致力于尋找更智能、優化的算法來解決船舶避碰決策問題。針對這個問題，學術界在避碰決策模型方面開展了廣泛的研究，一些啟發式進化算法，如遺傳算法、蟻群算法、粒子群算法、模擬退火算法（SA）等[4–7]，以及一些確定性避碰決策方法相繼取得一定的成果。但對于多種算法的混合策略研究不夠，不能全面提高算法的速度和計算結果的精度，存在局部和全局收斂不足的問題，算法的實時性也有待提升。

現代避碰決策技術已經向智能化方向發展。應用較多的避碰決策方法是專家系統（ES），如英國利物浦大學、東京商船大學、廣州艦艇學院等研究單位均研究了用于船舶避碰的專家系統[8–10]，這些避碰專家系統采用咨詢式輔助避碰手段，針對不同的會遇局面給出避碰決策結果。李麗娜[11]提出擬人化智能避碰決策方法，模仿經驗豐富的避碰決策，這種方法較專家系統更為快速，能在短時間內進行局面判斷，精確計算及預測避碰效果，提供決策支持，既可用于單船避碰，又可用于多船避碰。鄭中義和孫立成等[12–14]分別從信息熵理論和神經網絡理論出發研究了船舶避碰決策方法。劉以安等[15]采用模擬退火算法計算多船會遇局面下本船的轉向幅度，并進行3種會遇態勢下的避碰仿真驗證。

在多船會遇態勢下，船舶轉向避碰是采用頻率最高的一種避碰方法。本文從多目標函數全局優化問題出發，基于船舶碰撞危險度和航程損失的多目標函數優化，通過分級變異動態克隆選擇優化算法，在《國際海上避碰規則》約束的可行域空間內，從而在可行空間中找出滿足多目標函數和約束條件的全局范圍內的最優轉向幅度。

1 船舶碰撞危險度計算模型

本文的研究是基于開闊水域下多船會遇態勢下的轉向避碰幅度最優解計算，通過碰撞幾何原理分析可知，影響船舶碰撞危險度大小的因素很多，且互相制約，判斷船舶是否存在碰撞危險度的主要依據是基于船舶領域和動界的概念，對DCPA和TCPA進行綜合考慮。確定了最近會遇距離（DCPA）、最近會遇時間（TCPA）、兩船距離、相對方位、船速比5個主要影響因素的隸屬度函數，并考慮航行區域狀況、能見度情況和船舶的操縱性能等對船舶碰撞危險度的隸屬度函數修正，利用模糊規則和模糊綜合評價方法進行船舶復合碰撞危險度的計算，考慮了船舶微觀和主觀碰撞危險度因素。

基于模糊綜合評價的碰撞危險度計算結果可以作為主觀和客觀評價，通過減小其影響因素來得到最佳的計算結果。所以，本文不采用DCPA和TCPA加權的方法計算碰撞危險度，而是采用模糊綜合評價的方法計算碰撞危險度。文獻[16]中把DCPA、TCPA、兩船距離、相對方位、船速比5個因素作為基本評判參數，并考慮航行區域狀況、能見度情況和船舶的操縱性能等對船舶危險度的隸屬度函數修正。為了更加符合海上避碰行動實際，主要考慮以下5個影響因素：任意時刻目標船和本船的距離、目標船的方位、船速比、DCPA和TCPA。所以，目標影響因素的論域為：

目標影響因素的模糊權重分配如下，權重值根據文獻[16]，取為：

由文獻[17]可知，船舶間距離越小，船舶間碰撞危險度越大。任意時刻船舶間距離的隸屬度函數如下：

d1和d2的大小取決于航行區域的狀況、能見度以及人為因素的影響。動界是以駕駛員開始采取行動以避免緊迫局面時與他船的距離為基礎的超級領域。英國學者Davis等通過大量的調查統計得到了動界模型的具體數據，在進行平滑其邊界后，得到了一個半徑為2.7 n mile的圓的數學模型。令其區域半徑為R，可以得到其表達式：

式中：d1為船舶最晚避讓距離；d2為船舶協調避讓的距離；K1取決于能見度；K2取決于水域情況；K3取決于人為因素；DL為最晚施舵距離，一般取12倍船長[18]；R為任意時刻船舶動界的半徑。

不同方位的目標船對本船所構成的危險程度不同，一般來說右舷大于左舷，正橫前大于正橫后。

任意時刻目標船相對方位角的隸屬度函數，式中θ與本船與目標船的船速比有關：

如果其他參數相同，船速比不同時，其碰撞危險度也不相同。船速比越大，船舶碰撞危險度越大，令W≥0，W=2，0°≤C＜180°，船速比的隸屬度函數：

DCPA小于船舶安全會遇距離時，船舶存在碰撞危險，該值越小，碰撞危險程度越大。任意時刻DCPA的隸屬度函數[21]：

適用于開闊水域的基于船舶領域的船舶安全會遇距離計算時，需要考慮船舶領域存在的模糊邊界FBD[19]，船舶領域進行平滑連續后大小和模糊邊界值的計算如下[20]：

TCPA值大小與碰撞危險度的關系與DCPA類似，任意時刻TCPA的隸屬度函數：

根據模糊綜合評價方法得到目標危險度所有因素的綜合評判結果：

任意時刻的碰撞危險度C2為：

經過計算可以得到目標船的碰撞危險度大小。如果CRI=0，船舶間不存在碰撞危險；如果CRI=1，船舶間一定存在最大碰撞危險；如果CRI∈[0，1]，CRI越大，船舶碰撞危險性越大。

2 轉向避碰多目標函數模型

本文將多船會遇態勢下的轉向避碰作為一類多目標函數優化問題，應用分級變異動態克隆選擇優化算法，從《國際海上避碰規則》約束的可行域空間中找出滿足目標函數和約束條件的最優轉向避碰幅度，使得讓路船采取轉向避碰決策時滿足：1）與各目標船間的碰撞危險度盡量減小；2）轉向避碰幅度盡量小；3）盡量減小轉向到復航過程中的航程損失[21]。

2.1 碰撞危險度目標函數

確定了最近會遇距離（DCPA）、最近會遇時間（TCPA）、兩船距離、相對方位、船速比5個主要因素的隸屬度函數，并考慮航行區域狀況、能見度情況和船舶的操縱性能等對船舶碰撞危險度的隸屬度函數修正。因此，設碰撞危險度目標函數為

2.2 航程損失目標函數

航海避碰實踐中，考慮到《國際海上避碰規則》對避碰行動“大幅度”的要求，航向變化至少為30°；考慮到要減小航程損失，要求轉向幅度盡可能小。因此，航程損失目標函數為

式中：xi為轉向幅度，向右為“+”，向左為“–”；為航程損失函數值，其值域為（0，1]；xi∈[30，90]。目標函數值越小，則轉向幅度和航程損失越小。

假設上述多目標函數函數權重分配為8:2，則轉向避碰目標函數為

3 基于分級變異動態克隆選擇優化的船舶轉向避碰決策

3.1 克隆選擇算法基本原理

克隆選擇算法（Clonal Selection Algorithm）是模擬免疫系統防御外來侵襲的一種學習進化過程。免疫克隆選擇算法是通過無性繁殖（克隆、變異）連續傳代形成群體，通過抗體克隆群的變異來提高免疫力（親和度）從而實現種群的進化。克隆選擇算法雖然克服了遺傳算法局部搜索能力差且常出現進化緩慢現象的問題，但是用較小的變異概率來提高局部搜索能力，降低了全局搜索能力；而較大的變異概率雖然全局尋優速度提高，但收斂的精度下降。因此，其全局搜索能力和局部搜索能力矛盾。

3.2 分級變異動態克隆選擇算法

采用[0，1]區間內的浮點數編碼，以搜索全局最優解為目標，依據抗體與抗原的親和度將種群分化為功能不同的子種群，高親和度抗體在較小領域內精細搜索局部最優解，中親和度抗體在較大鄰域進行全局粗搜索，低親和度抗體則死亡并隨機再生以保持種群多樣性，且在進化中動態調整參數[22]。

4 轉向避碰幅度仿真和結果分析

4.1 仿真實例

已知本船為“育鯤”輪在開闊水域，以航向000°，航速15 kn航行，本船船長為116 m，滿載排水量為5 778.8 t，此時海上能見度良好，船舶操縱者駕駛狀況良好（取K1=1，K2=1，K3=1）。他船船長152 m，滿載排水量為9 879.6 t。與3艘目標船（TS1，TS2，TS3）形成多船會遇態勢，存在碰撞危險且本船為讓路船，采取轉向避碰決策。本船與目標船的會遇態勢如表1所示。

表 1 本船與多目標船會遇態勢Tab. 1 Multi-ship encounter situation

初始種群規模設為N0=100，初始克隆數目nc0=10，對于多目標函數，初始變異尺度變換因子n10=0.05，n20=1.5，分級變異概率為，。

4.2 結果分析

該算法隨機獨立運算100次，算法性能評價準則采用計算量和阻滯次數表示。目標函數變量范圍在[30，90]，目標函數評估次數為12 596±2 153，阻滯次數為0次。

可知分級變異克隆選擇優化算法計算量小，算法穩定。圖1為各代最優解，即本船最優轉向避碰幅度。最終結果收斂于某個固定值，100代內能夠快速趨于穩定，收斂速度快，算法執行耗時4～10 s，能夠保證多船避碰決策的實時性。結果表明，本船作為讓路船在該會遇態勢下應向右轉向約38.5°。轉向后，本船對各目標船（按TS1，TS2，TS3順序）的碰撞危險度分別為（0.233 8，0.334 6，0.273 7），船舶間碰撞危險度均明顯減小，能夠有效避免碰撞。

圖 1 最優解迭代變化Fig. 1 Optimal evolution for iteration

5 結 語

將分級變異動態克隆選擇優化算法應用到多船轉向避碰決策研究中，綜合考慮影響船舶轉向避碰幅度的多種因素，在《國際海上避碰規則》作為可行域約束的限制條件下，建立了相應合理的多目標函數，并考慮到各種因素之間的差異，對目標函數進行權重分配，使模型更加符合航海實際。結果表明：該算法可行、有效、能滿足實時決策等要求，為船舶駕駛員提供轉向避碰決策支持。

[1]AHNA J H, RHEE K P, YOU Y J. A study on the collision avoidance of a ship using neural networks and fuzzy logic [J].Applied Ocean Research, 2012(37): 162–173.

[2]孫立成, 王逢辰, 夏國忠, 等. 駕駛員避碰行為的統計研究[J].大連海事大學學報, 1996, 22(1): 1–6.

[3]江立軍, 鄭凱, 王國峰, 等. 現代船舶避碰系統研究進展[J].

上海船舶運輸科學研究報, 2015.

[4]鄒曉華, 倪天權. 遺傳算法在船舶轉向避碰幅度決策中的應用研究[J]. 艦船電子對抗, 2006.

[5]何祖軍, 齊亮. 基于蟻群算法的AUV動目標避碰規劃的方法研究[J]. 艦船科學技術, 2007(6): 86–89.

[6]王得燕, 劉以安. 粒子群算法在多船避碰決策中的應用[J].計算機工程與設計, 2009(14): 3380–3382.

[7]劉以安, 劉靜, 吳潔, 等. 模擬退火算法在船舶轉向避碰幅度決策中的應用[J]. 中國造船, 2007.

[8]HASEGAWA K, FUKUTO J. An intelligent ship handling simulator with automatic collision avoidance function of target ships [C]// INSLC 17-International Navigation Simulator Lecturers’ Conference. Rostock, Germany, 2012: F23-1–10.

[9]鶴田三郎. 船舶航行專家系統的基礎研究[J]. 國外航海科技.1988(5): 55–58.

[10]王敬全. 船舶避碰專家系統[M]. 廣州: 海軍廣州艦艇學院出版社, 1994.

[11]李麗娜, 楊神化, 曹寶根, 等. 船舶避碰智能決策自動化研究[J]. 集美大學學報(自然科學版), 2006(2): 188–192.

[12]呂紅光, 尹勇, 尹建川. 混合智能系統在船舶自動避碰決策中的應用[J]. 大連海事大學學報, 2015(4): 29–36.

[13]史國友, 賈傳熒. 航海模擬器中DCPA TCPA的算法[J]. 大連海事大學學報, 1999(3): 17–20.

[14]BUKHARI A C, TUSSEYEVA I, LEE Byung-gli, et al. An intelligent real-time multi-vessel collision risk assessment system from VTS view point based on fuzzy inference system[J]. Expert Systems with Applications, 2013: 1220–1230.

[15]FENG Ming-kui, LI Yong-jin. Ship intelligent collision avoidance based on maritime police warships simulation system [C]// IEEE Symposium on Electrical & Electronics Engineering (EEESYM). Kuala Lumpur, Malaysia, 2012:293–296.

[16]KOIKE T, OKAZAKI T. Development of ship simulator system for designing auto-pilot [C]// World Automation Congress (WAC). Kobe, Japan, 2010: 1–5.

[17]SUI Jiang-hua. An AND-OR fuzzy neural network, ant colony optimization-methods and applications [C]// IEEE International Conference on Robotics and Biomimetic. Sanya, China, 2007:1194–1199.

[18]薛彥卓, 魏伊, 孫淼. 基于避碰重點船算法的多船避碰模擬[J]. 大連海事大學報, 2014(1): 13–16.

[19]HASEGAWA K. Automatic collision avoidance system for ship using fuzzy control [C]// Proc Eighth Ship Control Systems Symposium (SCSS). The Hague, Netherlands, 1987:34–58.

[20]于家根, 劉正江, 卜仁祥, 等. 基于擬態物理學優化算法的船舶轉向避碰決策[J]. 中國航海, 2016(1): 36–38, 109.

[21]胡江強, 郭晨, 尹建川, 等. 分級變異的動態克隆選擇算法[J].控制與決策, 2007(6): 608–612.