劉家鵬，張雪松

(中國電子科學(xué)研究院,北京 100041)

0 引 言

信息時(shí)代戰(zhàn)爭中，依次關(guān)注制信息權(quán)、制天權(quán)、制空權(quán)、制海權(quán)。制空權(quán)也成為戰(zhàn)斗中爭奪的重要內(nèi)容，沒有制空權(quán)，就注定要失敗[1]。在制空權(quán)的爭奪中，決定戰(zhàn)局的不僅僅是攻擊利器，更重要的是能夠及時(shí)發(fā)現(xiàn)敵人并采取行動(dòng)。這催生了如預(yù)警機(jī)等具有預(yù)警探測和指揮控制功能的特種飛機(jī)?，F(xiàn)代信息化條件下的戰(zhàn)爭核心是及時(shí)準(zhǔn)確的獲取各種情報(bào)。而在空戰(zhàn)中，特別是對于地面預(yù)警探測系統(tǒng)難以企及的遠(yuǎn)程作戰(zhàn)中，特種飛機(jī)將成為戰(zhàn)場態(tài)勢感知的主要信息源[2]。

特種飛機(jī)的飛行航線直接影響機(jī)載傳感器的工作效果。在特種飛機(jī)航線規(guī)劃的同時(shí)，需要考慮多種因素。不僅需要考慮云層、山巒等自然因素，還需要考慮雷達(dá)探測效果、通信覆蓋率、無源偵察效果等情況。特種飛機(jī)使用中主要面臨對各傳感器規(guī)劃不足，在航線規(guī)劃中沒有針對雷達(dá)、通信、無源偵察效果的考慮。

近些年來，主要的航線規(guī)劃方法主要有蟻群算法[3]、Voronoi圖法[4]、啟發(fā)式A*算法[5]、粒子群算法[6]、遺傳算法等。蟻群算法收斂速度慢，計(jì)算時(shí)間長，易于過早陷入局部最優(yōu)；Voronoi圖法中曲率約束的常微分方程求解過程很復(fù)雜，不易工程實(shí)現(xiàn)；A*算法要收斂到最優(yōu)解需要很長的時(shí)間和較大的內(nèi)存；粒子群算法具有搜索空間有限，但容易陷入局部最優(yōu)。而自適應(yīng)遺傳算法能夠自適應(yīng)的修改遺傳變異參數(shù)，全局搜索效果和局部搜索效果好，本文采用自適應(yīng)遺傳算法。

1 遺傳算法及其應(yīng)用情況

遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用方法，它不依賴于問題的具體領(lǐng)域，對問題的種類有很強(qiáng)的魯棒性，所以遺傳算法已有廣泛的應(yīng)用：函數(shù)優(yōu)化、組合優(yōu)化、生產(chǎn)調(diào)度問題、自動(dòng)控制、圖像處理和機(jī)器人學(xué)等[7]。本文將遺傳算法應(yīng)用于航線規(guī)劃的研究。

遺傳算法是一種借鑒生物界自然選擇和自然遺傳機(jī)制的全局搜索算法。它與傳統(tǒng)的算法不同，大多數(shù)古典的優(yōu)化算法是基于單一度量函數(shù)的梯度或較高次統(tǒng)計(jì)，以產(chǎn)生一個(gè)確定性的實(shí)驗(yàn)解序列。而遺傳算法是一種全局搜索算法，它有效地解決了大空間搜索及全局優(yōu)化。它不依賴于梯度信息，而是通過模擬自然進(jìn)化過程來搜索最優(yōu)解。其中，選擇、交叉和變異構(gòu)成了遺傳算法的基本操作；參數(shù)編碼、初始群體的設(shè)定、適應(yīng)度函數(shù)的設(shè)計(jì)、遺傳操作設(shè)計(jì)、控制參數(shù)這5個(gè)要素組成了遺傳算法的核心內(nèi)容。

2 航線規(guī)劃問題建模

航線規(guī)劃必須對飛行區(qū)域的環(huán)境信息和自身傳感器的使用限制信息進(jìn)行精確地了解。因此，合理、有效地針對環(huán)境威脅、機(jī)載傳感器進(jìn)行建模是航線規(guī)劃成功的關(guān)鍵。

特種飛機(jī)在執(zhí)行任務(wù)的過程中，其飛行的航線直接影響任務(wù)完成情況、自身安全、探測目標(biāo)發(fā)現(xiàn)概率等。在航線規(guī)劃過程中，需要考慮自身安全和傳感器的使用，使其在保證安全的前提下，使特種飛機(jī)的探測能力最大化，各傳感器充分發(fā)揮最大效能。

第一類問題，安全系數(shù)。

在航線規(guī)劃所需考慮的諸多因素中，自身安全最為重要。首先特種飛機(jī)在使用時(shí)，飛行在我方控制空域，在整個(gè)飛行探測過程中與敵方的戰(zhàn)斗機(jī)、防空區(qū)保持距離，同時(shí)與敵我分界線保持距離。所以特種飛機(jī)需要避開威脅空間主要包括自然威脅，包括山巒、云雨層、雷區(qū)等。從公開發(fā)表的文獻(xiàn)[8]中可知，將各種威脅模型簡化為具有一定規(guī)則的幾何形狀組合，有利于減少計(jì)算復(fù)雜度。

對自然威脅的建模分為兩種情況，一是威脅區(qū)域，二是禁飛區(qū),如圖1、2所示。

圖1 威脅區(qū)域 圖2 禁飛區(qū)

威脅區(qū)域一般為山脈。山脈的威脅程度與距離有關(guān)，距離越近威脅程度越大。為計(jì)算航線段的威脅程度，引入Eij表示連接航線點(diǎn)i和j的航線片段，Lij表示航線片段Eij的長度。特種飛機(jī)所受到的威脅程度與航線在威脅區(qū)域的長短及與威脅中心的距離有關(guān)，

式中，(x,y)為威脅空間的中心點(diǎn)；(xk,yk)為進(jìn)入威脅區(qū)域的點(diǎn)；N為進(jìn)入威脅區(qū)域點(diǎn)的個(gè)數(shù)；a為系數(shù)。

而對于禁飛區(qū)，則是針對云層等惡劣天氣區(qū)進(jìn)行建模?？烧J(rèn)為特種飛機(jī)在天氣區(qū)內(nèi)部所受到的威脅程度是相同的，即天氣區(qū)對無人機(jī)的威脅服從均勻分布，因此采用均勻分布模型進(jìn)行建模，其概率密度函數(shù)為

式中，Ji為禁飛區(qū)i的威脅程度；(a,b)、(c,d)為禁飛區(qū)對角線上的的兩個(gè)頂點(diǎn)。

第二類問題，任務(wù)完成率。

優(yōu)先級模型，特種飛機(jī)在航線規(guī)劃過程中需要考慮多傳感器的使用情況，實(shí)際是一個(gè)多目標(biāo)優(yōu)化問題。所以對于不同傳感器模型，根據(jù)其重要程度對權(quán)重進(jìn)行設(shè)定。首先特種飛機(jī)的安全系數(shù)最為重要，設(shè)為1級。

特種飛機(jī)最主要的功能是雷達(dá)探測，所以將雷達(dá)探測最大化，將其設(shè)計(jì)為2級。雷達(dá)有多種盲區(qū)，包括近距機(jī)翼遮擋盲區(qū)，固定角度盲區(qū)，頂空和機(jī)下盲區(qū)。考慮到特種飛機(jī)的安全、近距機(jī)翼遮擋盲區(qū)以，及頂空和機(jī)下問題，飛機(jī)航線規(guī)劃在距離上需要距探測區(qū)域保持一定距離。由于某些特種飛機(jī)有一定角度的盲區(qū)，假設(shè)飛機(jī)機(jī)尾有盲區(qū)，所以最優(yōu)航線側(cè)向飛過探測區(qū)域，保證探測效果，而且需要提前進(jìn)入探測區(qū)域一側(cè)來盡可能減少機(jī)尾盲區(qū)的影響。航線規(guī)劃同時(shí)考慮到這些盲區(qū)，使雷達(dá)發(fā)揮最大效果。

然后將通信設(shè)為3級，通信設(shè)備可能在敵方干擾或山脈遮擋無法與基地或部隊(duì)實(shí)時(shí)聯(lián)系。只要在任務(wù)過程中大部分時(shí)間能夠與我方聯(lián)系，某些短暫時(shí)刻不能達(dá)到實(shí)時(shí)通信，也可以完成任務(wù)，所以將其設(shè)為3級。最后考慮無源探測，探測敵方雷達(dá)位置，開機(jī)時(shí)長等，對任務(wù)影響最小，設(shè)為4級。

通信和無源偵察盲區(qū)會(huì)影響通信設(shè)備和無源偵察傳感器的使用效果，降低任務(wù)完成率。其模型與自然威脅模型類似，采用圓形禁飛區(qū)域或方形禁飛區(qū)模型。這里的圓形禁飛區(qū)域模型與自然威脅區(qū)域不同，考慮通信設(shè)備和無源偵察設(shè)備在盲區(qū)中使用會(huì)受到影響，但與距離無關(guān)，所以采用禁飛區(qū)對無人機(jī)威脅服從均勻分布，概率分布為

對各個(gè)傳感器的威脅程度進(jìn)行歸一化處理，對不同的威脅區(qū)域針對其重要程度設(shè)置不同的權(quán)重wi。總的懲罰函數(shù)為

wi根據(jù)優(yōu)先級模型設(shè)定，將自然威脅w設(shè)為20，雷達(dá)探測w設(shè)為15，通信和無源偵察盲區(qū)w設(shè)為10。

3 算法改進(jìn)描述

3.1 航線染色體編碼

每一條航線由100個(gè)點(diǎn)組成，每個(gè)點(diǎn)的橫坐標(biāo)均勻分布，縱坐標(biāo)采用二進(jìn)制編碼，隨機(jī)生成的種群序列。這樣的坐標(biāo)實(shí)現(xiàn)方法基于兩點(diǎn)考慮：(1)將問題轉(zhuǎn)化為單值一維編碼；(2)如果將橫縱坐標(biāo)都進(jìn)行隨機(jī)初始的話，每個(gè)點(diǎn)都有可能出現(xiàn)在坐標(biāo)的任意位置，這樣航線連續(xù)兩點(diǎn)間距離會(huì)過大，不符合實(shí)際航線情況，同時(shí)也會(huì)造成搜索空間爆炸問題。

在此基礎(chǔ)上再進(jìn)行航線再編碼，因?yàn)殡S機(jī)編碼會(huì)產(chǎn)生初始航線起伏過大的問題，這樣需要很多代的遺傳變異才能生成較好的航線。所以需要對航線進(jìn)行再編碼，本文采用隨機(jī)生成[-1,1]內(nèi)隨機(jī)數(shù)，然后從原點(diǎn)開始航線，每一點(diǎn)都在前一點(diǎn)的基礎(chǔ)上隨機(jī)生成。并在此基礎(chǔ)上對每條航線進(jìn)行平滑處理，以減少航線的振蕩。這樣將航線處理得更加平緩，同時(shí)更貼近真實(shí)航線，算法的效果也明顯改進(jìn)。

3.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)以航線的飛行距離為基礎(chǔ)，飛行距離決定飛機(jī)油耗等飛行成本，飛機(jī)在探測區(qū)域留空時(shí)間，所以總體選取飛行總距離小的航線。在此基礎(chǔ)上增加懲罰因子，用與考慮威脅空間和各分系統(tǒng)的使用狀況。

式中,N為航線中點(diǎn)的個(gè)數(shù)；n為航線進(jìn)入威脅空間的總個(gè)數(shù)；wi為威脅空間i的權(quán)值；Ji為威脅空間i的威脅程度。

3.3 選擇策略

選擇策略為最小化問題，所以選擇的原則是以大概率選擇適應(yīng)度函數(shù)值低的個(gè)體，以小概率選擇適應(yīng)度函數(shù)值大的個(gè)體，從而體現(xiàn)生物學(xué)上優(yōu)勝劣汰的思想。

將所有航線代入適應(yīng)度函數(shù)，得到適應(yīng)度值排名，采用隨機(jī)遍歷抽樣，適應(yīng)度值小的子代以大概率遺傳。

3.4 交叉算子和變異算子的自適應(yīng)改進(jìn)

為了克服傳統(tǒng)遺傳算法早熟問題和局部搜索能力差的問題，采用自適應(yīng)技術(shù)。自適應(yīng)遺傳算法在種群進(jìn)化初期，選取較大的交叉概率和變異概率，增加種群多樣性，確保種群在大范圍內(nèi)搜索，增強(qiáng)全局搜索能力，避免早熟。在種群進(jìn)化后期，接近最優(yōu)解時(shí)，選取較小的交叉概率和變異概率，使種群在局部范圍內(nèi)進(jìn)行搜索，增加局部搜索能力，同時(shí)增加收斂速度。

交叉算子采用多點(diǎn)交叉和單點(diǎn)交叉并用，由于多點(diǎn)交叉有利與種群多樣化，但不利于最后算法的收斂。本文采用自適應(yīng)技術(shù)，即在前50次進(jìn)化的時(shí)候采用多點(diǎn)交叉，增加種群多樣化，在后450次進(jìn)化采用單點(diǎn)交叉，有利于算法快速收斂。改進(jìn)后算法流程圖如圖3所示。

圖3 改進(jìn)算法的流程圖

3.5 航線平滑處理

針對算法得出的最優(yōu)航線，考慮飛機(jī)飛行轉(zhuǎn)彎半徑的限制進(jìn)行平滑處理，航跡飛行轉(zhuǎn)彎角度符合飛機(jī)特性，對轉(zhuǎn)彎角度偏小的部分航線進(jìn)行再處理，然后再針對整個(gè)航線進(jìn)行平滑處理，保證航線能夠正常飛行。

4 實(shí)驗(yàn)與分析

實(shí)驗(yàn)在配置為Intel Core i5 3.2 GHz處理器、4 GB RAM臺(tái)式機(jī)上進(jìn)行仿真，仿真環(huán)境為windows XP系統(tǒng)，Matlab 2010a平臺(tái)。畫出一個(gè)橫坐標(biāo)為[0,10]，縱坐標(biāo)為[0，10]的坐標(biāo)系，飛機(jī)從(0，6)點(diǎn)出發(fā)。在坐標(biāo)系中畫出數(shù)個(gè)威脅空間、敵我分界線以及探測空間。如圖中小圈是無源偵察盲區(qū)，大圈是高山威脅，藍(lán)色的方框是通信盲區(qū)。這三個(gè)區(qū)域都影響任務(wù)的正常執(zhí)行，飛機(jī)不能飛入這些區(qū)域。帶方塊的直線為敵我分界線，節(jié)點(diǎn)為圓圈的方框?yàn)樘綔y區(qū)域。

仿真結(jié)果如圖4～圖11所示。

圖4 初始航線 圖5 進(jìn)化150代的航線 圖6 算法效果圖(終態(tài))

圖7 算法效果圖(經(jīng)過平滑后的航線) 圖8 算法解的變化 圖9 適應(yīng)度值的變化與解的變化

圖10 傳統(tǒng)遺傳算法初始航線 圖11 傳統(tǒng)最終航線

算法的個(gè)體數(shù)目N=50，最大遺傳代數(shù)MAXGEN=500，變量個(gè)數(shù)(點(diǎn)的個(gè)數(shù))NVAR=100，每個(gè)變量的二進(jìn)制編碼位數(shù)PRECI=20。每個(gè)圖表示本次進(jìn)化最優(yōu)解的航線，即最短航路所對應(yīng)的航線。

顯示在進(jìn)化初期(gen<50)，算法保持較大的變異概率Pm=0.01和較大的交叉概率Pc=0.7，選擇多點(diǎn)交叉方式，航線進(jìn)化時(shí)變化很大，有利于種群多樣化。圖8中所示在前50代的進(jìn)化中，最優(yōu)解的變化幅度很大，而且小于種群均值的變化，說明種群航線多樣，有利于全局搜索適宜航線。進(jìn)化后期采用單點(diǎn)交叉，和較小的變異概率Pm=0.000 35和較小的交叉概率Pc=0.5，有利與局部搜索，最優(yōu)解與均值幾乎重疊，在進(jìn)化的過程中逐步優(yōu)化航線。

圖9中表示適應(yīng)度值變化和解的均值變化，在前100代左右的進(jìn)化中，二者相差很大，這是懲罰函數(shù)在起作用。種群在進(jìn)化過程中，會(huì)有一些航線進(jìn)入威脅區(qū)域，通過懲罰機(jī)制增大其適應(yīng)度值，較小適應(yīng)度值的種群有更大的概率保留下來。最終選擇出不經(jīng)過威脅區(qū)域而且有利于探測的的航線，達(dá)到我們對航線的要求。

圖10、11標(biāo)識(shí)傳統(tǒng)遺傳算法生成的初始航線和計(jì)算的最終航線，初始航線震蕩幅度特別大，計(jì)算出的最優(yōu)航線仍然有很大震蕩，并會(huì)出現(xiàn)穿過威脅區(qū)域的情況，對比說明改進(jìn)算法有一定優(yōu)勢。

5 結(jié) 語

針對特種飛機(jī)在預(yù)警探測過程中存在的自然威脅等飛行安全問題，探測區(qū)域覆蓋率問題，機(jī)上設(shè)備使用限制等實(shí)際問題，提出了一種改進(jìn)的自適應(yīng)遺傳算法。算法通過對初始種群編碼的改進(jìn)，以及交叉概率和變異概率的自適應(yīng)計(jì)算。針對實(shí)際問題能夠快速計(jì)算出特種飛機(jī)航線，并能有效的解決的傳統(tǒng)遺傳算法的早熟現(xiàn)象，不易收斂于局部最優(yōu)解。

仿真結(jié)果表明，采用自適應(yīng)遺傳算法進(jìn)行航線規(guī)劃合理可行，能夠在大范圍內(nèi)進(jìn)行航線規(guī)劃計(jì)算。改進(jìn)的遺傳算法不易收斂于局部最優(yōu)，這在計(jì)算全局最優(yōu)航線時(shí)效果明顯。算法復(fù)雜度低、計(jì)算量少，適于工程實(shí)現(xiàn)。

[1] 朱里奧·杜黑.制空權(quán).[M].北京:解放軍出版社，1991.

[2] 劉波、沈齊、李文清.空基預(yù)警探測系統(tǒng)[M].北京:國防工業(yè)出版社.2012.

[3] 嚴(yán)勇，改進(jìn)的蟻群一遺傳算法在優(yōu)化航線中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用.2008.44(23):230-232.

[4] 李璠.無人機(jī)航跡規(guī)劃算法研究[D].大連：大連理工大學(xué).2011.

[5] 黃文剛，張怡，姜文毅，等.基于改進(jìn)稀疏A*算法的無人機(jī)航路規(guī)劃[J].遙測遙感.2012,33(6):12-16.

[6] 唐強(qiáng)，王建元，朱志強(qiáng).基于粒子群優(yōu)化的三維突防航跡規(guī)劃仿真研究[J].系統(tǒng)仿真學(xué)報(bào)，2004，16(9):2033-2038.

[7] 韓瑞鋒，遺傳算法原理與應(yīng)用實(shí)例[M],北京：兵器工業(yè)出版社，2010.

[8] 劉超，歐杰，曹琪.基于自適應(yīng)遺傳算法的航跡規(guī)劃研究[J].飛行力學(xué).2010,28(1):36-39.

[9] TING LU,JIE ZHU.A Genetic Algorithm for Finding a Path Subject to Two Constraints[J].Applied Soft Computing Journal,2013,13(2):.

[10] HAI-BIN DUAN，XIANG-YIN ZHANG,JIANG WU,et al.Max-min Adaptive Ant Colony Optimization Approach to Mult-UAVs Coordinated Trajictory Replanning in Dynamic and Uncertain Environments[J].Journal of Bionic Engineering,2009:161-171.

[11] IOANNIS K NIKOLOS ,KIMON P VALAVANIS;NIKOS C TSOURVELOUDIS,et al.Evolutionary Algorithm Based Ofnine/Online Path Planner for UAV Navigation[C]//Transactions on Systems，Man，and Cybernetics-part B：Cybernetics：Accepted for future publication．2003：1-15．

[12] YOUFANG HUANG,CHENGJI LIANG,YANG YANG.The Optimum Route Problem by Genetic Algorithm for Loading/Unloading of Yard Crane[J].Computers & Industrial Engineering,2009,56(3):993-1001.