基于遺傳算法的開敞水域帆船航線規(guī)劃

杜勝， 劉軼華， 陳茜， 閆化然

(上海海事大學(xué)商船學(xué)院， 上海 201306)

0 引 言

隨著經(jīng)濟發(fā)展和人民生活水平的提高，帆船運動在中國逐步發(fā)展起來，越來越多的人可以接觸和體驗到帆船運動。然而，駕駛帆船的技能和經(jīng)驗通常要經(jīng)過長時間的訓(xùn)練才能獲得，這阻礙了帆船運動在中國的普及。為促進帆船運動的推廣，讓更多的人體驗帆船運動的樂趣，有必要降低帆船運動的入門門檻，減少對經(jīng)驗的依賴。在確保安全的前提下，實現(xiàn)帆船在開敞水域的航線自動規(guī)劃，不僅能使帆船運動員達(dá)到良好的競技狀態(tài)，取得較好的訓(xùn)練效果，還能培養(yǎng)和鞏固帆船愛好者的興趣。

帆船的動力來自于風(fēng)，而海面的風(fēng)場是變化且不均勻的，因此帆船的航線規(guī)劃非常復(fù)雜。邢惠麗等[1-2]提出了基于分區(qū)段優(yōu)化和進化規(guī)劃的帆船航行路徑優(yōu)化方法，以及利用全局搜索優(yōu)化的進化規(guī)劃方法；葛艷等[3-4]提出一種基于模糊綜合評價和動態(tài)規(guī)劃理論的帆船直航訓(xùn)練最優(yōu)路徑動態(tài)規(guī)劃方法，利用動態(tài)規(guī)劃原理分階段進行航向決策；FOSSEN[5]和FLAY等[6]通過船體和帆的流體動力學(xué)分析計算帆船的航行速度，但由于帆船在海面航行時受到多種因素的影響，用流體動力學(xué)分析的方法所計算出的帆船航速不太準(zhǔn)確。以往關(guān)于帆船航線規(guī)劃的研究主要集中在近岸短距離繞標(biāo)競賽的情況下，對開敞水域帆船航線規(guī)劃的研究較少。本文基于相關(guān)領(lǐng)域的研究成果進一步研究開敞水域的帆船航線規(guī)劃。帆船航線規(guī)劃本質(zhì)上是一種路徑規(guī)劃，在問題規(guī)模較小時用分支定界法、動態(tài)規(guī)劃法[7]等能得到最優(yōu)解，在問題規(guī)模較大時可以使用進化算法[8-9]進行求解。遺傳算法是進化算法的一種經(jīng)典方法，來源于達(dá)爾文的進化論、魏茨曼的物種選擇學(xué)說和孟德爾的群體遺傳學(xué)說，是模擬自然界遺傳和進化[10]并引用隨機統(tǒng)計理論而形成的一種迭代式算法，具有堅實的生物學(xué)基礎(chǔ)[11]。該算法是一種成熟的具有高魯棒性和廣泛適用性的全局優(yōu)化方法，不受問題性質(zhì)的限制，可有效地處理傳統(tǒng)優(yōu)化算法難以解決的問題[12-13]。因此，本文采用遺傳算法進行開敞水域的帆船航線規(guī)劃。

1 模型建立

1.1 基本假設(shè)

受海浪、海風(fēng)及海流等環(huán)境因素的影響，海上航行環(huán)境具有模糊性和不定性的特點[1-2]。考慮到帆船運動的特點，同時為了提高求解效率，本模型作以下假設(shè)：

(1)浪和流對帆船的影響較小，可以忽略不計；(2)無航道寬度、航行水域范圍和礙航物的限制；(3)帆船嚴(yán)格按照既定的航向航行，不會偏航；(4)不考慮運動員的操帆技能和團隊協(xié)作水平；(5)不考慮后退的航行路徑。

1.2 坐標(biāo)系

離岸帆船駕駛通常是通過衛(wèi)星導(dǎo)航用大地坐標(biāo)進行定位的，同時需要借助于紙質(zhì)海圖或電子海圖。為方便計算，本文基于海圖建立平面直角坐標(biāo)系，將大地坐標(biāo)轉(zhuǎn)換為平面直角坐標(biāo)。

因為航海用海圖比例尺較大，坐標(biāo)轉(zhuǎn)換時緯度漸長率可以忽略不計，所以大地坐標(biāo)轉(zhuǎn)化為平面直角坐標(biāo)的公式為

(a,b)=f(α,β)

(1)

式中:(α,β)為海圖中某點的大地坐標(biāo)，(a,b)為其對應(yīng)的平面直角坐標(biāo)；f表示(a,b)與(α,β)之間的映射關(guān)系。式(1)可以表示為

(2)

即海圖圖幅范圍內(nèi)任意兩點的經(jīng)度之差與緯度之差的比值與這兩點在平面直角坐標(biāo)系中的縱坐標(biāo)之差與橫坐標(biāo)之差的比值相等。式(2)中，(α0,β0)為海圖中任意一點的大地坐標(biāo)，(a0,b0)為其對應(yīng)的平面直角坐標(biāo)。

1.3 風(fēng)場數(shù)字化

在海上通常不能精確測量每個位置的風(fēng)矢量數(shù)據(jù)，只能獲得氣象船或氣象浮標(biāo)等(統(tǒng)稱氣象站)站點的風(fēng)矢量數(shù)據(jù)。表1列有與航線規(guī)劃有關(guān)的關(guān)鍵位置點的地理坐標(biāo)及其相應(yīng)的平面直角坐標(biāo)，以及氣象站的風(fēng)矢量數(shù)據(jù)。

表1 與航線規(guī)劃有關(guān)的關(guān)鍵位置點初始數(shù)據(jù)

海面上一般沒有遮蔽物，風(fēng)場變化較為均勻，因此可以使用插值的方法得到整個風(fēng)場的風(fēng)矢量數(shù)據(jù)。通過查詢風(fēng)場的風(fēng)矢量數(shù)據(jù)可以獲得海圖圖幅范圍內(nèi)任意一點的風(fēng)矢量數(shù)據(jù)。

插值的方法多種多樣，本文采用反距離加權(quán)插值法。找到距離待插值點最近的氣象站，根據(jù)區(qū)域大小對這些氣象站數(shù)據(jù)進行插值[14]，公式如下：

式中：zj為平面直角坐標(biāo)(xj,yj)處的風(fēng)速值；dj是點(x,y)與點(xj,yj)之間的水平距離，j=1,2，…，k；p是一個大于0的常數(shù)，稱為加權(quán)冪指數(shù)，本文中取p=1?？梢允褂肧urfer、ArcGIS等輔助軟件完成該插值過程。

記插值完成后風(fēng)場的風(fēng)速值構(gòu)成矩陣為M。局部風(fēng)速值及帆船在風(fēng)場中的航線見圖1。圖1中：數(shù)字代表鄰近位置點的風(fēng)速值；曲線為風(fēng)速的等值線；*代表帆船在風(fēng)場中的轉(zhuǎn)向點位置，轉(zhuǎn)向點之間的有向線段代表航線。

圖1 風(fēng)場局部風(fēng)速值及帆船在風(fēng)場中的航線示意圖

1.4 目標(biāo)函數(shù)

以整個航程的航行時間Ti為目標(biāo)函數(shù)，建立以帆船在規(guī)劃航線上用時最短為目標(biāo)的優(yōu)化模型，即

(5)

式中：tj表示帆船從前一轉(zhuǎn)向點A航行到后一轉(zhuǎn)向點B所用的時間。由于點A與B之間的風(fēng)場是變化且不均勻的，所以很難直接求出帆船在這段航線

上用的時間。本文采用積分的思想來進行計算：假定在航段l0內(nèi)的風(fēng)場是均勻的，用l0起點位置處帆船的航速代替帆船在該航段內(nèi)的平均船速，通過調(diào)用風(fēng)速值矩陣M獲得該位置的風(fēng)向和風(fēng)速；把從點A到B的航向θ1代入式(7)和(8)計算出該船速v；把每個航段l0上所用的時間累積起來近似為tj。本文取l0=0.5 n mile，則從點A到B的航行時間公式[10]如下：

(6)

式中：n為兩個轉(zhuǎn)向點之間的距離與l0的比值；vi=fvθ(M(aij,bij))，(aij,bij)為風(fēng)場內(nèi)任意一點的平面直角坐標(biāo)，M(aij,bij)為該點的風(fēng)矢量數(shù)據(jù)，fvθ表示視風(fēng)速的計算。

式中：v和θ分別表示視風(fēng)速的大小和方向；v1和θ1分別表示船速大小和航行方向；v2和θ2分別表示真風(fēng)速大小和方向。

圖2 真風(fēng)速、船速和視風(fēng)速的矢量關(guān)系

2 算 法

2.1 初始解生成

2.2 初始解優(yōu)化

由于隨機生成的轉(zhuǎn)向點是雜亂的(圖3a)，若將這些轉(zhuǎn)向點從起點隨意連接到終點，則路線的有效性會很低(圖3b)。為獲得初始可行解，在隨機生成初始路線后增加轉(zhuǎn)向點排序操作，提高搜尋效率，使發(fā)現(xiàn)最優(yōu)解的可能性盡可能提高，有效避免帆船航線規(guī)劃問題的復(fù)雜性所帶來的搜尋時間過長的問題。具體做法是將從起點到轉(zhuǎn)向點的向量在從起點到終點的向量上的投影按從小到大的順序排列(圖3c)。具體計算公式如下：

A=(ad-as,bd-bs)

(9)

(10)

bj=|A0|·|Bj|cosθj

(11)

式中：A表示從起點到終點的向量；A0表示從起點到終點的單位向量；Bj表示從起點到第j個轉(zhuǎn)向點的向量；θj表示A與Bj的夾角；bj表示Bj在A上的投影大小。

a)隨機生成的轉(zhuǎn)向點位置b)轉(zhuǎn)向點排序前的航線

c)從起點到各轉(zhuǎn)向點的向量d)轉(zhuǎn)向點排序后的航線

圖3算法隨機生成的轉(zhuǎn)向點排序前后航線對比

當(dāng)初始可行解生成之后，用遺傳算法對其進行優(yōu)化，實現(xiàn)帆船航線的尋優(yōu)。

2.3 染色體編碼與解碼

帆船航線規(guī)劃包括規(guī)劃每個轉(zhuǎn)向點的位置，以及它們的連接順序。染色體編碼需要包含轉(zhuǎn)向點順序的信息。由于本文所使用海圖的橫向幅值和縱向幅值均不會超過1 500 pixel，因此轉(zhuǎn)向點坐標(biāo)值不超過1 500。由于210<1 500<211，編碼采用11位二進制數(shù)即可。

(12)

2.4 評價函數(shù)

(13)

圖4編碼前后的染色體

2.5 選擇、交叉和變異操作

2.6 終止規(guī)則

一般情況下，可以選擇最大迭代次數(shù)作為進化規(guī)劃算法的終止條件。如果最大迭代次數(shù)比較大，則相應(yīng)的計算時間比較長；如果設(shè)置的最大迭代次數(shù)較小則會導(dǎo)致種群過早成熟，無法保證得到全局最優(yōu)解。一般可以通過試探的方法找到比較合適的最大迭代次數(shù)，從而減少計算時間。最后，將生成的轉(zhuǎn)向點連接成線，也就生成了帆船的最優(yōu)航線。

圖5 染色體單點交叉示意圖

圖6 染色體變異前后示意圖

3 模型驗證

3.1 案例參數(shù)

某型28英尺(1英尺=0.304 8 m)帆船[15]是一款易于操控的龍骨型賽船，在近岸航行中性能優(yōu)異，是行業(yè)內(nèi)知名度較高的一種船型，因此選擇該類型帆船作為算法案例更具有代表性。通過實船測試獲得該帆船的航速表。因為表中數(shù)據(jù)較多，所以將帆船航速以航速圖的形式展現(xiàn)出來，見圖7。假定仿真過程中帆船能時刻保持在帆船航速表中所記錄的狀態(tài)。

圖7 不同風(fēng)速條件下帆船航速隨迎風(fēng)角的變化

中國東海某海域(27°10′～29°10′N，122°20′～125°20′E)較為開敞，水深條件好，沒有島嶼和其他礙航物，因此選擇該海域作為仿真海域。

獲取關(guān)鍵位置點的坐標(biāo)以及某日該海域的風(fēng)場資料，經(jīng)過數(shù)字化處理后的初始數(shù)據(jù)見表2。

表2 某海域關(guān)鍵位置點初始數(shù)據(jù)

經(jīng)過計算，海圖圖幅范圍為1 000 pixel×1 356 pixel。采用插值法計算出整個海域的風(fēng)矢量數(shù)據(jù)，生成風(fēng)場矩陣M，見圖8。圖8中：箭頭方向表示風(fēng)向；箭頭的長短和灰度表示風(fēng)力大小，右側(cè)是箭頭灰度的風(fēng)力比色卡。

圖8風(fēng)場示意圖

3.2 仿真結(jié)果及分析

由于本次航行直線距離為149.6 n mile，航程相對較短，設(shè)置轉(zhuǎn)向點數(shù)目(基因數(shù)目)C為15，種群數(shù)目(染色體數(shù)目)N為70，最大迭代次數(shù)為400。

運行程序后首先生成70個初始解，見圖9a。顯然，未經(jīng)排序的初始種群合理性很低。從排序后的種群(圖9b)可以看出，初始種群的合理性大大提高。

經(jīng)過選擇、交叉、變異等操作和迭代400次之后，得到如圖9c所示的種群適應(yīng)度。從圖9c可以看出，迭代約350次時，種群適應(yīng)度已經(jīng)逐漸穩(wěn)定，說明此時種群已經(jīng)收斂。

4 結(jié)束語

仿真結(jié)果表明，基于遺傳算法的開敞水域帆船航線規(guī)劃是可行的：既能根據(jù)氣象資料快速、準(zhǔn)確地生成帆船的航線，提高航線選擇的效率，又能減少帆船運動對航行經(jīng)驗的過度依賴，降低帆船運動的入門門檻，有利于帆船運動的普及。本文的算法僅考慮了對帆船運動影響最大的因素——風(fēng)的影響，沒有考慮其他次要因素的影響，存在一定的局限性，因此該算法需要通過實踐檢驗后再進行修正和完善。

a)未經(jīng)排序的初始種群

b)排序后的初始種群

c)種群適應(yīng)度變化曲線

d)適應(yīng)度最大的5條帆船航線圖9 航線規(guī)劃模擬仿真過程及結(jié)果

參考文獻：

[1] 邢惠麗, 胡西厚, 葛艷. 帆船比賽航行路徑優(yōu)化與仿真[J]. 計算機工程與應(yīng)用, 2010, 46(27): 245-248. DOI: 10.3778/j.issn.1002-8331.2010.27.069.

[2] 邢惠麗, 胡西厚, 葛艷. 基于分區(qū)段優(yōu)化方法的帆船繞標(biāo)航行路徑動態(tài)仿真[J]. 青島大學(xué)學(xué)報(工程技術(shù)版), 2009, 24(4): 58-61. DOI: 10.13306/j.1006-9798.2009.04.008.

[3] 葛艷, 孟慶春, 魏振鋼, 等. 帆船直線航行比賽最優(yōu)路徑動態(tài)規(guī)劃方法研究[J]. 控制與決策, 2005, 20(12): 1360-1364. DOI: 10.13195/j.cd.2005.12.42.gey.008.

[4] 葛艷, 孟慶春, 李紀(jì)平, 等. 基于模糊綜合評價的帆船行駛最優(yōu)路徑規(guī)劃方法[J]. 中國航海, 2005(1): 63-67.

[5] FOSSEN T I. Handbook of marine craft hydrodynamics and motion control[M]. Hoboken: John Wiley & Sons, 2011: 15-80. DOI: 10.1002/9781119994138.

[6] FLAY R G J, VULETICH I J. Development of a wind tunnel test facility for yacht aerodynamic studies[J]. Journal of Wind Engineering & Industrial Aerodynamics, 1995, 58(3): 231-258.

[7] LAI Xuejia, MASSEY J L, MURPHY S. Markov ciphers and differential cryptanalysis[M]//Advances in Cryptology-EUROCRYPT 1991. Heidelberg: Springer, 1991:17-38.

[8] 朱霞, 陳仁文, 徐棟霞, 等. 基于改進粒子群的焊點檢測路徑規(guī)劃方法[J]. 儀器儀表學(xué)報, 2014, 35(11): 2484-2493.

[9] VELAGIC J, VUKIC Z, OMERDIC E. Adaptive fuzzy ship autopilot for track-keeping[J]. Control Engineering Practice, 2003, 11(4): 443. DOI: 10.1016/S0967-0661(02)00009-6.

[10] 《現(xiàn)代數(shù)學(xué)手冊》編纂委員會. 現(xiàn)代數(shù)學(xué)手冊(計算機數(shù)學(xué)卷)[M]. 武漢: 華中科技大學(xué)出版社, 2001: 679-686.

[11] 周昕, 凌興宏. 遺傳算法理論及技術(shù)研究綜述[J]. 計算機與信息技術(shù), 2010(4): 37-39, 43.

[12] BUCKLAND M. 游戲編程中的人工智能技術(shù)[M]. 吳祖曾, 沙鷹, 譯. 北京: 清華大學(xué)出版社, 2006: 62-81.

[13] 王倩, 許勁松, 徐建云. 無人帆船循跡航行的控制研究[J]. 船舶工程, 2015, 37(9): 63-67.

[14] HENDERSON N, PENA L. The inverse distance weighted interpolation applied to a particular form of the path tubes method: theory and computation for advection in incompressible flow[J].Applied Mathematics and Computation, 2017, 304: 114-135.

[15] 上?，m伊玻璃鋼船艇有限公司. 單體帆船(FAREAST 28R): 303958507S[P]. 2016-12-07.