面向無人機(jī)三維航跡規(guī)劃的改進(jìn)粒子群優(yōu)化算法

宋 宇， 王志明

(長(zhǎng)春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，吉林 長(zhǎng)春 130012)

0 引 言

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

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

本文提出了結(jié)合模糊C均值(fuzzy C means,FCM)算法的改進(jìn)粒子群算法，在路徑規(guī)劃仿真實(shí)驗(yàn)中有效地避開了障礙物(局部最優(yōu))。

1 粒子群算法

在基本粒子群算法的迭代過程中，每個(gè)待選解(粒子的位置)都具有向全局最優(yōu)解與每個(gè)粒子當(dāng)前發(fā)現(xiàn)的最優(yōu)解的速度之和移動(dòng)的趨勢(shì)。每個(gè)待選解(粒子的位置)位置變化為

(1)

(2)

2 FCM算法

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

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

2)分別計(jì)算c個(gè)類的類中心P，P為一個(gè)c行n列的矩陣，每行代表一個(gè)類中心點(diǎn)

(3)

式中k為一個(gè)加權(quán)指數(shù)，一般取2。

3)計(jì)算距離矩陣D,D為一個(gè)大小為c×m的矩陣，其中Dij為第i個(gè)類中心到第j個(gè)數(shù)據(jù)點(diǎn)的距離

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

(4)

3 改進(jìn)粒子群算法

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

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

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

(5)

(6)

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

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

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

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

(7)

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

4 仿真實(shí)驗(yàn)

實(shí)驗(yàn)結(jié)果如圖1。由圖可知，經(jīng)改進(jìn)算法優(yōu)化迭代后得到的解更優(yōu)。

圖1 算法改進(jìn)前后對(duì)比

5 結(jié) 論

仿真實(shí)驗(yàn)的結(jié)果表明：改進(jìn)算法成功得到了落在障礙物以外的中間路徑點(diǎn)，且利用改進(jìn)算法找到的最優(yōu)路徑的距離的精度也大為改善。