遺傳算法在多機(jī)飛行沖突解脫中的應(yīng)用

姚成， 林琳， 李妮鍶

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

0 引言

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

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

遺傳算法作為一種新的全局優(yōu)化搜索算法[4]，利用其簡(jiǎn)單通用，搜索能力強(qiáng)以及易與其他算法結(jié)合的可擴(kuò)展性等特點(diǎn)廣泛應(yīng)用于諸多領(lǐng)域。在飛行沖突解脫的問(wèn)題上，國(guó)內(nèi)外學(xué)者應(yīng)用遺傳算法對(duì)此均有一定的研究，但大多局限在研究?jī)蓹C(jī)情況。本文在符合我國(guó)民航相關(guān)安全規(guī)定的前提下，參考了國(guó)內(nèi)外的有關(guān)資料，對(duì)基于遺傳算法通過(guò)改變飛行航向?qū)蓹C(jī)以及多機(jī)間的飛行沖突解脫問(wèn)題進(jìn)行了一定的研究。

1 遺傳算法原理與實(shí)現(xiàn)

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

圖1 遺傳算法流程圖

根據(jù)建立的模型和確定的編碼方法，本文遺傳算法實(shí)現(xiàn)的步驟如下。

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

圖2 輪盤賭選擇

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

表1 交叉示意圖

變異：在染色體上隨機(jī)選取一位，其二進(jìn)制值反轉(zhuǎn)，在自然界中變異的概率極低，在本文設(shè)置的參數(shù)也較小。

算法的終止：設(shè)定遺傳算法運(yùn)行代數(shù)為2 000代，并且設(shè)定如果連續(xù)500代運(yùn)算結(jié)果的適應(yīng)度大小無(wú)變化，則算法結(jié)束，如果2 000代內(nèi)沒(méi)有符合條件的結(jié)果則算法也相應(yīng)停止，需要進(jìn)行一些參數(shù)調(diào)整或重新啟動(dòng)。

2 模型的建立

根據(jù)國(guó)家空管的安全規(guī)定以及工程應(yīng)用的實(shí)用性，在本文的研究中將沖突問(wèn)題做如下簡(jiǎn)化[7]。

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

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

(3)根據(jù)民航局相關(guān)安全規(guī)定，飛機(jī)之間間隔距離大于20 km時(shí)不存在飛行沖突[10]。本文采用10 km為步長(zhǎng)作為沖突探測(cè)計(jì)算點(diǎn)，沖突區(qū)域設(shè)定在邊長(zhǎng)為200 km的正方形區(qū)域內(nèi)。

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

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

采用二進(jìn)制編碼，編碼方案如表2所示。

表2 編碼方案

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

2.2 目標(biāo)函數(shù)與約束條件的確定

假設(shè)有n架飛機(jī)進(jìn)入沖突區(qū)域，在從經(jīng)濟(jì)成本的角度看，希望飛機(jī)在不發(fā)生沖突的情況下沿著最短的路徑飛行即

(1)

式中，si為1架飛機(jī)在沖突區(qū)域內(nèi)的總飛行距離。同時(shí)還應(yīng)該保證區(qū)域內(nèi)的所有飛機(jī)在任意時(shí)刻的距離大于安全距離，本文為簡(jiǎn)化計(jì)算，以10 km為步長(zhǎng)作為一個(gè)計(jì)算點(diǎn)需滿足

(2)

式中，(xi,yi)，(xj,yj)為任意2架飛機(jī)在同一計(jì)算點(diǎn)的坐標(biāo)。迭代過(guò)程中總是向著適應(yīng)度增大的方向進(jìn)行，適應(yīng)度函數(shù)公式如下[11]，

(3)

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

3 仿真結(jié)果與分析

實(shí)驗(yàn)平臺(tái)：系統(tǒng)Windows10，CPU為1.6 GHz，內(nèi)存為16 GB，編程語(yǔ)言為Java，開發(fā)工具為IDEA2019.3.3，仿真參數(shù)的設(shè)置如表3所示。

表3 仿真參數(shù)的選取

考慮到運(yùn)行時(shí)間以及搜索速度，初步?jīng)Q定設(shè)定種群大迭代次數(shù)少或者種群小迭代次數(shù)多，仿真結(jié)果表明，種群大小超過(guò)100時(shí)，運(yùn)行時(shí)間較慢，超過(guò)1 min，并且收斂效果也不好。而設(shè)定種群小迭代次數(shù)多的參數(shù)時(shí)，運(yùn)行較快，通常在20 s內(nèi)，收斂效果也較好。故種群大小設(shè)置為20～100，迭代次數(shù)為2 000。

交叉概率：為了擴(kuò)大搜索范圍，避免出現(xiàn)局部最優(yōu)解[13]，也參考了其他相關(guān)文獻(xiàn)，交叉概率設(shè)置的值較大，為0.6～0.9。

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

安全距離由民航局相關(guān)安全規(guī)定設(shè)定。

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

圖3 2架飛機(jī)的沖突解脫過(guò)程

實(shí)例2：為了驗(yàn)證本文提出來(lái)的遺傳算法的有效性，在上述實(shí)例1的基礎(chǔ)上增加一架由西南方向飛向東北方向的飛機(jī)，建立3架飛機(jī)沖突解脫的模型，3架飛機(jī)以相同速度同時(shí)從各自起點(diǎn)進(jìn)入沖突區(qū)域。各個(gè)沖突之間相互制約，由原始航跡可以看出3架飛機(jī)仍將在第10步相遇。圖4為3架飛機(jī)的沖突解脫過(guò)程。結(jié)果表明，對(duì)于三機(jī)沖突，該算法也同樣能得出最優(yōu)沖突解脫路徑。

圖4 3架飛機(jī)的沖突解脫過(guò)程

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

圖5 4架飛機(jī)的沖突解脫過(guò)程

4 總結(jié)

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