基于改進蟻群算法的全局船舶路徑規(guī)劃方法

黃國良,周毅,鄭坤,李萌,蒙學(xué)昊

(中海油能源發(fā)展股份有限公司采油服務(wù)分公司,天津 300452)

路徑規(guī)劃算法性能的優(yōu)劣將直接影響船舶航行的安全和效率。蟻群算法作為最常用的元啟發(fā)式算法之一,在路徑規(guī)劃問題上取得了不錯的效果,但仍然存在若干缺陷[1]:①容易陷入局部最優(yōu),且很難自主跳出;②初始信息素濃度分配方式和信息素更新規(guī)則沒有針對性,不必要的探索會降低算法的收斂性。針對蟻群算法的兩個主要問題,學(xué)者們提出了各種改進方法[2-8],但目前在船舶路徑規(guī)劃問題的求解中,普遍存在算法規(guī)劃路徑質(zhì)量不高、收斂性與隨機性無法保持平衡的問題。因此,考慮結(jié)合船舶路徑規(guī)劃的任務(wù)需求,采用啟發(fā)式和融合式策略對蟻群算法進行改進。另外,將路徑長度、安全性和平滑性約束函數(shù)融入至信息素更新規(guī)則,以保障船舶航行路徑的安全。

1 蟻群算法數(shù)學(xué)模型

蟻群算法通過信息素濃度與距離啟發(fā)函數(shù)計算螞蟻選擇路徑的概率。假設(shè)蟻群中螞蟻的數(shù)量為m,任意兩路徑點間的信息素數(shù)值相同。在n時刻,螞蟻l=1,2,3,…,m從當(dāng)前路徑點i選擇任意路徑點j的概率為

(1)

式中:κ和λ分別是信息啟發(fā)式因子和期望值啟發(fā)式因子,Hij是距離啟發(fā)函數(shù),等于兩路徑點間歐式距離的倒數(shù),Dl為路徑點i下一時刻可選擇的路徑點集合。Iij為路徑點i、j間的信息素數(shù)值。

(2)

2 基于人工勢場的改進蟻群算法

2.1 引入人工勢場法

由于人工勢場法具有初始導(dǎo)向性強、計算便捷和魯棒性較強的特點,將人工勢場法引入蟻群算法,提高蟻群算法的初始迭代速度。由于引力勢場函數(shù)與本船到目的地的距離G的平方成正比,當(dāng)G較大時會導(dǎo)致該點的引力值趨于無窮大,增加本船與礙航物發(fā)生碰撞的風(fēng)險。為避免船舶與礙航物發(fā)生碰撞事故,設(shè)定引力勢場函數(shù)影響分界線R。當(dāng)G≤R時,使引力勢場值與G的平方成正比;當(dāng)G>R時,使引力勢場值與G成正比,從而降低引力勢場的影響范圍。引力勢場函數(shù)改進如下。

(3)

式中:Ka為引力勢場系數(shù)。

2.2 偽隨機狀態(tài)選擇概率的改進

傳統(tǒng)蟻群算法以路徑中信息素濃度和啟發(fā)式信息函數(shù)的乘積作為路徑選擇概率。這種選擇方式僅注重對新路徑的搜索,常忽略對當(dāng)前優(yōu)秀路徑的選擇,易增加算法的時間復(fù)雜度。為此,引入隨機數(shù)r與固定參數(shù)r0改進算法的選擇概率。當(dāng)r≤r0時,螞蟻將啟發(fā)式信息函數(shù)和信息素濃度乘積作為評價值,并選擇使其數(shù)值最大的路徑,即強化當(dāng)前路徑的選擇;當(dāng)r>r0時,選擇基本蟻群算法的策略作為選擇概率,即探索新路徑。改進后的狀態(tài)選擇概率公式可使開發(fā)當(dāng)前路徑和探索新路徑達到平衡,不僅能降低探索新路徑產(chǎn)生的額外時間開銷,還可避免過早的陷入局部最優(yōu)。改進后的轉(zhuǎn)移概率為

(4)

式中:r∈[0,1]為隨機數(shù);r0∈[0,1]為固定參數(shù),r和r0的具體取值由人為設(shè)定。

2.3 信息素更新規(guī)則的改進

傳統(tǒng)蟻群算法更新信息素時僅考慮了路徑長度,而在解決實際船舶路徑規(guī)劃問題時,不僅要考慮路徑長度,還要考慮路徑安全性和路徑平滑程度。因此,在信息素更新規(guī)則公式中加入路徑的長度、安全性和平滑性目標(biāo)約束,修改后的信息素公式更新為

(5)

式中:ω1、ω2、ω3是約束函數(shù)的權(quán)重系數(shù);Il是螞蟻l訪問過的節(jié)點;Fl、Fs、Fm分別為路徑長度、路徑安全性和路徑平滑度約束函數(shù)。

(6)

式中:t是路徑上節(jié)點的總數(shù)量;d(i,i+1)為節(jié)點i到節(jié)點i+1的距離;Si,i+1為前節(jié)點與下一節(jié)點的路徑安全性程度;θ(i,i+1)為節(jié)點i和節(jié)點i+1之間的轉(zhuǎn)向角度。

Si,i+1=

(7)

(8)

式中:SDA(i,i+1)為在路徑點i和i+1之間的船舶安全會遇距離。

3 算法實現(xiàn)

3.1 靜態(tài)路徑規(guī)劃算法的實現(xiàn)

本文提出的混合蟻群靜態(tài)路徑規(guī)劃算法(hybrid ant colony static algorithm,HACSA)具體實施步驟如下。

1)步驟1,利用柵格法建立船舶航行環(huán)境模型,確定船舶起始點、目的地和礙航物位置。

2)步驟2,對混合蟻群算法中的參數(shù)設(shè)置初始值,比如,螞蟻數(shù)量m,信息素揮發(fā)系數(shù)δ,初始信息素強度Q,引力勢場系數(shù)Ka,人工勢場影響系數(shù)R等。

3)步驟3,構(gòu)建改進蟻群算法禁忌表并對其進行初始化設(shè)置。

4)步驟4,根據(jù)公式計算各路徑點的信息素濃度。

5)步驟5,根據(jù)公式計算船舶所受合力的大小及方向,據(jù)公式計算當(dāng)前位置的轉(zhuǎn)移概率并確定下一步的移動位置j,并將該位置加入至禁忌表。

6)步驟6,更新完禁忌表后,判斷螞蟻是否到達目的地,若未抵達目的地則繼續(xù)執(zhí)行步驟5,反之,則記錄該螞蟻的路徑長度和路徑信息并進入到步驟7。

7)步驟7,令螞蟻索引l=l+1,并判斷l(xiāng)是否等于m,若不相等則返回步驟4,若相等則更新信息素濃度。船舶碰撞檢測見圖1。

圖1 船舶碰撞檢測

3.2 動態(tài)路徑規(guī)劃算法的實現(xiàn)

船舶動態(tài)路徑規(guī)劃算法在靜態(tài)路徑規(guī)劃的基礎(chǔ)上融入了碰撞危險計算、會遇態(tài)勢識別和避碰行動采取。假設(shè)任意目標(biāo)船與本船有個安全會遇半徑Dsafe=SDA,若本船和目標(biāo)船的船舶最近會遇距離Dcpa

(9)

根據(jù)公式判斷出本船與目標(biāo)船之間的狀態(tài),如果有碰撞可能且具有避讓責(zé)任時,本船應(yīng)采取合適的避讓措施。為簡化運算,本文均采用右轉(zhuǎn)向?qū)崿F(xiàn)避讓。在單船會遇情況下,已知本船與目標(biāo)船的安全圓有2個切點,切點Rp(xRp,yRp)和切點Lp(xLp,yLp),見圖2。

圖2 船舶避讓措施

本文將安全圓的左切點作為船舶避讓導(dǎo)向點,左右切點按照式計算。

(10)

(y-yt)(y-y0)=-(x-xt)(x-x0)

(11)

式中:(x,y)為待求切點坐標(biāo);(x0,y0)為本船坐標(biāo);(xt,yt)為目標(biāo)船坐標(biāo)。

在多船會遇情況下,根據(jù)目標(biāo)船個數(shù)分別計算出本船與目標(biāo)船的左切點和右切點對應(yīng)的角度。當(dāng)前局面下存在3個目標(biāo)船,見圖3。

圖3 多船避讓措施

聯(lián)立目標(biāo)船安全圓公式和可求得本船與目標(biāo)船的左右切點坐標(biāo),針對多目標(biāo)船會遇局面,重復(fù)利用公式-計算出本船與各目標(biāo)船的左切點角度分別為θAL、θBL、θCL。將選擇目標(biāo)船切點角度最小的左切點作為避讓導(dǎo)向點,而切點角度θgoal的選擇方法如式所示。

θgoal=min{θAL,θBL,θCL}

(12)

基于上述分析,提出混合蟻群動態(tài)路徑規(guī)劃算法(hybrid ant colony dynamic algorithm,HACDA),算法具體實施步驟如下。

1)步驟1,采用HACSA規(guī)劃出一條初始航行路徑,船舶將沿初始路徑航行。

2)步驟2,計算Tcpa、Dcpa和目標(biāo)船相對運動方位θT。

3)步驟3,使用公式判斷本船與目標(biāo)船之間是否存在碰撞危險,若不存在,本船將沿初始路徑繼續(xù)航行;反之,則進入步驟5。

4)步驟4,依據(jù)θT值判斷本船是否為讓路船,若本船不是讓路船,本船將沿初始路徑繼續(xù)航行,若本船為讓路船,判斷Dcpa≤Dsafe和Tcpa≤T是否同時成立。

5)步驟5,若Dcpa≤Dsafe和Tcpa≤T未同時成立,本船將沿初始路徑繼續(xù)航行。

6)步驟6,若Dcpa≤Dsafe和Tcpa≤T同時成立,則計算出本船與目標(biāo)船的左切點角度θAL、θBL、θCL,利用公式求得θgoal,并在開始滿足Dcpa≤Dsafe和Tcpa≤T時采取轉(zhuǎn)向工作。

7)步驟7,本船轉(zhuǎn)向避讓后,實時重復(fù)步驟2～6判斷本船是否應(yīng)繼續(xù)采取轉(zhuǎn)向避讓,直至本船到達目的地;若不需避讓,則應(yīng)用蟻群靜態(tài)路徑算法規(guī)劃出從當(dāng)前位置至目的地的航行路徑,本船將沿新路徑航行。

4 仿真實驗

4.1 靜態(tài)路徑規(guī)劃對比仿真實驗

為驗證HACSA在復(fù)雜航行環(huán)境中規(guī)劃路徑的穩(wěn)定性,設(shè)定仿真環(huán)境為50×50(n mile),對比分析傳統(tǒng)蟻群算法、文獻[7]、文獻[8]與HACSA的路徑規(guī)劃結(jié)果,見圖4、5,表1。

表1 復(fù)雜環(huán)境下不同算法的仿真結(jié)果

由圖4可知,除了傳統(tǒng)蟻群算法,其他三種方法均可收斂得到各自的最優(yōu)路徑。在復(fù)雜環(huán)境下HACSA得到路徑最短,距離為74.6 n mile。

圖5中,HACSA的收斂速度最快。盡管船舶航行環(huán)境更復(fù)雜,HACSA仍在第8次迭代完成收斂,而文獻[8]卻在20次迭代以后才完成收斂,所以復(fù)雜環(huán)境幾乎不會影響HACSA的運行效率。

圖5 復(fù)雜環(huán)境下算法的迭代收斂

另外,文獻[8]也加入了船舶安全性約束函數(shù)。由表1可知,相比于文獻[8]中的方法,復(fù)雜環(huán)境幾乎不會影響HACSA規(guī)劃路徑的安全性。所以無論是在復(fù)雜環(huán)境還是簡單環(huán)境,HACSA均取得了相對最優(yōu)的運行結(jié)果。

4.2 動態(tài)路徑規(guī)劃算法仿真實驗

4.2.1 單目標(biāo)船動態(tài)路徑規(guī)劃

為驗證HACDA算法在靜態(tài)障礙物和單一目標(biāo)船環(huán)境下船舶動態(tài)路徑規(guī)劃的實用性,設(shè)計船舶航行區(qū)域為20×20(n mile),本船航行起點柵格序號為1,航行終點柵格序號為400。設(shè)定本船航向為45°、航速為20 kn,目標(biāo)船的柵格起始序號為180、航向為180°、航速為16 kn。見圖6。

圖6 單目標(biāo)船動態(tài)路徑規(guī)劃

由圖6a)可知,在航行初始階段,HACDA首先規(guī)劃出一條自起點至終點的安全初始航行路徑(避開靜態(tài)和動態(tài)障礙物的初始位置),此后本船沿著初始路徑航行。判斷出兩船之間存在碰撞危險,本船為讓路船,且兩船間的Dcpa和Tcpa值均小于規(guī)定值。避讓過程中仍使用HACDA實時規(guī)劃出自當(dāng)前位置至目的地的局部新路徑,見圖6b)。一旦避碰過程結(jié)束,本船將沿局部新路徑航行,若避碰過程未結(jié)束本船將繼續(xù)進行避讓。當(dāng)本船航行到252號柵格時,本船與目標(biāo)船的碰撞危險解除,見圖6c)。此時本船將沿著更新后的局部新路徑繼續(xù)航行,最終抵達航行目的地。由圖6(d)可知,在整個航行過程中,本船能識別動態(tài)障礙物并完成避讓過程。

4.2.2 多目標(biāo)船動態(tài)路徑規(guī)劃

為驗證HACDA在靜態(tài)障礙物和多運動目標(biāo)船環(huán)境下船舶動態(tài)路徑規(guī)劃的穩(wěn)定性,設(shè)計船舶航行區(qū)域大小為20×20(n mile),本船航行起點柵格序號為1,航行終點柵格序號為400,本船航向為45°、航速為20 kn;目標(biāo)船1(TS1)起點柵格的序號為257、航向為180°、航速為16 kn;目標(biāo)船2(TS2)起點柵格的序號為138,航向為225°,航速為10 kn;目標(biāo)船3(TS3)起點柵格的序號為81,航向為315°,航速為10 kn。見圖7。

圖7 多目標(biāo)船舶動態(tài)路徑規(guī)劃

首先采用HACDA規(guī)劃一條初始路徑,見圖7a)。在圖7b)中,當(dāng)本船行駛至290號柵格時,可計算出本船與TS1的Dcpa值為0.94 n mile,θT值為18.65°,兩船相距6.07 n mile,相對運動速度vR1為36 kn,Tcpa的值為10.4 min。由HACDA可判斷出本船與TS1之間存在碰撞危險,且兩船間的Dcpa和Tcpa值均小于約定值,本船右轉(zhuǎn)實現(xiàn)以避讓。

當(dāng)本船行駛至274號柵格時,本船與TS1解除碰撞危險并將沿局部新路徑向目的地航行,見圖7b)。此時,由HACDA判斷出本船與TS2之間存在碰撞危險,且兩船間的Dcpa和Tcpa值均小于規(guī)定值,本船將采取右轉(zhuǎn)向避讓。隨后本船與TS2結(jié)束對遇局面并將沿更新后的局部新路徑駛向目的地,最終本船順利抵達航行目的地。

5 結(jié)論

為提高船舶路徑規(guī)劃的安全性與經(jīng)濟性,提出一種改進的蟻群算法用于船舶路徑規(guī)劃。針對蟻群算法迭代速度慢、易陷入局部最優(yōu)等問題,通過在算法迭代初始階段引入人工勢場法,有效改善了算法的迭代速度和尋優(yōu)能力。同時,為進一步使所規(guī)劃路徑符合實際情況,將路徑長度、安全性、平滑性約束條件融入至信息素更新規(guī)則,并綜合考慮航行規(guī)則約束。仿真實驗證明,所提出算法的可行、有效。主要分析靜態(tài)環(huán)境下的船舶路徑規(guī)劃,針對動態(tài)環(huán)境,僅實現(xiàn)了簡單多船環(huán)境下船舶路徑規(guī)劃。然而,動態(tài)環(huán)境下的影響因素更多,如何實現(xiàn)更為復(fù)雜環(huán)境下的船舶動態(tài)路徑規(guī)劃是后續(xù)研究方向。