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

郭曉林

摘 要：文章針對民航空中交通管理專業中近年來發展迅猛的流量管理輔助決策系統，分析了使用遺傳算法進行初始控制方案集合的計算的優點與不足，以及使用前景。

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

近年來，隨著民航業的快速發展，航班的迅猛增加，旅客運營量的飛速提升，空域資源與運營需求的矛盾凸顯。空中交通管制，是為了保障飛行安全和順暢而生，因此，當其所負責的管制空域或者終端區飛機數量出現超過管制員指揮和保障能力時，就會出現高風險指數，為了保障安全和順暢，需要將這種風險控制在可接受范圍之內，于是空域流量管理便由此而生。

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

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

首先，假設某管制空域，由數個終端機場，以及數條航路航線構成。將這個空域的所有進出口統一進行編號，為ADCBE等5個進出口，那么該空域對應的進口點5個，出口點5個，用小編號1表示入口，則入口有A1、B1、C1、D1、E1，同樣以小編號2表示出口，則出口有A2、B2、C2、D2、E2等5個，總共為10個進出點。

當使用風險評估來對該空域做流量管理決策時，我們通常是依靠管制員的工作經驗來判斷，換言之，并數據化的規則依據，一般情況下，比如上述空域，管制員是通過經驗提出針對上述10個進出口點提出流量管理決策，到單純的減少飛機數量的目的。

利用計算機使用遺傳算法可以幫助完成這一工作，并且這項技術在該領域擁有非常寬廣的拓展空間。

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

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

111 111 111 111 111 111 111 111 111 111

那么假設，目前管制空域風險壓力為P，可接受風險壓力為P0，目前已經打算采取一定的流量控制措施，預計其各個進出口開關的狀態為：

101 111 001 010 111 110 110 010 111 001

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

接下來，需要創建100個（或者更多）隨機編碼組作為基因組，他們每一個，都代表著一種候選的流量控制方法。

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

（1）檢查每個染色體，看它的可行性如何，并相應的為它分配一個適應性分數。

（2）從當前群體中選出兩個成員，選出的概率與適應性分數成正比。

（3）選擇雜交率，從每個選中的染色體中的一個隨機確定的點上進行雜交。

（4）按照預定的變異率，通過對被選染色體的位的循環，把相應的位實進行翻轉。

（5）重復2，3，4，知道100個成員的新群體被創建出來。

例如，系統隨機選出兩組編碼：

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

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

這里我們使用單點交叉法，在中間的空格位進行雜交后，得到新的兩個編碼：

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

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

其中第一個按照變異概率在第4位進行了變異，即翻轉（0和1互換）：

101 011 001 010 111 111 111 111 110 101

如果把這個編碼按照前面所述的編碼規則翻譯過來，就是新的代表10個進出口的控制方法。

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

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

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

參考文獻

[1]徐淑坦，孫亮，孫延風，關于遺傳算法模式定理的進一步探討[J].吉林大學學報（信息科學版），2009.

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

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