基于遺傳算法的渡船橫渡航法尋優(yōu)模型

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

(集美大學(xué) 航海學(xué)院， 福建 廈門(mén) 361021)

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

1 安全評(píng)價(jià)模型

1.1 模型簡(jiǎn)化

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

1.2 航路規(guī)劃安全性指標(biāo)

(1)

dCPA和tCPA的值就是對(duì)相應(yīng)的距離函數(shù)對(duì)時(shí)間t求導(dǎo)得到的最小值點(diǎn)。[12]

(2)

具體可表述為

(3)

(4)

對(duì)于任意路線，該路線轉(zhuǎn)向點(diǎn)處船位、船速、航向、船長(zhǎng)和船寬，以及模擬交通流中礙航船船位、船速、航向、船長(zhǎng)和船寬均已知，可求出任意路徑每個(gè)轉(zhuǎn)向點(diǎn)與每條礙航船的dCPA和tCPAi值。

適應(yīng)度函數(shù)中的dCPA值不能直接采用上述方法求取，在內(nèi)河流域，渡船頻繁變換方向，無(wú)法得知本船舶是否到達(dá)最短會(huì)遇的節(jié)點(diǎn)。運(yùn)用一個(gè)轉(zhuǎn)向點(diǎn)到下一轉(zhuǎn)向點(diǎn)的時(shí)間ti與tCPAi比較的方式來(lái)確定是否到達(dá)最短會(huì)遇節(jié)點(diǎn)。若已知任意路徑上各轉(zhuǎn)向點(diǎn)的位置坐標(biāo)，同時(shí)認(rèn)為一轉(zhuǎn)向點(diǎn)到下一轉(zhuǎn)向點(diǎn)的速度恒定，就可利用相應(yīng)公式計(jì)算出一轉(zhuǎn)向點(diǎn)到下一轉(zhuǎn)向點(diǎn)的時(shí)間ti。若ti

(5)

(6)

得到實(shí)際最近會(huì)遇距離為

(7)

實(shí)際最近會(huì)遇距離見(jiàn)圖1。

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

圖1 最近會(huì)遇距離

在計(jì)算該指標(biāo)時(shí)為保證船舶通航安全，有

(8)

仿真試驗(yàn)中添加判斷:若真實(shí)最小會(huì)遇距離

設(shè)θ為銳角，本船過(guò)目標(biāo)船艏部時(shí)，分析本船與目標(biāo)船航向的夾角α滿足

SDAmin=

(9)

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

2 基于GA內(nèi)河橫渡模型

2.1 產(chǎn)生初始種群

建立模型時(shí)，對(duì)河流寬度和港口寬度進(jìn)行限定，河流寬度為WR,港口寬度為WP，生成一定規(guī)模的種群，每個(gè)種群都有固定轉(zhuǎn)向點(diǎn)，但鑒于最終目的為實(shí)現(xiàn)橫渡河流，另加艏艉點(diǎn)，艏艉點(diǎn)在兩岸且位于港口范圍內(nèi)。轉(zhuǎn)向點(diǎn)設(shè)置為三維向量的形式為

M=(xij,yij,vij)

(10)

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

圖2 轉(zhuǎn)向點(diǎn)向量示意

(11)

2.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)對(duì)于GA程序而言至關(guān)重要，本文在構(gòu)建適應(yīng)度函數(shù)時(shí)加入時(shí)間指標(biāo)、轉(zhuǎn)向角和轉(zhuǎn)向點(diǎn)個(gè)數(shù)。適應(yīng)度函數(shù)為

fit=αTime+βGB+γAC

(12)

式(12)中：fit為個(gè)體適應(yīng)值；Time為時(shí)間指標(biāo)；GB為轉(zhuǎn)向角互補(bǔ)角；nAC為轉(zhuǎn)向點(diǎn)個(gè)數(shù)；α為時(shí)間指標(biāo)權(quán)重；β為轉(zhuǎn)向角指標(biāo)權(quán)重；γ為轉(zhuǎn)向點(diǎn)數(shù)權(quán)重。

對(duì)種群初始化時(shí)生成種群，計(jì)算安全性指標(biāo)，執(zhí)行遺傳操作。航行路徑經(jīng)濟(jì)最優(yōu)，可等價(jià)為時(shí)間最短，時(shí)間指標(biāo)求取方式為

(13)

式(13)中：nvars為第j條路徑轉(zhuǎn)向點(diǎn)數(shù)。

轉(zhuǎn)向角是船舶路徑規(guī)劃中的重要指標(biāo)，希望船舶在航行中沒(méi)有大幅度轉(zhuǎn)向，從而保證其安全航行。本文在仿真實(shí)現(xiàn)時(shí)采用常規(guī)的觀點(diǎn)，認(rèn)為：轉(zhuǎn)向角越小，船舶越穩(wěn)定、安全；限定轉(zhuǎn)向角越小，航線越優(yōu)。每條路徑都預(yù)設(shè)轉(zhuǎn)向點(diǎn)，每個(gè)轉(zhuǎn)向點(diǎn)都對(duì)應(yīng)一個(gè)轉(zhuǎn)向角，其轉(zhuǎn)向角的刻畫(huà)利用與其互補(bǔ)的角A(見(jiàn)圖3)。

圖3中：r為航線的轉(zhuǎn)向角，A為航路夾角，A越大，則r越小。此外，用cosA描述A的大小，在(0,π)內(nèi)單調(diào)遞減，因此在設(shè)計(jì)航路時(shí)期望cosA越小，路徑越優(yōu)。

圖3 航路夾角示意

(14)

(15)

(16)

因此，綜合時(shí)間指標(biāo)、轉(zhuǎn)向角、轉(zhuǎn)向點(diǎn)個(gè)數(shù)最優(yōu)路徑為

(17)

式(17)中：各指標(biāo)進(jìn)行算術(shù)相加均經(jīng)過(guò)z-score歸一化。

(18)

2.3 遺傳操作

由初始化函數(shù)生成渡船航行路徑，經(jīng)求適應(yīng)度函數(shù)求取每條路徑的適應(yīng)值，借助每條路徑相應(yīng)參數(shù)和求得的每條路徑適應(yīng)值進(jìn)行相應(yīng)的遺傳操作。

2.3.1選擇算子

選擇操作經(jīng)對(duì)比輪盤(pán)賭等常用選擇算子，最終采用兩人競(jìng)賽選擇方法，采用該方法時(shí)，每代最優(yōu)個(gè)體適應(yīng)度曲線波動(dòng)范圍更廣，收斂速度更快。兩人競(jìng)賽選擇方法，即每次隨機(jī)選出兩個(gè)個(gè)體，選出適應(yīng)值較大的個(gè)體作為新個(gè)體進(jìn)行保留，直到填滿初始種群數(shù)量為止。

2.3.2交叉算子

交叉操作采用相似交叉的方式。兩個(gè)父代航線是基于適應(yīng)度函數(shù)隨機(jī)選擇的，交叉點(diǎn)位置也是通過(guò)隨機(jī)產(chǎn)生的方法決定的，采取以節(jié)點(diǎn)為單位的方式進(jìn)行交叉操作。采用順序交叉方式產(chǎn)生新個(gè)體，設(shè)個(gè)體交叉概率為Pc，最大種群規(guī)模為Psize，則進(jìn)行交叉的個(gè)體數(shù)為

Ncross=Psize×Pc

(19)

2.3.3變異算子

為增加種群的多樣性和保證較好的收斂性，在執(zhí)行變異操作時(shí)，以小概率進(jìn)行變異操作，變異概率為Pm，根據(jù)群體規(guī)模和變異概率計(jì)算出變異個(gè)體個(gè)數(shù)為

NVar=Psize×Pm

(20)

2.3.4精華模型

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

式(17)和式(18)中：Pc和Pm的取值通過(guò)其對(duì)每代最優(yōu)個(gè)體適應(yīng)值的影響進(jìn)行驗(yàn)證，驗(yàn)證結(jié)果見(jiàn)圖4。由圖4可知：當(dāng)Pc取值為0.9、Pm取值為0.1時(shí)，每代最優(yōu)個(gè)體的適應(yīng)值曲線波動(dòng)范圍更廣，收斂速度更快。

a) 交叉算子

b) 變異算子

3 計(jì)算機(jī)仿真實(shí)現(xiàn)

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

轉(zhuǎn)向點(diǎn)個(gè)數(shù)根據(jù)實(shí)際需要和當(dāng)時(shí)的交通狀況設(shè)置，在進(jìn)行仿真試驗(yàn)時(shí)，通過(guò)咨詢鎮(zhèn)揚(yáng)渡船項(xiàng)目專家，認(rèn)為該航段轉(zhuǎn)向點(diǎn)個(gè)數(shù)應(yīng)在1～5個(gè)，超過(guò)5個(gè)的路徑顯然是不合理的。借助適應(yīng)度函數(shù)對(duì)初始路徑進(jìn)行篩選，將各指標(biāo)數(shù)值經(jīng)標(biāo)準(zhǔn)化之后加入權(quán)重，其中α、β和γ通過(guò)專家調(diào)研法取值分別為0.5、0.4和0.1，迭代所得最優(yōu)路徑見(jiàn)圖5。

表1 船舶數(shù)據(jù)

圖5 仿真實(shí)現(xiàn)最優(yōu)路徑

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

(22)

式(21)中：n為礙航船的數(shù)量，證明規(guī)劃所得路徑能保證航行的安全性，對(duì)于其他指標(biāo)，由該航線船長(zhǎng)對(duì)路徑轉(zhuǎn)向位置和采取的航速進(jìn)行分析，認(rèn)為路徑相對(duì)較優(yōu)，可用于實(shí)際航行。

4 結(jié)束語(yǔ)

基于遺傳算法建立渡船橫渡航線規(guī)劃模型，結(jié)合渡船橫渡內(nèi)河水域的實(shí)際需要，建立將dCPA加入船舶尺度中來(lái)建立安全評(píng)價(jià)指標(biāo)的模式。通過(guò)仿真可知：構(gòu)建的航法模型規(guī)劃所得路徑滿足船舶航行安全性的要求；適應(yīng)度函數(shù)兼顧經(jīng)濟(jì)性、轉(zhuǎn)向角和轉(zhuǎn)向角個(gè)數(shù)，綜合所得路徑航行時(shí)間較短，航線相對(duì)平滑，轉(zhuǎn)向次數(shù)盡可能少，符合實(shí)際駕駛要求。因此，構(gòu)建的渡船橫渡航法模型對(duì)實(shí)際渡船橫渡航線規(guī)劃有較強(qiáng)的指導(dǎo)價(jià)值。