李 鵬，李兵艦，亓 亮，陳凱翔，李 迪

(中國(guó)船舶重工集團(tuán)公司第七二三研究所，江蘇 揚(yáng)州 225101)

0 引 言

航路規(guī)劃是無(wú)人機(jī)實(shí)現(xiàn)自主飛行的基礎(chǔ)，是典型的多目標(biāo)大范圍優(yōu)化問(wèn)題。梯度法收斂速度快，但對(duì)目標(biāo)函數(shù)要求高，且容易陷入局部最優(yōu)解；動(dòng)態(tài)規(guī)劃算法能夠求得最優(yōu)解，但維數(shù)越大，計(jì)算量越大；遺傳算法穩(wěn)定性強(qiáng)，但收斂速度不快，容易早熟；稀疏A*算法能夠減少搜索空間，但求解時(shí)間隨著規(guī)劃空間的增大越來(lái)越長(zhǎng)。本文結(jié)合遺傳算法，對(duì)粒子群算法的種群進(jìn)行交叉、變異等遺傳操作，提高種群的多樣性，避免種群陷入“早熟”，從而獲得目標(biāo)函數(shù)的最優(yōu)解。為了驗(yàn)證遺傳-粒子群優(yōu)化(GA-PSO)算法的性能，通過(guò)4個(gè)基準(zhǔn)測(cè)試函數(shù)對(duì)GA-PSO算法進(jìn)行測(cè)試。結(jié)果表明，較常規(guī)的PSO算法，GA-PSO算法具有更快的收斂速度和收斂精度。針對(duì)無(wú)人機(jī)航路規(guī)劃問(wèn)題，采用GA-PSO算法進(jìn)行仿真實(shí)驗(yàn)，得到了理想的無(wú)人機(jī)航路，驗(yàn)證了GA-PSO在航路規(guī)劃中的有效性。

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

1.1 標(biāo)準(zhǔn)粒子群算法

粒子群優(yōu)化算法的思路如下：群體中的各個(gè)粒子具備自我學(xué)習(xí)能力，也可以根據(jù)群體中其他粒子的經(jīng)驗(yàn)知識(shí)進(jìn)行學(xué)習(xí)，根據(jù)學(xué)習(xí)結(jié)果，動(dòng)態(tài)地改變粒子的速度，整個(gè)群體通過(guò)各個(gè)粒子之間的信息交換，實(shí)現(xiàn)群體協(xié)作，進(jìn)而優(yōu)化群體行為[1]。標(biāo)準(zhǔn)粒子群算法中，粒子的更新過(guò)程如式(1)和(2)所示：

Vid(t+1)=wVid(t)+c1r1(Pid-Xid(t))+

c2r2(Pgd-Xid(t))

(1)

Xid(t+1)=Xid(t)+Vid(t+1)

(2)

式中：i=1，2，…，N，N為粒子規(guī)模；d=1，2，…，D，D為粒子的維數(shù)；t為當(dāng)前迭代次數(shù)；r1、r2為0～1的隨機(jī)數(shù)，能使粒子群呈現(xiàn)多樣性；w為慣性權(quán)重，用來(lái)平衡群體的全局搜索與局部探測(cè)能力(取值越大，越利于全局搜索，取值越小，越利于局部搜索)。

線性減小的慣性權(quán)重w的數(shù)學(xué)公式為[2]：

(3)

式中：通常wmax取0.9；wmin=0.4；I為迭代次數(shù)的最大值；i為當(dāng)前迭代次數(shù)。

c1、c2為學(xué)習(xí)因子，一般，c1=c2=1.496 2，c1、c2能夠使粒子自動(dòng)調(diào)整并接受群體中其它粒子的優(yōu)點(diǎn)，然后根據(jù)自己搜索到的歷史最優(yōu)位置和整個(gè)群體中的最優(yōu)位置進(jìn)化。

從式(1)和式(2)可以看出，粒子的移動(dòng)速度由三部分決定，自己原有的速度Vid、與自己的歷史最優(yōu)位置的距離(Pid-Xid)和與全體最優(yōu)位置的距離(Pgd-Xid)，并分別由權(quán)重系數(shù)w、c1和c2來(lái)決定其相對(duì)重要性。

1.2 量子粒子群算法

量子粒子群算法(QPSO)按照式(4)～(7)進(jìn)行粒子位置更新，則：

pi=(r1×pbest+r2×gbest)/(r1+r2)

(4)

L=(1/g)×abs(xid-pi)

(5)

(6)

式中：r1、r2和u都是0～1的隨機(jī)數(shù)；g稱為收縮系數(shù)；p沒(méi)有明確定義，為勢(shì)場(chǎng)位置參數(shù)[3]。

和標(biāo)準(zhǔn)粒子群算法一樣，為了后期擴(kuò)大搜索范圍使目標(biāo)函數(shù)值達(dá)到更優(yōu)值，收縮系數(shù)g的值,按照線性遞增的規(guī)則，從 0.6 逐漸遞增至 0.8，其更新公式如下：

g=0.6+0.2×i/I

(7)

可以看出：量子粒子群(QPSO)算法只有粒子更新方式和PSO算法不同，QPSO算法沒(méi)有速度參數(shù)，因而可以避免速度限制導(dǎo)致的全局搜索能力下降的問(wèn)題。

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

量子粒子群算法具有參數(shù)少、原理簡(jiǎn)單、通用性強(qiáng)、容易實(shí)現(xiàn)等優(yōu)點(diǎn)，由于沒(méi)有速度的限制，比常規(guī)粒子群算法具有更強(qiáng)的全局搜索能力，但是仍存在著收斂速度慢、容易陷入局部最優(yōu)的缺陷。通過(guò)增加粒子群數(shù)目，可以增強(qiáng)群體的全局搜索能力，但群體“早熟”的問(wèn)題沒(méi)有從根本上解決。

遺傳算法基于對(duì)自然界優(yōu)勝劣汰的進(jìn)化機(jī)制進(jìn)行模擬而提出，根據(jù)自然界的選擇、交叉、變異等遺傳現(xiàn)象，根據(jù)選定的適應(yīng)度函數(shù)對(duì)個(gè)體進(jìn)行篩選，淘汰適應(yīng)能力差的個(gè)體，保留適應(yīng)能力強(qiáng)的個(gè)體，并組成新群體。這樣，經(jīng)過(guò)多次循環(huán)，實(shí)現(xiàn)群體的進(jìn)化[3]。遺傳算法具有較強(qiáng)的全局搜索能力，但是局部搜索能力不足。

常規(guī)量子粒子群算法，在對(duì)粒子進(jìn)行更新時(shí)，沒(méi)有進(jìn)行任何判斷，因此會(huì)存在更新后粒子適應(yīng)值變差的情況。

本文在量子粒子群算法的基礎(chǔ)上，在粒子進(jìn)行更新時(shí)，先對(duì)粒子適應(yīng)值進(jìn)行判斷，如果能夠使適應(yīng)值更好，則更新，否則不更新，為保持粒子群一定的多樣性，判斷完成后，再以一定概率更新。

同時(shí)，針對(duì)常規(guī)量子粒子群算法容易“早熟”的問(wèn)題，本文結(jié)合遺傳算法，增強(qiáng)群體在搜索過(guò)程中得到全局最優(yōu)解的能力。具體步驟為：首先，計(jì)算粒子的適應(yīng)值，并排序，根據(jù)適應(yīng)值大小的順序?qū)αＷ舆M(jìn)行兩兩配對(duì)；然后根據(jù)其適應(yīng)值的大小，賦予一定的隨機(jī)雜交概率，適應(yīng)值越高，則進(jìn)行雜交操作的概率越小，反之則越大，依據(jù)雜交概率對(duì)配對(duì)的2個(gè)粒子進(jìn)行雜交；最后，按照一定的變異概率對(duì)雜交后的粒子進(jìn)行初始化，同樣按照適應(yīng)值的不同決定變異概率。

可以看出，該方法能夠增加粒子多樣性，群體中優(yōu)良粒子的特性得到充分利用，群體收斂速度加快，多樣性得到提高，避免了過(guò)早收斂。

雜交過(guò)程中，孩子粒子的位置由父母粒子的位置的算數(shù)加權(quán)來(lái)計(jì)算，即：

X1(t′)=r·X1(t)+(1-r())·X2(t)

(8)

(9)

式中：X為位置；而X1(t)和X2(t)為用來(lái)進(jìn)行雜交的粒子；r()為D維隨機(jī)變量；各分量在0～1間均勻分布。

由于該方法結(jié)合了遺傳算法，因此稱為GA-PSO算法，運(yùn)算步驟如下：

(1) 初始化粒子群。初始化粒子群，包括粒子群的大小、維數(shù)、粒子的位置、收縮系數(shù)等。

(2) 收縮系數(shù)g，依據(jù)式(4)～(7)更新粒子的位置(X1(k)，X2(k)，…，Xn(k))。

(3) 計(jì)算每個(gè)粒子的適應(yīng)值，根據(jù)適應(yīng)值大小進(jìn)行排序，并兩兩配對(duì)。

(4) 根據(jù)適應(yīng)值大小，賦予每個(gè)粒子一定的隨機(jī)雜交概率，適應(yīng)值越大，進(jìn)行雜交的概率越大；反之，越小。

行為風(fēng)格或人格能夠影響創(chuàng)造力，創(chuàng)造力與行為風(fēng)格或人格密切相關(guān)。早期的研究就發(fā)現(xiàn)了一些較為穩(wěn)定的人格對(duì)創(chuàng)造力有很大影響，如內(nèi)在動(dòng)機(jī)、寬廣的興趣、審美敏感、容忍模糊、直覺(jué)、冒險(xiǎn)、韌性與自信、不關(guān)注公眾認(rèn)可等。巴龍、愛(ài)杜森等人在研究科學(xué)家的創(chuàng)造力時(shí)發(fā)現(xiàn)，高度的自我力量、獨(dú)立自主的強(qiáng)烈需要、較高的自信水平、陶醉于所熱愛(ài)和傾注的事業(yè)等是創(chuàng)造者的共同個(gè)性特征?？祟D(1989)發(fā)現(xiàn)那些具有“創(chuàng)新性”解決問(wèn)題的人往往以“新穎的”方式解決看似普通的問(wèn)題，甚至重新“界定問(wèn)題表征”，然后再找尋答案。他說(shuō)，這些創(chuàng)造性行為風(fēng)格是較為穩(wěn)定的，一旦形成，就會(huì)貫穿于解決絕大多數(shù)問(wèn)題的過(guò)程之中。

(5) 對(duì)進(jìn)行雜交操作后的粒子按照變異概率進(jìn)行變異操作，變異概率同樣根據(jù)適應(yīng)值確定，適應(yīng)值越大，則變異概率越大；反之，則越小。

(6) 計(jì)算每個(gè)粒子的歷史最優(yōu)值和全局最優(yōu)值，并比較。如果粒子的當(dāng)前適應(yīng)度值好于歷史值，則替換該粒子適應(yīng)值和歷史最優(yōu)位置；如果粒子的歷史最優(yōu)適應(yīng)值好于全局最優(yōu)值，則替換全局最優(yōu)適應(yīng)值為該歷史最優(yōu)值，并記錄對(duì)應(yīng)的全局最優(yōu)粒子的位置。

(7) 判斷是否有粒子達(dá)到目標(biāo)值。如果有，退出循環(huán)，求出最優(yōu)解；否則跳轉(zhuǎn)到(2)，重新進(jìn)行迭代操作。

1.4 改進(jìn)效果仿真

為了驗(yàn)證GA-PSO算法的有效性，采用4個(gè)常用的測(cè)試函數(shù)進(jìn)行測(cè)試[4]，文獻(xiàn)[4]論述了這4個(gè)函數(shù)驗(yàn)證粒子群算法的尋優(yōu)性能及其代表性。這4個(gè)函數(shù)分別是：

(1) Sphere函數(shù)：

(10)

(2) Griewank函數(shù)：

(11)

(3) Rastrigin函數(shù)：

(12)

(4) Rosenbrock函數(shù)：

(13)

式中：函數(shù)f1為單峰函數(shù)，當(dāng)所有未知量都取0時(shí)，達(dá)到最?。籪2的最小值也在所有未知量取0時(shí)得到，且存在很多的局部極小點(diǎn)；f3存在一個(gè)全局最小值fmin=0，且具有大量局部極值點(diǎn)；f4為一個(gè)非凸函數(shù)，在(1,1,…,1)達(dá)到最小。

仿真實(shí)驗(yàn)中，粒子群規(guī)模取60，迭代次數(shù)取300，粒子維數(shù)取10，參數(shù)變化范圍為[-10，10]，變異系數(shù)取0.6，收縮系數(shù)從0.6線性增加至0.8。對(duì)上述4個(gè)測(cè)試函數(shù)，分別使用QPSO和改進(jìn)的粒子群算法(GAQPSO)計(jì)算其最小值，試驗(yàn)重復(fù)進(jìn)行100次，結(jié)果取平均值。為了更好地表現(xiàn)2種算法的差異，目標(biāo)函數(shù)適應(yīng)值取以10為底的對(duì)數(shù)進(jìn)行顯示。得到目標(biāo)函數(shù)適應(yīng)值隨迭代次數(shù)變化曲線如圖1～圖4所示。

圖1 Sphere函數(shù)適應(yīng)值隨迭代次數(shù)變化曲線

圖2 Griewank函數(shù)適應(yīng)值隨迭代次數(shù)變化曲線

圖3 Rastrigin函數(shù)適應(yīng)值隨迭代次數(shù)變化曲線

圖4 Rosenbrock函數(shù)適應(yīng)值隨迭代次數(shù)變化曲線

從以上結(jié)果可以看出，對(duì)于4種測(cè)試函數(shù)，GA-PSO算法收斂速度更快，能夠得到比常規(guī)的粒子群算法更優(yōu)的最優(yōu)解，說(shuō)明其具有更強(qiáng)的搜索能力，優(yōu)化性能顯著提高。

2 航路規(guī)劃

無(wú)人機(jī)航路規(guī)劃過(guò)程需要對(duì)飛行區(qū)域的基準(zhǔn)地形、障礙區(qū)域和威脅區(qū)域進(jìn)行分析研究，通過(guò)把地形、障礙和威脅等環(huán)境信息建立成帶有屬性特征和空間位置特征的數(shù)字地圖，進(jìn)行航跡路線建模，完成航路規(guī)劃[5]。

2.1 環(huán)境建模

根據(jù)無(wú)人機(jī)航路規(guī)劃的特點(diǎn)，其環(huán)境建模主要包括3個(gè)：基準(zhǔn)地形建模、障礙區(qū)域建模以及威脅區(qū)域建模。

基準(zhǔn)地形建模中，將飛行區(qū)域抽象為一個(gè)帶有坐標(biāo)信息的三維空間，空間中每個(gè)點(diǎn)的Z坐標(biāo)可以設(shè)為M×r，即0～M之間的隨機(jī)數(shù)。

采用山峰模型進(jìn)行障礙區(qū)域建模，其近似公式如下：

(14)

式中：z(x，y)為每個(gè)點(diǎn)的高度；i代表第i座山；(xi，yi)為第i座山的地理中心坐標(biāo)；hi為其高度；xsi為第i座山在x軸方向的坡度；ysi為第i座山在y軸方向的坡度(坡度值太小將導(dǎo)致山體坡度較大，不能起到障礙作用；太大會(huì)導(dǎo)致山體坡度較小，山體間會(huì)沖突)。

采用雷達(dá)近似模型進(jìn)行威脅區(qū)域建模，雷達(dá)探測(cè)區(qū)域的水平距離和雷達(dá)高度之間的關(guān)系可以用下式描述：

H=KR2

(15)

式中：K為與雷達(dá)特性(如信噪比、發(fā)射功率等)有關(guān)的系數(shù)。

無(wú)人機(jī)進(jìn)入到雷達(dá)探測(cè)范圍后，被探測(cè)到的概率p=Rmax4/(Rmax4+R4)，該概率是關(guān)于R4的泊松分布。Rmax表示雷達(dá)的最大作用距離，由雷達(dá)的參數(shù)確定。

雷達(dá)的探測(cè)特性受環(huán)境影響較大，其建模將十分復(fù)雜。為了驗(yàn)證算法的有效性，本文簡(jiǎn)化雷達(dá)探測(cè)性能的建模，用半徑為rs的半球體來(lái)近似表示雷達(dá)的探測(cè)范圍。

根據(jù)障礙山峰模型，建立的航跡規(guī)劃的環(huán)境模型如圖5所示。

圖5 航跡規(guī)劃環(huán)境模型

2.2 航跡路線建模

2.2.1 航跡路線建模

通過(guò)建立航跡評(píng)價(jià)函數(shù)，能夠衡量航線的優(yōu)劣，本文選擇航跡長(zhǎng)度Lp、最小轉(zhuǎn)彎角θmin和最低飛行高度hmin作為航跡評(píng)價(jià)函數(shù)的參數(shù)項(xiàng)，其他因素如風(fēng)速、轉(zhuǎn)彎半徑等，為簡(jiǎn)化問(wèn)題，本文進(jìn)行了忽略。

航跡長(zhǎng)度Lp表示無(wú)人機(jī)的飛行路程，顯然，該值越小越好。假設(shè)第i個(gè)航路點(diǎn)(xi,yi,zi)與第i+1個(gè)航路點(diǎn)(xi+1,yi+1,zi+1)間的距離為li，則2個(gè)航路點(diǎn)的距離為：

(16)

(17)

最小轉(zhuǎn)彎角θmin表示無(wú)人機(jī)最小拐彎角度，該值越小，路線越平穩(wěn)。

最低飛行高度hmin表示無(wú)人機(jī)與地形間的最短距離，該值越小，無(wú)人機(jī)與地形碰撞的幾率越大。

根據(jù)以上參考項(xiàng)，建立航跡評(píng)價(jià)函數(shù)如下：

(18)

式中：P為航路點(diǎn)總個(gè)數(shù)；Li為第i個(gè)航路點(diǎn)與第i-1個(gè)航路點(diǎn)間的距離。

總航跡長(zhǎng)度L=L2+L3+…+LP，Ti為第i個(gè)航路點(diǎn)處的威脅值，包含最小轉(zhuǎn)彎角度和最低飛行高度2個(gè)因素。φ1和φ2為0 ～ 1之間的權(quán)重系數(shù)，φ1越大，航跡長(zhǎng)度值越大；φ2越大，威脅項(xiàng)加權(quán)后的值越大。仿真中，φ1取為0.75，φ2取為0.25。

2.2.2 最優(yōu)航線求解

使用粒子群算法求解最優(yōu)航線時(shí)，每個(gè)粒子X(jué)i代表一條航線，Xi=(xid,yid,zid)，d=1,2,…,D，i=1,2,…,N，D表示粒子的維數(shù)，即每條航線包含的節(jié)點(diǎn)數(shù)，N表示粒子的個(gè)數(shù)。

為了使航線更加平滑，需要對(duì)所有的航路點(diǎn)進(jìn)行擬合，每2個(gè)航路點(diǎn)內(nèi)插Pin個(gè)點(diǎn)[6]。

擬合結(jié)束后，第d個(gè)航路點(diǎn)和第d+1個(gè)航路點(diǎn)之間的航路距離為這2個(gè)航路點(diǎn)及其之間所有內(nèi)插點(diǎn)連線的長(zhǎng)度，計(jì)算公式如下：

Ld=

(19)

得到航跡的長(zhǎng)度值和威脅值后，就能計(jì)算最優(yōu)航跡的評(píng)價(jià)值，根據(jù)該評(píng)價(jià)值判斷航跡的優(yōu)劣。

3 仿真試驗(yàn)與分析

假定無(wú)人機(jī)的飛行區(qū)域設(shè)置為300×300，出發(fā)點(diǎn)坐標(biāo)為(11,271,11)，目的地坐標(biāo)為(291,31,11)，7個(gè)山峰模型的參數(shù)分別為(151,250,120)、(230,60,50)、(50,150,100)、(100,100,90)、(50,50,60)、(150,180,70)、(160,50,80)，雷達(dá)模型的參數(shù)為(250,200,60)。

設(shè)定最大迭代次數(shù)I為150，粒子群數(shù)量N為50，粒子維數(shù)D為7，內(nèi)插點(diǎn)個(gè)數(shù)Pin為8，變異系數(shù)取0.6，收縮系數(shù)從0.6線性增加至0.8。

為了測(cè)試GA-PSO算法進(jìn)行無(wú)人機(jī)航路規(guī)劃的性能，進(jìn)行仿真實(shí)驗(yàn)，并和量子粒子群算法進(jìn)行比較，每種算法運(yùn)行50次，實(shí)驗(yàn)結(jié)果如圖6所示。

圖6 目標(biāo)函數(shù)適應(yīng)值隨迭代次數(shù)變化情況

從圖6可知，GA-PSO算法由于在粒子更新過(guò)程中引入了遺傳算法的操作，收斂速度明顯加快，且具有更好的尋優(yōu)能力。

使用GA-PSO算法得到的最優(yōu)航跡路線如圖7、圖8所示，為了使航跡更符合實(shí)際，對(duì)兩兩航跡點(diǎn)進(jìn)行擬合，這樣，航線更為平滑。

圖7 航跡規(guī)劃三維立體圖

圖8 航跡規(guī)劃三維俯視圖

4 結(jié)束語(yǔ)

本文結(jié)合遺傳算法，對(duì)粒子群算法的種群進(jìn)行交叉、變異等遺傳操作。對(duì)粒子進(jìn)行更新時(shí)，先進(jìn)行判斷，只有當(dāng)粒子更新后具有更好的適應(yīng)值時(shí)，才以一定的概率進(jìn)行更新；否則，不更新，種群多樣性得到提高，避免陷入“早熟”，從而得到目標(biāo)函數(shù)的最優(yōu)解。通過(guò)基準(zhǔn)測(cè)試函數(shù)對(duì)GA-PSO算法進(jìn)行測(cè)試，并與常規(guī)粒子群優(yōu)化算法進(jìn)行比較，結(jié)果表明，GA-PSO算法收斂速度更快、精度更高。針對(duì)無(wú)人機(jī)航路規(guī)劃問(wèn)題，采用GA-PSO算法進(jìn)行仿真，結(jié)果表明，采用本文提出的GA-PSO算法，能夠得到滿足要求的最優(yōu)航跡，而且，在種群維度較高的情況下，也能夠保證較高的航跡精度。