遗传算法在多机飞行冲突解脱中的应用

姚成， 林琳， 李妮锶

(中国民用航空飞行学院， 民航飞行技术与飞行安全科研基地， 四川， 广汉 618300)

0 引言

随着航空运输业的快速发展，飞机数量的不断增加导致空中交通变得越来越拥挤，给飞行安全提出了新的挑战。为了应对这一问题，国外学者提出了“自由飞行”的概念，即飞行员根据实际飞行状况采取措施利用剩下的还未开发的空域飞行，打破了固定航路的限制，能够有效地缓解空域拥挤带来的压力[1]。飞行数量的增加和自由飞行路线的多向性势必会增加飞行冲突的可能性，特别是在可用高度层有限而飞行流量又十分密集的低空空域。所以研究飞行冲突解脱的方法将是决定自由飞行技术能否实现的必不可少的一项关键技术[2]。

冲突解脱的主要目的是避免发生飞行冲突，即当探测到两架或多架飞机之间按照当前状态飞行将会发生冲突事件时，及时地规划出一条能够避免冲突发生的理想路径。近年来，在冲突解脱方面国内外学者尝试了很多的智能优化算法，如人工势场法、蚁群算法、神经网络算法等，但都有各自的局限性。人工势场法在缺乏全局信息时容易陷入局部最优值问题，无法得到最优解。蚁群算法虽然搜索能力很好但是在算法的初期收敛速度较慢。神经网络法有很强的学习能力，但其神经元的阈值需要随时间的改变而不断改变，并且在约束较多时网络结构庞大，计算效率较低[3]。

遗传算法作为一种新的全局优化搜索算法[4]，利用其简单通用，搜索能力强以及易与其他算法结合的可扩展性等特点广泛应用于诸多领域。在飞行冲突解脱的问题上，国内外学者应用遗传算法对此均有一定的研究，但大多局限在研究两机情况。本文在符合我国民航相关安全规定的前提下，参考了国内外的有关资料，对基于遗传算法通过改变飞行航向对两机以及多机间的飞行冲突解脱问题进行了一定的研究。

1 遗传算法原理与实现

遗传算法最早是由美国教授 John holland于20世纪七十年代根据生物体进化规律在其著作《自然界和人工系统的适应性》中提出来的[5]。它是一种通过模拟自然进化过程的随机搜索算法。将求解的实际问题的解编码成二进制的染色体基因，求解过程相应地转换成类似生物遗传学中的基因的选择、交叉、变异等过程，最后再解码得到问题的最优解或近似最优解。其中，自然选择根据适应值的大小来确定选择到下一代的概率，适应值由适应度函数确定，选择的目的是为了使种群尽可能地保留适应值大的染色体，使子代向着最优解的方向进化；交叉是将父代中的2个染色体以某种方式重新组合成产生2个新的染色体，交叉操作大大地提高了算法的搜索能力；变异指通过改变父代染色体中的某些基因位点的值，在子代种群中生成异于父代的新染色体，使得种群得以进化更新。本文遗传算法流程图如图1所示。

图1 遗传算法流程图

根据建立的模型和确定的编码方法，本文遗传算法实现的步骤如下。

选择：本文通过随机轮盘赌方式使在遗传过程中优秀个体被淘汰的情况得以有效避免[6]。如图2所示，转动轮盘，适应度越大的个体，被选中保留到下一代的可能性越高，对适应度最大的染色体直接继承。每次选择操作后将淘汰一部分个体，为了保持群体的总数不变，将随机生成新的个体对被淘汰后的个体进行补充。

图2 轮盘赌选择

交叉：遗传算法的交叉操作是指以某种方式在父代群体中的2个配对的染色体之间交换部分基因进化成新的子代，实现种群的更新换代。本文采用的单点交叉方式，即染色体依次两两配对，随机在一对染色体上选取一点分成两段，然后互换重组为新的2条染色体。最为理想的交叉策略是只选取种群中适应度较高的染色体进行交叉操作，并且在交叉后原染色体依旧保留到子代种群中。表1是8位二进制数的染色体上以第5位为交叉点为例的交叉示意图。

表1 交叉示意图

变异：在染色体上随机选取一位，其二进制值反转，在自然界中变异的概率极低，在本文设置的参数也较小。

算法的终止：设定遗传算法运行代数为2 000代，并且设定如果连续500代运算结果的适应度大小无变化，则算法结束，如果2 000代内没有符合条件的结果则算法也相应停止，需要进行一些参数调整或重新启动。

2 模型的建立

根据国家空管的安全规定以及工程应用的实用性，在本文的研究中将冲突问题做如下简化[7]。

(1)在正常的巡航阶段，飞机的实际飞行情况都是在固定的高度层飞行，加之考虑到需要满足旅客乘坐舒适度的要求，故当飞行冲突将要发生时不考虑调整高度层实现冲突解脱，而只是在水平面做出调整，将三维空间问题的冲突解脱简化为二维平面的冲突解脱问题进行处理以简化模型[8-9]。

(2)为了不影响飞机到达目的地的时间，设定飞机在偏离原始航向时的速度大小随着偏航角度大小的变化而变化，始终保持飞机在原始航向上的分速度大小不变。

(3)根据民航局相关安全规定，飞机之间间隔距离大于20 km时不存在飞行冲突[10]。本文采用10 km为步长作为冲突探测计算点，冲突区域设定在边长为200 km的正方形区域内。

(4)在正常的巡航阶段，在满足旅客乘坐舒适度要求的前提下，民航飞机不存在大幅度转弯或者转向操作。本文的飞行方向可设定为左、右偏航30°以及保持原航向。

2.1 遗传算法编码方式的确定

采用二进制编码，编码方案如表2所示。

表2 编码方案

为了提高冲突识别的准确性，采用原始航向上10 km为步长作为冲突探测计算点，这样任意一架进入冲突区域的飞机在冲突区域内总的飞行时间分为20步。在进入每一步之后，飞机的航向能做出调整，其二进制编码表示的含义如表1所示，2位二进制数可以表示4个变量，可以对3个航向角度进行编码。由于总的飞行时间被分为 20步，单架飞机在冲突区域的所有航向的变化能被编译为40位长度的染色体。n架飞机所有的航向改变将被编译为40×n位长度的染色体。

2.2 目标函数与约束条件的确定

假设有n架飞机进入冲突区域，在从经济成本的角度看，希望飞机在不发生冲突的情况下沿着最短的路径飞行即

(1)

式中，si为1架飞机在冲突区域内的总飞行距离。同时还应该保证区域内的所有飞机在任意时刻的距离大于安全距离，本文为简化计算，以10 km为步长作为一个计算点需满足

(2)

式中，(xi,yi)，(xj,yj)为任意2架飞机在同一计算点的坐标。迭代过程中总是向着适应度增大的方向进行，适应度函数公式如下[11]，

(3)

式中，di为规划路径离开点与原航迹终点之间的距离，k为常量，a的初始值为1，在迭代过程中遇到对不满足安全距离的染色体令a等于0，达到对不满足约束的染色体适应值置零的目的，使其在接下来的迭代中不易被选中[12]。

3 仿真结果与分析

实验平台：系统Windows10，CPU为1.6 GHz，内存为16 GB，编程语言为Java，开发工具为IDEA2019.3.3，仿真参数的设置如表3所示。

表3 仿真参数的选取

考虑到运行时间以及搜索速度，初步决定设定种群大迭代次数少或者种群小迭代次数多，仿真结果表明，种群大小超过100时，运行时间较慢，超过1 min，并且收敛效果也不好。而设定种群小迭代次数多的参数时，运行较快，通常在20 s内，收敛效果也较好。故种群大小设置为20～100，迭代次数为2 000。

交叉概率：为了扩大搜索范围，避免出现局部最优解[13]，也参考了其他相关文献，交叉概率设置的值较大，为0.6～0.9。

变异概率：在自然界中变异的概率极低，在本文设置的参数也较小。设置大小为0.01～0.1。

安全距离由民航局相关安全规定设定。

实例1：两架航向分别为自西向东和自南向北飞机以相同速度在同一时刻从各自起点进入冲突区域，根据空管相关规定，两机的安全距离设定为20 km，以原始航向上每10公里步长为一个计算点，在第10步时相遇，为避免发生冲突，采用遗传算法对冲突进行解脱，图3为两架飞机的冲突解脱过程，分别为原始航迹、迭代终止时种群航迹以及最佳解脱航迹，结果表明，对于双机冲突，该算法可以通过改变飞行航向快速有效地得出最优冲突解脱路径。

图3 2架飞机的冲突解脱过程

实例2：为了验证本文提出来的遗传算法的有效性，在上述实例1的基础上增加一架由西南方向飞向东北方向的飞机，建立3架飞机冲突解脱的模型，3架飞机以相同速度同时从各自起点进入冲突区域。各个冲突之间相互制约，由原始航迹可以看出3架飞机仍将在第10步相遇。图4为3架飞机的冲突解脱过程。结果表明，对于三机冲突，该算法也同样能得出最优冲突解脱路径。

图4 3架飞机的冲突解脱过程

实例3：为了进一步验证本文提出来的遗传算法的有效性与适应性，在实例2的基础上再增加一架由西北方向飞行东南方向的飞机，建立4架飞机冲突解脱的模型，4架飞机以相同速度同时从各自起点进入冲突区，由原始航迹可以看出4架飞机也将在第10步相遇。图5给出了4架飞机的冲突解脱过程，从第三个小图即解脱航迹图中可以看出随着飞机数量的增加，遗传算法虽然能实现解脱，但解脱后的在冲突区域内的航迹终点未与原始航迹终点重合，未能使解脱航迹都从原始航迹的终点退出冲突区域。当飞机数量较少时(双机或者三机)则不存在这一缺陷，解脱后的航迹终点均能与原始航迹终点重合，因此算法仍有优化和改进的空间。

图5 4架飞机的冲突解脱过程

4 总结

本文对遗传算法进行了深入的研究并将遗传算法应用于民航飞行冲突解脱的问题中，仿真结果表明，对于双机和三机的冲突解脱问题，本文提出的算法均能通过改变飞行航向快速有效地得出最优冲突解脱路径。但是随着飞机数量的进一步增加，此算法仍存在一定的局限性，虽然能实现解脱，但未能使所有航线都从原始航迹的终点退出冲突区域，后续将考虑提出与其他优化算法相结合的混合算法优化改进存在的缺陷，这还有待进一步研究。