基于EDA算法的航母弹药调度优化研究

陶俊权，苏析超，韩 维，李亚飞

(1.海军航空大学， 山东 烟台 264001； 2.海军研究院， 北京 100072)

1 引言

舰载机作为航母这个现代战争中最重要作战平台的基本作战力量，其出动架次率是衡量航母作战能力的关键指标。而航空弹药转运作业能力则是影响舰载机出动架次率的重要因素。作为航空保障作业诸多作业之一，航空弹药保障作业需要完成弹药的贮存、转运、装配、挂载，所需要的安全性高、作业流程复杂、花费时间长。弹药从出库到挂载，环节多，需要从弹药库取出，通过下层武器升降机运送，依据武器类型判断装配地点，装配好的弹药再通过上层武器升降机或飞机升降机送达飞行甲板，最终在飞行甲板完成舰载机弹药的挂载。因此优化航母弹药转运调度，对提高舰载机保障效率，增强航母作战能力有重要意义。

航母航空弹药转运作业问题复杂程度高，约束条件众多，且求解难度随单批次转运弹药数量增加呈指数性增长。对于此问题的求解，国内学者已进行了很多研究。首先是对美军航母弹药转运流程的分析，文献[5-6]介绍了美尼米兹级航母的航空弹药组成及弹药转运基本流程，并通过分析美航母转运作业过程中遇到的问题并提出相应的改进建议，其次是对航母弹药转运作业问题的智能算法求解。文献[7-11]应用遗传算法及蚁群算法，对舰载机弹药调度问题依据不同的假设条件进行了优化。除此之外，文献[12]基于PERT网络，对航空弹药保障人员配置方案进行分析，优选出有限保障人员的配置方案。文献[13]应用基于T-S的模糊非线性优化方法，实现了对弹药组装和转运速率的控制。文献[14]考虑航空弹药保障系统的动态特征，借鉴Multi-Agent方法，建立了航空弹药动态调运优化模型。文献[15]将航母弹药转运问题抽象为2阶段多目标规划问题，深入分析转运约束条件，采用弹药转运优先级的方法建立了转运模型。

本文在对航空弹药转运流程及其约束条件进行分析的基础上，将问题抽象为资源受限项目调度问题，构建了基于模块化运输单元的弹药转运优化模型，并使用EDA算法进行了求解。该模型通用性强，可适应不同航母的不同弹药转运流程，模型精细程度高，可实现对每一辆弹药转运车的独立调度，最后用实验表明，该算法及模型可有效求解航空弹药转运问题，对作业效率进行优化。

2 弹药调度问题模型描述

弹药转运作业时间长、工作量大，涉及包括各类武器弹药、弹药转运车、武器升降机、弹药装配区等在内的众多因素，其保障效率是制约舰载机出动架次率主要因素之一，本节对弹药保障转运过程中的运输流程及约束进行具体分析，构建弹药调度问题的总体框架。

2.1 弹药转运处理流程分析

参照美“福特”级航母的航空弹药转运作业流程，舰载机弹药转运基本环节如图1所示。弹药管理人员依据该出动批次飞机所需弹药，确定弹药总需求量、种类，并将运弹任务分配至各弹库。运弹人员则因弹药储存方式不同采取不同手段取出弹药并考虑是否进行简单装配。完成上述步骤的弹药将等待下层升降机空闲，若空闲则将下层升降机调至该弹库实施升降机转运。若弹药需要装配台进行装配，将弹药转运至弹药装配区进行装配作业，否则转运至机库甲板。待上层升降机或多用途升降机空闲后，弹药继续转运至飞行甲板及各停机位处进行挂载作业。最后弹药转运车及运弹人员待升降机空闲后原路返回，弹药转运结束。

图1 弹药转运流程框图

2.2 弹药运输约束分析

一个批次的弹药转运任务需要许多弹药转运车，当最后一辆弹药转运车在停机位完成弹药装载作业并成功返回原位后，该批次的弹药转运任务成功完成。视一辆弹药转运车为一个独立运输单元，其完成转运任务并回到原位的时间花费设为，时间从该批次弹药开始转运任务起计算。若有个运输单元，则其时间花费分别为,,…,，因该问题存在多个可行解，为完成整个转运任务时间花费最小的任务目标，目标函数可设为最后完成任务的运输单元所处时刻距任务开始时间最短。即：

=min{}

=max{,,…,}

(1)

弹药转运最优任务目标的完成仍需满足以下约束条件。

1) 从某一弹库获得某种弹数量不超过该弹库储存的该种类弹数量上限。

(2)

式(2)中，代表第个运输单元从第个弹库所取的第种弹的数量。共有个弹库，种弹药。

2) 每个运输单元只从一个弹库取弹。

(3)

式(3)中，为状态变量。若第个运输单元从任务规定的第个弹库取弹，则值为1，否则为0。

3) 每个运输单元只取一种类型的弹药。

(4)

式(4)中，为状态变量。若第个运输单元取任务规定的第种弹药，则值为1，否则为0。

4) 每个运输单元弹药量不超过该运输单元容纳弹药上限。

(5)

式(5)中，代表第个运输单元承载弹药数上限。

5) 升降机承载的运输单元数量不能超过最大载运量。

(6)

式(6)中：为状态变量，代表所处的升降机，共有个升降机；代表第个升降机能承载的弹药转运车数量。

6) 单个弹库内转运设备同时转运弹药数量不超过设计上限。

(7)

式(7)中：代表第个弹库内正在转运的第种弹药数量；代表第个弹库可同时转运弹药数量上限。

7) 弹药装配区同时进行装配数量不超过容纳上限。

(8)

式(8)中，代表弹药装配区装配台的数量。

8) 一个运输单元只能前往一个停机位。

(9)

3 改进分布估计算法设计及其实现

3.1 分布估计算法的基本原理

分布估计算法(estimation distribution algorithm,EDA)是一种基于统计学习理论的群体进化算法,通过建立起概率模型来描述候选解在搜索空间的分布信息并以此解决问题，利用统计分析的工具，EDA从群体宏观角度建立一个描述解分布的概率模型，估计精英个体所在编码变量的潜在概率分布。在生成初始种群和初始化概率矩阵后，采用迭代方法估计最优解的分布。EDA总体流程如图2所示。

图2 EDA算法总体流程框图

3.2 调度模型的改进分布估计算法实现

本节中，航母的弹药调度问题，将通过建立针对弹药调度问题的特殊概率模型、基于EDA搜索机制的概率更新机制以及进行深度优化的局部搜索机制来进行求解。

3.2.1 编码方案

参考多模式资源受限项目调度问题，采用调度顺序+双重模式的编码方式。一个批次弹药所对应的所有运输单元按先后顺序进行调度，起始弹库及停机位作为每个运输单元所对应的双重模式，如图3所示。

图3 编码方案示意图

第1行代表各个运输单元的调度顺序，数字代表运输单元编号。第2行则代表按运输单元编号排列的各运输单元所属弹库。第3行代表按运输单元编号排列的各运输单元将要运输到达的停机位。

各个运输单元序号及其所包含的弹种与弹药数量由各停机位所需弹药的运输任务分配情况决定。如图4所示，一辆转运车可转运弹药a数量为2，则转运5枚弹药a的任务被分配给了3个弹药车运输单元，所有运输单元编号顺序按停机位及弹药需求任务依次排列，而每辆弹药所需运载弹药也由此确定。

图4 停机位弹药分配过程框图

3.2.2 多弹库多通道并行调度时序生成方案

航母弹药转运，弹药从不同的弹库出发，经由固定的转运通道转运至飞行甲板及停机位。由于各转运通道的运输路径之间可能存在交叉，全舰的单批次弹药转运任务无法转化为各通道的单独弹药运输子任务，因此需要建立多弹库多通道联合调度方案。具体流程如图5所示。

3.2.3 概率模型及概率生成机制

相较于其他智能算法(如遗传算法等)采用交叉及变异方式产生新的解来求解弹药调度问题，分布估计算法采用更简便的概率模型来解决这一问题，如何产生概率模型是设计一个EDA算法的关键问题。

本文所建立的概率模型包含2个概率矩阵，一个是×的调度顺序概率矩阵()，为运输单元总数。另一个是×的弹库选择概率矩阵()，为弹库总数。

1)()：该概率矩阵被用来预测每个运输单元在总调度过程中的顺序。

(10)

式(10)中，象征编号为的运输单元位于第个被调度位置上的概率，其大小表示运输单元在位置上的优劣性。初始概率如式(11)所示，以此保证概率估计及采样的公正性。

(11)

图5 多弹库多通道转运任务求解流程框图

2)()：该概率矩阵被用来预测每个运输单元选择不同弹库的概率，即：

(12)

式(12)中，象征运输单元选择弹库的概率，其大小表示运输单元从弹库出发的优劣性。同调度概率矩阵一样，该矩阵也用保证公平的初始矩阵来确定平等选择各弹库。表达式为：

(13)

另外，由于不同弹库所储存的弹药种类有所不同，弹库选择概率初始矩阵，应根据不同运输单元所搭载的弹药种类将相应位置的概率归零并重新分配每行的概率。

由于各运输单元之间不存在前后序约束，因此各运输单元可以按照编号顺序依次经过调度顺序概率矩阵，并最终生成一个完整的调度顺序。运输单元选择位置的概率为：、

(14)

若位置已被选取，则对应的列概率全部归零，即该位置不可再被选取，以保证位置的唯一性。

选取完各单元位置后，还需对各单元所属弹库进行选择，运输单元选择弹库的概率为：

(15)

由于运输单元所属停机位在分配运输单元弹药时已经固定，故无需进行选取。最终，经过调度顺序概率矩阵及弹库选择概率矩阵的选取，可以确定一个完整的调度顺序集。由于存在同一弹库取弹量不得超过存弹量等约束条件，确定运输单元所属弹库后，需进行检验，若不满足约束，需重新进行选取。

将确定调度顺序集的操作重复次，由此得到了一个拥有个个体的种群，为之后的操作做准备。

3.2.4 局部搜索

3.2.5 概率矩阵更新机制

为了更好地进行迭代，加速获得更加优秀的解，需要依据计算所得的个优胜解对概率矩阵()及()进行更新，其更新规则为：

(16)

(17)

图6 局部搜索流程框图

3.3 EDA算法总结

经过上述设计，基于EDA算法的航母弹药调度问题可以有总结表述如下：首先，初始化概率矩阵，以保证选择公平性。其次，使用多弹库多通道并行时序生成方案，生成个解，挑选其中个优异解并进行局部搜索以优化解的质量。最后，依据优化后的优异解对概率矩阵进行修改，并进行迭代运算，以求得最终的最优解。

4 仿真实验

本节中，算法的实用性会通过一个具体实例来证明。由图1可知，航母的弹药转运流程可根据弹药种类及特点的不同分为2种：一种弹药经弹药装配区装配后转移至飞行甲板停机位，另一种在弹库简单装配后经机库甲板到达飞行甲板停机位，具体转运流程及编号如图7所示。

图7 2种弹药转运流程框图

设某型航母共有11个弹库，分为1-3号、4-7号、8-11号3个弹库群。相对应的有10台升降机，其中6台下层升降机(3台对应3个弹库群执行任务类别1，另外3台对应3个弹库群执行任务类别2)；4台上层升降机(3台对应各个弹库群执行任务类别1，另外1台对应所有弹库执行任务类别2)。

在弹药转运任务设置上，设该批次航母弹药转运涉及5个停机位，上层升降机位于飞行甲板上的4个出口与各停机位之间存在独立的转运时间。共需运输3种类型弹药，A型弹1车1枚，弹库内3枚联装，经任务类别1进行运输。B型弹一车2枚，弹库内独立包装，经任务类别2进行运输。C型弹1车1枚，弹库内独立包装，经任务类别1进行运输。共需运输5枚A型弹、10枚B型弹、5枚C型弹且各停机位弹药分配平均，均为1枚A型、2枚B型、1枚C型。共需调度15辆弹药转运车，即15个运输单元。

EDA算法参数设置上，种群大小设定为200，局部搜索概率为0.05，学习速率为0.3，共迭代运行4 000次，对比未采用局部搜索的EDA算法及采用局部搜索的改进EDA算法，运行结果如图8所示。

由图8可以看出，采用局部搜索的改进EDA算法所获得的最优解优于标准EDA算法，收敛速度也有所超出，这是对解空间进行深度搜索的结果。

各弹药转运车执行各个调度工序的甘特图如图9，横轴为时间，纵轴代表各个运输单元的编号，各甘特块长度代表所耗工时，其内编号为工序编号。所得到的最优调度方案尽可能利用各升降机，以保证总调度时间最小，实现资源的有效利用。通过该甘特图验证模型满足式(2)至式(9)中的各项约束，证明了模型的合理性。

图8 2种EDA算法运行结果曲线

图9 弹药运输单元工序甘特图

5 结论

改进的EDA算法引入了双概率矩阵的形式，对初始种群的生成进行了改进。并结合了局部搜索，相较于标准EDA算法，对于解空间的深度搜索效果有了很大的提高。充分结合了EDA算法种群正反馈机制下的全局搜索能力以及对精英个体深度搜索后的快速收敛能力。采用弹药转运车运输单元为基本单位进行计算，优化了解的精细程度。通过实例仿真，验证了其在航母弹药调度方案设计中的实用价值。