面向机场时段差异的航班延误免疫预测算法

丁建立，王 曼，曹卫东，胡海生，黄 威

（1.中国民航大学 计算机科学与技术学院，天津300300；2.中国民航信息网络股份有限公司，北京100010）

0 引 言

关于航班延误预测［1］问题，一些专家和学者曾进行了一系列理论研究，并取得了一些成果。文献 ［2］采用静态免疫否定选择算法对航班延误状况进行预测，可以得到某一天各个时段的延误预测结果；文献 ［3］在基本免疫机制基础上提出了基于模糊免疫策略的机场航班延误实时预测方法，将天气状况等影响航班延误的因素考虑在内。

生物免疫是指生物体对 “自我”或 “非我”的识别并排除非己的功能［2］。具体地说，免疫是指机体识别和排除抗原性异物，以维护自身生理平衡和稳定的一个过程。将生物免疫的机理应用于航班延误预测模型的建立，在预测前生成一定的抗体检测器，根据抗原匹配情况对机场的航班延误情况进行预测，获得一天内不同时段的航班延误数量。基于上述分析，尝试对免疫算法中的否定选择算法［2］进行改进，提出一种改进的基于的否定选择算法的航班延误预测方法，根据枢纽机场在一天内不同时间段的繁忙程度不同，实时对检测器参数进行适应性修改，使得预测结果更为准确。仿真结果表明，改进后方法的预测结果和实际情况的拟合度更高。

1 航班延误预测模型的免疫否定选择算法符号定义

否定选择算法是由Forrest等于1944年提出并开发的［4］，它依据生物免疫系统的免疫机理，模拟生物体的免疫过程。算法根据机场运行机制建立相应的免疫模型，预测航班作为抗原，利用航班历史运行数据建立各类抗体检测器。算法的整个预测流程主要包括两个过程，检测器的创建过程和抗体抗原的匹配过程，前一过程即为免疫耐受过程，主要负责产生不同阈值下的各类抗体检测器。后一过程模拟免疫检测，即抗原与抗体的匹配，这个过程中抗体检测器通过识别各抗原以预测航班的延误可能性。目前，否定选择算法在诸如网络入侵检测、防御病毒等多个领域都得到了充分的应用，利用其生成检测器是人工免疫算法中应用比较广泛的一种方法，其基本流程如图1所示。

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

定义3 D：抗体——各类抗体检测器的集合；

图1 否定选择算法的基本流程

定义4 Self：自体——所有正常运行航班的集合；

定义5 Nonself：非自体——所有延误航班的集合；

定义1～定义5的详细定义请参见文献 ［5］的形式。

定义6 λ：各检测器的延误率阈值的集合，根据枢纽机场一天不同时间段的繁忙程度的不同进行动态调整，当航班的延误率在设定的λ范围内时，就将此航班放入对应的检测器中作免疫记忆。

其中，ratio＜λ1：候选检测器；λ1＜ratio＜λ2：成熟检测器；ratio＞λ2：记忆检测器。

2 面向繁忙差异的免疫否定选择延误预测模型

2.1 初次应答

在免疫过程中，抗体与抗原发生初次应答是在抗原第一次进入免疫系统时，免疫系统会对抗原进行识别，并自发地进行自适应调节，为免疫记忆做准备。在改进的枢纽机场航班延误预测模型中，采用下式来表示待检测的抗原与抗体的匹配机制，即当日待预测是否延误的航班与相应历史延误航班之间的匹配［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 检测器延误率阈值的划分标准

检测器延误率阈值λ的取值决定了各类检测器中的检测细胞数量的大小，即决定了各类抗体的数量。与采用静态的统一设置检测器延误率阈值λ相比，根据机场繁忙时段的差异动态调整延误率阈值λ，在一天中机场繁忙程度比较高的时间段，检测器延误率阈值λ的取值偏小，则训练之后成熟和记忆检测器中的抗体数量增多，根据实际情况，预测航班发生的延误的整体概率增大。反之在一天中机场的非繁忙时间段内，训练之后的成熟检测器和记忆检测器中的抗体数量减小，预测航班发生延误的概率也随之减小。通过对检测器多次训练得到的预测结果表明，如表1中所示参数调整检测器延误率阈值λ后的延误预测准确率较之前有所提高，具体数值分析可见实验结果部分。

3 航班延误免疫否定动态预测过程

3.1 初始检测器的生成

初始检测器的生成是指在抗体与抗原初次应答时对检测器进行初始化。

首先确定预测航班延误状况的日期，设定检测器延误率阈值λ，初始化机场各检测器：年龄age为0，延误率ratio为0。继而根据所确定的预测日期，选择需要预测日期的前30天的机场航班历史运行数据进行统计，得到近一个月延误航班的历史延误率以及非延误航班表，用非延误航班表作为自体集合Self，在抗体检测器自学习阶段对其进行自体耐受。同时，根据一天不同时间段机场繁忙程度不同设定相应的延误率阈值λ，将此抗体检测器划分为候选检测器C、成熟检测器R、记忆检测器M，对于各类抗体检测器进行初始化。具体流程如图2所示。

3.2 训练初始检测器

为提高抗体检测器的健壮度，进而保证预测结果的准确度，在该阶段需要完成对初始检测器的训练，即类似于生物免疫系统中的二次应答过程。根据所选择的预测日期，选取近期机场10天的航班历史运行数据作为抗原对上述生成的各初始检测器进行训练，删除未能通过自体耐受的检测器，同时对初始的各类检测器中的抗体进行调整，得到更具适应性和稳定性的成熟检测器C和记忆检测器M。在这个过程中，抗体检测器能对以前识别过的抗原做出迅速的反应。

图2 初始检测器生成

3.3 航班延误动态预测

根据设定的预测日期，选取当天的航班信息作为抗原，利用上一阶段形成的航班记忆检器R和成熟检测器M作为抗体，对待预测日机场从上午7时到夜间24时的航班延误状态进行分时段预测，时段间隔为30min。图3为航班状态预测流程。

3.4 实验结果及误差分析

考虑到枢纽机场的航班延误率较高的情况，选取2013年6月～12月某机场的航班运行历史数据进行实验仿真，其中，航班延误标准的时间参数依据此机场标准设置为30 min。实验分别采用静态统一检测器阈值λ和动态调整检测器阈值λ的方式对航班延误状态进行预测。实验中λ取值为表1中所示，表2分别给出了采用两种方式预测的该机场某一天各时间段的航班延误数量的结果，表中所列为选取的部分非繁忙和繁忙时间段预测结果数据。

图3 航班延误预测流程

表2 机场各时段延误航班预测值与实际值

表3所示的误差率分析结果可以看出，改进前的延误数预测误差率最小为0.00，最大为1.00，其中统计计算得改进前的平均误差率为0.31。虽然改进后的延误数预测误差率最小为0.00，最大也为1，但统计计算得到改进后的平均误差率缩小为0.14。并且由图4、图5分别采用两种方式预测所得的预测延误值与实际延误值之间的对比图，可以更加直观地看出，改进后方法的预测值与真实值之间的拟合度更高。证明采用改进后的预测方法对机场航班延误状态的预测结果更为准确。此外，根据实验数据来看，当机场繁忙程度比较高时，预测延误值接近实际延误值的比例更高。

表3 误差率分析

图4 改进前的预测延误与实际延误对比

图5 改进后的预测延误与实际延误对比

4 结束语

由于枢纽机场的繁忙程度在一天的不同时间段是不相同的，而机场的繁忙程度和当天的航班运行情况有着直接的联系。在基本的免疫否定选择算法的基础上根据需要预测的时间段的不同，自适应调整算法中的检测器阈值，使得预测不同时段时生成的检测器中抗体规模和数量不同，充分利用机场在不同时间段内繁忙程度的不同对航班延误状况的影响，对航班延误状况做出预测。实验结果表明，此方法预测的机场航班延误状况，较基本的免疫否定选择算法而言，更能真实地反映机场实际的延误状况。由于条件局限，论文尚未考率在一年内不同时期，如节假日和非节假日等的机场繁忙程度对航班延误状态的影响，这有待进一步研究。

［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）. ［丁建立，仝冠生，徐涛.基于免疫否定选择算法的机场航班延误状态检测与实现［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］.北京：电子工业出版社，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）. ［吴刚，夏红山，高强.机场群运行方式下的航班时刻与频率优化模型［J］.交通运输工程学报，2013，13 （4）：79－86.］