面向機(jī)場時(shí)段差異的航班延誤免疫預(yù)測算法

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

（1.中國民航大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津300300；2.中國民航信息網(wǎng)絡(luò)股份有限公司，北京100010）

0 引 言

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

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

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

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

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

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

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

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

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

定義1～定義5的詳細(xì)定義請參見文獻(xiàn) ［5］的形式。

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

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

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

2.1 初次應(yīng)答

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

其中a∈待預(yù)測的航班集合A，d∈抗體檢測器集合D，aflightNo為待預(yù)測航班的航班號 （即為抗原），dflightNo為抗體檢測器中的航班號，aATD為航班的實(shí)際起飛時(shí)間，aPTD為航班的計(jì)劃起飛時(shí)間，T為該樞紐機(jī)場航班延誤標(biāo)準(zhǔn)的時(shí)間參數(shù)，1代表匹配，0表示不匹配。

在初次應(yīng)答中，根據(jù)需要預(yù)測的日期，選擇當(dāng)天的航班計(jì)劃數(shù)據(jù)作為抗原，需要預(yù)測日期前30天的航班歷史數(shù)據(jù)建立初始的抗體檢測器。

2.2 抗體的自體耐受

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

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

2.3 延誤率閾值λ的設(shè)定標(biāo)準(zhǔn)

樞紐機(jī)場在不同時(shí)間段內(nèi)的繁忙程度不盡相同，根據(jù)所需預(yù)測的時(shí)間段不同，需要實(shí)時(shí)修改抗體檢測器延誤率閾值λ來提高預(yù)測模型的適應(yīng)性，從而提高航班延誤預(yù)測結(jié)果的準(zhǔn)確度。為了方便表達(dá)，提出兩個(gè)概念，繁忙時(shí)間段和非繁忙時(shí)間段，其時(shí)間段定義如表1所示，其劃分依據(jù)為當(dāng)時(shí)段內(nèi)的航班計(jì)劃起降架次。檢測器延誤率閾值λ根據(jù)預(yù)測日期的航班計(jì)劃運(yùn)行時(shí)間屬于繁忙或者非繁忙時(shí)間段作如表1所示的調(diào)整。

表1 檢測器延誤率閾值的劃分標(biāo)準(zhǔn)

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

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

3.1 初始檢測器的生成

初始檢測器的生成是指在抗體與抗原初次應(yīng)答時(shí)對檢測器進(jìn)行初始化。

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

3.2 訓(xùn)練初始檢測器

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

圖2 初始檢測器生成

3.3 航班延誤動(dòng)態(tài)預(yù)測

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

3.4 實(shí)驗(yàn)結(jié)果及誤差分析

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

圖3 航班延誤預(yù)測流程

表2 機(jī)場各時(shí)段延誤航班預(yù)測值與實(shí)際值

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

表3 誤差率分析

圖4 改進(jìn)前的預(yù)測延誤與實(shí)際延誤對比

圖5 改進(jìn)后的預(yù)測延誤與實(shí)際延誤對比

4 結(jié)束語

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

［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ī)場大面積航班延誤預(yù)警方法研究 ［J］.南京航空航天大學(xué)學(xué)報(bào)，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）. ［丁建立，仝冠生，徐濤.基于免疫否定選擇算法的機(jī)場航班延誤狀態(tài)檢測與實(shí)現(xiàn)［J］.高技術(shù)通訊，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ī)場航班延誤自適應(yīng)實(shí)時(shí)預(yù)測方法 ［J］.南京航空航天大學(xué)學(xué)報(bào)，2011，43 （2）：257－261.］

［4］LI Tao.Computer immunology ［M］.Beijing：Publishing House of Electronics Industry，2004 （in Chinese）.［李濤.計(jì)算機(jī)免疫學(xué) ［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）. ［楊海彤.基于免疫算法的進(jìn)出港航班延誤免疫檢測與波及預(yù)測方法研究 ［D］.天津：中國民航大學(xué)計(jì)算機(jī)學(xué)院，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年航班正常率報(bào)告分析 ［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］.通信學(xué)報(bào)，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］.電子與信息學(xué)報(bào)，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ī)的機(jī)場航班延誤預(yù)警 ［J］.航空學(xué)報(bào)，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）. ［吳剛，夏紅山，高強(qiáng).機(jī)場群運(yùn)行方式下的航班時(shí)刻與頻率優(yōu)化模型［J］.交通運(yùn)輸工程學(xué)報(bào)，2013，13 （4）：79－86.］