朱代武，劉 豪，陳澤暉

（1.中國民用航空飛行學(xué)院圖書館，四川廣漢 618307；2.中國民用航空飛行學(xué)院空中交通管理學(xué)院，四川 廣漢 618307）

考慮到覆蓋率、數(shù)量、續(xù)航時間、障礙等諸多約束，無人機(jī)(UAV)的發(fā)展應(yīng)用需解決路徑規(guī)劃、最優(yōu)航跡規(guī)劃、編隊協(xié)同等相應(yīng)問題[2]，其中最為重要的是航路規(guī)劃問題。實現(xiàn)靈活和平滑的飛行航路規(guī)劃，能幫助無人機(jī)規(guī)避風(fēng)險、提高偵察和生存能力[3]。目前有學(xué)者提出相應(yīng)的航路規(guī)劃算法，如利用多層次分解、傳統(tǒng)GA、基于Voronoi 圖對UAV 進(jìn)行航路規(guī)劃等。但是已有算法因局限于特定場景的指定模型，無法實現(xiàn)UAV 多階段的整體航路規(guī)劃[4]。因此綜合UAV 協(xié)同、障礙和時間、巡航覆蓋率等約束，運(yùn)用基于改進(jìn)操作算子的MAGA 對航路進(jìn)行精細(xì)規(guī)劃，通過坐標(biāo)定義的航路點選擇和確定的飛行航跡，就能實現(xiàn)任意兩點間的直線飛行或者最大限度選擇最便捷的航路[5]。

1 MAGA無人機(jī)航路規(guī)模型建立

考慮到地理環(huán)境、威脅風(fēng)險及平臺運(yùn)動因子所產(chǎn)生的影響，分析UAV 的外部條件以及自身機(jī)動性能限制，建立UAV 飛行過程中的空間約束模型。基于該空間約束模型，以最優(yōu)化目標(biāo)函數(shù)的方式對航路進(jìn)行規(guī)劃，從而生成UAV 最優(yōu)化模型。

航路規(guī)劃目的是綜合考慮UAV 性能升限的限制，規(guī)避在巡航過程中的諸多風(fēng)險威脅到達(dá)指定點，在保證生存能力的同時提高其運(yùn)行效率。為實現(xiàn)上述的目標(biāo)，需對UAV 航路運(yùn)行進(jìn)行評價，在所用算法滿足約束條件的情況下，使迭代結(jié)果趨于最優(yōu)。

文中采用2D 空間模型，因UAV 任務(wù)剖面在巡航時段高度保持一致，且能夠比較直觀地反映其在同一高度平面的航路規(guī)劃問題，同時建立3D 立體巡航區(qū)作為避障參考。

文中建立直角坐標(biāo)系XOY，將指定航路劃分為M等分，得到R1(x1,y1)，R2(x2,y2)，…，Rm(xm，ym)共m個航路點。航路點的集合表示如下：

其中，S表示起始點，E表示結(jié)束點。

在給定數(shù)量為M的目標(biāo)集合中，有N架UAV從目標(biāo)R1出發(fā)，分別訪問剩余的M-1 個航段點，目標(biāo)函數(shù)為UAV 的總航程最短，此時定義0-1 變量，即：

為使UAV 在巡航過程中燃油消耗及威脅系數(shù)最低，從航路長度、耗油量、航路點受限程度、航路段是否跨越威脅區(qū)等方面進(jìn)行分析，對其代價函數(shù)的權(quán)重進(jìn)行調(diào)整，這里使用多Agent 系統(tǒng)進(jìn)行評估。每一個Agent 的目標(biāo)都是使航段點和UAV 最優(yōu)化，為此提出評估系統(tǒng)性能的評價函數(shù)：

其中，B(z)為該航路內(nèi)所有UAV 的懲罰代價之和；C(z)為各航段點的懲罰代價之和；α為歸一化系數(shù)，表示兩種代價的重要程度。

總代價懲罰是所有UAV 懲罰代價之和，即：

C(z)為各航段點的懲罰代價之和，表示為：

式中，Ca(z)為經(jīng)過i航點的UAV 為k時的代價懲罰，其表示為：

其中，kt是航段點k在t時刻的油耗代價，Cs為在航段點k時的平均油耗；δ為階躍系數(shù)，滿足上述式（2）、式（3）的0-1 變量關(guān)系。

同時，文中在基于MAGA 編碼方式及航路代價條件的基礎(chǔ)上建立合適的適應(yīng)度函數(shù)，提出包含航路長度f1、航路點是否在威脅區(qū)域罰函數(shù)f2、航段是否穿越威脅區(qū)罰函數(shù)f3的適應(yīng)度函數(shù)[5]，即適應(yīng)度函數(shù)F可描述為：

其中，罰函數(shù)f2、f3取1 時，航路點在威脅區(qū)域內(nèi)或者穿越威脅區(qū)域，否則取0；w1、w2、w3為相對應(yīng)的權(quán)重系數(shù)，也滿足上述式（2）、式（3）的0-1 變量關(guān)系之一，即：

2 MAGA操作算子改進(jìn)

MAGA 算法主要對算子包括如下操作：所涉參數(shù)的設(shè)計、原始種群大小的設(shè)定、適應(yīng)度函數(shù)的設(shè)置、遺傳迭代次數(shù)設(shè)置及參數(shù)約束的選取。其步驟為：

1）進(jìn)行編碼策略選取，將參數(shù)集合X和參數(shù)域轉(zhuǎn)換為位串結(jié)構(gòu)空間s；

2）對適應(yīng)度函數(shù)f(X)和適應(yīng)值進(jìn)行定義；

3）在遵循遺傳算法理論的基礎(chǔ)上，按照給定要求進(jìn)行篩選處理，主要從群體m的選擇、雜交、變異3個方面進(jìn)行考慮；

4）初始化處理形成群體P，并通過迭代處理使算子選取具有隨機(jī)性；

5）對群體中個體位串進(jìn)行解碼，隨后計算適應(yīng)值f(X)；

6）利用選擇功能使雜交和變異算子作用于種群，形成新一代種群；

7）對種群進(jìn)行評判。若滿足設(shè)定的標(biāo)準(zhǔn)，則進(jìn)行下一次迭代；若不滿足則停止迭代或者修改評價標(biāo)準(zhǔn)，其流程如圖1 所示。

圖1 MAGA算法基本流程圖

按照生物學(xué)仿真實驗特性及無人機(jī)巡航性能要求，文中采用依次置換交叉的方式，以確保目標(biāo)不被重復(fù)訪問或者出現(xiàn)數(shù)據(jù)丟失遺漏的情況。即在兩個父本上隨機(jī)選取染色體個數(shù)相同的基因序列進(jìn)行交換，其余位置的染色體依次與交換位置的染色體進(jìn)行比較；如果出現(xiàn)基因相同的情況，則按照出現(xiàn)的先后次序逐一排列，如表1 所示。

表1 交叉操作前基因位序表

隨機(jī)選取從位置6 到位置9 對父本染色體進(jìn)行交換，經(jīng)過交換后，兩個個體如表2 所示。

表2 交叉操作后基因位序表

其余位置的基因依次與交換后的基因相比，S1中基因1 和基因5 均出現(xiàn)重復(fù)。根據(jù)基因1 的前一個原始基因0，選擇基因2、3、6 中與原始基因距離最近的基因代替基因1，以完成一次交叉。

在使用置換交叉的基礎(chǔ)上，文中對操作算子進(jìn)行改進(jìn)，按照對應(yīng)的適應(yīng)度系數(shù)從大到小依次排列，并指定相應(yīng)的閾值S。若大于閾值S，則對該個體進(jìn)行復(fù)制，反之不予復(fù)制。

在研究過程中，擬選取較小的Pm對單獨片段基因進(jìn)行修改，以變異概率Pm選取兩個基因位；對交叉概率Pc也選擇兩個體的基因片段進(jìn)行修改。通過工程實踐可知，當(dāng)個體的適應(yīng)性接近種群平均適應(yīng)度時，其交叉概率Pc和變異概率Pm的值越低，優(yōu)良基因保留的可能性越大。因此文中基于Logistic 方程對交叉概率Pc和變異概率Pm進(jìn)行修改，實現(xiàn)兩者的自適應(yīng)，即：

其中，fmax代表種群中最大個體適應(yīng)度；favg代表種群所有個體的平均適應(yīng)度；f為要變異個體的適應(yīng)度[6]。

隨著f的變化需設(shè)置不同的變異概率以防止算法陷入局部最優(yōu)。若favg與f相等，迭代過程中就會出現(xiàn)局部最優(yōu)的情況。為防止局部最優(yōu)情況的發(fā)生，基于大數(shù)定律引入穩(wěn)態(tài)比例矩陣：

其中，diag(f)為m×m的對角矩陣，t為迭代次數(shù)。

如果在選擇之后變異，并且Mji是染色體xj到xi的概率，則對式（12）進(jìn)行改進(jìn)，得到：

其中，MT為M的轉(zhuǎn)置矩陣。如果p(t)達(dá)到穩(wěn)定態(tài)，則有pss=p(t-1)=p(t)，即：

3 仿真模擬

文中選取真實UAV 巡航任務(wù)案例，應(yīng)用實際坐標(biāo)和海拔數(shù)據(jù)，建立基于改進(jìn)操作算子的MAGA 航路規(guī)劃模型[7]。已知坐標(biāo)數(shù)據(jù)及海拔建立矩陣D=d(i，j)km，共計2 850 列、2 767 行。第一行為原點坐標(biāo)Z(0，0)，坐標(biāo)點之間等距設(shè)為100 m，即i處的數(shù)據(jù)為x=100×(i-1)，y=100×(j-1)[8]。選取8 個地方的中心點坐標(biāo)，設(shè)為A、B、C、D、E、F、G、H，其坐標(biāo)如表3 所示。

表3 選取地區(qū)中心點坐標(biāo)表

對表3 建立坐標(biāo)系，將ARCGIS 圖像導(dǎo)入Matlab中可得相應(yīng)的圖[9]，并對地區(qū)坐標(biāo)點進(jìn)行標(biāo)注，如圖2、圖3 所示。

圖2 UAV巡航區(qū)域圖

圖3 UAV巡航區(qū)域立體圖

UAV 巡航區(qū)域的上限高度為H0=2 km，即H0以下為主要目標(biāo)巡航區(qū)，滿足其對地巡航可視化范圍，且具有明顯不規(guī)則邊界劃分。UAV 從基站S出發(fā)，經(jīng)過高低不同的區(qū)域到達(dá)上述的8 個中心點，UAV飛行高度He為固定高度1 500 m，UAV 續(xù)航時間為5 h，平均飛行速度為60 km/h。基于MAGA 算法的思想，針對典型UAV 航路規(guī)劃任務(wù)，設(shè)原始種群為100，最大迭代次數(shù)為500[10]。

利用基于改進(jìn)操作算子的MAGA 算法對UAV在該區(qū)域內(nèi)的航路進(jìn)行最優(yōu)化處理。該算法在陷入局部極小解以及極大值時隨時終止循環(huán)，使得全局的整體結(jié)果最優(yōu)?？紤]到實際UAV 飛行性能以及越障情況，為使數(shù)據(jù)在模擬方面更具有真實性和操作性，這里取Pc1=0.9，Pc2=0.6，Pm1=0.1，Pm2=0.001[11]。規(guī)劃區(qū)域的航跡如圖4、圖5 所示。

圖4 UAV航路越障圖

在目標(biāo)區(qū)域內(nèi)，由H0決定的有效區(qū)呈現(xiàn)不規(guī)則地形，H0為巡航有效范圍內(nèi)的基準(zhǔn)海拔，且各區(qū)域內(nèi)按照MAGA 算法規(guī)劃設(shè)計出詳細(xì)的運(yùn)動軌跡，軌跡要求對8 個區(qū)域進(jìn)行覆蓋。文中將連線分為多段，由于模型中的E 和D 無法滿足巡航目標(biāo)區(qū)，因此UAV 不對兩點進(jìn)行巡航(圖4 及圖5 中E1、E2 和E3為E 地區(qū)的劃分子區(qū))。H 區(qū)域距離A 點較遠(yuǎn)，UAV巡航時間不能得到滿足，則不對H 區(qū)域進(jìn)行研究。同時按照可用面積比例，將目標(biāo)區(qū)域分解為300 個子區(qū)域(其中A 區(qū)域符號范圍為1～40，B 區(qū)域符號范圍為41～136，C 區(qū)域符號范圍為137～187，D 區(qū)域符號范圍為188～203，E 區(qū)域符號范圍為204～215，F(xiàn) 區(qū)域符號范圍為216～247，G 區(qū)域符號范圍為248～300)，結(jié)合QT4 算法，利用Matlab 進(jìn)行迭代分析[12]，其結(jié)果如表4、5 所示。

圖5 UAV航路避障圖

表4 UAV在目標(biāo)區(qū)域內(nèi)改進(jìn)MAGA路線編號

表5 UAV在目標(biāo)區(qū)域內(nèi)改進(jìn)MAGA路線編號

傳統(tǒng)MAGA 算法規(guī)劃的航路不能到達(dá)E 和D 區(qū)域，即在E 和D 區(qū)域內(nèi)無法正常巡航；而改進(jìn)MAGA能夠有效覆蓋E 和D 區(qū)域，使得能夠到達(dá)E 和D 中心點，保證無人機(jī)全階段任務(wù)順利完成。結(jié)果證明，經(jīng)過改進(jìn)操作算子的MAGA 相比于傳統(tǒng)算法迭代速度更快，航路更平滑，更有利于UAV航路任務(wù)的開展[13-14]。

4 結(jié)論

文中在傳統(tǒng)MAGA 的基礎(chǔ)上，通過對交叉概率Pc和變異概率Pm遺傳操作算子進(jìn)行改進(jìn)，并引入穩(wěn)態(tài)比例矩陣對UAV 航路進(jìn)行規(guī)劃研究[15-17]。通過對UAV 指定環(huán)境下模型構(gòu)建、UAV 航路規(guī)劃等問題進(jìn)行研究，提出基于改進(jìn)操作算子的MAGA 算法，解決了避障規(guī)劃、多機(jī)協(xié)同問題，最后通過仿真實例證明改進(jìn)MAGA 算法的有效性及魯棒性。