作战指挥控制下利用改进遗传算法进行资源调度的方法

李嘉伦 王 鹏 吕志刚 李晓艳 付博雯

(西安工业大学电子信息工程学院 陕西 西安 710021)

0 引 言

战场环境不确定性下的作战任务部署旨在面对一系列约束条件时如何能将军事单位所拥有的各类平台设备资源合理地部署给参战任务[1]，使其能达到作战目标最优的发挥。其中协同指挥控制是组织调度的关键问题，如何合理有序地组合平台设备、调度作战资源是现代战争取得胜利的关键要素，也是实现作战任务协同规划[2]的关键内容。

当面临任务开展时，战场会受到复杂不确定事件的影响，需要考虑当前作战天气、突发任务、硬件性能配置等不确定事件。任务使命也会在执行过程中因诸多不确定因素而使资源属性、作战任务属性发生变化，导致初始调度方案不能按原计划执行，或者存在一定偏差。因此需要对作战方案进行组合角度优化调整，使其满足当前的作战需求，以达到军事组织结构调整代价最小化输出。

本文从作战任务资源约束调度的问题出发，建立作战任务调度统一化约束模型，给出作战求解问题的体系框架[3]，搭建如图1所示的模块化的作战任务调度问题解集架构，从理论方法层面模拟了作战要求，并在实验中测试了改进的自适应遗传算法，验证了所提方法的实用性和求解效果。

图1 作战任务统一调度化建模与求解总体目标体系流程

1 作战问题描述

在现代战争中，作战设备面临着多种恶劣天气的威胁干扰以及遂行多样化的军事任务的压力，在面对战场上敌军时，对常规目标、敌军无人机、无人车、导弹等的监测防御中可能会消耗大量的资源配备。与此同时，加之不同的恶劣天气影响或者作战任务的紧急部署都会在一定程度上加重资源的重复或者冲突、低效的利用，降低了感知资源的利用率。

为了有效解决各平台的不同需求，从符合战场的约束条件如任务完成时间、部署搭配、感知负载能力、系统快速稳定性出发，制定相应的任务调度部署策略，同时达到资源在最合理的调度应用下使作战效能得到提升。本文研究了不确定环境下的战场资源调度问题，在指挥控制结构设计中，明确了各级协作匹配关系，将所涉及到的平台设备分组聚类成相应的不同参战组合类型，指导接下来的作战性调度部署。

1.1 作战事件相关定义

作战设备是指参与此次作战事件所用到的感知设备的集合，它可以隶属不同的类型，也可以是同类型不同型号设备。设q为作战设备集合，q∈φ1，集合φ1={1，2，…，Q}。

作战任务是指由决策实体指挥发布下的作战要求及作战使命项目下的各属性类(阶)作战环节。m为作战任务集合，m∈φ2，集合φ2={1，2，…，M}。

作战时刻是为了描述处于某时刻下正在进行的作战的时间分布情况。i为要考虑的时刻，i∈φ3，集合φ3={1，2，…，I}。

作战环境是指正在进行作战任务时决策实体控制的设备所承受的恶劣天气等环境因素。l为作战环境集合，l∈φ4，集合φ4={1，2，…，L}。

作战搭载平台是指参与作战执行任务的基本单元。一个作战平台至少调度部署一台作战设备。u为平台的种类集合，u∈φ5，集合φ5={1，2，…，U}。

指挥实体是组织兵力中负载指挥调度的要素，具有作战指挥、决策处理的能力。在作战过程中决策实体至少控制一个平台资源。CM为指挥实体，CM={CMc}(c=1,2，…，C)，其中C为表示指挥实体的数量。

作战资源调度方案体现了军事组织所拥有的单位作战元素与作战任务之间及作战不确定性环境的匹配关系，反映了作战任务被执行的情况。资源调度方案[1]可用式(1)和式(2)两关系式来进行表示。

(1)

式中：xql为设备-环境分配变量,∀q∈φ1,∀l∈φ4。

(2)

式中：wqm为设备-任务分配变量,∀q∈φ1,∀m∈φ2。

1.2 作战协同相关定义

图2简单模拟描述了作战情况下环境、设备、任务三者之间的关系[4]。当作战任务下发时，要及时确定当前及作战时的环境情况，如当正处于：l1层时，因其特殊的环境属性，为了保证更高效的作战效能只能选择适应能力更强的作战设备q1、q2;l2环境层时只能更适用作战设备q2、q3;l3层时选择其对应适应性更强的作战设备q3、q4。接下来根据任务属性的要求，进一步考虑作战规模、范围、力度的变化，认定其中存在的执行关系，如执行任务m2时同时需要q2、q3设备进行作战，然而q2、q3可能隶属于不同属性的类型，且受制于的不同的作战模式及资源配置。因此q2、q3在执行当前作战事件时存在可调度资源下的协作控制且在当前作战情况下存在着一定组合搭配可能。

图2 模拟作战情况示意图

2 资源调度模型设计

2.1 调度资源约束关系

(1)时间资源约束。在作战调度任务中，时间上的作战部署规划尤为重要[5]。假设共有m个作战任务类型，其中每一个任务段至少有1台或1台以上的协同并行执行作战任务。每个感知设备i可能经历不同环境层l或者处于不同的M任务状况中。每次作战任务一旦开始就不能中断。第q个感知设备在每次接收到新的作战任务时，都应重新适应新的环境层l，并预留任务前的缓冲准备时间R。在任意两个任务阶段即第m阶段和第m+1阶段或者环境层l之间的转变都会有一个切换蓄能时间T。规定在任意时刻一台设备q一次至多参与一个M任务。

Pq,m,l为第q个设备在第l层第m阶段的所需作战时间；Tq,m,m+1为设备在任务层之间的任务组合切换蓄能时间；Cq,l为第q个设备在第l层完成既定任务所需总时间。式(3)为新任务阶段的开始到结束的时间要小于此既定总任务的完成时间。

Pq,m,l+Rq,m,l+Tq,m,m+1≤Cq,l

(3)

式(4)保证作战效率，切换准备时间要远小于作战时间。

Rq,m,l+Tq,m,m+1≪Pq,m,l

(4)

在调度组合事件中，将作战任务的各类参战时间关系下的约束条件及调度时刻记为h1i。

(2) 性能资源约束。性能资源约束可分为能耗与功率约束，通常感知设备允许在短期具有较大发射功率，但在该功率下将产生大量热量与电磁干扰，当热量过高或者电磁干扰密集时都将损坏设备乃至烧毁设备，即影响设备的正常使用，可见大功率发射设备不能长期工作在大功率状态下。在功率的损耗变化期间，能耗的流失也影响着系统的进程。

设备发射接收功率在某时刻必须满足输出功率约束如下：

pout,ref(i)=Pb1(i)+Pc1(i)

(5)

(6)

(7)

式中：Pb1(i)和Pc1(i)为此次事件中感知设备的储存系统和采集传输系统的吸收功率；αd,b和αc,b为支撑其性能能量元件的充电和放电效率；αd,c和αc,c为支撑其采集传输能量元件的充电和放电效率。

此系统工作状态在任意t时刻满足的输出能量约束为：

Erate,b,c(i)≤Eb,cβb,c

(8)

式中：Erate,b,c为当前工作实测下输出能量，其等于释放能量减去损耗的能量；Eb,c为设备最大负荷能量；βb,c为元件的极限输出能力系数。

根据以上条件，将性能资源约束描述为各设备在不同作战天气下完成作战任务时所处理资源的利用率，该系统性能资源记为h2i。

(3) 硬件配置条件约束。在不同的恶劣天气下作战或者作战任务开始之前或结束之后，作战设备都有着不同作战硬件配置，受到其干扰与调度所呈现的适应性也就有所不同。尤其在一个组合里的设备，其还需要考虑各设备之间的干扰性。不同处理任务的感知信号都需要在计算机处理器中进行信号处理[6]。处理器配置属性对于一些不同类别的感知设备，在其镜头焦距、分辨率等自身硬件条件变化限制中，都会对调度事件的进程有一定的影响，因此设定各个设备的硬件配置约束条件。

(9)

式中：n为此次参战中所涉及到的硬件设备数量；γk为第k件硬件设备在处理事件i时刻所占的硬件资源；δmax为此次作战任务硬件处理系统可负荷最大处理量；α为受不同作战天气影响下各设备面对作战任务时归一化参考后的适应程度比，其归一化参考标准是能见度，是根据该设备性能在当前环境下与正常环境下的探测水平精度之比所决定。

R为当前作战环境探测距离：

(10)

式中：L为当前作战环境下的能见度，其受到当前消光系数、颗粒浓度、直径及降雨(雪)量影响；τ为大气透过率，其可能受到战场环境中各类化学烟雾气体的影响，所以在计算时，需要考虑光在大气中的总透过率；G为斜程大气修正系数，取G=0.19。

因此在作战任务中，将完成参战事件所发挥的硬件配置处理资源记为h3i。

2.2 约束条件分析及建模

在这三类的相互约束下，战场上的作战指挥中，需要作战在任务、环境下协同控制。作战环境、任务决定着设备不同的异构度，进而影响种群个体的适应度。匹配约束下异构度公式如下：

(11)

假设各类时间约束条件符合改进的指数函数的变化趋势(规划下的作战能力随时间的推移先呈增长趋势[7]，但在约束条件下会在一定时刻达到饱和状态，如若再运行下去会使作战能力呈小范围下降趋势)，其符合作战负载运转下的变化趋势。

通过对各类不同设备属性的分析，以其设备探测距离v和感知精度p作为主要的增益函数约束变量，对不同q感知设备设置相应的权重参数，并进行fq归一化函数处理，最终建立多项式函数来反映性能上的优劣，效能函数G定义为：

(12)

本文资源调度方案体现了约束条件的匹配关系，反映了作战环境、任务的部署状况。采用作战能力负载PCR(Combat-Range to Precision)作为评价作战调度方案优劣性的增益函数。PCR的计算如式(13)所示。

(13)

综上所述，以最小工作负载为整个调度事件优化模型：

minPCRmax

(14)

3 基于调度事件改进多层级关联自适应遗传算法

传统遗传算法求解感知设备组合调度事件问题时存在早熟收敛、局部最优陷阱等问题，无法准确高效地寻得全局最优解，进而使得调度算法耗时较长，调度效果较差。

3.1 基于聚类选择方法的种群初始化方法

传统的随机选择方法，容易使算法过早收敛和陷入最优解，聚类的思想将个体按照其适应度值的大小进行组合，在接下来的染色体编码交叉选择中，保证初始种群的多样性。具体步骤如下：

(1) 依据各设备的适应度大小对初始化种群进行分组，组合的个数即为聚类数V，并根据聚类算法设定聚类初始中心(f1,f2,…,fV)。

(2) 对群体中每个设备按个体与中心相邻之间的相似距离最近原则进行聚类，即fi-fv=min|fi-fv|。

(3) 选取最小适应度的数据点作为根节点，构建聚类树结构，通过步骤(2)寻找叶节点，并计算二者距离，将其划入各自聚类中心。

(4) 将剩余数据归入适应度比其小且距离最近的样本所在簇，即与叶节点划为一类的组合中，直到所有设备组合类别确定为止。

3.2 染色体编码方式

编码方式是编码空间向问题转化的桥梁和纽带，需要对染色体编码才能获得染色体的目标值；本文采用一种自组架构的矩阵形式的编码方案及二维编码方式[9]。

每一条染色体上包含所参与作战任务的q个设备，第一维是此次参战设备的序列编号，第二维是多层次关联选定下的不同聚类组合编号，不同作战任务阶段、恶劣天气环境，都将决定不同的组合编号。该组合编号是由调度约束条件h1i、h2i、h3i作为分析基础聚类而成的，其本质是将相同属性(约束条件相似)按照距离的原则迭代而成的。每个组合里的设备都具有不同属性优势，不至于出现作战缓存时间上的错乱、资源上的冲突、性能上的干扰。因此采用此方法事先给予要参与的作战设备进行调度约束条件下的聚类组合，为此时的层级关联编码提供了第二维编码的数据。

赋予每一段染色体在某时刻下所处事件的实时状态[10]，即每条染色体由q个二维矩阵构成(根据此次作战态势来进行设备的组合调度设定)，而每个矩阵Aq(第q作战设备)对应一个基因位，则矩阵Aq如下：

（3）C表示第r次摸到黑球是在第k次摸球时发生，我们仅需考虑前k次摸球即可，此时样本空间有（M+N）k个样本点。第k次摸到黑球，有M中可能，而前k-1次摸到r-1个黑球，由二项概率计算有中可能，故C中有M个样本点，由古典概率定义有

(15)

每个作战设备被分配到调度组合编号是根据聚类算法结果分配的，相比传统的随机初始化方法，其提供了更优的初始化种群个体，在保证初始种群多样性的同时确保相对最优的个体数量。

当作战环境变量确定后，匹配到每一条染色体上可存在的q个基因位的序列，即第二维编码基因序列。根据所处的问题的规模不同，编码处理的染色体上基因数也会有所不同，其每个染色体都对应着不同种类的组合调度方案。

第一维中出现的同层关联应该在第二维编码组合中进行有效的层次关联组合[11]，通过相连属性的组合搭配，进而可以达到迅速调度的协同指挥。

多层级资源动态调度组合在染色体交叉变异过程结构如图3所示。分配完成后参战设备都会对应展开其基因序列，在第二维编码中进行选择调度，将有相同组合的设备关联起来。此时作战状态的多层级资源组合中的某个资源在匹配关系的范围内进行优秀遗传个体的交叉更换，以获取更为合理的下阶段作战资源组合情况。

图3 染色体二维编码结构

最终，当种群繁殖到规定代数后，对各染色体的适应度大小进行计算并且筛选，满足调度约束的增益、目标函数的结果将会生成。

3.3 适应度函数

指挥控制设备资源调度的目的主要是减少作战任务总负载的同时兼顾各个决策实体控制的组合设备的工作负载尽可能差异小，更符合实际战场需要。

根据当前作战任务与环境状况及相关约束条件，对每一条染色体所对应的增益函数进行适应度评估，对于可行的染色体，采用决策实体控制下的异构度系数klm和效能函数G所构成的增益函数均方根形式作为本文算法的适应度函数即表示当前作战任务的工作负载情况，本文适应度函数表示为：

(16)

3.4 遗传算子

标准的自适应遗传算法(Adaptive Genetic Algorithm，AGA)在进行交叉和变异操作时并没有充分考虑进行运算的个体的优劣性[12]，只采用固定的交叉率和变异率，很大程度限制了算法的收敛速度及收敛稳定性。

本文算法在对于自适应交叉和变异算子的设定时，考虑到其区域处于靠近或者分离最优解集时，会出现收敛性的波动和陷入局部最优的可能，此时线性的适应度算子就不能很好地约束函数的变化。因此本文采用提升鲁棒性的分层三角稳定性的非线性自适应计算方式，融入约束正弦稳定性函数改善算子均率范围扩张性，稳定体现了均值平均度，能更好地跳出局部最优解,改进后的遗传算子如下：

(18)

式中：fmax-favg表示种群的收敛程度；f′表示当前个体适应度值。当fmax-favg减小时，表示favg向fmax靠拢，即向最优解靠拢。

由式(17)和式(18)可知，当个体适应度值接近于最大值时，由分层正弦函数约束其交叉率和变异率均趋近平均适应度。该方法在种群进化初期，解集空间较分散，使交叉概率增大，加速了搜索解空间；为了防止有效基因被破坏，使变异概率减小。若是处于种群进化后期，该方法有助于保护优秀个体，防止交叉和变异操作变化对优秀基因的破坏。

通过对研究内容采用本文改进的遗传算法，可以解决多层次关联下的资源调度问题[13]。图4为此算法调度处理过程，在作战天气确定的同时，任务集发布，匹配该任务属性下的多资源协同约束，进行多级资源工序的选定组合调度计划操作，最后经本文算法编码流程生成调度组合优化方案。

图4 改进遗传算法处理过程

4 仿真分析

4.1 实验配置

本文使用 Visual Studio Code 及Python 3.7.2 64-bit环境进行仿真实验。将本文算法与其他优化算法在控制优化等方面进行多方位对比，根据仿真结果，验证算法在组合调度方面的时效性以及在避免早熟收敛上的优越性。

4.2 实验案例与结果分析

4.2.1仿真实验1

通过对作战模拟指挥控制数据的分析，采用本文改进遗传算法的层次聚类算法对平台、设备进行组合编排[14]并对调度组合结果验证分析。表1为战场环境拟定配置方案，其中环境变量l1、l2、l3分别表示为雨、雪、雾三类天气。本文参与设备资源调度的环境选择l1雨天下的环境，设定该天气环境下各类设备的适应分配关系情况。

表1 模拟战场环境参数设置表

根据表1提供的数据，融入调度资源约束及分配策略的算法能合理地对所参与的设备平台进行聚类组合搭建，所聚类的结果在属性配置上都能匹配各自任务环境所提出的作战状要求，并对其实行多层级协调控制编排组合计划部署。表2为调度分配关系设置，其初始设备资源调度方案如图5所示。

表2 任务-平台-设备分配关系表

图5 初始设备资源调度方案

令任务完成的最低增益G=1.0，以初始调度方案执行至i=13时刻时，接到新任务M4，M4出现的时刻在任务时序列表中的任务1执行完成后，持续时间15 s。利用基于高度事件的改进遗传算法(IAGA)对新任务下达情况的资源调度方案进行策略调整。

当新任务M4发布时，任务M4将被合理调度分配到设备资源，通过IAGA得到最优的染色体编码为{0，0，1，1，1，1}，表示分配Q3、Q4、Q5、Q6共同执行任务M4，该染色体增益为1.175，目标函数值为5.61，则此时调整后的作战设备资源调度方案甘特图如图6所示。

图6 新任务发布后设备资源调度方案

表3为实际作战调度已定资源组合，已定资源组合满足多层级调度资源约束条件，保证了任务完成增益，同时保证整体执行任务时间最短。对于调度设备资源处理任务时，设备须尽可能满足当前任务资源、环境需求，并正好处于休眠状态，能减少缓存时间，保证处理时间最短。生成的优化调度方案保证了接下来的目标函数及增益仿真实验有效实现。

表3 多层级已定资源组合

4.2.2仿真实验2

对小规模作战环境下的调度遗传验证，具体实验参数设置为种群大小250,迭代次数500,染色体长度25,精英个体5,交叉概率0.8,变异概率0.01。

本实验以适应度函数作为实验的目标函数，首先根据约束条件聚类初始化种群，再根据染色体二维关联编码方式及改进遗传算子进行算法迭代，使得IAGA在求解的速度和有效性方面更好。

为了验证IAGA在资源调度问题上的优越性，将其与常用的调度算法中的模拟退火算法[15](SA)、粒子群算法[16](PSO)、自适应遗传算法(AGA)进行仿真对比分析，得到仿真结果如图7所示。

图7 遗传算法性能比较

可以看出，IAGA在前期随着迭代次数得增加，其算法性能有着明显的优势，其能最早达到稳定模式，且在迭代到450次左右时，当各类资源所具有的处理任务的能力都已基本能满足所参与任务的需求时，IAGA仍能取得最高的增益。因此本文算法对组合调度的能效性和时效性上都有了一定的提升改进。5种算法仿真结果对比如表4所示。

表4 遗传算法性能对比表

4.2.3仿真实验3

当战场环境局势相对分散且紧急的时候，作战的部署往往需要应对一定规模下军事任务的变换转型。由于作战任务的属性以及作战对任务部署强度的不同，在面对新增任务类、阶段的集中处理时[17]解决具有一定规模下的调度资源问题也成为了本文模型鲁棒性需要考虑的范畴。通过对增加不同任务规模下的数量或者阶段变化来反映本文模型的目标函数值与遗传迭代次数的变化趋势，进而分析本文改进算法性能优势。

假设在本次作战事件中，模拟战场任务数目M会增加至5、10、15类(阶段),新增任务的发生时刻用蒙特卡罗方法随机生成。本次实验对每组实例迭代100次，并测试50次取平均值,算法仿真结果如图8-图10所示。

图8 M=5类(阶段)任务作战规模下算法对比

图9 M=10类(阶段)任务作战规模下算法对比

图10 M=15类(阶段)任务作战规模下算法对比

表5为不同作战规模下的算法性能对比。

表5 不同作战规模下的算法性能对比表

通过表5可以看出，改进的自适应遗传遗传算法在与传统自适应算法在算法性能上存在相对的优势，即本文算法优于AGA,具体体现在能为作战资源的调度安排节省约25%的作战调度时间。另外在三类不同的作战规模下，相比AGA，本文算法在模型稳定时的收益率(minPCRmax)平均降低了6.7%左右,说明本算法中的工作负载(目标函数)得到了稳定的收敛且逐渐在完成相同作战规模时的工作负载更加均衡，作战资源调度更优。

综上，本文算法在收敛模型的整体性上适应程度更好，获得更稳定的搜素性能及更优的搜索值(更小的PCRmax值)，可以适应更多的作战规模变化;面对不同任务规模数量的变化时，能够更快地完成任务调度的变化，提高最优解的质量及收敛性(能够更快跳出局部收敛，避免进化停滞)。

5 结 语

本文所建模型具有应对不同战场规模的能力，在一定程度上能够解决战场环境变化下组织设备调度的不合理问题，缩短了各类资源收敛融合时间，提高了作战的调度时效性，并且增加了联合各类作战设备的战场态势效益。然而本文没有考虑算法任务执行精度、成功执行概率等方面，也缺乏考虑任务资源的动态调整规划，这将是今后改进的方向。