基于改进差分进化算法的舰面保障作业优化

刘小路，杨春辉，崔荣伟，崔海波，刘子玄

（1.海军工程大学，湖北武汉 430014；2. 92785部队，辽宁葫芦岛 125000；3. 92823部队，海南三亚 572000；4.海军航空大学，山东烟台 264001）

舰载机着舰后，需要在完成挂弹、加油、通电检查等一系列舰面保障作业之后才能再次出动。由于舰面环境狭小且复杂多变，舰面保障作业周期较长且呈现高度动态不确定性，因此，舰载机舰面保障作业调度效能是制约舰载机出动率和航母编队综合作战能力的重要因素。相关资料显示，美军最新一代“福特”级航母采用先进的“一站式”舰面保障技术和智能调度技术，使得舰载机出动能力相对于“尼米兹”级航母提升了33%，极大地增强了美军航母编队的威慑力和打击能力。我国对于航母的研究工作起步较晚，目前大多采用基于人工经验的作业调度模式，不仅调度效率低下，而且易发生危险，因此，亟须发展基于数学模型和先进决策优化算法的舰面保障作业智能调度技术。

国内外学者的相关研究为舰面保障作业优化提供了较多可借鉴的经验。韩维等分析了舰载机舰面作业的流程约束和资源约束，设计了双种群模糊引力搜索算法，用于作业流程的优化求解；Cui 等在给出舰面保障作业优化模型的基础上，设计了双种群多算子遗传算法用于模型求解。文献[2]和[3]均在算法中引入双种群结构以提高求解能力，并通过仿真验证了算法的优越性。苏析超等研究了一体化模式、大机组模式和单机机组模式下的甲板机务勤务作业调度问题，为保障作业人机匹配模式的选取提供了理论参考。文献[5-7]研究了舰面保障作业调度和资源配置联合优化问题，并提出了高效的优化求解算法框架。其中：文献[6]给出了求解该类问题的通用超启发式算法框架，降低了后续算法设计的复杂度；文献[7]分别以边际算法和人工蜂群算法为外、内层框架，研究了人员配置数量对保障效率的影响；文献[8-10]研究了不确定环境下的舰面保障作业鲁棒调度问题，在算法中嵌入了有效的预约束调度策略和资源鲁棒分配策略，给出了合理的鲁棒调度求解方法。

本文首先分析了舰面保障作业流程，建立了多机舰面保障作业调度（multi-aircraft flight deck operation scheduling，MAFDOS）优化模型；然后，设计了改进差分进化算法（modified differential evolution algorithm，MDE）用于模型求解，该算法采用基于作业开始时间改进的随机键编码方式和并行变异算子结构，提高了算法搜索效率；最后，设计了仿真试验，给出了典型保障任务的调度方案，并研究了变异算子类型对于算法性能的影响。

1 MAFDOS模型建立

舰载机舰面保障作业调度问题是一类高度复杂的资源受限项目调度问题（resource-constrained project scheduling problem，RCPSP），作业过程中既有考虑作业工序的流程逻辑约束，也有保障人员、设备等的资源约束。此外，由于调度方案需要下达至单个作业单元（人员以及设备），因此，还需要考虑资源分配规则。

2 MDE算法描述

基于RCPSP 建立的MAFDOS 模型是一类具有NP-hard性质的复杂组合优化难题，常规的分支定界等精确算法难以在有限时间内求解。近年来，研究人员将重点多放在启发式算法的设计与求解上。DE 是经典的群智能进化算法，由Storn 等提出，目前，在优化领域被广泛应用。本文在传统DE算法的基础上，根据MAFDOS 问题的特点，采用基于作业开始时间改进的随机键编码方式和并行变异算子结构，以增强算法的搜索效率，提出了MDE 算法用于MAFDOS模型的求解。

2.1 MDE算法流程

MDE 算法伪代码，如表1 所示。种群大小为。首先，初始化种群个体后，依次选择当前种群个体作为目标向量（target vector）；其次，针对该目标向量，采用并行变异算子结构生成多个变异向量（mutation vector）；再次，针对各变异向量，采用交叉算子产生其跟踪向量（trail vector）；最后，从跟踪向量和目标向量中选择最优个体遗传至下一代，达到算法停止准则之后，算法结束，输出种群最优个体。

表1 MDE算法伪代码Tab.1 Pseudo code of MDE algorithm

续表

2.2 编码

Debels 等指出，随机键编码和活动列表编码是求解RCPSP 问题常用的编码方式。任务列表编码的缺陷是个体经过交叉、变异等操作后，容易产生不满足工序流程逻辑约束的非法编码，若再采用修正机制修正非法编码，则会显著增加计算量。随机键编码则弥补了这一缺陷，其采用随机键表示工序调度的优先级（随机键越小，调度优先级越高）。1 种调度方案通常可以对应多个随机键编码，这无疑增大了算法的搜索空间。为了进一步提升搜索效率，本文提出的MDE算法在随机键编码的基础上，采用基于作业开始时间改进的随机键编码方式，如图1 所示。个体解码评价适应度后，以个体对应的调度方案中各工序的开始时间S代替个体编码。采用这种编码方式，可以确保个体编码和调度方案的一一对应，在减小算法搜索空间的同时不丢失可行解。

图1 基于作业开始时间修正的随机键编码Fig.1 Random key coding modified by the start time of the operation

2.3 解码

解码操作是指利用调度生成机制实现个体编码向调度方案映射，是评价个体适应度的关键阶段。RCPSP 问题的调度生成机制主要有串行调度生成机制和并行调度生成机制2类。并行调度生成机制解码的搜索空间是解空间的1个子集，当问题规模较大时，不能保证会搜索到最优解，因此，本文采用串行调度生成机制解码，采用该机制实现个体解码流程，如图2所示。

图2 串行调度生成机制流程图Fig.2 Flow chart of the serial scheduling generation scheme

2.4 并行变异算子结构

变异算子用于产生变异向量，从而引导算法能够持续探索解空间，避免算法陷入局部最优。在DE 算法中，主要采用以下5类变异算子。

1）DE/rand/1变异

式（9）～（13）中：V表示第个变异向量的第次迭代编码；X表示当前第个目标向量的第次迭代编码；X～X表示随机选取的5 个互不相同的个体；表示当前最优个体；是变异率。

通常，采用单一变异策略虽会使DE 算法迅速收敛，但无法保证解的全局最优性，因此，本文采用并行变异算子结构。针对同一目标向量X，同时采用多个变异算子分别生成变异向量，经过交叉操作产生跟踪向量后，从跟踪向量和目标向量中选择适应度最好的个体遗传至下一代。

2.5 交叉操作

3 仿真试验

本节通过构建案例进行仿真试验，验证模型和算法的有效性。假设某型航母甲板共有12 个保障停机位，可为舰载机提供燃油、电源、氧气、氮气和液压油等5类消耗性资源。单机保障共有19道工序，各工序的“前驱—后继”约束关系，如图3 所示。工序1 和19分别是虚拟开始、结束工序，受文章篇幅限制，各工序工期及保障所需的资源未在文中列出。

图3 单机保障工序流程图Fig.3 Flow chart of operation scheduling of single aircraft

共设计3 组出动仿真任务，各任务舰载机保障所在停机位及入场时间情况，如表2所示，其中“—”表示该停机位无待保障舰载机。保障过程中共涉及航电、特设、机械和军械4类保障人员，保障人员配置数量与任务规模相关：任务1中，各类人员配置数量分别为3、3、5、6；任务2中，各类人员配置数量分别为4、4、6、8；任务3中，各类人员配置数量分别为5、5、8、10。

表2 各出动仿真任务舰载机在不同停机位入场时间Tab.2 Parking spot of the aircraft and its released time 单位：min

MDE算法参数设置情况为：种群规模=50，交叉率=0.3，变异率=0.7，算法终止准则为评价次数达到5 000 次。采用DE/rand/1 和DE/best/1 变异算子组成并行变异算子结构，对3 组出动任务进行试验仿真。为了验证算法改进效果，采用DE 算法同步进行仿真试验，DE 算法参数设置情况与MDE 算法相同。各任务保障完工时间收敛情况，如图4所示。

图4 保障完工时间收敛情况Fig.4 Convergence curve of the makespan

从图4 可以看出，随着保障规模的增大，MDE 算法所得最优保障完工时间增大，且各仿真任务中MDE算法收敛性优于DE 算法。任务1 的保障人员分配方案甘特图，如图5所示，其中，符号Lp表示第类第个保障人员，I-表示舰载机的第道工序。经过检验，分配方案满足各项约束，验证了模型和算法的有效性。

图5 任务1保障人员分配方案甘特图Fig.5 Gantt chart of the personnel allocation plan in mission 1

进一步地进行仿真试验，研究不同种类变异算子组成的并行变异算子结构对于MDE算法的影响。对第2.4节所示的5种类型的变异算子进行两两组合，共可产生10 种类型的并行变异算子结构，以数组[]表示并行变异算子结构中两变异算子类型，和的取值均为1～5。针对3 组仿真任务，算法独立运行10次，算法终止准则为评价次数达到5 000次，以10次独立运行所得保障完工时间的平均值（Ave.）、最优值（Bes.）作为性能指标，结果如表3所示。

表3 并行变异算子结构对MDE算法性能影响情况Tab.3 Influence of the parallel mutation operator structure on the algorithm performance单位：min

从表3 可以看出，由DE/best/1 和DE/rand/2 变异算子组成的并行算子结构在各组仿真任务中表现均优于另一组合，因此，在后续使用中，可采用DE/best/1和DE/rand/2 构成的并行变异算子结构，以期获得更优的调度方案。

4 结论

本文研究了舰载机舰面保障作业优化问题。在分析舰面保障作业流程约束的基础上，以最小化舰面保障作业完工时间为目标函数，建立了MAFDOS 模型，设计了MDE算法用于模型求解。案例仿真表明，采用MDE算法生成的调度方案可以满足MAFDOS模型的各项约束，可用于舰面保障作业调度方案的制定，MDE 算法收敛性优于传统DE 算法，由DE/best/1和DE/rand/2 变异算子组成的并行算子结构可以有效提高MDE算法的寻优能力。