第8卷第1期 智能系统学报 Vol.8 No.1 2013年2月 CAAI Transactions on Intelligent Systems Feh.2013 D0I:10.3969/j.issn.16734785.201210032 网络出版地址：htp:/nw.cmki.net/kcms/detail/23.1538.TP.20130125.1454.007.html 采用遗传算法的多机自由飞行冲突解脱策略 吴君，张京娟 (北京航空航天大学仪器科学与光电工程学院，北京100191) 摘要：为了解决自由飞行时飞机间的冲突解脱问题，提出了一种能够快速准确解算最优航路的算法.遗传算法具 有简单通用、鲁棒性强等特点，应用遗传算法通过改变飞行航向和飞行速度2种方式解决了两机及多机间自由飞行 冲突解脱问题，同时还探讨了多机相对飞行时冲突解脱的有效飞行机制仿真结果表明，无论是改变飞行航向还是 改变飞行速度，算法均能够较快地得出最优冲突解脱路线，同时当多机在一点处存在冲突时，采用改变航向的解脱 方式具有更好的适用性. 关键词：多机；自由飞行；遗传算法；冲突解脱；飞行机制 中图分类号：TP301.6文献标志码：A文章编号：1673-4785(2013)01001605 Conflict resolution of multiple airplanes in free flight based on the genetic algorithm WU Jun,ZHANG Jingjuan (School of Instrument Science and Opt-electronic Engineering,Beihang University,Beijing 100191,China) Abstract:In order to resolve the conflict among airplanes in free flight,the study proposed to examine a genetic al- gorithm to quickly solve the best route.The genetic algorithm was considered to be a simplification,generalization and strong robustness.By applying the genetic algorithm,the conflict relief among multi-planes can be resolved re- spectively by altering the heading,speed,and the effective flight mechanism when multiple airplanes are flying rel- atively at the same time.The simulation results show that the algorithm can achieve the optimal conflict relief route quickly by utilizing both methods,and if there is a conflict at a point among multi-planes,using the method of changing the heading is more applicable. Keywords:multiple airplanes;free flight;genetic algorithm;conflict relief;flight mechanism 随着航空运输需求量的不断增长，空中交通面性必然增加了飞行冲突的可能性.尤其是低空空域 临着越来越严重的航线拥挤，给现有的交通管制系 飞行流量密集，可用高度层有限，所以研究飞行冲突 统带来前所未有的压力.在现行空中交通管制模式 检测与解脱方法和技术的发展都至关重要，并且将 下12】，民航飞机都是遵照地基导航系统所限定的 是影响自由飞行能否实现的一项关键技术[3 由无线电信标建立起来的航线安排航班的，飞机必 遗传算法作为一种新的全局优化搜索算法「4] 须沿着由一系列导航台组成的固定航路进行飞行 以其简单通用、鲁棒性强、适合并行处理及应用范围 由于这些设施不是在任何地方都建立的，因而飞机 广等显著特点，奠定了它作为21世纪关键智能计算 不能选取通往目的地的最直接路线，这导致航路交 之一的地位.国内应用遗传算法解决冲突解脱问题 通日益拥挤，空域整体利用率不高.对于这种状况， 已经取得了一定的进展，但大多局限在研究两机情况 “自由飞行”是一个有效的解决办法， 和变航向的方法56.本文应用遗传算法解决了两机及 然而，飞行数量的增加和自由飞行路线的多向 多机间通过改变飞行速度和方向的冲突解脱问题， 收稿日期：2012-10-22.网络出版日期：201301-25. 基金项目：国家自然科学基金资助项目(61079017) 1基于遗传算法的冲突解脱算法 通信作者：吴君.E-mail:dugujian5@ina.com. 遗传算法是模拟生物在自然环境中的遗传和进
第1期 吴君，等：采用遗传算法的多机自由飞行冲突解脱策略 ·17. 化过程形成的一种全局优化概率搜索算法，它反复 速度分量随偏航角度大小变化 通过选择、交叉和变异等操作算子作用于整个进化 根据我国空管安全规定[8]，雷达管制条件下巡 群体，最终得到问题的最优解或近似最优解).图1 航阶段2架航班之间的间隔大于等于20km时，不 所示为遗传算法的基本流程图 存在飞行冲突.那么在仿真分析区域内，算法中飞机 (开始 以步长10km的间隔前进.在任何时刻当2架飞机 间的距离小于20km时，即认为有冲突的可能，需要 确定实际问题参数集、 编码方案及评价函数 采取措施以避免冲突 1.2改变航向冲突解脱策略 进化代数i=0 1.2.1改变航向冲突解脱算法方案 初始化种群⑦ 根据算法流程，具体实现途径如下. 1)编码方式.采用二进制编码，用6位二进制编码 聚辉 表示[-35°，35°]的偏航角，N为飞机的数量，这样就需 N 要6N位二进制数来表示偏航角， 计算群体中各个 输出结果 体适应值 2)目标函数和约束条件的确定.从燃料消耗角 结束 度看，希望飞机在不发生冲突的情况下沿最短路径 从yP0巾选择M个 个体进入+1) 飞行，即 种群p) 每2个个体随机 y=min∑S 阳对并以概率 种群 +1) P执行交叉 式中：S:为一架飞机从进人区域到离开区域的总飞 、遗传操作 对每个个体以 产生下…代 行距离。 概率P执行 种群+1) 变异操作 同时，应该保证区域内的所有飞机间的距离满 足国家空管安全规定，即 =41 d=√(-)+(y:-y)≥20. 图1遗传算法基本流程 式中：(，)、(y,y)为区域内任意2架飞机的坐标 Fig.1 Basic flow chart of the genetic algorithm 对于不满足安全距离的飞行路径，采用惩罚函 1.1模型简化 数的方法使其不易进入下一代的计算中，即 根据国家空管安全规定和实际飞行操控的具体 y=s,+mx(a-山. 情况，在研究过程中将对实际问题做如下简化： 1)飞机在飞行过程中，除了起飞和降落阶段， 式中：∑S为飞机的飞行路径长度，m为比例系数， 考虑到旅客的舒适和节约燃料，都是定高飞行，所以 d-d:为2架飞机间最小安全距离与实际距离的差 将问题简化为二维平面的冲突解脱问题. 值.这样不满足最小安全距离的飞行路径总飞行长 2)考虑到飞机实际飞行过程中不会做太大角 度比满足最小安全距离的总飞行长度大，在以后的 度的变航向飞行，假设飞机能选择的飞行航向改变 选择过程中就不易被选中. 范围为[-35°，35].为求得最优飞行路径，将此变 3)选择采用随机遍历选择法9]，如图2所示， 化范围均匀地划分成若干份. 设N,为需要选择的个体数目，等距离地选择个体， 3)为了保证飞机按时到达目的地，假设飞机在 选择指针的距离是1/Nv,第1个指针的位置由 所飞方向上的分速度不变，飞机偏航时偏航方向上的 [0,1/Nv]的均匀随机数决定 指 个针 00.15 0.340.350.410.480.510.590.600.780.921.00 图2随机遍历选择法 Fig.2 Stochastic universal sampling method 这样，通过计算各个体的适应值，飞行距离短的长，更容易被选中进入下一代计算 个体具有较大的适应值，在图2的轴上占有距离较 4)交叉和变异.采用单点交叉算子，即在个体
·18 智能系统学报 第8卷 编码串中只随机设置一个交叉点，然后在该点相互 90m 交换部分基因.采用离散变异算子，用特定概率（变 80H 异率取为0.02)对当前种群中某个元素进行变异， 70 60 也就改变飞机在这点的偏航角度： 50 5)遗传算法的终止.设定遗传算法运行代数为 40 1000代，并且设定如果连续30代运算结果变化范 30 围小于0.000001，则算法结束.如果1000代内没 20H 有符合条件的结果则算法也相应停止，需要进行一 些参数调整或重新启动， 01020304050607市8090 x/km 1.2.2仿真及结果 仿真参数设置如下：2架飞机一架自西向东飞 (c)第214代 图32机冲突解脱仿真过程 行，另一架飞机自南向北飞行；飞行距离为90km, Fig.3 The diagrams of 2 airplanes procedure 两机间的安全距离为20km;代沟为0.7，即在每次 1001 的选择过程中将父代中70%的较优个体遗传到下 一代，变异率0.02，交叉率0.7；种群规模设置为 80 600,最大迭代次数为1000次，同时当连续相邻30 代种群变化幅度小于0.000001时，即认为此时的 解为近似最优解，算法终止.图3给出了一次遗传算 20 法的仿真过程.可以看出，生成的初始种群包含了设 置的整个算法空间，保证了初始种群的多样性.随着 20 40 60 80 100 x/km 算法的进行，那些偏离最优解较大的个体已经被淘 汰掉，保留下来的个体均为距最优解较近的个体，算 (a)第1代 法在第214代得出了最优解，2条飞行路径不仅不 存在冲突情况，也保证了最短飞行距离， 90 60 70 44 20 20 40 60 80100 x/km (b)第401代 0102亦3布布50和布8动列 x/km 100 (a)第1代 80 60 90 40 20 60 20 406080100 x/km 04 20 (c)第644代 1 图43机冲突解脱仿真过程 010203040.5060708090 x/km Fig.4 The diagrams of 3 airplanes procedure 为考察算法性能，给出三机冲突解脱的相关实 (b)第201代 验结果，如图4所示.可以看出初始种群仍能保证算
第1期 吴君，等：采用遗传算法的多机自由飞行冲突解脱策略 ·19 法的多样性，且算法收敛性较好，最终可以收敛到一 变飞行航向的策略取得的结果，为了提供更加充实的 个最优解. 理论参考，下面研究采用改变飞行速度策略的情况 再通过观察图5所示六机冲突解脱的相关结果， 根据我国空管安全规定和实际飞行情况，对实 发现在改变航向的冲突解脱算法中，各飞机都朝着各 际情况做如下简化， 自相同方向改变，如果面临冲突问题的飞机架次较少 1)仍然将问题简化为二维平面的飞行冲突解 时还可以通过协商改变航方向进行解脱，但是当架次 脱问题 较多时再临时协调解脱方案就会引起很大的混乱.因 2)为了保证飞机按照规定时间到达目的地，不 此在今后的冲突解脱规则中建立起相应“左行”或者 会因为加速飞行而提前到达，也不会因为降低速度 “右行”机制的空中“交通规则”，规范面临冲突问题时 而推迟到达时间，假设飞机在整个飞行过程中既有 飞机的解脱方案将会给实际冲突解脱问题带来极大的 加速过程也有减速过程. 便利，这对今后实际飞行具有一定参考意义 3)考虑到飞机实际飞行过程中不能太大地改 变飞行速度，假设飞机的飞行速度变化范围为加速 或减速为正常飞行速度的50%，即可以将正常飞行 速度的50%~150%的范围划分为若干份. 4)仍假设飞机以步长为10km,在任何时刻当2 架飞机间的距离小于20km时，即认为有冲突的可 能，需要调整速度来避免冲突。 算法流程和改变航向策略相似，具体实现途径 20 40km608000 如下. 1)选择编码方式.采用二进制编码，用6位二 (a)第1代 进制编码表示正常飞行速度的50%~150%的速度 100 变化，N为飞机的数量，这样就需要6N位二进制数 80 来表示速度变化大小 60 2)目标函数的确定.从燃料消耗角度和旅客舒 适度来看，总是希望飞机在不发生冲突的情况下尽 可能少地变速，即 20 y=min∑S, 20 406080100 x/km 式中：S:为飞机当前时刻位置和不变速时理论位置 (b)第201代 之间的距离， 3)其余条件和改变航向策略相同. 100 1.3.2仿真及结果 80 图6为算法一次执行结束时得出的最优解，可 以看出算法在第308代收敛得出了最优解，自西向 40 东的飞机先减速再加速，而自南向北的飞机先加速 再减速，2架飞机通过改变飞行速度不仅避免了相 20 互间的冲突情况，也保证了总体的最优飞行路线. 40 6080T00 x/km 图7为算法一次运行结束时得出的最优解，可以 看出在第518代时收敛，自西向东的飞机先加速再减 (c)第290代 速，而自东南向西北的飞机先减速再加速，自西南向东 图5六机冲突解脱仿真过程 北飞行的飞机速度变化较小.然而发现一个问题就是 Fig.5 The diagrams of 3 airplanes procedure 仅靠改变速度策略对于两机冲突具有较好的解脱效 1.3改变速度冲突解脱策略 果，无外乎其中一架飞机加速另一架飞机减速，这很好 1.3.1改变速度冲突解脱算法方案 理解.但是当3架飞机冲突时就发现一架飞机加速一 上述算法模型是当有潜在飞行冲突时，执行改 架飞机减速，另一架飞机要么超前要么略晚点到达.本
·20 智能系统学报 第8卷 仿真中自西南向东北飞行的飞机就是提前1个时刻到 [2]程丽媛.自由飞行冲突探测与解脱技术的国内外发展和研 达了目的地.要不然速度改变量的幅度大一些，才能确 究现状[J].中国民航飞行学院学报，2007,39(5)：2123. 保另一架飞机也能按时到达， CHENG Liyuan.The development and research of free flight conflict detection and resolution technology at home and a- 90r broad[J].Joumal of Civil Aviation Flight University of Chi- 80 70 na,2007,39(5):21-23. 60 [3]KUCHAR J K,YANG L C.A review of conflict detection and resolution modeling methods[J].IEEE Transactions on 40 3 Intelligent Transportation Systems,2000,1(4):179-189. 20 [4]周明，孙树栋.遗传算法原理及应用[M].北京：国防工 1 业出版社，1999：2-3. 610203040506流708090 [5]杨尚文，戴福青.基于一种免疫遗传算法的自由飞行冲 x/km 突解脱[J].航空计算技术，2007,37(1)：4143， YANG Shangwen,DAI Fuging.Conflict resolution in free 图6第308代 flight based on an immune genetic algorithm[J].Aeronauti- Fig.6 The 308th generation cal Computing Technique,2007,37(1):41-43. 100r [6]刘星，胡明华，董襄宁.遗传算法在飞行冲突探测解脱中的 80 应用[J].南京航空航天大学学报，2002,34(1)：36-39. LIU Xing,HU Minghua,DONG Xiangning.Application of genetic algorithms for solving flight conflicts[J].Journal of Nanjing University of Aeronautics Astronautics,2002,34 (1):3639. [7]赵荣，张京娟.改进的遗传算法在飞行冲突解脱中的应 用[J].电子测量技术，2009,32(11)：37-39. ZHAO Rong,ZHANG Jingjuan.Conflict resolution based 20 406080100 x/km on an improved genetic algorithm[J].Electronic Measure- ment Technology,2009,32(11):37-39. 图7第518代 [8]王洁宁，袁志娟.基于粒子群算法的飞行冲突解脱问题 Fig.7 The 518th generation [J].中国民航大学学报，2010,28(4)：14. 上述实验结果表明，所设计的算法具有较好的 WANG Jiening,YUAN Zhijuan.Study on resolution of flight 性能，无论是改变航向策略还是改变速度策略，对于 conflicts based on particle swarm optimization[J].Joumal of 两机和三机冲突解脱，算法都有着良好的表现. Civil Aviation University of China,2010,28(4):1-4. [9]魏全新，刘贤锋，黄锵，等.遗传算法选择方法的比较分 2结束语 析[J].通讯和计算机，2008,5(8)：61-65. WEI Quanxin,LIU Xianfeng,HUANG Qiang,et al.The 本文基于遗传算法的冲突解脱问题进行了深人研 comparison of different selection methods in genetic algo- 究，在研究两机冲突解脱的基础上进一步研究了多机 rithms[J].Journal of Communication and Computer,2008, 的冲突解脱方法，通过大量的仿真，验证了所提出的改 5(8):6165, 变飞行航向和飞行速度的策略都可以实现有效冲突解 作者简介： 脱通过仿真结果也可以看出，采用改变速度的解脱策 吴君，男，1987年生，硕士研究生， 略在处理多机冲突问题时具有一定的局限性，而采用 主要研究方向为高精度惯性导航技术 和组合导航，发表学术论文3篇. 改变航向的方法具有更好的适用性，同时还讨论了多 机冲突解脱时相应的飞行机制问题这些结果为自由 飞行和空管自动化系统的研究提供了重要的理论参 考.另外，文中仅对2种解脱方法分别进行了研究，并未 张京娟，女，1975年生，讲师，博士 讨论这2种方法结合的解脱策略，这有待进一步研究. 后，主要研究方向为高精度惯性导航技 参考文献： 术、组合导航和空基体系感知技术等， 发表学术论文10余篇。 [1]张军.现代空中交通管理[M].北京：北京航空航天大学 出版社，2003：17-33