0.   引言

随着中国民航事业的发展, 空域拥挤的问题越来越严重, 减少航班延误造成的经济损失成为当前亟待解决的问题。依靠扩充机场容量, 增加跑道数目减少飞机延误的方法受到多种因素的制约, 因此优化进场飞机的排序, 使延误最小成为当前空中交通流量管理的一个重要内容。

在解决单跑道飞机排序问题时, 最常用的排序方法是先到先服务(FCFS) 算法, 由于他是依靠飞机预计到达时间(ETA) 的次序来决定飞机的着陆次序, 造成延误较大。因此, 国内外对飞机队列的优化算法做了一些研究, 如时间提前量算法(Time Advanced, TA) ^[1]、约束位置交换算法(Constrained Position Shift, CPS) ^[2]、模糊模式识别算法^[3]等。这些方法都是基于单跑道的优化, 其中TA算法是使飞机队列中第一架飞机加速, 对于多数飞机来说使其减少了燃油消耗, 但那些加速的飞机是以提高飞行成本为代价的, 所以在使用TA算法时, 要综合考虑多方面的因素。CPS算法是建立在动态规划的基础上, 对所有可能的飞机排列树进行寻优, 找到一条花费(这里指每2架飞机之间所必需的时间间隔的总和) 最小的路径, 即得到了该组飞机的最佳次序, 但这样可能会使队列的次序有较大变动, 增加了管制员负担, 同时也增大了实现的难度。模糊模式识别以模糊数学理论为基础, 综合考虑了飞机排序的各个因素, 模拟管制员的决策过程做出决策, 进行科学排序, 但该算法隶属度函数的选择较为困难, 且计算较为复杂。

遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应搜索算法, 特别适合于处理传统搜索算法解决不好的复杂和非线性问题, 文献[4]中基于遗传算法的自由飞理论能够有效解决飞行冲突问题。本文研究遗传算法在终端区跑道分配和飞机排序中的应用, 并给出了相关的仿真算例。

1.   机场终端区交通流环境的描述

空中交通管制系统的服务对象是在空域中运行的飞机。空中交通管制的目的是防止飞机和飞机之间以及飞机与障碍物之间相撞。目前的空中交通管制主要是基于距离间隔保证飞机飞行的安全, 但为了实现系统自动化就必须引入时基^[5]的概念。也就是说, 在终端区的交通管理中以时间作为统一的标准来管理所有的飞机, 把管制条例中规定的距离间隔转化为时间间隔。时间间隔与距离间隔的转化是由计算机根据实时数据, 应用速度剖面来完成的。用时间间隔对终端区的飞机进行管理可以有效地提高终端区复杂的环境下空中交通的有序性, 有效地提高航空运输的经济性, 提高机场和航路的容量, 减轻管制员的工作负担。不同类型的飞机相互之间需要不同的时间间隔。国际民航组织(ICAO) 已经规定了在无风条件下不同类型的飞机之间尾流间隔的最小距离标准, 由此可以得到最小时间间隔标准。

图 1给出了一个机场终端区的水平航路结构示意图。本文假设只考虑着陆队列, 规定飞机可能从几条不同的航路进入机场终端区, 概率大致相等。这样所有进入机场终端区的飞机都可以按照时间排成一个队列。

图  1  机场终端区航路结构

Figure  1.  Route structure of airport terminal area

下载: 全尺寸图片 幻灯片

由图 1可知, 机场终端区的空域被划分为3部分, 由2个调度界限来定义。起始调度界限是一个空间界限, 是每架飞机进入管制区的边界, 当飞机穿越他时, 排序算法就接受他的一组参数, 进行排序; 终止调度界限是由特定的距离着陆时间来定义的, 也可以称为冻结界限, 一旦一架飞机穿越了冻结界限, 他到达机场跑道的计划到达时间就保持不变, 直到着陆。2个界限之间称为排序区。

2.   遗传算法原理

2.1   遗传算法概述

遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型, 由美国Michigan大学的Holland.J教授于1975年首先提出的^[6]。该算法是一种基于生物自然选择与遗传机理的随机搜索算法, 起源于对生物系统进行的计算机模拟研究, 是自然遗传学和计算机科学相互结合渗透而成的算法, 所以遗传算法中经常使用一些有关自然进化中的基础用语^[7]。

2.2   基本操作

与传统搜索算法不同, 遗传算法^[6-7]从一组随机产生的初始解开始搜索过程, 该初始解称为种群(population)。种群中的每个个体是问题的一个解, 称为“染色体”。染色体是一串符号, 比如一个二进制字符串, 这些染色体在后代迭代中不断进化, 称为遗传。在每一代中用适应值来衡量染色体的好坏, 生成的下一代染色体, 称为后代。后代是由前一代染色体通过交叉或变异运算形成的。在新一代形成中, 根据适应值的大小选择部分后代, 淘汰部分后代, 从而保持种群大小是常数, 适应值高的染色体被选中的概率较高。这样, 经过若干代之后, 算法收敛于最好的染色体, 他可能就是问题的最优解或次优解, 算法流程见图 2。

图  2  遗传算法流程

Figure  2.  Flow chart of genetic algorithm

下载: 全尺寸图片 幻灯片

第1步随机产生初始种群, 个体数目一定, 每个个体表示为染色体的基因编码。

第2步计算个体的适应度, 并判断是否符合优化准则, 若符合, 输出最佳个体及其代表的最优解, 并结束计算, 否则转向第3步。

第3步依据适应度选择再生个体, 适应度高的个体被选中, 适应度低的个体可能被淘汰。

第4步按照一定的交叉概率和交叉方法, 生成新的个体。

第5步按照一定的变异概率和变异方法, 生成新的个体。

第6步由交叉和变异产生新一代的种群, 返回到第2步。

遗传算法作为一种新的优化技术, 在优化问题时有如下优点。

(1) 遗传算法对所有的优化问题没有太多的数学要求。

(2) 遗传算法是由很多个体组成的一个初始群体开始最优解的搜索过程, 因此是多点搜索。

(3) 遗传算法, 从数学角度看, 是一种概率搜索算法, 其各种算子的运算过程都是以一种概率方式运行, 从而增加了算法的灵活性。

2.3   遗传算法的基本概念

2.3.1   基因和染色体

基因是染色体DNA长链结构中占有一定位置的基本遗传单位, 本文中所指的基因是跑道和飞机个体, 而染色体是飞机基因和跑道基因组成的序列。

2.3.2   适应度

适应度是在研究自然界中生物的遗传和进化现象时, 用来度量某个物种对于生存环境的适应程度。对生存环境适应度较高的物种将获得更多的繁殖机会, 而对生存环境适应程度较低的物种, 其繁殖机会就会相对较少, 甚至逐渐灭绝。本文中采用飞机到达时间总延迟加1后的倒数作为适应度衡量值。

2.3.3   选择

选择指决定以一定的概率从种群中选择若干个体的操作。一般而言, 选择的过程是一种基于适应度的优胜劣汰的过程, 本文中选择过程将采用基于适应度选择的轮盘赌算法实现。

2.3.4   交叉

有性生殖生物在繁殖下一代时2个同源染色体之间通过交叉而重组, 即在2个染色体的某一相同位置处DNA被切断, 其前后2串分别交叉组合形成2个新的染色体。本文中的交叉是对选中的2条跑道染色体进行交叉操作, 按照一定的交叉概率进行单点交叉。

2.3.5   变异

在细胞进行复制时可能以很小的概率产生某些复制差错, 从而使染色体发生某种变异, 产生出新的染色体, 这些新的染色体表现出新的性状。本文中的变异采用对染色体中飞机序列和跑道标号按照一定的变异概率进行变异^[8]。

2.3.6   轮盘赌选择方法

适应度大的个体被选中的机会多, 适应度小的个体被选中的几率小, 产生的结果是优胜劣汰, 类似于博彩游戏中的轮盘赌。个体适应度按比例转化为选中概率, 将轮盘分成10个扇区, 因为要进行10次选择, 所以产生10个[0, 1]之间的随机数, 相当于转动10次轮盘, 获得10次轮盘停止时指针位置, 指针停止在某一扇区, 该扇区代表的个体即被选中。

2.3.7   单点交叉

单点交叉中, 交叉点k的范围为[1, N-1], N为个体变量数目, 在该点为分界相互交换变量, 见图 3。

图  3  单点交叉

Figure  3.  Single point crossover

下载: 全尺寸图片 幻灯片

2.3.8   自适应遗传算法

基本遗传算法中的交叉和变异概率是固定的, 但是通常造成遗传算法性能不稳定, 因而需要对其进行改进。本文采用自适应法(Adaptive GA, AGA) 对种群进行交叉和变异操作, 交叉概率P_c和变异概率P_m能够随适应度自动改变。当种群各个体适应度趋于一致或者趋于局部最优时, 使P_c和P_m增加; 而当群体适应度比较分散时, 使P_c和P_m减小。同时, 对于适应度高于群体平均适应值的个体, 使该解得以保护, 进入下一代; 而低于平均适应值的个体, 对应于较低的P_c和P_m, 使该解被淘汰。因此, 自适应的P_c和P_m能够提供相对某个解的最佳P_c和P_m。自适应遗传算法在保持种群多样性的同时, 保证遗传算法的收敛性。

在自适应遗传算法中, P_c和P_m按如下公式进行自适应调整

${\rm P}{}_c=\{\begin{array}{cc}{\rm P}{}_{c1}-\frac{({\rm P}{}_{c1}-{\rm P}{}_{c2})(f{}^{´}-f{}_{avg})}{f{}_{\max }-f{}_{avg}}\hfill & (f{}^{´}\ge f{}_{avg})\hfill \\ {\rm P}{}_{c1}\hfill & (f{}^{´}<f{}_{avg})\hfill \end{array}(1)$

${\rm P}{}_m=\{\begin{array}{cc}{\rm P}{}_{m1}-\frac{({\rm P}{}_{m1}-{\rm P}{}_{m2})(f{}_{\max }-f)}{f{}_{\max }-f{}_{avg}}\hfill & (f\ge f{}_{avg})\hfill \\ {\rm P}{}_{m1}\hfill & (f<f{}_{avg})\hfill \end{array}(2)$

式中: f^′为要交叉的2个个体中较大的适应度值; f_avg为每代群体的平均适应度值; f_max为群体中最大的适应度值; f为要变异个体的适应度值。一般取P_c1=0.9, P_c2=0.6, P_m1=0.1, P_m2=0.001。

3.   模型的建立

3.1   定义染色体

本文用2条染色体分别代表飞机序列和跑道序列。一对染色体即决定了跑道分配和飞机的排序、调度。对n架飞机进行排序, 每条染色体即包含n个基因。飞机序列染色体决定了飞机之间的相对位置, 只有当2架飞机位于同一条跑道上时他们之间的相对次序才是重要的。每架飞机位于哪条跑道上由相对应的跑道染色体决定。对飞机进行排序后, 他们之间的间隔要满足最小尾流间隔, 即

$S{}_i=\max [S{}_{i-1}+\Delta {}_{i-1,i},E{}_i]$

式中: Δ_{i-1, i}为前机和后机之间的最小尾流间隔标准; E_i为第i架飞机预定到达跑道的时间; S_i为第i架飞机的排序到达时间。

3.2   遗传算法流程

(1) 目标函数为总的飞机延误时间的倒数, 优化准则为当世代数超过预先设定值时, 结束计算。

(2) 随机产生N个个体作为初始种群。

(3) 采用轮盘赌法对初始种群进行选择操作, 适应值大的个体被选中, 适应值较小的个体被淘汰。

(4) 对跑道染色体进行交叉操作, 按照式(1) 计算交叉概率。采用单点交叉方法, 如跑道染色体分别为(1和2分别表示1号跑道和2号跑道)

随机选中第6个位置为交叉点, 进行交叉后, 2条染色体分别为

(5) 对飞机染色体进行变异操作, 按照式(2) 计算变异概率。进行变异操作时, 随机选取飞机染色体中的2个基因, 进行互换。如飞机染色体为(数字代表飞机代码)

$(0‚2‚\begin{array}{|c|}\hline 4\\ \hline\end{array}‚6‚8‚\begin{array}{|c|}\hline 1\\ \hline\end{array}‚3‚5‚7‚9)$

随机选中的基因为3和5两个位置, 则变异后的飞机染色体即为

$(0‚2‚\begin{array}{|c|}\hline 1\\ \hline\end{array}‚6‚8‚\begin{array}{|c|}\hline 4\\ \hline\end{array}‚3‚5‚7‚9)$

4.   仿真算例及结果

4.1   仿真算例

本文以10架飞机, 2条跑道为例进行仿真, 10架飞机的航班代码分别为

$\begin{array}{l}C=(\text{Η}\text{C}0,\text{L}\text{C}1,\text{Η}\text{C}2,\text{Η}\text{C}3,\text{S}\text{C}4\\ \text{Η}\text{C}5,\text{L}\text{C}6,\text{Η}\text{C}7,\text{Η}\text{C}8,\text{S}\text{C}9)\end{array}$

其中第一个字母表示飞机的类型。根据国际民航组织的规定, 有3种类型的飞机, 分别是重型(H)、大型(L) 和小型(S)。

跑道排序见图 4, 给定以下条件。

图  4  双跑道的排序

Figure  4.  Scheduling of dual-runways

下载: 全尺寸图片 幻灯片

在计算E时已经包含了飞机性能和飞行模式的约束条件。飞机的排序到达时间S不能早于相应的E (为具有通用性, 本文是用时间轴上的整数点作为时间单位)。所有降落到跑道上的飞机必须满足前机和后机之间的最小尾流时间间隔。每架飞机的延迟定义为S和飞机到达2条跑道较早的E之间的差值, 即

$d=S-\min (E{}_1,E{}_2)$

式中: 下标1、2分别表示1号跑道和2号跑道。

所求目标函数为延迟最小, 所以适应度函数为

$f=1/(1+d)$

相应的飞机到达跑道的E由一个10×2的矩阵来表示, 其中第一列代表到达1号跑道的时间, 第二列代表到达2号跑道的时间。E的转置矩阵为

$\mathit{E}{}^{\text{Τ}}=\left[\begin{array}{cccccccccc}11& 15& 6& 6& 9& 7& 15& 6& 6& 9\\ 10& 17& 7& 7& 12& 6& 17& 7& 7& 12\end{array}\right]$

不同类型飞机之间的最小尾流间隔标准由一个3×3的时间矩阵(单位为min) 来表示

$\mathit{{\rm T}}=\left[\begin{array}{ccc}1.0& 1.5& 2.0\\ 1.0& 1.5& 1.5\\ 1.0& 1.0& 1.0\end{array}\right]$

其中行代表前机, 列表示后机, 行和列代表的飞机种类依次为H、L、S。

4.2   参数设置

用VC6.0++编写了仿真程序, 每条染色体用一个结构体表示, 结构体中包含了飞机数组和跑道数组。产生随机的初始种群, 采用面向对象编程技术, 对对象进行封装, 分别设计了选择、交叉和变异函数, 对种群进行操作。

基本遗传算法有4个运行参数需要提前设定: N为群体大小, 即群体中所含个体的数量, 一般取为20~1 000;M为遗传运算的终止进化代数, 一般取为100~500代; P_c为交叉概率, 一般取为0.40~0.99;P_m为变异概率, 一般取为0.000 1~0.100 0。

需要说明的是, 这4个运行参数对遗传算法的求解结果和求解效率都有一定的影响, 但目前尚无合理选择他们的理论依据。在遗传算法的实际应用中, 往往需要经过多次试算后才能确定出这些参数合理的取值大小或取值范围。本文中对遗传算法进行了改进, 采用自适应的交叉和变异概率, 取值分别按照式(1) 和式(2) 计算得到。在本文中遗传算法参数取为: 染色体长度为10;种群大小为100;最大进化代数为100。

4.3   仿真结果

经过100代的遗传, 得到的计算结果如下, 可由程序得到打印结果, 并且与先到先服务的排序结果进行了比较。根据先到先服务的原则, 按照飞机的E次序分配跑道和排序, 得到的排序结果见表 1; 采用遗传算法, 经过40~50代遗传后, 适应值趋于平稳状态, 得到的一对染色体为

(HC8, HC2, HC5, HC3, SC9, HC7, SC4, HC0, LC6, LC1)

(1, 1, 2, 2, 1, 2, 1, 2, 1, 1)

表  1  先到先服务排序仿真结果

Table  1.  Simulation result of scheduling using FCFS

下载: 导出CSV 

| 显示表格

上文中表 1为先到先服务的排序结果, 表 2为遗传算法的排序结果。由表 1和表 2比较可以看出, 总延迟时间由先到先服务的12.5个时间单位减少到了6.5个时间单位, 延时减少了40%, 适应度值由0.074 07上升到0.133 33, 适应度值增加了80%。遗传算法排序的结果明显优于先到先服务排序结果, 排序的结果倾向于将相同类型的飞机组成飞机簇。

表  2  遗传算法排序结果

Table  2.  Simulation result of scheduling using genetic algorithm

1号跑道				2号跑道
航班代号	S	Emin	延迟时间	航班代号	S	Emin	延迟时间
HC8	6.0	6.0	0.0	HC5	6.0	6.0	0.0
HC2	7.0	6.0	1.0	HC3	7.0	6.0	1.0
SC9	9.0	9.0	0.0	HC7	8.0	6.0	2.0
SC4	10.0	9.0	1.0	HC0	10.0	10.0	0.0
LC6	15.0	15.0	0.0	总延误时间=6.5 适应度值=0.133 33
LC1	16.5	15.0	1.5

下载: 导出CSV 

| 显示表格

图 5为遗传算法排序得到的最大适应度值和平均适应度值进行曲线以及FCFS的适应度值。由图 5可以看出, 经过多代遗传后, 种群的适应度值趋于一个稳定的值。模仿自然界的生物进化过程进行终端区飞机的排序过程, 经过遗传算法对染色体的选择、交叉和变异操作, 实现了优胜劣汰, 适应度值小(即总的延迟时间大) 的染色体被淘汰, 适应度值大(即总的延迟时间小) 的染色体被继承下来, 因而遗传算法的总体趋势是提高染色体的适应度值。但由于算法的随机性和灵活性, 在计算过程中也有可能出现局部的种群质量有所下降的现象, 但并不影响曲线的整体上升趋势。

图  5  历代适应度进行曲线

Figure  5.  Fittness curves of all generations' evolution

下载: 全尺寸图片 幻灯片

5.   结语

本文主要研究了遗传算法在终端区多条跑道多架飞机排序中的应用, 并且给出了相关的仿真结果。采用遗传算法解决跑道分配和飞机的排序、调度问题, 可以在较大的搜索空间内寻找最优或次优解。仿真结果表明遗传算法在对终端区进场飞机进行科学排序和管理等空中交通流量管理问题中具有较大的应用潜力。