基于遗传算法的作战任务分配和资源调度问题研究_刘建.pdf

59兵工自动化 Ordnance Industry Automation2023-07 42(7)doi:10.7690/bgzdh.2023.07.013 基于遗传算法的作战任务分配和资源调度问题研究 刘 建，陈桂明，李新宇(火箭军工程大学保障学院，西安 710025)摘要：在作战行动中出现多任务与多种保障资源合理调度困难的问题十分常见。笔者以任务完成的总时间最短为目标函数构建数学模型，使用遗传算法进行迭代优化得到保障资源调度的全局最优解。对遗传算法进行自适应改进、移民交叉算子操作和迭代条件优化，解决了过早收敛无法求出全局最优解的问题，并使算法运行效率提高了76.4%。仿真实验结果表明：该方法切实可行，可以快速准确地完成多种保障资源调度并形成任务分配方案，满足现阶段作战部队资源保障的现实要求。研究成果在高效完成保障资源调度的同时不产生冗余负担，具有较好的应用价值和发展前景。关键词：任务分配；资源调度；装备保障；遗传算法 中图分类号：TJ06 文献标志码：A Research on Combat Task Assignment and Resource Scheduling Based on Genetic Algorithm Liu Jian,Chen Guiming,Li Xinyu(College of Operational Support,Rocket Force University of Engineering,Xian 710025,China)Abstract:In combat operations,it is very common to have difficulties in the rational scheduling of multi-task and multi-support resources.In this paper,a mathematical model is constructed with the objective function of the shortest total time of task completion,and the global optimal solution of support resource scheduling is obtained by using genetic algorithm for iterative optimization.The genetic algorithm is improved by self-adaptation,the operation of emigration and crossover,and the optimization of iterative conditions,which solves the problem that the global optimal solution can not be obtained by premature convergence,and improves the efficiency of the algorithm by 76.4%.The simulation results show that the method is feasible,and it can quickly and accurately complete a variety of support resource scheduling and form a task allocation scheme to meet the realistic requirements of combat force resource support at this stage.The research results have good application value and development prospects,which can efficiently complete the support resource scheduling without generating redundant burden.Keywords:task allocation;resource scheduling;equipment support;genetic algorithm0 引言 对多种保障要素进行统一调度，可以有效解决长期以来多种保障要素独立行动、不协调、不同 步、保障能力不均衡的问题1。现代作战任务往往是多任务交错并存且需要多种保障要素，而保障资源在一定时间内的供给量及保障能力是一个有限的随机变量2。科学合理地制定任务分配计划及资源调度方案，对充分发挥保障效能，高效精确地完成作战任务至关重要，从而实现“任务资源时间”三者之间的最佳匹配3。资源调度问题的研究通过协同任务规划得到了初步解决，但仍存在着诸多问题。张家良等4只考虑了任务时序逻辑关系约束和任务完成效能约束，任务需求和实际作战能力仍存在不匹配的问题。王艳鹏等5-7基于动态列表规 划(dynamic list scheduling，DLS)方法，结合遗传算法(genetic algorithm，GA)和量子遗传算法(quantum genetic algorithm，QGA)提出的混合任务分配方法以及针对装备保障任务规划问题，提出基于优先排序和粒子群优化(particle swarm optimization，PSO)的混合任务规划方法，与其他启发式智能优化算法一样，普遍存在着全局搜索能力与局部搜索能力难以协调等问题。姚敏8使用的多种群遗传算法通过研究多目标并行调度问题一定程度上克服了 GA 的弊端。笔者针对部队作战与装备运用的实际特点，确定任务分配和资源调度的约束条件，构建保障资源调度模型，设计一种全新的资源分配算法，并通过遗传算法进行优化迭代。通过一个仿真举例完成对 1 收稿日期：2023-03-27；修回日期：2023-04-20 作者简介：刘 建(1987)，男，山东人，从事装备保障与资源优化研究。E-mail:。60 兵工自动化第 42 卷算法的检验，得到任务序列甘特图和资源调度分配方案，证实了该算法的可行性和实用性。对传统的遗传算法进行了改进，算法性能进一步提升。1 问题描述与模型构建 在多种要素保障多任务实施的问题背景下，分析约束条件，建立模型假设，通过对资源调度优化的指标设计确定优化指标函数，构建优化数学模型。1.1 问题描述 实施作战行动，在保障资源有限的前提下，既要满足任务的实施要求，又要尽可能使任务完成时间最短。假设保障单元需要保障 n 个作战任务。每项任务需要的保障要素数量各不相同。n 个任务之间有多种联系，可以是串行的、并行的，也可以是串并共行的，如图 1 所示。图 1 作战任务序列 n 个任务可构建出一个任务集 T=Ti，其包含的属性有任务完成时间，以及任务保障要素需求向量，构建一个任务需求要素表直观地展现出来，如表 1 所示。作战单位拥有的保障资源数量是有限的，可用编组保障要素属性如表 2 所示。表 1 作战任务要素需求 作战任务 要素需求向量 开始时间 任务完成时间 结束时间油料车 通信车 诸元车 R Rn T1 x1 y1 z1 Ts1 t1 Tf1 T2 x2 y2 z2 Ts2 t2 Tf2 Ts3 Tf3 Tn xn yn zn Ts4 tn Tf4 表 2 编组要素属性 属性 编组拥有的要素资源向量 油料车 通信车 诸元车 R Rn 拥有数量 x y z 在作战任务的牵引下，将保障要素按照其需求进行分配。剩余的保障要素数量可以用于其他任务的保障，以同时进行的所有任务定义为一个梯队，梯队之间为串行序列。根据此办法依次求得满足约束条件下任务完成的序列模式和资源调度方案。1.2 问题约束与假设 假设问题资源更新时不考虑损耗情况，一个梯队打击完成后，所有保障要素就地进行原料补给与休整，并可以恢复到最初状态，等待下一梯队的保障行动，忽略了天气、人员士气、单位训练水平、装备质量等无关变量的影响，不再考虑其对作战保障效能发挥的影响。1.2.1 任务需求约束 参与第 u 项任务的第 j 种保障要素用 Xju描述，该量必须要大于等于完成该任务的需求量即 Yju。XjuYju。(1)1.2.2 资源限定约束 同一梯队打击中，要素消耗后不能补充，所以执行所有任务所需要的某种保障要素不能超过该保障要素的总数。1UjujuXQ=。(2)1.2.3 现实条件约束 根据题设要求并结合实际可知，每个保障要素只能编入一个保障编组内或者不参与编组。Ri(u)=1。(3)上式表示第 i 个保障要素保障第 u 个保障任务，否则为0。1.3 优化指标的设计 在保障单元协同作用和保障效能上精确匹配下，整个作战任务高度衔接，密切配合，使得任务完成的时间最短。由于梯队内任务为并行序列，在并行任务中，任务是同时进行的，各个任务之间互不干扰，各自为战。各个任务完成时间的最大值即为该梯队完成的时间，即为需要优化的指标。可以将其表示为：mintbcj。(4)式中 tbcj表示梯队内任务为并行序列完成时间的最大值，即优化的原理为最小最大原则。梯队之间为串行序列，在串行序列中，一个梯 61刘 建等：基于遗传算法的作战任务分配和资源调度问题研究 第7期队完成以后再执行下一个梯队，各个梯队之间紧密衔接，梯队之间存在原料补给的时间间隔 tbj。各个梯队的任务完成时间之和就是需要优化的指标：1min(1)mbcbjjTztjmt=+-；(5)maxbctjt u=。(6)式中：tu为同一梯队内u个任务完成时间；j为某梯队；m为共有梯队数量。1.4 构建数学模型 由上述分析可知，保障单元编组模型的构建是一个资源调度和动态任务规划问题。在满足约束条件的前提下，优化编组和任务序列，使得优化的指标最小，即T最小，数学表达式为：1minmax(1)mbjjTzt umt=+-。(7)式中各符号含义与上文相同。约束条件为：1jujuUjujuXYXQ=|。(8)2 优化算法的设计 由于保障要素数量受限，保障任务较多，所以将任务确定为串并共行的打击方案，并根据要素需求划分梯队打击。笔者的算法设计主要思路为随机产生一个任务序列，按照任务序列的顺序从前至后求在同一梯队的任务，直至最后一个任务分配结束，并按照这个序列进行遗传算法的实数编码，而后优化求解。2.1 算法步骤 步骤1：确定梯队内首先执行的任务。在编码给定顺序的保障任务集中选定编号第一个为首先发射的任务Ti，并按需求要素表分配保障要素数量。成功分配后更新现有的保障要素剩余总数。步骤2：确定同梯队最多并行任务。每确定一个任务，现有的保障要素剩余总数都会得到更新，将更新后的保障要素数量表和任务要素需求表进行比对，按照编码确定的任务顺序寻找出可以并行的最多任务编号，进而计算该梯队的完成时间tbcj。梯队完成后，将所有的保障要素恢复初始值，表示原料补给完成。步骤3：确定发射梯队。将已完成分配的任务从未分配保障任务集中剔除，并重复以上步骤1和2，进行发射梯队的确定，直到未分配保障任务集为空集。步骤4：计算任务完成总时间。根据步骤2的方法计算各个梯队完成的时间，在梯队确定后，加上梯队之间原料补给的时间，即为任务完成的总时 间Tz。2.2 遗传算法寻优解算 在算法使用时需预先设定其遗传代数gen，交叉概率pc，变异概率pm，种群规模n，并将终止条件设定为达到遗传代数。笔者采取实数编码的方式对任务序列进行编码，编码的数字代表任务编号，编码的位置代表任务进行的顺序9。以8个任务为例，编码示意图如图2所示。31725864 图 2 编码 由2.1节的步骤4可计算得到总时间，即优化目标是要求总时间最短；因此，可将适应度函数值设定为BZfitnessVal=1/Tz，当总时间最短时，适应度取得最大值。选择操作通过锦标赛法进行实现，即随机选择种群中4个个体，比较4个个体并选择其中适应度值最大的作为父代，可以将优良基因遗传下