资源描述：
《自适应遗传算法在飞机调度问题中的应用_杨秋辉》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、2004年12月四川大学学报(自然科学版)Dec.2004第41卷第6期JournalofSichuanUniversity(NaturalScienceEdition)Vol.41No.6文章编号:049026756(2004)0621158205自适应遗传算法在飞机调度问题中的应用1112杨秋辉,游志胜,冯子亮,樊鸿(1.四川大学计算机学院,成都610065;2.四川省公路局,成都610041)摘要:基于自适应遗传算法,实现了单跑道降落飞机调度问题的求解.算法以所有飞机的排列次序做为个体编码,
2、解码时用移动方法确定飞机的降落时间.适应度函数的构造综合考虑了飞机的提前和延迟带来的损失,选择算子采用期望值方法,交叉算子用顺序交叉,变异算子用倒位变异.为提高算法的执行效率并避免早熟收敛,对交叉和变异概率均采用自适应策略.仿真结果表明了自适应遗传算法用于飞机调度问题的有效性.关键词:自适应遗传算法;空中交通流量管理;飞机调度;空闲时间中图分类号:V355文献标识码:A1引言随着航空运输业的快速发展,空中交通流量管理的研究越来越受到人们的关注.由于航班安排、气候、机场设施等方面的影响,在一些繁忙的
3、机场,经常发生航班拥堵,给航空公司造成了极大的经济损失.对终端区等待降落的飞机给出合理的调度是空中交通流量管理的一个主要方面.在目前的空管中,飞机的调度通常是按照先来先服务FCFS(FirstComeFirstServed)的原则进行的.这种方法的不足之处是不能综合考虑关于飞机的多方面因素,比如机型、乘客数等.针对各种需要,目前国际上已有一些用于飞机调度的系统[1～4]和研究成果.调度问题是典型的NP组合优化问题,传统对此类问题的求解一般是用经典运筹学中的数学规划方法.随着问题规模增大以及目标函数
4、的复杂化,传统方法很难计算NP问题.很多研究表明,寻找NP问题的最优解是非常困难的,具有实际工程意义的求解算法是放弃寻找最优解的目标,转而在合理有限的时间内寻找到一个近似的、可行的、接近最优的解.近年来,将智能优化算法用于求解优化问题得到了极大的发展,特别是其中的遗传算法,已成功用于优化求解的多个方面.遗传算法GA(GeneticAlgorithm)是由美国Michigan大学的JohnHolland教授创立的一种自适应启发式全局寻优算法.该算法基于达尔文的自然选择原理,通过对候选解进行选择、交叉
5、、变异等操作,模拟自然界“优胜劣汰”的自然选择过程,反复迭代自动寻优,最终得到问题的最优解.由于其思路简单,易于实现,以及表现出来的鲁棒性,遗传算法很快便在各个领域得到了广泛的应用.我们将自适应遗传算法用于降落飞机调度问题的求解,在实现调度时综合考虑多方面因素,最终给出合理的调度结果.2问题描述已知当前有n架飞机{A1,A2,⋯,An}进入终端区等待降落,各飞机的机型、乘客数等信息已知,各飞机提前降落时的开销函数为{g1,g2,⋯,gn},延迟降落时的开销函数为{h1,h2,⋯,hn},机场具有单
6、跑道.在保证飞机之间安全间隔要求的前提下,要求给出这n架飞机的降落次序和时间,让各飞机尽量在接近其预计的降落时间ETA(EstimatedTimeofArrival)时完成降落.不同机型(H:重型;L:大型;S:小型)之间的收稿日期:2004205224作者简介:杨秋辉(1970-),女,山东青岛人,2001级博士研究生.©1994-2010ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://www.cnki
7、.net第6期杨秋辉等:自适应遗传算法在飞机调度问题中的应用1159最小安全间隔矩阵见图1.图1安全间隔矩阵(单位:min)问题的求解目标是:n++f(x)=min∑gi3(Ti-ti)+hi3(ti-Ti)(1)i=1+式中,x表示当前的一种调度方案;Ti表示飞机Ai的预计降落时间;ti表示飞机Ai的实际降落时间;(R)表示当R大于0时,取值为R,当R小于等于0时,取值为0;gi,hi分别表示Ai比Ti提前和延迟时的开销函数,在通常情况下,飞机提前到达引起的额外开销较小,因此,我们取gi为一个较
8、小的常数,即gi表示飞机Ai提前一个单位时间降落引起的开销.而飞机延迟降落时引起的开销通常不是线性的,它与飞机的机型、乘客数等有关,因此我们设置hi为一个随时间增长而指数增大的函数βthi(t)=ki3(e-1)(2)式中,ki是表示飞机重要程度的量,与飞机的机型、乘客数等有关;β的大小反映延迟开销增长快慢;括号中的-1可以保证飞机正点到达时((2)式中的t=0时)的延迟开销为0.由上可见,该问题的目标函数较为复杂,用传统的规划求解难以实现,因此我们采用自适应遗传算法实现对该问题的
