基于粒子群算法的飞行冲突解脱问题

1、第28卷第4期2010年8月中国民航大学学报JOURNALOFCIVILAVIATIONUNIVERSITYOFCHINAVol.28No.4August2010基于粒子群算法的飞行冲突解脱问题王洁宁，袁志娟（中国民航大学空中交通管理研究基地，天津300300）摘要：自由飞行可有效解决航线日益加剧的拥挤问题，但同时也增加了管制员管制监控的难度，从而使飞行冲突探测和解脱成为自由飞行的关键问题。粒子群算法（particleswarmoptimization）是一种群智能优化算法，尝试将其应用于飞行冲突解脱问题，构造了适合飞行冲突解脱问题的粒子表达方式，建立了冲突解脱问题的粒子群算法，成功解决了飞行

2、冲突，并将其运行结果与遗传算法结果作了对比试验。实验结果表明，粒子群算法是求解飞行冲突解脱问题的一个较好方案。关键词：空中交通管理；飞行冲突探测与解脱；粒子群算法；自由飞行；遗传算法中图分类号：V355.1文献标识码：A文章编号：16745590（2010）04000104StudyonResolutionofFlightConflictsBasedonParticleSwarmOptimizationWANGJie-ning，YUANZhi-juan（AirTrafficManagementResearchBase，CAUC，Tianjin300300，China）Abstract：Free

3、flightisaconceptualoperationinsolvingtheincreasingairtrafficcongestions；howeveritwouldmakethe（particleswarmoptimization）aircontrollermoredifficulttomakedecisionstooptimizeconflictresolution.PSOisaswarmintelligenceoptimization.Inthispaper，PSOisattemptedtobeusedtosolvetheconflictresolution.Thispaperpr

4、oposesanovelparticlepresentationfortheconflictresolution，establishesaPSOalgorithmforthiskindofproblem，solvestheconflictinflightsuccessfully，andcompareswithGAinthesameconflictresolutionexperiments.ExperimentalresultsshowthatthePSOisaneffectivemethodinsolvingtheconflictresolutionproblem.Keywords：airtr

5、afficmanagement；conflictdetectionandresolution；particleswarmoptimization；freeflight；geneticalgorithm随着民航运输业的快速发展，空中交通流量不断增加，导致由扇区和航路组成的空域严重超载。为了从根本上解决空中交通的拥挤状况，从20世纪90年代开始，美国等一些航空发达国家提出了“自由飞行”的概念，即飞行员可自主选择飞行速度、飞行高度和最直飞行航线。自由飞行能够使航班自由选取最快、接的路径，提高空域利用率。但自由飞行使空中交通管制变得复杂，增加了空中交通管制的难度。因此，飞行冲突的探测和解脱问题的研究变

6、得异常重要。世界各国的研究者做了大量这方面的研究工作并提出了几种方法，概括起来大致可分为6类：基于遗传算法的冲突探测与解脱1-4；神经网络模型5；非结构网格生成的冲突探测方法6；人工势场法解决飞行收稿日期：2009-12-04；修回日期：2010-03-11冲突7；Delaunay方法用于冲突探测8；线性规划法用于冲突解脱9。本文提出使用粒子群优化算法解4决自由飞行中的飞行冲突问题，并与GA（遗传算法）进行了比较。1粒子群算法粒子群算法（particleswarmoptimization，PSO）于1995年由Kennedy和Eberhart提出，该算法模拟鸟群飞行觅食的行为，通过鸟的集体协作

7、使群体达到最优10。在PSO系统中，每个可行解被称为一个“粒子”（particle），多个粒子共存、合作寻优。每个粒子根据自身经验和群体最优经验在问题域中向更好的位置“飞行”，基金项目：国家自然科学基金项目（60832011）；中国民航大学博士启动基金项目（06QD07S）作者简介：王洁宁（1966），男，甘肃兰州人，研究员，博士，研究方向为空中交通流量管理、空管信息系统.中国民航大学学报2010年8月搜索最优解。PSO算法解析如下11：设搜索空间为D维，总粒子数为n。第i个粒子位置表示为向量Xi=（xi1，xi2，xiD）；第i个粒子“飞行”历史中的最优位置为Pi=（pi1，pi2，piD）

8、，其中第g个粒子的历史最优位置Pg为所有P（ii=1，2，n）中的最优；第i个粒子的位置变化率（速度）为向量Vi=（vi1，vi2，viD）。每个粒子的位置按如下公式进行变化vid（t+1）=wvid（t）+c1rand（）pid（t）-xid（t）+c2rand（）pgd（t）-xid（t）（1）xid（t+1）=xid（t）+vid（t+1）1in1dD（2）式中：c1、c2为正常数，称为加速因子；rand（）为0，1之间的随机数；w称为惯性因子。第d（1dD）维的位置变化范围为-Xmaxd，Xmaxd，速度变化范围为-Vmaxd，Vmaxd，迭代中若位置和速度超过边界范围则取边界值。粒子

9、群初始位置和速度随机产生，然后按式（1）、式（2）进行迭代，直至找到满意的解。目前，常用的粒子群算法将全体粒子群（global）分成若干个有部分粒子重叠的相邻子群（1ocal）。Kennedy提出了多种邻接子群拓扑结构12，如Ring型、Wheel型、Star型等，并做了相关分析。每个粒子根据各子群的历史最优Pp调整速度和位置，即将式（1）中pgd换为ppd。PSO算法基本流程如下：1）随机初始化粒子群的位置和速度。2）计算每个粒子的适应值。3）对于每个粒子将其适应值与其所经历过的最好位置Pi的适应值进行比较，若较好，则将其作为当前最好位置。4）对于每个粒子将其个体历史最优适应值与群体历史最优

10、位置P（或gPp）的适应值进行比较，若更好，则将其作为群体最优位置。5）按式（1）更新粒子速度，按式（2）更新粒子位置，超出边界按边界取值。6）未满足停止条件，则返回步骤2）。近些年的研究和实践表明，PSO在多维空间多峰问题寻优、动态目标寻优方面有着速度快、解质量高、鲁棒性好等优点11。2问题描述根据中国空管安全规定，雷达管制条件下，巡航阶段两架航班之间的间隔不小于20km时，不存在飞行冲突。飞行冲突问题的一种常见描述为：在一个边长为200km的正方形扇区内，一架飞机由南向北飞行，而另一架飞机由西向东飞行。在保证间隔的条件下，对问题进行简化4，9，13，即：在巡航阶段，通常航班只采用改变水平方

11、向进行避障，因此问题可简化为一个二维问题。同时为了避障时不做大角度转弯的机动动作，在此假设航班只选择左偏30、右偏30和直飞3个机动动作飞行。假设飞行速度不变，本文对于该假设条件在问题求解时做了适当的优化，即文献中假设的飞行速度不变4，9，13，只表示飞机在所飞方向上的速度分量不变。为了保持该速度分量不变，航班右偏或左偏都会导致实际飞行速度的增大，也就是航班的速率随航班的偏转而发生变化，本文采用严格按照实际飞行速度不变的假设对问题进行分析。为计算方便，每架航班在在扇区内都设一个理论进入点和退出点，为简化问题，假设所有飞机在同一时间进入扇区。设步长为s=10km，每一步在起始点处调整好航向。任意

12、两架航班在任何时候的间隔小于20km即为飞行冲突。为避免冲突，需进行航线调整，此时飞行轨迹最优化的目的是所有航班通过该扇区的总距离最短。3飞行冲突解脱问题粒子群算法3.1模型建立本文采用文献4所提出的K架航班进入扇区的数学模型。目标是在保证不发生飞行冲突的情况下，总航线长度最短，即KminZ=Si（3）i=1在此任意两架航班满足姨ijij20i=1，2，nj=1，2，n（4）式（3）中：K为同时进入扇区的航班架次；Si为第i架航班在该扇区内的航线长度。式（4）中：（xi，y）i和（xj，y）j分别表示第i架和第j架航班在该扇区内的位置。3.2构造粒子表达方式及其约束下模型的改进本文构造一个KL

13、维空间，其中：K为航班数，L=20为各航班在本扇区内的步长数。将每个粒子对应的KL维向量X分解成K个L维向量：Xk=（xk1，xk2，xkL）（k=1，2，K），表示第k架航班在本扇区内的飞行轨迹。每个粒子的速度向量V与之对应表示为：Vk=（vk1，vk2，vkL）（k=1，2，K）。其中姨姨姨-1第k架航班在第l步左偏30x姨姨kl=姨姨0第k架航班在第l步直飞姨姨姨姨+1第k架航班在第l步右偏30第28卷第4期王洁宁，袁志娟：基于粒子群算法的飞行冲突解脱问题例如：在该扇区内，两架航班时飞行冲突解脱问题的粒子表达式为一个220维向量，如X=（00，00，0，0，0，0）表示两架航班直飞时的粒

14、子X0120个X0220个表达式。此时意思相同且维数仅是文献4中相同问题表达式维数的一半，因此本文构造的粒子表达方式比较合适。本文对“飞行速度不变”假设条件改进后，某架航班在本扇区内有l步转弯避障，则20步完成后还存在（1-cos30）10lkm的距离未到达预计扇区退出点。在该粒子表达方式下的距离可写为（1-cos30）Lsxklkm，又因（1-cos30）s为常数，所以此l=1目标函数可进一步简化为KLminZ=xkl（5）k=1l=1需满足式（6）式（9）的约束条件姨1l2l1l2l20（6）式中l（a1l，b1）l=（ls-（1-cos30）sx1i，i=1l100-sin30sx1）i

15、i=1l（a2l，b2）l=（100+sin30sx2i，i=1lls-（1-cos30）sx2ii=1分别表示第l步时两架航班的位置。Lxkl=0k=1，2（7）l=1xkl-xk（l-1）2k=1，2l=2，3，20（8）xkl=1，0或-1k=1，2l=2，3，20（9）其中：式（7）限制所有航班均在扇区理论退出点离开扇区；式（8）、式（9）限制连续两步的最大转弯角度为30。因式（9）限制xkl只能取1、0或-1，所以式（5）式（9）所描述的飞行冲突解脱模型为整数规划模型。3.3算法实现过程由于前文所介绍的PSO算法为连续空间算法，而两个航班的冲突解脱问题是整数规划问题，因此对算法实现过

16、程做了适当修改。步骤1初始化粒子群。1）将粒子群划分成两两重叠的子群；2）每个粒子的X（kk=1，2）的每一维随机取-1，0，1；3）每个速度向量V（kk=1，2）的每一维随机取-22之间的实数；4）用评价函数EVAL评价所有粒子，即计算各个粒子的目标函数值；5）将初始值作为个体历史最优Pi和各子群历史最优Pp及群体历史最优Pg。步骤2循环以下步骤，直到满足终止条件。1）对每个粒子按照式（1）计算V，按式（2）计算X；2）用评价函数EVAL评价所有粒子；3）若某个粒子的当前评价值优于其历史最优评价值，则记当前评价值为该历史最优评价值，同时记当前位置为该粒子历史最优位置Pi；4）寻找当前各子群最

17、优解和总群体最优解，若优于历史最优解则更新Pp、Pg。其中，评价函数EVAL完成的任务为：1）计算该粒子代表方案的转弯次数Z。若某个粒子所代表的路径为不可行解，则把该方案的评价值置为不可达到的大值，如该问题总的步骤数为KL=40，则置不可行解的评价值为大于40的值。实验中取不可达到的大值为100。2）对于迭代计算中的X，若X中某一维的值大于等于1时取值为1，值在（-1，1）之间时取0，值小于等于-1时取值为-1。4实验结果及分析为便于比较结果，用Matlab7.0编写飞行冲突解脱问题的PSO和GA程序。其中参数取值如下：GA参数4：群体规模n=1000；交叉因素Pc=40%；突变因素Pm=5%

18、。PSO参数12：粒子数n=40；分为2个子群，群体规模为21，重叠粒子为2；w=0.729；c1=c2=1.49445；最大迭代次数为200。将GA算法和PSO算法实现过程分别在Matlab7.0中运行100次，结果对比如表1所示，两种算法的最优运行结果如图1和图2所示。从表1可以看出，PSO搜索成功率在转弯次数12时高达68%，而GA只成功搜索22次，比率为22%；且两者搜索总时间差距不大。由图1、图2显示的算法最优运行结果可知：本文通过对问题的优化改进使其更符合实际情况、更直观，粗实线部分即为调整后航班比直线飞行时多飞的距离；扇区内遗传中国民航大学学报2010年8月表1GA和PSO运行结

19、果对比Tab.1ComparisonofGAandPSOalgorithmsrunningresults转弯次数优化算法GAPSO80次27次100次21次1222次20次1278次32次总搜索时间/s548527注：搜索的最优结果为转弯次数不同时在100次运行中出现的次数。算法比粒子群算法优化结果多飞行了（1-s（12-8）km；粒子群优化结果只需调整1架航班就能使冲突解脱，减少了管制员的工作负荷。显然，在相同扇区内两架航班冲突问题中，粒子群算法优化结果优于遗传算法优化结果。5结语本文针对自由飞行条件下扇区内的飞行冲突问题，提出利用粒子群算法的思想，构造了适合该问题的粒子表达方式，同时建立了

20、在该粒子表达方式下的数学模型，从而构建了飞行冲突解脱问题的粒子群算法，有效解决了两架航班在扇区内的飞行冲突。分析粒子群算法实现过程可以看出，每个粒子均能够直接获取群体和个体历史经验，比遗传算法更有效；把粒子划分为几个子群，且子群之间相互重叠，从而降低了收敛于局部最优的可能性。因此，把粒子群算法应用到飞行冲突解脱问题的求解中，取得了比较好的效果。但随着航班数量的增加，将会出现许多新的问题，有待不断深入研究和探索。参考文献：1ALLIOTJM，GRUBERH，JOLYG，etalGeneticAlgorithmsforSolvingAirTrafficControlConflictsC/TheNi

21、nthConferenceonArtificialIntelligenceforApplications，1993：338-344.2NEERASOOD，SANDEEPMULGUND，CRAIGWANKE，etalAMulti-ObjectiveGeneticAlgorithmforSolvingAirspaceCongestionProblemsC/AIAAGuidance，NavigationandControlConference，2007.3VORMERFJ，MULDERM，VANPAASSENMM，etalOptimizationofflexibleapproachtrajector

22、iesusingageneticalgorithmJ.JournalofAircraft，2006，43（4）：941-952.4刘星，胡明华，董襄宁遗传算法在飞行冲突解脱中的应用J南京航空航天大学学报，2002，34（1）：35-38.5BURDUNIYAnAISituationalPilotModelforReal-TimeApplicationsC/Proceedingsofthe20thCongressoftheInternationalCounciloftheAeronauticalSciences，Sorrento，Napoli，Italy，September8-13，1996：210-237.6FULTONNLAirspacedesign：towardsarigorousspecificationofcomplexitybasedoncomputationalgeometryJAer