基于改進GA的神經網絡航班保障時間估計

邢志偉，韓大浩，羅 謙

(1.中國民航大學 電子信息與自動化學院，天津 300300；2.中國民航局第二研究所工程技術研究中心,四川 成都 610041)

0 引 言

機場運行是以機場保障服務為核心展開的，因此要對機場保障服務流程進行建模、評估、優化。在航班保障服務仿真模擬方面，王琪[1]從不同角度考慮建立不同的數學模型，以達到減少餐食配送成本的目的。殷龍等[2]建立基于KNN算法的帶有時間窗的車輛調度數學模型，提高機場的資源利用率。Kellenbrink等[3]采用遺傳算法建立數學模型實現資源的合理調度，用于安排具有資源約束的靈活項目。Ansola P G等[4]提出了一個理論與實驗相結合的多智能體系統，以強制實現物理元素與信息通信技術之間的劃分。ANDREATTA G等[5]提出將快速啟發式算法集成到現代機場實時調度決策支持系統中，來提高處理操作的效率。樊瑋等[6]建立多目標車輛數學模型并設計啟發式算法，實現了特種車輛的合理調配。Miller T等[7]建立仿真模擬系統，結合具體案例將改進后的需求工程流程模型應用于維護大型空中交通模擬器；在航班保障服務優化方面，Makhloof M A A等[8]利用項目評估和評審技術以及關鍵路徑方法有效提升了過站航班保障服務的效率。朱新平等[9]構建了基于Petri網的關聯模型，將保障服務過程按層級進行分解，結合實例驗證模型的有效性。Du J Y等[10]引入了基于VRP的MIP模型，提出一種算法求解該模型，目標函數將操作成本降到最低；在航班保障服務時間估計方面，丁建立等[11]分析了航班過站時間的影響因素，建立網絡拓撲模型，用增量學習的方法對所建立的模型進行修正。邢志偉等[12]通過建立貝葉斯網絡模型，采用機器學習的方法，實現對航班保障服務時間的動態估計。

本文提出一種基于改進遺傳算法(AMGA)優化BP神經網絡的航班保障服務時間估計方法，即AMGA-BP算法，該算法的主要創新點在于：在傳統遺傳算法的基礎上，分別對染色體結構、適應度函數、選擇算子、交叉算子、變異算子以及交叉變異概率進行設計，以實現對航班保障服務時間的準確估計，進而提高保障服務效率。

1 相關理論和航班保障服務過程分析

1.1 主成分分析理論

主成分分析(PCA)方法是利用降維(線性變換)的思想，在很少丟失信息的情況下把多個指標轉化為幾個不相關的指標,每個主成分都是原始指標的線性組合,各主成分之間互不相關。影響航班保障服務時間的主成分分析步驟如下：

(1)根據對航班保障服務時間影響因素大小的不同，因此在PCA之前要根據式(1)對原始數據進行標準化處理

(1)

(2)根據標準化后的數據矩陣，計算相關系數矩陣及其特征值λj。

(3)根據式(2)計算貢獻率η，從大到小對貢獻率進行排序，選擇累計貢獻率大于85%的特征值λj所對應的多個主成分來作為最終網絡結構輸入

(2)

1.2 保障服務流程

過站的地面航班保障服務流程是指從飛機著陸后上輪擋開始到撤輪擋完成結束之間的一系列作業活動的集合。本文選取的研究對象是空客A320和波音B737系列等型號的航空器。地面航班保障服務流程是一個復雜的拓撲網絡，我們能夠將其抽象表示出來，如圖1所示，通過對大型樞紐機場地面保障過程的了解和分析，航班保障作業大致可以由4個并行工作流程組成，分別是機務巡檢服務、客艙服務、貨艙服務、航油加注服務，每一個并行的工作流程又由許許多多的串行子工作流程組成。航班作業具體包括以下部分：廊橋對接，開客艙門，開貨艙門，航油加注，垃圾處理，客艙清潔，旅客登機等21個標準動作節點，在這個網狀拓撲圖中，按圖1箭頭所指方向依次進行，每個節點相互之間既有時間順序，不可進行顛倒，又有邏輯次序，能夠確保航班保障服務過程的合理性。這21個節點之間的復雜關系組成了地面保障服務的過程。在這個流程中，如果各種保障服務車輛沒有及時到位，那么將會對后續的一系列作業產生極大的影響，即所謂的波及效應，會造成航班延誤。

圖1 航班保障服務流程

1.3 地面保障服務的BP神經網絡結構設計

2 AMGA-BP算法對航班保障服務時間的估計

AMGA-BP算法是基于BP神經網絡理論，將傳統GA中的染色體表示為兩層結構并改進相應算子，將傳統變異概率設計為自適應交叉變異概率，來優化網絡結構和網絡連接權重、閾值，下面對AMGA-BP算法的主要思想做簡要介紹。

2.1 AMGA-BP算法的兩層結構染色體設計

對傳統的染色體進行改進，染色體的結構是由許多基因按照層次排列起來的，將染色體基因設計分為上下兩層，包括對照基因和參數基因，對照基因處于上層，控制隱含層節點數，優化BP神經網絡網絡結構；參數基因在下層，優化BP神經網絡的網絡權重和閾值，并且下層的參數基因串由上層對照基因來控制。對基因進行編碼，對照基因的編碼為二進制，“1”代表對應基因處于活化狀態，與這個基因相聯系的低層基因串有效；“0”代表對應基因處于失活狀態，與這個基因相聯系的低層基因串無效；參數基因編碼為實數。設計的兩層結構染色體及其編碼圖如圖2所示。本文所設計的染色體可以分為兩個層次，對照基因的編碼長度應該等于隱含層節點數量m，其位置應該處于染色體的上層；參數基因的位置應該處于染色體的下層，其編碼長度應該等于染色體中連接權重和閾值的總數 (n+1)*m+(m+1)*p，其中m為隱含層節點數，n為輸入層節點個數，p為輸出層節點個數。

圖2 兩層階梯結構染色體及其編碼

2.2 AMGA-BP算法的適應度函數設計

AMGA-BP算法既要實現對BP網絡結構的優化，又要實現對BP網絡連接權重和閾值的優化，從而既能夠使航班保障服務時間的估計誤差最小，又能使所建立模型的復雜程度達到最優，這是一個雙目標的優化問題。設計的適應度函數既應該能夠反映BP網絡結構的復雜性，又應該能夠反映BP網絡結構的估計精度。估計精度是由航班保障服務各個節點時間實際訓練集數據的總體估計誤差決定，而網絡復雜程度是由所設計的神經網絡結構的隱含層節點數所決定。適應度函數設計如下

(3)

2.3 AMGA-BP算法的選擇算子

傳統的輪盤和基于適應度比例的一些方法通常會出現“過早成熟”或者“封閉的競爭”。使得沒有可行的辦法進行檢索，最終容易導致陷于局部的極值點而非最值點。針對這個局限，選擇 “最佳個體保存策略”和“規模為2的隨機聯賽選擇策略”的操作方法。

(1)最佳個體保存策略：選擇父代群體中最適應的個體，把選定的個體直接選入下一代群體，這樣不僅使上一代種群中的最佳個體得以保存下來，還確保了遺傳算法的全局收斂。

(2)規模為2的聯賽選擇策略：對于除了上一代種群中最優解決方案之外的所有個體，隨機挑選兩個個體來對比它們的適應度，將具有更好適應度的個體選擇進入到下一代群體中，并淘汰具有較差適應值的個體，直到產生完整的后代群組。這保證了具有相對較高質量的個體能夠進入下一代群體中。

2.4 AMGA-BP算法的交叉算子和變異算子

在AMGA-BP算法中，染色體上層的對照基因層使用單點交叉算子和簡單變異算子；染色體下層的參數基因層使用整體算數交叉算子和非均勻變異算子。整體算數交叉算子使用幾何向量的疊加原理來計算相交上一代矢量的每一個分量，從而擴大了算法的搜索范圍；非均勻變異算子使突變與群體的進化代數相關聯，并且在進化過程的早期階段精英個體數量比較少，使用的范圍比較大，并且在演化過程中的后期階段，為了防止優秀個體被破壞，允許變化的范圍比較窄，這樣能夠獲取局部最佳值。

2.5 AMGA-BP算法的自適應交叉和變異概率

因為交叉、變異概率的選擇會導致遺傳算法效率的降低，如果挑選的概率太大，它將輕松破壞種群中的優秀個體；如果挑選的概率太小，個體更新的速度會變慢很多，很容易陷入“過早成熟”，設計自適應交叉概率的計算公式如下

(4)

式中：fc對應具有較小適應度值的交叉個體，fmin對應當前種群中的最小的適應度值，fa對應當前種群適應度的平均值，0

(5)

式中：fm對應待變異個體的適應度值，fmin對應當前群體中的最小的適應度值，fa對應當前群體的平均適應度值，0

2.6 AMGA-BP神經網絡算法實施步驟

步驟1 載入數據，然后把樣本數據分成兩部分，一部分是作為訓練數據集合，另一部分用于對模型進行測試，將地面航班保障服務每個節點時間的樣本數據歸一化，采用PCA方法降維；

步驟2 設置群體的操作參數，總體數為N，最大進化代數G，開始假設的隱含層節點數(通常采用較大的值)等；

步驟3 隨機產生N個個體組成初始種群，將種群分成兩個子代群體并且將染色體編碼為兩層結構；

步驟4 解碼個體以統計上層子代群體中單個基因串中1的數量，就是相應BP網絡的隱含層節點數量；將上層對照基因相聯系的下層參數基因的實參數串分解成值1，得到隱含層節點最開始的連接權重和閾值；同時訓練BP神經網絡計算適應值；

步驟5 將得到的網絡連接權值和閾值賦給BP神經網絡，使用訓練樣本訓練網絡，然后在使用測試樣本測試網絡，求出測試誤差；

步驟6 根據每一個個體的不同適應值，按照所設計2.3中的選擇算子，選擇進入下一代的精英個體；

步驟7 根據本文設計2.4中的交叉和變異算子，選定的個體利用自適應概率執行變異操作，以生成后代群體；

步驟8 解碼后代群體中上、下層個體，獲得BP網絡結構和網絡初始權重和閾值，多次訓練網絡，并計算它們的適應度值；

步驟9 確定最佳個體適應度值能否滿足設定值，或者能否增加到最大進化數，如果能，則進入步驟10，如果不能，則回到步驟4；

步驟10 解碼具有最佳適應度值的個體，獲得隱含層節點的最佳數量及其最佳網絡初始連接權重和閾值，并分配給BP網絡。AMGA-BP算法流程如圖3所示。

圖3 AMGA-BP神經網絡模型流程

3 航班保障服務流程實例建模分析

通過對國內某樞紐機場航班保障服務過程的研究，本文建立AMGA-BP神經網絡模型。主要考慮了空客A320機型和波音B737機型的航班保障服務過程，提取國內某樞紐機場2017年1月份到8月份實際保障服務時間數據，經初步處理隨機篩選出3600組數據作為訓練樣本，1200組數據作為測試樣本，實驗過程是用MATLAB2014a軟件來完成的。

3.1 數據處理

本文采用主成分分析方法對相關輸入進行降維，最終確定網絡輸入節點數量為10個。本文所設計的估計模型可以用函數的形式表示為y=F(x1,x2,x3,x4,x5,x6,x7,x8,x9,x10)。 在訓練模型之前，為了提高模型估計的準確性，要對規范化輸出變量y和輸入變量x1、x2、x3、x4、x5、x6、x7、x8、x9、x10的數據做歸一化處理，歸一化公式如下

(6)

式中：u對應處理后輸入變量值，xi對應處理前輸入變量值，xmax對應數據最大輸入變量值；xmin對應最小輸入變量值；umax對應處理后的上限值，umin對應處理后的下限值，假設我們處理后數據范圍控制到[0，1]，則umax=1，umin=0。

3.2 模型評價標準

(7)

(8)

(9)

3.3 實驗結果

實驗過程分兩步進行：第一步，AMGA算法用于優化BP網絡，來確定隱含層節點的最佳數量m和最佳初始化連接權重wij、vj1、閾值θj、γ；第二步，將第一步中確定的最佳值賦給BP網絡來訓練BP、GA-BP、AMGA-BP估計模型，使用3個模型對測試集進行估算，通過比較估算結果來評估模型的估算性能。最后用AMGA-BP算法對BP網絡優化后的結構參數確定如下：種群規模N=100；最大進化代數G=200；估計精度調整系數的適應度函數α=0.9，網絡復雜調整系數β=0.1；自適應交叉、變異概率Pc、Pm中系數k1=1,k2=1、k3=0.5、k4=0.5，最終確定輸入層節點個數n=10，輸出層節點個數為1，隱含層節點數取m=14；連接權值wij、vj1和閾值θj、γ的取值范圍為[-3，3]。如圖4所示，經過103代演化，平均適應度達到最小，并且隨著進化代數的增加平均適應度基本不再變化。如圖5所示，當進化代數為103代時，對應的隱含層節點個數為7，因此網絡的最佳隱含層節點數量是m=7，相應的網絡最佳初始連接權重和閾值見表1，其中I1～I10表示10個輸入節點，H1～H7表示7個隱含層節點，O1表示輸出節點，θj為每一個隱含層的閾值，γ為輸出層的閾值。

圖4 平均適應度變化

圖5 隱含層節點數變化

表1 最優初始權值、閾值

建立網絡結構為10-7-1的AMGA-BP航班保障服務神經網絡模型，并分配表1中的最佳初始權重和閾值，選取Sigmoid函數作為激勵函數，學習率取0.01，步長取0.9，最大訓練次數取2000，訓練期望值取0.01。同時訓練BP神經網絡估計模型和傳統的遺傳算法優化的BP神經網絡的估計模型,分別用3種模型來估算地面保障服務時間，隨機抽取測試集中的45組樣本，估計效果的評價指標值見表2，不同算法估計的保障服務時間誤差對比如圖6所示。

圖6 3種模型估計誤差對比

表2 估計效果評價指標值

表2中能夠看出，AMGA-BP網絡模型的平均絕對誤差MAE值小于BP、GA-BP兩種神經網絡模型，希爾頓系數TIC值小于BP、GA-BP模型，說明AMGA-BP模型具有更高的估計精度。從圖6中可以看出：AMGA-BP模型的估計誤差曲線基本上低于BP和GA-BP模型的誤差曲線；GA-BP與BP模型的誤差估計曲線變化趨勢基本相同。將3個模型的保障服務時間估計值與實際值作對比，如圖7所示。

綜上所述，與BP網絡算法和GA-BP算法相比，AMGA-BP算法能夠更好的對地面保障服務時間進行估計，能夠更好的對非線性問題進行處理。值得注意的是，AMGA-BP模型并不是對每個航班保障服務時間的估計都非常準確，但是AMGA-BP模型的總體估計更加穩健。從圖6中可以看出對于某些航班，AMGA-BP模型的保障服務時間估計的準確性遠遠高于GA-BP和BP模型，但誤差仍然不是特別小，這表明AMGA-BP模型需要進一步提高航班保障服務時間在不同條件下的適應性。圖7分別將AMGA-BP、GA-BP、BP算法的估計值與實際航班保障服務時間作對比，可以清晰的看出，BP算法的估計值與實際值相差最大，說明針對航班保障服務這一復雜的非線性問題，僅僅使用傳統的BP算法無法達到期望的要求，必須要在BP神經網絡算法的基礎上進行改進。經過改進后的AMGA-BP算法估計的地面保障服務時間最接近實際地面保障服務時間。

4 結束語

為了提高機場航班保障服務效率，提出了一種基于自適應多層遺傳算法(AMGA)的BP神經網絡模型。該算法是對傳統遺傳算法進行改進，將染色體設計為兩層結構、分別采用不同的編碼方法和遺傳操作模式，并且引入自適應的交叉和變異概率，既實現了對BP網絡結構的優化，又實現對網絡初始權重和閾值的優化，有效提高了BP網絡對非線性問題的處理能力。與傳統的BP、GA-BP方法相比，AMGA-BP算法的估計時間與實際時間相比小于3.9分鐘。AMGA-BP算法具有更好的估計精度和魯棒性，能夠作為估算大型機場地面保障服務時間的有效方法。本文僅僅是以單個航班作為研究對象，因此在后續研究中，將重點研究多航班保障協同以及在不同航班密度、不同機型、不同保障資源量、不同天氣情況下對時間的估計，進一步提高地面保障服務模型的有效性和普遍適應性。

圖7 航班保障服務時間估計值與實際值對比