劉麗峰，楊 飛，張樹清，孔維華，王殷行

1.山東理工大學(xué)，山東 淄博 255049；2.中國科學(xué)院地理科學(xué)與資源研究所，北京 100101；3.中國科學(xué)院東北地理與農(nóng)業(yè)生態(tài)研究所，吉林 長春 130102

1 引 言

地形跟蹤、地形回避和威脅回避（TF／TA2）對(duì)巡航導(dǎo)彈的軍事行動(dòng)和飛機(jī)導(dǎo)航有重要意義［1］。本文主要研究飛機(jī)參考航線規(guī)劃問題。常用的航線規(guī)劃算法有：粒子群算法，由初始解追隨最優(yōu)粒子搜索最優(yōu)解，該算法有易陷入局部最優(yōu)解的不足［2］；遺傳算法通過仿效生物界的進(jìn)化規(guī)律（適者生存，優(yōu)勝劣汰遺傳機(jī)制）進(jìn)行隨機(jī)化搜索，然而該算法局部搜索能力差、易于早熟收斂，且難以保持優(yōu)良個(gè)體和群體多樣性［3－4］；模糊邏輯指在多值邏輯的基礎(chǔ)上，運(yùn)用模糊集合研究模糊性思維等規(guī)律的科學(xué)，但該算法的模糊規(guī)則提取困難［5］；A＊搜索算法通過啟發(fā)函數(shù)估計(jì)搜索點(diǎn)和目標(biāo)點(diǎn)間的距離，但有搜索速度慢、難以得到全局最優(yōu)解的缺陷［6］；Voronoi圖方法是由一組相鄰點(diǎn)的垂直平分線構(gòu)成連續(xù)多邊形，但此算法在三維航線規(guī)劃中復(fù)雜度較高，從而降低其實(shí)用性［7］；模擬煺火方法［8］通過模擬固體退火過程實(shí)現(xiàn)，然而有運(yùn)算效率低、速度慢的弊端；禁忌搜索利用禁忌準(zhǔn)則和藐視準(zhǔn)則避免迂回搜索并保證解的多樣性，但結(jié)果依賴于初始解的選擇［9－10］；進(jìn)化算法通過模擬自然進(jìn)化過程進(jìn)行隨機(jī)搜索的方法，該方法有保持群體的多樣性及收斂性差的不足［11－12］；人工神經(jīng)網(wǎng)絡(luò)算法由大量加權(quán)節(jié)點(diǎn)（或稱神經(jīng)元）相互連接構(gòu)成，缺陷有收斂速度慢、易于限于局部最優(yōu)解［13－14］；GIS空間查詢代數(shù)能實(shí)現(xiàn)最短路徑查詢，但空間計(jì)算較復(fù)雜［15］；文獻(xiàn)［16］研究出租車司機(jī)選擇道路的經(jīng)驗(yàn)及規(guī)律，由此建立道路尋徑模型，但又受限于司機(jī)的經(jīng)驗(yàn)；文獻(xiàn)［17］將時(shí)間因子引入啟發(fā)式評(píng)價(jià)函數(shù)，提出了基于路段標(biāo)號(hào)的時(shí)間依賴A＊最短路徑算法以及上述算法的混合算法［18－19］。電勢理論屬于梯度尋優(yōu)算法，選取懲罰函數(shù)最小的梯度方向逼近目標(biāo)點(diǎn)，該算法結(jié)構(gòu)簡單速度快，但容易陷入局部最優(yōu)［20］。以上算法在大范圍內(nèi)搜索時(shí)都存在信息存儲(chǔ)、處理量巨大與全局最優(yōu)的矛盾。因此，本文針對(duì)該問題研究飛機(jī)在復(fù)雜環(huán)境下安全、實(shí)用航線的規(guī)劃問題。

針對(duì)遺傳算法（GA）的缺點(diǎn)，文獻(xiàn)［21］利用BP神經(jīng)網(wǎng)絡(luò)提高GA實(shí)時(shí)性和解決非線性問題的能力；文獻(xiàn)［22］將知識(shí)規(guī)則和GA相結(jié)合實(shí)現(xiàn)多目標(biāo)優(yōu)化。目前，人工免疫算法（AIA）多用于機(jī)器人路徑規(guī)劃領(lǐng)域，而在飛機(jī)航線規(guī)劃領(lǐng)域較少［23－24］。文獻(xiàn)［25］提出混合 Memetic算法—GA神經(jīng)免疫網(wǎng)絡(luò)用于靜態(tài)環(huán)境下的次優(yōu)無碰撞路徑規(guī)劃。本文探討利用AIA規(guī)劃復(fù)雜環(huán)境下三維TF／TA2航線［26－27］。

2 利用AIA的航線規(guī)劃

2.1 問題提出

本文利用人工免疫算法計(jì)算在復(fù)雜環(huán)境下滿足飛機(jī)性能等要求的三維飛行航線。本研究中將航線規(guī)劃分為單機(jī)和雙機(jī)兩類。在雙機(jī)規(guī)劃問題中需考慮：①多機(jī)合作問題；②多機(jī)協(xié)同問題。雙機(jī)系統(tǒng)的重點(diǎn)是雙機(jī)間的合作問題，包括到達(dá)時(shí)間、攻擊方向以及任務(wù)分配方面的協(xié)調(diào)。

飛機(jī)TF／TA2路徑規(guī)劃的特點(diǎn)有：

（1）隱蔽性。飛行路徑優(yōu)先選擇威脅最小的區(qū)域，例如雷達(dá)盲區(qū)、距障礙最小安全距離、最大飛行高度以及距地面最小距離。

（2）可飛性。飛行航線需滿足飛機(jī)的性能有：爬升／下降率、航線角、航程、空速以及最小轉(zhuǎn)彎半徑。

（3）協(xié)同性。對(duì)于多機(jī)規(guī)劃來說，要求飛機(jī)同時(shí)到達(dá)目的地。

（4）實(shí)時(shí)性。要求下一航段規(guī)劃時(shí)間小于當(dāng)前航段的飛行時(shí)間。

2.2 利用AIA規(guī)劃飛行路徑過程

人工免疫算法（AIA）是借鑒人工免疫系統(tǒng)的概念和理論，將計(jì)算模型與工程應(yīng)用相結(jié)合的方法。該方法將待求問題作為抗原，問題的解視為抗體。本研究利用AIA能并行計(jì)算及保持解多樣性優(yōu)點(diǎn)，結(jié)合飛機(jī)特性設(shè)計(jì)飛行航線。AIA飛行路徑規(guī)劃過程包括：種群特征初始化、選擇技術(shù)、交叉操作、變異操作、接種、種群更新技術(shù)、進(jìn)化技術(shù)和收斂條件。

2.2.1 種群特征

種群包括一定數(shù)目的抗體，抗體代表待選航線；在本試驗(yàn)中每條待選航線包括10個(gè)航跡點(diǎn)，其中，起、止點(diǎn)（第1點(diǎn)和10點(diǎn)，）為任務(wù)的出發(fā)點(diǎn)和目標(biāo)點(diǎn)，航跡點(diǎn)2—9坐標(biāo)在空域范圍內(nèi)隨機(jī)產(chǎn)生（xmin≤xij≤xmax，ymin≤yij≤ymax，xminymin指空域左下角坐標(biāo)，xmax、ymax為空域右上角坐標(biāo)），即“開始點(diǎn)→x1y1→x2y2…x8y8→結(jié)束點(diǎn)”，xji、yji指第i條航線li（式（1））的第j個(gè)航跡點(diǎn)的x、y坐標(biāo)。Nanti為抗體總數(shù)，x0y0和x9y9分別為起始點(diǎn)和目標(biāo)點(diǎn)的x、y坐標(biāo)

2.2.2 選擇技術(shù)

2.2.3 復(fù)制和變異操作

當(dāng)抗體未達(dá)到終止條件時(shí)，抗體需要執(zhí)行變異操作。由于“1－1選擇概率”能為抗體提供高變異概率，因此本研究中復(fù)制全部父抗體用于變異操作；若變異后新抗體的親和力值小于原抗體則取代之，否則，保留原抗體不變。變異分為兩種模式：①交叉后變異，此方式適用于交叉操作不滿足終止條件的情形；②不交叉直接變異，此方式的主要操作對(duì)象為疫苗。

變異方式1的步驟如下：

（1）復(fù)制全部父代抗體；

（2）按照選擇的交叉方式對(duì)復(fù)制的抗體執(zhí)行交叉操作，生成新抗體；

（3）將抗體二值化，并隨機(jī)選出變異位置執(zhí)行變異操作，即將變異位置的值變異，若變異位置的值為“0”則變?yōu)椤?”，反之亦然；

（4）計(jì)算新抗體的親和力值，若親和力值小于原抗體親和力值，則取代原抗體，否則，保留原抗體。

變異方式2的具體步驟為：

（1）復(fù)制全部父代抗體；

（2）將抗體二值化，并隨機(jī)選擇變異位置進(jìn)行變異，操作同變異方式1。

2.2.4 交叉和接種

本文采用3種選擇抗體模式進(jìn)行點(diǎn)交叉操作，計(jì)算過程見式（3），其中i，j∈（1，Nanti），為提高抗體的多樣性，隨機(jī)選擇交叉點(diǎn)位置k，k∈（1，8），ln指新生成的抗體：

（1）隨機(jī)選擇抗體i、j執(zhí)行交叉操作。

（2）任意選擇抗體i，計(jì)算抗體j執(zhí)行交叉操作，其中j＝Nanti＋1－i。

（3）隨機(jī)選擇第i個(gè)抗體，計(jì)算出抗體j的位置，其中j＝［Nimm／2］＋i，［］指向下取整

計(jì)算抗體親和力函數(shù)值?？贵w親和力函數(shù)值小于疫苗閾值即為疫苗，加入疫苗池。再通過以下3種選擇方法，選出抗體和疫苗執(zhí)行接種操作：

（1）隨機(jī)地選擇抗體i和疫苗j接種（見式（4）），其中i∈（1～Nanti）。

（2）每個(gè)抗體i和隨機(jī)選出的疫苗j接種，見式（4）

式中，i∈（1，Nanti），j∈（1，Nimm）；k、q為0～9之間的隨機(jī)數(shù)，且q＞k；lni表示第i個(gè)新抗體；Nimm指疫苗總數(shù)。上述兩種方式中，隨機(jī)選擇接種位置k進(jìn)行接種，接種位置與航線段中航跡點(diǎn)的順序、長度和疫苗一致，設(shè)疫苗段起始位置為m，即k＝m、q＝n。

（3）每個(gè)抗體i都接種，接種位置p和疫苗段起始位置m都是隨機(jī)選擇的，但接種抗體段和疫苗段的長度相同，見式（5）

式中，p＝k＋（n－m）；k∈｛0，1，2，…，9｝，p∈｛0，1，2，…，9｝；p≠m；i∈｛1～Nanti｝。

2.2.5 構(gòu)建親和函數(shù)（懲罰函數(shù)）

親和力函數(shù)指抗體總威脅代價(jià)值見式（6）。本文中親和力函數(shù)定義為抗體的3D綜合路徑長度。為統(tǒng)一計(jì)算各威脅值，本文中將其他威脅轉(zhuǎn)化為地形威脅，因此該函數(shù)不但能反映地形威脅，還能表達(dá)不確定性威脅以及不可飛區(qū)域?qū)︼w行安全的影響

式中，affinity（lj）是路徑（抗體）lj的親和力函數(shù) 值（j＝1，2，…，Nanti）；d（p（i）、p（i＋1））是航線lj中航線段p（i）p（i＋1）距離；X（i）、Y（i）、Z（i）和X（i＋1）、Y（i＋1）、Z（i＋1）分別為航跡點(diǎn)i、航跡點(diǎn)i＋1的三維坐標(biāo)，其中i∈（1，n），n表示航跡點(diǎn)總數(shù)，n＝10。

2.2.6 種群更新技術(shù)

抗體群由疫苗和復(fù)制的部分父抗體組成。計(jì)算種群中全部抗體的親和力函數(shù)值，親和值大于閾值或不滿足可飛性條件的抗體將由疫苗取代，疫苗也按照親和力值小的優(yōu)先選出，且保證抗體總數(shù)Nanti不變

式中，affinityset為設(shè)定的親和力閾值；Nchooseanti指小于affinityset的抗體數(shù)。ldeimmk指親和力函數(shù)值較小的（Nanti－Nchooseanti）個(gè)疫苗；j∈Nanti；i∈Nanti。

2.3 進(jìn)化技術(shù)和收斂條件

通過上述操作可以得到新抗體群（路徑解）。計(jì)算本代最優(yōu)抗體與抗原比較，如果滿足要求程序結(jié)束；若不滿足收斂條件時(shí)，程序繼續(xù)循環(huán)，否則，需要調(diào)整初始參數(shù)，例如增加種群個(gè)數(shù)、提高變異概率等，實(shí)現(xiàn)種群更新進(jìn)化。在本試驗(yàn)中，為保證航線的實(shí)時(shí)性和實(shí)用性，在收斂條件結(jié)合了迭代代數(shù)和時(shí)間因素。itationset為設(shè)定的迭代次數(shù)，ldest指抗原（即最優(yōu)航線）。

表1 算法迭代和收斂過程Tab.1 Iterative algorithms and convergence process

2.4 航線光滑處理

利用AIA設(shè)計(jì)的初步飛行路徑由條折線段連接而成，實(shí)用性受到限制；為提高飛行航線的實(shí)用性和安全性，需要對(duì)航線光滑處理。在本文中，航線光滑處理步驟包括：首先，在水平方向上，按照最大轉(zhuǎn)彎角對(duì)航跡點(diǎn)檢查，若航跡點(diǎn)轉(zhuǎn)彎角超限，則需按坡度和曲率限制對(duì)其坐標(biāo)值調(diào)整（見式（9）），否則，航跡點(diǎn)位置不變；其次，在垂直方向上，要求航跡點(diǎn)滿足法向過載和最大爬升角限制；法向過載在－g～2g之間（g為重力加速度），最大爬升角限制的計(jì)算見式（10）；最后，利用三次B樣條曲線對(duì)航線作光滑處理

航線規(guī)劃流程圖中說明了人工免疫算航線規(guī)劃的具體步驟（見圖1）。

3 仿真試驗(yàn)及分析

本試驗(yàn)中，空域設(shè)為60km×60km，飛行條件中，俯仰角為－20°～20°，最大轉(zhuǎn)彎角為－60°～60°，最小航線段長度為5km，飛行速度為61～77m／s。計(jì)算機(jī)環(huán)境為Pentium（R）2CPU 2.2GHz。在單機(jī)航線規(guī)劃中，起始點(diǎn)和目標(biāo)點(diǎn)的坐標(biāo)分別為（1km，1km，0.3km）和 （60km，60km，0.3 km）。在雙機(jī)航線規(guī)劃中，甲、乙起始點(diǎn)坐標(biāo)為（1 km，8km，0.3km）和（10km，1km，0.3km）；雙機(jī)的目標(biāo)點(diǎn)和單機(jī)相同（60km，60km，0.3km）。為了測試該算法的有效性和魯棒性，在虛擬戰(zhàn)場中假設(shè)了3種想定，對(duì)動(dòng)態(tài)變化復(fù)雜環(huán)境進(jìn)行仿真試驗(yàn)，包括飛機(jī)數(shù)量和威脅種類或／及數(shù)量變化，并與相同條件下的遺傳算法（GA）進(jìn)行了對(duì)比分析。

在本研究中，試驗(yàn)環(huán)境分為兩類：簡單威脅環(huán)境（簡稱簡單環(huán)境）和復(fù)雜威脅環(huán)境（簡稱復(fù)雜環(huán)境）。在簡單威脅環(huán)境中，僅包括考慮地形威脅，對(duì)應(yīng)于TF／TA2任務(wù)的起飛階段（即起始點(diǎn)進(jìn)入敵方空域段）。復(fù)雜威脅環(huán)境指在敵方空域飛行階段，威脅包括不可飛區(qū)域和突發(fā)威脅。

3.1 測試想定1

本想定的威脅環(huán)境包括：起始點(diǎn)處4座山峰（影響安全航線產(chǎn)生）及目標(biāo)點(diǎn)前方1座山峰（阻礙航線收斂）。在圖2（a）中，威脅區(qū)域由一組等高線表示，山峰的高程見圖2（b）右側(cè)高程表；圖2（a）中曲線表示AIA航線（三維路徑在水平面上的投影）選擇了縱軸附近安全、低空區(qū)域。圖2（b）中為AIA規(guī)劃的三維飛行路徑，飛行通過區(qū)域?yàn)橥{度最小的地區(qū)。圖3表示利用遺傳算法（GA）規(guī)劃的航線，與AIA相比規(guī)劃時(shí)間較短（GA 4.344s，AIA 5.88s），但航線長度稍長。此試驗(yàn)表明，GA在簡單環(huán)境下能快速設(shè)計(jì)出飛行航線。表2體現(xiàn)了在簡單威脅環(huán)境下，遺傳算法在規(guī)劃時(shí)間及標(biāo)準(zhǔn)差方面都優(yōu)于人工免疫算法。

圖2 簡單環(huán)境下AIA規(guī)劃的飛行航線Fig.2 Flight path by AIA under a simple environment

圖3 簡單環(huán)境下GA規(guī)劃的飛行航線Fig.3 Flight path by GA under a simple environment

3.2 測試想定2

由于飛機(jī)視域及飛行速度的限制，在復(fù)雜環(huán)境下飛行需具有快速應(yīng)對(duì)突發(fā)威脅能力。想定2的規(guī)劃環(huán)境為：在想定1中加入4個(gè)不可飛區(qū)域，安全區(qū)域僅為靠近縱軸狹窄通道（見圖4（a））。不可飛區(qū)指航線不能飛越的區(qū)域，在圖4（a）和圖4（b）分別中由一組圓環(huán)和圓柱體表示。

圖4 復(fù)雜環(huán)境下AIA規(guī)劃的飛行航線Fig.4 Flight path by AIA on a complex environment

圖4證實(shí)了在復(fù)雜環(huán)境下AIA解決飛行航線規(guī)劃問題的可行性和有效性。在圖5中，GA能設(shè)計(jì)出滿足要求的航線，但航線規(guī)劃的迭代代數(shù)（196代）及失敗次數(shù)較多（＞95%）。原因在于GA中航線評(píng)價(jià)標(biāo)準(zhǔn)是唯一的，即個(gè)體對(duì)目標(biāo)的適應(yīng)度，而AIA中評(píng)價(jià)標(biāo)準(zhǔn)包括個(gè)體的適應(yīng)度及自身的濃度，要求滿足以上2個(gè)條件（即不但適應(yīng)度高且個(gè)體濃度不高）的抗體才能被選擇，這有利于保持群體多樣性。另外，GA在交叉和變異時(shí)，以交叉為主變異為輔，在復(fù)雜環(huán)境下，若陷入局部最優(yōu)解時(shí)僅僅通過交叉操作很難找到可行解；而AIA則相反，以變異為主，交叉為輔，抗體則可以通過變異改善解群取值找到可行解。通過該試驗(yàn)得到如下結(jié)論：在復(fù)雜環(huán)境下單機(jī)航線規(guī)劃，相同條件下AIA比GA算法尋優(yōu)能力更強(qiáng)。因此，在復(fù)雜環(huán)境下較易搜索到可行航線。

圖5 復(fù)雜環(huán)境下GA規(guī)劃的飛行航線Fig.5 Flight path by GA on a complex environment

3.3 測試想定3

想定3為雙機(jī)航線規(guī)劃情景：兩機(jī)從異地飛向相同目標(biāo)點(diǎn)，要求兩機(jī)的航線差最?。ㄍㄟ^速度調(diào)整可以實(shí)現(xiàn)同時(shí)到達(dá)）。規(guī)劃環(huán)境包括：①與想定1相同；②在想定1出現(xiàn)突發(fā)威脅；③在想定1內(nèi)加入了4個(gè)不可飛區(qū)域。

（1）在該規(guī)劃環(huán)境下，AIA和GA規(guī)劃航線見圖6、圖7。圖6（b）顯示了GA僅能為甲機(jī)規(guī)劃飛行航線，而不能為乙機(jī)規(guī)劃出的可行航線；圖7（b）表明AIA能為雙機(jī)規(guī)劃出可行航線，且滿足航程短、航線差小、飛行安全的要求。在圖7中，甲機(jī)航線航程64.658km，乙機(jī)航線63.704 km，航線差為0.955km，可以通過速度調(diào)整實(shí)現(xiàn)同時(shí)到。圖7（c）顯示了雙機(jī)都有多條備選路徑，其中左側(cè)淺色橢圓內(nèi)的航線為甲機(jī)待選航線，右側(cè)深色橢圓內(nèi)的航線為乙機(jī)待選航線。待選航線生成提高了該算法的實(shí)用性，即當(dāng)威脅環(huán)境變化時(shí)，飛機(jī)能夠快速調(diào)用備選航線。

該試驗(yàn)說明：在較復(fù)雜環(huán)境下的雙機(jī)航線規(guī)劃，AIA比GA更有效；源于GA以獲得全局最優(yōu)解為目的，而AIA則能搜索多極值函數(shù)的多個(gè)極值點(diǎn)，該算法自身特點(diǎn)決定了AIA在雙機(jī)航線規(guī)劃中具有GA不具備的優(yōu)勢。

圖6 復(fù)雜環(huán)境下用GA規(guī)劃的雙機(jī)飛行航線Fig.6 Flight paths planning for dual aircrafts by GA under a complex environment

（2）在該規(guī)劃環(huán)境中，設(shè)定突發(fā)威脅出現(xiàn)在圖4中參考航線附近（即參考航線位于突發(fā)威脅的影響范圍內(nèi)），重新規(guī)劃后的航線見圖8。圖8（a）和8（b）表示規(guī)劃出的雙機(jī)安全航線，甲機(jī)航線采取低空地形回避策略，乙機(jī)航線則選擇地形跟隨策略，8（c）顯示了甲乙兩機(jī)規(guī)劃的待選航線。

（3）在該規(guī)劃環(huán)境中，在想定1中加入4個(gè)不可飛區(qū)域，規(guī)劃結(jié)果見圖9。從圖9（a）和9（b）中表明雙機(jī)航線都位于安全且地勢較低的區(qū)域，9（c）則顯示了由于環(huán)境復(fù)雜度提高，迭代代數(shù)的極大增加，也得到更多次優(yōu)航線。AIA規(guī)劃的航線通過低空威脅度最小的區(qū)域，且充分地利用了地形的隱蔽作用，因此能提高飛機(jī)TF／TA2的成功率。

圖7 復(fù)雜環(huán)境下AIA規(guī)劃的雙機(jī)飛行航線及待選航線Fig.7 Flight and candidate paths planning for dual aircrafts by AIA under a complex environment

圖8 復(fù)雜環(huán)境下有突發(fā)威脅時(shí)AIA規(guī)劃的飛行航線及待選航線Fig.8 Flight and candidate paths with unexpected threats for dual aircrafts by AIA under a complex environment

圖9 復(fù)雜環(huán)境下有不可飛區(qū)域時(shí)AIA規(guī)劃的飛行航線及待選航線Fig.9 Flight and candidate paths with unexpected threats for dual aircrafts by AIA under a complex environment

3.4 算法的性能評(píng)價(jià)

對(duì)于GA和AIA的性能進(jìn)行評(píng)價(jià)，表2和表3為AIA和GA算法在計(jì)算復(fù)雜度、實(shí)時(shí)性、魯棒性方面對(duì)比，圖10顯示了AIA和GA算法在收斂性方面比較。表2顯示了在簡單環(huán)境下，兩種算法規(guī)劃的航線實(shí)時(shí)性都較強(qiáng)，GA規(guī)劃時(shí)間和計(jì)算復(fù)雜度比人工免疫算法（增加了接種操作）較優(yōu)，但在離線航線規(guī)劃中由于地面計(jì)算資源和規(guī)劃時(shí)間充足而影響極小。另外，AIA能規(guī)劃出多條備選航線，可以應(yīng)對(duì)突發(fā)狀況的出現(xiàn)，從而提高了該算法的魯棒性和適應(yīng)性。

圖10 人工免疫算法和遺傳算法的收斂曲線Fig.10 The convergence curves of AIA and GA

表2 簡單環(huán)境下遺傳算法和人工免疫算法比較Tab.2 The comparison of GA and AIA under a simple environment s

表3 復(fù)雜環(huán)境下遺傳算法和人工免疫算法比較Tab.3 The comparison of GA and AIA under complex environment

由表2可知，算法計(jì)算復(fù)雜度與抗差性成反比，在計(jì)算復(fù)雜度和抗差性方面AIA優(yōu)于GA。這在復(fù)雜環(huán)境下遺傳算法未能為雙機(jī)規(guī)劃出飛行航線中體現(xiàn)出來。圖10是在地形威脅環(huán)境下兩種算法收斂時(shí)間的比較：AIA（180代）收斂速度比GA（大于200代）快，因此實(shí)時(shí)性也較好。在迭代的初始階段，AIA的航線代價(jià)（87.5）大于GA（74.6），隨著迭代代數(shù)的增加，航線代價(jià)不斷地減小，在146代時(shí)小于GA，這體現(xiàn)了該算法在航線安全性方面的優(yōu)勢（總代價(jià)與安全性成反比）。

4 結(jié)論與討論

本文研究利用人工免疫算法規(guī)劃單、雙機(jī)TF／TA2飛行路徑。在基本人工免疫算法基礎(chǔ)上，加入威脅環(huán)境、飛行任務(wù)及可飛性和安全性約束條件，對(duì)算法進(jìn)行初步改進(jìn)。另外，通過設(shè)計(jì)綜合安全性能評(píng)價(jià)函數(shù)（親和力函數(shù)）和三次樣條曲線光滑處理方法對(duì)該算法進(jìn)一步優(yōu)化，提高其實(shí)用性。仿真試驗(yàn)結(jié)果表明，在復(fù)雜環(huán)境下，人工免疫算法能夠?yàn)轱w機(jī)規(guī)劃出一條最優(yōu)或多條待選次優(yōu)飛行航線。本算法在出發(fā)點(diǎn)處障礙率為94.25%的環(huán)境下規(guī)劃出多條安全飛行航線。平均規(guī)劃時(shí)間5.49s遠(yuǎn)小于最小航線段飛行時(shí)間60s，迭代代數(shù)160，且標(biāo)準(zhǔn)差小于0.7，說明該算法具有較強(qiáng)的搜索能力、抗差性和實(shí)時(shí)性。

本研究分別在簡單環(huán)境和復(fù)雜環(huán)境下的AIA單雙機(jī)航線規(guī)劃，并與相同條件下GA規(guī)劃結(jié)果比較：在復(fù)雜環(huán)境下的航線規(guī)劃中，AIA比GA收斂性更強(qiáng)，成功率更高。這是由于免疫算法具有以下特點(diǎn)：①提取一部分親和力較低的抗體作為疫苗，并將疫苗與復(fù)制擴(kuò)增參的父代抗體接種，提高算法收斂性；②交叉、變異操作能夠有效地保持抗體的多樣性，使其更適應(yīng)于復(fù)雜環(huán)境下的航線規(guī)劃；③復(fù)制過程是抗體自身復(fù)制過程，抗體之間沒有交叉；④疫苗池能夠較好地保持優(yōu)良抗體及其信息。因此，AIA具有全局搜索能力較強(qiáng)，且局部搜索能力快的優(yōu)點(diǎn)。另外，AIA自身的模式識(shí)別能力，也能夠生成適應(yīng)復(fù)雜環(huán)境下不同任務(wù)的抗體，使其特別適用于復(fù)雜環(huán)境下最優(yōu)解和多解的問題。由于在復(fù)雜環(huán)境下的航線規(guī)劃中AIA比GA的成功率提高了175%，也說明該算法在復(fù)雜環(huán)境下優(yōu)越性更強(qiáng)。

［1］ TANG Q，ZHANG X G，LIU X C.TF／TA2Trajectory Tracking Using Nonlinear Predictive Control Approach［J］.Journal of Systems Engineering and Electronics，2006，17（2）：396－401.

［2］ LI Linyi，LI Deren.Image Texture Classification Based on Immune Particle Swarm Optimization［J］.Acta Geodaetica et Cartographica Sinica，2008（5），37（2）：185－195.（李林宜，李德仁.基于免疫粒子群優(yōu)化算法的影像紋理分類［J］.測繪學(xué)報(bào)，2008（5），37（2）：185－195.）

［3］ ALLAIRE F C J，TARBOUCHI M，LABONTéG，et al.FPGA Implementation of Genetic Algorithm for UAV Real－time Path Planning［J］.Journal of Intelligent and Robotic Systems，2009，54（1－3）：495－510.

［4］ FOO J L，KNUTZON J，KALIVARAPU V，et al.Path Planning of Unmanned Aerial Vehicles Using B－splines and Particle Swarm Optimization［J］.Journal of Aerospace Computing，Information，and Communication，2009，6：271－290.

［5］ SABO C，COHEN K，KUMAR M，et al.Effectiveness of 2DPath Planning in Real Time Using Fuzzy Logic［C］∥Proceedings of the 48th AIAA Aerospace Sciences Meeting Including the New Horizons Forum and Aerospace Exposition.Orlando：AIAA，2010：1－13.

［6］ WARREN C W.Fast Path Planning Using Modified A＊Method［J］.Robotics and Automation，1993，2：662－667.

［7］ HAMMOURI O M，MATALGAH M M.Voronoi Path Planning Technique for Recovering Communication in UAVs［C］∥Proceedings of ACS International Conference on Computer Systems and Applications.Doha：ACS，2008：403－406.

［8］ ZHANG Keshi，WANG Zhengping.On Optimizing Large－scale Air－combat Formation with Simulated：Annealing GA （Genetic Algorithm）［J］.Journal of North Western Polytechnical University，2003，21（4）：477－480.（張科施，王正平.基于遺傳模擬退火算法的空戰(zhàn)編隊(duì)優(yōu)化研究［J］.西北工業(yè)大學(xué)學(xué)報(bào)，2003，21（4）：477－480.）

［9］ QIU Z P，ZHANG Y.Parametric Optimization Design of Aircraft Based on Hybrid Parallel Multi－objective Tabu Search Algorithm［J］.Chinese Journal of Aeronautics，2010，23（4）：430－437.

［10］ BAI Zhipeng，CHEN Fuji.Compound Method of Taboo Search and Genetic Algorithm to Sove Knapsack Problem［J］.Automation ＆Information Engineering，2007，28（2）：9－11.（白志鵬，陳福集.禁忌搜索與GA算法結(jié)合求解背包問題［J］.自動(dòng)化與信息工程，2007，28（2）：9－11.）

［11］ ZHANG Fuwei，LI Jun，MENG Pinchao，et al.Survey of Multi－objective Evolutionary Algorithms［J］.Journal of Changchun University of Science and Technology：Natural Science Edition，2012，35（3）：102－105.（張福威，李軍，孟品超，等.多目標(biāo)進(jìn)化算法綜述［J］.長春理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，35（3）：102－105.）

［12］ PONGPUNWATTANA A，RYSDYK R.Evolution－based Dynamic Path Planning for Autonomous Vehicles［J］.Studies in Computational Intelligence，2007，70：113－145.

［13］ DONG Z，YUAN J.A Formulation for Collision Identification and Distance Calculation in Motion Planning Using Neural Networks［J］.The International Journal of Advanced Manufacturing Technology，1993，8（4）：227－234.

［14］ YOU Shucheng，YAN Tailai.A Study on Artificial Neural Net Work Based Surface Interpolation［J］.Acta Geodaetica et Cartographica Sinica，2000，29（1）：30－34.（尤淑撐，嚴(yán)泰來.基于人工神經(jīng)網(wǎng)絡(luò)面插值的方法研究［J］.測繪學(xué)報(bào)，2000，29（1）：30－34.）

［15］ LI Lin.Variable Query Algebra and Shortest Path Analysis［J］.Acta Geodaetica et Cartographica Sinica，2000，29（1）：59－63.（李霖.變量查詢代數(shù)及最短路徑分析［J］.測繪學(xué)報(bào)，2000，29（1）：59－63.）

［16］ TANG Luliang，CHANG Xiaomeng，LI Qingquan.The Knowledge Modeling and Route Planning Based on Taxi’Experience［J］.Acta Geodaetica et Cartographica Sinica，2010，39（4）：404－409.（唐爐亮，常曉猛，李清泉.出租車經(jīng)驗(yàn)知識(shí)建模與路徑規(guī)劃算法［J］.測繪學(xué)報(bào)，2010（8），39（4）：404－409.）

［17］ ZHENG Nianbo，LU Feng，LI Qingquan，et al.The Adaption of A＊Algorithm for Least－time Path in Time－dependent Transportation Networks with Turn Delays［J］.Acta Geodaetica et Cartographica Sinica，2010，39（5）：404－409.（鄭年波，陸鋒，李清泉，等.顧及轉(zhuǎn)向延誤的時(shí)間依賴A＊最短路徑算法［J］.測繪學(xué)報(bào)，2010，39（5）：404－409.）

［18］ JIANG Y，WANG H G，F(xiàn)ANG L J，et al.2006.Motion Planning for Climbing Robot Based on Hybrid Navigation［J］.Advance in Machine Learning and Computing，2006，3930：91－100.

［19］ KURNAZ S，KAYNAK O，KONAKO L U E.Adaptive Neuro－fuzzy Inference System Based Autonomous Flight Control of Unmanned Air Vehicles［J］.Expert Systems with Applications，2007，37（2）：14－21.

［20］ XIN Y，ZHU Q D，YAN Y J.Collision Avoidance Planning in Multi－robot System Based on Improved Artificial Potential Field and Rules［J］.Journal of Harbin Institute of Technology，2009，16（3）：413－418.

［21］ LIU Hanli，ZHOU Chenghu，ZHU Axin，et al.Multi－Population Genetic Neural Network Model for Short－term Traffic Flow Prediction at Intersections［J］.Acta Geodaetica et Cartographica Sinica，2009，38（4）：363－368.（劉漢麗，周成虎，朱阿興，等.多子群遺傳神經(jīng)網(wǎng)絡(luò)模型用于路口短時(shí) 交 通 流 量 預(yù) 測 ［J］.測 繪 學(xué) 報(bào)，2009，38（4）：363－368.）

［22］ ZHAI Renjian，WU Fang，DENG Hongyan，et al.An Automated Selection Model of Ditch Based on Multiobjective Optimization by Genetic Algorithm［J］.Acta Geodaetica et Cartographica Sinica，2008，37（1）：108－113.（翟仁健，武芳，鄧紅艷，等.基于遺傳多目標(biāo)優(yōu)化的人工河網(wǎng)自動(dòng)選取模型［J］.測繪學(xué)報(bào)，2008，37（1）：108－113.）

［23］ MAYORGA R V，WONG A K C.A Robust Method for the Concurrent Motion Planning of Multi－manipulators Systems［J］.Journal of Intelligent and Robotic Systems，1997，19（1）：73－88.

［24］ YU Z G，SONG S M，DUAN G R.A New Artificial Immune Algorithm and Its Application for Optimization Problems［J］.Journal of Harbin Institute of Technology，2006，13（2），129－133.

［25］ BHADURI A.University Time Table Scheduling Using Genetic Artificial Immune Network［C］∥International Conference on Advances in Recent Technologies in Communication and Computing.Los Alamos：IEEE Computer Society，2009：289－292.

［26］ MALIM M R，KHADER A T，MUSTAFA A.Artificial Immune Algorithms for University Timetabling［C］∥Proceedings of the 6th International Conference on Practice and Theory of Automated Timetabling.Brno：［s.n.］，2006：234－245.

［27］ OBERHEID H，S?FFKER D.Cooperative Arrival Management in Air Traffic Control：A Coloured Petri Net Model of Sequence Planning［J］.Applications and Theory of Petri Nets，2008，5062：348－367.