遺傳算法在多機飛行沖突解脫中的應用

姚成， 林琳， 李妮鍶

(中國民用航空飛行學院， 民航飛行技術與飛行安全科研基地， 四川， 廣漢 618300)

0 引言

隨著航空運輸業的快速發展，飛機數量的不斷增加導致空中交通變得越來越擁擠，給飛行安全提出了新的挑戰。為了應對這一問題，國外學者提出了“自由飛行”的概念，即飛行員根據實際飛行狀況采取措施利用剩下的還未開發的空域飛行，打破了固定航路的限制，能夠有效地緩解空域擁擠帶來的壓力[1]。飛行數量的增加和自由飛行路線的多向性勢必會增加飛行沖突的可能性，特別是在可用高度層有限而飛行流量又十分密集的低空空域。所以研究飛行沖突解脫的方法將是決定自由飛行技術能否實現的必不可少的一項關鍵技術[2]。

沖突解脫的主要目的是避免發生飛行沖突，即當探測到兩架或多架飛機之間按照當前狀態飛行將會發生沖突事件時，及時地規劃出一條能夠避免沖突發生的理想路徑。近年來，在沖突解脫方面國內外學者嘗試了很多的智能優化算法，如人工勢場法、蟻群算法、神經網絡算法等，但都有各自的局限性。人工勢場法在缺乏全局信息時容易陷入局部最優值問題，無法得到最優解。蟻群算法雖然搜索能力很好但是在算法的初期收斂速度較慢。神經網絡法有很強的學習能力，但其神經元的閾值需要隨時間的改變而不斷改變，并且在約束較多時網絡結構龐大，計算效率較低[3]。

遺傳算法作為一種新的全局優化搜索算法[4]，利用其簡單通用，搜索能力強以及易與其他算法結合的可擴展性等特點廣泛應用于諸多領域。在飛行沖突解脫的問題上，國內外學者應用遺傳算法對此均有一定的研究，但大多局限在研究兩機情況。本文在符合我國民航相關安全規定的前提下，參考了國內外的有關資料，對基于遺傳算法通過改變飛行航向對兩機以及多機間的飛行沖突解脫問題進行了一定的研究。

1 遺傳算法原理與實現

遺傳算法最早是由美國教授 John holland于20世紀七十年代根據生物體進化規律在其著作《自然界和人工系統的適應性》中提出來的[5]。它是一種通過模擬自然進化過程的隨機搜索算法。將求解的實際問題的解編碼成二進制的染色體基因，求解過程相應地轉換成類似生物遺傳學中的基因的選擇、交叉、變異等過程，最后再解碼得到問題的最優解或近似最優解。其中，自然選擇根據適應值的大小來確定選擇到下一代的概率，適應值由適應度函數確定，選擇的目的是為了使種群盡可能地保留適應值大的染色體，使子代向著最優解的方向進化；交叉是將父代中的2個染色體以某種方式重新組合成產生2個新的染色體，交叉操作大大地提高了算法的搜索能力；變異指通過改變父代染色體中的某些基因位點的值，在子代種群中生成異于父代的新染色體，使得種群得以進化更新。本文遺傳算法流程圖如圖1所示。

圖1 遺傳算法流程圖

根據建立的模型和確定的編碼方法，本文遺傳算法實現的步驟如下。

選擇：本文通過隨機輪盤賭方式使在遺傳過程中優秀個體被淘汰的情況得以有效避免[6]。如圖2所示，轉動輪盤，適應度越大的個體，被選中保留到下一代的可能性越高，對適應度最大的染色體直接繼承。每次選擇操作后將淘汰一部分個體，為了保持群體的總數不變，將隨機生成新的個體對被淘汰后的個體進行補充。

圖2 輪盤賭選擇

交叉：遺傳算法的交叉操作是指以某種方式在父代群體中的2個配對的染色體之間交換部分基因進化成新的子代，實現種群的更新換代。本文采用的單點交叉方式，即染色體依次兩兩配對，隨機在一對染色體上選取一點分成兩段，然后互換重組為新的2條染色體。最為理想的交叉策略是只選取種群中適應度較高的染色體進行交叉操作，并且在交叉后原染色體依舊保留到子代種群中。表1是8位二進制數的染色體上以第5位為交叉點為例的交叉示意圖。

表1 交叉示意圖

變異：在染色體上隨機選取一位，其二進制值反轉，在自然界中變異的概率極低，在本文設置的參數也較小。

算法的終止：設定遺傳算法運行代數為2 000代，并且設定如果連續500代運算結果的適應度大小無變化，則算法結束，如果2 000代內沒有符合條件的結果則算法也相應停止，需要進行一些參數調整或重新啟動。

2 模型的建立

根據國家空管的安全規定以及工程應用的實用性，在本文的研究中將沖突問題做如下簡化[7]。

(1)在正常的巡航階段，飛機的實際飛行情況都是在固定的高度層飛行，加之考慮到需要滿足旅客乘坐舒適度的要求，故當飛行沖突將要發生時不考慮調整高度層實現沖突解脫，而只是在水平面做出調整，將三維空間問題的沖突解脫簡化為二維平面的沖突解脫問題進行處理以簡化模型[8-9]。

(2)為了不影響飛機到達目的地的時間，設定飛機在偏離原始航向時的速度大小隨著偏航角度大小的變化而變化，始終保持飛機在原始航向上的分速度大小不變。

(3)根據民航局相關安全規定，飛機之間間隔距離大于20 km時不存在飛行沖突[10]。本文采用10 km為步長作為沖突探測計算點，沖突區域設定在邊長為200 km的正方形區域內。

(4)在正常的巡航階段，在滿足旅客乘坐舒適度要求的前提下，民航飛機不存在大幅度轉彎或者轉向操作。本文的飛行方向可設定為左、右偏航30°以及保持原航向。

2.1 遺傳算法編碼方式的確定

采用二進制編碼，編碼方案如表2所示。

表2 編碼方案

為了提高沖突識別的準確性，采用原始航向上10 km為步長作為沖突探測計算點，這樣任意一架進入沖突區域的飛機在沖突區域內總的飛行時間分為20步。在進入每一步之后，飛機的航向能做出調整，其二進制編碼表示的含義如表1所示，2位二進制數可以表示4個變量，可以對3個航向角度進行編碼。由于總的飛行時間被分為 20步，單架飛機在沖突區域的所有航向的變化能被編譯為40位長度的染色體。n架飛機所有的航向改變將被編譯為40×n位長度的染色體。

2.2 目標函數與約束條件的確定

假設有n架飛機進入沖突區域，在從經濟成本的角度看，希望飛機在不發生沖突的情況下沿著最短的路徑飛行即

(1)

式中，si為1架飛機在沖突區域內的總飛行距離。同時還應該保證區域內的所有飛機在任意時刻的距離大于安全距離，本文為簡化計算，以10 km為步長作為一個計算點需滿足

(2)

式中，(xi,yi)，(xj,yj)為任意2架飛機在同一計算點的坐標。迭代過程中總是向著適應度增大的方向進行，適應度函數公式如下[11]，

(3)

式中，di為規劃路徑離開點與原航跡終點之間的距離，k為常量，a的初始值為1，在迭代過程中遇到對不滿足安全距離的染色體令a等于0，達到對不滿足約束的染色體適應值置零的目的，使其在接下來的迭代中不易被選中[12]。

3 仿真結果與分析

實驗平臺：系統Windows10，CPU為1.6 GHz，內存為16 GB，編程語言為Java，開發工具為IDEA2019.3.3，仿真參數的設置如表3所示。

表3 仿真參數的選取

考慮到運行時間以及搜索速度，初步決定設定種群大迭代次數少或者種群小迭代次數多，仿真結果表明，種群大小超過100時，運行時間較慢，超過1 min，并且收斂效果也不好。而設定種群小迭代次數多的參數時，運行較快，通常在20 s內，收斂效果也較好。故種群大小設置為20～100，迭代次數為2 000。

交叉概率：為了擴大搜索范圍，避免出現局部最優解[13]，也參考了其他相關文獻，交叉概率設置的值較大，為0.6～0.9。

變異概率：在自然界中變異的概率極低，在本文設置的參數也較小。設置大小為0.01～0.1。

安全距離由民航局相關安全規定設定。

實例1：兩架航向分別為自西向東和自南向北飛機以相同速度在同一時刻從各自起點進入沖突區域，根據空管相關規定，兩機的安全距離設定為20 km，以原始航向上每10公里步長為一個計算點，在第10步時相遇，為避免發生沖突，采用遺傳算法對沖突進行解脫，圖3為兩架飛機的沖突解脫過程，分別為原始航跡、迭代終止時種群航跡以及最佳解脫航跡，結果表明，對于雙機沖突，該算法可以通過改變飛行航向快速有效地得出最優沖突解脫路徑。

圖3 2架飛機的沖突解脫過程

實例2：為了驗證本文提出來的遺傳算法的有效性，在上述實例1的基礎上增加一架由西南方向飛向東北方向的飛機，建立3架飛機沖突解脫的模型，3架飛機以相同速度同時從各自起點進入沖突區域。各個沖突之間相互制約，由原始航跡可以看出3架飛機仍將在第10步相遇。圖4為3架飛機的沖突解脫過程。結果表明，對于三機沖突，該算法也同樣能得出最優沖突解脫路徑。

圖4 3架飛機的沖突解脫過程

實例3：為了進一步驗證本文提出來的遺傳算法的有效性與適應性，在實例2的基礎上再增加一架由西北方向飛行東南方向的飛機，建立4架飛機沖突解脫的模型，4架飛機以相同速度同時從各自起點進入沖突區，由原始航跡可以看出4架飛機也將在第10步相遇。圖5給出了4架飛機的沖突解脫過程，從第三個小圖即解脫航跡圖中可以看出隨著飛機數量的增加，遺傳算法雖然能實現解脫，但解脫后的在沖突區域內的航跡終點未與原始航跡終點重合，未能使解脫航跡都從原始航跡的終點退出沖突區域。當飛機數量較少時(雙機或者三機)則不存在這一缺陷，解脫后的航跡終點均能與原始航跡終點重合，因此算法仍有優化和改進的空間。

圖5 4架飛機的沖突解脫過程

4 總結

本文對遺傳算法進行了深入的研究并將遺傳算法應用于民航飛行沖突解脫的問題中，仿真結果表明，對于雙機和三機的沖突解脫問題，本文提出的算法均能通過改變飛行航向快速有效地得出最優沖突解脫路徑。但是隨著飛機數量的進一步增加，此算法仍存在一定的局限性，雖然能實現解脫，但未能使所有航線都從原始航跡的終點退出沖突區域，后續將考慮提出與其他優化算法相結合的混合算法優化改進存在的缺陷，這還有待進一步研究。