APP下载

基于遗传算法的军用飞机智能起降调度方法研究*

2015-03-15刘生学王公宝

舰船电子工程 2015年2期
关键词:军用飞机军机尾流

刘生学 王公宝 胡 忠

(1.海军工程大学理学院 武汉 430033)(2.海军工程大学兵器工程系 武汉 430033)



基于遗传算法的军用飞机智能起降调度方法研究*

刘生学1王公宝1胡 忠2

(1.海军工程大学理学院 武汉 430033)(2.海军工程大学兵器工程系 武汉 430033)

计及军用飞机起降过程中的时间窗口约束和尾流间隔约束条件,基于遗传算法建立了军用飞机智能起降调度的数学模型。飞机队列顺序采用整数染色体编码方案,依据初始化种群、求解适应度函数和轮盘赌方式的选择操作,并配合相应的交叉、变异算子,对军用飞机航班规划问题进行了求解和优化。通过仿真计算,并与其他调度方法进行对比分析,验证和说明了所采用的模型和算法的有效性。

遗传算法; Matlab; 优化

Class Number TP301

1 引言

军用飞机起降频率及其时刻的确定是军用航班规划的重要内容之一[1]。军用飞机在某一时段内进驻同一机场,其起飞和着陆是一个循环使用机场的过程,此时军用飞机的出动强度较大,而且对起降时刻和操作安全的要求较高。因此,采用一定的优化策略对军用机场的有限资源进行科学合理的配置,不仅可以显著提高人员的工作效率,而且可以有效加速空中战斗力的生成。现实军用空管中的辅助工具一般由人工调度和智能调度两种模式组成[2],其中人工调度完全基于管制员的个人经验,在交通繁忙的情形下往往调度效率低下,夜间疲劳时易危及飞行安全。近年来,随着航班规划问题规模的增大及目标函数的复杂化,文献[3~6]尝试采用数学规划方法研究机场飞机的智能起降调度问题。作为一类智能优化,遗传算法具有很强的全局优化能力,适合于求解众多的最优化问题[7]。本文基于整数编码方案和相应的交叉、变异算子,将遗传算法应用于军用飞机的智能起降调度问题之中,对军用飞机航班规划问题进行了求解和优化。通过仿真计算,并与其他调度方法进行对比分析,验证和说明了所采用的模型和算法的有效性。

2 军用飞机起降调度的约束条件

针对军用飞机的起降调度问题,本文主要从作战效能和飞行安全的角度出发,构建了起降调度的数学模型,该模型的约束条件主要包括时间窗口约束和尾流间隔约束。

2.1 时间窗口约束

为了最大限度地发挥军用飞机的作战效能,军机起降时间必须限制在一定的时间窗口内。对于起飞军机,过早起飞则可能导致浪费作战资源;过晚起飞,则可能导致无法完成任务。对于降落军机,最早降落时刻为军机保持最大飞行速度返航降落的时刻,最晚降落时刻为确保燃油能够使得军机安全降落的最大时刻。

2.2 尾流间隔约束

依据空气动力学原理,飞机在飞行过程中会产生“尾流”,如果它后面的飞机距离太近则会失去飞行平衡,从而造成飞行事故。国际民航组织(ICAO)将最大起飞重量在136吨以上的飞机定义为重型机,7~136吨之间的飞机定义为中型机,7吨以下的飞机定义为轻型机,并规定了无风条件下不同类型飞机之间尾流间隔的最低标准[8],如表1所示(单位:s)。例如,对于需进场着陆的两重型机(机型均为1),前机和后机之间的尾流间隔至少应大于60s,这样才能有效避免起飞飞机遭遇尾流影响。

表1 飞机之间的尾流间隔(s)

注:1,2,3分别代表进场着陆的重型机、中型机和轻型机;4,5,6分别代表离场起飞的重型机、中型机和轻型机。

3 军用飞机起降调度的数学模型

在军用飞机起降调度模型中,主要涉及如下的参数或变量,其符号及物理含义表述如下。

n:起降军机的数量;

ti:军机i的计划起飞/降落时刻;

ei:军机i的最早起飞/降落时刻;

li:军机i的最晚起飞/降落时刻;

Sji:军机j和i之间的最小尾流间隔;

gi:军机i早于ti起飞/降落造成不利影响的单位系数;

hi:军机i晚于ti起飞/降落造成不利影响的单位系数;

xi:军机i的实际起飞/降落时刻;

Ei:max{0,ti-xi};

Ti:max{0,xi-ti}。

n架军机的起降,会形成一个起降队列p。所谓军机起降调度问题,就是在满足时间窗口约束和尾流间隔约束的前提下,寻找一个最优的起降队列p,使得军机的实际起降时刻与计划起降时刻之间的误差对作战造成的不利影响最小。定义军用飞机起降时刻的误差对作战造成的不利影响函数为f(p),则军用飞机起降调度的数学模型可描述如下:

(1)

4 算法的实现

4.1 染色体编码方案

在飞机编号中为充分体现军用飞机的航班号或呼叫号[9],本文对染色体采用整数编码的思想。此处一个飞机的起降队列定义为一个染色体,每个染色体由n个整数组成,每个基因值代表一架飞机,一个染色体代表一种调度方案,表示安排军机的一种顺序。在一条染色体中,每个基因值均会出现,且出现次数仅有一次。比如某一染色体为124356,则表示首先为1号军机安排降落时间,然后依次安排2、4、3、5、6军机,如图1所示。这种编码方案的优点在于其简练而直观,便于数值实现。

图1 染色体编码

4.2 解码

具体的解码过程是:按照染色体中第i架军机的次序,安排实际的调度时间xi,首先令xi等于最早起降时刻ei,这样可以尽可能早地为军机安排调度时刻,避免因延误而对战机造成不利影响。如果最早时刻不能满足尾流约束,这样就会对作战造成一定的不利影响;同时,飞机的实际调度时刻会在满足尾流约束的基础上产生一定的延误。这里定义一个延误系数,表示由于延误对人的判断有一定的影响,从而对战机造成影响的一个随机因子,本文的延误系数随机取为0~0.05。故军机的起飞时刻模型可采用下式描述

(2)

式中:rand是扰动因子,为处于[0,1]之间服从均匀分布的随机数,该参数的引入可有效避免算法陷入局部最优。依据上述解码方法,则可确定每条染色体中全部军机的实际起飞时刻。

4.3 种群的初始化

在遗传算法中,种群规模和初始种群的质量对运算过程及数值结果有较大的影响。为确保初始种群的多样性和数值解的可行性,在种群初始化中采用FCFS(First Come First Serve)策略,令其中一条染色体按照军机的先后起降顺序排列;其余1/3的染色体为1~20的序列,由每两个数随机产生;还有1/3的染色体为1~20的序列中每三个数随机产生;最后剩下的染色体为随机产生的序列。

4.4 适应度函数

适应度函数的设计通常要与问题的求解目标相关。由于飞机调度问题的目标函数值越小越好,而通常遗传算法中认为适应度大的个体其适应性较好,本文设计的适应度函数如下:

(3)

4.5 选择运算

采用轮盘赌方式,可依据适应度函数的大小决定群体中个体被选中的概率,这体现了自然界中的适者生存原则。

4.6 交叉运算

为使得后代交叉运算结果的合理性,交叉算子在随机确定交叉的位置后,首先需对两个父代个体的相应基因进行交换,然后从相应的父代个体中按照原来的基因顺序将不重复的基因拷贝到对应的子代个体中,如图2所示。

图2 交叉运算

4.7 变异运算

由于染色体中飞机编号必须且只能出现一次,为了保证后代变异运算后的合理性,本文采用染色体中相邻基因进行位置交换的方式处理变异运算。首先随机确定变异位置,再将该位置上的基因与该位置之后的基因进行交换,如图3所示,这种概率较大的变异算子将有助于优化结果的快速获得。

图3 变异运算

在种群规模的控制上,本文采用保持固定种群规模的策略,在每一代的进化过程中,保留最佳个体,去掉最差个体,而个体的总数在进化过程中保持不变。在这种情况下,算法将快速收敛并得到最优解。同时,这也便于计算机使用固定的内存需求以确保算法的快速实现。

5 仿真结果与分析

本文选择某单跑道机场内20架军机进行仿真验证,表2罗列了各军机的起降机型、起降时刻、最早起降时刻、最晚起降时刻及其对飞机起降造成不利影响的单位系数,各参数的物理含义详见文中第3节相关内容。

表2 军用飞机起降参数

根据该算法的实现理论,在Matlab中编制了仿真程序。经过进化计算,同时保留每一代中的最优个体,最后再从所有的最优个体中选择出最佳的调度序列和起降时刻,并与文献[2]提出的粒子群和FCFS策略的结果进行比较,表3给出了仿真计算的结果。

表3 数值仿真结果

由表3可知,运用遗传算法计算得出的结果相比粒子群算法和FCFS策略所得结果更优,其中遗传算法与粒子群算法得到的目标函数值相近,比FCFS策略的结果要低48%,这表明了遗传算法在优化军用飞机起降调度问题中的优势。

图4 各飞机的实际起降时刻

为进一步验证结果的正确性,将军机的最早、最晚、计划、实际起降时刻进行比较(见图4)。由图4可知,飞机的实际起降时刻均在其最早和最晚起降时刻之间,这样可保证结果满足时间窗口约束;另外,实际起降时刻都在计划起降时刻附近,这表明该算法所求得结果的正确性。

6 结语

从军用飞机的作战效能和起降安全的角度出发,基于遗传算法建立了军用飞机智能起降调度的数学模型。通过引入时间窗口约束和尾流间隔约束,该模型可适当地调整部分军机的起降序列,有效提高战机进场着陆和离场起飞的效率,进而获得较优的作战效果。针对军用飞机起降调度的特点,分别设计了遗传算法的编码方法、适应度函数、遗传算子(选择、交叉、变异运算)等,并通过计算机仿真验证了其优良性能。

在结果分析方面,将本文所提出的算法与粒子群算法和FCFS策略进行比较,发现本文算法优化所得的结果明显比粒子群算法和FCFS策略得到的结果优异,这说明了该算法具有良好的优化性能。

[1] 冯心玲,龚月娇,林映霞,等.用遗传算法优化航班规划问题[J].计算机工程与设计,2009,30(19):4468-4471.

[2] 胡训强,谢晓方,李德栋.军用飞机智能起降调度技术研究[J].系统工程与电子技术,2012,34(11):2280-2284.

[3] 孙宏,张翔,徐杰.应用模拟退火算法求解飞机调度问题[J].飞行力学,2006,24(2):84-87.

[4] 杨秋辉,游至胜,冯子亮,等.自适应遗传算法在飞机调度问题中的应用[J].四川大学学报,2004,41(6):1158-1162.

[5] Hu X B,Paolo E D.Binary-representation-based genetic algorithm for aircraft arrival sequencing and scheduling[J].IEEE Trans on Intelligent Transportation System,2008,9(2):301-310.

[6] Chou T Y,Liu T K,Lee C N,et al.Method of inequality-based multiobjective genetic algorithm for domestic daily aircraft routing[J].IEEE Trans on Systems,2008,38(2):299-308.

[7] 胡毓达.实用多目标最优化[M].上海:上海科学技术出版社,1990.

[8] Beasley J E,Krishnamoorthy M,Sharaiha Y M,et al.Scheduling aircraft landings-the static case[J].Transportation Science,2000,34(2):180-197.

[9] 余江,罗晓利.遗传算法在飞机着陆调度问题上的应用[J].航空计算技术,2007,37(3):1-4.

An Intelligent Method for the Depart-and-Land Scheduling of Military Aircraft Based on Genetic Algorithm

LIU Shengxue1WANG Gongbao1HU Zhong2

(1.College of Science,Naval University of Engineering,Wuhan 430033)(2.Department of Weaponry Engineering,Naval University of Engineering,Wuhan 430033)

Based on the genetic algorithm,an intelligent method is proposed for the depart-and-land scheduling of military aircraft,where the time window and vortex separation constraints are taken into account in the course of departure and landing processes.For the sequencing problem,the aircraft are numbered by the integer chromosome codes.According to the population initialization,fitness-function implementation and selecting operation in the roulette form,the military aircraft planning problem is resolved and optimized with the corresponding crossover and mutation operators.Through the comparison of other two scheduling methods,the effectiveness of the model and algorithm presented is validated in the simulation process.

genetic algorithm,Matlab,optimization

2014年8月6日,

2014年9月21日

刘生学,男,硕士研究生,研究方向:军事运筹学。

TP301

10.3969/j.issn1672-9730.2015.02.009

猜你喜欢

军用飞机军机尾流
一位制造商一架军机(欧亚篇)
一位制造商一架军机(美国篇)
大胆小偷,闯“禁区”盗走军机设备
军机空难 一箩筐
任务准备期内的军用飞机瞬时可用度
飞机尾流的散射特性与探测技术综述
锥形流量计尾流流场分析
水面舰船风尾流效应减弱的模拟研究
浅水圆柱绕流流动模式探讨