基于改進(jìn)蟻群算法的船舶避碰路徑規(guī)劃決策支持

江冠超 肖英杰 徐笑鋒

上海海事大學(xué)商船學(xué)院

0 引言

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

避碰決策支持系統(tǒng)不僅考慮相關(guān)的危險(xiǎn)和避碰措施，還需要考慮偏離原航線的情況，即船舶避碰路徑。船舶避碰路徑規(guī)劃是一個(gè)多準(zhǔn)則、非線性規(guī)劃問題，必須在航行安全與經(jīng)濟(jì)之間尋求平衡。馬文耀等[4,5]提出以船舶避碰轉(zhuǎn)向后至復(fù)航回到原航向的航行距離為目標(biāo)函數(shù)，通過算法求出最優(yōu)的避碰路徑。于家根等[6]提出將最近會遇距離和轉(zhuǎn)向角度作為兩個(gè)目標(biāo)函數(shù)，通過賦予權(quán)重構(gòu)成單一目標(biāo)函數(shù)，通過算法尋找最優(yōu)路徑。曾勇等[7]提出轉(zhuǎn)向角度、航行距離及最近會遇距離構(gòu)成三個(gè)目標(biāo)函數(shù)，賦予權(quán)重構(gòu)成單目標(biāo)函數(shù)。劉冬冬等[8]提出以偏航時(shí)間、避碰水域?qū)挾群涂偤叫芯嚯x為目標(biāo)函數(shù)的最短避碰路徑。劉仁偉等[9]提出考慮風(fēng)、流及岸壁淺水等環(huán)境因素的船舶碰撞危險(xiǎn)度量化模型。趙舟等[10]提出以碰撞危險(xiǎn)度和轉(zhuǎn)向角度值的負(fù)函數(shù)表示能夠反映決策中避碰安全、路徑優(yōu)化的目標(biāo)函數(shù)。目前大多數(shù)避碰路徑規(guī)劃模型沒有對安全性經(jīng)濟(jì)性量化或者沒有考慮復(fù)航。蟻群算法在路徑規(guī)劃問題中的應(yīng)用，需要將規(guī)劃區(qū)域網(wǎng)格化產(chǎn)生坐標(biāo)點(diǎn)進(jìn)而轉(zhuǎn)化成類似旅行商的問題[11-15]。在現(xiàn)有的蟻群算法應(yīng)用中，還不能直接將蟻群算法應(yīng)用于非線性函數(shù)尋優(yōu)問題。

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

1 兩船會遇態(tài)勢

根據(jù)《1972年國際海上避碰規(guī)則》（以下簡稱規(guī)則），兩艘機(jī)動(dòng)船相遇時(shí)，其會遇態(tài)勢分為三種，分別為對遇、交叉相遇、追越，如圖1所示。

圖1 會遇態(tài)勢

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

2 轉(zhuǎn)向避碰路徑規(guī)劃模型

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

2.1 碰撞危險(xiǎn)度目標(biāo)函數(shù)模型

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

圖2

其中，θ 為轉(zhuǎn)向后兩船相對運(yùn)動(dòng)線與目標(biāo)船方位線夾角，A為轉(zhuǎn)向后兩船相對運(yùn)動(dòng)線與本船船首向夾角，△C0t為轉(zhuǎn)向后兩船航向線夾角，△C0為本船轉(zhuǎn)向角度，Vr為轉(zhuǎn)向后兩船相對運(yùn)動(dòng)速度，D 為兩船轉(zhuǎn)向后的距離，V0為本船速度，Vt為目標(biāo)船速度。

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

由公式（1）可見，船舶轉(zhuǎn)向避碰后最大的最近會遇距離maxdCPA=D，即θ=90°時(shí)。從安全角度考慮，dCPA越大安全性越高，構(gòu)建兩船碰撞危險(xiǎn)度目標(biāo)函數(shù)f1：

式（6）中，f1值域?yàn)閇0,1]，且最近會遇距離越大，其函數(shù)值越大。

2.2 航行距離目標(biāo)函數(shù)模型

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

根據(jù)規(guī)則第16 條規(guī)定，讓路船應(yīng)該大幅度行動(dòng)，綜合考慮環(huán)境因素以及人為因素，限制以下約束條件：△C0=[30°, 90°]，△Cr=[30°, 60°]，T0=[tCPA1,60 min]，tCPA1為轉(zhuǎn)向后的最近會遇時(shí)間。構(gòu)建本船航行距離目標(biāo)函數(shù)f2：

式（8）中，f2值域?yàn)?0,1]，且d 越小，其函數(shù)值越大。

2.3 總目標(biāo)函數(shù)模型

所構(gòu)建的碰撞危險(xiǎn)度目標(biāo)函數(shù)及航行距離目標(biāo)函數(shù)的值域都為[0,1],且取值越優(yōu)函數(shù)值越大。若對兩個(gè)目標(biāo)函數(shù)分別賦予權(quán)重α、β（α+β=1），則多目標(biāo)函數(shù)構(gòu)成單目標(biāo)函數(shù)f：

對f 求最大值，其最大值所對應(yīng)的參數(shù)即為最優(yōu)避碰路徑的參數(shù)：避碰轉(zhuǎn)向角度、復(fù)航轉(zhuǎn)向角度、復(fù)航時(shí)間。

3 蟻群算法

3.1 蟻群算法模型

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

3.2 改進(jìn)蟻群算法

本文所構(gòu)造的目標(biāo)函數(shù)模型是非線性函數(shù)極值尋優(yōu)問題。從所參考的文獻(xiàn)上發(fā)現(xiàn)，蟻群算法較多用于TSP 問題及其衍生問題上，即問題需要有坐標(biāo)點(diǎn)，通過網(wǎng)格化坐標(biāo)點(diǎn)得到轉(zhuǎn)移概率，進(jìn)而求出最短路徑。受式（10）轉(zhuǎn)移概率公式的啟發(fā)，在非線性函數(shù)尋優(yōu)問題中，可行解轉(zhuǎn)移概率為：

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

由式（12）、（13）、（14）構(gòu)造出可用于非線性函數(shù)尋優(yōu)的蟻群算法。

3.3 算法流程

步驟1：將參數(shù)初始化。蟻群規(guī)模，最大迭代次數(shù)，信息素?fù)]發(fā)因子，信息素釋放因子，轉(zhuǎn)移概率常數(shù)，本船與來船航向航速，來船方位等。

步驟2：建立解空間。初始時(shí)，對螞蟻隨機(jī)分散置于不同位置，然后根據(jù)轉(zhuǎn)移概率對每個(gè)螞蟻確定下一個(gè)位置。

步驟3：信息素更新。根據(jù)信息素更新公式對每個(gè)位置信息素進(jìn)行更新，同時(shí)記錄當(dāng)前計(jì)算中的最大值。

步驟4：終止判斷。若當(dāng)前迭代次數(shù)達(dá)到最大迭代次數(shù)，結(jié)束算法，輸出最大值；否則，返回步驟2。如圖3所示。

4 仿真實(shí)驗(yàn)結(jié)果

設(shè)本船航速為12 kn，航向000°，目標(biāo)船航速為12 kn。綜合考慮安全與經(jīng)濟(jì)的重要性，取α=0．6，β=0．4。根據(jù)規(guī)則，通過模擬對遇、小角度交叉相遇、大角度交叉相遇三種態(tài)勢驗(yàn)證避碰模型。為驗(yàn)證算法有效性，避免隨機(jī)性，重復(fù)執(zhí)行20次算法過程。

對遇：目標(biāo)船航向180°，方位000°，距離5 nm，其matlab仿真結(jié)果顯示，除個(gè)別值外其目標(biāo)函數(shù)值的范圍為[0．581 2, 0．598 3]，最優(yōu)值迭代過程如圖4所示；小角度交叉相遇：目標(biāo)船航向240°，方位040°，距離5 nm，仿真結(jié)果顯示，除個(gè)別值外其目標(biāo)函數(shù)值的范圍為[0．527 1, 0．543 0]，最優(yōu)值迭代過程如圖5 所示；大角度交叉相遇：目標(biāo)船航向280°，方位050°，距離5 nm，仿真結(jié)果顯示，除個(gè)別值外其目標(biāo)函數(shù)值的范圍為[0．415 9, 0．432 1]，最優(yōu)值迭代過程如圖6 所示。三種會遇態(tài)勢仿真結(jié)果，最優(yōu)目標(biāo)函數(shù)值所對應(yīng)的避碰轉(zhuǎn)向角度、復(fù)航轉(zhuǎn)向角度、避碰轉(zhuǎn)向到復(fù)航轉(zhuǎn)向時(shí)間、最短航行距離見表1。

圖3 基于改進(jìn)蟻群算法的目標(biāo)函數(shù)尋優(yōu)模型

表1 基于改進(jìn)蟻群算法的最優(yōu)避碰路徑參數(shù)

分析仿真結(jié)果，此目標(biāo)函數(shù)模型能夠在綜合考慮安全性與經(jīng)濟(jì)性權(quán)重后給出最優(yōu)避碰路徑。改進(jìn)后用于非線性函數(shù)尋優(yōu)的蟻群算法結(jié)果可以在迭代50 次內(nèi)收斂于某一固定值，收斂速度較快；算法運(yùn)行時(shí)間3～6 s，計(jì)算速度較快；重復(fù)執(zhí)行20 次算法后，除個(gè)別值外，目標(biāo)函數(shù)值穩(wěn)定在很小的范圍內(nèi)：對遇態(tài)勢下范圍[0．581 2,0．598 3]，小角度交叉態(tài)勢下范圍[0．527 1, 0．543 0]，大角度交叉態(tài)勢下范圍[0．415 9,0．432 1]，此算法可行。

圖4 對遇目標(biāo)函數(shù)最優(yōu)值

圖5 小角度目標(biāo)函數(shù)最優(yōu)

圖6 大角度目標(biāo)函數(shù)最優(yōu)

5 結(jié)束語

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