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

郝 震，張 健，蔡滿意

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

0 引言

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

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

1 航跡規(guī)劃各種約束分析

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

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

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

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

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

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

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

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

3 自適應遺傳算法

3.1 基本遺傳算法

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

3.2 遺傳算子的改進

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

1)排序選擇算子和最優(yōu)解保存算子。

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

2)多點交叉算子。

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

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

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

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

3.3 自適應遺傳算法

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

通過觀察種群的平均適應度favg和種群最優(yōu)適應度fmax的關系來判別算法是否收斂于最優(yōu)。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)實現(xiàn)根據(jù)染色體適應度大小來自適應調(diào)整其交叉概率和突變概率［8］，當算法陷于局部最優(yōu)時，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)。結合起始點和目標點的極坐標，則該條航跡的極坐標序列為

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

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

采用航跡偏角調(diào)整尺度Δψ0的倍數(shù)作為染色體編碼的基因位。若航跡染色體的第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 ]，基于這種航跡偏角的極坐標編碼方式，解決了最大航跡偏角、最小航跡步長、最大航跡點數(shù)3個約束。

4.2 航跡適應度函數(shù)

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

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

代價函數(shù)懲罰項:

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

航跡適應度函數(shù):

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

4.3 遺傳操作算子

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

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

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

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

4.4 仿真參數(shù)

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

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

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

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

4.5 仿真結果驗證

在Matlab 7.0集成環(huán)境下仿真結果見圖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中，五角星表示突防區(qū)域內(nèi)的威脅，以五角星為圓心的點線圓圈表示了各雷達的最大作用范圍，由于對探測威脅是用雷達發(fā)現(xiàn)概率Pdetection來處理，R1半徑越大，則Pdetection越小，并考慮到該區(qū)域周圍的飛行器撞地概率，因而航跡穿過于R1作用范圍的邊緣是可以接受的，也符合實際情況。在圖4中，實線表示地形高程，虛線表示各航跡點的高度。由仿真結果可以看出，飛行器較好地實現(xiàn)了TF/TA2。

5 結束語

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

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

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

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

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

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

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

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

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

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

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

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