[發(fā)明專利]一種基于遺傳算法的多USV群體協(xié)同避碰規(guī)劃方法

有效

• 申請?zhí)枺?/td>: 201910033307.4
• 申請日: 2019-01-14
• 公開（公告）號: CN109765890B
• 公開（公告）日: 2022-07-29
• 發(fā)明（設(shè)計）人: 王宏健;付忠健;于丹;徐欣;高娜
• 申請（專利權(quán)）人: 哈爾濱工程大學(xué)
• 主分類號: G05D1/02
• 分類號: G05D1/02;G06F30/15;G06F30/27;G06N3/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于遺傳算法的多USV群體協(xié)同避碰規(guī)劃方法，其特征在于，包括：

步驟一，采用浮點(diǎn)數(shù)編碼方式對USV的速度調(diào)節(jié)量和艏向調(diào)節(jié)量進(jìn)行初始化編碼并設(shè)置控制參數(shù)；

每個USV的初始種群設(shè)置50個個體，個體編碼長度為2，其中第j USV的每個個體i_j(Δv_ji,Δω_ji)包含當(dāng)前USV速度調(diào)節(jié)量Δv_ji和航行器艏向調(diào)節(jié)量Δω_ji兩部分；

任意設(shè)置第j USV的初始位置(x_j0,y_j0)，而每個USV初始速度v₀和初始艏向ω₀則分別取(10,40)節(jié)和(0°,360°)范圍內(nèi)的任意值；考慮到保證USV的航行穩(wěn)定性和避免出現(xiàn)大角度轉(zhuǎn)向與緊急加減速，設(shè)置每個USV的速度改變量的變化范圍為+2節(jié)到-2節(jié)，速度的變化范圍為10節(jié)到40節(jié)；每個USV的艏向變化量的變化范圍為-15°到+15°，即艏向調(diào)節(jié)量Δω初始化時取-15°～15°范圍內(nèi)的隨機(jī)數(shù)；

步驟二，構(gòu)建評價函數(shù)，計算出種群的每代個體的評價函數(shù)值從而對種群個體進(jìn)行輪盤賭選擇、離散交叉、高斯變異的遺傳操作，建立迭代過程得出最優(yōu)解；

每個USV進(jìn)行完當(dāng)前時刻狀態(tài)的尋優(yōu)后，下一時刻的當(dāng)前位置、當(dāng)前速度與艏向、終點(diǎn)位置、航行環(huán)境中障礙物的位置以及航行器到障礙物的距離參數(shù)發(fā)生了變化，需要重新進(jìn)行下一時刻的初始化種群，再找到這時刻的最優(yōu)解；由每一時刻的最優(yōu)速度調(diào)節(jié)量與艏向調(diào)節(jié)量組成了第j USV的一系列最優(yōu)解結(jié)構(gòu)為：

(Δv₀,Δω₀)→(Δv₁,Δω₁)→…→(Δv_m,Δω_m)→…→(Δv_n,Δω_n)

其中，(Δv_m,Δω_m)為第m次優(yōu)化的最優(yōu)解；

假設(shè)第j USV當(dāng)前的位置為(x_jm,y_jm)，當(dāng)前的速度和艏向為(v_jm,ω_jm)，第m步遺傳算法迭代得到最優(yōu)解為(Δv_jm,Δω_jm)，那么下一時刻的航速和艏向為：

下一時刻的位置為：

假設(shè)(x_j0,y_j0)和(x_jn,y_jn)為第j USV的起點(diǎn)和終點(diǎn)，(x_jm,y_jm)為第m次優(yōu)化的最優(yōu)解求出的路徑點(diǎn)，由此組成一條第j USV的最優(yōu)路徑，其結(jié)構(gòu)為：

(x_j0,y_j0)→(x_j1,y_j1)→…→(x_jm,y_jm)→…→(x_jn,y_jn)；

USV避碰規(guī)劃的評價函數(shù)取為：

其中，f為評價函數(shù)值，其值衡為正，f值越大被選擇成為子代的可能性越大；ω_i+1為USV下一時刻選取第i個體的艏向角；d₀為雷達(dá)坐標(biāo)系的原點(diǎn)到障礙物的最短距離；d₁表示本USV到另一USV的最短距離；d表示USV當(dāng)前位置到對應(yīng)終點(diǎn)的距離；ν和μ為障礙物邊界上下限角，γ和δ為另一USV邊界上下限角；

評價函數(shù)采取獎懲機(jī)制增大區(qū)分度，當(dāng)所取個體的下一時刻艏向角在障礙物邊界上下限角范圍內(nèi)或者另一USV邊界上下限角范圍內(nèi)，對其評價函數(shù)值縮小100倍使其被選擇的概率減小；當(dāng)所取個體的下一時刻的艏向角不在障礙物邊界上下限角范圍內(nèi)和另一USV邊界上下限角范圍內(nèi)，對其評價函數(shù)值擴(kuò)大100倍使其被選擇的概率增大，為極大值求解；

計算出種群個體的評價函數(shù)值后，選擇輪盤賭選擇法根據(jù)每個個體的評價函數(shù)值計算每個體被選擇組成子代的概率，評價函數(shù)值越大的個體被選擇的概率越大，并按照計算出的概率值隨機(jī)選擇個體組成下一代種群；

假設(shè)f(ji)為第j USV該代種群50個體的評價函數(shù)值，則每個體被選擇的概率為：

其中，i＝1,2,...,50；

每個個體的累計概率：

之后產(chǎn)生區(qū)間[0,1]范圍內(nèi)的隨機(jī)數(shù)p，若p＜q(i)，則選擇個體i；否則選擇滿足q(k-1)＜p＜q(k)條件的個體k，這樣重復(fù)50次后則完成了選擇操作；

采用離散交叉，即隨機(jī)選擇個體配對后個體之間交換變量值且子代個體隨機(jī)選擇父代個體，交叉概率設(shè)置為0.8，將兩個速度調(diào)節(jié)量和艏向調(diào)節(jié)量分開交叉，即航速變化量基因與航速變化量基因交叉、艏向變化量基因與艏向變化量基因交叉；

選擇高斯變異方式，即產(chǎn)生一個服從高斯概率分布的隨機(jī)數(shù)取代原來個體，設(shè)置種群個體的倒數(shù)0.02為變異概率，按照該變異概率選擇個體的某個變量進(jìn)行變異操作；

為了有效解決交叉、變異進(jìn)化過程中隨機(jī)性較強(qiáng)搜索效率低下致使進(jìn)化迭代過程中出現(xiàn)子代最優(yōu)個體劣于父代最優(yōu)個體的“退化”，在傳統(tǒng)遺傳算法的基礎(chǔ)上添加了保留操作，即比較父代子代種群的評價函數(shù)值，將其中最優(yōu)個體完整的保留到下一代中；

最后，經(jīng)過若干代種群的迭代后判斷算法是否滿足迭代結(jié)束條件，若滿足，則輸出最優(yōu)個體的航速變化量和艏向變化量；若不滿足，則重新構(gòu)造評價函數(shù)進(jìn)行迭代。