面向機場時段差異的航班延誤免疫預測算法

丁建立，王 曼，曹衛(wèi)東，胡海生，黃 威

（1.中國民航大學 計算機科學與技術學院，天津300300；2.中國民航信息網絡股份有限公司，北京100010）

0 引 言

關于航班延誤預測［1］問題，一些專家和學者曾進行了一系列理論研究，并取得了一些成果。文獻 ［2］采用靜態(tài)免疫否定選擇算法對航班延誤狀況進行預測，可以得到某一天各個時段的延誤預測結果；文獻 ［3］在基本免疫機制基礎上提出了基于模糊免疫策略的機場航班延誤實時預測方法，將天氣狀況等影響航班延誤的因素考慮在內。

生物免疫是指生物體對 “自我”或 “非我”的識別并排除非己的功能［2］。具體地說，免疫是指機體識別和排除抗原性異物，以維護自身生理平衡和穩(wěn)定的一個過程。將生物免疫的機理應用于航班延誤預測模型的建立，在預測前生成一定的抗體檢測器，根據抗原匹配情況對機場的航班延誤情況進行預測，獲得一天內不同時段的航班延誤數量。基于上述分析，嘗試對免疫算法中的否定選擇算法［2］進行改進，提出一種改進的基于的否定選擇算法的航班延誤預測方法，根據樞紐機場在一天內不同時間段的繁忙程度不同，實時對檢測器參數進行適應性修改，使得預測結果更為準確。仿真結果表明，改進后方法的預測結果和實際情況的擬合度更高。

1 航班延誤預測模型的免疫否定選擇算法符號定義

否定選擇算法是由Forrest等于1944年提出并開發(fā)的［4］，它依據生物免疫系統(tǒng)的免疫機理，模擬生物體的免疫過程。算法根據機場運行機制建立相應的免疫模型，預測航班作為抗原，利用航班歷史運行數據建立各類抗體檢測器。算法的整個預測流程主要包括兩個過程，檢測器的創(chuàng)建過程和抗體抗原的匹配過程，前一過程即為免疫耐受過程，主要負責產生不同閾值下的各類抗體檢測器。后一過程模擬免疫檢測，即抗原與抗體的匹配，這個過程中抗體檢測器通過識別各抗原以預測航班的延誤可能性。目前，否定選擇算法在諸如網絡入侵檢測、防御病毒等多個領域都得到了充分的應用，利用其生成檢測器是人工免疫算法中應用比較廣泛的一種方法，其基本流程如圖1所示。

定義1 U：所有航班的集合；

定義3 D：抗體——各類抗體檢測器的集合；

圖1 否定選擇算法的基本流程

定義4 Self：自體——所有正常運行航班的集合；

定義5 Nonself：非自體——所有延誤航班的集合；

定義1～定義5的詳細定義請參見文獻 ［5］的形式。

定義6 λ：各檢測器的延誤率閾值的集合，根據樞紐機場一天不同時間段的繁忙程度的不同進行動態(tài)調整，當航班的延誤率在設定的λ范圍內時，就將此航班放入對應的檢測器中作免疫記憶。

其中，ratio＜λ1：候選檢測器；λ1＜ratio＜λ2：成熟檢測器；ratio＞λ2：記憶檢測器。

2 面向繁忙差異的免疫否定選擇延誤預測模型

2.1 初次應答

在免疫過程中，抗體與抗原發(fā)生初次應答是在抗原第一次進入免疫系統(tǒng)時，免疫系統(tǒng)會對抗原進行識別，并自發(fā)地進行自適應調節(jié)，為免疫記憶做準備。在改進的樞紐機場航班延誤預測模型中，采用下式來表示待檢測的抗原與抗體的匹配機制，即當日待預測是否延誤的航班與相應歷史延誤航班之間的匹配［5］

其中a∈待預測的航班集合A，d∈抗體檢測器集合D，aflightNo為待預測航班的航班號 （即為抗原），dflightNo為抗體檢測器中的航班號，aATD為航班的實際起飛時間，aPTD為航班的計劃起飛時間，T為該樞紐機場航班延誤標準的時間參數，1代表匹配，0表示不匹配。

在初次應答中，根據需要預測的日期，選擇當天的航班計劃數據作為抗原，需要預測日期前30天的航班歷史數據建立初始的抗體檢測器。

2.2 抗體的自體耐受

為了保證在抗原與抗體匹配的過程中，抗體檢測器在識別延誤航班時不會對非延誤航班形成誤判，在初次應答生成初始抗體檢測器后，需要對初始檢測器中的航班進行自體耐受，即將非延誤航班作為自體集Self從抗體檢測器中刪除。在此采用的是免疫否定選擇方法來實現對抗體的自體耐受，下式定義中1表示該檢測器通過自體耐受，0表示沒有通過自體耐受，d∈抗體檢測器集合D

若某檢測器d尚未通過自體耐受，則δ（d）＝0，刪除該檢測器，通過自體耐受的檢測器作為初始檢測器的一部分保留。

2.3 延誤率閾值λ的設定標準

樞紐機場在不同時間段內的繁忙程度不盡相同，根據所需預測的時間段不同，需要實時修改抗體檢測器延誤率閾值λ來提高預測模型的適應性，從而提高航班延誤預測結果的準確度。為了方便表達，提出兩個概念，繁忙時間段和非繁忙時間段，其時間段定義如表1所示，其劃分依據為當時段內的航班計劃起降架次。檢測器延誤率閾值λ根據預測日期的航班計劃運行時間屬于繁忙或者非繁忙時間段作如表1所示的調整。

表1 檢測器延誤率閾值的劃分標準

檢測器延誤率閾值λ的取值決定了各類檢測器中的檢測細胞數量的大小，即決定了各類抗體的數量。與采用靜態(tài)的統(tǒng)一設置檢測器延誤率閾值λ相比，根據機場繁忙時段的差異動態(tài)調整延誤率閾值λ，在一天中機場繁忙程度比較高的時間段，檢測器延誤率閾值λ的取值偏小，則訓練之后成熟和記憶檢測器中的抗體數量增多，根據實際情況，預測航班發(fā)生的延誤的整體概率增大。反之在一天中機場的非繁忙時間段內，訓練之后的成熟檢測器和記憶檢測器中的抗體數量減小，預測航班發(fā)生延誤的概率也隨之減小。通過對檢測器多次訓練得到的預測結果表明，如表1中所示參數調整檢測器延誤率閾值λ后的延誤預測準確率較之前有所提高，具體數值分析可見實驗結果部分。

3 航班延誤免疫否定動態(tài)預測過程

3.1 初始檢測器的生成

初始檢測器的生成是指在抗體與抗原初次應答時對檢測器進行初始化。

首先確定預測航班延誤狀況的日期，設定檢測器延誤率閾值λ，初始化機場各檢測器：年齡age為0，延誤率ratio為0。繼而根據所確定的預測日期，選擇需要預測日期的前30天的機場航班歷史運行數據進行統(tǒng)計，得到近一個月延誤航班的歷史延誤率以及非延誤航班表，用非延誤航班表作為自體集合Self，在抗體檢測器自學習階段對其進行自體耐受。同時，根據一天不同時間段機場繁忙程度不同設定相應的延誤率閾值λ，將此抗體檢測器劃分為候選檢測器C、成熟檢測器R、記憶檢測器M，對于各類抗體檢測器進行初始化。具體流程如圖2所示。

3.2 訓練初始檢測器

為提高抗體檢測器的健壯度，進而保證預測結果的準確度，在該階段需要完成對初始檢測器的訓練，即類似于生物免疫系統(tǒng)中的二次應答過程。根據所選擇的預測日期，選取近期機場10天的航班歷史運行數據作為抗原對上述生成的各初始檢測器進行訓練，刪除未能通過自體耐受的檢測器，同時對初始的各類檢測器中的抗體進行調整，得到更具適應性和穩(wěn)定性的成熟檢測器C和記憶檢測器M。在這個過程中，抗體檢測器能對以前識別過的抗原做出迅速的反應。

圖2 初始檢測器生成

3.3 航班延誤動態(tài)預測

根據設定的預測日期，選取當天的航班信息作為抗原，利用上一階段形成的航班記憶檢器R和成熟檢測器M作為抗體，對待預測日機場從上午7時到夜間24時的航班延誤狀態(tài)進行分時段預測，時段間隔為30min。圖3為航班狀態(tài)預測流程。

3.4 實驗結果及誤差分析

考慮到樞紐機場的航班延誤率較高的情況，選取2013年6月～12月某機場的航班運行歷史數據進行實驗仿真，其中，航班延誤標準的時間參數依據此機場標準設置為30 min。實驗分別采用靜態(tài)統(tǒng)一檢測器閾值λ和動態(tài)調整檢測器閾值λ的方式對航班延誤狀態(tài)進行預測。實驗中λ取值為表1中所示，表2分別給出了采用兩種方式預測的該機場某一天各時間段的航班延誤數量的結果，表中所列為選取的部分非繁忙和繁忙時間段預測結果數據。

圖3 航班延誤預測流程

表2 機場各時段延誤航班預測值與實際值

表3所示的誤差率分析結果可以看出，改進前的延誤數預測誤差率最小為0.00，最大為1.00，其中統(tǒng)計計算得改進前的平均誤差率為0.31。雖然改進后的延誤數預測誤差率最小為0.00，最大也為1，但統(tǒng)計計算得到改進后的平均誤差率縮小為0.14。并且由圖4、圖5分別采用兩種方式預測所得的預測延誤值與實際延誤值之間的對比圖，可以更加直觀地看出，改進后方法的預測值與真實值之間的擬合度更高。證明采用改進后的預測方法對機場航班延誤狀態(tài)的預測結果更為準確。此外，根據實驗數據來看，當機場繁忙程度比較高時，預測延誤值接近實際延誤值的比例更高。

表3 誤差率分析

圖4 改進前的預測延誤與實際延誤對比

圖5 改進后的預測延誤與實際延誤對比

4 結束語

由于樞紐機場的繁忙程度在一天的不同時間段是不相同的，而機場的繁忙程度和當天的航班運行情況有著直接的聯系。在基本的免疫否定選擇算法的基礎上根據需要預測的時間段的不同，自適應調整算法中的檢測器閾值，使得預測不同時段時生成的檢測器中抗體規(guī)模和數量不同，充分利用機場在不同時間段內繁忙程度的不同對航班延誤狀況的影響，對航班延誤狀況做出預測。實驗結果表明，此方法預測的機場航班延誤狀況，較基本的免疫否定選擇算法而言，更能真實地反映機場實際的延誤狀況。由于條件局限，論文尚未考率在一年內不同時期，如節(jié)假日和非節(jié)假日等的機場繁忙程度對航班延誤狀態(tài)的影響，這有待進一步研究。

［1］LV Xiaojie，WANG Hong.Method for swept flight delay early warning of large aeronautic hub ［J］.Journal of Nanjing University of Aeronautics ＆ Astronautics，2009，30 （19）：4564－4566（in Chinese）.［呂曉杰，王紅.大型樞紐機場大面積航班延誤預警方法研究 ［J］.南京航空航天大學學報，2009，30（19）：4564－4566.］

［2］DING Jianli，TONG Guansheng，XU Tao.The detection and implementation of airport flight delays state based on immune negative selection algorithm ［J］.High Technology Letters，2008，18 （4）：387－391 （in Chinese）. ［丁建立，仝冠生，徐濤.基于免疫否定選擇算法的機場航班延誤狀態(tài)檢測與實現［J］.高技術通訊，2008，18 （4）：387－391.］

［3］DING Jianli，YANG Haitong，GU Bin.Adaptive real－time forecasting method of airdrome flight delay based on fuzzy immunization strategy ［J］.Journal of Nanjing University of Aeronautics ＆ Astronautics，2011，43 （2）：257－261 （in Chinese）.［丁建立，楊海彤，顧彬.基于模糊免疫策略的機場航班延誤自適應實時預測方法 ［J］.南京航空航天大學學報，2011，43 （2）：257－261.］

［4］LI Tao.Computer immunology ［M］.Beijing：Publishing House of Electronics Industry，2004 （in Chinese）.［李濤.計算機免疫學 ［M］.北京：電子工業(yè)出版社，2004.］

［5］YANG Haitong.Research on detection and propagation prediction method for arrival and departure flight delays based on immune algorithm ［D］.Tianjin：School of Computer Science and Technology Civil Aviation University of China，2011：19－21 （in Chinese）. ［楊海彤.基于免疫算法的進出港航班延誤免疫檢測與波及預測方法研究 ［D］.天津：中國民航大學計算機學院，2011：19－21.］

［6］Ding J L，Ji J L.Optimization of airport flight arrival and departure based on compromise immune algorithm ［C］／／3rd International Conference on Natural Computation，2007.

［7］PAN Yonggang，WANG Xu.Analysis of 2006flight on－time performance rate reporte ［J］.China Civil Aviation，2007，77（5）：36－39 （in Chinese）. ［潘永剛，王旭.2006年航班正常率報告分析 ［J］.中國民用航空，2007，77 （5）：36－39.］

［8］JIN Zhangzan，LIAO Minghong，XIAO Gang.Survey of negative selection algorithms ［J］.Journal on Communications，2009，30（19）：4564－4566 （in Chinese）.［金章贊，廖明宏，肖剛.否定選擇算法綜述 ［J］.通信學報，2013，34 （1）：159－169.］

［9］ZHANG Xiongmei，YI Zhaoxiang，SONG Jianshe，et al.Research on negative selection algorithm based on matrix representation ［J］.Journal of Electronics ＆Information Technology，2010，32 （11）：2701－2706 （in Chinese）. ［張雄美，易昭湘，宋建社，等.基于矩陣形式的否定選擇算法研究 ［J］.電子與信息學報，2010，32 （11）：2701－2706.］

［10］Tu Yufeng，Ball M，Jank W.Estimating flight departure delay distributions a statistical approach with long－term trend and short－term pattern ［J］.Journal of the American Statistical Association，2008，103 （481）：112－125.

［11］Hsu Chauq－Inq， Hsu Che－Chanq，Li Hui－Chieh.Flight－delay propagation allowing for behavioral response ［J］.International Journal of Critical Infrastructures，2007，3 （3／4）：301－326.

［12］Parikshit D.Robust air－traffic control using ground delays and rerouting of flights ［J］.Journal of Aerospace Computing Information and Communication，2009，6 （12）：630－655.

［13］Rasvan V，Danciu D，Popescu D.Nonlinear and time delay systems for flight control ［J］.Mathematical Reports，2009，11 （4）：359－367.

［14］XU Tao，DING Jianli，GU Bin，et al.Forecast warning level of flight delays based on incremental ranking support vector machine ［J］.Acta Aeronautica et Astronautica Sinica，2009，30 （7）：1256－1263 （in Chinese）. ［徐濤，丁建立，顧彬，等.基于增量式排列支持向量機的機場航班延誤預警 ［J］.航空學報，2009，30 （7）：1256－1263.］

［15］WU Gang，XIA Hongshan，GAO Qiang.Optimization model of flight time and frequency under operation mode of multi－airports system ［J］.Journal of Traffic and Transportation Engineering，2013，13 （4）：79－86 （in Chinese）. ［吳剛，夏紅山，高強.機場群運行方式下的航班時刻與頻率優(yōu)化模型［J］.交通運輸工程學報，2013，13 （4）：79－86.］