彭 攀，白沐炎，陈长春，陈晓宇

（1.上海卫星工程研究所，上海 201109；2.上海航天技术研究院，上海 201109；3.中国地质大学 计算机学院，湖北 武汉 430074）

0 引言

成像侦察卫星调度问题是一类混合时间和资源分配的复杂调度问题，且已被证明是一类非确定多项式竞争（Non-deterministic Polynomial Complete，NPC）问题［1］，涉及了多学科交叉知识，是我国空天地一体化体系设计的基础。作为空间信息网络构建和卫星应用控制领域的关键支撑技术，成像侦察卫星调度问题已成为实际应用中的一个重要研究内容，受到学术界和工程界的高度重视［2］。

很多学者最初研究了单星调度规划问题，设计了高效的求解模型和算法。Jang等［3］通过对任务可见时间窗口离散化，并在此基础上构建了0/1 线性规划模型。Wu等［4］提出了一种基于任务动态划分的自适应模拟退火算法，并引入禁忌表求解了单星多轨道对地观测调度规划问题。潘耀等［5］通过对遥感卫星成像任务规划中的点目标进行聚类，构建了任务聚类图模型，设计了一种改进的单轨最优团划分聚类方法。这一系列的工作在单星调度规划最优可行解生成和问题界限描述上均取得了显著的进展。

随着航天任务的复杂化和要求的提高，在轨运行卫星数量和类型逐渐增多，用户需求不断增加，且表现出复杂多样的特性，由多颗星组成的卫星网络系统在通信、导航和遥感等领域都得到了重要的应用。与单星调度规划问题相比，调度复杂任务约束下多颗协同运作的卫星需要考虑观测资源选择和执行时间窗口选择，以及更多的执行操作约束［6］。考虑到传统任务规划算法不能适应多卫星资源的应用特点，有学者将多星联合调度规划问题划分为任务到资源分配的主问题和多个单星调度规划的子问题［7-8］。贺仁杰等［9］深入分析了成像卫星任务规划技术，将其看作是带时间窗口约束的并行机调度问题，并采用禁忌搜索算法求解了较大规模的任务协同规划问题。刘伟［10］提出了混合整数规划模型和约束满足模型相结合的调度规划模型，研究了这两种模型下的Lagrangian 松弛确定性优化方法和模拟退火算法随机性优化方法。Salman等［11］提出了混合差分进化的元启发式随机扩散搜索算法，研究了多卫星联合广播任务调度问题。Xu等［12］提出了基于任务优先级指标的蚁群算法，研究了最大化收益值的多敏捷卫星对地观测调度规划问题。Zhang等［13］构建了一个独立的复杂冲突结构图模型，以最小化任务执行时延为目标，提出了蚁群优化多星联合调度问题。Zheng等［14］提出一种改进的混合动态变异算子的遗传算法求解多星联合对地观测调度规划问题，显著提升了算法的性能。严珍珍等［15］提出一种加入精英策略的改进蚁群算法的多敏捷卫星成像调度方法。陈晓宇等［16］提出了基于任务优先级和冲突消解的改进差分进化算法。Song等［17］采用带局部搜索的改进遗传算法，求解了多星调度规划问题，提高了算法搜索效率。

在上述研究背景下，本文主要针对智能优化算法求解多星联合调度规划问题中存在的算法性能随问题规模增大而大大降低的问题，旨在提出一种改进差分进化算法。首先建立了多星联合调度规划约束满足最优化模型，并在标准差分进化算法的基础上，通过分析成像卫星的成像过程和工作原理，将成像卫星调度过程分为调度预处理、任务规划和调度优化3 个阶段。其中，调度预处理操作是根据用户需求来筛选卫星系统资源，确定每个观测任务的可选资源以及可分配的时间窗口；在任务规划过程中，采用基于启发式思想的差分进化算法对成像卫星调度问题进行求解，重新定义了个体适应度评估函数，设计了任务冲突消解方法；优化过程是根据系统性能评估结果，主要对调度规划结果中由于资源冲突而未完成的任务和因时间限制有时延的任务进行进一步的优化。

1 问题描述

多成像侦察卫星调度问题可以描述为在m个互不相同的遥感设备（资源集合R）安排n个观测任务（活动集合M）。对每个活动Mi∈M，只有资源子集R(Mi)∈R可以满足其执行要求，该活动完成需要占用资源Rj∈R，占用时间为[Begi，Endi]。此外，活动Mi在占用资源Rj时具有一组互不相交的时间窗口集约束，且只能在其中的一个时间窗口内不中断地执行完成。如果活动Mi和活动Mi'在执行过程中占用同一个资源Rj，且活动Mi在活动Mi'之前执行，那么活动Mi执行完成后，必须经过一个转换时间活 动Mi'才能开始执行。由于资源 能力及时间的限制，活动可能不被安排。因此，每个活动Mi都有权值wi，代表该活动安排时的效益值。

一个最优调度方案应满足以下条件：1）每个活动只能在自己的时间窗口内执行，否则，认为该活动未安排；2）每个活动只能占用满足其要求的资源集合中的一个资源，且执行过程不能中断；3）每个资源在任何时候只能同时满足一个活动的需求；4）安排活动的总权值最大。

2 约束满足最优化模型

2.1 符号定义

2.1.1 集合

M：活动集合。M={M1，M2，…，Mn}，其中第i个任务用Mi表示。

R：资源集合。R={R1，R2，…，Rm}，其中第j个资源用Rj表示。

M(Rj)：所有可以被安排在资源Rj上被执行的活动集合。Rj∈R，M(Rj)∈M。

R(Mi)：满足观测活动Mi要求的资源集合。Mi∈M，R(Mi)∈R。

TWij：活动Mi占用资源Rj是所允许的时间窗口集合。Nij表示活动Mi占用资源Rj时所允许的可见时间窗口数目。其中，代表在活动Mi占用资源Rj时所允许的第k个时间窗口开始时间，代表活动Mi占用资源Rj时 所允许的第k个时间窗口结束时间。

RTWj：资源Rj的有效执行区间段集合，表示资源在哪些时间段内可用。

2.1.2 参数

RPj：表示资源的图像类型。RPj=1 表示可见光成像，RPj=2 表示红外线成像，RPj=3 表示多光谱成像，RPj=4 表示雷达成像。

Δj：表示资源Rj成像前的稳定时长。

Aj：表示资源Rj在整个仿真周期内的最大执行时长。

wi：活动Mi的权值。Mi∈M，wi＞0。

Di：活动Mi完成所需要的持续时间。Mi∈M，TDi＞0。

TPi：活动Mi成像所要求的图像类型。TPi=0表示成像类型无要求，TPi=1 表示可见光成像，TPi=2 表示红外线成像，TPi=3 表示多光谱成像，TPi=4 表示雷达成像。

SCBeg：场景开始时间。

SCEnd：场景结束时间。

Begi：活动Mi的开始执行时间约束。其中，Mi∈M，Begi≥SCBeg。

Endi：活动Mi的执行结束时间约束。其中，Mi∈M，Endi≤SCEnd。

2.2 复杂操作约束形式化描述

2.2.1 优化变量

dsti：表示活动Mi被安排时的开始执行时间。

2.2.2 优化目标

最大化任务执行总效益

2.2.3 约束条件

1）每个任务Mi最多只被执行一次，且只能在一个时间窗口内执行，或即使被执行多次也只计算一次的收益，即

2）资源最大使用时长。该约束用于表示在一个轨道周期或给定时长内的总侧摆次数和开机工作时长不能超过其允许的上限范围，即

3）任务执行时间约束。每个任务都需要被分配在其所属规划时间区间内，该条件多用于表示周期性覆盖或者受光照等约束的应急任务或通信任务中。即，如果

4）为每个任务分配的观测窗口需要满足成像资源的可用性约束和任务的观测时长约束。在调度过程中，如果为任务Mi分配了资源Rj以及相应的可见时间窗口，则该任务的观测时间段必须完全落在分配的可见时间窗口内。该约束表示如下：

对于任意的Mi∈M，以及任意的Rj∈R(Mi)，k∈{1，2，…，Ni，j}，如果，则

5）同一资源上的连续两个观测任务间的最小转换时长约束。上述分析可知，卫星在执行任务的过程中，星载传感器的侧摆角和旋转角随着不同开始执行时间变化，因此，安排在同一资源上相邻的两个任务，需要考虑任务间的最小转换时长，从而使得卫星或者星载传感器调整到正确的姿态。同时考虑到两个任务的不同执行先后顺序，该约束表示如下：

对于任意的Rj∈R和分配在该资源上的任意两个连续 观测任务序列Mi，Mi'∈M(Rj)，如 果且同时成 立，则

6）成像资源类型选择约束。当任务Mi选定资源Rj以及相应的可见时间窗口时，必须满足当前情况下资源Rj是可用的，并且资源Rj对应的载荷图像类型能够满足活动要求的成像类型要求。即，如果，则

7）优化变量取值约束。对于任意的Mi∈M、资源Rj∈R(Mi)，以及所有的k∈{1，2，…，Ni，j}，有如下约束：

3 改进差分进化算法

针对成像卫星调度这一NP 完全问题的求解，为提高问题的求解效率，首先可以对该问题进行分类，然后再采用相应的算法进行求解。考虑在通常情况下，当问题求解规模较大时，该问题往往很难得到一组可行解，此时，只能通过一些典型的智能算法进行求解。而差分进化（Differential Evolu⁃tion，DE）算法是一种用于最优化问题的后设启发式算法，是一种基于实数编码的具有保优思想的贪婪遗传算法。在相关已有工作中，大量研究表明DE 是一种性能非常好的求解实数编码优化问题的启发式方法。为了提高调度方案解的优越性及算法的运行效率，本文是在标准DE 基础上，加入调度预处理操作和一些启发式思想对成像卫星调度问题进行求解。同样，当采用近似算法对问题进行求解后，往往还存在很多未完成的任务，这时可通过再次运用确定性算法，为未完成的任务在剩余的时间窗口内尝试重新选取时间窗口，从而进一步达到问题最优解的定义。

在演化的过程中，算法中涉及的几项重要操作（调度预处理、冲突消除、效益值计算、可行解二次优化）如下。

3.1 调度预处理

首先，对卫星系统资源及用户需求进行分析，优先处理多星联合对地覆盖过程中只与其静态覆盖性能相关的约束，计算所有满足星地观测需求的可见时间窗口集合。只有当观测需求同时具有可用资源和可用时间时，才认为该观测需求可能被完成，需要通过进一步调度来确定其是否被执行、执行该观测需求的卫星和为其分配的成像时间段。其次，当任务至少存在一个可见时间窗口且在调度过程中可能被执行时，分析该任务的可见时间窗口区间上的资源争用冲突度，考虑优先安排含有空闲资源的任务，旨在降低问题的搜索空间，提高算法求解效率。

针对某一假定调度规划场景，经过调度预处理操作，可生成卫星与目标之间的可见时间窗口约束集，如图1 所示。

种群中个体上每个基因位编码为一个任务的执行状态（包括任务属性、是否被安排执行、被安排的观测资源和观测时间窗口），种群中的每个个体对应一个调度可行解。个体的初始化主要分为两个方面：1）采用基于任务执行时间优先或基于任务执行收益优先的贪心算法得到的可行解，对个体中的部分任务进行编码，调度方案中未能完成的剩余任务则在其可见时间窗口集中随机选择进行编码；2）首先对拥有空闲时间区间的任务进行编码，其次为剩余的任务在其所有可见时间窗口中随机选择进行编码。

图1 调度预处理Fig.1 Scheduling preprocessing

3.2 冲突消除

当个体中的多个任务争用资源产生资源冲突情况时，如何消除资源冲突，通常情况下是采用其中一个个体的冲突基因位重新随机选择时间窗口，而对于这类资源冲突较大的情况，重新选择的时间窗口往往会引起与其他任务更多的资源冲突情况，因此，对于发生资源冲突的基因位选择新的资源和执行时间窗口也是至关重要的。运用启发式的思想，当为个体中两个成像任务分配的资源和执行时间不满足约束条件，则需要消除一个任务，为其重新分配资源和执行时间。为了使得该优化序列的效益值最大，可通过以下方式选择消除的基因位：1）冲突基因位的冲突效益值；2）冲突基因位的可见时间窗口长度和时间窗口的冲突度。

在 同一资源上 执行的任 务M1、Mi、Mj、Mk，有任务Mi、Mj、Mk执行时间 窗口相互冲突，如 图1 所示。其中，任务Mi和Mk的冲突度均为1，而任务Mj的冲突度为2，且该任务的可见时间窗口长度最大，故为任务Mj重新选择时间窗口。在重新选择的时间窗口时，任务Mj的第一个时间窗口又可能会引起任务Mi和Mk的冲突，故为任务Mj重新分配的执行时间窗口为第3 个可见时间窗口。

3.3 效益值计算

通常情况下，效益值的计算是直接与任务完成个数或个体冲突度相关联的［18］，即适应度函数值的计算与个体效益值无关，只与完成个数和冲突度相关，即冲突个数相等的两个个体效益值相等，同样对于如下情况计算得到的效益值也是相等的。

假设任务Mi、Mj、Mk有相同的效益值，显然，对于图2 所示任务执行状态1，在调度方案中只需要消除任务Mj，就可完成Mi和Mk两项任务，而对于图3所示任务执行状态2，无论如何消除冲突，调度方案中最终只有一个任务可以被完成。

对于上述情况，可以采取一种个体任务冲突度的方式消除冲突。个体适应度评估函数为

图2 任务执行冲突1Fig.2 Mission execution conflict of case 1

图3 任务执行冲突2Fig.3 Mission execution conflict of case 2

式中：任 务Mi、Mj、Mk的效益值分别为wi、wj、wk，故任务Mi、Mj、Mk的冲突度分别为Vi、Vj、Vk，Vi=wj+wk，Vj=wi+wk，Vk=wi+wj，按任务冲 突度降序排序，依次删除任务，直到个体中无任务冲突为止，此时再计算个体中的所有分配时间窗口的任务的效益之总和。这样可以更大限度地保留效益值或权重较大的任务，从而更有效地选出效益值较大的个体，生成较优的调度方案。

3.4 可行解二次优化

当采用近似算法求解该卫星星座调度问题时，对于每次求解生成的调度方案，针对性地用确定性算法对调度结果进行二次优化。针对某一次的调度结果，主要从任务完成率、资源利用率和时效性3个方面对指定卫星系统的本次调度方案进行评估。对于当前调度结果，如果存在由于资源冲突而未能完成的任务，或者为任务分配的时间段对其要求的时间限有延迟，则通过调度优化操作可以在任务完成率、资源利用率和时效性3 个方面都能够进行优化，从而进一步解决并优化调度结果，使得调度结果更优，并能够满足用户的需求。

1）对调度结果中的所有已分配时间窗口的任务进行时间优化。找出已分配时间窗口的任务，结合预处理结果，将所有任务的分配时间窗口前移，且主要针对有时间延迟的任务，尝试为其选择更好的执行时间窗口。

2）为调度方案中因资源冲突未完成的任务重新搜索时间窗口。针对上一步操作，对经过时间优化后的调度结果进行分析，找出所有因资源冲突而未能安排的任务，遍历其所有可见时间窗口，尝试为其重新选择执行时间窗口。

4 仿真试验及结果分析

4.1 场景管理

成像侦察卫星需要包括观测卫星及其所载传感器。为了使本文设计的成像侦察卫星系统资源更加切合实际，从国外卫星应用强国发射并投入使用的观测卫星中选取了5 颗构造了一个成像侦察卫星 网，分别 是SPOT-5、MTI、ORBVIEW-3、IKO⁃NOS-2、EO-1，卫星轨道参数可查询AGI 公司发布的全球卫星轨道数据库。随着卫星应用的深入，卫星星上载荷类型不断丰富，从传感器角度看，包括可见光、红外、多光谱、高光谱、合成孔径雷达（Syn⁃thetic Aperture Radar，SAR）等多种传感器类型。为体现成像类型约束，本文中星载传感器的性能参数设置见表1。场景仿真周期为2018-01-01 00∶00∶00—2018-01-01 18∶00∶00

表1 传感器参数Tab.1 Sensor parameters

地面目标即观测目标，它是生成观测任务的基本要素。本文在地球陆地范围内随机选取了100 个地面目标以及中国境内的35 个城市作为目标。这个地面目标集合具有一定的代表性，基本上能够以一定的密度覆盖地球陆地。地面目标的具体分布如图4 所示（软件STK 提供的二维平面地图）。图4中，红色圆点表示待成像的地面目标，阴影部分表示星载传感器在当前时刻对地面的覆盖范围。在实际应用中，经常会对某一个地区比较集中的若干点目标进行观测，从而引起任务对资源的争用冲突，因此，在地面目标集也设计了几组位置比较集中的点目标，这种目标比较集中的观测任务往往会带来对卫星资源的需求冲突问题，采用手工计算很难解决，必须依靠计算机来解决。

图4 二维地面目标分布图Fig.4 2D ground-target distribution

4.2 规划结果

对于上述测试实例计算可得，任务完成理论上限为135 个。分别采用标准DE 和基于启发式思想的改进DE 进行求解，实验生成的调度方案结果对比见表2 和表3。

表2 标准DE 任务完成情况Tab.2 Mission completion status with the standard DE

4.3 结果分析

1）标准DE 和改进DE 对该问题的求解，算法性能对比分析。

测试方案的任务完成率和任务完成效益比值分别如图5 和图6 所示。图中，红线表示任务完成上限，绿线表示采用改进DE 得到的结果，蓝线表示采用标准DE 得到的结果。

由图5 和图6 可知：本文在问题的求解过程中，采用启发式思想消除个体冲突和计算适应值，可以有效地生成较好的任务规划结果，生成调度方案的任务完成率和任务完成效益非常接近于任务完成理论上限值，并且对于每一组调度方案，任务的完成效益都大于任务的完成率。

表3 改进DE 任务完成情况Tab.3 Mission completion status with the improved DE

图5 测试方案的任务完成率Fig.5 Mission completion rate of the test scheme

图6 测试方案的任务完成效益率Fig.6 Mission completion benefit rate of the test scheme

2）采用调度优化模块对调度方案的结果影响分析。

采用标准DE 生成调度方案的任务完成率和任务完成效益比值分别如图7 和图8 所示。图中，红线表示任务完成上限，蓝线表示直接采用标准DE得到的结果，绿线表示在调度方案的基础上采用调度优化模块后得到的结果。

图7 标准DE 生成调度方案的任务完成率Fig.7 Mission completion rate of the scheduling scheme generated by the standard DE algorithm

图8 标准DE 生成调度方案的任务完成效益Fig.8 Mission completion benefit rate of the scheduling scheme generated by the standard DE algorithm

采用DE 生成调度方案的任务完成率和任务完成效益比值分别如图9 和图10 所示。图中，红线表示任务完成上限，蓝线表示直接采用改进DE 得到的结果，绿线表示在调度方案的基础上采用调度优化模块后得到的结果。

由调度优化模块对调度方案的影响结果分析图可知，当采用近似算法求解该卫星星座调度问题时，对于每次求解生成的调度方案，具有针对性地用确定性算法对调度结果进行二次优化。对于存在由于资源冲突而未能完成的任务，或者为任务分配的时间段对其要求的时间限有延迟，则通过调度优化操作可以在任务完成率、资源利用率和时效性3 个方面都能够进行优化，从而进一步解决并优化调度结果，使得调度结果更优，并能够满足用户的需求。

图9 改进DE 生成调度方案的任务完成率Fig.9 Mission completion rate of the scheduling scheme generated by the improved DE algorithm

图10 改进DE 生成调度方案的任务完成效益Fig.10 Mission completion benefit rate of the scheduling scheme generated by the improved DE algorithm

5 结束语

本文通过分析成像卫星的成像过程和工作原理，建立了多成像卫星的约束满足最优化调度规划模型。在此基础上，采用启发式算法思想，设计了成像卫星联合任务规划问题的改进DE 求解方案。通过测试实例发现，在改进DE 迭代过程中采用启发式算法思想，消除个体中任务的冲突并计算个体适应值，可以快速地生成较优的调度方案。调度优化操作的实现对每一次调度结果进行优化，可以进一步提高本次调度方案的任务完成率、资源利用率和时效性。同时，调度优化操作的实现，同样也可以应用到应急调度中，从而生成较优的调度方案。