基于并行遗传算法的舰载机再次出动作业调度

范加利,朱兴动,高 伟,王 正

(1.海军航空大学 青岛校区，山东 青岛 266041；2.海军航空大学，山东 烟台 265200)

根据任务需求，航母上舰载机的出动方式通常按照单波次大批量起降、多波次适当批量起降等多种方式组织实施。为高效使用飞行甲板资源，航母通常按一定时间周期进行作业[1]。在舰载机和航母设计定型后，如何优化配置和合理安排批次舰载机的再次出动保障工作对于提高航母舰载机出动强度的提高具有非常重要的意义。

受作业完成时间的不确定性、舰载机及保障装设备故障的随机性、作业环节的多态性等因素的影响，涉及多架舰载机、多种保障资源的舰载机再次出动作业的调度问题属于典型的动态调度问题。近年来，国内学者在该领域进行了大量的研究工作，针对该问题常用的方法是建模仿真方法[2]，最优化方法[3-5]，以及基于专家方案的逆向强化学习方法等[6]。但多数文献中仍以静态调度为研究基础，通过提高调度结果的鲁棒性来保证和自适应性来增强调度系统、算法对动态、随机环境的响应能力，避免频繁重调度。在众多研究文献中，对甲板站位保障能力和舰载机转运路径约束的考虑较少，而实际的甲板作业环境下，必须要考虑站位能力约束和转运路径约束。

针对复杂的舰载机舰面航空保障作业调度问题，本文重点研究双周期出动模式下舰载机再次出动准备的调度，分析再次出动准备的作业过程以及约束条件，建立了舰载机再次出动准备的优调度模型，并采用一种岛式并行遗传算法求解调度模型，最后以库兹涅佐夫航母上8机双周期再次出动准备作业为例进行了验证。

1 舰载机甲板作业调度模型

1.1 舰载机甲板作业过程描述

舰载机在飞行甲板上的相关作业包括机务保障与勤务保障作业，机务保障作业主要机务人员对舰载机及其发动机实施各种不要的检查与修理，勤务保障主要指为舰载机提供电源、惯性导航基准信号源、气源、油料、弹药等各种物资，勤务保障主要由母舰所属人员完成。所有保障工作必须在航母飞行甲板上的特定站位上完成。以某型俄制航母为例，其飞行甲板布局如图1所示。

图1 某航母甲板停机区域分布示意图

图1中过渡区、停机区、暖机区均设置有多个舰载机站位，各停机区域均设有类型和数量不等的固定式勤务保障装置，如加油站、供电口盖、气源口盖、导航对准口盖等。除暖机区和起飞位上的舰载机可实施起飞前的暖机作业外，其他区域站位上的舰载机均不能起动发动机。受甲板区域大小限制，过渡区与起飞区存在重叠，着舰区与暖机区存在部分重叠。由于重叠区域存在，舰载机甲板作业时，要求任一时刻起飞与着舰不能同时进行，且着舰作业时，暖机区II中停放的舰载机必须转运至其他位置，并清空着舰区域，起飞作业时，除起飞位上的舰载机，其他待机区的舰载机必须转运至其他位置。

飞行甲板运转过程中，舰载机从暖机区的停机位按一定顺序滑行至起飞位起飞，位于停机区停机位上的舰载机则需滑行至起飞位或暖机区停机位进行暖机后方可起飞。着舰的舰载机在引导员引导下分别滑行至待机区和暖机区的空闲停机位停放，并接受再次出动准备，等待下一次飞行。舰载机再次出动准备的甲板作业过程如图2所示。

图2 舰载机再次出动准备作业时序框图

图2中作业集TS1中的加油、挂弹和牵引至暖机位作业的执行顺序可任意调换，但受技术和管理性约束，对于某一架飞机这3项作业不能同时进行；作业集TS2中的惯导对准、暖机、滑行、起飞任务必须依次执行；再次出动机务检修(飞机后的检修、视情添加辅助油料、充氧充氮等)作业可与作业集TS1和TS2中的部分作业并行执行。作业集中有些需独占资源、有些需特定资源有些可认为不占资源。

多架舰载机在实施再次出动准备作业过程中，主要存在以下约束：

1)作业顺序约束。波次出动舰载机的再次出动保障作业顺序约束如图2所示。其中作业集TS1必须先于作业集TS2实施。

2)甲板保障设备/组约束。甲板保障设备包括固定式和移动式两种，保障类别包括油、气、电等。固定式保障设备受管线长度限制，通常只能保障就近的若干停机位，如图1中的加油站。移动式保障设备包括牵引车、电源车等，受空间资源限制，配置的数量受限。保障组主要包括机务保障组、勤务弹药保障组，机务保障组数量通常不存在约束，弹药保障组受舰上编制和挂弹车数量的制约，其配置数量也受限。

3)空间站位约束。如图1所描述，由于部分区域重叠，使得甲板作业过程中应尽量不占用着舰区，以备舰载机紧急着舰，且同一时刻，只允许一架舰载机起飞。处于停机区和待机区的舰载机不能实施暖机，因此，必须转运至暖机位进行暖机及其相关保障作业。此外，舰载机转运作业受空间避免限制，如过渡区的舰载机应从舰艏位置逆序往暖机位转运。

4)供给资源能力限制。受母舰航空保障装备技术水平限制，勤务保障资源的油、气、电供应量存在上限，如同一时刻，甲板上进行加油作业的舰载机数量受限。

1.2 调度模型建立

调度模型的目标函数取为最小化本波次舰载机的再次出动准备时间：

F=minCmax

(1)

约束条件为：

(2)

(3)

(4)

(5)

(6)

sti1jzy≤sti2jzy，∀ZWi1,i2∈Hs，Xzwi1≥Xzwi2

(7)

式(2)和式(3)联合确保每一作业必须只被每一架飞机启动一次，带有仅单一资源的特定性任务需要额外执行要求的作业通过式(3)强调。不等式(4)确保作业期间的时序优先级条件，该不等式主要针对作业集TS2。不等式(5)确保仅有有限数量的甲板资源被用于完成不定资源约束型作业，不等式(6)确保对于每一架飞机没有两个可以导致安全问题的作业同时进行。不等式(7)表示调运可行路径约束通，其中ZWi1表示舰载机在甲板的停机站位，Hs表示舰艏区域站位集合；Xzwp表示站位的x坐标，jzy表示转运作业。

2 调度模型求解算法

基于上述模型与分析，舰载机甲板作业是多架舰载机各作业工序在甲板上各种资源约束下的时序安排和资源分配问题。该问题属于一类特殊的资源受限多项目调度问题(Resource-Constrained(Multi-)Project Scheduling Problem，RC(M)PSP)。国内外学者对该类问题进行了大量的研究工作，研究热点是多模式多项目模型求解，以及各种应用场景[7-9]。在求解算法方面，该类问题多采用优先级规则和智能启发式算法求解。鉴于遗传算法在该求解该类问题方面的研究成果较多，本文采用一种改进的岛式并行遗传算法(IMGA)框架，在局部采用禁忌搜索进行强化搜索。采用矩阵形式染色体结构，采用串行调度生成机制进行解码。

2.1 算法总体框架

并行遗传算法比普通遗传算法有全局搜索能力强的优点。目前，并行GA算法分为3种模型[10,11]：主-从式，粗细粒度式和岛式模型。在第1种模式中，有一个初始种群，计算由多个处理器执行；在第2种模式中，也是产生一个初始种群，但每个个体分配给一个处理器进行运算，选择和复制仅限于邻居之间；在第3种模式中，整个初始种群被分成多个独立的孤岛(子种群)，并被分配给各个处理器，在各个处理器中使用其自己的进化过程，探查各自的搜索空间，偶尔通过迁移机制交换信息，该模式也可在单处理器上以伪并行模式运行。本文采用一种混合岛模型遗传算法求解该问题，总体框图如图3。

为改进算法效率，算法中加入本质自适应调整阶段，该阶段具有在分散和强化搜索过程中的平衡能力。在自调整阶段最好的个体被用于禁忌搜索，最差的个体被用于执行全局搜索。

算法具体流程如下：

步骤1：输入待保障的舰载机数量，各舰载机需要完成的作业集，甲板环境参数及资源约束参数，并将舰载机与甲板站位相关联，标明舰载机在站位上的停放方向

步骤2：采用文献[2]中的矩阵形编码方式，每一行代表一架舰载机的作业工序，从舰艏区站位上的舰载机从前往后依次排序。采用随机方式产生岛屿的各初始种群。

步骤3：各岛内进行基本GA算法进化，在进化过程中，采用轮盘赌方法选择个体，采用基于排序的交叉操作。为避免早熟，文中的自适应策略是对最优个体实施禁忌搜索，对最差个体实施搜索。全局搜索中通过组合交换、插入和逆序算子对个体实施变异。对违反约束的不可行解采用适应度中加入罚函数的办法进行处理。

步骤4：各岛进化完成后，采用迁移策略生成新的初始种群，进一步进化，直到满足终止条件。

2.2 种群迁移策略

种群迁移策略在并行GA中发挥重要作用，其控制了岛间信息交互过程。迁移策略的工作机制主要依赖于4个因素：通讯拓扑、迁移率、选择方法和代替方法。

图3 岛式并行遗传算法总体框图

通讯拓扑结构规范了岛间迁移路径。通常，公共结构是环形、星形、网形、非限制型(完全网)，以及线性矩阵形。通讯代价主要取决于网络直径。为了获得岛间直接低代价迁移，我们采用非限制性结构，如图4所示。

图4 岛间通讯拓扑

迁移率规范了迁移数量和迁移数据。为了获得较好的收敛性，迁移应采用实时模式，通常是任何一个岛收敛时，即发生迁移。当任何一个岛的连续5代后代无任何改进时，即让迁移在岛间发生。

为了允许岛间分享它们关于有希望出现最优解的区域的信息，轮盘赌方法被用作迁移选择方法。即个体xj被选择的概率由下式决定：

(8)

迁移替代方法决定哪一个本地个体将被从他们所在岛的种群中移除，为迁入个体腾出空间。在此选择种群中最差的个体进行替代。

2.3 编码与解码

染色体采用矩阵形编码在处理该调度问题时有直观性，且能很好地反映工序约束关系。本文的染色体行为矩阵A所示。

(9)

其中aij取[0,J]上的整数，代表舰载机的作业集。0为空工序，矩阵前半部分各元素为0～3之间的整数，代表加油、挂弹和转运；矩阵后半部分各元素由于表示任务集TS2中的作业。这样编码的优势是在进行进化过程中只需操作前半部分染色体，从而缩小解的搜索空间。

解码采用串行进度生成机制(SGS)。依次取矩阵A的各列，判断是否满足资源和空间约束，若满足则将该架机上一作业结束时间作为该工序开始，若存在资源或空间约束，则计算资源释放等待时间。以挂弹作业为例，算法如下：

1：functionCaldt()

2：记录没架飞机第j到作业工序为挂弹作业的飞机数为tgd，自增

3：取当前舰载机作业工序j的上一工序结束时间→TempJ

4：若当前为所有飞机的第一道作业工序，且tdg≤NGD(挂弹资源约束)，则dt=0，否则dt=tgdd，tgdd为d区域的预计挂弹作业时间

5：当前已安排挂弹作业的飞机数量ngdTask，并将其预计结束时间按从小到大排序

6：若当前非第一道作业工序，且ngdTask

3 算例仿真

图5 8机再次出动准备调度时序优化结果图

从仿真结果可以看出：并行GA算法可以获得较接近最优解的调度结果。调度模型输出的作业逻辑符合实际甲板作业环境，方案可行。

4 结论

在考虑甲板站位能力和移动路径约束的前提下，建立了适用于舰载机甲板作业时序安排调度模型，设计了一种岛式并行GA算法对模型求解。在并行框架下，引入自调整策略，增加搜索过程中的分散性与集中性。建立的调度模型符合实际航母甲板作业环境，采用的算法能够在可接受时间内获得近似最优解。