禁忌单亲遗传算法的某指挥控制舱协同任务规划*

李 康，高虹霓，王 崴，瞿 珏

（空军工程大学防空反导学院，西安 710051）

禁忌单亲遗传算法的某指挥控制舱协同任务规划*

李 康，高虹霓，王 崴，瞿 珏

（空军工程大学防空反导学院，西安 710051）

指挥控制舱是武器系统中指挥控制的功能核心，通过多人协同交互完成指控任务。为提高人员协同效率和操控效率。建立了以完成所有任务的时间最短为目标函数的多人协同任务规划模型。在求解模型时，采用禁忌单亲遗传混合优化算法，通过无性繁殖的方法，减少了在子代中产生无效染色体的情况，提升了算法的效率，通过禁忌算法有效避免陷入局部极小值。通过实例分析，算法使总任务执行时间减少了12豫。本模型以及求解算法在解决指挥控制舱多人协同任务规划时具有可行性，对指挥控制舱任务流程设计具有一定参考价值。

指挥控制舱，任务规划，单亲遗传算法，甘特图

0 引言

指挥控制舱作为地导装备指挥控制系统基本的装载单元，是武器系统中的核心装备，是战勤操作人员进行态势分析、目标识别、威胁判断、拦截排序、目标分配等人机交互的重要场所。信息化条件下的战争形态和战争特点，要求作战人员必须具备快速的反应能力，在这种情况下必然要求作战人员在短时间完成大量的任务处理［1］。以美军地空导弹武器系统为例，美国PAC-3导弹系统AN/MSQ-104ZZ控制舱中有3名操作员，要分别管理两个控制台和一个拥有3个无线电中继终端的通讯站，同时跟踪100个目标，同时攻击9个目标，而系统最短反应时间仅有15 s［2］。对于战时指挥控制这种高实时性、高强度的对抗方式，任务决策过程往往只有数十秒钟，几秒钟的延迟、微小的失误就可能导致任务的失败。一方面，可以通过加强训练来提高完成任务的效率，另一方面，对指挥控制舱的多人协同任务进行合理高效的规划，也是一个提高作战任务效率的有效途径。目前在军事应用领域，任务规划方法研究主要集中于武器目标分配［3-4］、无人机系统调度［5-6］等领域，缺乏以指挥控制舱为具体应用背景的协同任务规划方法的研究。图1为指挥控制舱场景图。

图1 指挥控制舱场景图

基于以上分析，本文结合具体作战流程规划，建立了以完成所有任务时间最短为目标函数的多人协同任务规划模型，针对指挥控制舱协同任务规划的特点，在模型求解中采用禁忌单亲遗传混合优化算法。通过模型的建立与求解，在一定程度上缩短了任务完成的时间，提升了作战效率。

1 模型建立

1.1 问题描述

指挥控制舱是多人进行协同交互完成作战任务的场所，一般配备有一名指挥员和多名操作号手等，而具体的指挥控制任务逻辑复杂，与传统的并行任务调度问题不同，指挥控制舱内每个任务只能被指定的号手完成。各号手之间的交互协作通过指挥员完成，指挥员观察各操作号手的任务执行情况，并及时通过口令向各号手发布任务执行命令，号手之间的任务存在复杂且严密的时序关系。如图2所示。

图2 指挥控制舱任务场景描述

①设需要完成的任务总数为N，Ri表示第i号任务，其中；

②指挥控制舱的操作号手数为X。Hj表示第j个号手，其中；对于每一个具体的任务都只能由一个号手完成。

③设每个任务开始的时间、完成需要的时间分别为 sti、ti。

④设任务Ri的紧前任务集合为preRi。

为了研究问题的方便性，现对模型作出如下假设：

①号手之间进行信息传递的时间即指挥员发布任务命令的时间算在任务执行时间内；

②每一个任务在对应操作号手上完成所需时间都是固定的。

1.2 协同任务数学模型

针对以上的指挥控制舱协同任务规划的所建立的数学模型如下：

①目标函数

对于指挥控制舱作战任务规划，以执行完所有任务的时间最小为规划目标，则其目标函数为：

上式右边表示对于任意任务的开始时间加上其完成时间的最大值即完成任务所需要的总时间。Yi是二维决策属性变量表示任务Ri被执行，其他情况为0。

②约束条件

ⓐ紧前任务约束

对于每一个任务，其被允许执行的条件为其紧前任务全部被完成。即

表示在第j个号手上执行Ri任务的开始时间，表示Ri任务的上一个任务Rl的任务开始时间，tl表示Rl的任务执行时间。

2 算法设计

根据指挥控制舱协同任务规划的特点，本文计划采用遗传算法框架解决指挥控制舱的任务分配和调度问题。

文献［7］首先将GA应用于并行任务的调度与分配中，为GA解决并行任务调度问题提供了理论基础。然而传统遗传算法存在问题描述困难、容易早熟的缺点。针对以上问题，本文结合指挥控制舱任务特点提出了一种禁忌搜索单亲混合遗传算法。

对于指挥控制舱协同任务规划问题，若采用传统遗传算法的交叉操作，则必然会产生子代染色体中某两个基因序号相同的情况，那么这个个体就会是无效的个体。基于以上原因，本文采用单亲遗传算法，单亲遗传算法是一类专门针对组合优化问题提出来的基于序列编码的遗传算法［8］，它采用无性繁殖的方式，取代了传统遗传算法的交叉算子，简化了遗传算法，提高了计算效率。而雷建平等也证明了单亲遗传算法在处理流水作文问题优化时具有收敛速度快、可信度高的优点［9］。

单亲遗传算法虽然解决了子代中无效染色体的情况，但由于父代只有一个，导致种群多样性降低，更容易出现“早熟收敛”的情况，陷入局部最优。

由于上述原因，本文采用禁忌搜索算法解决单亲遗传算法容易陷入局部最优的问题。TS是全局逐步寻优的算法，与传统的优化算法比较，它能够在搜索过程中以一定概率接受劣解，通过这种方式跳出局部最优解，增加获得全局最优解的概率［10］。禁忌算法对陷入局部最优的个体进行局部搜索，采用灵活的记忆能力，记录当前子代个体的适应度，选择适应度最大的个体保留，将搜索过的解存放于禁忌表中，在下一步的搜索过程中避开禁忌表中存在的个体，提高了搜索效率。然而，TS算法对初始解依赖度较高，好的初始解能得到比较优化的解，而差的初始解则会影响算法的收敛速度。关于结合GA与TS的优点，提高计算效率，前人提出了很多改进策略，Glover是禁忌算法的创始人，它从理论上论述了GA与TA结合的可行性与必要性。文献［11］以TS替代变异算子，利用TS接受劣解和记忆的特性，延缓GA早熟现象的发生，提高了算法的爬坡能力，然而变异算子概率设置过大，将会提高GA的随机性，一定程度上降低了TS算法的“爬山能力”，文献［12］对交叉和变异后的子代通过禁忌算子进行可行化处理，降低了无效染色体的概率，获得最优解，但每次迭代都调用了禁忌算子，算法效率不高。文献［13］采用固定TS算法调用频率的方法，也提升了“爬山”能力，但禁忌算法的调用完全依赖于迭代次数，容易导致GA还没收敛到一个较好的解就调用禁忌搜索，收敛过程波动幅度大。作为本文融合PGA以及TS算法的思想，给出了一种基于单亲遗传算法和禁忌搜索算法的混合优化算法（Tabu search Partheno Genetic Optimization Algorithm，TSPGA），先用PGA进行大范围全局搜索，待收敛进入局部最优时，个体的相对位置比较集中，再利用TS算法进行局部搜索，这种方法改善了PGA与TS的缺陷，也减少了TS算法的调用次数，增加了算法的效率。通过设置参数k判断算法是否陷入局部最优，若连续有k代最佳适应度值不变则认为算法陷入局部极小值。

2.1 基因及染色体编码设计

基于以上模型的构建，采用实数编码方式，此种方式相对于二进制编码方式更加直观且可操作性强。本文采用基于任务时序的染色体编码，这种编码方式简单且准确性高。每个数字即可代表相应的具体的任务编号，基因的前一个任务的开始时间小于等于后一个编码任务的开始时间。编码如表1所示。

表1 信息编码

2.2 适应度函数的构建

多人协同任务规划的目的是达到完成所有任务的时间最小。根据目标函数设计相应的适应度函数。

T（x）表示染色体x完成所有任务的总时间，T（x）越大表示染色体x的适应度值越低，被淘汰的概率也就越高。

2.3 算法的进化操作

遗传算法产生进化的下一代种群的核心是选择、交叉、变异操作。对于选择算子本文采用轮盘赌算法，根据其适应度函数来计算下一代的选择存留的概率，适应度越大的个体生存空间越大。

本文采用的单亲遗传算法，它只需要一个父代就能完成基因重组操作，基因重组又包括基因移位、基因换位和基因倒位等。而已有文献证明，这3种操作是等价的［9］。故仅采取基因换位来产生下一代种群。具体换位操作如图3所示，其换位位点与换位次数随机。

图3 换位操作

对于基因突变，由于任务只能在其对应号手上进行，且若只对单个基因进行变异，那么变异后产生的子代个体也必然会出现序号相同的情况，产生无效染色体，故基因变异只能成对出现，这与换位操作类似，另外，由于本文运用禁忌搜索算法解决了遗传算法陷入局部最优的问题，故算法可不设置变异算子。

2.4 算法步骤

指挥控制舱内协同任务规划的具体算法步骤如下：

步骤1：参数初始化，包括种群规模，换位概率，最大迭代次数max_GA，局部最优判别参数k。

步骤2：对种群进行选择、换位操作，产生新一代群体。

步骤3：计算种群所有个体适应度函数值，记录每代最优个体以及个体的最优适应度值。

步骤4：若连续k代最优适应度值不变，则调用禁忌搜索算法优化种群质量，更新最优值个体。否则转至步骤5。

步骤5：设迭代次数为t，若t＜max_GA，且经过禁忌搜索得到的最优适应度值大于之前的局部最优值或者没有调用禁忌搜素，则转步骤2。否则，输出当前最优值结果。

3 实例验证

取某型指挥控制舱操作教令中的开始的一部分作为本文的验证实例。该任务共配置有4个号手，共26个任务，按照上述模型的描述方法即，结果表示如表2所示。

表2 任务基本信息及模型

3.1 仿真结果及分析

基于上述实例，采用本文所描述的单亲遗传算法对模型进行了规划求解，连续运行10次，最优仿真结果如图4所示。

图4 TSPGA遗传进化过程

图5 PGA遗传进化过程

如图4所示，通过TSPGA算法，在160代左右时，遗传进化过程趋于稳定，在进化过程中多次调用禁忌搜索算法，通过记忆功能和藐视准则，跳出局部最优，得到了最优的任务规划路径，算法搜索效率较高且结果稳定。而相对于传统的单亲遗传算法，如图5所示，进化过程缓慢，迭代过程加长，算法灵活性不高，且通过表3可知，算法不稳定，与TSPGA算法对比，PGA运行结果很难得到最优的结果。

表3 10次优化结果对比

为了描述各任务单元在执行过程中的串并行时序关系，绘制任务甘特图如下页图6、图7所示。

从图6可以看出，原始任务采用基于逻辑时序的任务规划方法，其任务衔接紧凑，就现有的任务规划方案来看，时间利用合理，然而，号手存在的空闲时间较多，完成任务总共耗费的时间为63 s。优化后的结果如图7所示，总共耗时57 s，比原有方案少了6 s，而前面13 s属于任务开始阶段，不具备优化条件，故现有方案比原有方案在总时间上优化了12豫，且从图中可以看出，号手的空闲时间明显减少，增加了协同交互的效率。证明了模型以及求解算法的可行性。

图6 原始任务时序甘特图

图7 优化后任务时序甘特图

4 结论

本文针对指挥控制舱协同任务规划问题主要做了以下工作。

①对指挥控制舱多人协同任务作出了数学描述，并且以完成所有任务的时间最短为目标函数，建立了满足任务流程约束的指挥控制舱多人协同任务规划模型。

②针对上述建立的模型，采用禁忌搜索单亲遗传混合优化算法，设计了其信息编码，适应度函数以及算法流程，对上述模型进行了求解。

③通过某型指挥控制舱操作开始部分阶段的教令实例验证。结果表明上述模型以及求解算法可以很好地处理指挥控制舱多人协同任务规划问题，并取得了良好的结果。为指挥控制舱设计作战任务流程提高了良好的思路。

另外，本文仅针对如何缩短总任务执行时间作出了系统规划，下一步工作可针对既能够快速地完成任务，又能够精简操作号手的任务规划作进一步研究，进而能够通过任务流程的规划，总结出指挥控制舱人机功能分配的原则。

［1］颜声远.武器装备人机工程［M］.哈尔滨：哈尔滨工业大学出版社，2009.

［2］张巍，王敏，徐世录.美国导弹防御系统的发展动向分析［J］.现代防御技术，2007，35（3）：25-31.

［3］蔡怀平，陈英武.武器-目标分配（WTA）问题研究进展［J］.火力与指挥控制，2009，34（12）：11-15.

［4］王步云，姜伟，徐建志.基于多Agent的编队导弹攻击火力分配的优化研究［J］.指挥控制与仿真，2008，30（2）：45-47.

［5］王国强，罗贺，胡笑旋.无人机编队协同任务规划仿真系统研究［J］.系统仿真学报，2014，26（8）：1856-1861.

［6］朱毅，张涛，程农，等.多UAV协同任务规划研究［J］.系统仿真学报，2009，21（S2）：194-199.

［7］HOU E，ANSARI N，REN H.A geneteic algorithm for multiprocessor scheduling［J］.IEEE Trans.on Parallel and Distribution Systems，1994，5（2）：113-120.

［8］陈慧琴，刘刚.用整数编码的单亲遗传算法求解组合优化问题［J］.武汉理工大学学报，2003，27（4）：241-243.

［9］雷建平，袁刚，袁细发.单亲遗传算法与流水作业优化［J］.武汉理工大学学报，2004，28（8）：593-596.

［10］姚英彪，王璇.面向多核任务调度的混合遗传算法［J］.系统工程与电子技术，2015，37（8）：1928-1935.

［11］朱文真，唐敦兵，王雷.基于遗传禁忌搜索算法的自动化立体仓库出入库路径优化研究［J］.机械科学与技术，2011，30（7）：1202-1205.

［12］周创明，华继学，李成海.具有禁忌算子的遗传算法目标优化分配 ［J］.空军工程大学学报，2005，6（2）：87-71.

［13］廖良才，张琦.基于混合遗传算法和关键链的多资源多项目进度计划优化［J］.科学技术与工程，2014，6（2）：190-194.

［14］唐贇.单亲遗传算法在车间布局中的应用研究［D］.上海：上海交通大学，2014.

Coordinated Task Planning in Command and Control Square Based on PGA

LI Kang，GAO Hong-ni，WANG Wei，QU Jue
（School of Air and Missile Defense，Air Force Engineering University，Xi’an 710051，China）

Command and control square is the function core of weapon system，tasks in here are executed by collaboration.In order to improve the efficiency of collaboration and control，a planning model for cooperative mission is established，taking the minimal time of all tasks as the objective function.Tabu search partheno genetic algorithm （TSPGA）is adopted to solve this planning model，invalid chromosome is reduced by vegetative propagation and local minimum is avoided by tabu search，algorithm efficiency is improved.Finally，example simulation analysis shows that the task completion time reduce by 12%，proving the feasibility of planning model and algorithm，present a new idea for the design of task flow in command and control square.

command and control square，task schedule，PGA，gantt chart

E83

A

10.3969/j.issn.1002-0640.2017.08.026

1002-0640（2017）08-0115-05

2016-06-12

2016-07-14

国家自然科学基金（51405505）；航空科学基金资助项目（201455960）

李 康（1994- ），男，湖北咸宁人，硕士研究生。研究方向：人机工程。