摘 要:艦船在障礙物環(huán)境中航行，如果采用傳統(tǒng)的人工繪制航線的方法，不僅費時費力，并且繪制的航線非常不準確，在障礙物位置發(fā)生變更的情況下，整條航線都要重新設(shè)計和繪制;其次，人工繪制的航線圖，不便于保存，應(yīng)用范圍非常窄。為了彌補人工繪制航線的缺陷，采用一種基于改進蟻群算法的方法規(guī)劃艦船的航線，并對改進的蟻群算法進行了仿真，獲得了艦船在障礙物環(huán)境下的最優(yōu)航線。

關(guān)鍵詞:航路規(guī)劃; 蟻群算法; 障礙物環(huán)境; Matlab仿真

中圖分類號:TN911-34文獻標識碼:A

文章編號:1004-373X(2010)21-0186-03

Path Planning of Ships Based on Improved Ant Colony Algorithm

WANG Ying，LIU Wei-ting

(Jiangsu University of Science and Technology， Zhenjiang 212000， China)

Abstract: The traditional artificial method of planning route is not accurate and cost too much when ships sail in the obstacle environment. At first， if the locations of obstacles were changed， the entire route has to be redesigned. Secondly， this method of planning route is not easy to save， so its application is narrow. A method based on improved ant colony algorithm for ship planning route to compensate for the shortcomings of artificial planning route， the improved ant colony algorithm is simulated，and an optimal route for ships in the obstacle environment is obtained.

Keywords: path planning; ant colony algorithm; obstacle environment; Matlab simulation

0 引 言

艦船航路規(guī)劃是艦船航行過程中必不可少的一個環(huán)節(jié)，其關(guān)鍵性直接決定著艦船在海上航行的安全性和經(jīng)濟性。艦船的航路規(guī)劃問題就是根據(jù)已經(jīng)的地理信息數(shù)據(jù)，尋找一條從起始點到達目標點的最安全并且航程最短的航線。傳統(tǒng)的規(guī)劃算法如可視圖法、自由空間法、人工勢場法等都有一定的局限性。近年來蟻群算法以其并行性、分布式計算、正反饋機制、具有較強的魯棒性等諸多優(yōu)點，已成為路徑規(guī)劃中使用較多的一種方法。該方法被廣泛用于機器人、飛行器等的路徑規(guī)劃，但是考慮到基本蟻群算法存在搜索時間較長，易出現(xiàn)停滯等現(xiàn)象，提出了改進的蟻群算法。仿真結(jié)果表明，改進后的蟻群算法在路徑的搜索效率、可靠性等方面較基本的蟻群算法有明顯的提高。

1 蟻群算法的機理

蟻群算法是新興的仿生學(xué)算法，它是由意大利學(xué)者Dorigo M等在1991年法國巴黎召開的第一屆歐洲人工生命會議上最早提出的，1992年，Dorigo M又在其博士學(xué)位論文中進一步論述蟻群算法的核心思想[9]。

在自然界中，螞蟻的食物源總是隨機分布在蟻巢周圍的，盡管從蟻巢到食物源的路徑有多條，但是經(jīng)過一段時間后，螞蟻總是可以找到蟻巢和食物源的最短路徑。盡管單個螞蟻的行為比較簡單，但是整個螞蟻群卻表現(xiàn)出高度的協(xié)作性。

研究表明，螞蟻在覓食的運動過程中，能夠在其經(jīng)過的路徑上留下一種稱為信息素的物質(zhì)，螞蟻自身在運動的過程中也能感受到這種物質(zhì)的存在和強度。這些物質(zhì)可以引導(dǎo)螞蟻自身和其他螞蟻的運動。螞蟻總是傾向于向信息素濃度高的地方移動。在同等的時間段內(nèi)，較短路徑上的信息素遺留的較多，而選擇較短路徑的螞蟻也較多。這正是螞蟻的正反饋現(xiàn)象[1]。

蟻群算法正是基于自然界螞蟻的這種覓食行為而設(shè)計出的一種優(yōu)化算法。該算法按照一定的搜索策略，最終獲取最佳的路徑。

2 艦船航行環(huán)境建模

2.1 艦船航行環(huán)境表示

艦船在大洋中航行，其航行的空間是一個障礙物空間，要為艦船規(guī)劃出一條航路就要對艦船的航行空間進行劃分。

柵格法是目前研究最廣泛的規(guī)劃空間的方法。該方法將艦船航行的空間解耦成多個簡單的區(qū)域，稱為柵格。這些柵格構(gòu)成一個連通圖，在這個連通圖上搜索一條從起始柵格到目標柵格的路徑。

在本文的研究中，采用序號法和直角坐標法相結(jié)合的應(yīng)用，螞蟻經(jīng)過的柵格用序號法表示。因為序號法較直角坐標法節(jié)省內(nèi)存，表示簡潔。對螞蟻經(jīng)過的柵格進行評價時，則將序號轉(zhuǎn)換成坐標形式，因為坐標法更便于表示柵格之間的相對位置，計算路徑長度及檢驗路徑的可行性。柵格的直角坐標和序號示意圖如圖1所示。

圖1 柵格示意圖

直角坐標和序號的關(guān)系表示為:

i=x+Nx(y-1)(1)

x=mod((i-1)，Nx)+1(2)

y=fix((i-1)/Nx)+1(3)

式中:i表示螞蟻經(jīng)過的柵格序號;x，y表示對應(yīng)的直角坐標。其中，Nx表示Xmax/δ;δ表示單位柵格的邊長;Xmax表示x的最大值;mod表示Matlab中取余數(shù)的函數(shù);fix表示向零取整數(shù)的函數(shù)。

2.2 障礙區(qū)的處理

根據(jù)電子海圖顯示及信息系統(tǒng)中，一般采用S-57的顯示標準。根據(jù)S-57的標準，障礙物區(qū)域是由一個或多個多邊形環(huán)組成，本文模擬艦船航行的障礙物區(qū)域，將其近似成由多個正方形組合而成。

在對障礙物區(qū)域進行處理時，本文采用以下方法:

(1) 不滿一個柵格時算一個柵格;

(2) 障礙物的空凹部分和這個障礙物算成一個整體障礙物，避免局部死區(qū)的出現(xiàn);

(3) 臨近障礙物的處理，如果障礙物的物理距離比較小，把這兩個障礙物的中間區(qū)域也看作是障礙物，否則，看成兩個不同的障礙物。

對任意形狀的障礙物進行近似，近似后如圖2所示。

2.3 障礙區(qū)的擴充

由于艦船出海航行經(jīng)常受天氣狀況(如風、流、浪等)的影響，另外障礙物的位置不確定、導(dǎo)航定位系統(tǒng)的精度變化等都會給設(shè)計的航線帶來影響。考慮到以上的不確定性，本文采用對障礙物區(qū)域進行一定的擴充，以此達到留有余地、安全可靠的目的。對障礙區(qū)擴充后如圖3所示。

圖2 障礙物近似

圖3 障礙區(qū)擴充

2.4 障礙物矩陣構(gòu)造

在完成了障礙區(qū)的處理和擴充后，需要構(gòu)造障礙物的矩陣，在本文中令障礙物的柵格狀態(tài)為1，令自由柵格的狀態(tài)為0。例如:

OBSTACLE=

00001

00111

00000

11000

11100

此時模擬的空間如圖4所示。

圖4 模擬航行空間

3 蟻群算法實現(xiàn)

蟻群算法中，螞蟻根據(jù)信息素的大小選擇下一個路徑點，因此首先對艦船航行區(qū)域的各個柵格進行信息素初始化，這樣才能方便螞蟻進行下一步搜索。接著把所有的螞蟻放在起始點上，根據(jù)蟻群算法中狀態(tài)轉(zhuǎn)移概率式(9)選擇下一個航路點，并把已經(jīng)過的點和選擇的點加入到禁忌表中。以此類推，最終找到目標點。算法中當所有螞蟻均完成一次環(huán)游，即完成一次迭代后，根據(jù)各個螞蟻搜索的路徑以及目標函數(shù)的限制條件判斷可行的路徑，然后對可行路徑的各個路徑點進行信息素的更新。后續(xù)的搜索過程如上，直至完成迭代要求。

3.1 信息素的更新

在基本的蟻群算法中，當所有螞蟻完成一次迭代時，對路徑(i，j) 上的信息量按如下公式進行調(diào)整:

τij(t+n)=(1-ρ)#8226;τij(t)+Δτij(t)(4)

Δτij(t)=∑mk=1Δτkij(t)

(5)

Δτkij(t)=Q/Lk

(6)

式中:τij(t+n)表示t+n時刻路徑(i，j)上的信息量;ρ表示信息素揮發(fā)系數(shù);1-ρ表示信息素殘留因子;τij(t)表示本次循環(huán)中路徑(i，j)上的信息素增量;Q表示一常數(shù)即信息素強度;Lk表示第k只螞蟻在本次遍歷中所走路徑的長度。

為了增強蟻群算法的快速性和有效性，本文改進了信息素的更新機制，改進后的算法增強了每次迭代中尋找到可行路徑中目標函數(shù)最優(yōu)值對應(yīng)路徑上各個節(jié)點上的信息素量，減弱找到可行路徑但目標函數(shù)最差路徑上的各個節(jié)點信息素量。通過該方法加強蟻群算法的尋優(yōu)策略。改進后的信息素按照以下方式進行調(diào)整:

τi，j(t+n)=(1-ρ)τi，j(t)+Δτi，j(t)

(7)

Δτi，j(t)=Q/Lk+Q/Lmin-Q/Lmax

(8)

式中:Lmin表示第k只螞蟻本次迭代中可行路徑的最小值;Lmax表示第k只螞蟻在本次迭代中可行路徑的最大值。

3.2 下一個路徑點的選擇

螞蟻從一個點運動到下一個點按照以下的公式進行選擇:



pkij(t)=[τij(t)]α#8226;[ηij(t)]β∑[τis(t)]α#8226;[ηis(t)]β，s∈nextnode

0，otherwise

(9)

ηij=1/dij(10)

dij=(xi-xe)2+(yi-ye)2

(11)

式中:ηij表示啟發(fā)函數(shù);dij表示下一個路徑點到目標點的距離;(xi，yi)表示當前路徑點的直角坐標;(xe，ye)表示目標點的直角坐標。

4 仿真結(jié)果

選取海區(qū)范圍為200海里×200海里的正方形區(qū)域，利用柵格法將海區(qū)進行劃分，將其劃分為40×40的小網(wǎng)格，每個小網(wǎng)格代表5海里×5海里。利用改進后的蟻群算法，通過Matlab 7.0軟件進行編程仿真。仿真結(jié)果如圖5，圖6所示。圖5中灰色區(qū)域表示由淺水區(qū)、禁航區(qū)、沉船區(qū)等組成的障礙物區(qū)，圖5中的實線表示艦船通過該海區(qū)最優(yōu)的航路，航路的起始柵格用倒三角表示，航路的目標柵格用圓圈表示。圖6則表示改進后的蟻群算法在每次迭代過程中最大路徑的收斂曲線。

圖5 改進蟻群算法艦船航路規(guī)劃

圖6 改進蟻群算法收斂曲線

仿真結(jié)果表明，本文采用的改進算法能有效地解決艦船的航路問題，并且改進算法的搜索時間短，提高了蟻群算法的搜索效率。

5 結(jié) 語

在已知航海區(qū)域障礙物位置的前提下，采用本文的改進蟻群算法，能夠為艦船設(shè)計出一條最優(yōu)的航線，并且該算法克服了基本蟻群算法搜索效率低，易出現(xiàn)停滯等缺點。仿真結(jié)果表明，該算法在效率、經(jīng)濟上較傳統(tǒng)的人工繪制航線有明顯的優(yōu)勢。

參考文獻

[1]段海濱.蟻群算法原理及其應(yīng)用[M].北京:科學(xué)出版社，2005.

[2]王樹禾.圖論[M].北京:科學(xué)出版社，2009.

[3]吳啟迪，汪鐳.智能蟻群算法及應(yīng)用[M].上海:上?？萍冀逃霭嫔?，2004.

[4]鄭中義，吳兆麟.船舶避碰決策[M].大連:大連海事大學(xué)出版社，2000.

[5]謝興瀾.ECDIS中航線設(shè)計與最優(yōu)航法[D].大連:大連海事大學(xué)，2003.

[6]唐正平，趙寶慶，關(guān)楠.基于蟻群算法的艦船避險航路規(guī)劃[J].航海工程，2008，37(5):110-112.

[7]何立居，李啟華.基于蟻群算法的航線自動生成研究[J].中國航海，2009，32(3):71-75.

[8]李興鋒.基于S-57國際標準的電子海圖顯示與導(dǎo)航系統(tǒng)[D].西安:西安電子科技大學(xué)，2007.

[9]DORIGO M， GAMBARDELLA L M. Ant colony system: a copperative learning approach to the traveling salesman problem [J]. IEEE Trans. on Evolutionary Computing，1997，1(1):50-60.

[10]MONTEMANNI R， GAMBARDELLA L M， RIZZOLI A E， et al. A new algorithm for a dynamic vehicle routing problem based on ant colony system [C]//Istituto Dalle Molle di Studi sull′Intelligenza Articiale. Manno， Switzerland: IDSIA，1998: 111-118.