基于改進蟻群算法的艦船航路規劃研究

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

關鍵詞:航路規劃; 蟻群算法; 障礙物環境; 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 引 言

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

1 蟻群算法的機理

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

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

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

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

2 艦船航行環境建模

2.1 艦船航行環境表示

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

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

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

圖1 柵格示意圖

直角坐標和序號的關系表示為:

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

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

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

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

2.2 障礙區的處理

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

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

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

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

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

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

2.3 障礙區的擴充

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

圖2 障礙物近似

圖3 障礙區擴充

2.4 障礙物矩陣構造

在完成了障礙區的處理和擴充后，需要構造障礙物的矩陣，在本文中令障礙物的柵格狀態為1，令自由柵格的狀態為0。例如:

OBSTACLE=

00001

00111

00000

11000

11100

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

圖4 模擬航行空間

3 蟻群算法實現

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

3.1 信息素的更新

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

τ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)上的信息量;ρ表示信息素揮發系數;1-ρ表示信息素殘留因子;τij(t)表示本次循環中路徑(i，j)上的信息素增量;Q表示一常數即信息素強度;Lk表示第k只螞蟻在本次遍歷中所走路徑的長度。

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

τ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表示啟發函數;dij表示下一個路徑點到目標點的距離;(xi，yi)表示當前路徑點的直角坐標;(xe，ye)表示目標點的直角坐標。

4 仿真結果

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

圖5 改進蟻群算法艦船航路規劃

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

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

5 結 語

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

參考文獻

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

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

[3]吳啟迪，汪鐳.智能蟻群算法及應用[M].上海:上海科技教育出版社，2004.

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

[5]謝興瀾.ECDIS中航線設計與最優航法[D].大連:大連海事大學，2003.

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

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

[8]李興鋒.基于S-57國際標準的電子海圖顯示與導航系統[D].西安:西安電子科技大學，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.