自適應遺傳算法在飛行器離線航跡規劃中的應用

郝 震，張 健，蔡滿意

(空軍工程大學工程學院，西安 710038)

0 引言

在飛行器低空突防的TF/TA2過程中，要根據任務區域的地形、地物和威脅以及飛行器性能等約束進行飛行航跡規劃，得到最優飛行航跡，提高飛機生存率和完成任務的概率［1］。

在范圍較大的任務區域，用動態規劃進行航跡規劃，信息處理量太大。由于地形曲面復雜，基于梯度法優化算法很難得到全局最優航跡。A*算法計算簡單容易實現，但啟發函數的選取限制了解的全局最優性。針對低空突防的特殊要求，將基本遺傳算法改進，提出一種自適應遺傳算法，使飛行航跡嚴格經過飛機的起始點和目標點，使威脅飛機的因素最小，有效地提高了飛機的任務生存概率。

1 航跡規劃各種約束分析

為了讓規劃出的航跡更符合實際，對各種約束條件進行分析，使航跡滿足這些約束條件。按航跡規劃約束來源的不同，將約束劃分為以下4類:

1)任務戰術約束，任務完成時間t，起始點S(xS，yS，zS)，目標點 T(xT，yT，zT)，攻擊方位角 ψ0，初始航向ψ0;

2)威脅約束，雷達發現概率Pdetection，飛行器撞地概率Pcollision，最小橫側向離地間隙Δdmin，最小離地高度Δhmin;

3)飛行器性能約束［2］，最小平飛速度Vmin，最大平飛速度Vmax，航程Lmax，最大飛行高度Hmax，水平最小轉彎半徑 Rmin，最大爬升角 θmax，最大航跡偏角 Δψmax，最大縱向曲率ρmax，最大過載nzmax;

4)其他約束，最小航跡步長lmin，最大航跡節點數Nmax。

2 規劃空間建模、地形預處理以及威脅建模

在規劃空間建模問題中，為研究方便且不失一般性，航跡規劃算法仿真驗證時，模擬生成一塊數字地形，以代替真實數字地圖，作為算法驗證的環境。其中用指數函數模擬算法模擬山峰地形，用正余弦函數模擬算法模擬山脈地形，用隨機模擬算法模擬隨機地形，最后生成綜合模擬地形［3］;對于生成的數字地形預處理，利用二維三次卷積插值算法對數字地形插值平滑［4］;在威脅建模方面，考慮了低空突防中可能遭遇的地形威脅和雷達探測威脅，并把孤立山峰當作威脅來處理［5］。

將飛機的最小離地高度、最小橫側向離地間隙、坡度限制、最大縱向曲率和威脅這些約束條件融入到數字地形預處理中，生成了安全飛行曲面［6］，在安全曲面上進行二維航跡規劃，縮減了規劃的維數，降低了問題的復雜度。

3 自適應遺傳算法

3.1 基本遺傳算法

基本遺傳算法已經得到了廣泛的應用，但有兩個嚴重的缺點:容易早熟收斂和進化后期搜索效率較低。基本遺傳算子采用適應度比例選擇、單點交叉和單點變異方法進行遺傳操作。由于選擇及交叉算子的作用，使得一些優秀的基因片段過早丟失，限制了搜索范圍，造成了算法的早熟收斂。

3.2 遺傳算子的改進

為了克服這些缺點，對基本遺傳操作進行改進，提出了新的選擇、交叉和變異算子。

1)排序選擇算子和最優解保存算子。

排序選擇算子是首先根據個體的適應度大小進行排序，然后基于排序號進行選擇。最優解保存算子的思想是把群體中適應度值最優的解不進行配對交叉，而直接復制到下一代中。其優點是:進化過程中某一代的最優解可以不被交叉和變異操作所破壞，并總能收斂至最(次)優解。

2)多點交叉算子。

采用兩點交叉和單點交叉相結合的方式。通過增加交叉方式，增強算法的全局搜索能力，防止陷入局部最優。兩點交叉設置兩個交叉點，將兩個交叉點之間的同組基因進行基因的互換。因而當染色體長為n時，則可能有(n－2)(n－3)種交叉點的設置。

3)高斯變異算子［7］。

采用高斯算子變異方式，讓變異與適應度緊密相聯，防止變異對適應度較優的個體的損傷，按變異率選擇某個體(這里選定k染色體)按下式變異:

式中:gen′(i)，gen(i)分別為新生代和父代個體的第i個基因;fmax、fk分別為本代個體的最優適應度和第k個個體的適應度。γi為均值為0、方差為1的高斯隨機變量。當gen(i)超出基因位數值范圍時，則重新產生γi變異，直到滿足要求為止。

3.3 自適應遺傳算法

在基本遺傳算法的運行過程中，選取固定的交叉概率和變異概率控制參數易產生早熟現象，陷入局部極值，但是選擇較大的交叉和變異概率就會成為隨機搜索，選擇較小的交叉和變異概率又不容易跳出局部極值點。可以通過協調交叉概率Pc和變異概率Pm達到使算法收斂于全局最優和抑制早熟。各染色體差異越小，則給定的交叉和變異概率愈大，這樣在群體中的各個體過分趨于一致時，會使交叉和變異的可能性增加，從而提高群體的多樣性，增強算法的搜索能力;而在群體多樣性已經很強時，則減少交叉和變異概率，以免破壞優良個體。但是增大交叉概率Pc和變異概率Pm的值，將增大算法的運行時間。使用中等大小的交叉概率Pc(0.5～1.0)和小的變異概率 Pm(0.01～0.15)，根據適應度值的大小，自適應改變交叉和變異概率的大小來達到全局優化和運算時間折中的目的。

通過觀察種群的平均適應度favg和種群最優適應度fmax的關系來判別算法是否收斂于最優。Pc和Pm值的大小依賴于favg－fmax的變化。當整個種群趨于收斂時，即favg－fmax變小時，增大Pc和Pm;反之，減小Pc和Pm。因此構造Pc和Pm表達式為

式中:f′代表要交叉的兩個個體中較大的適應度值;f代表要變異的個體的適應度值;0≤k1≤1;0≤k2≤1;0≤k3≤1;0≤k4≤1。

自適應遺傳算法通過式(2)、式(3)實現根據染色體適應度大小來自適應調整其交叉概率和突變概率［8］，當算法陷于局部最優時，favg－ fmax將減小，由表達式可知，Pc和Pm增大，增大了搜索范圍;當解空間過于分散時，favg－fmax增大，而Pc和Pm值減小，從而縮小搜索范圍。對于 k2和 k4，由于此時 f′≥favg或 f≥favg，即個體適應度大于平均適應度，說明個體特性差，增大Pc和Pm，使差的個體破壞的可能性增大，k2和k4的值就大一些。

4 自適應遺傳算法仿真

4.1 航跡極坐標編碼方式

航跡極坐標編碼方式［9－10］是利用航跡點極坐標序列來表示航跡。如圖1所示，S、T分別為起始點和目標點。(1，2，…，N －1)分別為航跡點序號，與 S、T 構成N個航跡段，航跡點(1，2，…，N－1)的極徑依次為1ρ0，2ρ0，3ρ0，…，(N －1)ρ0。其中，ρ0為航跡點 1 所在圓弧的半徑，且 ρ0=ρT/N。

圖1 航跡偏角的極坐標編碼方式Fig.1 Flight path polar coordinate coding mode

通過以上處理，只需對航跡點的極角編碼即可，若航跡點編碼為(θ1，θ2，…，θN－1)。結合起始點和目標點的極坐標，則該條航跡的極坐標序列為

由于只需對極角進行編碼，大大減少了航跡規劃的時間，提高了效率。

利用直角坐標和極坐標的關系，將式(4)的航跡點極坐標序列解碼轉換到規劃空間的直角坐標系中，就得到了直角坐標系下的航跡點坐標。

采用航跡偏角調整尺度Δψ0的倍數作為染色體編碼的基因位。若航跡染色體的第i個基因值為gi，則第 i個航跡段［i－1，i］偏離第 i－1個航跡段［i－2，i－1］的航跡偏角 Δψi=gi·Δψ0，其中Δψ0、Δψi、Δψmax的含義如圖 3 所示。若 Δψmax/Δψ0=M，則航跡染色體各基因位的取值范圍為 gi∈[－M，…，－2，－1，0，1，2，…，M ]，基于這種航跡偏角的極坐標編碼方式，解決了最大航跡偏角、最小航跡步長、最大航跡點數3個約束。

4.2 航跡適應度函數

若一條航跡由染色體X表示，代價函數為

其中:優化項 fL(X)、fH(X)、fPd(X)、fPc(X)分別表示航跡長度代價、航跡高度代價、雷達發現概率代價和飛行器撞地概率代價;wL、wH、wPd、wPc為對應的各航跡子代價在航跡總代價中所占的權重，且滿足wL+wH+wPd+wPc=1。用層次分析法［11］對權重進行分配，這里令wL=0.0582，wH=0.1052，wPd=0.2603，wPc=0.5762。

代價函數懲罰項:

這里令:ω1=1000，ω2=10000，ω3=100000，使那些違背無人機性能約束的航跡個體的代價值非常大，從而在進化過程中被淘汰。

航跡適應度函數:

其中:f(X)為航路染色體X的代價。進而問題由代價最小化轉化為航跡適應度最大化。

4.3 遺傳操作算子

1)選擇算子。將當代適應度最大的10個染色體復制兩份，一份不經過交叉和變異直接復制到下一代中，另一份取代由于適應度最小而被淘汰的10個染色體，將中間的染色體復制一份產生下一代，直到被進化產生的更優個體所取代為止。

2)交叉算子。采用兩點交叉和單點交叉相結合的交叉算子。

3)變異算子。在航跡染色體的世代進化時，采取在［－M，M］內進行實值高斯變異。

4)對于算法參數，結合仿真，對自適應交叉概率和變異概率進行改進:

4.4 仿真參數

遺傳算法的參數:初始種群數目100;進化代數300;自適應交叉概率Pc1=0.9，Pc2=0.6;自適應變異概率 Pm1=0.01，Pm2=0.001。

雷達參數有R1位置(25，50)，作用半徑12;R2位置(45，25)，作用半徑 12;R3位置(60，55)，作用半徑15;R4位置(75，75)，作用半徑 10。

任務參數:起始點S(10，10);目標點T(90，90)。

進入方位角+45°(目標左側進入)，裕度5°。

4.5 仿真結果驗證

在Matlab 7.0集成環境下仿真結果見圖2～圖4。

圖2 三維航跡曲線Fig.2 Three-dimensional flight path curve

圖3 水平航跡曲線Fig.3 Horizontal flight path curve

圖4 縱向航跡曲線Fig.4 Longitudinal flight path curve

在圖2中，曲線表示生成的飛行器三維航跡。在圖3中，五角星表示突防區域內的威脅，以五角星為圓心的點線圓圈表示了各雷達的最大作用范圍，由于對探測威脅是用雷達發現概率Pdetection來處理，R1半徑越大，則Pdetection越小，并考慮到該區域周圍的飛行器撞地概率，因而航跡穿過于R1作用范圍的邊緣是可以接受的，也符合實際情況。在圖4中，實線表示地形高程，虛線表示各航跡點的高度。由仿真結果可以看出，飛行器較好地實現了TF/TA2。

5 結束語

針對飛行器航跡規劃多約束三維規劃問題，生成安全飛行曲面和采用極坐標編碼方式，將復雜的三維規劃問題轉化為一維問題，部分約束融入到安全飛行曲面和極坐標編碼方式中，減少了規劃時間。為避免局部最優，采用自適應交叉和變異概率，提高了遺傳算法的全局尋優能力，使規劃出的最(次)優航跡更加穩定，得到了較滿意的實際效果。

［1］閔昌萬，袁建平.軍用飛行器航跡規劃綜述［J］.飛行力學，1998，16(4):14-18.

［2］吳強，曹義華，金長江.最小安全飛行高度的計算［J］.戰術導彈技術，2003(2):21-24.

［3］李棟，曹義華，馮婷.基于地形特征的簡易地形模擬算法［J］.航空計算技術，2005，35(2):32-35.

［4］孫向春.直升機飛行航跡規劃與控制跟蹤技術研究［D］.北京:北京航空航天大學，2004.

［5］胡志忠，徐克虎，沈春林.低空突防用數字地圖信息的融合處理［J］.南京航空航天大學學報，2000，32(4):434-438.

［6］唐強，王建元，朱志強.基于粒子群優化的三維突防航跡規劃仿真研究［J］.系統仿真學報，2004，16(9):2033-2036.

［7］范洪達，馬向玲，葉文.飛機低空突防航路規劃技術［M］.北京:國防工業出版社，2007.

［8］王小平，曹立明.遺傳算法理論應用與軟件實現［M］.西安:西安交通大學出版社，2002.

［9］李娜，張海.基于遺傳算法的軍用飛行器航跡規劃［J］.戰術導彈控制技術，2004(3):86-94.

［10］馬云紅，周德云.基于遺傳算法的無人機航路規劃［J］.電光與控制，2005，12(5):24-27.

［11］張紅，盧廣山，朱榮剛.無人作戰飛機任務系統技術研究［J］.電光與控制，2006，13(1):55-59.