[發(fā)明專利]一種基于遺傳算法的開敞水域帆船路徑規(guī)劃方法

有效

• 申請?zhí)枺?/td>: 201710619152.3
• 申請日: 2017-07-26
• 公開（公告）號: CN107525509B
• 公開（公告）日: 2020-12-04
• 發(fā)明（設(shè)計）人: 杜勝;劉軼華;陳茜;閆化然;朱小林
• 申請（專利權(quán)）人: 上海海事大學(xué)
• 主分類號: G01C21/20
• 分類號: G01C21/20;G06N3/12
• 代理公司: 上海三和萬國知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 31230
• 代理人: 陳偉勇

1.一種基于遺傳算法的開敞水域帆船路徑規(guī)劃方法，其特征在于，包括以下步驟：

步驟一.準(zhǔn)備帆船航速表和帆船航速圖，每一節(jié)風(fēng)對應(yīng)一個帆船航速表格，帆船航速表中列有不同風(fēng)舷角對應(yīng)的最大航速；

步驟二.準(zhǔn)備待航行水域的海圖；

步驟三.輸入航行區(qū)域內(nèi)所有氣象站的數(shù)據(jù)到表中，表中列有不同氣象站編號和對應(yīng)的經(jīng)度、緯度、風(fēng)向、風(fēng)速；

步驟四.輸入航行起點和航行終點的位置到表中，表中列有起點、終點的經(jīng)度和緯度：

步驟五.將步驟二中的海圖進(jìn)行數(shù)字化處理，獲得海圖中關(guān)鍵位置點的平面坐標(biāo)，海圖中的地理坐標(biāo)和平面坐標(biāo)轉(zhuǎn)化公式為：(a,b)＝f(α,β)，其中，a,b,α,β之間的關(guān)系為：a和α分別為地理坐標(biāo)和平面坐標(biāo)的橫坐標(biāo)，b和β分別為地理坐標(biāo)和平面坐標(biāo)的縱坐標(biāo)，a₀和α₀分別為任意點的地理坐標(biāo)和平面坐標(biāo)的橫坐標(biāo)，b₀和β₀分別為任意點的地理坐標(biāo)和平面坐標(biāo)的縱坐標(biāo)；

步驟六.結(jié)合采集到的各氣象站數(shù)據(jù)和對應(yīng)的氣象站坐標(biāo)上，分別生成氣象站風(fēng)向矩陣和氣象站風(fēng)速矩陣；

步驟七.采用反距離加權(quán)插值法，找到距離待插值點最近的氣象站，對氣象站風(fēng)向矩陣和氣象站風(fēng)速矩陣進(jìn)行網(wǎng)格化處理，獲得整個風(fēng)場的風(fēng)向矩陣和風(fēng)速矩陣，計算公式為：其中，z_j為點(x_j,y_j)在水平面的垂直高度，此處取為常數(shù)1，是點(x,y)到(x_j,y_j)點的水平距離，j＝1,2，···k，P是一個大于0的常數(shù)，稱為加權(quán)冪指數(shù)，取p＝1；

步驟八.作以下建模的簡化：

1).在開敞水域沒有航道寬度、路徑范圍以及礙航物的限制；

2).帆船航行在每一段航線時嚴(yán)格按照既定的航向航行，不會偏航；

3).帆船不能往后航向，因為即使目標(biāo)處于正迎風(fēng)位置，常規(guī)的帆船路線也不會采用后退的路線，這樣可以提高隨機(jī)生成路線到達(dá)終點的有效性，避免生成很多無效路徑，提高模型求解效率；

4).設(shè)置轉(zhuǎn)向點數(shù)目為C，即基因數(shù)目為C，種群數(shù)目為N，即染色體數(shù)目為N，每一個轉(zhuǎn)向點為一個基因，總的路徑為一個染色體；

步驟九.根據(jù)上一步確定的轉(zhuǎn)向點個數(shù)生成初始種群，在數(shù)字化海圖圖幅范圍內(nèi)，隨機(jī)生成N條航線，即N條航線，每個染色體中有C個轉(zhuǎn)向點，初始種群P⁰＝{P₁⁰,P₂⁰,…,P_i⁰,…,P_N⁰}，其中P⁰表示第0代種群，P_i⁰是第0代的第i個染色體；第i條航線的轉(zhuǎn)向點：P_i⁰＝[p⁰ⁱ₁,p⁰ⁱ₂,…,p⁰ⁱ_j…,p⁰ⁱ_C]，其中p⁰ⁱ_j是第0代的第i個染色體的第j個轉(zhuǎn)向點，坐標(biāo)為(c⁰ⁱ_j,d⁰ⁱ_j)；

步驟十.由于一張海圖的橫向幅值和縱向幅值均不會超過1500單位，在步驟五海圖網(wǎng)格化處理的時候東西向和南北向的間距為10單位，因此轉(zhuǎn)向點坐標(biāo)值的大小不超過150，由于2⁷1502⁸,因此基因編碼采用8位二進(jìn)制數(shù)；

步驟十一.根據(jù)轉(zhuǎn)向點落在起點到終點的向量的投影大小對隨機(jī)生成的轉(zhuǎn)向點排序,計算公式如下：其中，表示從起點到終點的向量，表示從起點到終點的單位向量，表示起點與第j個轉(zhuǎn)向點構(gòu)成的向量，θ_j表示與的夾角，C′_j表示第j個轉(zhuǎn)向點落在起點到終點的向量的投影大小，其中，m和r分別為起點坐標(biāo)和終點坐標(biāo)的橫坐標(biāo)，n和s分別為起點坐標(biāo)和終點坐標(biāo)的縱坐標(biāo)；

步驟十二.依次將上一步排序后的每個轉(zhuǎn)向點p⁰ⁱ′_j的橫坐標(biāo)和縱坐標(biāo)轉(zhuǎn)換為二進(jìn)制形式排成一列，形成一個16*C位的二進(jìn)制數(shù)列即完成了染色體的編碼；

步驟十三.計算出每個染色體P_i⁰從起點到終點用時長度T_i，計算公式為其中，t_j表示從轉(zhuǎn)向點p^0i′_j航行到轉(zhuǎn)向點p^0i′_j+1所用的時間；采用積分的方法計算p^0i′_j到p^0i′_j+1這段航線上的時間，計算公式為視風(fēng)是真風(fēng)和船風(fēng)的矢量和，視風(fēng)計算公式為其中，v，θ分別表示視風(fēng)大小和方向，v₁，θ₁分別表示航速大小和航行方向，v₂，θ₂分別表示真風(fēng)大小和方向，s表示轉(zhuǎn)向點之間的直線距離；

步驟十四.根據(jù)帆船從起點到終點的時間設(shè)置評價函數(shù)eval(P_i)，用來對種群中的每個染色體P_iⁿ設(shè)定一個概率，P_iⁿ表示第n代的第i個染色體，以使該染色體被選擇的可能性與其種群中其它染色體的適應(yīng)性成比例，染色體的適應(yīng)性越強(qiáng)，被選擇的可能性也就越大，計算公式為

步驟十五.使用輪盤賭的選擇方法，具體操作如下：

1).對每個染色體P_i，計算累計概率q_i，公式如下所示：

2).從(0,q_C]中產(chǎn)生一個隨機(jī)數(shù)r；

3).如果q_i-1r≤q_i，則選擇第i個染色體P_i，i＝1,2,…,C；

4).重復(fù)2)和3)共C次，這樣可以得到C個復(fù)制的染色體

步驟十六.交叉方式采用單點交叉，具體操作如下：

1).首先定義種群中交叉概率為R_C，種群中有期望值為N*R_C個染色體將進(jìn)行交叉操作，

2).為了定義交叉操作的父代個體，從i＝1到i＝N重復(fù)以下過程：

3).從[0,1]中產(chǎn)生隨機(jī)數(shù)r，如果rR_C，則選擇P_iⁿ′作為一個父代，用P₁ⁿ′，P₂ⁿ′…表示上面選擇的父代，并把它們隨機(jī)分組；

4).當(dāng)父代個數(shù)為奇數(shù)時，則隨機(jī)去掉一個染色體以保證兩兩成對；

5.對于點(P′₁,P′₂)，隨機(jī)產(chǎn)生1個介于1和k之間的交叉點r，通過交換染色體P₁ⁿ′和P₂ⁿ′的第r至第C個基因來形成兩個后代，染色體P₁ⁿ′＝(pⁿ¹₁,pⁿ¹₂,…,pⁿ¹_C)，P₂ⁿ′＝(pⁿ²₁,pⁿ²₂,…,pⁿ²_C)，即：

X＝(pⁿ¹₁,pⁿ¹₂,…,pⁿ²_r,…,pⁿ²_C)

Y＝(pⁿ²₁,pⁿ²₂,…,pⁿ¹_r,…,pⁿ¹_C)

步驟十七.變異操作的具體步驟如下：

1).定義參數(shù)R_m為遺傳系統(tǒng)的變異概率，這個概率表明，種群中將有期望值為N*R_m個染色體用來進(jìn)行變異操作；

2).類似于交叉操作中選擇父代的過程，從i＝1到i＝C重復(fù)以下過程：

3).從區(qū)間[0,1]中產(chǎn)生隨機(jī)數(shù)r，如果rR_m，則選擇染色體P_iⁿ作為變異的父代，對每一個選擇的父代，用P_iⁿ＝(pⁿⁱ₁,pⁿⁱ₂,…,pⁿⁱ_j,…,pⁿⁱ_C)表示，按下面的方法進(jìn)行變異操作

4).首先選擇一個介于1與k之間的變異點s，如果該點基因為0，則將改基因替換為1，如果該點基因為1，則將改基因替換為0，形成的后代的基因型為：

P_iⁿ＝(pⁿⁱ₁,pⁿⁱ₂,…,pⁿⁱ_s-1,pⁿⁱ′_s,pⁿⁱ_s+1,…,pⁿⁱ_C)

其中，pⁿⁱ′_s表示變異點s上經(jīng)過基因轉(zhuǎn)變后的基因塊；

步驟十八.經(jīng)過上面的選擇、交叉和變異操作后，得到一個新的種群，原有的群體由新生一代所組成的群體來代替，重復(fù)上面的選擇、交叉、變異過程，直到染色體的用時T_i收斂到一個比較穩(wěn)定的解，終止計算；也可以選擇最大迭代次數(shù)作為進(jìn)化規(guī)劃算法的收斂判據(jù)，而且為了得到全局最優(yōu)解，如果設(shè)置最大迭代次數(shù)比較大，則相應(yīng)計算時間會比較長；實際中可以通過試探，確定一個比較合適的最大迭代次數(shù)作為收斂判據(jù)，從而減小計算時間；

步驟十九.解碼操作為，分別將用時T_i最短的P_iⁿ對應(yīng)的二進(jìn)制數(shù)字轉(zhuǎn)換為十進(jìn)制平面坐標(biāo)集合，P_iⁿ＝[pⁿⁱ₁,pⁿⁱ₂,…,pⁿⁱ_j…,pⁿⁱ_C]，其中,pⁿⁱ_j是第n代的第i個染色體的第j個轉(zhuǎn)向點，坐標(biāo)為(cⁿⁱ_j,dⁿⁱ_j)；

步驟二十.將上一步十進(jìn)制平面坐標(biāo)轉(zhuǎn)換為地理坐標(biāo)：

步驟二十一.將生成的轉(zhuǎn)向點連接成線，也就生成了帆船的最優(yōu)路徑。