吳君，張京娟

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

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

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

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

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

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

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

1.1 模型簡(jiǎn)化

根據(jù)國(guó)家空管安全規(guī)定和實(shí)際飛行操控的具體情況，在研究過程中將對(duì)實(shí)際問題做如下簡(jiǎn)化.

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

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

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

根據(jù)我國(guó)空管安全規(guī)定［8］，雷達(dá)管制條件下巡航階段2架航班之間的間隔大于等于20 km時(shí)，不存在飛行沖突.那么在仿真分析區(qū)域內(nèi)，算法中飛機(jī)以步長(zhǎng)10 km的間隔前進(jìn).在任何時(shí)刻當(dāng)2架飛機(jī)間的距離小于20 km時(shí)，即認(rèn)為有沖突的可能，需要采取措施以避免沖突.

1.2 改變航向沖突解脫策略

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

根據(jù)算法流程，具體實(shí)現(xiàn)途徑如下.

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

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

式中:Si為一架飛機(jī)從進(jìn)入?yún)^(qū)域到離開區(qū)域的總飛行距離.

同時(shí)，應(yīng)該保證區(qū)域內(nèi)的所有飛機(jī)間的距離滿足國(guó)家空管安全規(guī)定，即

式中:(xi，xj)、(yi，yj)為區(qū)域內(nèi)任意2架飛機(jī)的坐標(biāo).

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

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

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

圖2 隨機(jī)遍歷選擇法Fig.2 Stochastic universal sampling method

這樣，通過計(jì)算各個(gè)體的適應(yīng)值，飛行距離短的個(gè)體具有較大的適應(yīng)值，在圖2的軸上占有距離較長(zhǎng)，更容易被選中進(jìn)入下一代計(jì)算.

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

5)遺傳算法的終止.設(shè)定遺傳算法運(yùn)行代數(shù)為1 000代，并且設(shè)定如果連續(xù)30代運(yùn)算結(jié)果變化范圍小于0.000 001，則算法結(jié)束.如果1 000代內(nèi)沒有符合條件的結(jié)果則算法也相應(yīng)停止，需要進(jìn)行一些參數(shù)調(diào)整或重新啟動(dòng).

1.2.2 仿真及結(jié)果

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

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

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

為考察算法性能，給出三機(jī)沖突解脫的相關(guān)實(shí)驗(yàn)結(jié)果，如圖4所示.可以看出初始種群仍能保證算法的多樣性，且算法收斂性較好，最終可以收斂到一個(gè)最優(yōu)解.

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

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

1.3 改變速度沖突解脫策略

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

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

根據(jù)我國(guó)空管安全規(guī)定和實(shí)際飛行情況，對(duì)實(shí)際情況做如下簡(jiǎn)化.

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

2)為了保證飛機(jī)按照規(guī)定時(shí)間到達(dá)目的地，不會(huì)因?yàn)榧铀亠w行而提前到達(dá)，也不會(huì)因?yàn)榻档退俣榷七t到達(dá)時(shí)間，假設(shè)飛機(jī)在整個(gè)飛行過程中既有加速過程也有減速過程.

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

4)仍假設(shè)飛機(jī)以步長(zhǎng)為10 km，在任何時(shí)刻當(dāng)2架飛機(jī)間的距離小于20 km時(shí)，即認(rèn)為有沖突的可能，需要調(diào)整速度來避免沖突.

算法流程和改變航向策略相似，具體實(shí)現(xiàn)途徑如下.

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

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

式中:Si為飛機(jī)當(dāng)前時(shí)刻位置和不變速時(shí)理論位置之間的距離.

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

1.3.2 仿真及結(jié)果

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

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

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

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

上述實(shí)驗(yàn)結(jié)果表明，所設(shè)計(jì)的算法具有較好的性能，無論是改變航向策略還是改變速度策略，對(duì)于兩機(jī)和三機(jī)沖突解脫，算法都有著良好的表現(xiàn).

2 結(jié)束語

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

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

［2］程麗媛.自由飛行沖突探測(cè)與解脫技術(shù)的國(guó)內(nèi)外發(fā)展和研究現(xiàn)狀［J］.中國(guó)民航飛行學(xué)院學(xué)報(bào)，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］周明，孫樹棟.遺傳算法原理及應(yīng)用［M］.北京:國(guó)防工業(yè)出版社，1999:2-3.

［5］楊尚文，戴福青.基于一種免疫遺傳算法的自由飛行沖突解脫［J］.航空計(jì)算技術(shù)，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］劉星，胡明華，董襄寧.遺傳算法在飛行沖突探測(cè)解脫中的應(yīng)用［J］.南京航空航天大學(xué)學(xué)報(bào)，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ìn)的遺傳算法在飛行沖突解脫中的應(yīng)用［J］.電子測(cè)量技術(shù)，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］.中國(guó)民航大學(xué)學(xué)報(bào)，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］.通訊和計(jì)算機(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.