基于遗传算法和神经网络的航班到达延误预测方法

Prediction Method of Flight Arrival Delay Based on Genetic Algorithm and Neural Network

摘要: 影响航班到达延误的因素众多，涉及节假日、时段、天气、航空器故障等。本文提出一种基于神经网络多输入–单输出的航班到达延误预测方法，并利用遗传算法优化神经网络的结构与参数，从而进一步提升预测精度。最后，以2015年美国亚特兰大机场为例，给出了预测结果，并与传统神经网络进行性能对比，从而验证了本研究的有效性。研究表明：研究表明，经过遗传算法优化后的神经网络的误差比仅为单独使用神经网络误差的58%。

Abstract: There are many factors affecting flight arrival delay, including holidays, time periods, weather, aircraft failures, etc. In this paper, a multi input single output prediction method of flight arrival delay based on neural network is proposed, and genetic algorithm is used to optimize the structure and parameters of neural network, so as to further improve the prediction accuracy. Finally, taking Atlanta Airport in the United States in 2015 as an example, the prediction results are given and compared with the performance of traditional neural networks to verify the effectiveness of this study. The research shows that the error ratio of neural network optimized by genetic algorithm is only 58% of the error of neural network alone.

1. 引言

根据中国民用航空局发布的《航班正常管理规定》规定，航班若晚于预定时间15分钟后到港，就可以视为延误。显然，当航班延误发生的时候，会给各方面带来极大的影响。因此，若能对航班延误进行精确的预测，就能够减小其给各方带来的损失以及减少其产生的影响。然而，影响航班延误的因素众多，其出现具有偶然性、复杂性等特点，如何精准预测航班延误吸引了国内外学者和工业界的广泛关注[1] [2]。

目前，已有大量文献研究航班延误预测问题[1]-[8]，主要分为时间序列[3]-[5] [8]和因果关系[1] [2] [6] [7]两类，主要成果归纳如下：李俊生[1]从某个枢纽机场航班延误出发，对其关联机场的衔接航班的延误影响进行分析；曹卫东[2]基于贝叶斯网络预测航班离港延误；罗赟骞[3]针对在一天中执行多次任务的航空器延误预测问题，利用其在下游某一机场的历史航班运行数据和当天上游机场的航班运行数据；徐涛[4]利用支持向量机对航班延误预警等级的预报进行相关预测；吴仁彪[5]使用通道卷积神经网络构建航班延误预测模型；丁建立[6]增加天气因素与前序航班相关因素，并针对训练时间较长的问题进行改进，选用运行速度快、占用内存低的轻量级梯度提升机方法；Arian Prabowo [7]提出了一种基于视觉的解决方案，以实现高预测精度；Waqar Ahmed Khan [8]提出了一种新的分层集成机器学习模型，用于预测航班起飞延误和持续时间，以避免决策中的模糊性。

由上可知，现有研究的不足之处有：1) 目前众多学者关注航班离港延误，较少研究航班到达延误问题，其影响因素众多，涉及天气、空管和安全等；2) 多数文献直接利用神经网络、深度学习等机器学习方法进行航班延误预测，缺少利用智能算法优化其结构和参数，提升其预测精度。综上所述，本文提出一种基于神经网络多输入–单输出的航班到达延误预测方法，以2015年美国亚特兰大机场为例，通过计算仿真误差数据，来验证模型的有效性。

2. GA-BP的构建

2.1. GA-BP模型介绍

神经网络是一种模仿生物神经网络结构和功能的数学模型，在通用逼近理论的作用下，其可以逼近任意函数，但其容易陷入局部极小化等问题。本文中采取的神经网络模型为使用反向传播算法(BP)的神经网络模型，其适合于求解内部机制复杂的问题[9]。遗传算法是模拟自然界生物进化所产生的一种智能算法，包括初始化种群、适应度计算以及选址交叉变异等步骤[10]。为了解决神经网络易于陷入局部最优的缺点，利用遗传算法对神经网络的权值与阈值进行优化，据此能够大幅缩短神经网络的训练时间、提高收敛速度[11]。

2.2. BP神经网络的建立

如图1所示，本文选取节假日、天气、空中系统延误、安全问题、航线延误等7个因素为输入，实际航班到港时间为输出，建立基于神经网络多输入–单输出的航班到达延误预测模型，其中：设置15个隐藏层节点数，将$W_1$ 定义为输入层到隐藏层所有权值的集合，$B_1$ 定义为隐藏层所有阈值的集合，$W_2$ 定义为隐藏层到输出层所有权值的集合，$B_2$ 定义为输出层所有阈值的集合，$val$ 定义为适应度函数值，将$\left[W_1,B_1,W_2,B_2,val\right]$ 定义为一条基因的个体。

Figure 1. Neural network structure of arrival delay

图1. 到达航班延误的神经网络结构

2.3. GA-BP的构建

其模型构建分为如下几个过程

过程一：首先构建神经网络结构，神经网络网络的结构如上一节所示，其具体参数为训练次数为1000次，学习率取0.1，目标误差设置为$1\times {10}^{-3}$ ，训练函数的方法为梯度下降法。

过程二：利用遗传算法对神经网络的权值阈值进行优化，其大致流程如下。

1) 种群初始化：种群规模设置为100，设置边界为[0, 1]，进化代数设为50代。

2) 适应度函数：每个染色体由神经网络的权值阈值以及适应度值构成，适应度函数为训练集输出与神经网络输出差的平方和，使得误差越小适应度值越大。

3) 选择操作：采取的方法为基于归一化几何分布的排名选择函数。其原理为把所有的上一代放在一条直线上，每个染色体所对应的上一代都在这条直线上对应了一条线段，该线段的长度与其上一代在经适应度映射后的值成正比，在分配节点时线段长度越大的父代被分配的节点就越多。

4) 交叉操作：采用拓展算术交叉方法，由两个个体的线性组合组成的新个体，其交叉公式如下：

$y_1={\lambda }_1{x}_1+{\lambda }_2{x}_2$ (1)

$y_2={\lambda }_2{x}_1+{\lambda }_1{x}_2$ (2)

${\lambda }_1+{\lambda }_2=1$ (3)

其中$y_1$ ，$y_2$ 为新生成的两个个体，$x_1$ ，$x_2$ 为原来的两个个体，${\lambda }_1$ ，${\lambda }_2$ 为系数，由随机数生成。

5) 变异操作：采取的方法为非均匀突变，其是基于非均匀概率分布改变父代的一个参数。使用非均匀突变算子，可以使得下一代突变量变为0的概率增加，以防止在种群的早期阶段进化停滞。

过程三：利用遗传算法所得到的优化后的权值与阈值赋给神经网络，利用新的神经网络对训练集中数据进行训练，将第t个、第t − 1个、第t − 2个……第t − u个航班预计到达时间作为训练输入，第t个、第t − 1个、第t − 2个……第t − u个航班实际到达时间作为训练输出来预测第t + 1个，第t + 2个，第t + 3个……第t + i个航班的实际到达时间并输出。其流程图如图2所示。

Figure 2. Optimization of neural network flowchart using GA

图2. 利用神经网络优化遗传算法流程图

3. 数值仿真

以2015年美国亚特兰大机场的37,742条达到航班为测试样本，选取80%的数据为训练集以及剩下的20%数据为测试集。本文使用MATLAB实现GA-BP，在 Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz，8GRAM，Radeon (TM) 540上进行测试。

3.1. 数据的预处理

将时间转化为分钟便于模型预测，如2215转换为1335。为解决BP输入权值两极化以及获得更好的学习率，对达到航班测试数据进行标准化处理，如公式(4)所示：

$y=\frac{\left(y_{\max }-y_{\min }\right)*\left(x-x_{\min }\right)}{x_{\max }-x_{\min }}+y_{\min }$ (4)

其中$y_{\min }$ 与$y_{\max }$ 为设定的标准化的区间。$x$ ，$x_{\min }$ ，$x_{\max }$ 分别为被标准化数值，被标准化数值的最大值与最小值。

3.2. 到达航班延误预测结果分析

3.2.1. 常见的评价指标

为了客观的评价预测结果的误差，验证模型的有效性，本文采取如下几个指标进行评价[12]-[15]。

1) 均方根误差

$\text{RMSE}=\sqrt{\frac{1}{n}{\displaystyle {\sum }_{i=1}^n\left({\widehat{y}}_i-y_i\right)}}$(5)

2) 平均绝对百分比误差

$\text{MAPE}=\frac{100\%}{n}{\displaystyle {\sum }_{i=1}^n\left|\frac{{\widehat{y}}_i-y_i}{y_i}\right|}$(6)

3) 拟合度

$R2=1-\frac{{{\displaystyle \sum }}_{I=1}^n{\left({\widehat{y}}_i-y_i\right)}^2}{{{\displaystyle \sum }}_{I=1}^n{\left({\overline{y}}_i-y_i\right)}^2}$ (7)

4) 相对误差

$\text{error}100\%=\frac{{\widehat{y}}_i-y_i}{y_i}\times 100\%$(8)

其中，$y_i$ 为真实值，${\widehat{y}}_i$ 为预测值。

3.2.2. 预测结果

将GA-BP预测值与真实值的相对误差与BP神经网络进行对比，如图3和表1所示，从中可知：1) BP的平均误差率为4.23%，而使用GA-BP的平均误差率为1.16%，GA-BP的误差要明显小于BP；2) GA-BP的RMSE和MAPE仅为BP的58.2%；3) GA-BP的R2为0.909，优于BP的R2值0.8664。由上可知，经过GA优化后的BP在进行预测时，其精度与准确度优于传统BP的效果与适用性。

Figure 3. Flight arrival delay prediction error of GA-BP and BP

图3. GA-BP和BP的航班到达延误预测误差

Table 1. Value of each evaluation index of GA-BP and BP

表1. GA-BP和BP的各个评价指标数值

	RMSE	MAPE	R2	Relative error
BP	0.5279	5.0961*10^−4	0.8664	0.410
GA-BP	0.2857	2.7580*10^−4	0.9090	0.0176

此外，利用GA优化BP的结构和权重收敛曲线如图4所示，最佳适应度在迭代25次之后趋于平缓，平均适应度也与之几乎重合，从而得到了BP的最佳参数配置。

Figure 4. Convergence of algorithm iteration

图4. 算法迭代的收敛情况

4. 结束语

本文在剖析到达航班延误的影响因素基础上，针对传统BP网络模型的不足，研究一类基于GA-BP的多输入–单输出航班到达延误预测模型，以2015年美国亚特兰大机场为例，并与传统模型进行对比。研究表明：

1) 相比于单一因素，综合考虑多种影响因素的到达航班延误预测，预测结果更加准确、可靠。

2) 经过遗传算法优化后的神经网络的误差比仅为单独使用神经网络误差的58%，从而证明GA-BP在此类预测问题上的精度与准确度要优于BP。

然而，本文使用的BP网络模型无法揭示航班延误时空相关性，亟待利用深度学习挖掘航空网络中航路点和航段时空相关性对航班延误的影响。因此，基于GA-深度学习的航班延误预测是我们下一步工作方向。