机场航空器地面滑行调度优化研究分析航空航天专业.docx

基于改进遗传算法的滑行道优化研究摘要随着我国民航运输业的快速发展，繁忙机场面临着日渐增大的流量压力。研究机场滑行调度优化的目的，是在保证安全的前提下，充分利用机场滑行道系统的资源，提高运行效率，增大机场容量。本文简单地介绍了机场场面结构及滑行优化问题的建模思路。根据双流机场得到的滑行路径和序列数据，确定各个航班的滑行时间。在优化算法的选择环节，对比常见遗传算法滑行道调度模型，提出一种基于标准遗传算法与模拟退火算法思想相结合的改进算法。展示了优化结果与算法的收敛性，验证了该模型达到优化的可行性。关键词：机场；滑行调度；改进遗传算法；数学模型；模拟退火算法RESEARCHONOPTIMIZATIONOFTAXIWAYBASEDONIMPROVEDGENETICALGORITHMAbstractWiththerapiddevelopmentofChina'scivilaviationtransportindustry,busyairportsarefacingincreasingtrafficpressure.Thepurposeofstudyingairporttaxiwaydispatchingoptimizationistomakefulluseoftheresourcesofairporttaxiwaysystem,improveoperationefficiencyandincreaseairportcapacityonthepremiseofensuringsafety.Thispaperbrieflyintroducesthemodelingideaofairportscenestructureandtaxiingoptimizationproblem.AccordingtothetaxiingpathandsequencedataobtainedfromShuangliuAirport,thetaxiingtimeofeachflightisdetermined.Intheselectionofoptimizationalgorithm,animprovedalgorithmbasedonthecombinationofstandardgeneticalgorithmandsimulatedannealingalgorithmisproposedbycomparingthecommongeneticalgorithmtaxiwayschedulingmodel.Theconvergenceoftheoptimizationresultsandthealgorithmisshown,andthefeasibilityofthemodeltoachieveoptimizationisverified.Keywords:airport;taxiwayscheduling;improvedgeneticalgorithm;mathematicmodel;conflictresolution摘要IRESEARCHONOPTIMIZATIONOFTAXIWAYBASEDONIMPROVEDGENETICALGORITHMIIAbstractII引言11.1 选题背景和意义11.2 国内外研究概况21.3 课题主要研究工作3第二章机场场面介绍42.1机场场面结构42.1.1跑道42.1.2滑行道42.2机场场面滑行过程42.3机场场面滑行优化问题62.4建立机场场面网络结构模型62.5多跑道运行相关规定62.6本章小结8第三章遗传算法介绍93.1遗传算法的生物学基础93.2遗传算法的原理概述93.3 遗传算法应用于繁忙机场路径优化的优劣势分析93.4 遗传算法的实现步骤103.4.1流程框架103.4.2染色体编码103.4.3适应度函数的选择113.4.5遗传操作123.4.6终止条件133. 5遗传算法的运行参数13第四章基于改进遗传算法的滑行路径优化调度144. 1模型建立144.1.1滑行道调度模型144.1.2标准遗传算法过早收敛及改进猜想16图4.12标准遗传算法早熟收敛示意图174.L5模型改进174.1.6初始群体的生成184. 2优化策略184.3算法的实现194. 4本章总结20第五章研究展望和总结215. 1总结设计工作提出不足215. 2研究展望21致谢22参考文献23引言1.1 选题背景和意义我国民航事业近些年来发展迅速，作为一个民航大国正不断向民航强国的目标前进。根据2018年民航业发展统计公报显示2018年我国机场主要生产指标继续保持平稳较快增长，全年旅客吞吐量超过12亿人次，完成126468.9万人次,较上年增长10.2%o分航线看，国内航线完成113842.7万人次，较上年增长9.9%（其中内地至香港、澳门和台湾地区航线完成2872.7万人次,较上年增长6.0%）；国际航线完成12626.1万人次，较上年增长13.0%o据从民航资源网获取的2018年中国民航机场吞吐量排名数据显示，2018年我国颁证运输机场数量达到235个，完成飞机起降1108.8万架次，较上年同比增长8.2%。详细数据见下表（表1.12018年中国民航机场旅客吞吐量排名）。其中各机场起降架次更是呈现明显增长趋势,部分国内机场2018年起降架次甚至比2017年同期增长超过百分之百，例如琼海博鳌机场2018年起降架次比同期增长122.90%,广元盘龙机场2018年起降架次比2017年同期增长100.30%,详细数据见下表1.2（表1.22018年中国民航机场起降架次排名取前十）。表IT2018年中国民航机场旅客吞吐量排名机场旅客吞吐量（人次）名次本期完成上年同期同比增速%合计1,264,688,737114786.710.2北京/首都1100,983,29094,393,4545.4上海/浦东274,006,33166,002,4145.7广州/白云369,720,40365,806,9775.9成都/双流452,950,52949,801,6936.3深圳/宝安549,348,95045,610,6518.2昆明/长水647,088,14044,727,6915.3上海/虹桥743,628,00441,884,0594.2西安/咸阳844,653,31141,857,2296.7重庆/江北941,595,88738,715,2107.4杭州/萧山1038,241,63035,570,4117.5表卜22018年中国民航机场起降架次排名机场名次起降架次(架次)同比增速起降架次本期完成北京/首都1614022597,2592.80上海/浦东2504794496,7741.60广州/白云3477364465,2952.60昆明/长水4360785350,2733.00深圳/宝安5355907340,3854.60成都/双流6352124337,0554.50西安/咸阳7330477318,9593.60重庆/江北8300745288,5984.20杭州/萧山9284893271,0665.10上海/虹桥10266790263,5861.20民航业务发展迅速，而各种原因造成的延误也随之增多，尤其是大型机场繁忙时段，机场场面的大面积延误，不仅降低了机场场面资源的运行效率，还增加了航空公司的成本，造成环境污染，而且使管制员的工作负荷加重，存在风险，对空中交通和机场地面交通管理形成了极大的压力。因此研究高效的机场场面调度的优化手段成为当务之急。滑行道负责作为连接停机位和跑道的通道，机场活动区内不仅存在航空器的运行，还存在车辆、人员等诸多可能影响正常运行的不定因素，交通状况相当复杂，管制员为进离港航班分配滑行道需要同时考虑人员、车辆、航班等诸多因素，因此滑行道的利用率很难最大化，造成航班在滑行道以及跑道外等待的延误。即使目前我国部分机场已发布对应停机位的标准滑行路径，但是管制现场大部分情况仍然是管制员人工决策，且机场场面活动具有动态性、复杂性的特点，大型机场航班量高度集中时标准滑行路径难以满足滑行安全与效率的需求。因此，在当前中国民航大发展的背景下寻求可行的优化算法对机场滑行道进行研究具有现实意义。1.2 国内外研究概况针对机场滑行道调度问题，国内外学者已经做出了许多优化研究。包括解决滑行冲突点避让和动态优先级滑行调度的优化等。HenryYKLan等团队网提出一种带有边界约束的路径集合划分的方法调度进离场航空器；GillianLClare团队成员采用了混合整数线性规划模型(mixedintegerlinearprogramming,MILP)和滚动时域相结合的方法解决此问题，提高了MlLP算法的可操作性。国内的研究方面，汪千川在2001年研究记忆遗传算法和模拟退火算法的改进和应用，潘全科在解决车间调度问题上，提出了遗传算法和模拟退火算法的不足，结合采用了遗传退火，并与遗传算法作比较取得了进展。刘兆明研究了基于计算智能的航空调度优化方法研究，通过自适应函数代入遗传算法进行航空路径的优化。在中国研究航空器滑行调度方面，仍然不够成熟，没有讲方法进行规模和系统化,只能根据以往的历史数据进行统计分析，但依赖统计数据缺乏实际操作和系统性理论的支撑。国外学者对机场机动区域内的关键冲突点以及安全风险识别和评估等相关问题进行了较全面深入的研究。2010年NASA由提出了一种“机场地面交通冲突避免”的概念，用以实现机场滑行道等的潜在冲突。S.G.PonnambalamandM.MohanReddy于2003年提出了遗传退火算法多目标混合搜索算法用于排序。在上述文献中，大量地阐述了场面冲突的监视或者规避，对于静态路径规划具有较大的意义；但对随机突发事件引起的时间状态和路径改变，原有方法将不再适用，在科技急速发展的当下，需要对原有算法进行大胆创新与验证。1.3 课题主要研究工作机场调度问题覆盖许多子问题，而地面滑行调度是连接多个问题的枢纽，将进离港航空器与停机等问题连接起来。本文在国内外学者相关研究的基础上，提出一种基于标准遗传算法动态变化交叉遗传的概率，以及与退火算法相结合。利用改进的遗传算法，调整航班优先级序列，达到既能解决标准遗传算法的缺陷也能取得模拟退火算法的有点；根据法律以及相关明文规定的滑行调度约束条件，为滑行道各节点确定各个航班经过的滑行路径。在解决航空器滑行冲突的情况后，将冲突等待时间分散在停机位和滑行道上，更加符合实际运行的情况。第二章机场场面介绍由于我国航空业的发展速度较快，空中交通流量的增长也随之加快，我国民航机场的数量与规模也随之壮大，机场地面运行结构也变得更加复杂多样。本章简单介绍机场场面各单元的基本概念，对机场场面滑行网络进行抽象成有向网络结构模型，对航空器的滑行过程，存在的冲突以及冲突解决策略进行简单描述，简述了多跑道（尤其是平行跑道）运行的相关规定，明确本文问题研究目标。2.1机场场面结构机场场面功能区主要包括飞行区、航站楼、货运站、飞机维修区等区域，本文研究机场场面优化的对象主要是针对机场飞行区内供航空器起降与滑行的跑滑系统，包括航空器的滑行过程，主要涉及包括跑道、滑行道系统。2.1.1跑道跑道是机场上为航空器起飞和落地而划定修建的场地，主要用于航空器的起降、滑跑活动。若有进离场航空器正使用跑道，禁止其他航空器进入同一条跑道。跑道属性有：方向、数量、长度、宽度、运行模式等。跑道设计的方向主要考虑机场的主要风向及风速。跑道长度受诸多因素影响，其中典型影响因素包括机场所处海拔高度、平均温度、跑道道面强度、坡度及设计供起降的最大机型的起降滑跑距离。2.1.2滑行道滑行道主要作用是作为进离场航空器在跑道与其他机场区域之间活动的通道，滑行道将机场各单元连接为一个整体，使机场场面连贯运行，是避免航空器在地面运行产生冲突的重要系统。根据滑行道不同的功能以及分布，滑行道一般可分为主滑行道（也称作平行滑行道）、快速脱离道、绕行滑行道等。主滑行道是指在跑道与停机位之间，航空器主要使用的滑行道，通常也称作平形滑行道。快速脱离道是起连接跑道和主滑行道的功能，沿着跑道分布的通道，主要用以加快跑道使用效率，供落地航空器尽快脱离跑道。2.2机场场面滑行过程滑行道连接跑道和停机位，是机场场面运行的重要元素。机场场面滑行过程主要是进港过程以及离港过程。航空器进港滑行过程。对于进港的航空器而言，获取落地许可后，航空器落地并经由适当的脱离道脱离跑道，脱离跑道后航空器沿管制员指定的滑行路径滑行进位分配的停机位，进港滑行过程结束。航空器离港滑行过程。对于离港的航空器而言，当其在停机位上所有的保障工作完成后，根据管制员的指令进行推出开车或原地开车。当完成开车的准备工作后，飞行员向管制员发出请求滑出的请求，地面管制员经综合分析该航空器所使用跑道以及当时机场场面交通状况，向该航空器发出滑行指令，指令中包含为该航空器指定的滑行路径。航空器沿管制员指定的滑行路径滑行至正确的跑道，并在跑道等待点等待管制员的进一步指令，离港滑行过程结束。在航空器滑行过程中飞行员与驾驶员必须遵守相应的滑行规则，包括：（1）飞行员必须严格按照管制员指定的滑行路径滑行；（2）航空器滑行速度应根据飞行手册或机场相关驾驶规定调整，场面滑行速度一般不允许大于50k叫（3）航空器滑行时应注意保持安全间隔，实际运行之中，由飞行员负责把握与其他航空器之间的间隔；（4）管制员指定滑行路径时应考虑提前规避对头冲突。对航空器的地面滑行过程进行分析，可将滑行路径上存在的潜在冲突归为交叉冲突、追尾冲突以及对头冲突三大类：（1）交叉冲突：两架或多架航空器滑行过程中存在同时经过同一个滑行道道口的情况。在大型繁忙机场，主滑行道一般连接多条快速脱离道，而实际管制工作中，管制员一般会尽可能指挥航空器在平行滑行道上滑行，这种情况下，在平行滑行道上的航空器容易与从快速脱离道脱离跑道的航空器产生交叉冲突。交叉冲突的冲突解除策略一般采用先到先服务原则，即允许先到达滑行道道口的航空器通过节点，另一架后到达的航空器等待一段时间直至满足最小安全间隔。（2）追尾冲突：两架滑行方向相同的航空器同时使用同一段滑行道，而在滑行过程中，存在后机追赶前机发生碰撞的可能。但实际运行中，后机驾驶员会依据情况调整航空器速度自行把握与前机的安全间隔。在构建数学模型时，为规避这类冲突，可以规定链路中的所有航空器滑行速度相同。（3）对头冲突：两架滑行方向相对的航空器同时使用同一段滑行道。实际管制工作过程中，机场场面布局复杂，无法完全理想化分配滑行路径，而滑行路径由管制员临场指定，管制员易遗忘已发布的滑行路径，这就会导致对头冲突的发生。在数学模型中,假定两节点分别为i与/,为规避对头冲突，若已经将ifj的链路分配给一架航空器，则将/'的链路视作0,该链路不可用，并且每架航空器经过某节点后不可重复经过。2. 3机场场面滑行优化问题针对进场航空器是指给进场航空器分配适当的跑道出口脱离跑道，进入滑行道并指定适当的滑行路线使其顺利进入指定的停机位。针对离场航空器是指给离场航空器指定适当的滑行路线使其由停机位出发滑行到所使用跑道的跑道等待点。机场场面滑行路径优化主要研究工作是为进离场航空器分配最优的滑行路径，达到进离场航空器总滑行时间最短的目标。跑道的运行调度也是影响机场场面运行调度的一个重要环节。进场航空器落地后，何时以及从哪个脱离道口脱离跑道，决定了其滑行过程的开始滑行时间、滑行路径的起点。离场航空器滑行至跑道等待点等待的时间决定其使用跑道的最早时间，进入跑道的时间也受前行使用跑道的航空器运行情况影响，因此跑道运行也是离场滑行过程的影响因子。本文将跑道的运行调度考虑进了滑行优化模型，主要针对离场航空器，将连续放行多架航空器以及着陆与起飞航空器之间的安全间隔考虑进模型中，构建滑行道与跑道的联合优化模型。3. 4建立机场场面网络结构模型机场场面系统整体而言是一个相对复杂的结构。本文拟使用网络模型来简化描述机场场面系统的各组成部分，网络由节点、还有节点之间的连线组成，机场场面系统可以抽象理解成机场场面网络图G-(WE),其中V,表示节点集合,主要包括滑行道之间的交叉点、跑道等待点以及脱离道口。E表示链路边，即各段滑行道，链路边的属性包括长度属性、航空器机型限制、滑行速度限制、滑行方向限制等。机场场面结构图简单示例见图2.1。图2-1双流机场场面结构局部示例4. 5多跑道运行相关规定根据跑道的数量，可以将机场分为单跑道和多跑道机场。多跑道机场中，比较普遍的是平行跑道布局，而我国目前所有多跑道机场均采用平行跑道布局模式。根据我国民航局于2004年6月26日开始实施中国民用航空总局第123号令平行跑道同时仪表运行管理规定，平行跑道同时仪表运行分为独立平行仪表进近、相关平行仪表进近、独立平行离场、隔离平行运行等四种模式。本文模型考虑的是双流机场隔离平行运行模式，即其中一条跑道只用于离场，另一条跑道只用于进近。根据跑道间距的条件不同，规定了该平行跑道能够使用的运行模式，总结见下表2.1。表2.1平行跑道同时仪表运行规定平行跑道中心线最小间距/m运行模式<760按一条跑道起降间隔执行760允许隔离运行、独立平行离场915-1035允许相关平行仪表进近>1035允许独立平行仪表进近先后连续起降的航空器之间必须配备一定的纵向间隔，以保证航空器使用跑道的过程中不存在冲突。起降航班之间的安全间隔通常为根据航空器的机型分类而规定的尾流间隔最低标准，根据航空器最大起飞权重划分为重、中、轻三类，见下表2.2o表2.2航空器分类航空器最大准许起飞全重/吨航空器机型7轻型机7-136中型机136重型机（备注：B757尾流归为重型机尾流）若前机为离场航空器，后机为进场航空器，在前机起飞并离开跑道后，后机可以落地；若前，后机均为离场航空器，则需根据机型满足相关的尾流间隔。若前机为进场航空器，后机为离场航空器，只有前机报告其脱离跑道后，后机方可开始进入跑道（实际在流量大的情况下前机落地后，可指挥后机进入跑道等待）；若后机为进场航空器，则需根据机型满足相关的尾流间隔。本文计划采用双流国际机场作为实际案例进行分析，双流国际机场平行跑道02L/20R与跑道02R/20L的跑道中心线间距1525米，根据我国民用航空空中交通管理规则对安全尾流间隔进行规定。前后起飞离场或前后进近的航空器，其雷达间隔的尾流标准见下表2.3：表2.3雷达间隔的尾流标准单位：千米重型机后机中型机轻型机A380-80011.113.014.8重型机7.49.311.1刖机中型机669.3轻型机6662.6本章小结本章对机场场面结构进行了一个简单的分析讨论，尤其是针对飞行区的滑行系统以及跑道系统进行了简单的探讨。关于本文研究的滑行路径优化问题，本章针对滑行过程中航空器应注意的几个规则以及滑行过程中可能出现的三种冲突与如何在算法中解决此类冲突进行了简单阐述，探讨了规避各类冲突的解决方案，提出了构建机场场面网络机构模型，介绍了平行跑道同时仪表运行的运行模式以及运行间隔标准，为构建机场场面滑行优化模型建立理论基础。第三章遗传算法介绍3.1遗传算法的生物学基础【221自然界生物在繁衍生息过程中，遵循着对于自然环境的“适者生存”法则和一定的遗传规律。现代生物进化理论以自然选择学说为核心，其基本观点为：生物的进化是以种群为单位，而不是以个体为单位。生物的进化主要依赖于基因的变异，所以生物进化的实质就是种群基因的变化。通常，自然界中新物种的形成需要以下几个步骤：第一步是基因突变和基因重组，这个过程会形成多种基因组合形式，进而以表现型出现在自然界中，经历第二步的自然选择；第二步就是自然界的“物竞天择，优胜劣汰”过程，能够适应环境的基因得以留存，反之则被淘汰消失；第三步为种群隔离，新生的种群开始与其它种群形成生殖隔离，这起到保护新种群的作用。生物新物种的形成有两种方式：渐变式和爆发式。渐变式是指物种随着时间的推移，通过多代的突变积累，最终形成新的物种，这个过程当中还会有亚种的出现；爆发式与渐变式最大的不同在于没有中间亚种的阶段，一次完成新物种的产生。这种新物种的产生方式一般有三种类型：杂交、染色体结构变化、多倍体化。遗传是渐变式和爆发式两种方式的融合。人类基于遗传这一自然界现象开发出的遗传算法，在解决各种复杂优化问题的过程中，能展现出其独特的优势。3. 2遗传算法的原理概述遗传算法是一种借鉴现代生物进化理论。以生物遗传的规律为框架，属于启发式算法的一种，目前得到的广泛的应用。遗传算法通过模拟优胜劣汰的过程来进行种群的优化，首先利用特定的编码技术，将染色体用字符串的形式表示，之后将这些字符串类比于生物群体然后进行计算。算法过程使用有组织的、随机的字符交换来重新组合一些适应性好的字符串，产生新的、由适应性好的字符串组成的群体。经过这样多次的迭代，最终寻找到一个最优解或者相对最优解。3. 3遗传算法应用于繁忙机场路径优化的优劣势分析遗传算法相比一般的路径规划算法存在优势，是因为遗传算法在寻找最优解时，不仅仅是对状态空间中的节点进行一个个地排除，而且在不同结果组成的集合中寻找最优解。在对所有飞机的路径形成的集合进行寻优时，可以充分考虑效率要求和冲突约束条件，在全局层面上找到最优解，使得单位时间所有航班的总滑行路程（时间）最小，并可以最大程度避免冲突。遗传算法属于启发式算法，但其在全局规划方面的优势，是诸如贪婪算法,模拟退火算法算法所无法比拟的。遗传算法在应对繁忙机场的路径优化时，也存在不足。遗传算法的搜索空间较大、算法较为复杂，所以效率不高。特别是，随着环境中节点的增加或障碍物数目的增加，算法的复杂度和寻优难度会迅速增加。另外，由于繁忙机场场面情况时刻在变化，因此需要进行较高频率的重规划，也会使得系统负担过重，造成效率下降。解决这样的问题，一是在满足安全条件的情况下，要不断尝试简化设计遗传算法，使得算法的体量减小；二是路径规划系统的硬件计算能力要足够强大，才能在较短时间内完成寻优和保证稳定性。3.4遗传算法的实现步骤3. 4.1流程框架使用遗传算法求解目标函数的最优解，通常需要围绕所建立的数学模型，进行遗传算法的操作，简单遗传算法的流程框图如图3.1所示。图3-1简单遗传算法的流程框图5. 4.2染色体编码编码是将遗传算法应用到实际优化问题的第一步，根据所研究问题的性质和要求，可选择不同的编码方式。编码方式的选择，直接影响到之后的选择、交叉、变异等操作，进而影响整个算法的性能。从所求解问题的可行解空间，转化为能够被遗传算法处理的搜索空间这一过程，叫做编码。路径优化类问题常见的编码方式有二进制编码和实数编码。（1）二进制编码二进制编码方法是遗传算法中最常见的编码方式，它使用由二进制符号0、1组成的二进制字符串表示种群中个体的基因，每个字符串对应一个基因型。例如：IWxW100,精度为1。m表示二进制编码长度，m的值取决于式：2m-l100（精度为1）2m-l,所以此例中取m=70则字符串OloOlOo表示一个基因,其对应的解空间中的x=36o二进制编码具有如下特点：编码与解码简单易行，容易实现交叉与变异操作，但当字符串的长度较大时，会使遗传算法的搜索空间急剧增大。另外，它不能像实数编码那样直观地反映出所求问题本身的特征和性质。（2）实数编码对于一些拥有较大搜索空间、较多变量约束条件并且精度要求较高的优化问题，使用二进制编码表示基因时将会有上述的不利之处。这种情况下实数编码更为适用。实数编码使用一定范围内的实数来表示种群中个体的基因型，其个体的编码长度只取决于数学模型中变量的位数。3.4.3适应度函数的选择遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传机会的大小。如果说利用自然选择从一群普通羊中筛选出能够适应高原气候的羊便是遗传算法优胜劣汰的原理，那么每只羊对于高原环境的适应能力就用适应度来表示，在本文用适应度函数表示。直接影响遗传算法的收敛速度以及能否找到最优解或者近似最优解，主要取决于适应度函数（fitnessfunction）的选取,因为遗传算法在进化搜索中仅考虑种群内部的各种约束，外界因素影不纳入到实际计算中，所以适应度函数就成为了影响整个算法的主要依据，利用种群每个个体的适应度来进行搜索。因为适应度函数的复杂度是遗传算法复杂度的主要组成部分,所以适应度函数的设计应尽可能简单,使计算的时间复杂度最小。为了描述在遗传算法中各个体的主要指标，就会引入适应度函数。根据对环境适应度的大小，对种群中个体进行优胜劣汰。从生物学角度讲,适应度相当于达尔文进化论提出的“生存竞争、适者生存”的生物生存能力。将优化问题的目标函数与个体的适应度建立映射关系,即可在群体进化过程中实现对优化问题目标函数的寻优。适应度函数也称评价函数，是用于区分群体中个体优劣的标准，总是非负的，到最后函数会进行收敛，取决于适应度函数以及迭代次数的选择，结果越收敛越合理。最后，算法应构建合理的适应度函数来评估个体的解决方案的利弊，适应度函数针对不同的问题有不同的定义。有必要根据特定问题来构造合适的适应度函数。3. 4.5遗传操作（一）选择选择操作的目的是从种群中挑选出优秀的个体，使它们保留下来，将优秀的基因遗传下去。选择操作的方法是基于上述构造的适应度函数，得出个体的适应度值，依据适应度值对种群中的个体给予评价，挑选出优秀的个体保留并遗传到下一代。适应性强的个体将有更大的概率将基因遗传给后代，这是符合达尔文的适者生存原则的。本文中使用轮赌盘选择法实现选择操作。每一个个体进入下一代的概率与其适应度呈正相关,适应度值越高的个体，被选择保留并进入下一代的概率就越大,从而做到每一代新个体相比于上一代有了优化，反之重新加入循环，优化后在输出。（二）交叉标准遗传算法中起决定性作用的遗传操作就是交叉操作。新的个体的获取可以由种群之中个体的交叉操作得到，并使之组成新的种群。随机配对的个体在群体的基础上，配以一定概率（通常交叉概率），一旦出现在赶驴区间范围，则在它们之间交换的染色体，成为新个体的染色体。因此，新个体组合了上一代个体的基因。但决定交叉率时应当注意其大小，交叉率过大，计算过程就成为了纯粹的随机操作。本文采用双切点交叉法，实现此操作的步骤为：（1）在种群内随机挑选两个个体进行配对；（2）基于交叉概率Pc,决定是否进行交叉操作，如果是，执行第三步；（3）在相互配对的两个个体的染色体（编码串）中，各随机设置两个交叉占“、,（4）在两个人设定的交点之间的部分染色体交换。假设I、11为两条染色体，对其交叉操作可以得到III、IV两条新染色体，具体示意如下：I：125789III：124569II：234568IV：235789（三）变异在自然界的生物变化是由于该基因片段的变化。在遗传算法中，相应的变化是在串结构数据特定值的变化。变异操作群体中的一个随机选择的个体，并且是以一定的概率（突变的通常的概率）来改变某一基因或几个基因与其它等位基因。不同于交叉概率，变异的概率一般很低，因为在本质上是一种生物变异的可能性。变化提供了新的个人发展机会。同交叉流程，变异率应该更小，否则算法会成为单一的随机选择操作。本文依据一定的变异概率Pm来决定上一步产生的新染色体是否发生变异。如果染色体被选中进行变异，则随机产生两个指定的染色体交换位置，互换基因（单个实数），例如有一条染色体为123456,随机产生两个交换位置1和4,则变异后的染色体为423156o3.4.6终止条件运行遗传算法解决优化类问题时，算法不会自动停止，需要设置一个用来终止算法无休止进行搜索的条件。这个终止条件可以是以下几种。（一）一个设定好的个体适应度值，当种群中个体的适应度值与给定值相同时，算法停止搜索；（二）当遗传算法中同时存在种群适应度和个体适应度时，当两者都稳定在一个值附近时，算法即停止；（三）遗传算法的寻优搜索是一个不断迭代的过程，为使得算法求解在某个时刻终止，可以设定迭代的次数。一般设置为100-150代，这种方法是在遗传算法寻优问题中常用的。3.5遗传算法的运行参数在基本的遗传算法，以下四种工作参数需要被预先设定，即M,T,PC,PMoM为群体大小，这个值代表群体中拥有个体的数量，常用取值为2（M（X）;T为遗传算法的迭代终止代数，当算法迭代代数达到这个值时，算法自动终止，常用取值为100-150；PC为交叉概率，常用取值为0.4-0.99,本文采用概率区间（0.55,0.75）；Pm为变异概率，常用取值为0.0001-0.1,由于概率过小，如要达到预期效果计算量会过大，所以本文根据实际计算量适当增加了变异率，采用区间（0.1,03）o第四章基于改进遗传算法的滑行路径优化调度4.1 模型建立4.1.1 滑行道调度模型航班滑行调度是在保证滑行安全前提下为每架航班制定滑行路径及到达其路径上交叉点的时间，使得总滑行时间最短或总经济损失最小。本文根据机场场景的布局和飞行的滑行特性，我们可以抽象机场滑行道布局到由点和圆弧的网络结构图中，由G=(V,E)表示。将飞机分为进场和离场两类，如果有一架进场飞机，则终点为点Al,A2,A3,起点为脱离道口点1；若有一架离场飞机，则终点为跑道入口点10,起点为点GLG2,G3o其中各路段距离表示为进场路段：(1,2)=100,(2,3)=200,(2,4)=300,(4,5)=500,(5,6)=200,(4,7)=200,(5.8)=200,(6,9)=150,(3,7)=300,(7,8)=500,(8,9)=300,(7,A1)=300r(8,A2)=500,(9,A3)=400,离场阶段：(10,11)=1001(11,12)=100,(11,14)=200,(14,17)=400,(12,13)=200,(13,15)=200,(13f14)=100,(15,16)=200,(16,18)=300,(16,17)=100,(18,19)=500,(15,G1)=300,(18,G2)=200,(19,G3)=400,约束条件为：Eti,ut,uLt,ulVuR,i=1t2,n(4-2)Et,v=Eti,u+du,vVimV(u,v)R,i=1r2,n(4-3)1.tlv=Ltiu+duvV,nV(u,v)Ri,i=1,2-,n(4-4)SijfU=(tv-tu)/du,v*d(u,v)RRj,ijF,iJ(4-5)yj.utj.u>ylj,u(tiu+Sij,u)i,jFtij,uRlRj(4-6)yij.u-yij,v=Oi,jF,V(u,v)RiRj(4-7)yij,u-yj,v=OVitjF,(u,v)Rr(vtu)Rj(4-8)yw=0或1VijF,u(RiRj)(4-9)F=1,2n)为飞机的集合，F"'F(进场降落飞机集合)，LF(离场飞机集合)；R=R,R2.Rn,Ri表示飞机i的滑行路线；Rl是由一系列点组成(VoV,.vk,),vijV(j=1,2-,k),并且(vij,v,j+1)E(j=1,2.,kl-1);(u,v)Ri表示弧(u,v)是飞机i的滑行线路之一；uR:点U在飞机i的滑行线路上；Du：点U和V之间的距离；Vlin(i=1,2.n):飞机i的最小速度；VL(i=1,2.n):飞机i的最大速度；Ti.uR*(iF,uR):飞机i到达点U的实际时间；Etl.uR+(iF,uJ):预计飞机i到达点U的最早时间；1.ti.uR+(iF,uR):预计飞机i到达点U的最晚时间；二元变量加户!表示飞机i在j之前到达点U,否则=0；Si,u(ijF,u(RDR)表示飞机i和j到达点U的最小时间间隔;目标函数Minimize(4必LU)(4-o)ieF,'uk，U|ti,uk表示飞机i到滑行终点k的时间，tiM表示飞机i第一个点开始滑行的时间。目标函数求所有航空器滑行时间总和，描述所有个体飞机总的滑行时间最短;(4-2)式表示，这架飞机的实际到达时间必须是最早到达时间和最迟到达时间之间；公式(4-3)和(44)分别确定飞机到达的最早和最晚时间。两架飞机ij的飞机之前和之后的到达之间的最小时间间隔由(4-5)表示。当两个飞行器滑行前进，后退，有一定的安全距离，必须按照有关规定出租车保证。否则，会发生危险，而不同类型的飞机之前和之后的安全距离不相同，一般安全距离为d=50米:；式(4-6)确保两架飞机滑行在同一条线路上时保持一个安全的距离；式(47)确保任意两架飞机不会相互超过；式(4-8)确保飞机之间不会相遇；式(4-9)表示变量y只能在。和1中取值。4.1.2标准遗传算法过早收敛及改进猜想早熟收敛是标准遗传算法的一种现象。由于本文采用赌轮盘的方式筛选个体，当算法前期出现超级个体时，即该个体对于环境的适应度大大超过了当前种群的平均适应度，从而导致在赌轮盘计算时，该类个体被筛选的概率大大增加，进而种群多样性提早且迅速降低，种群进化能力急剧丧失。以上现象发生，就会导致算法提前收敛于局部最优解。为避免或者减少此类现象发生，本文在一定程度上引入模拟退火算法(SA)的思想。标准遗传算法在对种群全局优化的选择能力较强，但存在“早熟收敛”问题使得种群优化容易偏向于取得相对最优解，模拟退火算法正好可以弥补标准遗传算法“爬坡难”的问题，本文尝试将两种算法结合以解决滑行道调度优化问题。根据模拟退火算法实际使用情况，本文对SA算法原理仅做简单介绍。SA灵感源于将固体加热至足够高的温度，然后对加热固体进行自然冷却，然后记录其内部变化的原理。加热时，固体内部受热导致粒子逐渐无序，温度升高，固体内能增加，而当缓慢冷却，内部颗粒逐渐变得有序，每个温度达到平衡，最后在常温下达到基态，内能降低到最小。随着温度T的不断下降，在算法取得最优解或者相对最优解时，SA算法会想右跳跃部分取得新解，并且以一定概率接收这个新解，即局部最优解以概率方式跳跃并最终变为全局最佳或相对最佳。D-EIkTP=e（4.11）图4-2标准遗传算法早熟收敛示意图4.L5模型改进采用模拟退火算法指数型函数的思想，即本文实际没有使用到模拟退火算法关于温度自然降低导致结构突变的计算方法，而是借鉴了