离场航班推出时间预测方法研究.doc

南京航空航天大学毕业设计离场航班推出时间预测方法研究 学生姓名： 米佳树 学 号： 071030230 学 院： 民航学院 专 业： 空中交通管理与签派 班 级： 0710104 指导老师： 彭瑛二零一四年六月南京航空航天大学本科毕业设计（论文）诚信承诺书 本人郑重声明：所呈交的毕业设计（论文）（离场航班推出时间预测方法研究）是本人在导师的指导下独立进行研究所取得的成果。尽本人所知，除了毕业设计（论文）中特别加以标注引用的内容外，本毕业设计（论文）不包含任何其他个人或集体已经发表或撰写的成果作品。作者签名： 年 月 日 （学号）： 离场航班推出时间预测方法研究摘 要 随着国民经济持续保持强劲增长势头，我国航空产业得到了蓬勃发展。然而由于飞行流量的不断增加，繁忙机场的终端区经常发生严重拥挤现象，显著影响了航班正常飞行，造成大量航班延误，给航空公司和乘客形成了巨大的经济损失，也给终端区航班安全飞行带来了隐患。近些年，到场航班的调度算法研究比较成熟，相比之下，离场航班的调度问题特别是相关算法的研究较少，因此研究离场航班推出时间的预测显得格外重要。 本文基于双码自适应遗传算法，采取一种新型单亲变异遗传算法，重点解决多滑行道单跑道情况下航空器离场排序问题，并运用相关的数学工具和实验手段设计离场航班推出时间优化的航班排序，研究和分析离场航班推出最小总时间，得到离场排序问题的全局最优解。关键词：双码自适应，遗传算法，变异，离场航班排序 The flight departure time prediction method research Abstract With the continued to maintain strong growth momentum of the national economy, Chinas aviation industry to flourish. However, with the increasing of air traffic flow, severe congestion occurs frequently in terminal area and busy airports, significantly affect the flight, resulting in a large number of flight delays, causing a huge economic losses to the airlines and passengers, but also bringing terminal area hidden trouble. In recent years, research on scheduling algorithms to arriving flights tends more mature,compared to departure flight scheduling issues, so the research of the departure flight time prediction is particularly important. This paper bases the double code adaptive genetic algorithm, adopts a new methods of single parent variation genetic algorithm,focused on solving the problem of multi taxiway runway case in departure aircraft sequencing problem,and use the mathematical tools and experimental methods related to the best design of departure flight push time optimization genetic algorithm, then analyze the departure flight time to minmize the total time, get the global optimal departure sequencing problem.Key words:Adaptive dual code; Genetic algorithm; Variation; Departure flight sequencingII 目 录摘要.IAbstract.II第1章 引 言.1 1.1 研究的背景和意义.1 1.2 国内外研究状况.11.2.1 国外研究情况.11.2.2 国内研究情况.2 1.3 本文研究内容.21.3.1 本文组织结构.21.3.2 本文拟采用的方法.2第2章 离场排序问题描述及其数学模型.2 2.1 离场排序问题的描述.2 2.2 离场排序数学模型的介绍.3第3章 遗传算法原理的介绍.4 3.1 基本的遗传算法的描述.4 3.2 遗传算法的基本实现技术.53.2.1 编码方法.53.2.2 适应度函数.63.3.3 选择算子.63.3.4 交叉算子.73.3.5 变异算子.73.3.6 遗传算法的运行参数.8第4章 遗传算法在离场航班排序中的设计.8 4.1 算法设计.84.1.1 编码方法设计.94.1.2 交叉算子设计.104.1.3 变异算子设计.10 4.1.4 选择算子.114.1.5 适应度函数.134.1.6 全局收敛性.134.1.7 算法中的其他辅助设计.13 4.2 算法设计步骤小结.14第5章 离场调度与仿真.15 5.1 仿真条件.15 5.2 仿真结果.16第6章 总结与展望.19参考文献.20致谢.21附录.22第1章 引 言1.1 研究的背景和意义 随着国民经济持续保持强劲增长势头，我国航空产业得到了蓬勃发展。然而随着飞行流量的不断增加，繁忙机场的终端区经常发生严重拥挤现象，显著影响了航班正常飞行，造成大量航班延误，给航空公司和乘客形成了巨大的经济损失，也给终端区航班安全飞行带来了隐患。航班进离场排序越来越引起人们的重视。特别是随着空中交通的飞速发展，国内外空中交通拥挤现象日趋严重并且造成了巨额损失，从而使得这方面的研究变得十分迫切。其中，到场航班的调度(到场航班在降落机场上空的排序等)算法研究比较成熟，相比之下，离场航班的调度问题特别是相关算法的研究较少，因此研究离场航班推出时间的预测显得格外重要，其主要体现在以下三方面： （1）降低航空公司的经济损失。离场航班推出时间主要的优化目标就是为航班提供合理的离场顺序，最大程度的降低航班的延误损失。 （2）降低管制员的管制负荷和工作复杂度。优化排序的方案为管制员提供了航班离场顺序的咨询，辅助管制员对航班进行管制，有效的减少管制压力。 （3）合理的利用机场、跑道容量，提高机场运营效率。科学合理的离场方案在保证安全的前提下充分利用起降时隙，增大单位时间内机场跑道的航班起降量。 由此可见，研究和分析离场航班推出时间预测方法对于改善繁忙机场离场拥堵的现象，缩减总的离场耗时十分必要。1.2 国内外研究现状1.2.1 国外研究情况（国内外合并起来，并用上标表示引用） 在美国，对于离场航班调度的问题，Shumsky于1997年曾提出了一个机场容量和滑行迟滞的模型用于预测离场航班时间。2000年，Bolender提出了一种启发式算法用于解决离场调度的问题，但却无法保证解的最优性。2009年，Cautam等建立了一个混合整数线性规划模型用于机场离场的规划，具有一定的通用性，但仅限于单跑道机场或多跑道运行模式下仅用于起飞的跑道，且解算不能满足实时性要求。2010年，Ioannis等建立了一个机场离场过程分析动态排队模型，将跑道配置，气象条件，停机坪位置和起飞队列长度作为模型的输入，相应得到场面的拥塞水平及航空器预计的滑出时间。但该模型仅能给出单一的统计计算结果，未考虑进离场航班流的相互影响。1.2.2 国内研究情况 近年来随着我国空中交通运输的迅速发展，国内也陆续开展了有关管理方面的研究。2004年，王来军、史忠科针对航班的离场排序问题，通过建立相应的离场排序优化模型，采用双码自适应遗传算法，有效的减少离场耗时。王来军、胡大为等人继续研究，于2009年通过建立一种新型启发式算法，有效的解决空中交通运输中的航班离场排序的问题。2013年，张明、周毅等人在前人的研究基础上，分析各种调度规划方法的优缺点，针对不同的机场跑道提出了相应的离场规划方法。1.3 本文研究内容1.3.1 本文组织结构 本文通过参阅国内外对于离场航班时间调度的多种预测方法，重点研究多滑行道单跑道情况下的离场航班推出时间。首先，了解并熟悉离场航班排序问题的数学模型，进一步通过运用遗传生物学的遗传算法，解决实际航空离场航班推出运行的方案，最后通过仿真模拟得出优化的离场航班推出排序。1.3.2 本文拟采用的方法 本文主要基于求解模型的双码自适应遗传算法，通过给出相应的技术描述和具体的算法过程，最后应用到民航实际中，并对算法进行仿真验证。从结果看出，改进后的算法设计合理，可以有效地缩短总的离场耗时，给出优化的离场航班排序，保证全局解的最优。第2章 离场排序问题描述及其数学模型（每一章另起一页，一章内容只有2页太少）2.1 离场排序问题的描述 离场的航班是指航班加入航线阶段前的整个过程,包括准备起飞过程、飞离机场过程和飞离终端区三个过程。我们把离场操作分为地面操作和空中操作两部分,本文将重点讨论地面操作部分。地面操作主要涉及航班起飞前的两个阶段排序问题。本文中的研究对象为多条滑行道、单跑道条件下，多个航班离场的队列,每队航班各占一个滑行道,如图1所示。 离场航班调度的实质就是对一定时间段内的离场航班进行优化排序,使得跑道被充分利用并能够有效的减少航班在机场上空的滞留。显然,每个离场航班都要对应一个起飞跑道,一条滑行路线和一个离场时段。通常,有两点需要确定,即滑行路线的分配和随后航班的离场排序。于是,我们可将离场航班的优化排序问题分为两个阶段来描述:（1）自航班抵达机坪的分配点起,安排航班进入离场队列和滑行路线。该阶段问题的解决一般基于机场的相关规定和统计数据,并依赖于地面管制员的经验,因此基本上属于人工操作安排,本文不予深究。（2）离场航班分多个队列分别抵达跑道的起飞端,航线管制员对航班重新进行优化排序。这一阶段问题的关键在于,在跑道离场端,如何从多个滑行道起飞队列的所有离场航班中选择最先离场者及后续航班离场的顺序，以使离场航班所消耗的总的离场时间和最小。这个问题可以通过建立排序模型、设计排序算法来解决。2.2 离场排序数学模型的介绍 建立目标函数是使得所有等待起飞的航班所消耗的离场时间之和最小： （2-1）其中,表示机场上正在等待起飞的航班总数,表示给第架航班的分配离场时刻,表示目前正在跑道上的航班的离场时刻,表示最后一架航班的分配离场时刻。 相邻的离场航班应该满足规定的尾涡间隔和纵向间隔，所以：， （2） 并且，为了谋求离场消耗时间和最小，各个航班都尽可能连续起飞，所以目标函数可进一步修订为： （3） 航班离场服从于先到先服务原则，所以每个滑行道上的航班队列都应该满足：， （4）其中,分别表示第条滑行道上的航班队列中相邻航班中的后机和前机的分配起飞时刻,表示第队的航班数目。假设共有条滑行道(则对应个队列),因此成立。另外。约束条件(4)同时也保证了在先到先服务原则下离场航班遵循的一条重要性质:性质 1 直至飞离机场,各队航班的相对顺序保持不变。 进一步的，有如下定理：定理 1 根据排列组合的知识，条滑行道对应的跑道起飞端的离场队列能有种的可能。其中，表示第队航班的数目，表示所有航班数的总和。（没有讲完）第3章 遗传算法原理的介绍(并入第二章)3.1 基本的遗传算法的描述 遗传算法是近几年发展起来的一种崭新的全局优化算法,它借助生物遗传学的观点,通过自然选择、遗传、变异等作用机制,实现各个个体的适应性的提高，体现了自然界中“物竞天择、适者生存”进化过程。因此，遗传算法已被成功用于解决任务的最优化问题中。 遗传算法最早于上世纪60年代由J.H.Holland提出。Holland认识到生物的遗传自然进化现象与人工自适应系统非常相似，提出在研究人工自适应系统时，可以借鉴生物遗传的机制，以群体的方法进行自适应搜索，并充分认识到交叉、变异等运算策略在自适应系统中的重要性。70年代，Holland教授提出了遗传算法的基本定理模式定理，从而奠定了遗传算法的理论基础。经过后人的不断发展，才有了今天比较完善的遗传定理。 遗传算法的基本流程如图2所示。可以看出遗传算法的本质，即通过选择算子将当前群体中的优良模式遗传到下一代中去，通过交叉算子进行模式的重组，再通过变异算子进行模式的突变。通过这些遗传运算，适应度较差的模式会逐步的被淘汰，适应度较好的模式会逐步被遗传和进化，最终达到问题的最优解。 3.2 遗传算法的基本实现技术3.2.1 编码方法 编码是应用遗传算法时首要解决的问题，也是设计遗传算法的一个关键步骤。编码方法除了决定染色体排列形式之外，还影响到交叉算子、变异算子等遗传算子的运算方法。由此可见，编码方式在很大程度上决定了如何进行群体的遗传进化运算以及遗传进化运算的效率。一般多采用二进制编码的方式，使用由二进制符号0和1组成编码符号集0,1，它所构成的个体基因型是一个二进制编码符号串，方便问题的解决。3.2.2 适应度函数 遗传算法中使用适应度这个概念来度量群体中各个个体在优化计算中有可能达到或接近于最优个体解的程度。适应度高的个体遗传到下一代的概率比较大，适应度低的个体遗传到下一代的概率就比较小，度量这个适应度的函数就是适应度函数。 需要注意的是，在遗传算法运行的初期阶段，群体中可能会有少数几个个体的适应度相对于其他个体来说非常高。若按照常用的比例选择算子来确定个体的遗传数量时，在种群规模较小的极端情况下，新的群体完全可能由这些少数个体组成。为了克服这种现象，我们在遗传算法运行的初期，对适应度较高的个体进行控制，降低其适应度与其他个体适应度的差异，从而限制其复制数量，维护种群的多样性。又例如，在遗传算法运行的后期，群体中所有个体的平均适应度可能会接近于群体中最佳个体的适应度，从而是竞争过程缺乏竞争，影响遗传算法的效率。所以在遗传算法的后期，对个体的适应度应当进行适当的放大，扩大最佳适应个体适应度与其他个体适应度的差异，以提高个体的竞争性。3.3.3 选择算子 遗传学中的选择算子用来对个体的优胜劣态进行操作，适应度较高的个体被遗传到下一代的概率比较大，适应度较低的个体被遗传到下一代的概率相对较小。一般多采用最优保存策略进化模型来进行优胜劣汰操作，即当前群体中适应度最高的个体不参与交叉运算和变异运算，而是用它来替换掉本代群体中经过交叉、变异等遗传操作后所产生的适应度最低的个体。具体操作过程如下：（1） 找出当前群体中适应度最高的个体和适应度最低的个体。（2） 若当前群体中最佳个体的适应度比之前总的最好个体的适应度还要高，则以当前群体中的最佳个体作为新的迄今为止最好的个体。（3） 用迄今为止的最好的个体来替换掉当前群体中的最差个体。 经常采用的是一种比例选择算子，实际上是一种有退有还的随机选择，也叫赌盘选择，因为这种选择方式与赌博中的赌盘操作非常相似。图4所示为赌盘示意图。 整个赌盘被分为大小不同的一些扇面，分别对应这一些价值不同的赌博物品。当旋转着的赌盘自然停下来的时候，其指针所指扇面上的物品就归赌博者所有。虽然赌博的指针具体停在哪一扇面无法预测，但指针指向各个扇面的概率却是可以估计的，它与各个扇面的圆心角成正比，圆心角越大，停在该扇面的可能性就越大；圆心角越小，停在该扇面的可能性就越小。与此类似，遗传算法中，整个群体被各个个体所分割，各个个体的适应度在全部个体的适应度之和中所占比例大小不一，这个比例值瓜分了整个赌盘盘面，他们决定了各个个体被遗传到下一代的概率。3.3.4 交叉算子 交叉重组是遗传与进化过程中产生新个体的主要操作过程。交叉，即将群体P（t）内的各个个体随机搭配成对，对每一对个体，以某个概率（交叉概率）交换他们之间的部分染色体。交叉运算的重点在于确定交叉点的位置和如何进行部分基因交换。3.3.5 变异算子 变异，即对群体P（t）中的每一个个体，以某一概率（变异概率）改变一个或某一基因座上的等位基因。虽然交叉运算是新个体产生的主要方法，决定了遗传算法的全局搜索能力，但变异运算作为产生新个体的辅助方法，也是必不可少的一个过程，因为它决定了遗传算法的局部搜索能力。只有交叉算子与遗传算子的相互配合，共同对搜索空间进行全局搜索和局部搜索，才能得到最优化的搜索结果。另外，变异算子用新的基因值替换原有的基因值，从而改变个体的遗传编码，便于维持群体的多样性，防止出现早熟现象。3.3.6 遗传算法的运行参数 遗传算法中需要选择的运行参数主要有个体编码串长度、群体大小、交叉概率、变异概率、终止代数等。这些参数的设置对遗传算法的进行有着重大的作用，需要谨慎选择。（1） 编码串长度。一般用二进制编码表示个体。（2） 群体大小。群体大小表示群体中所含个体的数量。（3） 交叉概率。交叉操作作为遗传算法中产生新个体的主要方法，通常交叉概率一般取值较大。但若取值过大，会破坏群体中的优良模式，对以后的遗传计算产生不利的影响；若取值过小，产生新个体的速度较慢。一般的取值范围为0.40.99。（4） 变异概率。若变异概率取值较大的话，虽然能产生较多的新个体，但更多的会破坏掉许多较好的模式；若变异概率取值较小的话，则变异操作产生新个体的能力和抑制早熟现象的能力就会变弱。一般的取值范围为0.00010.1。（特殊情况除外）（5） 终止代数。终止代数是遗传算法运行结束约束条件的一个参数，它表示运行到指定的进化代数之后就停止运行。一般的取值为1001000。第4章 遗传算法在离场航班排序中的设计4.1 算法设计 基于上述离场问题的数学描述和基本遗传算法的介绍，我们来设计排序算法，控制在跑道离场端如何从多个起飞队列的第一架航班中选择最先离场者。以使离场航班所消耗的总的离场时间和最小。为了简单起见，我们研究两队列离场的情形,并称两队列为“分队”,最终合并形成的离场队列为“总队”。根据定理1,如果采用枚举算法,离场排序问题的计算量增大，所以当离场航班数量较大时,使得问题的求解效率低下。所以,本文基于求解问题双码自适应的遗传算法采取一种新型的遗传算法解决离场航班推出总时间。“双码”是指仅采用两种类型(“1”，“2”)符号的编码方法；“自适应”则是针对交叉概率和变异概率的设置方法而言。4.1.1 编码方法设计 在一般的用遗传算法处理的问题当中，绝大部分的基因序列的编码都是采用“0”“1”的随机数字序列来表示，但是由于始终要保持各分队所属航班的相对顺序不变，又要满足交叉或者变异生成的总队满足此约束条件并且具有实际意义，我们通过比较分析，认为这种的编码方式过于简单，对于航班顺序问题的处理不够灵活，信息量存储太小，并且变异和交叉等环节算法的设计困难，所以，我们采用结构体这种复合的数据结构来保存飞机队列的信息。如图3所示，描述了一个飞机队列基因GENE的数据结构，它是由四个变量组合而成的: (1) s_QUENE是一个结构体数组，代表飞机的“总队”信息，即一种可能的飞机的离场总序列，数组的大小等于总共的飞机数，数组当中的每一个元素都是结构体类型，这个结构体包含两个属性信息，分别数flight_type和flight_quene，分别表示该飞机的大小类型和该飞机所处的分队序号； (2) s_MARK是一个double类型的变量数据，代表该飞机的“总队”离场需要的总时间和； (3) s_GRADE是一个double类型的变量数据，代表该基因序列在种群当中的得分评价，得分越高，表示该基因序列最优可能存活下来，在进行自然选择的时候，有很小的概率能够被筛选到； (4) s_KILLRATE是一个double类型的变量数据，代表进行自然选择即后面所要阐述的转盘赌过程当中对种群当中所有个体的得分进行规则化后的一个数据，根据这个数据，来随机的选中将要被淘汰的个体。 每一个GENE型的变量，都代表了一种可能的调度方案，遗传算法的关键在于对一个GENE型的数组进行交叉、变异、转盘赌等过程处理，使得数组的数据不断的更新、变化，最后得到一个比较满意的GENE，即可以接受的调度方案。图 3 基因结构体框架4.1.2 交叉算子设计 由于本文在先前的遗传算法上进行了改动，采用大变异概率而不选取交叉概率，类似于生物学中的单亲无性繁殖过程，因此无需设计交叉算子。 4.1.3 变异算子设计 在进一步的根据对航班排序问题的具体分析，认为交叉算子不适合处理该问题，考虑到遗产算法也是从生物进化的规律得到的灵感，认为自然界中存在不通过父代基因的交叉而产生子代基因的物种，他们的进化只通过自身的变异，也许这种物种没有性别这一特征。而从算法程序的本质上讲，交叉和变异算法对基因序列的处理都是为了过得更新的基因序列，两种算法只是保证了算法种类的丰富性，以及避免了单一算法的局限性。所以，本遗传算法处理程序只设计了变异算法部分，实际程序的运行效果也比较满意。 变异算法的本质是交换原有基因序列当中的元素位置，产生新的基因。我们这个算法函数每被调用一次，就会将原来基因中的一个元素随机选择一个位置进行插入操作，通过多次进行变异操作，使基因中的多个元素进行变异，使基因产生较大的变化，更加容易找到最优基因。 现举例说明变异算法如何进行，如图5所示，为一种飞机“总队”序列，其中方形表示飞机分队1中的飞机，三角形表示飞机分队2中的飞机，该飞机队列中总共有15架飞机，其中分队1中飞机有7架，分队2中飞机有8架。我们通过一系列的随机操作来产生变异后的基因序列。步骤如下： (1)我们选择要移动的元素所在的飞机分队，即产生一个在12之间的随机数，为方便说明，假定这一过程选中的飞机分队为2； (2)在选中的分队元素当中选择可以移动的元素，我们选中的分队为分队2，在图5当中需要移动三角形，为了保持各个分队的飞机顺序不变，被移动的三角形的可插入的范围是一定的，以4号元素为例，它可插入的位置为6号元素之前，不能插在6号元素之后，否则，飞机分队的顺序将会改变，4号元素可以选择的所有位置为：1之前，1、2之间，2、3之间，3、5之间，5、6之间，共5个，再看9号元素，由于这个元素与分队2中的8号、10号元素相邻，所以9号元素不可移动。针对图5当中的飞机序列，我们得到可以移动的元素代号为：4、6、8、10、12、14，总共6个，通过产生一个16之间的随机数，我们选中要移动的元素； (3)我们再选择选中的元素可以移动的位置，还是以元素4为例，上面分析出元素4可以移动的位置有5个，通过产生15之间的随机数，得到元素4将要插入的位置，假定选择第1个位置，即元素4将要插在元素1之前； (4)我们得到变异之后的基因序列。 整个过程中，我们并没有改变各个分队的顺序，即ag，AH的字母顺序没有发生改变，特别地，为了保证程序的正确性，以及变异产生的基因序列复合要求，特别的加入基因序列检查函数，能够检查新得到的基因序列是否满足顺序相对不变的条件。图 5 航班变异算法的模型4.1.4 选择算子 本文采用轮盘赌进行自然选择的过程。对于一个种群，为了得到更优基因，必须进行自然选择，淘汰掉一些不符合要求的基因，但是较优的基因和较差的基因都应该有一定的几率被选中，所以设计了转盘赌算法来对种群个体进行选择。 转盘赌算法的设计思想是根据种群当中的所有的个体的评价得分即s_GRADE的比重，对某一个常数NUMBER进行分配，通常设置NUMBER为1000即可。首先求出种群中每个个体的s_GRADE，；然后，计算种群当中的总的评价得分；然后，计算每个个体被淘汰的概率值。如图6所示，根据每个个体的s_KILLRATE值，分配一个圆盘的面积，将其转换成坐标轴之后，形成一个个01000的区间，通过产生一个01000的随机数，判断随机数所落的区间，决定那一个个体被淘汰掉，由于算法的设置，较优的基因所占的面积较小，较差的基因所占的面积较大，因此有利于保留较优基因。通过转盘赌算法，缩减种群个体数目到一定数量，然后再开始下一次的进化。图6 转盘赌个体基因存活率示例 选择算子的具体执行过程可描述为: （1）先计算出群体中所有个体的适应度的总和。 （2）其次计算出每个个体的相对适应度的大小，它即为各个个体被遗传到下一代群体中的概率。 （3）最后再使用模拟轮盘赌操作来确定各个个体被选中的次数。 可以看出比例选择算子其基本思想是：各个个体被选中的概率与其适应度大小成正比。设群体的大小为，则个体的适应度为。则个体被选中的概率为： 也就是说，适应度越高的个体被选中的概率就越大；适应度越低的个体被选中的概率就越小。4.1.5 适应度函数 适应度函数为： （5）其中，为第架航班和第航班的最小时间间隔，。所以就是总的最小离场耗时。4.1.6 全局收敛性 为了保证遗传算法的收敛性,在遗传算法中实施了最优个体保留策略。即考虑到解的可行性,同时对最优个体和最优可行个体进行保留。具体做法为:将第0代中得到的最优个体和最优可行个体保留起来,从第1代开始,将每一代中得到的最优个体和最优可行个体同前一代的保留个体进行比较,如果当前代的最优个体和最优可行个体优于前一代保留个体,则其将成为当前代的保留个体,否则将前一代保留个体作当前代保留个体。4.1.7 算法中的其他辅助设计灾变算法设计 对于一个函数，在一个区间内存在着一个最值，但是却可能存在着很多个极值，遗传算法函数非常适合于寻找局部区间的最值，也就是极值问题，这就容易使得在寻找最值时容易陷于某个极值区间而无法跳出，为了避免这种情况，就要设法改变输入变量的位置，所以添加了灾变算法。在大自然当中，其实也存在着灾变这种情况，比如恐龙等物种的灭绝，正因为这样可能才产生了更适宜地球环境生存的生物。该算法的设计思想是从物种的第1代开始，就预测下一次出现比当前找到的最优基因更优的基因所需要的代数FORCAST_NUM，如果在这个代数范围内找到了一个更优基因，说明这个值设置的比较合理，现在的物种进化速度较快，不用发生灾变，当找到更优基因时，将预测的代数变量重新设置为FORCAST_NUM即可；如果已经到达超过预测代数的子代，但是仍没有找到一个更优的基因，说明当前物种进化速度较慢，或者种群已经在某个极值区间内反复的搜索，无法找到更优值，此时可以进行灾变，即将当前种群中的所有个体杀死，然后通过程序生成新的个体，形成新的种群，新的种群是通过对种群当中的最优基因变异产生的，通过不断的发生灾变，可以避免种群在陷于极值的搜索。基因优化算法设计 为了保证基因进化的方向始终朝着最优基因的方向进行，每次对原有基因进行变异之后，可以进行基因优化处理，以加快物种进化的速度。基因优化函数的思想是通过对相邻基因元素进行交换处理，将现有基因的s_MARK值更小，在本论文中也就是使得飞机离场的总时间最小。以图5当中的基因序列为例，阐述基因优化的过程为： (1)从基因序列的起始端开始，先计算出前三个飞机的离场时间t1，然后交换前两个的位置（如果可以的话），再次计算前三个飞机的离场时间t2，如果t2t1，那么就保持前两个基因序列元素交换位置的状态，否则，不做任何改变； (2)从基因序列的第2个位置开始，以循环位置起始的四个基因序列元素为一组数据，先计算这四个飞机的离场时间t1，然后交换中间两个飞机的顺序（如果可以的话），再次计算这四个飞机的离场时间t2，比较两个值的大小，如果t2t1，那么就保持前两个基因序列元素交换位置的状态，否则，不做任何改变； (3)对于末尾的三个元素，也采用同(1)的策略，只不过交换的是后两个元素。 通过以上的步骤，我们就可以将现有的基因进一步的优化，使得整个种群的进化都朝着目标的方向进行，加快种群进化速度。4.2 算法设计步骤小结 基于上面的分析,改进后的双码自适应遗传算法的计算步骤如下: 图7 选取最优基因的主程序流程图（用visio画图，不要用图片格式，方框保持大小一致） 上面算法使用了最佳个体的保留策略,因此根据遗传算法的收敛性定理易知,该算法一定可以收敛到问题的全局最优解。第5章 离场调度与仿真5.1 仿真条件 假定仿真系统中只包含一定数量的4类航班，即重型航班(H)、大型航班(L)、中型航班(M)和小型航班(S),它们将排成两队,在各队航班相对顺序保持不变的前提下,从一条跑道上顺序起飞。下面给出仿真系统中这四类航班的尾涡间隔：前机 后机重型（H）大型（L）中型（M）小型（S）重型（H）1.2m2.0m3.0m5.0m大型（L）1.0m1.0m1.2m1.5m中型（M）0.8m0.8m1.0m1.2m小型（S）0.5m0.5m0.8m1.0m表1 仿真系统中的航班尾涡间隔（编号不对，表的标题在表的上方。数据来源是什么？数据不对） 为了使问题简单化,仿真时没有考虑航班之间的纵向间隔。显然,这并不影响本文模型和算法的正确性和有效性。仿真采用matlab编程语言,在CPU速度为3.2G的计算机上运行,对两条滑行道上的两队列离场航班进行了优化调度研究。 离场调度问题一般都限定在一定的时间内，并且本文仅仅研究双滑行道单起飞跑道情形,所以对应航班的数量不可能太大，假设每分队20架次为上限（本文的仿真对航班的数量并无限制，完全可以处理更多架次的情况）。下面为一种两分队离场情形，相应的仿真结果将在下一小节给出。1234567891011121314151617D1MSSLSHMMLSHLLSMSD2MMML LSHSH表2 两分队航班原始序列5.2 仿真结果 对应于上面的离场航班序列,仿真得到了相应离场总队的优化排序结果,并分别同随机排序情形进行了对比。如表3：随机安排结果随机安排耗时（m）优化安排结果1优化安排耗时（m）优化安排结果2优化安排耗时（m）M(D1)0M(D1)0M(D2)0S(D1)1.2S(D1)1.2M(D2)1.0M(D2)2.0M(D2)2.0M(D1)2.0S(D1)3.2S(D1)3.2S(D1)3.2M(D2)4.0L(D1)3.7S(D1)4.2M(D2)5.0M(D2)4.9L(D1)4.7L(D2)5.8M(D2)5.9M(D2)5.9L(D1)6.8S(D1)7.1S(D1)7.1S(D1)8.3H(D1)7.6L(D2)7.6H(D1)8.8L(D2)9.6H(D1)8.6M(D1)11.8M(D1)10.8L(D2)10.6L(D2)12.6L(D2)11.6M(D1)11.8M(D1)13.8M(D1)12.8M(D1)12.8S(D2)15S(D2)14S(D2)14H(D2)15.5L(D1)14.5L(D1)14.5L(D1)17.5S(D1)16S(D1)16S(D1)19H(D2)16.5H(D2)16.5H(D1)19.5H(D1)17.7H(D1)17,.7L(D1)21.5L(D1)19.7L(D1)19.7S(D2)23L(D1)20.7S(D2)21.2L(D1)23.5S(D2)22.2L(D1)21.7S(D1)25S(D1)23.2S(D1)23.2M(D1)25.8M(D1)24M(D1)24S(D1)27S(D1)25.2S(D1)25.2H(D2)27.5H(D2)25.7H(D2)25.7表3 优化前后离场总队的排序和对应起飞时刻 从上面的结果可看出，优化后所形成的航班序列保持了各队原有的相对顺序，同时将总的离场耗时压缩到了最小，这就说明了本文模型和算法的正确性和有效性。为了说明该遗传算法的可靠有效，本人又通过穷举法进行计算对比，(表3优化结果安排2)所得结论与遗传算法结论相同，确定本文算法得到的结果为全局最优解。图7 仿真显示的最佳序列总耗时图8 仿真显示的最佳序列 图7显示了经过70代的变异得到了最优的排序，总耗时25.7m。 图8显示了遗传算法里变异子代中最佳的离场航班排序，解码后的结果即：M(D1)S(D1)M(D2)S(D1)L(D1)M(D2)M(D2)S(D1)H(D1)L(D2)M(D1)L(D2)M(D1)S(D2)L(D1)S(D1)H(D2)H(D1)L(D1)L(D1)S(D2)S(D1)M(D1)S(D1)H(D2) 通过优化过程我们还可以思考得出： （1）采用遗传算法效率更高，遗传算法经过不到1分钟的计算，使用枚举法，计算用时5分钟，可见遗传算法可以加快收敛速度，提高了运行效率，因此，遗传算法要优于一般的算法。 （2）优化后的离场序列比随机得到的离场序列分布得均匀，排序的结果倾向于将同类型的飞机组成飞机簇。即优化的过程将尽量剔除大尾涡间隔的出现，比如紧随重型航班之后不安排小型航班的情况。 （3）全局最优并不意味着航班序列固定。比如,在不影响各个分队航班相对顺序的前提下，由于存在要起飞的两条滑行道上的飞机类型相同，或者起飞前后不同类型飞机但尾流间隔等待时间相同这两种情况，所以可能出现调整相邻两架航班的顺序，并不影响总的离场耗时。 （4）随机排序下,某序号航班离场时间有可能早于优化排序中该序号航班的离场时间,这说明了全局最优并不要求步步最优。（见表3优化结果安排1和优化结果安排2）第6章 总结与展望（内容太少） 本文针对航班的离场排序问题，基于双码自适应的遗传算法，但并没有完全的套用传统遗传算法的结构，采用单亲变异繁殖模型建立了优化排序的数学模型，并最终设计了优化的离场航班排序。不仅合理的给出了飞机的离场顺序，对提高机场的吞吐量也具有一定的实用价值。仿真结果表明，通过本文设计的算法求解相应最小化的问题，可以有效的缩减总的离场耗时，并能得到离场航班排序问题的全局最优解。 由于遗传算法具有许多其他算法所缺乏的独特优点，相信随着未来科技的发展，遗传算法将会在离场航班排序中有更大的更有意义的应用，使得资源分配更加趋于合理，公司管理更加趋于科学，航班离场更加趋于正常化。参考文献1 韩瑞锋等。遗传算法原理与应用实例 M。第1版，北京：兵器工业出版社，2010。2 王来军，史忠科。航班离场排序的遗传算法设计J。系统工程理论与实践，2005，09:119-126。3 王来军，肖润谋，胡大伟，郭捷。一种新型启发式算法及其在航班离场排序问题中的应用。西北大学学报(自然科学版)，2011，41(3)：423-426。4 李珍，张军，张学军。基于遗传算法的航班离港调度建模及仿真J。交通与计算机，2008，6(26)：39-42。5 刘丹，韩松臣，舒旎。多跑道起降航班排序模型和算法J。武汉理工大学学报(信息与管理工程版)，2011，33(1)：27-31。 6 杨秋辉，游志胜，冯子亮，樊鸿。自适应遗传算法在飞机调度问题中的应用J。四川大学学报（自然科学版），2004,41（6）：1158-1162。 7 徐肖豪，姚源。遗传算法在终端区飞机排序中的应用J。交通运输工程学报，20