基于遺傳算法的ADS—B飛行航跡規(guī)劃方法研究

袁小凱 傅強 侯明利

摘要：ADS-B是廣播式自動相關(guān)監(jiān)視，是一種比較先進的監(jiān)視技術(shù)，也是未來監(jiān)視系統(tǒng)的發(fā)展走向，因此研究ADS-B飛行航跡規(guī)劃具有重要意義，在此將研究如何利用遺傳算法優(yōu)化ADS-B飛行航跡，優(yōu)化過程中，采用特定的編碼方法和適應度函數(shù)。

關(guān)鍵詞：遺傳算法；ADS-B；飛行航跡

中圖分類號：V249.1文獻標識碼：A文章編號：1008-4428（2019）03-0170-02

一、 引言

廣播式自動相關(guān)監(jiān)視（ADS-B）是空管領(lǐng)域中的一項革命性技術(shù)，這項技術(shù)實現(xiàn)的是空對空、空對地、地對空以及地對地的信息傳遞和監(jiān)控。它是以廣播的形式向外發(fā)送信息，其信息可以包含多種，比如高度、速度、位置等信息，發(fā)送效率高，而且自動的，無須人工干預，監(jiān)視設(shè)備費用比較低，易于安裝。該監(jiān)視系統(tǒng)是全球最為認可的監(jiān)視系統(tǒng)，它是未來監(jiān)視手段的發(fā)展走向，未來它將達到普及。廣播式自動相關(guān)監(jiān)視系統(tǒng)將使民航飛行更加安全和高效，國際民航組織也將其確定為未來發(fā)展的主方向，現(xiàn)在許多歐美國家以及澳大利亞正在大量使用該系統(tǒng)，未來中國也會將其普及。它不像雷達監(jiān)視系統(tǒng)那樣具有局限的覆蓋范圍，會有探測盲區(qū)，自動相關(guān)監(jiān)視系統(tǒng)發(fā)射范圍廣，投資費用不高，而且后期維護費用也不高，可以更長時間使用。另外，可以提高空域利用率，原來雷達覆蓋盲區(qū)，通過使用自動相關(guān)監(jiān)視系統(tǒng)，使得空域利用增加。這種監(jiān)視系統(tǒng)可以實現(xiàn)信息的交互，無論是在天上還是地上，只要有接收設(shè)備都可以收到發(fā)射機發(fā)射的信息，因此可以形成互相監(jiān)視，使得運行更加安全。在天上時，其中一架飛機可以得知其他飛機的位置、高度、航班號等信息，而地面人員也能夠得知該架飛機的信息；在地面上時，地面上運動體通過該系統(tǒng)相互得知位置，一旦有沖突就會及時發(fā)現(xiàn)，及時處理。廣播式自動相關(guān)監(jiān)視系統(tǒng)功能比較強大，意義深遠，可以提高安全性、空域利用容量，還可以降低投資成本，為建設(shè)民航強國奠定基礎(chǔ)。

遺傳算法是一種人工智能算法，它模仿了生物進化的思想，生物進化中的自然選擇和進化機制被有效地借鑒，它具有高度并行、隨機、自我適應的功能。遺傳算法應用比較廣泛，它被越來越多的應用于各個領(lǐng)域，其中路徑規(guī)劃就是典型的應用例子，對于路徑規(guī)劃的研究方法，遺傳算法比較適用。通過整體搜索的方法，在一定的約束條件下，進行一系列的操作，主要包括選擇、交叉、遺傳操作，使得復雜的問題逐一解決。

飛行器航跡規(guī)劃是實現(xiàn)飛行器自動導航的一項關(guān)鍵技術(shù)。對飛行器航跡進行規(guī)劃，要在一定的特定約束條件下，飛行器從起點到終點，航跡規(guī)劃就是從許多的航跡中挑選出最優(yōu)的航跡。在航跡規(guī)劃中，其主要內(nèi)容就是在滿足一系列約束條件下，找到那條最優(yōu)航跡。路徑規(guī)劃是一個復雜的問題，它涉及滿足物理無人機的約束條件操作環(huán)境和其他操作要求。最重要的是要滿足的約束路徑必須是可飛的?？梢燥w的路徑是那些滿足飛行器的運動約束，滿足這個約束確保飛行器的運動在最大范圍內(nèi)操縱，路徑的安全性是通過能力來衡量的，避免威脅、障礙和其他無人機的沖突。

在執(zhí)行飛行任務時，飛行器需要以任務規(guī)劃所得的參考航線為基準，該航線上的威脅信息都可以展示出來，依據(jù)威脅信息，可以計算得到飛行器的最優(yōu)航跡，監(jiān)控整個過程直到任務完成。雖然當前的方法比較實用，但是仍然存在著許多問題：在航跡優(yōu)化的過程中，函數(shù)收斂比較慢，而且在執(zhí)行飛行任務時，從起點出發(fā)，過程中不能更有效的收斂于終點，要想達到結(jié)果，就要設(shè)置優(yōu)化方程，這樣一來，整個過程就顯得愈加復雜，整個優(yōu)化過程中最重要的就是收斂于終點。

二、 進行航跡規(guī)劃

（一）編碼

在此，將遺傳算法歸納為以下五個元素：

GA={Mu，Cv，Pc，Ea}（1）

假設(shè)一次飛行器的飛行任務，從M點到N點，由于飛行任務的過程是連續(xù)的，所以飛行路線很可能在A和B之間的菱形區(qū)域內(nèi)。

通過設(shè)置坐標函數(shù)，我們將飛行軌跡描述為

f（x）=a0sin（ω0x）+a1sin（ω1x）+…+aN-1sin（ωN-1x）（2）

為了保證所得的航線能夠肯定經(jīng)過航跡的起點和終點，將正弦波的角頻率確定為：

ω0=π/L，ωn=2ωn-1，n=1，…，N-1（3）

幅值的限制：|an|≤1λnC（4）

在這種整體范圍下，保持整體的不變性，單獨擴大基因的數(shù)量，可以得到比較理想的飛行器航跡，但是，在此情況下，卻使得總體規(guī)模的多樣性變低了，使得航跡優(yōu)化遇到瓶頸。rmin需要滿足：

2rmin<12N-1（5）

所以，在進行整體判斷或者基因選擇時，需要考慮一些其他因素，比如整體總?cè)旱亩鄻有?，以及飛行器的性能，以此達到最優(yōu)。

（二）初始化種群

種群的初始化就是依據(jù)編碼規(guī)則給出種群的初始解。算法在開始時都要進行種群的初始化，在隨機方法中，比較常用的是RNG。而定值設(shè)定法則比較偏向于在搜索空間中產(chǎn)生均勻分布的點。

（三）最優(yōu)化函數(shù)

為達到要求，獲得最優(yōu)解，必須選取合適的適應度函數(shù)，這個函數(shù)必須滿足一定的條件，其中的變量要設(shè)置好，它是所有內(nèi)容中最重要的組成部分，這個函數(shù)的構(gòu)成影響到最終結(jié)果的確定性和遺傳算法中收斂的速度。在設(shè)計這個函數(shù)的時候，要盡可能地考慮全面，而且最重要的是不要設(shè)計得太過于復雜，因為函數(shù)的復雜程度決定了遺傳算法的復雜程度，簡單點，這樣計算時間也會更少。本文使用如下代價函數(shù)：

J=∫t0（ω1C2t+ω2h2+ω3fTA）dt（6）

在一定程度上，這個公式反映了在飛行器航跡規(guī)劃上的幾個重要因素對航跡規(guī)劃的影響。

（四）選擇策略

廣義的決策策略選擇則包含判斷與決策兩個部分?；隈R爾科夫決策策略選擇方法，解決具有復雜目標間關(guān)聯(lián)的多階段目標選擇問題。使用決策策略描述目標體系各層狀態(tài)間的影響關(guān)聯(lián)，并以目標體系整體失效為求解目的，建立了基于離散時間 MDP 的多階段打擊目標選擇模型。

（五）交叉運算

將交叉算子作用于群體，在遺傳算法中，最為重要的就是交叉算子，它發(fā)揮著重要作用。

三、 改進算法

利用遺傳算法進行飛行器的航跡規(guī)劃，航跡中的每個航路點對應著染色體中的每個基因。其中，任何一個航路點都由（xi，yi）來表示。

算法中的定義和實際情況下的內(nèi)容是有一定區(qū)別的，因此在運算過程中可能會出現(xiàn)“航線回頭”“過早收斂”和“越界”等一系列的問題。為避免這種情況，以下采用改進后的算法：

（一）編碼方式

編碼的時候，對起始點和目標點默認為必須經(jīng)過的點，僅為航跡線的中間部分節(jié)點編碼。最終，才能確保任何一條航跡線都能真正的通過起止點。

（二）“航線回頭”的現(xiàn)象

為了確保沒有“航線回頭”的現(xiàn)象，在此選擇（8）方程式限定條件，這就確保了無論哪一條染色體都能相互對應起來，進行延伸下去。

xib≥xi+1，i=1，2，…，N-1（7）

在上面方程式中，N代表了染色體中的基因數(shù)量。

（三）“過早收斂”的現(xiàn)象

在進行航跡優(yōu)化的時候，可能會有還沒到達終點就在早期出現(xiàn)收斂的現(xiàn)象。在選擇上，優(yōu)化參數(shù)比較重要，參數(shù)會影響到結(jié)果，在一定情況下，選擇合適的參數(shù)會得出更好的優(yōu)化結(jié)果。

（四）“越界”的現(xiàn)象

當某航路點（xi，yi）滿足式（7）時，稱為“越界”：

xi（0，L），yi（-H，H）

i=1，2，…，N（8）

式中，L=（yN-y1）2+（xN-x1）2為航線長度；H為飛行器允許的最大偏航距離；N為每條染色體的基因數(shù)目。

（五）自然選擇

在生存斗爭中，具有有利變異的個體，容易在生存斗爭中獲勝而生存下去。反之，具有不利變異的個體，則容易在生存斗爭中失敗而死亡。這就是說，凡是生存下來的生物都是適應環(huán)境的，而被淘汰的生物都是對環(huán)境不適應的，這就是適者生存。達爾文把在生存斗爭中，適者生存、不適者被淘汰的過程叫作自然選擇。在此對剩余個體采用隨機競爭的方法進行自然選擇操作。

四、 結(jié)論

在未來，ADS-B監(jiān)視手段會慢慢普及達到全面，這種廣播式自動相關(guān)監(jiān)視系統(tǒng)會更加適用。對于目前以及將來使用ADS-B進行監(jiān)視的飛行器，相互之間知道位置等信息，使用模擬遺傳算法對飛行器的航跡進行規(guī)劃，有效利用空域資源，減少飛行器與障礙物或與其他飛行器之間的沖突。

參考文獻：

[1]Stiles P， Glickstein I. Route planning[A]. 10thDASC[C].420-425.

[2]Mahmoud Tarokh. Genetic path planning with fuzzy logic adaptation for rovers traversing rough terrain[J]. San Diego： Springer-Verlag Berlin Heidelberg 2007：215-218.

[3]何珮，屈香菊.應用自適應航跡規(guī)劃算法進行參考航跡規(guī)劃[J].航空學報，2003，24（6）：499-502.

[4]劉慧英.基于數(shù)字地圖的無人戰(zhàn)斗機低空突防軌跡規(guī)劃方法研究[D].西安：西北工業(yè)大學，2004.

[5]何珮，金長江，武哲.低空突防航跡規(guī)劃方法研究[D].北京：北京航空航天大學，2003，6.

[6]王棟.低空突防航跡規(guī)劃、航跡控制的工程實現(xiàn)[D].南京：南京航空航天大學，1999.

作者簡介：

袁小凱，男，山東淄博人，中國民用航空飛行學院碩士研究生，研究方向：空中交通管理；

傅強，男，四川廣漢人，中國民用航空飛行學院研究員，研究方向：計算機；

侯明利，女，河北唐山人，中國民用航空飛行學院碩士研究生，研究方向：空中交通管理。