基于改進(jìn)蟻群算法的艦船航路規(guī)劃研究

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

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

中圖分類號(hào):TN911-34文獻(xiàn)標(biāo)識(shí)碼:A

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

1 蟻群算法的機(jī)理

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

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

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

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

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

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

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

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

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

圖1 柵格示意圖

直角坐標(biāo)和序號(hào)的關(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)過(guò)的柵格序號(hào);x，y表示對(duì)應(yīng)的直角坐標(biāo)。其中，Nx表示Xmax/δ;δ表示單位柵格的邊長(zhǎng);Xmax表示x的最大值;mod表示Matlab中取余數(shù)的函數(shù);fix表示向零取整數(shù)的函數(shù)。

2.2 障礙區(qū)的處理

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

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

(1) 不滿一個(gè)柵格時(shí)算一個(gè)柵格;

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

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

對(duì)任意形狀的障礙物進(jìn)行近似，近似后如圖2所示。

2.3 障礙區(qū)的擴(kuò)充

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

圖2 障礙物近似

圖3 障礙區(qū)擴(kuò)充

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

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

OBSTACLE=

00001

00111

00000

11000

11100

此時(shí)模擬的空間如圖4所示。

圖4 模擬航行空間

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

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

3.1 信息素的更新

在基本的蟻群算法中，當(dāng)所有螞蟻完成一次迭代時(shí)，對(duì)路徑(i，j) 上的信息量按如下公式進(jìn)行調(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時(shí)刻路徑(i，j)上的信息量;ρ表示信息素?fù)]發(fā)系數(shù);1-ρ表示信息素殘留因子;τij(t)表示本次循環(huán)中路徑(i，j)上的信息素增量;Q表示一常數(shù)即信息素強(qiáng)度;Lk表示第k只螞蟻在本次遍歷中所走路徑的長(zhǎng)度。

為了增強(qiáng)蟻群算法的快速性和有效性，本文改進(jìn)了信息素的更新機(jī)制，改進(jìn)后的算法增強(qiáng)了每次迭代中尋找到可行路徑中目標(biāo)函數(shù)最優(yōu)值對(duì)應(yīng)路徑上各個(gè)節(jié)點(diǎn)上的信息素量，減弱找到可行路徑但目標(biāo)函數(shù)最差路徑上的各個(gè)節(jié)點(diǎn)信息素量。通過(guò)該方法加強(qiáng)蟻群算法的尋優(yōu)策略。改進(jìn)后的信息素按照以下方式進(jìn)行調(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 下一個(gè)路徑點(diǎn)的選擇

螞蟻從一個(gè)點(diǎn)運(yùn)動(dòng)到下一個(gè)點(diǎn)按照以下的公式進(jìn)行選擇:



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表示下一個(gè)路徑點(diǎn)到目標(biāo)點(diǎn)的距離;(xi，yi)表示當(dāng)前路徑點(diǎn)的直角坐標(biāo);(xe，ye)表示目標(biāo)點(diǎn)的直角坐標(biāo)。

4 仿真結(jié)果

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

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

圖6 改進(jìn)蟻群算法收斂曲線

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

5 結(jié) 語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

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

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

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

[8]李興鋒.基于S-57國(guó)際標(biāo)準(zhǔn)的電子海圖顯示與導(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.