基于多目标优化的任务计划建模及方法*

孙鹏，李锴，孙昱，王勋，胡诗骏

（空军工程大学信息与导航学院，西安710077）

基于多目标优化的任务计划建模及方法*

孙鹏，李锴，孙昱，王勋，胡诗骏

（空军工程大学信息与导航学院，西安710077）

针对任务计划在进行多目标优化时采用进化算法求解效率较低的问题，设计了一种结合分组策略的非支配排序遗传（NSGA-Ⅱ）算法，可以快速有效地得到合理的分组结果。基于分组结果，调整NSGA-Ⅱ算法的步骤，灵活地进行种群初始化，使最终分配结果各优化的目标有了明显的改善，提高了算法的效率。通过实验分析，验证了所提方法的可行性和有效性。

任务计划，分组策略，NSGA-Ⅱ，多目标优化

0　引言

任务计划问题是指挥控制领域的一个关键问题。该问题通过任务-平台的合理匹配，确定由作战使命分解所得各任务的开始时间和执行资源，实现任务计划各目标优化。合理的任务计划可以有效实现作战预期，完成作战使命。近年来国内外学者对该问题的建模和解决方法进行了广泛地研究。

文献［1］中将任务计划问题作为指挥控制组织（C2组织）设计的第一个阶段，提出了多维动态列表调度算法。文献［2］采用任务选择平台组、平台选择任务以及两者选择冲突消除改进的方法，提出了多优先级列表动态规划算法。文献［3］将分组技术（GT）引入到任务计划问题，降低了问题复杂度。文献［4］研究了不确定性下任务计划问题，主要考虑了使命成功的不确定性、平台能力损耗的不确定性以及任务执行时间的不确定性。文献［5］针对“任务-平台”关系设计问题提出了一种在使命完成时间限制条件下的问题设计模型和求解算法。文献［6］建立了含时间窗任务计划问题数学模型，通过扩展的多维动态列表规划算法进行求解。文献［7］针对任务计划问题中多目标特点，把NSGA-Ⅱ算法用于求解任务计划问题。

采用进化算法对任务计划问题进行多目标优化，往往存在搜索空间过大、进化效率低的情况，且随着问题规模的增大和优化目标数的增多，这个缺陷更加明显。本文以NSGA-Ⅱ算法为基础，设计了一种合理的分组策略，以减小搜索空间，提高算法效率。

1　模型建立

合理解决任务计划问题，首先要对该问题进行建模。一个好的模型可以提高求解质量，为指挥员提供更加详细的作战方案，更加符合实际的作战环境。

1.1问题要素

在任务计划问题中主要包括两个要素：任务和平台，下面对这两个要素进行定义。

定义1任务是由作战使命分解得到子行动。所有任务组成任务集Ts=（T1，T2，…，TN），其中N为任务的数目。任务Ti的属性包括：

（1）任务的开始时间si；

（2）任务的处理时间ti；

（3）任务的资源需求矢量TRi=（tri1，tri2，…，triL），其中L是资源类型的数目；

（4）任务所在的地理位置（xi，yi）；

（5）任务对抗激烈程度TDi∈｛0，1，2，3，4，5，6，7，8，9｝。

定义2平台是实际作战中提供资源能力以执行任务的物理载体。对于每个平台Pm（m=1，2，…，K），K为平台的数量。它的主要属性包括：

（1）平台移动的最大速度vm；

（2）平台的初始资源能力矢量PRm=（prm1，prm2，…，prmL），prmL（l=1，2，…，L）表示从平台Pm中可以得到的第l种类型的资源的数量；

（3）平台所在的地理位置（Xm，Ym）；

（4）平台的基本损耗率PFj：表示当平台Pj执行任务Ti，对抗激烈程度TDi=1时平台的损耗速率［4］。

1.2问题变量

（1）分配变量ωim：

（2）转移变量xijm：

当i=j时，转移变量为0，即xijm=xjim=0（i，j=1，2，…，N；m=1，2，…，K）。设作战使命起始和终止任务为虚拟任务T0，令x00m=0（m=1，2，…，K）。

（3）顺序变量aij：

（4）使命完成时间T：

（5）平台移动总距离Ssum：

其中sim为平台Pm执行任务Ti时移动的距离。

（6）使命完成概率P：

其中p（i）为任务Ti完成概率。

（7）损耗速率kiml表示平台Pm执行任务Ti时，其拥有的能力l的损耗速率：

则实际平台损耗为

1.3问题约束条件

考虑平台分配约束、任务开始时间约束等情况：

（1）平台约束分配

当ωim=1时，平台Pm在分配给Ti之前肯定执行过某一任务（包括起始任务T0），也将被分配执行下一任务（包括终止任务T0），因此

所有平台在起始任务开始执行使命，在终止任务完成使命，即：

（2）任务开始时间约束

当aij=0，任务的开始时间需满足式（12）：

考虑到任务Ti，Tj之间的执行关系，将式（11）转化为（12），得

其中，dij为Ti，Tj之间距离，即：

当aij=1时，任务开始时间需满足

式（15）中，T'是所有任务完成时间的上界，满足T'≥T。综合式（13）和式（15），得到任务开始时间约束

1.4问题模型

任务计划的目的就是在最短的时间内最大概率地完成作战使命；同时根据自动目标识别领域的经验，移动目标被发现概率比静止目标高出90%以上［7］。因此，目标函数分别是：极小化使命完成时间；极小化平台移动总距离；极大化使命完成概率（即极小化使命失败概率），所建立问题模型如下：

2　基于分组策略和NSGA-Ⅱ的求解算法

NSGA-Ⅱ算法是多目标优化领域一个经典算法，本文以该算法为基础对任务计划多目标优化问题进行求解；同时设计了一种分组策略以解决NSGA-Ⅱ在多目标优化过程中进化效率低的缺陷。本文所采用案例的任务序列图GT、各任务、平台的属性均已给出（来源于文献［1］），其中GT代表了任务间的时序关系和逻辑关系。

2.1分组策略

GT是根据目标的特点将目标归于类型、性质相似的不同胞元的一种技术，常用的分组方法包括：矩阵分组；层次分组；图论分组；人工智能分组；进化分组以及数学规划方法［3］。在上节中所建立的问题模型是一种联合优化问题，属于NP-难问题。采用GT可以针对此类大规模复杂问题提供较为成熟的初步方案，降低问题的规模，提高整体算法的效率。

文献［3］首次引入GT用于解决任务计划问题，但是它采用嵌套遗传算法随机产生分组方案，并针对每个随机产生的分组方案随机产生最终分配方案，这样导致了问题求解效率缓慢。文献［8］定义了平台装备的层次关系，提出了平台装备的树形结构，为平台分类提供了参考。文献［9］所采用的粒度计算方法也是一种类似分组的思想，目的是降低问题的规模。

本文设计了一种新的分组算法，通过一次从头到尾的求解可以得到一个合理的分组方案，提高了后续NSGA-Ⅱ的算法效率。

分组结果的好坏有以下几个衡量标准：

（1）所分各组内平台和任务的资源属性应尽量匹配。因为每个平台都有自己擅长执行的任务，首先要做到物尽其用，减少资源浪费。

（2）分组结果要尽可能减少平台之间的协同，一个平台可独立完成的任务不要交由多个平台执行，一方面可以减少平台间的交流负载，另外一方面可以降低总体平台移动距离。

（3）分组结果应能使整个任务计划方案执行的并行程度较高，以达到使命完成时间较短的目的。

下面是本文所设计的分组算法步骤：

步骤1对任务进行分组：

每个任务都有自己的资源需求矢量，将资源需求矢量相同或者相近的任务归为一类，且注意到分组方案随任务数的增加而呈指数快速增长，会出现“组合爆炸”，因此，必须控制分组的数目。具体方法是：计算每个任务的资源需求总量：

定义3假设现有两个任务a和b，它们的资源需求向量分别是TRa和TRb，若∀j=1，2，…，L，有traj≥trbj，则称任务a包含任务b，记作a⊇b；特别地，若∀j=1，2，…，L，有traj=trbj，称任务a等价于任务b，记作a=b。

从资源需求总量最多的任务开始，检验其是否有等价任务，若没有则将该任务归为“特殊任务”组；否则计算该任务所包含的所有任务，若此任务包含的任务数目超过N/2，则将该任务归为“特殊任务”组；否则将该任务以及它所包含的所有任务归为一组，并将该任务定义为该组的“基本任务”，基本任务的资源需求矢量为该组的最大资源需求矢量。上述过程执行完毕，所剩余的单个任务为特殊任务。

步骤2对平台进行分类

相应地，每个平台拥有自己的资源能力矢量PRm，首先找到PRm相等的平台并将其归为一类，例如：战斗机1，战斗机2，战斗机3。其次，若两个平台能力类型相同但能力大小不同，将其归为一类，例如：工程兵分队和扫雷舰的主要能力在扫雷上，而在其他方面的能力近似为零。分类完毕后剩余的具有特殊功能的单个平台为特殊平台。

步骤3对各任务组分配平台

观察各个分组的最大资源需求矢量TRi（i=A，B，C…），对于它们每个不为零的分量，肯定有至少一个平台分配方案，以满足该能力分量的需求。找出可选方案数最少（即选择余地最小）的分量，开始对其进行平台分配。在这些方案中，有的是分配单个平台，有的则是分配若干个平台。挑选其中涉及平台数尽量少的方案，这样可以有效减少各平台的协作数，降低总平台移动距离。计算这些方案中平台对该组的资源满足度：

其中，l为当前分量，i为当前分量所属组别，分子表示平台Pm对组i提供的资源数，分母表示平台Pm对除组i外的其他组提供的资源数。取方案中各平台满足度的均值作为该方案的满足度，选择满足度最高的方案。

若两个方案的满足度相同，计算其资源冗余度：

同样取方案中各平台冗余度均值作为方案的冗余度，选择冗余度小的方案。

每次对某分量进行平台分配后，在其余分量的可选平台中剔除掉这些平台，同时计算该组在这次分配后的剩余资源需求矢量。持续这个过程，直到每个分组的最大资源需求矢量TRi被完全满足，将剩余的平台归为“预备平台”组。若某平台同时被多个组需求，无其他可替代方案，则将该平台同时归入这多个组。

2.2NSGA-Ⅱ

任务计划问题关注多个设计指标［7］。处理多目标的常见方法是把各目标加权形成单个目标，这种策略需要事先确定各目标的权重关系［10-11］，除非各目标相互独立，否则不能保证算法收敛到最优解。采用NSGA-Ⅱ这个经典多目标优化算法，可以直接处理多个优化目标，保证算法的最优性。但是利用NSGA-Ⅱ算法针对两个以上目标进行优化时，由于搜索空间较大，会出现进化效率缓慢的情况，随着问题规模增大，优化的目标数目增多，这个缺陷越来越明显。

本文利用上节所给出的分组结果，随机生成初始种群。种群个体即任务-平台分配方案，对所有个体进行非支配排序，每个个体的非支配排序等级作为其适应值，通过进化可得到的一组最优解以及它们的非支配排序等级。基于分组策略的NSGA-Ⅱ算法作以下几点调整，其余设置见文献［12］：

（1）染色体表示：采用布尔型编码的方式，每一个染色体由一个N×K的0/1矩阵来表示，0/1表示是/否使用平台执行任务。

（2）种群初始化：基于多维动态列表调度（MDLS）算法的思想，由任务序列图GT得到当前可执行任务集READY，将空闲平台归入FREE集。对READY集中的任务随机分配组内平台；若无组内平台可分，则随机分配预备平台组中跟组内平台同类的平台；若无同类平台可分，则随机分配预备平台组中与组内平台不同类的平台；若无不同类平台可分，则随机分配其他组的平台，直到FREE集为空。执行已分配的任务，更新READY集和FREE集，直到所有任务完成，得到一个完整的任务-平台分配方案。通过这样的方式，可以最大限度使用平台同时执行多个任务，增加任务的并行程度，缩短使命完成时间。

（3）强制变异操作

每代进化后，若存在两个个体完全相同的情况，则对其中某个个体进行变异操作，随机对某个基因执行变异，这样可以避免出现大量重复个体的情况。

3　实验验证

按照分组算法步骤1对案例的任务进行分组得到任务分组结果见下页表1：

表1　任务分组

观察任务分组情况：组A为补给、策应任务；组B为地面进攻和防御任务；组C为行进任务；组D为夺取目标任务，分组结果是较合理的。

按照步骤2对案例的平台进行分类得到平台分类结果见表2：

表2　平台分类

观察平台分类情况：除了b类外，其余各类中的平台资源能力完全相同。因此，表3所示分组结果中各平台可以被同类的其他平台替换（除b类外）。

按照步骤3对案例的任务组分配平台，结果见表3：

表3　一个分组结果

NSGA-Ⅱ算法种群规模为50个个体，进化200代后停止，任务对抗激烈程度矢量TDi=（6，6，1，1，3，7，7，7，2，2，4，4，4，4，8，8，3，5）［4］。由分组结果运行NSGA-Ⅱ算法得到的第200代种群50个个体，在各子目标分量上的值如图1所示，图1中Pareto最优解曲面由部分非支配解拟合而成。

从图1中可以看出，50个个体大多靠近最优解曲面且分布均匀，可知本文所采用算法具有较好的有效性和稳定性。取最优解曲面上的两个个体D1，D2，观察他们的甘特图，分别如图2，图3所示。

图1　第200代种群的50个个体及Pareto最优解曲面

图2　个体D1甘特图

图3　个体D2甘特图

从图2，图3中可以看出方案D1所使用平台次数较多，因此，平台移动距离较大，为908，相应的使命完成概率也较高，为0944 8；方案D2则恰好相反，平台移动总距离为819.9，使命完成概率为0.931 3；而在使命完成时间上，两者大致相当，其值为139左右。

下页图4是由文献［3］通过嵌套遗传算法得出的一个的任务-平台分配方案的甘特图。通过计算可得，该方案的使命完成概率过低，仅有0.717 5；使命完成时间也较长，为175.64。出现这种情况的原因是：文献［3］本着最小化组间协同的原则，找到一个“最优分组结果”，并严格按照分组结果进行最后分配，导致产生不合理的解空间的限制；而且嵌套遗传算法效率过低。事实证明，拘泥于分组的限制产生的分配方案不是最优的，达不到任务-资源匹配的目的［13］。

图4　文献［3］任务-平台分配方案甘特图

50个个体的各目标分量平均值与其最大值之比随进化代数的变化曲线如图5所示。

图5　子目标分量平均值统计

由图5可知，NSGA-Ⅱ进化至180代左右时，已经可以得到多个最优解，继续进化改进效果已不明显。文献［7］中采用NSGA-Ⅱ算法对两个目标进行优化，经过1 200代得到均匀分布的收敛结果。由此可见，相比单纯NSGA-Ⅱ算法，引入分组策略后，收敛速度更快，算法效率明显提高。

4　结论

本文采用基于分组策略的NSGA-Ⅱ算法对任务计划多目标优化问题进行求解，设计了一种快速产生合理分组的分组算法。通过实验验证，可得主要结论包括：①本文所设计的分组算法相较于利用遗传算法进行分组，通过一次从头到尾的计算，使求解更加迅速；而且同样可以达到降低问题规模，提高后续算法的效率的目的。②任务计划中各任务和平台属性都有不同程度的差别，完全按照分组结果进行分配以得到最优解是不现实的。本文不囿于分组结果，只是将分组步骤作为提高算法效率的手段，结合MDLS算法的思想灵活地进行种群初始化，使最终得到的任务-平台分配方案在各优化目标上有较明显的改善。③执行任务的过程中减少平台间的协同，可以有效降低平台移动距离，减小平台被发现和摧毁的概率。

［1］LEVCHUK G M，LEVCHUK Y N，LUO J，et al.Normative design oforganizations—part I：mission planning［J］.IEEE Transactions on Systems，Man，and Cybernetics，2002，32（3）：346-359.

［2］阳东升，彭小宏，张维明，等.C2组织结构设计：平台-任务关系设计［J］.火力与指挥控制，2006，31（3）：9-13.

［3］YU F，TU F，PATTIPATIKR.Novelcongruentorganizational designmethodology using group technology and a nested genetic algorithm［J］.IEEE Transactions on Systems，Man，and Cybernetics，2006，36（1）：5-18.

［4］牟亮，张维明，陈涛，等.不确定条件下C2组织结构的“任务-平台”关系设计模型及算法［J］.系统工程与电子技术，2010，32（12）：2576-2583.

［5］张杰勇，姚佩阳，李凡.使命完成时间限制下的任务-平台关系设计模型及算法［J］.系统工程与电子技术，2012，34（8）：1621-1629.

［6］陈行军，齐欢，阳东升.含时间窗联合作战计划问题的建模与求解［J］.系统工程理论与实践，2012，32（9）：1979-1985.

［7］乔士东，黄金才，修保新，等.基于NSGA-Ⅱ多目标优化的C2组织设计［J］.国防科技大学学报，2009，31（5）：64-69.

［8］阳东升，刘宏芳.C2组织测试的想定描述：平台装备及其状态定义［J］.计算机与数字工程，2010，38（2）：31-34.

［9］修保新，张维明，刘忠，等.C2组织适应性设计方法［J］.系统工程与电子技术，2007，29（7）：1102-1108.

［10］XIU B X.A novel organizational designmethodology based on the theory of information granulation［C］//Proceedingsof the Fourth International Conference on Machine Learning and Cybernetics，Guangzhou，2005.

［11］SRINIVASN，DEB K.Multiobjective function optimization using nondominated sorting genetic algorithms［J］.Evol. Comput.，1995，2（3）：221-248.

［12］DEB K，PRATAPA，AGARWAL S，et al.A fast and elitist multiobjectivegenetic algorithm：NSGA-Ⅱ［J］.IEEETransactionson Evolutionary Computation，2002，6（2）：182-197.

［13］NADLERD A，TUSHMANM L.Competing by Design［M］. New York：oxford，1997.

M odeland M ethod ofM ission Planning Based on M ulti-objectiveOptim ization

SUN Peng，LIKai，SUN Yu，WANGXun，HU Shi-jun
（School of Information and Navigation，Air Force Engineering University，Xi’an 710077，China）

In this paper，a nondominated sorting genetic algorithm（NSGA-Ⅱ）combined with Group Technology（GT）is designed in order to solve with the problem of low efficiency of using evolutionary algorithm for Mission planning in the Multi-objective Optimization（MO），and a reasonable grouping results can be gotten quickly and efficiently.The steps of the nondominated sorting genetic algorithm and flexibly initialized to the population based on the group result are adjusted.The optimization goals of the final result of the distribution improve significantly，and the efficiency of algorithm is greatly increased.The feasibility and effectiveness of the proposed method was verified through experimental analysis.

mission planning，group technology（GT），nondominated sortinggenetic algorithm（NSGA-Ⅱ），multi-objectiveoptimization（MO）

TP391.9

A

1002-0640（2016）09-0018-06

2015-07-20

2015-08-05

中国博士后基金资助项目（2014M 562585）

孙鹏（1972-），男，副教授。研究方向：指挥决策与通信指挥。