遺傳算法在空域流量管理決策輔助中的應(yīng)用前景及分析

郭曉林

摘 要：文章針對(duì)民航空中交通管理專業(yè)中近年來發(fā)展迅猛的流量管理輔助決策系統(tǒng)，分析了使用遺傳算法進(jìn)行初始控制方案集合的計(jì)算的優(yōu)點(diǎn)與不足，以及使用前景。

關(guān)鍵詞：空中交通管制；空域；航路、航線；遺傳算法；流量管理

近年來，隨著民航業(yè)的快速發(fā)展，航班的迅猛增加，旅客運(yùn)營量的飛速提升，空域資源與運(yùn)營需求的矛盾凸顯?？罩薪煌ü苤?，是為了保障飛行安全和順暢而生，因此，當(dāng)其所負(fù)責(zé)的管制空域或者終端區(qū)飛機(jī)數(shù)量出現(xiàn)超過管制員指揮和保障能力時(shí)，就會(huì)出現(xiàn)高風(fēng)險(xiǎn)指數(shù)，為了保障安全和順暢，需要將這種風(fēng)險(xiǎn)控制在可接受范圍之內(nèi)，于是空域流量管理便由此而生。

大家都知道，在一個(gè)管制空域內(nèi)，同時(shí)存在與該空域內(nèi)的飛機(jī)數(shù)量，和一段時(shí)間將要進(jìn)入或退出該空域的飛機(jī)數(shù)量，決定了該管制空域在一段時(shí)間內(nèi)的壓力，當(dāng)壓力超過或者預(yù)計(jì)超過管制部門的負(fù)荷能力時(shí)，“流控”便應(yīng)運(yùn)而生，但是，如何科學(xué)地建立針對(duì)空域或者終端區(qū)流量管理方法，是近年來迫切需要解決的問題，在民航大力發(fā)展SMS系統(tǒng)建設(shè)的同時(shí)，目前有許多基于風(fēng)險(xiǎn)控制理論的空域流量管理輔助決策系統(tǒng)正在被開發(fā)，但是在確定最初的控制方案集合方面，即在求解該優(yōu)化問題最初的解集時(shí)，大部分系統(tǒng)采用了傳統(tǒng)的經(jīng)驗(yàn)數(shù)據(jù)作為初始解集使用，這對(duì)于系統(tǒng)的可擴(kuò)展性以及全局優(yōu)化的可兼容性其實(shí)非常不利。

在這里，我提出利用遺傳算法來幫助在空域流量管理決策輔助過程中，代替管制員的經(jīng)驗(yàn)數(shù)據(jù)尋找初始流量控制方案的想法。

首先，假設(shè)某管制空域，由數(shù)個(gè)終端機(jī)場(chǎng)，以及數(shù)條航路航線構(gòu)成。將這個(gè)空域的所有進(jìn)出口統(tǒng)一進(jìn)行編號(hào)，為ADCBE等5個(gè)進(jìn)出口，那么該空域?qū)?yīng)的進(jìn)口點(diǎn)5個(gè)，出口點(diǎn)5個(gè)，用小編號(hào)1表示入口，則入口有A1、B1、C1、D1、E1，同樣以小編號(hào)2表示出口，則出口有A2、B2、C2、D2、E2等5個(gè)，總共為10個(gè)進(jìn)出點(diǎn)。

當(dāng)使用風(fēng)險(xiǎn)評(píng)估來對(duì)該空域做流量管理決策時(shí)，我們通常是依靠管制員的工作經(jīng)驗(yàn)來判斷，換言之，并數(shù)據(jù)化的規(guī)則依據(jù)，一般情況下，比如上述空域，管制員是通過經(jīng)驗(yàn)提出針對(duì)上述10個(gè)進(jìn)出口點(diǎn)提出流量管理決策，到單純的減少飛機(jī)數(shù)量的目的。

利用計(jì)算機(jī)使用遺傳算法可以幫助完成這一工作，并且這項(xiàng)技術(shù)在該領(lǐng)域擁有非常寬廣的拓展空間。

作者將上述10個(gè)進(jìn)出口按照開放等級(jí)來劃分，以表示其控制程度，類似于開關(guān)效應(yīng)，通過控制所有開關(guān)的開放大小來控制整個(gè)系統(tǒng)中的壓力和流量。那么首先需要使用三位二進(jìn)制編碼來表示開關(guān)大小，從000開始，到111結(jié)束，代表著6個(gè)級(jí)別的開關(guān)范圍，從完全關(guān)閉到無限制開放。

同樣按照ABCDE的順序，將入口放在前面進(jìn)行排序，那么該空域的進(jìn)出口無限制狀態(tài)可以被二進(jìn)制碼表示為：

111 111 111 111 111 111 111 111 111 111

那么假設(shè)，目前管制空域風(fēng)險(xiǎn)壓力為P，可接受風(fēng)險(xiǎn)壓力為P0，目前已經(jīng)打算采取一定的流量控制措施，預(yù)計(jì)其各個(gè)進(jìn)出口開關(guān)的狀態(tài)為：

101 111 001 010 111 110 110 010 111 001

這組編碼，就是遺傳算法中的“數(shù)字染色體”。作者目的在于，希望通過這樣的控制方法，在一段時(shí)間內(nèi)盡可能的將P控制在P0以下。

接下來，需要?jiǎng)?chuàng)建100個(gè)（或者更多）隨機(jī)編碼組作為基因組，他們每一個(gè)，都代表著一種候選的流量控制方法。

這個(gè)集合被稱作初代基因組，而初代基因組里面，有可能包含著最好的解決方案，但有很大一部分估計(jì)是根本不可行的方案，接下來要做的工作就是選擇適應(yīng)度函數(shù)來對(duì)這個(gè)基因組的每一個(gè)染色體進(jìn)行適應(yīng)度評(píng)價(jià)，接著使用“輪盤法”來對(duì)其進(jìn)行雜交和變異操作，其流程如下：

（1）檢查每個(gè)染色體，看它的可行性如何，并相應(yīng)的為它分配一個(gè)適應(yīng)性分?jǐn)?shù)。

（2）從當(dāng)前群體中選出兩個(gè)成員，選出的概率與適應(yīng)性分?jǐn)?shù)成正比。

（3）選擇雜交率，從每個(gè)選中的染色體中的一個(gè)隨機(jī)確定的點(diǎn)上進(jìn)行雜交。

（4）按照預(yù)定的變異率，通過對(duì)被選染色體的位的循環(huán)，把相應(yīng)的位實(shí)進(jìn)行翻轉(zhuǎn)。

（5）重復(fù)2，3，4，知道100個(gè)成員的新群體被創(chuàng)建出來。

例如，系統(tǒng)隨機(jī)選出兩組編碼：

（1）101 111 001 010 111 110 110 010 111 001

（2）111 101 001 001 110 111 111 111 110 101

這里我們使用單點(diǎn)交叉法，在中間的空格位進(jìn)行雜交后，得到新的兩個(gè)編碼：

（1）101 111 001 010 111 111 111 111 110 101

（2）111 101 001 001 110 110 110 010 111 001

其中第一個(gè)按照變異概率在第4位進(jìn)行了變異，即翻轉(zhuǎn)（0和1互換）：

101 011 001 010 111 111 111 111 110 101

如果把這個(gè)編碼按照前面所述的編碼規(guī)則翻譯過來，就是新的代表10個(gè)進(jìn)出口的控制方法。

在遺傳算法的應(yīng)用中，雜交率以及變異率和適應(yīng)度函數(shù)是遺傳算法中最為重要，但也最難確定的關(guān)鍵性技術(shù)問題，到目前為止世界上還沒有快速有效的該值的確定規(guī)則，雜交率太小，系統(tǒng)將難以“向前搜索”，也就是說，系統(tǒng)需要經(jīng)歷足夠長的“進(jìn)化”過程才能得到想要的結(jié)果，而太大則會(huì)破環(huán)“適應(yīng)度”規(guī)則，變異率太小的話，難以產(chǎn)生新的基因結(jié)構(gòu)，太大會(huì)使遺傳算法編程單純的隨機(jī)搜索。在本問題中，我們通常應(yīng)該把雜交率定為0.5-0.7之間，變異率確定在0.001。而適應(yīng)度函數(shù)，如果在系統(tǒng)風(fēng)險(xiǎn)評(píng)估中，P函數(shù)使用到了包含各個(gè)空域進(jìn)出口的開關(guān)作為變量，由于該函數(shù)的值本身不可能為負(fù)，所以就可以直接使用該目標(biāo)函數(shù)作為適應(yīng)度函數(shù)。時(shí)代數(shù)應(yīng)選在100至500之間，當(dāng)個(gè)體的適應(yīng)度不再上升時(shí)，算法的迭代過程收斂，循環(huán)結(jié)束，否則，用經(jīng)過選擇、交叉、變異的新一代群體取代上一代群體并返回到第1步即繼續(xù)執(zhí)行。

通常情況下，我們可以使用C++編程或者在MATLAB上進(jìn)行實(shí)驗(yàn)來完成上述計(jì)算過程，然后將最后得到一組二進(jìn)制編碼，按照前面所述的編碼規(guī)則，翻譯成為各進(jìn)出口開關(guān)的流量控制等級(jí)。

但是需要注意的是，這只是滿足條件的一個(gè)方法，并不是最優(yōu)的流量管理辦法，我們可以得到這樣一個(gè)符合條件的初始解集，然后再將其用于流量管理輔助決策系統(tǒng)進(jìn)行后續(xù)的優(yōu)化工作，例如結(jié)合其它的優(yōu)化系統(tǒng)，結(jié)合空域和航線氣象條件，主干道航路航線與支線的影響權(quán)重，起飛、目的地機(jī)場(chǎng)權(quán)重等等影響因素，對(duì)上述初始解集再次優(yōu)化和選擇，這樣，可以避免因?yàn)槭褂萌藶榈慕?jīng)驗(yàn)數(shù)據(jù)作為初始解集的誤差，以及局限性，提高系統(tǒng)的智能化程度，以及可擴(kuò)展性，并達(dá)到充分節(jié)約人力的目的，幫助流量管理輔助決策系統(tǒng)更加智能化的完成任務(wù)，并且，在大范圍內(nèi)使用同系統(tǒng)的輔助決策系統(tǒng)時(shí)，用遺傳算法得到各個(gè)管制空域初始流量管理解集將為大范圍內(nèi)的航班的全局優(yōu)化提供統(tǒng)一的初始數(shù)據(jù)平臺(tái)，更加科學(xué)有效地減少航班延誤以及避免在某一管制地帶出現(xiàn)過分擁堵的情況，也為我們個(gè)更好的優(yōu)化航路和航線結(jié)構(gòu)提供了數(shù)據(jù)支持。

參考文獻(xiàn)

[1]徐淑坦，孫亮，孫延風(fēng)，關(guān)于遺傳算法模式定理的進(jìn)一步探討[J].吉林大學(xué)學(xué)報(bào)（信息科學(xué)版），2009.

[2]周明，孫樹棟.遺傳算法原理及應(yīng)用[J].國防工業(yè)出版社，2002.

[3]Z.米凱利維茨[美].周家駒，何險(xiǎn)峰譯.演化程序-遺傳算法和數(shù)據(jù)編碼的結(jié)合[M].科學(xué)出版社，2000.endprint