基于改进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 航班保障服务时间估计值与实际值对比