[發明專利]一種基于粒子螢火蟲群優化算法的無人機航路路徑確定方法

有效

• 申請號: 201410807943.5
• 申請日: 2015-02-28
• 公開（公告）號: CN104573812B
• 公開（公告）日: 2018-06-01
• 發明（設計）人: 周永權;羅淇方;唐忠華
• 申請（專利權）人: 廣西民族大學
• 主分類號: G06N3/00
• 分類號: G06N3/00
• 代理公司: 重慶強大凱創專利代理事務所(普通合伙) 50217
• 代理人: 黃書凱

1.一種基于粒子螢火蟲群優化算法的無人機航路路徑確定方法，包括以下幾個步驟：

步驟一：根據任務信息確定路徑的起始點和目標點，并根據起始點和目標點確定飛行搜索區域；

步驟二：以起始點Q(x1，y1)為坐標原點，起始點Q(x1，y1)和目標點M(x2，y2)的連線為橫坐標X′，通過以下坐標變換公式實現把坐標點(x1，y1)變換為新坐標點(x′，y′)：

θ = a r c s i n y 2 - y 1 | A B → | - - - ( 1 ) ]]>

x y = c o s θ s i n θ - s i n θ cos θ · x ′ y ′ + x 1 y 1 - - - ( 2 ) ]]>

其中，(x，y)作為原坐標系中的點，經過變換后在新坐標系中的坐標為(x′，y′)，新舊坐標系之間的旋轉角度為θ；

將新坐標系Ox＇y＇的橫坐標X′上的坐標點分為D等分，在相應的節點上作垂線，得到相應縱坐標Y′上的坐標，按順序連接這些點，得到初始的飛行路徑；

步驟三：利用粒子螢火蟲群優化算法優化無人機路徑，其包括以下步驟：

3.1 參數初始化：對表示螢火蟲個數的種群規模n，表示空間的問題維數m，表示螢火蟲的進化代數G，螢火蟲的初始熒光素值l0，螢火蟲的視覺范圍即決策域r0，螢火蟲的初始移動步長st，高斯分布變異的方差σ參數初始化；

3.2 在新坐標系下，將其橫坐標劃分為D等分；

3.3 部署螢火蟲種群分布：假設每個螢火蟲個體飛行的軌跡對應一條候選路徑；

3.4 確定目標函數

min J＝kJt+(1-k)Jf (3)

計算螢火蟲個體對應航路的威脅代價值，wt表示航路上各點的威脅代價；wf表示各點的油耗代價，是航路長度的函數，實驗中，wf恒為1；k∈[0，1]表示安全性能與燃油性能的權衡系數，其值可根據無人機所執行的任務而定，如果任務重視飛行的安全性，則k選擇較大的值，如果任務需要飛機的快速性，則k選擇較小的值，其中威脅代價最小性能指標為：

min J t = ∫ 0 L w t d l - - - ( 4 ) ]]>

其中L為航路的長路，

油耗代價最小性能指標為

min J f = ∫ 0 L w f d l - - - ( 5 ) ]]>

其中L為航路的長路，

3.4.1 定義威脅總代價：當無人機沿路徑Li，j飛行時Nt個威脅源對其產生的總威脅代價為

w t , L i j = ∫ 0 L i , j Σ k = 1 N t t k [ ( x - x k ) 2 + ( y - y k ) 2 ] d l - - - ( 6 ) ]]>

3.4.2 簡化3.4.1的計算：把路徑Li，j分成5段，取其中的5個點來計算路徑Li，j所受到的威脅代價，若威脅點到邊的距離在威脅半徑之內，根據下式來計算其威脅代價：

w t , L i j = L i j 5 5 Σ k = 1 N t ( 1 d 0.1 , k 4 + 1 d 0.3 , k 4 + 1 d 0.5 , k 4 + 1 d 0.7 , k 4 + 1 d 0.9 , k 4 ) - - - ( 7 ) ]]>

式中，Lij為連接點i，j邊的長度；d0.1，k表示Li，j邊上1/10分點距第k個威脅源的距離；tk為威脅源的威脅等級，由于燃油代價與航程有關，故可簡單認為wf＝L，則對每條邊的燃油代價有

3.5 判斷是否達到最大進化代數G，若是，則進入步驟四，否則，進入步驟3.6；

3.6 螢火蟲群算法優化

3.6.1 螢火蟲位置分布階段：根據步驟3.4確定鄰居集合，將整個螢火蟲群隨機均勻分布在搜索空間中，每個螢火蟲攜帶等量的初始熒光素并擁有相同的初始感應半徑；

3.6.2 螢火蟲亮度更新階段：螢火蟲亮度反映了螢火蟲所處位置的優劣程度，螢火蟲越亮則表示其所在位置目標函數值越優，以較大的概率吸引其他螢火蟲向此目標飛行以搜尋出更好的解，整個種群所有螢火蟲個體亮度的都會據下式進行更新：

li(t)＝(1-ρ)li(t-1)+γJ(xi(t))i＝1，2，，，.n. (8)

式中，li(t)表示螢火蟲i在第t代的熒光素值；ρ和γ分別表示熒光素的衰減和增強因子；n表示螢火蟲種群的規模；J(xi(t))表示螢火蟲i所在位置對應的目標函數值；

3.6.3 螢火蟲位置移動階段，每個螢火蟲按照如下概率式在自身的鄰居集合中選擇一個鄰居并按概率式向其移動，螢火蟲選擇在其決策半徑內并且比自身亮的螢火蟲作為其鄰居：

p i j ( t ) = l j ( t ) - l i ( t ) Σ k ∈ N i ( t ) l k ( t ) - l i ( t ) - - - ( 9 ) ]]>

式中，j∈Ni(t)，Ni(t)表示螢火蟲i的鄰居集合，鄰居集合由如下等式確定

式中，dij(t)表示螢火蟲i與j在第t代的歐氏距離，表示螢火蟲i在第t代的鄰域范圍半徑，

x i ( t + 1 ) = x i ( t ) + s t * ( x j ( t ) - x i ( t ) | | x j ( t ) - x i ( t ) | | ) - - - ( 11 ) ]]>

上式中，st為移動步長，||·||表示歐氏距離；

3.6.4 螢火蟲決策半徑更新階段：決策半徑更新的主要目的是使其區域決策半徑隨著鄰居數量來調整大小：若鄰居密度小，螢火蟲加大其區域決策半徑搜尋更多鄰居，反之，若鄰居密度大，螢火蟲減少搜索半徑，螢火蟲決策半徑按如下公式進行更新：

r d i ( t + 1 ) = m i n { r s , m a x { 0 , r d i ( t ) + β ( n t - | N i ( t ) | ) } } - - - ( 12 ) ]]>

式中，β為決策區域控制常量，為螢火蟲i在第t代的決策半徑，nt為控制鄰居數量的閾值，|Ni(t)|為螢火蟲i在第t代的鄰居個數；

3.7 更新螢火蟲個體位置，按如下公式更新螢火蟲位置：

xi(t+1)＝xi(t)+c1*rand*(xj(t)-xi(t))+c2*rand*(xgb(t)-xi(t)) (13)

式中，xi(t)表示螢火蟲i在第t代的位置；xj(t)表示螢火蟲i的鄰居j在第t代的位置；xgb(t)是算法運行到第t代為止全局最優的螢火蟲的位置；c1、c2加速常數；rand為隨機數；

m(t)＝D-ceil(D*t/G)+1 (14)

式中，m(t)表示在第t代螢火蟲需更新的維數；D表示問題維數；ceil(·)是進一法取整函數；G表示最大迭代次數；

3.8 判斷當前進化代數是否是5的倍數，若不是進入步驟3.9，若是進入步驟3.8.1；

3.8.1 進行混合變異

3.8.1.1 據如下等式賦予每個螢火蟲個體一個變異能力值：

mc i = 0.05 + 0.45 ( exp ( 5 ( i - 1 ) / ( m - 1 ) ) - 1 ) exp ( 5 ) - 1 - - - ( 15 ) ]]>

式中，i表示螢火蟲個體編號，m表示種群規模；

3.8.1.2 令i＝1到m，當ceil(mci+rand-1＝＝1)時，若rand≤pu，則xi(t)＝(1+rand)*xi(t)，否則xi(t)＝Gaussian(σ)*xi(t)，

其中，Gaussian(σ)產生一個方差為σ且服從高斯分布的隨機數，Ceil(p)產生大于或等于p的最小整數，xi(t)表示第i只螢火蟲在第t代的位置，pu是進行均勻分布變異的概率因子，1-Pu進行高斯分布變異的變異因子，在粒子螢火蟲群優化算法中，采用線性變異因子，線性變異如下公式所示：

pu(t)＝1-t/G (16)

式中，t表示當前迭代次數；G表示最大迭代次數；

3.8.2 局部搜索：每五代在全局最優的螢火蟲附近執行一次局部搜索，若能搜索到更優的位置則用搜索到的位置代替螢火蟲原來位置并退出搜索，若執行4次局部搜索之后仍未能找到更優位置，則退出搜索，螢火蟲保持原來位置不變，局部搜索時新位置按下式計算：

xgb′(t)＝st(t)*rand*xgb(t) (17)

式中，xgb(t)代表全局最優最晚；st(t)表示第t代移動步長；xgb′(t)為搜索到的新位置，st(t)據下式進行計算：

st＝st(0)*(1-t/G)+10-4 (18)

式中，st(0)為初始移動步長；t為當前迭代次數G表示最大迭代次數；10-4為移動步長下界；

步驟四：根據

θ = a r c s i n y 2 - y 1 | A B → | ]]>

x y = c o s θ s i n θ - s i n θ cos θ . x ′ y ′ + x 1 y 1 , ]]>

坐標反轉換，得到無人機的最優路徑；

步驟五：輸出結果，得到無人機航路最優路徑的坐標軌跡。