振動(dòng)遺傳算法在無(wú)人機(jī)三維航路規(guī)劃的算法研究*

席慶彪，李 康，劉慧霞

（1.西北工業(yè)大學(xué)自動(dòng)化學(xué)院，西安 710061；2.西北工業(yè)大學(xué)第365研究所，西安 710065）

振動(dòng)遺傳算法在無(wú)人機(jī)三維航路規(guī)劃的算法研究*

席慶彪1，2，李 康1，劉慧霞1，2

（1.西北工業(yè)大學(xué)自動(dòng)化學(xué)院，西安 710061；2.西北工業(yè)大學(xué)第365研究所，西安 710065）

針對(duì)代價(jià)函數(shù)權(quán)重需要根據(jù)環(huán)境變化而變化的問(wèn)題，結(jié)合飛行約束條件提出歸一化的代價(jià)函數(shù)，當(dāng)環(huán)境發(fā)生變化時(shí)，不用再修改代價(jià)函數(shù)，增強(qiáng)了算法的魯棒性。為了彌補(bǔ)傳統(tǒng)定步長(zhǎng)尋徑算法耗時(shí)長(zhǎng)的缺陷，設(shè)計(jì)了一種基于B樣條曲線與遺傳算法的高時(shí)效尋徑算法。利用遺傳算法在地圖中所尋合適的控制點(diǎn)，再結(jié)合B樣條曲線生成航路。為了增強(qiáng)遺傳算法的全局搜索能力，遺傳算法中加入振動(dòng)法則，使得種群在進(jìn)化中后期依舊保持一定的多樣性。仿真結(jié)果表明該算法與精英蟻群算法相比，規(guī)劃時(shí)間大幅縮短；與振動(dòng)遺傳算法相比，航路代價(jià)明顯降低。

歸一化，航路規(guī)劃，B樣條曲線，振動(dòng)遺傳算法

引言

隨著近年來(lái)戰(zhàn)場(chǎng)環(huán)境和無(wú)人機(jī)所承擔(dān)的任務(wù)的復(fù)雜化，無(wú)人機(jī)在飛行過(guò)程中可能遇到事先沒(méi)有偵測(cè)到的威脅或臨時(shí)改變?nèi)蝿?wù)，其必須在飛行過(guò)程中及時(shí)規(guī)劃出一條新的安全航路，由此對(duì)航路規(guī)劃算法的實(shí)時(shí)性提出了更高的要求。目前常見(jiàn)的算法其耗時(shí)通常在十幾秒到幾十秒不等，難以滿足新環(huán)境下對(duì)無(wú)人機(jī)航路搜索算法的實(shí)時(shí)性要求。

為了提高算法的實(shí)時(shí)性，學(xué)者們開(kāi)始嘗試并行算法與B樣條曲線相結(jié)合的方法［1-3］。本文將常見(jiàn)的代價(jià)函數(shù)進(jìn)行歸一化設(shè)計(jì)，避免了在陌生環(huán)境下權(quán)重不易分配的難題，且當(dāng)環(huán)境發(fā)生變化時(shí)，不用再修改代價(jià)函數(shù)。采用遺傳算法與B樣條曲線相結(jié)合的方法，B樣條曲線能只通過(guò)少數(shù)點(diǎn)生成整條航路，因此，時(shí)間開(kāi)銷與空間開(kāi)銷更少，并且得到的航路光滑、可導(dǎo)，更適于無(wú)人機(jī)飛行。在遺傳算法中加入振動(dòng)法則和新的種群，以此增加遺傳算法的種群多樣性。在三維環(huán)境下，將本文算法分別與定步長(zhǎng)算法蟻群算法和文獻(xiàn)［3］中振動(dòng)遺傳算法進(jìn)行仿真對(duì)比；最后進(jìn)行重規(guī)劃仿真，驗(yàn)證其實(shí)時(shí)性和魯棒性。

1 問(wèn)題描述

假設(shè)存在三維空間（x，y，z），其中x∈［0，mapx］，y∈［0，mapy］，z∈［0，mapz］，存在起點(diǎn)（xs，ys，zs）、終點(diǎn)（xd，yd，zd）及n個(gè)半徑為Rn的圓柱形威脅區(qū)域（xrn，yrn），且（xrn，yrn）滿足xrn∈［0，mapx］，yrn∈［0，mapy］。

2 代價(jià)函數(shù)設(shè)計(jì)

無(wú)人機(jī)飛行中所需要考慮的硬約束條件［4-5］有：最小飛行高度，最大水平轉(zhuǎn)角，禁飛區(qū)；軟約束有：航路長(zhǎng)度，飛行高度，飛行高度差。

常見(jiàn)的代價(jià)函數(shù)有幾個(gè)缺陷：

①可能存在大數(shù)吃掉小數(shù)的問(wèn)題；

②對(duì)于已知條件不充分或設(shè)計(jì)時(shí)間不充裕的情況下，權(quán)重k的取值較為困難。

為了克服上述缺陷，本文在設(shè)計(jì)代價(jià)函數(shù)時(shí)采用歸一化思想，用除法消去每個(gè)代價(jià)函數(shù)的單位，使其在理論上可以做加法；并將變化范圍控制在0到1之間，從而避免了對(duì)權(quán)重k的設(shè)計(jì)［6］。

為了全面地反應(yīng)無(wú)人機(jī)飛行中所需要考慮的硬約束與軟約束，給出如下定義的航路代價(jià)函數(shù)：

定義：代價(jià)函數(shù)

其中，Cost1為航路地形規(guī)避代價(jià)，Cost2為航路平滑代價(jià)，Cost3為航路安全代價(jià)，Cost4為航路高度代價(jià)，Cost5為航路長(zhǎng)度代價(jià)，Cost6為航路高度起伏代價(jià)。

其中N1為與地面發(fā)生碰撞的航路點(diǎn)的個(gè)數(shù)，p1為無(wú)人機(jī)與地形發(fā)生碰撞時(shí)的懲罰系數(shù)，N∑為航路點(diǎn)的總個(gè)數(shù)，zbline，m為通過(guò)B樣條曲線生成的第m個(gè)點(diǎn)的高度，zterrain，m（x，y）為zbline，m正下方對(duì)應(yīng)的地表的高度，m=1，2，3，…，N∑。發(fā)生碰撞的點(diǎn)越多，其值越大，并且只要一旦發(fā)生碰撞，其值就大于p1，否則為0。

其中N2為不平滑的點(diǎn)的個(gè)數(shù)，Pm為B樣條曲線生成的第m個(gè)點(diǎn)，p2為當(dāng)航路不平滑或經(jīng)過(guò)威脅區(qū)域時(shí)的懲罰系數(shù)。航路越不平滑，其值越大，與Cost1類似，只要航路不平滑，其值就大于p2。

其中N3為經(jīng)過(guò)威脅區(qū)域的點(diǎn)的個(gè)數(shù)，xm與ym分別為B樣條曲線生成的第m個(gè)點(diǎn)的x軸坐標(biāo)與y軸坐標(biāo)。經(jīng)過(guò)威脅區(qū)域的點(diǎn)越多，其值越大，與Cost2類似，一旦經(jīng)過(guò)威脅區(qū)域，其值就大于p2。

其中ΣHm為所有點(diǎn)的高度之和，Hmax為地形最高點(diǎn)的高度，通常情況下Hmax〉Σzm/N∑。航路高度越高，其值越大。

其中l(wèi)sd為起點(diǎn)到終點(diǎn)的直線距離，L∑為規(guī)劃所得航路的路程，zm為B樣條曲線生成的第m個(gè)點(diǎn)的z軸坐標(biāo)。航路長(zhǎng)度越長(zhǎng)，其值越大。

其中ΔH∑為相鄰兩點(diǎn)高度的差值，abs為求絕對(duì)值運(yùn)算。航路高度改變?cè)絼×遥渲翟酱蟆?/p>

建議p1≥3，p2≥2，使得Cost1∈［0］∪（3，∞），Cost2∈［0］∪（2，∞），Cost3∈［0］∪（2，∞）；對(duì)于Cost4，分子為整條航路的平均高度，其值必小于分母，即Cost4∈（0，1）；對(duì)于Cost5，由兩點(diǎn)之間線段最短可知，lsd/L∑∈（0，1），則Cost5∈（0，1）；對(duì)于Cost6，分子為航路的平均高度差，其值必小于分母，即Cost6∈（0，1）。因此，當(dāng)Cost1〉0時(shí)，Cost1將遠(yuǎn)遠(yuǎn)大于Cost4，Cost5，Cost6。Cost2及Cost3與Cost1類似。這樣就能體現(xiàn)代價(jià)函數(shù)對(duì)于硬約束和軟約束的不同重視程度。經(jīng)過(guò)歸一化處理消除了各個(gè)代價(jià)函數(shù)的單位，理論上可以執(zhí)行加法運(yùn)算，并且不用考慮k的取值。在此代價(jià)函數(shù)的指導(dǎo)下，航路會(huì)朝著安全、平滑、路程短、高度低和高度改變較小的方向進(jìn)化。

3 算法描述

3.1 種群初始化

第1部分種群在地圖中隨機(jī)生成，第2部分種群在遠(yuǎn)離威脅區(qū)域或地勢(shì)較低的區(qū)域選取。為了方便起見(jiàn)，本文過(guò)每個(gè)威脅的圓心做起點(diǎn)與終點(diǎn)聯(lián)線的垂線，與靠近地圖的上下邊緣處相交，得到的點(diǎn)作為第2部分種群，方法如下所示：

其中，pop為種群的數(shù)量，ypb（k）為經(jīng)過(guò)第k個(gè)威脅區(qū)域圓心的中垂線方程，xrk與yrk為第k個(gè)威脅區(qū)域的x坐標(biāo)與y坐標(biāo)；yup與ydown分別代表靠近地圖上下邊緣的邊界線。值得說(shuō)明的是，通常選擇cnum個(gè)控制點(diǎn)，cnum個(gè)數(shù)根據(jù)地圖的復(fù)雜程度來(lái)確定，加上起點(diǎn)與終點(diǎn)，總計(jì)cnum+2個(gè)控制點(diǎn)。本文采用3次B樣條曲線，總計(jì)生成cnum+1段航路，合并成一條完成的航路。通常cnum取值范圍在［2，4］之間，本文由于仿真規(guī)模不大，取cnum=2，再加上起點(diǎn)與終點(diǎn)共計(jì)4個(gè)控制點(diǎn)。此時(shí)得到的僅僅是x坐標(biāo)與y坐標(biāo)，為了以三維坐標(biāo)進(jìn)行編碼，還需要得到z坐標(biāo)，方法如下所示：

Control（z）=zterrain（Control（x），Control（y））+height（9）

由于本文不考慮無(wú)人機(jī)的起飛與降落階段，而zterrain（Control（x），Control（y））得到的是地表的高度，所以控制點(diǎn)的高度需要再加上一個(gè)適當(dāng)?shù)母叨戎?，即height，建議取值范圍在［0.1*Hmax，0.3*Hmax］之間。

3.2 進(jìn) 化

3.2.1 振 動(dòng)

在進(jìn)化開(kāi)始前，所有種群先進(jìn)行振動(dòng)。振動(dòng)頻率為fr，即每fr代振動(dòng)一次，每次振動(dòng)從第1個(gè)種群的第1個(gè)控制點(diǎn)開(kāi)始，到第2個(gè)種群的第1個(gè)控制點(diǎn)，至最后一個(gè)種群的第1個(gè)控制點(diǎn)。再回到第1個(gè)種群的第2個(gè)控制點(diǎn)開(kāi)始繼續(xù)振動(dòng)，到最后一個(gè)種群的最后一個(gè)控制點(diǎn)結(jié)束，描述如下：

其中rand∈［0，1］，i=1，2，3，…，pop+2*n，j=2，3，…，cnum+1，gen為fr的整數(shù)倍。

3.2.2 選 擇

為了使種群在后期依舊保持種群的多樣性，僅第1部分種群參與選擇，使用輪盤(pán)賭的方法。值得一提的是，由于本文的航路代價(jià)越小越好，所以每個(gè)種群以各自的代價(jià)函數(shù)的倒數(shù)參與輪盤(pán)賭的選擇。即：

其中，fitness（i）為第i個(gè)種群參與輪盤(pán)賭選擇時(shí)的參考值，i=1，2，3，…，pop，Cost（i）為第i個(gè)種群的航路代價(jià)。其Cost越小，說(shuō)明種群越優(yōu)秀，則fitness越大，通過(guò)輪盤(pán)賭脫穎而出的概率就越大。

3.2.3 交 叉

同樣，為了保持種群多樣性，僅第1部分種群參與交叉。本文使用單點(diǎn)交叉的方法，描述如下：

其中，u1=1，2，3，…，pop，u2=1，2，3，…，pop。值得一提的是，交叉過(guò)后需要重新排列控制點(diǎn)的順序，使第2個(gè)控制點(diǎn)靠近起點(diǎn)，第3個(gè)控制點(diǎn)靠近終點(diǎn)。

3.2.4 進(jìn) 化

所有種群，包括第1部分與第2部分的種群參與進(jìn)化。本文采用單點(diǎn)進(jìn)化，描述如下：

其中，i=1，2，3，…，pop+2*n。

3.3 B樣條曲線生成航路

3.3.1 B樣條曲線

本文采用三次B樣條曲線，其矩陣形式表達(dá)如下：

由B樣條曲線性質(zhì)可知，當(dāng)通過(guò)點(diǎn)P1作點(diǎn)P2的鏡像點(diǎn)P0時(shí)，以P0，P1，P2，P3為控制點(diǎn)的B樣條曲線的起點(diǎn)必然會(huì)與點(diǎn)P1重合。

3.3.2 生成航路

利用B樣條曲線的上述性質(zhì)，以P1與P4作為航路規(guī)劃的起點(diǎn)與終點(diǎn)，在地圖中通過(guò)隨機(jī)選擇控制點(diǎn)P2與P3，再加上鏡像點(diǎn)P0與P5，即可得到嚴(yán)格經(jīng)過(guò)起點(diǎn)與終點(diǎn)的無(wú)人機(jī)航路。再用遺傳算法選擇出更優(yōu)秀的控制點(diǎn)P2與P3，得到航路代價(jià)數(shù)更小的無(wú)人機(jī)航路，描述如下：

3.4 擇 優(yōu)

將得到的航路按式（3）～式（9）計(jì)算航路代價(jià)，記錄最好的航路，并將最差的種群刪除，按照式（10）在地圖中隨機(jī)選擇一組種群填補(bǔ)最差的種群，循環(huán)次數(shù)加1，繼續(xù)循環(huán)直至滿足循環(huán)條件。

3.5 輸出最優(yōu)航路

相對(duì)于傳統(tǒng)定步長(zhǎng)算法來(lái)說(shuō)，本文利用B樣條曲線生成整條航路，實(shí)際參與遺傳算法進(jìn)化的點(diǎn)只有2個(gè)，因此，計(jì)算量大大降低。相對(duì)于傳統(tǒng)遺傳算法來(lái)說(shuō)，在遺傳算法第fr次循環(huán)進(jìn)化開(kāi)始之前，進(jìn)行振動(dòng)，增加了種群的多樣性。大部分種群隨機(jī)生成并參與振動(dòng)、選擇、交叉與進(jìn)化，小部分種群在遠(yuǎn)離威脅的區(qū)域生成并只參與振動(dòng)與進(jìn)化，在保證種群收斂性的同時(shí)也增強(qiáng)了算法的全局搜索能力。以更加科學(xué)的代價(jià)函數(shù)為參考，指導(dǎo)種群進(jìn)化。因此，本文算法在實(shí)時(shí)性及全局搜索能力方面將具有一定優(yōu)勢(shì)。

3.6 重規(guī)劃

假設(shè)圖4中出現(xiàn)了新的威脅區(qū)域，并用雙層圓柱體來(lái)表示新威脅區(qū)域，由此得到圖5。本文假定當(dāng)無(wú)人機(jī)飛行到達(dá)新威脅區(qū)域外層圓柱體時(shí)，無(wú)人機(jī)偵測(cè)到新威脅區(qū)域，并開(kāi)始重規(guī)劃新的航路。為了縮短重規(guī)劃時(shí)間，盡量利用已規(guī)劃的航路。因此，以已規(guī)劃航路與新威脅區(qū)域外層圓柱體相交的兩個(gè)點(diǎn)分別作為起點(diǎn)與終點(diǎn)，對(duì)穿越新威脅區(qū)域的航路進(jìn)行重規(guī)劃，而未穿越新威脅區(qū)域的航路保持不變。由于重規(guī)劃的規(guī)模較小，B樣條曲線的Δt應(yīng)適當(dāng)增大。

4 算法流程

①環(huán)境建模與參數(shù)初始化；

②根據(jù)式（8）在地圖中選擇控制點(diǎn)，Controli（xj，yj，zj），使xj∈［0，mapx］，yj∈［0，mapy］，zj∈［0，mapz］；

③根據(jù)式（9）編碼；

④判斷是否滿足振動(dòng)條件，若滿足，則根據(jù)式（10）振動(dòng)；若不滿足則跳至第5步；

⑤第1部分種群參加群輪盤(pán)賭選擇，根據(jù)式（12）單點(diǎn)交叉；全體種群根據(jù)式（13）單點(diǎn)進(jìn)化；

⑦根據(jù)式（1）～式（7）計(jì)算無(wú)人機(jī)航路代價(jià)Costi；

⑧將代價(jià)最大Costimax的一組基因Controli（x，y，z）刪除，在地圖中根據(jù)式（8）重新隨機(jī)選擇控制點(diǎn)Controli（xrand，yrand，zrand）補(bǔ)充至種群；

⑨判斷是否迭代完成，若完成，跳至第10步；若未完成，跳至第4步；

圖1 算法流程圖

5 仿真分析

5.1 仿真環(huán)境

本文仿真采用 Window xp操作系統(tǒng)，matlab2008a作為仿真軟件，計(jì)算機(jī)配置為Intel（R）Core（TM）2 Duo P8600 2.39 GHz，2.87 GB內(nèi)存。忽略無(wú)人機(jī)的起飛與降落階段，即無(wú)人機(jī)只需從起點(diǎn)或起點(diǎn)正上方飛行至終點(diǎn)或終點(diǎn)正上方即可。

為了對(duì)比本文算法與傳統(tǒng)定步長(zhǎng)算法，以蟻群算法為例，在模擬地形中進(jìn)行仿真5.2，驗(yàn)證其實(shí)時(shí)性與全局搜索能力。為了進(jìn)一步貼近工程實(shí)踐與驗(yàn)證算法的魯棒性，仿真5.3在數(shù)字地形中對(duì)比了本文算法與振動(dòng)遺傳算法。仿真5.4同樣在數(shù)字地形中進(jìn)行重規(guī)劃仿真，驗(yàn)證本文算法的實(shí)時(shí)性能夠滿足重規(guī)劃的需求。本文中N∑=150，總計(jì)有3/Δt個(gè)點(diǎn)，即Δt=0.02，fr=2，pop=24。

5.2 精英蟻群與本文算法仿真對(duì)比

考慮到蟻群算法的空間開(kāi)銷與時(shí)間開(kāi)銷，本文只在模擬地形中將精英策略蟻群算法與本文算法進(jìn)行對(duì)比。數(shù)學(xué)函數(shù)如式（1）所示，其中，a=-1.5，b=1，c=-2，d=0.6，e=0.1，f=-1，g=-1，以黑色六邊形表示起點(diǎn)與終點(diǎn)，地形步長(zhǎng)為 0.5，mapx=25，mapy=25，mapz=15，Rn=2，n=1，2，3，起點(diǎn)坐標(biāo)為（2，2，8），終點(diǎn)坐標(biāo)為（21，22，5），威脅區(qū)域坐標(biāo)分別為（5，5），（11，11），（10，19），蟻群算法步長(zhǎng)為1，因?yàn)閜op=24，n=3，所以種群數(shù)量為30，算法步長(zhǎng)為1。值得一提的是，在模擬地形中Control（z）可以根據(jù)數(shù)學(xué)函數(shù)式（1）直接計(jì)算得到。數(shù)字地形中，以（Control（x），Control（y））為中心，臨近的4個(gè)點(diǎn)構(gòu)成正方形，以正方形4個(gè)頂點(diǎn)的高度的平均值作為Control（z）的值。

表1 精英策略蟻群算法部分參數(shù)

表2 本文算法部分參數(shù)

在模擬地形中運(yùn)行蟻群算法、本文算法1和本文算法2各50次。其運(yùn)行結(jié)果如圖2與圖3所示，對(duì)比結(jié)果如表3所示：

表3 蟻群算法與本文算法航路代價(jià)對(duì)比

圖2 蟻群算法運(yùn)行結(jié)果

圖3 本文算法運(yùn)行結(jié)果

其中，本文算法1中heihgt=2，本文算法2中heihgt=1.5。通過(guò)上述對(duì)比可以發(fā)現(xiàn)，本文算法得到的航路代價(jià)與蟻群算法得到的近似，但是本文算法的運(yùn)行時(shí)間遠(yuǎn)遠(yuǎn)短于蟻群算法，僅占蟻群算法用時(shí)10%不到，證明該算法有著良好的實(shí)時(shí)性。

5.3 本文算法與振動(dòng)遺傳算法仿真對(duì)比

為了更加貼近工程實(shí)踐和驗(yàn)證算法魯棒性，在數(shù)字地形中運(yùn)行振動(dòng)遺傳算法和本文算法各1 000次。其中，以紅色六邊形表示起點(diǎn)與終點(diǎn)，mapx=11 250，mapy=11250，mapz=1000，Rn=700，n=1，2，3，4。起點(diǎn)坐標(biāo)為（1097，9410，279），終點(diǎn)坐標(biāo)為（11220，1976，286），威脅區(qū)域坐標(biāo)分別為（2 312，8 500），（3 000，4 100），（6 424，6 424），（9 500，2 800），地形步長(zhǎng)約為90 m，仿真環(huán)境如下頁(yè)圖4所示，其對(duì)比結(jié)果如下頁(yè)表4所示。

圖4 數(shù)字地形

表4 振動(dòng)遺傳算法與本文算法航路代價(jià)對(duì)比

如表4所示，本文算法平均航路代價(jià)小于振動(dòng)遺傳算法的平均航路代價(jià)，減少了近40%的航路代價(jià)，證明本文算法的全局尋優(yōu)能力較振動(dòng)遺傳算法更強(qiáng)。

5.4 重規(guī)劃仿真

如圖5所示，在原有的威脅區(qū)域的基礎(chǔ)上，增加了3個(gè)新的威脅區(qū)域，每個(gè)新的威脅區(qū)域用雙層圓柱體來(lái)表示。里面的圓柱體為威脅的實(shí)際范圍，外面的圓柱體代表無(wú)人機(jī)偵測(cè)范圍。新威脅區(qū)域的內(nèi)層半徑為700，外層半徑為1 400，其坐標(biāo)分別為（5 000，8 000），（6 024，3 224），（9 400，4 800）。

圖5 重規(guī)劃仿真環(huán)境

圖6 重規(guī)劃仿真結(jié)果

在上述數(shù)字環(huán)境下運(yùn)行2 000次，有1 100次發(fā)生重規(guī)劃?？紤]到重規(guī)劃時(shí)只生成了一小段航路，因此在重規(guī)劃時(shí)N∑=30。其重規(guī)劃結(jié)果與初始規(guī)劃航路代價(jià)收斂曲線如圖6、圖7所示，實(shí)時(shí)性如表5所示。

表5 預(yù)規(guī)劃與重規(guī)劃耗時(shí)

圖7 航路代價(jià)收斂曲線

如圖7所示，無(wú)人機(jī)在偵測(cè)到新威脅區(qū)域前的航路避開(kāi)了所有的威脅區(qū)域，在偵測(cè)到新威脅區(qū)域后重規(guī)劃航路也避開(kāi)了新威脅區(qū)域。從表5中可以看到，本文算法速度快，預(yù)規(guī)劃耗時(shí)僅為個(gè)位數(shù)，重規(guī)劃耗時(shí)不到1 s，能夠在偵測(cè)到新威脅后的極短時(shí)間內(nèi)重規(guī)劃出一條航路避開(kāi)新的威脅區(qū)域。

6 結(jié) 論

本文針對(duì)常見(jiàn)的代價(jià)函數(shù)中權(quán)重難以確定的問(wèn)題與傳統(tǒng)定步長(zhǎng)算法時(shí)間成本大的問(wèn)題，分別設(shè)計(jì)了歸一化的代價(jià)函數(shù)與基于B樣條曲線與振動(dòng)遺傳算法的航路規(guī)劃算法，并改進(jìn)了進(jìn)化策略，增強(qiáng)了算法的魯棒性與時(shí)效性。在此基礎(chǔ)上通過(guò)仿真對(duì)比本文算法與精英策略的蟻群算法，其結(jié)果表明本文算法在航路代價(jià)近似的情況下，速度明顯優(yōu)于蟻群算法，其耗時(shí)僅占蟻群算法10%不到。本文算法相對(duì)于振動(dòng)遺傳算法航路代價(jià)優(yōu)化了近40%。并且在數(shù)字環(huán)境中進(jìn)一步驗(yàn)證了該算法的重規(guī)劃耗時(shí)不到1 s，能夠滿足重規(guī)劃的時(shí)間需求。

［1］Huo C L，Lai T Y，Sun T Y.The Preliminary Study on Multi-Swarm Sharing［J］.IEEE，2011：1770-1776.

［2］Huang H C，Tsai C C.Global Path Planning for Autonomous Robot Navigation Using Hybrid Metaheuristic［J］.SICE Annual Conference，2011：1338-1343.

［3］Pehlivanoglu Y V，Hacioglu A.Vibrational Genetic Algorithm Based Path［J］.IEEE，2007：573-578.

［4］馬培軍，毛云云，張洪濤，等.基于3DSAS的多約束多航跡協(xié)同規(guī)劃與搜索方法［J］.系統(tǒng)工程與電子技術(shù)，2011，33（4）：1527-1533.

［5］楚 瑞.基于蟻群算法的無(wú)人機(jī)航路規(guī)劃［D］.西安：西北工業(yè)大學(xué)碩士論文，2006.

［6］丁 吉，樊瓊劍，任 博.未知環(huán)境中的無(wú)人偵察機(jī)動(dòng)態(tài)航路規(guī)劃［J］.四川兵工學(xué)報(bào)，2012，33（5）：28-31.

［7］Roberge V，Tarbouchi M，Labonté G.Comparison of Parallel Genetic Algorithm and Particle Swarm Optimization for Real-Time UAV Path Planning［J］.IEEE Transactions on Industrial Informatics，2013，9（1）：132-141.

［8］Ermis M，F(xiàn)üsunlengin，Abdurrahman Hacioglu.Vibrational Genetic Algorithm（Vga）for Solving Continuous Covering Location Problems ［C］//ADVIS 2002，LNCS 2457，2002.

［9］Pehlivanoglu Y V，Baysal O，Hacioglu A.Path Planning for Autonomous UAV Via Vibrational Genetic Algorithm［J］. Aircraft Engineering and Aerospace Technology，2002，79（4）：352-359.

Research on UAV Path Planning Based on Vibrational Genetic Algorithm in 3D

XI Qing-biao1，2，LI Kang1，LIU Hui-xia1，2
（1.School of Automation，Northwestern Polytechnical University，Xi'an 710072，China；
2.No.365 Research Institute，Northwestern Polytechnical University，Xi'an 710075，China）

Concerning the weight of cost function has to change with the environment，a normalized cost function is designed with flight constraints in this paper，which could improve the robustness of the algorithm since there is no need to modify the cost function when the environment is changed.A high timeliness routing algorithm is proposed which is based on B-spline curve and Genetic Algorithm（GA）to reduce the time cost of traditional fixed step algorithms.First，the control points are searched by GA in the map.Then the whole path is produced by B-spline curve with control points.An appropriate vibrantion law is added in order to enhance the global search ability of GA so that the population still maintains a certain diversity in the evolution of the late.Simulation result shows that the method is much faster than Elite Ant Algorithm and the cost of flight route is obviously lower than that of Vibrational Genetic Algorithm.

normalized，route planning，B-spline，vibrational genetic algorithm

TJ630

A

1002-0640（2014）10-0030-06

2013-08-05

2013-10-09

國(guó)家自然科學(xué)基金資助項(xiàng)目（61074155）

席慶彪（1964- ），男，安徽合肥人，研究員，碩士生導(dǎo)師。研究方向：無(wú)人機(jī)導(dǎo)航、制導(dǎo)與控制，飛行控制與仿真技術(shù)等。