采用遺傳算法的多機自由飛行沖突解脫策略

吳君，張京娟

(北京航空航天大學儀器科學與光電工程學院，北京100191)

隨著航空運輸需求量的不斷增長，空中交通面臨著越來越嚴重的航線擁擠，給現有的交通管制系統帶來前所未有的壓力.在現行空中交通管制模式下［1-2］，民航飛機都是遵照地基導航系統所限定的由無線電信標建立起來的航線安排航班的，飛機必須沿著由一系列導航臺組成的固定航路進行飛行.由于這些設施不是在任何地方都建立的，因而飛機不能選取通往目的地的最直接路線，這導致航路交通日益擁擠，空域整體利用率不高.對于這種狀況，“自由飛行”是一個有效的解決辦法.

然而，飛行數量的增加和自由飛行路線的多向性必然增加了飛行沖突的可能性.尤其是低空空域飛行流量密集，可用高度層有限，所以研究飛行沖突檢測與解脫方法和技術的發展都至關重要，并且將是影響自由飛行能否實現的一項關鍵技術［3］.

遺傳算法作為一種新的全局優化搜索算法［4］，以其簡單通用、魯棒性強、適合并行處理及應用范圍廣等顯著特點，奠定了它作為21世紀關鍵智能計算之一的地位.國內應用遺傳算法解決沖突解脫問題已經取得了一定的進展，但大多局限在研究兩機情況和變航向的方法［5-6］.本文應用遺傳算法解決了兩機及多機間通過改變飛行速度和方向的沖突解脫問題.

1 基于遺傳算法的沖突解脫算法

遺傳算法是模擬生物在自然環境中的遺傳和進化過程形成的一種全局優化概率搜索算法，它反復通過選擇、交叉和變異等操作算子作用于整個進化群體，最終得到問題的最優解或近似最優解［7］.圖1所示為遺傳算法的基本流程圖.

圖1 遺傳算法基本流程Fig.1 Basic flow chart of the genetic algorithm

1.1 模型簡化

根據國家空管安全規定和實際飛行操控的具體情況，在研究過程中將對實際問題做如下簡化.

1)飛機在飛行過程中，除了起飛和降落階段，考慮到旅客的舒適和節約燃料，都是定高飛行，所以將問題簡化為二維平面的沖突解脫問題.

2)考慮到飛機實際飛行過程中不會做太大角度的變航向飛行，假設飛機能選擇的飛行航向改變范圍為［－35°，35°］.為求得最優飛行路徑，將此變化范圍均勻地劃分成若干份.

3)為了保證飛機按時到達目的地，假設飛機在所飛方向上的分速度不變，飛機偏航時偏航方向上的速度分量隨偏航角度大小變化.

根據我國空管安全規定［8］，雷達管制條件下巡航階段2架航班之間的間隔大于等于20 km時，不存在飛行沖突.那么在仿真分析區域內，算法中飛機以步長10 km的間隔前進.在任何時刻當2架飛機間的距離小于20 km時，即認為有沖突的可能，需要采取措施以避免沖突.

1.2 改變航向沖突解脫策略

1.2.1 改變航向沖突解脫算法方案

根據算法流程，具體實現途徑如下.

1)編碼方式.采用二進制編碼，用6位二進制編碼表示［－35°，35°］的偏航角，N 為飛機的數量，這樣就需要6N位二進制數來表示偏航角.

2)目標函數和約束條件的確定.從燃料消耗角度看，希望飛機在不發生沖突的情況下沿最短路徑飛行，即

式中:Si為一架飛機從進入區域到離開區域的總飛行距離.

同時，應該保證區域內的所有飛機間的距離滿足國家空管安全規定，即

式中:(xi，xj)、(yi，yj)為區域內任意2架飛機的坐標.

對于不滿足安全距離的飛行路徑，采用懲罰函數的方法使其不易進入下一代的計算中，即

式中:∑Si為飛機的飛行路徑長度，m為比例系數，d－di為2架飛機間最小安全距離與實際距離的差值.這樣不滿足最小安全距離的飛行路徑總飛行長度比滿足最小安全距離的總飛行長度大，在以后的選擇過程中就不易被選中.

3)選擇采用隨機遍歷選擇法［9］，如圖2所示，設NV為需要選擇的個體數目，等距離地選擇個體，選擇指針的距離是1/NV，第1個指針的位置由［0，1/NV］的均勻隨機數決定.

圖2 隨機遍歷選擇法Fig.2 Stochastic universal sampling method

這樣，通過計算各個體的適應值，飛行距離短的個體具有較大的適應值，在圖2的軸上占有距離較長，更容易被選中進入下一代計算.

4)交叉和變異.采用單點交叉算子，即在個體編碼串中只隨機設置一個交叉點，然后在該點相互交換部分基因.采用離散變異算子，用特定概率(變異率取為0.02)對當前種群中某個元素進行變異，也就改變飛機在這點的偏航角度.

5)遺傳算法的終止.設定遺傳算法運行代數為1 000代，并且設定如果連續30代運算結果變化范圍小于0.000 001，則算法結束.如果1 000代內沒有符合條件的結果則算法也相應停止，需要進行一些參數調整或重新啟動.

1.2.2 仿真及結果

仿真參數設置如下:2架飛機一架自西向東飛行，另一架飛機自南向北飛行;飛行距離為90 km，兩機間的安全距離為20 km;代溝為0.7，即在每次的選擇過程中將父代中70%的較優個體遺傳到下一代，變異率0.02，交叉率0.7;種群規模設置為600，最大迭代次數為1 000次，同時當連續相鄰30代種群變化幅度小于0.000 001時，即認為此時的解為近似最優解，算法終止.圖3給出了一次遺傳算法的仿真過程.可以看出，生成的初始種群包含了設置的整個算法空間，保證了初始種群的多樣性.隨著算法的進行，那些偏離最優解較大的個體已經被淘汰掉，保留下來的個體均為距最優解較近的個體.算法在第214代得出了最優解，2條飛行路徑不僅不存在沖突情況，也保證了最短飛行距離.

圖3 2機沖突解脫仿真過程Fig.3 The diagrams of 2 airplanes procedure

圖4 3機沖突解脫仿真過程Fig.4 The diagrams of 3 airplanes procedure

為考察算法性能，給出三機沖突解脫的相關實驗結果，如圖4所示.可以看出初始種群仍能保證算法的多樣性，且算法收斂性較好，最終可以收斂到一個最優解.

再通過觀察圖5所示六機沖突解脫的相關結果，發現在改變航向的沖突解脫算法中，各飛機都朝著各自相同方向改變，如果面臨沖突問題的飛機架次較少時還可以通過協商改變航方向進行解脫，但是當架次較多時再臨時協調解脫方案就會引起很大的混亂.因此在今后的沖突解脫規則中建立起相應“左行”或者“右行”機制的空中“交通規則”，規范面臨沖突問題時飛機的解脫方案將會給實際沖突解脫問題帶來極大的便利，這對今后實際飛行具有一定參考意義.

圖5 六機沖突解脫仿真過程Fig.5 The diagrams of 3 airplanes procedure

1.3 改變速度沖突解脫策略

1.3.1 改變速度沖突解脫算法方案

上述算法模型是當有潛在飛行沖突時，執行改變飛行航向的策略取得的結果，為了提供更加充實的理論參考，下面研究采用改變飛行速度策略的情況.

根據我國空管安全規定和實際飛行情況，對實際情況做如下簡化.

1)仍然將問題簡化為二維平面的飛行沖突解脫問題.

2)為了保證飛機按照規定時間到達目的地，不會因為加速飛行而提前到達，也不會因為降低速度而推遲到達時間，假設飛機在整個飛行過程中既有加速過程也有減速過程.

3)考慮到飛機實際飛行過程中不能太大地改變飛行速度，假設飛機的飛行速度變化范圍為加速或減速為正常飛行速度的50%，即可以將正常飛行速度的50%～150%的范圍劃分為若干份.

4)仍假設飛機以步長為10 km，在任何時刻當2架飛機間的距離小于20 km時，即認為有沖突的可能，需要調整速度來避免沖突.

算法流程和改變航向策略相似，具體實現途徑如下.

1)選擇編碼方式.采用二進制編碼，用6位二進制編碼表示正常飛行速度的50%～150%的速度變化，N為飛機的數量，這樣就需要6N位二進制數來表示速度變化大小.

2)目標函數的確定.從燃料消耗角度和旅客舒適度來看，總是希望飛機在不發生沖突的情況下盡可能少地變速，即

式中:Si為飛機當前時刻位置和不變速時理論位置之間的距離.

3)其余條件和改變航向策略相同.

1.3.2 仿真及結果

圖6為算法一次執行結束時得出的最優解，可以看出算法在第308代收斂得出了最優解，自西向東的飛機先減速再加速，而自南向北的飛機先加速再減速，2架飛機通過改變飛行速度不僅避免了相互間的沖突情況，也保證了總體的最優飛行路線.

圖7為算法一次運行結束時得出的最優解，可以看出在第518代時收斂，自西向東的飛機先加速再減速，而自東南向西北的飛機先減速再加速，自西南向東北飛行的飛機速度變化較小.然而發現一個問題就是僅靠改變速度策略對于兩機沖突具有較好的解脫效果，無外乎其中一架飛機加速另一架飛機減速，這很好理解.但是當3架飛機沖突時就發現一架飛機加速一架飛機減速，另一架飛機要么超前要么略晚點到達.本仿真中自西南向東北飛行的飛機就是提前1個時刻到達了目的地.要不然速度改變量的幅度大一些，才能確保另一架飛機也能按時到達.

圖6 第308代Fig.6 The 308th generation

圖7 第518代Fig.7 The 518th generation

上述實驗結果表明，所設計的算法具有較好的性能，無論是改變航向策略還是改變速度策略，對于兩機和三機沖突解脫，算法都有著良好的表現.

2 結束語

本文基于遺傳算法的沖突解脫問題進行了深入研究，在研究兩機沖突解脫的基礎上進一步研究了多機的沖突解脫方法，通過大量的仿真，驗證了所提出的改變飛行航向和飛行速度的策略都可以實現有效沖突解脫.通過仿真結果也可以看出，采用改變速度的解脫策略在處理多機沖突問題時具有一定的局限性，而采用改變航向的方法具有更好的適用性，同時還討論了多機沖突解脫時相應的飛行機制問題.這些結果為自由飛行和空管自動化系統的研究提供了重要的理論參考.另外，文中僅對2種解脫方法分別進行了研究，并未討論這2種方法結合的解脫策略，這有待進一步研究.

［1］張軍.現代空中交通管理［M］.北京:北京航空航天大學出版社，2003:17-33.

［2］程麗媛.自由飛行沖突探測與解脫技術的國內外發展和研究現狀［J］.中國民航飛行學院學報，2007，39(5):21-23.CHENG Liyuan.The development and research of free flight conflict detection and resolution technology at home and abroad［J］.Journal of Civil Aviation Flight University of China，2007，39(5):21-23.

［3］KUCHAR J K，YANG L C.A review of conflict detection and resolution modeling methods［J］.IEEE Transactions on Intelligent Transportation Systems，2000，1(4):179-189.

［4］周明，孫樹棟.遺傳算法原理及應用［M］.北京:國防工業出版社，1999:2-3.

［5］楊尚文，戴福青.基于一種免疫遺傳算法的自由飛行沖突解脫［J］.航空計算技術，2007，37(1):41-43.YANG Shangwen，DAI Fuqing.Conflict resolution in free flight based on an immune genetic algorithm［J］.Aeronautical Computing Technique，2007，37(1):41-43.

［6］劉星，胡明華，董襄寧.遺傳算法在飛行沖突探測解脫中的應用［J］.南京航空航天大學學報，2002，34(1):36-39.LIU Xing，HU Minghua，DONG Xiangning.Application of genetic algorithms for solving flight conflicts［J］.Journal of Nanjing University of Aeronautics ＆ Astronautics，2002，34(1):36-39.

［7］趙榮，張京娟.改進的遺傳算法在飛行沖突解脫中的應用［J］.電子測量技術，2009，32(11):37-39.ZHAO Rong，ZHANG Jingjuan.Conflict resolution based on an improved genetic algorithm［J］.Electronic Measurement Technology，2009，32(11):37-39.

［8］王潔寧，袁志娟.基于粒子群算法的飛行沖突解脫問題［J］.中國民航大學學報，2010，28(4):1-4.WANG Jiening，YUAN Zhijuan.Study on resolution of flight conflicts based on particle swarm optimization［J］.Journal of Civil Aviation University of China，2010，28(4):1-4.

［9］魏全新，劉賢鋒，黃鏘，等.遺傳算法選擇方法的比較分析［J］.通訊和計算機，2008，5(8):61-65.WEI Quanxin，LIU Xianfeng，HUANG Qiang，et al.The comparison of different selection methods in genetic algorithms［J］.Journal of Communication and Computer，2008，5(8):61-65.