基于Petri网和遗传算法的飞行训练计划优化编排

王里付，朱新平

(1.中国人民解放军95337部队司令部，广西 柳州 545112;2.南京航空航天大学民航学院，江苏 南京 210016)

随着综合国力的增强，一大批先进战机列装空军。在这种情况下，为适应高强度训练需要，军航必将占用更多空域，而目前专用的军航训练空域建设滞后，因而导致空域资源紧张，尤其对某些以基地化保障模式为主的机场，这种现象更为突出[1]。因此，科学合理地安排飞行训练计划，以便高效安全地使用训练空域，成为当前航空兵部队训练面临的紧迫问题。笔者主要对航空兵部队飞行训练计划优化编排问题开展研究。

航空兵部队飞行训练通过飞行计划来组织，而飞行计划则由若干科目构成，科目是实际飞行训练的最小组织单元。飞行训练过程中，各科目对空域并发动态占用和释放，对训练空域的科学管理提出了挑战。在一定条件约束下，如何统筹安排各科目对训练空域占用的起止时间，以提高空域利用效率，即为笔者所研究的航空兵部队飞行训练计划优化编排问题。

以往关于航空兵部队飞行训练的研究多集中在仿真系统设计与实现[2－6]，以及飞行训练后勤保障方面[7－9]，对训练计划本身的优化编排则缺乏研究。文献[2]指出飞行训练过程中，战机群运行体现出典型的离散事件特征。Petri网作为一种适合描述离散事件动态系统的工具，非常适合用于描述和分析飞行训练科目对空域的占用[10]。但采用Petri网建模训练科目对空域占用过程，模型状态的变化受制于初始标识和模型结构，很难实现托肯所代表的科目对空域占用过程的自动优化。考虑到遗传算法(genetic algorithm，GA)具有良好的全局寻优能力[11]，笔者采用赋时库所Petri网TPPN建立训练科目对空域占用过程模型，并将其与GA结合，实现飞行训练计划的优化编排。

1 基于TPPN的飞行训练空域占用过程建模

1.1 飞行训练对空域资源的占用

飞行训练计划是指占场时间之内，各科目对训练空域的占用起止时间。如表1所示，需要为4 种训练科目制定训练计划，A1、A2、A3、A4为可供安排训练科目的空域。在实际飞行训练过程中，一个空域可能同时安排多个科目，也可能只安排一个科目。对所有空域进行逻辑划分，使得每一逻辑空域只能同时被一个科目占用。由于不同空域具有不同的空间结构，因此，同一科目在不同空域运行时可能需要不同的时间。如表1中，A2/(23)，A3/(12)表示科目1选择A2作为训练空域需要23个单位时间，而在空域A3内飞行时需要12个单位时间。

表1 训练飞行科目对空域资源的占用需求

从表1可以看出，为同时安排上述科目的飞行训练计划，需考虑科目－空域占用调度问题，由于科目安排在不同的空域，执行的顺序不同，完成整个训练计划所需的空域占用时间也就不同，从而影响空域的使用效率，调度不合理也会带来空域资源占用冲突问题。如科目3和科目4均可占用空域A2，而先被哪一个科目占用则应根据计划优化编排的优化目标来决定。这里考虑的最优调度是完成所有训练科目，满足所需空域占用时间最短、无科目结束时刻相同这两个目标的科目－空域调度序列。为了得到最优序列，首先建立飞行训练对空域占用过程的赋时库所Petri网模型。

1.2 飞行训练科目对空域占用的TPPN模型

定义 1[12]TPPN 定义为 TPPN={P，T，I，O，M0，φ}。其中，P为库所集;T为变迁集，且满足P∩T≠Φ，P∪T≠Φ;I，O分别为模型的前向和后向关联矩阵;M0为模型初始标识;φ:P→D定义为库所每次被标识应持续的时间，其中，D={dτ0，dτ1，…，dτn}为持续时间集合。

TPPN变迁使能规则为:对变迁t∈T，若库所pi∈(p)t被标识的时刻为xi，对应的持续标识时间为 dτi，当所有 pi∈(p)t均被标识，且当前时间时，该变迁被使能。

TPPN变迁激发规则为:当变迁使能规则满足后，便可以激发。激发过程为瞬时，可以输出一个托肯到其输出库所。托肯到达库所后，便可形成新的标识。

结合一个实例，说明用TPPN建立科目－空域占用过程模型的方法和步骤。

(1)用TPPN建立单个飞行训练科目对某一空域的占用过程模型，如图1所示。在该模型中，有库所、变迁、弧和托肯。其中，库所Ak表示对应训练空域k(k=1，2，…，n)的状态，若该库所被标识，则表示对应的训练空域可被占用。其他库所则表示该科目所处的执行状态，分为3种:①psi为科目i(i=1，2，…，n)初始状态库所，表示对应训练科目的准备状态，其中托肯数为这类科目的数量;②pij为科目 i的第 j种执行状态库所，dτij为对应的空域占用时间;③pei为科目i的执行完成状态库所。当其中托肯数等于psi中的初始托肯数时，表明科目i的所有训练任务均被执行完成。

图1 单个科目对某一空域的占用过程模型

(2)建立飞行训练科目－空域占用关系表，如表2所示，该表描述了各个科目可在哪些空域中完成，及其对应的空域占用时间。为建立与对应的科目－空域占用TPPN模型的联系，在表2中还给出了科目每一次空域占用过程对应的赋时库所，其中，A1、A2、A3、A4表示可占用的训练空域。以科目1为例，该科目有两种执行方案，分别为:①在空域A2中执行23个单位时间后退出该空域;②在空域A3中执行12个单位时间后退出该空域。对应的赋时库所分别为p11、p12。

表2 飞行训练科目－空域占用关系表

(3)利用飞行训练科目－空域占用关系表，关联已建立的所有单个科目－空域占用TPPN模型。模型仅通过库所状态的变化描述训练科目某次执行对某一个空域的占用过程，并没有体现科目执行过程对多个空域的选择性占用可能。为了全面直观地描述所有科目对空域的占用过程，必须在此基础上结合科目－空域占用关系表，建立更为完善的科目－空域占用TPPN模型。以科目1和科目2为例，结合表2，说明如何关联起所建立的单个科目－空域占用TPPN模型，可分3个步骤进行:①对单个科目－空域占用过程模型进行扩展，增加选择库所sij，描述科目i的第j种执行选择。如图2(a)中，库所s11、s12为科目1对应的两种执行方案的选择库所，当某一选择库所被标识时，表明其对应的科目－空域占用方案被选择，空域占用时间则可根据对应的赋时库所p11和p12以及表2来确定。②对步骤①所得到的单个科目－空域占用扩展模型，将其中属于同一类科目的模型进行联合，如图2(b)是由图2(a)联合得到。在图2(a)中，变迁t0和t1均描述科目1对空域的占用，可将其前向库所集中的科目初始状态库所合并;同理，变迁t2和t3均描述科目1对空域的释放，可将其后向库所集中的科目完成状态库所合并。③对其他类科目的科目－空域占用过程模型进行上述步骤①和步骤②操作，可得到所有科目－空域占用过程的完整TPPN模型。需要说明的是，在最终得到的TPPN模型中，所有名称相同的训练空域库所作为同一库所对待。为了绘图方便，同一空域库所可多次出现。

图2 单个科目－空域的占用TPPN模型关联过程

2 飞行训练计划编排的优化

由TPPN模型可知，每一类科目均可选择不同的空域来执行。飞行训练计划编排的优化需要考虑多方面的因素，属于NP难问题。在TPPN仿真过程中，通过用GA控制模型相关选择库所中托肯的配置，使得其变迁的激发过程得到优化，从而满足设定的计划编排优化目标。GA的显著特点是可以同时对搜索空间中的多个解进行评估，具有较好的全局优化能力。

2.1 染色体编码

用GA对科目－空域占用方案进行规划，首先需要建立空域占用方案与染色体之间的一种对应关系。根据训练计划编排的特点，所设计染色体根据科目类型分成多段，每段染色体的长度为该类型科目将要执行的次数，且每个基因对应一个该类型科目的选择库所。从图2可以看出，每种类型的科目可选择不同的空域进行训练。如在图2中，库所s11和s12为科目1的选择库所集合。在安排每个训练科目时，均可从对应的选择库所集合中随机选择，作为染色体的基因，同时也就表明对应的空域占用方案被选择。如选择了s11作为染色体基因，就表示科目1在执行过程中将选择占用空域A2。将每种类型科目多次执行过程对应的选择库所依次排列，形成一条染色体，即可表示一个完整的飞行计划编排方案，如图3所示。

图3 染色体编码方案

2.2 适应度函数

研究的目标是所有训练科目均完成时，所需空域占用时间最短，且空域占用过程中无任何两个科目结束时刻相同，以便实现高效、安全地利用训练空域。

(1)科目每次执行过程占用空域时间的取得。根据染色体所规定的空域占用方案控制TPPN模型的运行，直到所有科目初始状态库所和执行状态库所中的托肯数均为0。此时表明该TPPN模型完成了所有科目的空域占用过程，在该过程中，记录每一次科目执行过程中的空域结束时间。

(2)染色体适应度函数。根据各科目每次执行过程占用空域的时间，可求得各个空域占用的时间time(Ai)。以各空域占用时间最大值中的最小值作为整个空域的占用时间，即取染色体适应度函数为 f=min{max[time(Ai)]}。

2.3 遗传操作

对所获得的初始种群进行基本的遗传操作:

(1)选择。选择是为了从当前群体中确定优良的个体，使其作为父代繁殖下一代种群。可采用首先计算适应度数值，然后按照轮盘赌选择的方法确定新的种群。

(2)交叉。采用两点交叉方法，即在双亲的染色体上随机地选择两个固定的点，然后将这两个点之间的基因进行交换。图4(a)为两个用于交叉操作的父代染色体，随机确定两个交叉点P和D，然后交换两个交叉点之间的部分染色体，得到子代染色体如图4(b)所示。

图4 两点交叉法

(3)变异。变异是指对种群中的每个个体，以某一概率随机地改变某个或某些基因座上的基因值。操作方法是:在个体中随机选择一个位置作为变异点，确定其对应的选择库所集，从中重新随机地选择一个基因来替代原来的基因。

3 试验验证

采用基于Petri网与GA的飞行训练计划优化编排方法，对某一预定的训练任务计划编排进行试验研究。该训练任务包含7种训练科目，其中前4种的执行次数和科目－空域占用关系表如表1和表2所示，后3种的科目－空域占用关系表如表3和表4所示。

表3 训练科目及其对空域资源的占用

表4 科目－空域占用关系表

根据表1～表4，并利用所给的TPPN模型建立方法，可构建完整的飞行科目－空域占用过程TPPN模型，利用提出的算法进行训练飞行计划优化编排。在该过程中，考虑到GA的随机性，分别设置不同的进化代数进行20次试验。结果表明，当进化代数为40代时，优化效果已较为理想，整个试验过程所得优化结果如表5所示。

表5 优化结果

图5为其中一次最佳优化过程对应的曲线，对应各试验参数设置为:代沟GGAP=0.9，交叉概率XOVR=0.8，变异概率MUTR=0.2，初始种群数量NIND=20，迭代次数为MAXGEN=40。此时空域占用时间为99个单位时间，其对应的染色体为s12s11s21s21s33s32s31s41s41s53s53s51s61s61s61s71s72，且各科目占用空域 A1、A2、A3、A4的甘特图如图6所示。

图5 训练计划编排仿真优化过程曲线

图6 飞行训练计划中科目占用空域甘特图

4 结论

根据航空兵部队飞行训练对空域占用的特点，建立了科目－空域占用过程的TPPN模型，并基于该模型对训练计划优化编排问题进行了研究。一方面描述了各科目对空域的并发占用和释放，以及空域占用之间的约束关系;另一方面，把建立的TPPN模型与飞行训练计划优化编排联系起来，采用GA对模型中的选择库所托肯配置进行优化，满足了既定的优化目标。仿真结果表明，该方法为航空兵部队飞行训练计划的自动优化编排提供了有效的技术支持。下一步的研究主要包括降低大规模训练科目－空域占用过程TPPN模型建立的难度，以及在计划编排时考虑更多的限制因素，如飞行人员和指挥员的指挥能力等。

[1] 王里付.军航使用条件下的空域容量评估及优化方法研究[D].南京:南京航空航天大学图书馆，2010.

[2] 刘志勤.基于Petri网模型的航空兵仿真研究[J].陕西师范大学学报:自然科学版，2005，33(1):221－223.

[3] 高惠英，王恒霖.美国空军的分布式仿真训练系统[J].飞航导弹，1999(2):35 －37.

[4] 石玉峰，蒲建春.空军战役训练仿真系统体系结构及典型模型研究[J].兵工自动化，2010，29(1):47 －49.

[5] 李杰，陈蕾，周俊杰，等.基于仿真的飞行模拟器优化配置研究[J].系统仿真技术，2010，6(4):323 －327.

[6] 尧丰，韩松臣，朱新平.低空空域综合管理系统软件架构研究[J].武汉理工大学学报:信息与管理工程版，2010，32(2):257 －260.

[7] 张荣培，邢建春.军用机场场务保障决策支持系统研究[J].四川兵工学报，2010，31(8):32 －35.

[8] 邵晓根.应用混合遗传算法求解飞机牵引调度问题[J].微电子学与计算机，2009，26(10):82 －85.

[9] 张兵，韩晓明，贺沁荣.空军机场综合评价模型[J].四川兵工学报，2009，30(7):95 －97.

[10] 袁崇义.Petri网原理[M].北京:北京大学出版社，1999:21－26.

[11] 雷英杰，张善，李续武，等.MATLAB遗传算法工具箱及其应用[M].西安:西安电子科技大学出版社，2009:12－14.

[12] 李慧芳，范玉顺.基于Petri网仿真的批处理过程动态调度[J].系统仿真学报，2002，14(7):928 －931.