基于遺傳算法的渡船橫渡航法尋優模型

孫志宏， 索永峰， 楊神化， 劉武藝

(集美大學 航海學院， 福建 廈門 361021)

渡船既是長江兩岸車輛來往、運輸物資重要而便捷的交通工具，也是陸上公路運輸的水上連接線。盡管長江上已呈現增架橋梁的局面，但渡船在長江干線水域的重要地位依然不能完全取代。[1]鑒于具有類似渡船的復雜內河水域交通流密集，船舶位置靈活多變，給渡船橫渡目標水域帶來很大的碰撞風險，在很大程度上增加了該水域的交通壓力。目前，渡船橫渡主要依靠駕駛員根據實時交通狀況做出臨時反應，對駕駛員的要求較高。本文重點研究復雜水域的渡船橫渡路徑規劃問題，旨在運用遺傳算法(Genetic Algorithm，GA)對交通狀況進行整體把握，降低航行風險，提前規劃出最優路徑。目前對航路尋優的研究主要集中在無人機、機器人等領域，水路交通路徑優化研究相對較少，主要從路徑優化和自動避碰兩個方面開展研究。目前，對避碰決策的研究主要有：基于模糊數學的避碰決策研究[2-3]；基于專家系統的避碰決策研究[4-6]；基于動態規劃的避碰決策研究。[7]在路徑優化方面，馬全黨等[8]提出多目標規劃模型，在此基礎上利用GA求解最優路徑，采用多目標規劃算法操作，綜合考慮航路安全性、船舶可操縱性和操船者的主觀意識等因素，對油田區水域航路規劃有較強的適用性，但因沒考慮船舶尺度的問題，該研究不適用于狀況復雜的內河水域。田鶴等[9]采用改進的GA對艦艇航線進行規劃，利用蟻群搜索策略生成初始種群，其中適應度函數編寫時主要從威脅代價和航程代價方面進行構建，但其針對艦艇的航路規劃展開，艦艇的操縱性能和對危險的定義有所不同。倪生科等[10]針對在不同會遇態勢下的船舶避碰路徑規劃問題，構建一種基于GA和非線性規劃理論的避碰路徑規劃模型,該模型加入非線性規劃理論，以解決GA局部搜索能力較弱的問題，但其研究針對的是單一目標船舶的情況，更適用于開闊水域的船舶會遇。謝玉龍等[11]針對傳統GA解決船舶路徑規劃問題的不足，提出一種改進的GA,在傳統GA的基礎上增加復原操作、重構操作和錄優操作等3種新的遺傳；復原和重構操作能避免算法收斂于局部最優解，使算法盡早收斂于全局最優解，錄優操作保證種群朝著最優解方向進化。另外，設計插入算子、刪除算子和平滑算子來提高種群進化效率和生成路徑的現實意義,但其在環境仿真方面僅考慮通航時的礙航物，如島嶼、暗礁等靜止物標，未加入目標船舶信息。本文首先建立安全評價模型作為適應度函數的閾值，然后建立GA模型作為安全評價模型的下級指標，在滿足閾值的基礎上，綜合考慮經濟性、船舶操縱性和轉向個數得出適應值，再進行遺傳操作和迭代計算，最終所得適應度函數最優路徑即為最終規劃所得路徑。

1 安全評價模型

1.1 模型簡化

交通狀況模擬根據鎮揚渡船某一時刻的真實交通狀況生成交通流，為簡化研究，將其他礙航船看作在規定區域內航向、航速固定，根據該船轉向點設置的時間間隔進行實時更新，其中礙航船選用鎮揚航段兩岸港口以直線相連后上下游的來往船舶。將目標水域看作規則區域，根據鎮揚所得原始數據，經過坐標轉化得到模擬交通流初始的船舶位置、航向和航速。確定安全性指標主要參考本船和他船的位置、航速、航向和船舶尺度,其中船舶數據均借助鎮揚段船舶自動識別系統(Automatic Identification System, AIS)和岸基雷達獲得。

1.2 航路規劃安全性指標

(1)

dCPA和tCPA的值就是對相應的距離函數對時間t求導得到的最小值點。[12]

(2)

具體可表述為

(3)

(4)

對于任意路線，該路線轉向點處船位、船速、航向、船長和船寬，以及模擬交通流中礙航船船位、船速、航向、船長和船寬均已知，可求出任意路徑每個轉向點與每條礙航船的dCPA和tCPAi值。

適應度函數中的dCPA值不能直接采用上述方法求取，在內河流域，渡船頻繁變換方向，無法得知本船舶是否到達最短會遇的節點。運用一個轉向點到下一轉向點的時間ti與tCPAi比較的方式來確定是否到達最短會遇節點。若已知任意路徑上各轉向點的位置坐標，同時認為一轉向點到下一轉向點的速度恒定，就可利用相應公式計算出一轉向點到下一轉向點的時間ti。若ti

(5)

(6)

得到實際最近會遇距離為

(7)

實際最近會遇距離見圖1。

為判別船舶是否有碰撞風險，此處引入安全會遇距離(Safe Distance of Approach,SDAmin),SDAmin是最近安全會遇距離最小值[13-14]，SDAmin也可稱為船舶臨界碰撞會遇距離，對于該參數的求取，在考慮本船和目標船尺度與相對航向的基礎上，將船舶會遇局面分為本船過目標船艏部、本船過目標船艉部和本船與目標船接近相向或同向等3種情況[15]進行求解。

圖1 最近會遇距離

在計算該指標時為保證船舶通航安全，有

(8)

仿真試驗中添加判斷:若真實最小會遇距離

設θ為銳角，本船過目標船艏部時，分析本船與目標船航向的夾角α滿足

SDAmin=

(9)

式(9)中：Lt為目標船船長；Lo為本船船長;Bt為目標船船寬;Bo為本船船寬;α為本船與目標船航向夾角;P為目標船全球定位系統(Global Positioning System, GPS)的定位精度,m。

2 基于GA內河橫渡模型

2.1 產生初始種群

建立模型時，對河流寬度和港口寬度進行限定，河流寬度為WR,港口寬度為WP，生成一定規模的種群，每個種群都有固定轉向點，但鑒于最終目的為實現橫渡河流，另加艏艉點，艏艉點在兩岸且位于港口范圍內。轉向點設置為三維向量的形式為

M=(xij,yij,vij)

(10)

式(10)中：xij和yij為第i條路徑，第個轉向點的位置;vij為在此點的速度。以任意一邊港口的中點為O′點，并以該邊的河岸做x軸，以過O′點垂直x軸并指向另一河岸為y軸(見圖2)。

圖2 轉向點向量示意

(11)

2.2 適應度函數

適應度函數對于GA程序而言至關重要，本文在構建適應度函數時加入時間指標、轉向角和轉向點個數。適應度函數為

fit=αTime+βGB+γAC

(12)

式(12)中：fit為個體適應值；Time為時間指標；GB為轉向角互補角；nAC為轉向點個數；α為時間指標權重；β為轉向角指標權重；γ為轉向點數權重。

對種群初始化時生成種群，計算安全性指標，執行遺傳操作。航行路徑經濟最優，可等價為時間最短，時間指標求取方式為

(13)

式(13)中：nvars為第j條路徑轉向點數。

轉向角是船舶路徑規劃中的重要指標，希望船舶在航行中沒有大幅度轉向，從而保證其安全航行。本文在仿真實現時采用常規的觀點，認為：轉向角越小，船舶越穩定、安全；限定轉向角越小，航線越優。每條路徑都預設轉向點，每個轉向點都對應一個轉向角，其轉向角的刻畫利用與其互補的角A(見圖3)。

圖3中：r為航線的轉向角，A為航路夾角，A越大，則r越小。此外，用cosA描述A的大小，在(0,π)內單調遞減，因此在設計航路時期望cosA越小，路徑越優。

圖3 航路夾角示意

(14)

(15)

(16)

因此，綜合時間指標、轉向角、轉向點個數最優路徑為

(17)

式(17)中：各指標進行算術相加均經過z-score歸一化。

(18)

2.3 遺傳操作

由初始化函數生成渡船航行路徑，經求適應度函數求取每條路徑的適應值，借助每條路徑相應參數和求得的每條路徑適應值進行相應的遺傳操作。

2.3.1選擇算子

選擇操作經對比輪盤賭等常用選擇算子，最終采用兩人競賽選擇方法，采用該方法時，每代最優個體適應度曲線波動范圍更廣，收斂速度更快。兩人競賽選擇方法，即每次隨機選出兩個個體，選出適應值較大的個體作為新個體進行保留，直到填滿初始種群數量為止。

2.3.2交叉算子

交叉操作采用相似交叉的方式。兩個父代航線是基于適應度函數隨機選擇的，交叉點位置也是通過隨機產生的方法決定的，采取以節點為單位的方式進行交叉操作。采用順序交叉方式產生新個體，設個體交叉概率為Pc，最大種群規模為Psize，則進行交叉的個體數為

Ncross=Psize×Pc

(19)

2.3.3變異算子

為增加種群的多樣性和保證較好的收斂性，在執行變異操作時，以小概率進行變異操作，變異概率為Pm，根據群體規模和變異概率計算出變異個體個數為

NVar=Psize×Pm

(20)

2.3.4精華模型

為避免子代退化，改善種群的多樣性，引進精華模型和精英操作。引入精華模型對之前精英操作所得最優個體進行比較更新，確保最優個體能一直保留。

式(17)和式(18)中：Pc和Pm的取值通過其對每代最優個體適應值的影響進行驗證，驗證結果見圖4。由圖4可知：當Pc取值為0.9、Pm取值為0.1時，每代最優個體的適應值曲線波動范圍更廣，收斂速度更快。

a) 交叉算子

b) 變異算子

3 計算機仿真實現

利用GA進行渡船橫渡路徑尋優仿真，其實現過程選取鎮揚渡船航段兩岸渡口的連線作為參照，通過模型簡化轉化為規則圖形區域，然后通過等比放縮轉化為規則簡單圖形區域。2018年12月10日09：00時鎮揚段實時交通狀況見表1，其中，以渡口兩岸的連線為參照，沿上下游分別垂直于內河走向做連線的平行線，以截取距離渡口500 m范圍內的船舶。船長和船寬用于計算SDAmin，渡船長76 m,寬14 m。

轉向點個數根據實際需要和當時的交通狀況設置，在進行仿真試驗時，通過咨詢鎮揚渡船項目專家，認為該航段轉向點個數應在1～5個，超過5個的路徑顯然是不合理的。借助適應度函數對初始路徑進行篩選，將各指標數值經標準化之后加入權重，其中α、β和γ通過專家調研法取值分別為0.5、0.4和0.1，迭代所得最優路徑見圖5。

表1 船舶數據

圖5 仿真實現最優路徑

最終所得最優路徑為有3個轉向點的路徑，其轉向位置如圖5所示：(x,y)為轉向點處的位置；v為到達下一轉向點應采取的速度，箭頭為試驗時該處的交通流的初始狀態；(x,y)、v和c分別為其他船舶位置、航速、航向，在仿真過程，該交通流會隨轉向點更新船位。仿真驗證導出每個轉向時間節點處其他礙航船更新的船位、航速和航向，將其與本船真實dCPAmin和SDAmin比較，其中dCPAmin=194.4,SDAmin=79.9。因此，所有真實dCPA滿足

(22)

式(21)中：n為礙航船的數量，證明規劃所得路徑能保證航行的安全性，對于其他指標，由該航線船長對路徑轉向位置和采取的航速進行分析，認為路徑相對較優，可用于實際航行。

4 結束語

基于遺傳算法建立渡船橫渡航線規劃模型，結合渡船橫渡內河水域的實際需要，建立將dCPA加入船舶尺度中來建立安全評價指標的模式。通過仿真可知：構建的航法模型規劃所得路徑滿足船舶航行安全性的要求；適應度函數兼顧經濟性、轉向角和轉向角個數，綜合所得路徑航行時間較短，航線相對平滑，轉向次數盡可能少，符合實際駕駛要求。因此，構建的渡船橫渡航法模型對實際渡船橫渡航線規劃有較強的指導價值。