面向無人機三維航跡規劃的改進粒子群優化算法

宋 宇， 王志明

(長春工業大學 計算機科學與工程學院，吉林 長春 130012)

0 引 言

無人機的自主化需要無人機各個模塊的協同工作，無人機的研究方向有路徑規劃、飛行控制、空間定位、圖像識別、飛行器設計[1]。其中，無人機的路徑規劃中當環境已知時，路徑規劃算法一般有：群智能算法，A*算法，D*算法，可視圖法，元胞自動機算法；其中常見的群智能算法有蟻群算法，粒子群算法等[2～6]。

引入粒子濃度機制,將當前代中適應度低且濃度大的粒子的交叉變異概率提高,使得這些粒子在下一次迭代中交叉變異的可能性變大，這種方法改進了基本粒子群算法在無人機三維航跡規劃后期收斂速度慢的問題[7]；通過自然選擇機制，對所有粒子按適應度值排序后，用適應度較好的前一半的粒子取代適應度差的后一半粒子，同時在粒子速度更新公式中保留所有粒子所記憶的最優位置，有效地增加了粒子的全局尋優能力，改善了基本粒子群算法在路徑規劃中易陷入局部最優解的問題[8]；用適應度值加權后的所有粒子經歷的最優位置，代替單個粒子的所記憶的最優位置的，充分利用全部粒子的個體最優位置信息，有效地加強了粒子群算法在路徑規劃中的尋優能力[9]；在灰狼算法中，利用第一優個體與第三優個體的差值所帶來的當前尋優狀態信息,當最優個體位置與第三優個體位置的差值大于給定閾值時采用適應度值加權的速度更新策略，增強了算法的全局尋優能力[10]；無免費午餐定理指出不存一個群啟發式算法對解決所有的優化問題都表現最佳[11]。

本文提出了結合模糊C均值(fuzzy C means,FCM)算法的改進粒子群算法，在路徑規劃仿真實驗中有效地避開了障礙物(局部最優)。

1 粒子群算法

在基本粒子群算法的迭代過程中，每個待選解(粒子的位置)都具有向全局最優解與每個粒子當前發現的最優解的速度之和移動的趨勢。每個待選解(粒子的位置)位置變化為

(1)

(2)

2 FCM算法

FCM算法將所有待分類中每個點的隸屬度取值為0～1之間的數。模糊C均值算法的步驟如下：

1)給定待分類的數據矩陣A,A的大小為m×n，m為待分類點的個數,n為每個點的維數,準備將給定數據分為c類，隨機初始化隸屬度矩陣W,W為一個c行m列，滿足每列之和都等于1，其中的Wij指代第j個待選解(粒子位置)對第i個類的隸屬度值。

2)分別計算c個類的類中心P，P為一個c行n列的矩陣，每行代表一個類中心點

(3)

式中k為一個加權指數，一般取2。

3)計算距離矩陣D,D為一個大小為c×m的矩陣，其中Dij為第i個類中心到第j個數據點的距離

4)更新隸屬度矩陣中wij的值

(4)

3 改進粒子群算法

1)隨機初始化粒子位置(可能解)矩陣，隨機初始化粒子速度(可能解在一次迭代中的變化量)矩陣，設定粒子位置與速度的最大最小值。

2)調用FCM算法，準備將所有粒子分為g類，得到停止分類后的隸屬度矩陣，再根據得到的隸屬度矩陣用輪盤賭算法最終確定每個粒子分別屬于哪類。

3)分別計算每個粒子的適應度函數值，得到本次迭代中每個類內適應度值最優粒子位置goal(i,:)與全部粒子到目前為止所經歷的全局最優粒子位置globle，為了防止算法陷入局部最優，此處的goal(i,:)不具有記憶性，goal(i,:)的值僅取決于當前代第i類內的最優粒子位置，而此處的globle為具有記憶性的目前為止所有迭代次數中最優粒子的位置，算法按照式(5)更新待選解的改變量(粒子速度)，按照式(6)更新待選解的值(粒子位置)

(5)

(6)

4)將待選解(粒子位置)的速度與位置的越界值賦值為規定的邊界值。

5)判斷當前迭代次數是否為g的倍數：若否，跳到步驟(6)；若是，再次調用FCM算法，根據FCM算法得到的隸屬度矩陣，按輪盤賭算法確定每個粒子屬于哪類。

6)迭代次數加1，若未達到最大迭代次數，跳到步驟(3)，若達到最大迭代次數，算法結束。

為了增加粒子群算法在全局最優解附近的搜索精度，可將式(5)替換為

(7)

式中 增加的最后一項為每個粒子趨向類內其他粒子的速度分量，p為從1到本類最大粒子數目的隨機數，classi(p)為一個本類內部隨機選定的粒子的位置，w1取為0.1。

4 仿真實驗

實驗結果如圖1。由圖可知，經改進算法優化迭代后得到的解更優。

圖1 算法改進前后對比

5 結 論

仿真實驗的結果表明：改進算法成功得到了落在障礙物以外的中間路徑點，且利用改進算法找到的最優路徑的距離的精度也大為改善。