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

袁小凱 傅強 侯明利

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

關鍵詞：遺傳算法；ADS-B；飛行航跡

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

一、 引言

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

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

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

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

二、 進行航跡規劃

（一）編碼

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

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

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

通過設置坐標函數，我們將飛行軌跡描述為

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

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

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

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

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

2rmin<12N-1（5）

所以，在進行整體判斷或者基因選擇時，需要考慮一些其他因素，比如整體總群的多樣性，以及飛行器的性能，以此達到最優。

（二）初始化種群

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

（三）最優化函數

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

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

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

（四）選擇策略

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

（五）交叉運算

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

三、 改進算法

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

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

（一）編碼方式

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

（二）“航線回頭”的現象

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

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

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

（三）“過早收斂”的現象

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

（四）“越界”的現象

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

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

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

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

（五）自然選擇

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

四、 結論

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

參考文獻：

[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]何珮，屈香菊.應用自適應航跡規劃算法進行參考航跡規劃[J].航空學報，2003，24（6）：499-502.

[4]劉慧英.基于數字地圖的無人戰斗機低空突防軌跡規劃方法研究[D].西安：西北工業大學，2004.

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

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

作者簡介：

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

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

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