基于魚群算法的船舶避淺航線設計

陳 曉， 戴 冉， 趙延鵬， 張超越

(大連海事大學 航海學院， 遼寧 大連 116026)

船舶擱淺事故是船舶在海上的常發(fā)事故之一，現(xiàn)階段對于船舶避淺大部分的研究處于擱淺事故概率的計算，主要采用的分析方式是基于事故樹模型[1]，并在此基礎上引入模糊原理[2]、貝葉斯網(wǎng)絡[3]等方法不斷地修正擱淺概率模型，以及采用設置警戒區(qū)域的方式對可能會擱淺的船舶進行報警處理[4]。上述方法多處于理論研究階段，雖然能夠分析發(fā)生擱淺事故概率，但是對于如何避淺的研究還不夠深入。船舶交通服務(Vessel Traffic Services,VTS)[5]作為海上交通安全保障的重要機構(gòu)，主要的職責是保障船舶航行安全，根據(jù)其完善的法律法規(guī)和相關航行管理規(guī)范，基于豐富的交通情況數(shù)據(jù)和環(huán)境數(shù)據(jù)，能夠做出正確、有效的決策判斷。[6]目前，VTS值班員主要是根據(jù)自身的經(jīng)驗判斷，指導危險水域的船舶航行，這種方式不但增加值班員的工作量，而且對值班員自身的素質(zhì)有較強的依賴性。因此，研究智能算法，規(guī)劃船舶避淺航線，為值班員的決策提供理論依據(jù)是具有一定現(xiàn)實意義的。

為實現(xiàn)相關危險區(qū)域和水深點信息的呈現(xiàn)，利用柵格法，對船舶航行區(qū)域進行格柵處理，并在此基礎上，以轉(zhuǎn)向角度和轉(zhuǎn)向點數(shù)量作為約束條件，對可能發(fā)生擱淺的船舶規(guī)劃新的航線，從而達到船舶避淺的目的。

1 海圖模型建立

對于船舶航行的淺灘水域，不能直接使用其中危險區(qū)域的信息，需要對相關信息建立模型。利用格柵化的方法，提取淺灘區(qū)域的信息，在生成的格柵圖中規(guī)劃船舶的避淺航線。

1.1 柵格法

柵格法[7]是20世紀60年代提出的一種對地圖的處理方法，柵格法將地圖環(huán)境分解為一系列具有二值信息的網(wǎng)絡單元格，環(huán)境中的障礙區(qū)域在整個規(guī)劃的過程中位置和大小不發(fā)生改變。利用尺寸相同的柵格對二維的環(huán)境空間進行劃分，柵格的大小自定，對于不含任何障礙物的柵格稱為自由柵格，反之稱為障礙柵格。[8]

1.2 柵格海圖構(gòu)建

首先對所選海圖內(nèi)的淺灘區(qū)域進行擴展，設置安全距離h。h的設置原則：

1) 安全區(qū)域外的水深滿足船舶的吃水要求。

2) 根據(jù)船舶的操作性能，船舶在做轉(zhuǎn)向操作時，船體不會觸及安全距離的邊界。把已擴展的區(qū)域定義為安全區(qū)域，見圖1。在航線的重新規(guī)劃中，即使靠近已擴展的淺灘區(qū)域，也能保障重新規(guī)劃后的航線符合安全操作的要求。

基于淺灘區(qū)域擴展后的海圖，假設所截取的海圖環(huán)境為E，對于不滿一個柵格的不可航行區(qū)域算一個柵格，建立數(shù)學模型為

E={gij|gij=0或1，i∈L/b,j∈W/b}

(1)

式(1)中：L為截取海圖的最大長度；W為截取海圖的最大寬度；b為柵格的長寬尺度；gij=0為可航行區(qū)域;gij=1為淺灘或危險區(qū)域。利用MATLAB軟件對截取海圖上的區(qū)域進行仿真，得到格柵化海圖示意見圖2。圖2中：黑色區(qū)域為障礙柵格，即不可航行的淺灘區(qū)域;空白區(qū)域為自由柵格，即可航行的安全區(qū)域。

圖1 擴展安全區(qū)域示意

圖2 格柵化海圖示意

2 航線規(guī)劃數(shù)學建模

避淺航線規(guī)劃的目的是避開淺灘，使船舶回歸到計劃航線。在避開淺灘的整個過程中要盡可能地使航行路徑最短、轉(zhuǎn)向點數(shù)目最少，并且以航道作為避淺航線的范圍標準，結(jié)合船舶的實際航行情況，考慮船舶航向的變化，對船舶的轉(zhuǎn)向角度和轉(zhuǎn)向點的數(shù)目進行數(shù)學約束，并建立相關的數(shù)學模型。[9]設規(guī)劃后航線的轉(zhuǎn)向點序列為(P1，P2，P3，…，Pn)，則

(2)

s.t.PiPi+1∩Bj=?,i∈R;j∈R

(3)

θ≤90°

(4)

h≥hmin

(5)

式(2)～式(5)中：式(2)為規(guī)劃后航線的距離是最短；式(3)為相鄰轉(zhuǎn)向點間的連線不與海圖環(huán)境內(nèi)的淺灘區(qū)域或者其他障礙區(qū)域相交，其中B為不同淺灘區(qū)域或者障礙物區(qū)域的集合；式(4)為船舶航向角度的改變不能超過90°；式(5)為對淺灘區(qū)域或者障礙物的擴展至少達到安全距離的要求。

3 航線規(guī)劃

3.1 魚群算法原理

3.1.1魚群算法簡介

影響魚群覓食的主要原因是環(huán)境中的食物濃度，人工魚群模擬自然界中魚群的覓食、聚群、追尾以及隨機等行為，通過這些行為在搜索域中尋優(yōu)，從而達到優(yōu)化的目的。模擬魚群的行為見圖3，假設一條人工模擬魚的位置位于Q，其視野范圍為Visual，Qn1、Qn2為視野內(nèi)其他魚的位置，前進一次的步長為Step，位置Qu為某時刻的視點所在位置：如果該位置的食物濃度高于當前位置，則向前前進一步，到達位置Qnext；如果位置Qu的濃度比當前位置Q的食物濃度低，則繼續(xù)巡視視野內(nèi)的其他位置。巡視的次數(shù)越多，則對視野內(nèi)的狀態(tài)了解越全面，有助于做出相應的判斷和決策。[10]

圖3 人工魚的視野和移動步長

(6)

(7)

式(6)～式(7)中：r是[-1,1]區(qū)間的隨機數(shù)，允許存在一定的不確定性，可用于擺脫局部最優(yōu)，從而實現(xiàn)尋找全局最優(yōu)。

3.1.2魚群行為描述[11]

(1) 覓食行為：這是魚群最為基本的一種行為，是趨向于食物的一種活動；一般可認為通過感知環(huán)境中食物的濃度來選擇運動趨向，在航線規(guī)劃過程中，食物濃度表示路徑長度值，濃度越大，路徑長度越小。

(2) 聚群行為：魚群在覓食和躲避敵害的時候通常是以聚集成群的形式進行的，人工魚群的聚群行為表示魚群會向食物濃度更優(yōu)且在視野內(nèi)并不擁擠的方向移動。

(3) 追尾行為：當某一條或幾條魚發(fā)現(xiàn)食物時，他們附近的魚會尾隨而來，進而更遠處的魚也會尾隨而來。

(4) 隨機行為：魚群在水域中自由游動，更大范圍地尋找食物或者其他魚群，隨機行為是人工魚群算法中的一種缺省行為，當魚群的其他行為無法找到更優(yōu)解時，利用隨機行為去尋找新的解。

3.2 航線規(guī)劃魚群算法的實現(xiàn)

魚群算法的目的是尋找到食物濃度最高的位置以實現(xiàn)優(yōu)化。在航向規(guī)劃過程中，設魚群的狀態(tài)為X，食物濃度為Y，其中X記錄一條完整的路徑結(jié)果，如果路徑的起點為A0=(x0,y0)，終點為AZ=(xZ,yZ)，則X[12]可表示為

X=A0A1…AZ=(x0,y0)(x1,y1)…(xZ,yZ)

(8)

式(8)中：Z為航線規(guī)劃的節(jié)點數(shù)目，其本身的數(shù)字大小與魚群算法優(yōu)化后的人工魚狀態(tài)X有關。

在航向規(guī)劃的過程中，為保證船舶能避開淺灘，且能返回到原始的計劃航線，初始點A0與終止點AT是不變的，改變的是這兩點間的其余轉(zhuǎn)向點，魚群算法優(yōu)化的根本是調(diào)整其他路徑點以找到最優(yōu)的路徑。

魚群算法的實現(xiàn)主要是對魚群行為的實現(xiàn)，在進行算法實現(xiàn)之前，首先設點相關參數(shù)符號，設定魚群的個體大小為N，人工魚移動的最大步長為Step，人工魚的視野范圍為Visual，覓食行為最大嘗試次數(shù)為try_number，最大迭代次數(shù)為Max，最大擁擠程度為δ，gen記錄迭代的次數(shù)，初始gen=1，r為[-1,1]區(qū)間的隨機數(shù)，人工魚個體之間的距離定義為d，則人工魚群算法實現(xiàn)的流程見圖4。

魚群算法在得到初始化后，會優(yōu)先執(zhí)行聚群或追尾行為。圖4中的聚群與追尾行為均包含覓食和隨機行為：當魚群的條件不滿足執(zhí)行聚群或追尾的觸發(fā)條件時，會執(zhí)行覓食行為;如果覓食行為得不到更優(yōu)解，會進行隨機行為;每一條魚完成路徑搜索后會加入到路徑列表，完成全部迭代過程，確定最優(yōu)解。

圖4 魚群算法流程

3.2.1覓食行為

設人工魚群的當前狀態(tài)為Xi，在其感知范圍內(nèi)隨機選擇下一個Xj，在求算路徑規(guī)劃問題中，狀態(tài)的改變是對其內(nèi)部路徑點的調(diào)整：若食物濃度Yi

圖5 覓食行為過程

3.2.2聚群行為

設人工魚當前的狀態(tài)為Xi，根據(jù)其Visual的限制，搜索視野內(nèi)其他人工魚，確定視野內(nèi)其他人工魚的數(shù)目為nf，這些人工魚的中心位置為Xc，食物濃度為Yc，如果Yc/nf>δ×Yi，這表明其他魚群的中心位置有較多的食物，并且不太擁擠，則該人工魚向視野內(nèi)其他魚群學習，朝中心位置方向前進一步，否則執(zhí)行覓食行為。聚群行為過程見圖6。

圖6 聚群行為過程

3.2.3追尾行為

設人工魚當前的狀態(tài)為Xi，根據(jù)其Visual的限制，搜索視野內(nèi)其他人工魚，設視野內(nèi)其他人工魚的數(shù)目為nf并找到其中食物濃度最大的人工魚，設該人工魚的狀態(tài)為Xk，食物濃度為Yk，如果Yk/nf>δ×Yi，這表明狀態(tài)為Xk的人工魚據(jù)有較高的食物濃度，并且不太擁擠，則人工魚Xi朝人工魚Xk方向前進一步，否則執(zhí)行覓食行為。追尾行為過程見圖7。

圖7 追尾行為過程

3.2.4隨機行為

隨機行為的實現(xiàn)是在人工魚的視野范圍內(nèi)隨機選擇一個狀態(tài)位置，并朝這個位置前進一步，作為覓食行為的缺省行為，設人工魚當前的狀態(tài)為Xi，下一個位置為Xi|next，則隨機行為為

Xi|next=Xi+r×Step

(9)

3.3 航線調(diào)整

柵格法將海圖環(huán)境分解成同等大小的柵格后，人工魚群算法利用不同的柵格信息規(guī)劃航線，通過這種方式生成的原始航線雖然能滿足式(2)、式(3)和式(5)的約束，但會呈現(xiàn)出鋸齒狀，不能完全符合航線規(guī)劃的基本要求。為滿足船舶航線規(guī)劃中轉(zhuǎn)向點盡可能少的航行習慣及式(4)中的約束條件，需要對生成的原始航線作進一步的調(diào)整，從而滿足上述要求。

路徑調(diào)整的思路為：取優(yōu)化后的路徑點，采用回溯的方式，將離終點最近的點與終點相連，判斷連線是否穿越淺灘區(qū)域，若不穿越，則放棄該點，按照從終點到起點的方向，使下一個點與終點相連進行判斷，直到出現(xiàn)一點與終點相連穿越淺灘區(qū)域，則記錄該點前一點為轉(zhuǎn)向點，再以該轉(zhuǎn)向點為終點，繼續(xù)回溯，直到達到起點為止。通過這種方式，在保證點與點之間的航線不穿過淺灘區(qū)域的情況下，盡可能地平滑航線，這樣既能減少轉(zhuǎn)向點，又能控制轉(zhuǎn)向角度不會過大，從而滿足式(4)中的約束條件。具體的航線調(diào)整流程[13]見圖8。

圖8 航線調(diào)整流程

通過人工魚群算法最終輸出人工魚的最優(yōu)狀態(tài)X，X存貯的路徑點用A表示，如式(8)所示。路徑矩陣W本身包含起點A0與終點AZ，所添加的轉(zhuǎn)向點均插入到起點與終點之間，最終輸出矩陣W，完成航線調(diào)整。

4 算法模擬

根據(jù)國內(nèi)淺灘水域的實際情況，模擬船舶航行環(huán)境見圖9，試驗假設船舶吃水為2.5 m，富余水深為0.5 m，由圖9可知:計劃航線穿過了4號淺灘，該處淺灘的水深為2.0 m，小于船舶的吃水數(shù)據(jù)，表明該計劃航線存在擱淺危險。[14]

利用MATLAB軟件提取船舶航行環(huán)境建立的模型見圖10，其中黑色區(qū)域為已進行安全距離擴展后的淺灘區(qū)域，并進行格柵處理。為獲得一定精度以及適合的計算速度，將模擬航行環(huán)境分成50×50個小格，其中點S和點T分別為需航線規(guī)劃的起點和終點。

對MATLAB建立的環(huán)境模型利用人工魚群算法規(guī)劃航線，圖中鋸齒狀的實線是規(guī)劃后的結(jié)果，見圖11。

圖9 航行水域

圖10 MATLAB模型

圖11 人工魚群算法航線規(guī)劃結(jié)果

利用航線路徑調(diào)整的思想重新生成航線見圖12，經(jīng)過調(diào)整，航線內(nèi)僅剩1個轉(zhuǎn)向點，且符合船舶轉(zhuǎn)向時轉(zhuǎn)向角度<90°的限制條件。

將利用MATLAB軟件模擬得到的轉(zhuǎn)向點添加到海圖環(huán)境中，最終得到的航線規(guī)劃見圖13。圖13中:黑色實線為規(guī)劃后的航線;點S為航線的起點;T為航線的終點。轉(zhuǎn)向點如圖13所示。

圖12 調(diào)整后的航線

圖13 航線生成示例

5 結(jié)束語

為實現(xiàn)船舶避淺航線規(guī)劃，依次從建立環(huán)境模型、人工魚群算法航線規(guī)劃以及航線路徑調(diào)整3個階段進行研究。首先利用柵格法對選取的海圖環(huán)境建立模型，提取其中淺灘區(qū)域和障礙區(qū)域信息，進行安全距離擴展；在已建立的環(huán)境模型上利用人工魚群算法，得到初始規(guī)劃航線；隨后利用航線調(diào)整原則對已優(yōu)化的航線進一步進行調(diào)整，減少轉(zhuǎn)向點，滿足約束條件。

通過仿真試驗可得到：利用人工魚群算法能準確實現(xiàn)船舶避淺，并且滿足海上航行的一般要求。與傳統(tǒng)的VTS值班員根據(jù)自身經(jīng)驗指導船舶避淺的做法相比，基于人工魚群算法的航線規(guī)劃更具科學性，在一定程度上減少VTS值班員的工作量。但是，該算法考慮得并不全面，沒有顧及周圍動態(tài)船舶及天氣的影響，這些因素會在今后做出進一步的研究。