基于遺傳算法的船舶避碰系統(tǒng)

李世友

摘 要：隨著全球經(jīng)濟的飛速發(fā)展，經(jīng)濟貿易往來日益頻繁，海上運輸變得越來越頻繁，海面上船舶密度不斷增大，各類船舶間發(fā)生碰撞概率也不斷增大。基于遺傳算法研究船舶自動避碰策略并構建了一個避碰演示系統(tǒng)進行仿真驗證。定義了確保安全距離下的最短復航路程作為適應度函數(shù)并建立碰撞危險模型并分析其避讓責任及相應的避碰決策?；贛atlab構建了一個簡單的仿真平臺對避碰算法進行仿真驗證。仿真結果驗證了基于遺傳算法的避碰策略的有效性。

關鍵詞：船舶自動識別系統(tǒng);船舶避碰;遺傳算法;適應度函數(shù)

中圖分類號：U664.82? ? ? ? ? 文獻標識碼：A? ? ? ? ? ? 文章編號：1006—7973（2021）12-0045-04

隨著全球海運事業(yè)的快速發(fā)展，使得航線上船舶密度不斷增大，隨著船舶數(shù)量增多，也給海上交通的監(jiān)控和管理帶來嚴峻的挑戰(zhàn)。據(jù)中國海上搜救中心發(fā)布的數(shù)據(jù)來分析，由船舶碰撞造成的險情占海上事故的五分之一[1]。因此，船舶避碰是海面航行安全研究的熱點問題之一[2～9]。早在上世紀90年代末21世紀初就有許多相關研究，例如文獻[2]提出了利用框架式專家系統(tǒng)與數(shù)理分析相結合的仿人智能避碰方法;文獻[3]基于信息熵理論研究評價了在交叉相遇局面中讓路船舶兩船間初始船舶安全距離和距離采取避碰行動種類的不確定性;文獻[4]分析了航海避碰專家系統(tǒng)軟件開發(fā)的必要性與緊迫性并對整個軟件開發(fā)的思路、方法及軟件要求作了論述，同時還建立了船舶避碰危險度的數(shù)學模型;文獻[5]在研究船舶碰撞危險度的基礎上建立船舶動態(tài)避碰行動領域模型。

最近幾年許多學者從不同角度開展船舶避碰相關的理論分析或者系統(tǒng)研究。胥文等2017年在船舶碰撞幾何原理的基礎上利用模糊規(guī)則和模糊綜合評價方法提出一種船舶復合碰撞危險度的計算方法并進行了仿真分析[6];2019年倪生科等針對不同會遇態(tài)勢下的船舶避碰路徑規(guī)劃問題建立一種基于遺傳算法和非線性規(guī)劃理論的船舶避碰路徑規(guī)劃模型[7];崔瑾娟通過尋找船舶運動最優(yōu)最短的避碰路徑提出了遺傳算法規(guī)劃路徑的船舶避碰系統(tǒng)[8]。

遺傳算法（genetic algorithms， GA）[9]是一種元啟發(fā)式自然選擇的過程，屬于進化算法（EA）大類。遺傳算法本身具有優(yōu)勝劣汰的能力，在船舶避碰領域得到廣泛應用[6～9]。本文利用遺傳算法來進行船舶避讓的最優(yōu)避碰路徑規(guī)劃。首先介紹了船舶避碰系統(tǒng)的組成以及船舶避碰的遺傳算法描述，并定義了確保安全距離下的最短復航路程作為適應度函數(shù)f。在此基礎上，根據(jù)對船舶運動參數(shù)進行計算來建立碰撞危險模型并分析其避讓責任及相應的避碰決策。其次構建了一個簡單的仿真平臺對避碰算法進行仿真驗證，分別以兩船的對遇和交叉情況來進行驗證，實現(xiàn)以上兩種情況下的仿真，來驗證算法的有效性。

1船舶避碰系統(tǒng)組成遺傳算法描述

1.1船舶避碰的遺傳算法描述

本文采用的避碰規(guī)則為國際避碰規(guī)則，即《1972年國際海上避碰規(guī)則》[10]（下文簡稱《規(guī)則》）?！兑?guī)則》將兩船之間的會遇態(tài)勢總分為三種局面：對遇、交叉相遇和追越。遺傳算法的基本流程如圖1所示。

其主要操作步驟如下：第一步，隨機產(chǎn)生一個種群，作為問題的初代解;第二步，尋找一種合適的編碼方案對種群中的個體進行編碼，可以選擇如浮點數(shù)編碼或二進制編碼等常用編碼方案;第三步，以多峰函數(shù)的函數(shù)值作為個體的適應度，計算種群中每個個體的適應度（算出的適應度將為后續(xù)的個體選擇提供依據(jù)）;第四步，根據(jù)適應度的高低選擇最合適的個體，并以此不斷淘汰適應度低的個體;第五步：對篩選出的個體進行遺傳操作，找到最優(yōu)解;第六步：根據(jù)一定的準則判斷是繼續(xù)執(zhí)行算法，還是找出所有子代中適應度最高個體作為解返回并結束程序。

1.2遺傳算法操作

具體遺傳操作分為編碼、群體設定、定義適應度函數(shù)、選擇遺傳算子等操作。其中，選擇遺傳算子包括交叉算子、變異算子、遷移算子等。

1.3定義適應度函數(shù)

在GA中，很少使用搜索空間以外的知識以及通過其他方式獲得的其他輔助信息，而是使用設計好的適應度函數(shù)來評價每個個體的優(yōu)或者劣。適應度高的，也就是優(yōu)秀的個體有更大的幾率參與繁衍，遺傳自己的基因。一般的，適應度函數(shù)根據(jù)目標函數(shù)來確定，有時候直接將目標函數(shù)值作為適應度。

本文采用確保安全距離下的最短復航路程作為總適應度函數(shù)。該適應度函數(shù)包括安全性適應度、路徑總長適應度和航線偏離適應度三個適應度。這三個適應度分別定義如下：①安全性適應度，其中為避碰過程中時刻本船的路徑點與對應時刻干擾船之間的安全性，由安全距離決定，如果距離大于安全距離，則為1否則為0;②路徑總長適應度，其中為避碰過程中從時刻到時刻本船經(jīng)過的路程，則代表從采取避碰措施偏離原來航線到復航至原來的航線上的實際避碰航線的總長度;③航線偏離適應度點路： 其中為在避碰過程中實際位置與原航線的對應時刻的對應位置之間的偏移距離。上述定義中的代表時刻?？傔m應度函數(shù)，其中為路徑長度和偏離度的權重，且滿足。時刻的總適應度函數(shù)。

2 船舶避碰仿真系統(tǒng)設計

2.1船舶避碰仿真系統(tǒng)界面設計

本文在MATLAB GUI界面下設計船舶避碰系統(tǒng)的仿真界面并對避碰算法進行仿真驗證。本文設計的船舶避碰系統(tǒng)的仿真界面如圖2所示。該船舶避碰仿真界面主要設計了本船和臨近干擾船的相關參數(shù)，包括初始位置、目標位置及速度等信息，用來模擬AIS的數(shù)據(jù)源。

2.2船舶避碰仿真系統(tǒng)軟件設計

在船舶避碰仿真程序的設計過程中，通過輸入本船與干擾船的相關參數(shù)，模擬AIS的監(jiān)測結果，完成程序的初始條件設定。設置了本船與干擾船之間對遇與交叉會遇的兩種狀態(tài)，通過調用第1節(jié)的遺傳算法，最終得到最優(yōu)避碰路徑。船舶避碰系統(tǒng)的主程序流程圖如圖3所示。

3 基于AIS數(shù)據(jù)的避碰仿真

3.1基于天拓三號星載AIS數(shù)據(jù)的船舶交叉案例

本節(jié)首先給出一個基于真實星載AIS數(shù)據(jù)的船舶交叉的案例。國防科技大學2015年發(fā)射了我國第二顆AIS微納衛(wèi)星[11]。天拓三號星載AIS載荷是我國第二代星載AIS，優(yōu)勢在于它擁有更好的覆蓋范圍，極大地提高了信號偵收能力;并且，天拓三號的AIS系統(tǒng)實現(xiàn)了對每一條信息的精確時間顯示，為今后實現(xiàn)對海面船舶進行連續(xù)跟蹤與監(jiān)視提供了良好的技術基礎[13]。

圖4給出兩船交叉會遇的例子。A船最初位置的經(jīng)緯度為（121.0760， 27.2450），B船所在的位置為（121.0760， 27.3450），兩船舶航行方向成一個夾角，兩船最初的相距11.1195公里，經(jīng)過一段時間的航行，兩船之間的距離不斷減少，最終在A船所在位置為（121.6640，27.3250），B船所在位置為（121.6640，27.3450），兩船舶的距離為2.2239公里。兩船小于最小預警距離（3公里），如果不采取避碰措施，兩船將很快相撞。

3.2船舶交叉會遇避碰仿真分析

以3.1小節(jié)的例子為藍本對兩船交叉會遇進行兩船交叉避碰仿真分析。本船與干擾船（來船）的初始會遇態(tài)勢如圖5所示。圖中，紅色方框和黑色圓圈分別代表本船和干擾船的初始位置;紅色實線和黑色實線分別表示本船和干擾船的初始航線。本船的航速為14.4 kn，本船的航向45°;干擾船的航速是也是14.4 kn，干擾船的航向是270°，與本船的相對方位是225°，與本船之間的距離是8.2nmile。兩船安全會遇距離為1.55 nmile，約為2.87 km。當本船與干擾船的距離小于安全距離時，則本船與來船存在碰撞危險，需要采取避碰行動，用避碰算法進行避讓航線選擇。

在兩船交叉仿真中，根據(jù)《規(guī)則》的相關要求，當兩艘機動船交叉相遇致有構成碰撞危險時，有干擾船在本船右舷的船舶應給他船讓路，如當時環(huán)境許可，還應避免橫越他船的前方。因此在遺傳算法控制下，令干擾船保速保向而只讓本船采取向右轉向進行避讓行動。

圖5為兩船在交叉情況下不采取避碰措施和調用遺傳算法進行避碰的仿真結果。上圖為不調用遺傳算法時候的兩船航行狀態(tài)。在此情況下，兩船都沿著既定行駛路線繼續(xù)航行，則在某時刻本船與干擾船會相撞;下圖為調用遺傳算法子程序的時候的兩船航行狀態(tài)，紅色虛線代表本船原來的航線，紅色實線代表避碰航線。調用遺傳算法，使用避碰程序設定干擾船與本船的初始狀態(tài)參數(shù)后，應用隨機的方式產(chǎn)生初始種群，該種群中包括一條初始的路徑。然后利用已經(jīng)尋找到的適應度函數(shù)對每一條初始遺傳算法在船舶避碰行動決策中的應用研究路徑進行相應的評價，最后尋找出初始種群中適應度函數(shù)值最大的一條初始路徑，這條路徑就是我們所要尋找的最佳的初始路徑，如圖5下圖所示。

本節(jié)案例仿真結果表明，在兩船對遇的情況下，本船執(zhí)行避碰策略，在判斷可能存在與干擾船的對遇碰撞的時候通過遺傳算法得到向右轉向的策略從而避免與干擾船碰撞，最終完成與對遇干擾船的避碰過程。結果表明避碰算法是合理可行的。

4 結論

本文基于遺傳算法研究船舶自動避碰策略并構建了一個避碰演示系統(tǒng)進行仿真驗證。首先定義了確保安全距離下的最短復航路程作為適應度函數(shù)。該適應度函數(shù)包括安全性適應度、路徑總長適應度和航線偏離適應度三個適應度。在此基礎上，根據(jù)對船舶運動參數(shù)進行計算來建立碰撞危險模型并分析其避讓責任及相應的避碰決策。其次構建了一個簡單的仿真平臺對避碰算法進行仿真驗證，分別以兩船的對遇和交叉情況來進行驗證，實現(xiàn)以上兩種情況下的仿真，來驗證算法的有效性。仿真結果表明，基于遺傳算法的避碰模型能夠將最優(yōu)良的基因保留下來從而進化出更加強大、更適合生存的基因，從而得到最優(yōu)的避碰航線完成船舶避碰。

本文的研究主要構建仿真平臺進行仿真分析以驗證算法的可行性，下一步將結合實際的AIS數(shù)據(jù)進行實際應用。

參考文獻：

[1]李曉松， 孔憲衛(wèi). 船舶碰撞事故致因及管控措施研究[J]. 水道港口， 2019， 40（3）：313-318.

[2]李麗娜， 陳聰貴. 船舶自動避碰方法的研究[J]. 中國航海， 1999， 22（1）：20-24.

[3]鄭中義， 吳兆麟. 交叉相遇局面中船舶避碰行動的不確定性[J]. 中國航海， 2000， 23（02）：56-61.

[4]楊帆， 劉克中. 船舶智能避碰軟件開發(fā)的研究[J]. 武漢交通科技大學學報， 2000， 24（5）：580-582.

[5]畢修穎， 賈傳熒， 吳兆麟，等. 船舶避碰行動領域模型的研究[J]. 大連海事大學學報， 2003， 24（01）：9-12.

[6]胥文， 胡江強， 尹建川，等. 基于模糊理論的船舶復合碰撞危險度計算[J]. 艦船科學技術， 2017， 39（7）：78-84.

[7]倪生科， 劉正江， 蔡垚，等. 基于混合遺傳算法的船舶避碰路徑規(guī)劃[J]. 上海海事大學學報， 2019， 40（1）：21-26.

[8]崔瑾娟. 基于遺傳算法規(guī)劃路徑的船舶避碰系統(tǒng)[J]. 艦船科學技術， 2019，41（6A）：43-45.

[9]吉根林. 遺傳算法研究綜述[J]. 計算機應用與軟件， 2004， 21（2）： 69-73.

[10]海司航保部. 1972年國際海上避碰規(guī)則[M]. 人民交通出版社， 1978.

[11] LI S Y， CHEN X Q， CHEN L H， et al. Data Reception Analysis of the AIS on board the TianTuo-3 Satellite [J]. The Journal of Navigation， 2017b， doi：10.1017/S0373463316000916.

基金項目：湖南省教育廳優(yōu)秀青年項目（編號18B572）;湖南省自然科學基金資助項目（編號2020JJ4451）。