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

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

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

0 引 言

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

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

1 模型建立

1.1 基本假設(shè)

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

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

1.2 坐標(biāo)系

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

因?yàn)楹胶Ｓ煤D比例尺較大，坐標(biāo)轉(zhuǎn)換時(shí)緯度漸長(zhǎng)率可以忽略不計(jì)，所以大地坐標(biāo)轉(zhuǎn)化為平面直角坐標(biāo)的公式為

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

(1)

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

(2)

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

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

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

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

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

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

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

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

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

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

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

(5)

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

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

(6)

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

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

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

2 算 法

2.1 初始解生成

2.2 初始解優(yōu)化

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

A=(ad-as,bd-bs)

(9)

(10)

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

(11)

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

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

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

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

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

2.3 染色體編碼與解碼

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

(12)

2.4 評(píng)價(jià)函數(shù)

(13)

圖4編碼前后的染色體

2.5 選擇、交叉和變異操作

2.6 終止規(guī)則

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

圖5 染色體單點(diǎn)交叉示意圖

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

3 模型驗(yàn)證

3.1 案例參數(shù)

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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

b)排序后的初始種群

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

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

參考文獻(xiàn)：

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

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

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

[4] 葛艷, 孟慶春, 李紀(jì)平, 等. 基于模糊綜合評(píng)價(jià)的帆船行駛最優(yōu)路徑規(guī)劃方法[J]. 中國(guó)航海, 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] 朱霞, 陳仁文, 徐棟霞, 等. 基于改進(jìn)粒子群的焊點(diǎn)檢測(cè)路徑規(guī)劃方法[J]. 儀器儀表學(xué)報(bào), 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é)手冊(cè)》編纂委員會(huì). 現(xiàn)代數(shù)學(xué)手冊(cè)(計(jì)算機(jī)數(shù)學(xué)卷)[M]. 武漢: 華中科技大學(xué)出版社, 2001: 679-686.

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

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

[13] 王倩, 許勁松, 徐建云. 無(wú)人帆船循跡航行的控制研究[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.