基于改进NSGA Ⅱ算法的舰载机保障作业调度

张 勇

(1.海军航空大学 航空作战勤务学院， 山东 烟台 264001; 2.清华大学 精密仪器系， 北京 100084)

1 引言

航空保障调度系统正常运行是实现舰载机出动回收的基础，提高舰载机保障作业调度能力对于提升航母编队整体作战效能具有重要意义[1]。

近年来，舰载机保障作业调度处于由智能优化调度向人机交互智能决策调度的过渡阶段。Dastidar等[2]提出了基于排队网的舰载机保障作业调度方法，各保障站位视为网络中的节点，将调度问题被转化为访问节点的决策问题。Yu等[3]基于柔性作业车间调度模型，提出了舰载机保障作业调度问题的混合整数规划模型。Su等[4]研究了不确定工时保障作业鲁棒调度问题，并提出了鲁棒调度机制，设计了鲁棒调度算法。李经等[5]以尼米兹航母多站式保障为背景，研究了舰载机多站式保障调度问题，并利用遗传算法求解问题，但没有给出具体人员和设备的调度方案。韩维等[6]详细描述了单机保障作业流程，分析了保障作业约束，建立了基于计划评审技术的多机一体化机务保障作业调度模型。蒋婷婷等[7]针对舰载机集中式保障模式，综合考虑保障中的工序逻辑约束和资源约束，建立了舰载机集中式保障调度动态分层目标优化模型。苏析超等[8]研究了不同人机匹配模式下的舰载机机务勤务保障调度问题，通过仿真试验表明，一体化保障模式具有更高的保障效率和人员负载均衡性。

随着舰载机“综合保障”概念的提出与实践，机务保障人员“一专多能”已成为发展趋势。在一体化保障模式下，舰载机舰面保障作业需要机务保障人员可以完成跨专业、多工种的保障工作，因此机务保障人员专业合并是舰载机舰面保障作业需要研究的问题。本文首先建立了保障作业与资源配置联合优化(joint optimization for flight deck operations and resource allocation,JOFDORA)模型。然后，设计了改进的NSGA Ⅱ算法(improved nondominated sorting genetic algorithm Ⅱ,iNSGA Ⅱ)用于模型求解。在个体选择阶段，采用k-means聚类方法将种群个体分组，在不同分组中分别选取个体用于种群进化。在进化阶段，采用正态分布取样变异算子控制基因变异范围。种群合并后，采用删减策略去除联合种群重复个体。最后基于案例仿真，验证了模型和算法的有效性，研究了保障人员专业合并对于舰载机保障作业调度效能的影响。

2 数学模型

舰载机在出动之前需要进行加油、挂弹、充氧、通电等保障作业，以维持其良好的作战性能。舰载机进入保障停机位之后，各专业机务保障人员按照既定的工序执行顺序，进行舰载机的保障作业，作业过程中，各类固定保障设备为各项工序作业提供油、液、气、电等供给类资源。为提高保障效率，甲板上还配置一定数量的移动保障设备。受供给能力的制约，各供给类资源仅可同时为一定数量的保障设备提供服务。各工序存在多种执行模式，不同执行模式需要的保障人员数量不同，但需要的保障设备数量相同。保障人员在执行工序时，需要占据一定的工位空间。舰载机舰面作业调度问题可视为满足工序逻辑约束和资源约束条件下的资源受限项目调度问题。JOFDORA模型中涉及的符号描述如表1所示。

表1 JOFDORA模型符号表

续表(表1)

建立的JOFDORA模型如下：

(1)

Si1≥Exi, ∀i∈I

(2)

Sij≥Eih, ∀(i,h)∈Pij, ∀(i,j)∈J

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

其中：式(1)表示模型的目标函数为最小化保障完工时间和最小化保障人员、移动保障设备配置数量；式(2)表示舰载机各保障工序最早开始时间为其进入保障停机位的时间；式(3)为工序逻辑约束，只有当某工序的所有紧前工序完成后，该工序才可以开始；式(4)为工序的执行模式约束；式(5)表示工序的开始与结束时间决策变量的关系；式(6)表示保障人员转移时序约束，只有当保障人员从前一个保障工位转移至待调度工序工位后，待调度工序才可以开始执行；式(7)表示保障设备只能对其覆盖范围内的舰载机提供资源服务；式(8)表示保障设备的转移时序约束；式(9)表示工位空间最大容纳人员量约束；式(10)表示供给类资源最大供给量约束；式(11)和(12)表示调度方案中的人员及设备的分配量与需求量关系；式(13)、(14)表示决策变量关系约束。

3 iNSGA Ⅱ算法

JOFDORA问题属于大规模多目标组合优化问题，以群智能优化算法等为代表的元启发式算法在此类问题中应用效果较好[9-12]。NSGA Ⅱ算法[13]作为经典的多目标进化算法，在多目标优化领域具有广泛的应用，但NSGA Ⅱ算法存在非支配个体多样性低，个体在目标函数空间分布性差等缺点，本文在NSGA Ⅱ算法基础上，采用k-means聚类方法将种群分组[14]，并在种群合并后采用删减策略去除联合种群重复个体，提出了iNSGA Ⅱ算法，用于JOFDORA模型的求解。

3.1 算法整体流程

iNSGA Ⅱ算法流程如图1所示，N为种群个体数量。在个体选择阶段，采用k-means聚类方法将种群个体分为k组，然后随机选择两组，分别在两组中采用二元锦标赛方式选择一个个体，2个个体经过交叉、变异后产生子代。父代种群与子代种群合并后，采用删减策略去除联合种群中重复个体，然后进行重组裁剪，产生新的父代种群。重复以上过程，直至达到最大评价次数，输出父代种群个体及个体对应的调度方案，算法终止。

3.2 编码与解码

采用四段编码方案，第一段编码用于表示工序调度的优先级[15]。第二段编码用于表示机务保障人员配置数量，记人员资源强度为RS，第k(k∈Kp)类专业人员配置数量|Lpk|由式(15)计算得到：

(15)

目标函数f2、f3可将个体编码中第二、三段编码对应的数值分别相加计算得到。对于目标函数f1，采用串行调度生成机制将工序调度优先级转换为可行调度方案，进而得到保障完工时间[16]。

图1 iNSGA Ⅱ算法流程框图

3.3 k-means聚类算法

经过重组裁剪得到新的父代种群后，需要从中选择个体执行交叉、变异操作，以实现种群的进化。若直接从父代种群中选取个体，容易导致进行交叉操作的个体相似度过高，进而导致子代个体与父代个体差异性小，降低种群个体多样性，最终得到的Pareto最优解集分布性变差。本文采用k-means聚类算法将父代个体分为k组，然后从不同组中分别选取个体，提高了选择个体的差异性，提高算法的搜索能力。k-means聚类算法的伪代码如下:

Algorithm：k-means algorithm

Input：k, parents populationPpop

Randomly selectkindividuals fromPpopas cluster centers

Repeat

Foreach individualpinPpop

Calculate the Euclidean distance betweenpand each cluster center in the objective space

Reassignpto the cluster with the minimum Euclidean distance

Update the cluster center as the mean value of members in the objective space for each cluster

Untilclusters do not change

Output:kclusters

首先随机选取父代种群中的k个个体作为各组聚类中心，然后计算父代种群中各个体到这k个聚类中心的欧式距离(目标函数空间)，将其归入欧式距离最小的组，全部个体分组完毕后，计算各组目标函数均值作为新的聚类中心。重复以上过程，直至聚类结果不发生改变。

3.4 选择、交叉与变异

在交叉阶段，对选择的子代个体的每一段编码实行单点交叉操作。对于完成交叉操作的2个子代个体编码进行变异操作，其中对于第一、二、四段编码采用均匀变异方式。为了能够使算法在相同或相近的人员配置数量下通过迭代进一步压缩算法得到的机群保障完工时间，对于第三段编码采用正态分布取样变异方式，对子代个体的第三段编码中的人员配置数量|Lpk|，用均值为|Lpk|，方差为1的正态分布随机数替代，即

|Lpk|←⎣norm(|Lpk|,1)」

(16)

若随机数为负数，则重新生成随机数。各段编码的变异率分别是pmut1，pmut2，pmut3，pmut4。

算法中共涉及两次个体选择。首先在种群聚类操作后，从k组父代种群中随机选取两组，在每组种群中选择2个父代个体，比较2个父代个体的适应度函数值，选取适应度好的个体作为子代。其次是在重组裁剪时，依次按照适应度高、非支配排序序值低、拥挤度小的原则，从联合种群中择优选择N个个体作为新的父代种群，用以执行下一次的种群进化。

3.5 删减策略

联合种群经过非支配快速排序后，按照个体序值从大到小的顺序，依次判断目标函数空间内有无重复个体，若有，则将重复个体删除。经过个体删减后，联合种群中的每个个体在目标函数空间中都有唯一的位置，避免重复个体进入下一次的种群进化阶段，提高种群个体的多样性，提高进化效率。需要注意的是，经过个体删减后，联合种群中应至少保留N个个体，否则无法完成后续种群的重组裁剪操作。

4 仿真试验及分析

4.1 案例描述

航母甲板共有16个保障停机位，仿真试验中共设计了任务1～任务3三类保障任务。机务保障人员共有4个专业类型，勤务保障设备共有5种类型，供给类资源共有5种类型，每类勤务保障设备均需要消耗对应的供给类资源，仅考虑座舱一种类型的工位空间，可同时容纳的保障人员数量为1。人员资源强度上下限分别为RSU=3.9和RSL=2.0。各类型移动类保障设备配置数量上下限分别取NeU=3,NeL=0。受篇幅限制，文中没有给出各工序工期、执行模式及其所需的资源类型，保障人员和保障设备在工位之间的转移时间，以及勤务保障设备的覆盖范围。

考虑到特设和航电2个专业的保障内容、维护设备具有一定的相似性，因此本文将2个专业合并为综合航电专业。

4.2 仿真结果分析

iNSGAⅡ算法参数设置为种群数量N=100，各段编码的变异率分别是pmut1=0.05，pmut2=0.2，pmut3=0.2，pmut4=0.2，k-means聚类数量k=10。算法的终止条件为评价次数达到5 000次，算法独立重复运行10次，将10次仿真得到的Pareto最优解集合并，作为最终的仿真结果。

为了更加清楚地反映保障人员专业合并之后对调度方案的影响，将任务1～任务3的专业合并前、后移动保障设备配置数量分别为3、4时的Pareto最优解单独提取出来，结果如图2—图4所示。

图2 专业合并前、后任务1的Pareto最优解曲线

图3 专业合并前、后任务2的Pareto最优解曲线

图4 专业合并前、后任务3的Pareto最优解曲线

由图2—图4可以发现，在相同的机务保障人员和移动保障设备配置数量下，专业合并之后同一保障任务的保障完工时间普遍小于专业合并之前。随着保障任务规模的扩大，专业合并对于保障效率的提升效果越来越显著。在移动保障设备配置数量相同的情况下，随着机务保障人员配置数量的增加，专业合并前后保障完工时间差值逐渐减小，这是由于机务保障人员配置数量增加后，其对于保障完工时间的约束性减小，保障完工时间主要受移动保障设备和甲板消耗性资源的限制，专业合并对于保障效率提升的效果不再显著。因此，在机务保障人员配置数量受限的情况下，专业合并会显著提升给机务勤务保障效率，缩短保障完工时间。

5 结论

构建了JOFDORA模型，在NSGA Ⅱ算法基础上，采用k-means聚类方法将种群分组，并增加了删减策略，提出了iNSGA Ⅱ算法用于模型的求解。在试验仿真部分，讨论了航电和特设专业的机务保障人员合并对于保障效率的影响。结果表明，在机务保障人员配置数量受限的情况下，专业合并会显著提升舰载机保障效率，缩短保障完工时间。