基于数据驱动型敏捷卫星任务并行调度方法

摘要

本发明公开了一种基于数据驱动型敏捷卫星任务并行调度方法，包括步骤1、获取敏捷成像卫星历史任务调度数据和待分配任务集；2、通过基于深度学习算法对任务预测模型进行训练，并对每个待分配任务的调度概率进行预测；3、根据概率预测结果，将每个任务分配给调度概率最大的卫星，将大规模卫星任务调度问题转化成多个平行的单星调度问题；4、求解；5、输出每一个待分配任务的敏捷成像卫星任务调度序列。本发明通过机器学习算法得到的任务调度概率预测模型，将每个任务分配给调度概率最大的卫星来执行，使复杂问题得到了简化，使任务调度时间由小时级缩短到分钟级，有效提升了大规模敏捷成像卫星任务的调度效率。

说明书

技术领域

本发明属于任务规划调度领域，尤其涉及一种基于数据驱动型敏捷卫星任务并行调度方法。

背景技术

随着卫星技术的不断发展，以及人类对地球与太空资源的不断开发利用，应用卫星已经成为一种十分重要的天基资源。根据不同的卫星应用类型，应用卫星通常可以分为成像卫星、通讯卫星和导航卫星。其中，地球成像卫星主要拍摄或收集地球表面的图像与情报信息，已在资源勘测、地理信息系统管理、气象预报、导弹预警等各类军事或民用领域得到广泛应用。随着我国成像卫星应用向广度和深度的不断发展，各行业用户向卫星管控部门提出了大规模、复杂化的对地成像需求。同时，在国家航天发展战略的不断推进下，我国在轨成像卫星数量也持续增长。面临着需求规模和资源规模双重增长，如何通过合理调度充分发挥成像卫星观测能力、提升多星协同管控水平、最大化卫星资源使用效益，成为一个必需研究的课题。

为了克服传统成像卫星只具备滚动自由度成像能力的不足，世界各卫星大国相继研发并发射了具备完整三个自由度转动成像能力的敏捷成像卫星。如图1(a)所示，由于传统卫星只具备绕着飞行轨迹侧摆的成像能力，故只能拍摄其星下点轨迹两点的地面目标。那么传统卫星任务调度问题可以理解为为每个地面目标选择一个卫星成像机会，称为可见时间窗口(Visible Time Window,VTW)。而对于图1(b)所示敏捷成像卫星，由于其还具备俯仰和偏航的机动能力，故敏捷成像卫星的可见时间窗口通常要更长。换言之，同一个地面目标的成像任务，若由传统卫星执行，则该成像动作需要覆盖整个可见时间窗口；而若由敏捷成像卫星执行，则该成像活动可以在可见时间窗口内的任意时刻开始。那么敏捷成像卫星的调度问题不仅需要决策可见时间窗口的选择，同时还要决策成像动作在窗口内的开始时刻。可见，敏捷成像卫星的任务调度问题将具有更大的解空间，带来了更高的求解难度。此外，为了满足持续增长的对地观测任务需求，多星协同技术也常常被使用，这样无疑进一步加剧了敏捷成像卫星任务调度大规模和长时耗的特点。在目前卫星管控部分每天仅预留事迹分钟到几小时调度时间的现实背景下，怎样在有限时间内快速对大规模多敏捷成像卫星进行调度并给出调度方案已成为敏捷成像卫星任务调度的首要难题。

发明内容

本发明要解决的技术问题是针对大规模敏捷卫星调度速率慢，不能在有限时间内快速给出调度方案的问题，提供了一种基于数据驱动型敏捷卫星任务并行调度方法。

为解决该问题，本发明采用的技术方案是：

基于数据驱动型敏捷卫星任务并行调度方法，包括以下步骤：

步骤1：获取敏捷成像卫星历史任务调度数据和待分配任务集；

步骤2：通过基于深度学习算法使用历史任务调度数据对任务预测模型进行训练，并基于训练后的预测模型对每个待分配任务的调度概率进行预测；

步骤3：根据卫星任务调度概率预测结果，将待分配任务集中的每个任务分配给调度概率最大的敏捷卫星，从而将大规模多敏捷成像卫星任务调度问题转化成多个平行的单星调度问题；

步骤4：对多个平行的单星调度问题进行求解；

步骤5：输出(待分配任务集中每一个待分配任务的)敏捷成像卫星任务调度序列。

进一步地，步骤2中基于深度学习算法使用历史任务调度数据对任务预测模型进行训练的具体方法为：

步骤2.1：提取历史任务调度数据的任务特征作为样本训练数据；

步骤2.2：使用样本训练数据基于深度学习算法对任务预测模型进行训练；

步骤2.3：得到训练后的任务调度概率预测模型。

进一步地，所述任务特征为：任务优先级、成像时间、成像时间窗口数量、成像时间窗口长度、成像时间窗口冲突数、成像时间窗口冲突长度。

进一步地，步骤2.2中所述深度学习算法为协同进化神经网络算法。

进一步地，所述协同进化神经网络算法的步骤为：

步骤1：初始化，提取任务特征作为初始神经网络的输入，生成具有相同神经网络结构的初始种群，所述初始种群具备输入节点和输出节点；

步骤2：选择，选择80％种群规模的神经网络个体并保留它们到下一代；

步骤3：交叉，随机选择60％种群规模的神经网络结构个体进行交叉操作，然后进行禁忌搜索操作，用交叉后较优的个体替换父代中较差的个体，并保持种群大小不变；

步骤4：变异，随机选择20-40％种群规模的神经网络结构个体进行变异操作，随后进行禁忌搜索操作，用变异后较优的个体替换父代中较差的个体。

步骤5：若满足最大迭代次数或样本预测准确度阈值，则输出最佳的神经网络模型，否则跳至步骤2。

进一步地，所述将待分配任务集中的每个任务分配给调度概率最大的敏捷卫星的方法为：

步骤3.1：将待分配任务集R⁰中的任务按照优先级降序进行排序；

步骤3.2：将候选敏捷卫星集合S按照最早可见时间窗时刻升序进行排序；

步骤3.3：假设任务r_i分配给卫星s_j，则提取任务特征f_ij，其中r_i∈R⁰表示第i个待分配任务，s_j∈S，表示第j个候选敏捷卫星，f_ij表示第i个任务r_i分配给第j个卫星s_j时的任务特征；

步骤3.4：将任务特征f_ij输入任务调度概率预测模型预测出任务可调度概率，记录任务r_i分配给卫星s_j的调度预测概率。若候选卫星遍历完毕，转步骤3.5，否则返回步骤3.3且j＝j+1；

步骤3.5：输出任务r_i调度预测概率最大的卫星s_j，将任务r_i分配给该卫星。

步骤3.6：若任务分配完毕，则结束，否则转步骤3.3且i＝i+1。

进一步地，所述计算成像时间窗口冲突长度的方法为

步骤2.1.1：将已分配给该卫星的全部任务按照可见时间窗口在时间轴上排列；

步骤2.1.2：计算待分配任务的可见时间窗口与已分配任务可见时间窗口的总重叠长度。

进一步地，所述对平行的单星调度问题进行求解的方法为禁忌模拟退火算法或禁忌逾期算法。

进一步地，所述禁忌模拟退火算法包括以下步骤：

步骤4.1：初始化随机选择一个解i，计算收益值f(i)；设初始代数k＝0,初始温度t₀＝T,最优解s＝i；

步骤4.2：判断是否达到最大迭代次数。若达到最大迭代次数，则转步骤10，否则进入步骤4.3；

步骤4.3：判断当前模拟退火温度下是否完成30次内循环。若完成内循环，则进入步骤4.9，否则进入步骤4.4；

步骤4.4：从当前解i的邻域中随机选择一个解j，计算j的收益值f(j)；

步骤4.5：若f(j)>f(i)，则进入步骤4.7，否则进入步骤4.6；

步骤4.6：根据模拟退火算法Metropolis准则，判断解j是否被接受。若解j被接受，则进入步骤4.7，否则返回步骤4.2；

步骤4.7：判断新解j是否在禁忌表中。若新解j不在禁忌表中，则进入步骤8，否则返回步骤4.2；

步骤4.8：令i＝j，更新最优解s＝j；将解j放入禁忌表，并将禁忌表中最早的一个解删除；

步骤4.9：模拟冷却降温,令t_k＝t₀/(1+lg(1+k))，并令迭代次数k＝k+1；

步骤4.10：输出当前最优解s。

进一步地，所述禁忌逾期算法包括以下步骤：

步骤4.1’：初始化随机选择一个解i_k，计算收益f(i_k)；设逾期表长度为L，设初始代数k＝L,,最优解s＝i_k；

步骤4.2’：判断是否达到最大迭代次数。若达到最大迭代次数，则进入步骤9，否则进入步骤4.3’；

步骤4.3’：k＝k+1；更新逾期表，计算i_k-L的收益值f(i_k-L)；

步骤4.4’：从当前解i_k的邻域中随机选择一个解j，计算j的收益值f(j)；

步骤4.5’：若f(j)≥f(i_k)，则进入步骤4.7’，否则进入步骤4.6’；

步骤4.6’：若f(j)≥f(i_k-L)，则进入步骤4.3’，否则进入步骤4.7’；

步骤4.7’：判断新解j是否在禁忌表中。若新解j不在禁忌表中，则进入步骤8，否则返回步骤4.3’；

步骤4.8’：令i_k＝j，更新最优解s＝j；将解j放入禁忌表，并将禁忌表中最早的一个解删除；

步骤4.9’：输出当前最优解s。

与现有技术相比，本发明取得的有益效果为：

本发明充分利用了敏捷成像卫星历史调度数据，通过提取历史调度数据的任务特征作为训练数据，然后通过协同进化神经网络算法对任务预测模型进行训练，得到训练后的任务调度概率预测模型，将每个任务分配给最有可能完成该任务的一颗卫星执行，即将每个任务分配给对该任务来说调度概率最大的一颗卫星来执行，从而将大规模敏捷成像卫星任务调度被转化为并行单星任务调度，使复杂的大规模卫星调度问题转化成简单的并行单星调度问题，本发明通过将数据学习、任务分配和并行调度技术有机结合，使复杂问题得到了简化，实验表明，通过本发明可将大规模敏捷成像卫星任务调度时间由小时级缩短到分钟级，有效提升了大规模敏捷成像卫星任务的调度效率。

附图说明

图1为传统成像卫星与敏捷成像卫星的区别示意图,(a)传统卫星成像方式.(b)敏捷卫星成像方式；；

图2为本发明流程图；

图3为协同进化神经网络算法中采用的激励函数类型

图4为协同进化神经网络模型五节点神经网络；(a)五节点神经网络编码示意图(b)五节点神经网络结果示意图

图5为C-NEAT算法中的两种结构变异方式示意图；

图6为C-NEAT算法神经网络结构交叉操作示意图；

图7为任务成像时间窗口冲突长度的计算方法；

图8为敏捷成像卫星任务调度优化中的遗传策略；

图9为混合禁忌策略的智能优化算法；

图10为成像目标与卫星仿真环境，(a)目标分布.(b)卫星轨迹；

图11为不同方法的任务调度对比结果图；

图12为1000目标规模场景的调度效率参数定义；

图13为不同目标规模场景下本方法的调度效率参数

具体实施方式

图1至图13示出了本发明基于数据型敏捷卫星认为调度规划方法的一种实施例，如图2所示，本发明包括步骤1：获取敏捷成像卫星历史任务调度数据和待分配任务集；步骤2：通过基于深度学习算法使用历史任务调度数据对任务预测模型进行训练，并基于训练后的预测模型对每个敏捷成像卫星任务调度概率进行预测；步骤3：根据卫星任务调度概率预测结果，将待分配任务集中的每个任务分配给调度概率最大的敏捷卫星，从而将大规模多敏捷成像卫星任务调度问题转化成多个平行的单星调度问题；步骤4：对多个平行的单星调度问题进行求解；步骤5：输出待分配任务集中每一个待分配任务的敏捷成像卫星任务调度序列。在卫星任务调度实践中，虽然已有基于负载平衡和优先级平衡等的任务分配策略，但这些任务分配策略在任务调度之前并不可能预测哪些任务最终将由卫星执行，所以很难保证任务分配的合理性。本发明通过充分利用了敏捷成像卫星历史调度数据，通过提取历史调度数据的任务特征作为训练数据，然后通过协同进化神经网络算法对任务预测模型进行训练，得到训练后的任务调度概率预测模型，将每个任务分配给最有可能完成该任务的一颗卫星执行，即将每个任务分配给对该任务来说调度概率最大的一颗卫星来执行，从而将大规模敏捷成像卫星任务调度被转化为并行单星任务调度，使复杂的大规模卫星调度问题转化成简单的并行单星调度问题，本发明通过将数据学习、任务分配和并行调度技术有机结合，使复杂问题得到了简化，实验表明，通过本发明可将大规模敏捷成像卫星任务调度时间由小时级缩短到分钟级，有效提升了大规模敏捷成像卫星任务的调度效率。

本实施例中，步骤2中基于深度学习算法使用历史任务调度数据对任务预测模型进行训练的具体方法为：

步骤2.1：提取历史任务调度数据的任务特征作为样本训练数据；

步骤2.2：使用样本训练数据基于深度学习算法对任务预测模型进行训练；

步骤2.3：得到训练后的任务调度概率预测模型。

在本实施例中，历史任务调度数据中任务特征提取对任务预测模型训练发挥着重要作用，因为其不仅需从历史任务数据中学习并训练模型，还需进一步驱动任务分配。所以，首先需要明确用于训练的数据输入(样本特征)与输出(样本标签)。若任务被成功调度，则训练输出为1，否则为0。

为了提升样本特征提取的合理性，基于如下的敏捷成像卫星任务特征分析，本实施例中采用如表1所示参数实现任务特征的提取：

·任务优先级：直接影响了任务调度收益，高优先级的任务往往具有更高的调度可能性；

·成像时间：表示了任务需要占用卫星资源的程度和时间，成像时间越长的任务很可能越难被调度；

·成像时间窗口数量：反映了任务被观测的机会，拥有更多成像时间窗口的任务很可能更容易被调度；

·成像时间窗口长度：同样反映了任务被观测的机会，拥有更长成像时间窗口的任务很可能更容易被调度；

·成像时间窗口冲突数：与其他待调度任务的成像时间窗口相比较，是否存在冲突。若该任务与其他任务存在较多的成像时间窗口冲突，那么这个任务很可能无法被调度。

·成像时间窗口冲突长度：与其他待调度任务的成像时间窗口相比较，存在冲突的成像窗口总长度。若该任务的成像时间窗口中大部分已与其他任务成像窗口冲突，那么这个任务很可能无法被调度。其中，成像时间窗口冲突长度的计算方法如图7所示，具体为：

步骤2.1.1：将已分配给该卫星的全部任务按照可见时间窗口在时间轴上排列；

步骤2.1.2：计算待分配任务的可见时间窗口与已分配任务可见时间窗口的

总重叠长度。

表1:敏捷成像卫星任务特征

本实施例中，历史任务调度数据的任务特征有：任务优先级、成像时间、成像时间窗口数量、成像时间窗口长度、成像时间窗口冲突数、成像时间窗口冲突长度。

本实施例中，基于深度学习算法为协同进化神经网络算法。进化神经网络(NeuroEvolution of Augmenting Topologies，NEAT)算法是一种采用进化算法优化神经网络结构的算法框架。NEAT能够通过进化算法对神经网络中的节点设置、链接及权值等进行迭代优化，在诸多研究中表现出优于传统BP神经网络的预测结果。同时，许多学者针对NEAT中激励函数的多样性、神经网络结构变异操作等方面开展了改进研究。由此，为进一步提高NEAT在敏捷成像卫星任务调度场景中的预测精度，本方法在NEAT迭代进化过程中引入局部禁忌搜索(Tabu Search，TS)策略，设计改进型的深度进化神经网络(Cooperative NeuroEvolution of Augmenting Topologies，C-NEAT)。C-NEAT能够在TS策略的帮助下，帮助神经网络结构在进化算法中跳出局部最优，同时增加收敛速度，能够在有限的时间内完成样本训练并收敛至满意的模型优化结果。

本实施例中，协同进化神经网络算法的步骤为：

步骤1：初始化，提取任务特征作为初始神经网络的输入，生成具有相同神经网络结构的初始种群，所述初始种群具备输入节点和输出节点；

步骤2：选择，选择80％种群规模的神经网络个体并保留它们到下一代；

步骤3：交叉，随机选择60％种群规模的神经网络结构个体进行交叉操作，然后进行禁忌搜索操作，用交叉后较优的个体替换父代中较差的个体，并保持种群大小不变；较优是指交叉前的个体有一个收益值，交叉后的个体又有一个收益值。若后者大于前者，则用后者替换前者。

步骤4：变异，随机选择20-40％种群规模的神经网络结构个体进行变异操作，随后进行禁忌搜索操作，用变异后较优的个体替换父代中较差的个体。

步骤5：若满足最大迭代次数或样本预测准确度阈值，则输出该神经网络模型，否则跳至步骤2。本实施例中，样本预测准确度阈值为95％。

C-NEAT算法中神经网络结构需要表示神经网络的独立和完整的结构。C-NEAT的个体基因组通常分为节点基因和连接基因，它们分别表示神经节点的信息和不同节点之间的关系。因此，考虑到人工神经网络和进化算法的特点，本方法中将C-NEAT中神经网络的基因编码如下：

·节点基因，包括节点id、节点属性、输入/输出属性、偏好值和激励函数等。其中激励函数采用如图3所示的log-sigmoid、tan-sigmoid和relu函数；

链接基因，包括链接识别id、开始节点、结束节点、是否激活和权值等。

图4给出了协同进化神经网络模型五节点神经网络示意图，可以通过对编码的调整实现C-NEAT算法的变异操作。在C-NEAT中，变异操作可以对神经网络结构、节点偏好值、节点激励函数、链接权值和链接激活状态等同时进行。其中，节点偏好值、链接权值与传统进化算法中的变异操作相同，激励函数变异即在图3中随机选择一个函数作为新函数。而神经网络结构变异较为特殊，可以通过增减链接和增减节点实现，如图5(a)和图5(b)所示。

为了实现C-NEAT算法的交叉操作，则必须区分种群中任意两个个体之间基因的匹配关系，这其中链接基因中的链接识别id则发挥了重要作用。通过链接识别id，C-NEAT可以判断出具有相同链接识别id的两个基因来源于同一个基因祖先。换言之，C-NEAT的初始化和变异操作都可能要生成或删除一个链接识别id，以此作为交叉操作的依据，并在整个交叉过程中保持不变。在图6中，父代神经网络基因1和2在节点1、2、4、5和5中具有相同的链接识别id，因此这些基因是从相同的祖先基因进化而来的。那么，在交叉操作中，两个基因组中具有相同创新数的基因排列在一起，然后后代随机地从父代基因中遗传染色体。而链接识别id不同的基因则从适应度函数值更高的父代中遗传染色体。值得注意的是，链接识别id、起始节点和结束节点在整个进化过程中保持不变，但激活函数和权值将进行变异操作。由此可见，上述交叉操作能够保留父代神经网络的主要结构，符合进化算法的本质特点。本实施例中，考虑到进化算法的全局寻优能力和局部搜索算法的局部优化能力，本方法将TS算法与传统NEAT结合，以帮助神经网络结构在进化算法中跳出局部最优，同时增加收敛速度，能够在有限的时间内完成样本训练并收敛至满意的模型优化结果。

本发明通过数据驱动的方式指导任务分配，如果每个任务都分配给最有可能完成该任务的一颗卫星执行，那么任务分配后的调度收益很可能更高。本发明通过在步骤二协同进化神经网络训练预测模型的基础上，设计了一种可调度性预测收益最大化的任务分配算法，其核心是将每一个任务分配给最可能完成这个任务的卫星。

本实施例中，将待分配任务集中的每个任务分配给调度概率最大的敏捷卫星的方法为：

步骤1：将待分配任务集R⁰中的任务按照优先级降序进行排序；

步骤2：将候选敏捷卫星集合S按照最早可见时间窗时刻升序进行排序；

步骤3：假设任务r_i分配给卫星s_j，则提取任务特征f_ij；

步骤4：将任务特征f_ij输入任务调度概率预测模型预测出任务可调度概率，记录任务r_i分配给卫星s_j的调度预测概率。若候选卫星遍历完毕，进入步骤3.5，否则进入步骤3且j＝j+1；

步骤5：输出任务r_i调度预测概率最大的卫星id，将任务r_i分配给该卫星。

步骤6：若任务分配完毕，则结束算法，否则进入步骤3.3且i＝i+1。

本实施例中，对平行的单星调度问题进行求解的方法为禁忌模拟退火算法或禁忌逾期算法。模拟退火算法(Simulated Annealing，SA)和逾期接受算法(Late Acceptance，LA)等广泛使用的人工智能优化算法已成为求解大规模NP难问题的有效途径。针对经任务分配后的敏捷成像卫星任务调度问题，本发明分别从解的编码和邻域搜索的角度出发，在传统SA和LA算法的邻域搜索过程中引入遗传策略和禁忌策略，以提升算法求解敏捷成像卫星任务调度问题的全局搜索能力。

1.混合遗传策略

在敏捷成像卫星任务调度问题中，本发明采用整数编码的方式，记录了每颗敏捷卫星所需要执行的任务id,如图8所示。为提升算法的全局搜索能力，本节在传统SA和LA的基础上引入遗传算法中的交叉与变异策略。

交叉策略包括单轨任务序列交叉和多轨任务序列交叉。单轨任务序列交叉操作对某一卫星轨道当前计划任务集合中连续几个任务进行交换，实现单轨任务序列片段顺序的交叉操作，例如图8(a)中任务序列片段122->1316与915->303进行了交换。多轨任务序列交叉操作则交换两条卫星轨道中连续的任务计划，实现两条轨道的任务序列交叉，例如图8(b)中轨道i的任务48->915与轨道j的任务1599->65进行了交叉。而变异策略即采用图8(c)所示的单点变异操作。

2.混合禁忌策略

禁忌策略主要体现在局部搜索的过程中。在SA算法方面，禁忌策略嵌入其每次降温操作前的内循环过程中，记录内循环搜索空间中局部最优解，以提升当前退火温度下局部搜索的效果。算法流程如图9(a)所示。其中，适应度函数f(i)即敏捷成像卫星任务调度问题中的目标函数；模拟退火算法的冷却降温过程采用经典降温函数；温度t_k下的平衡条件为连续30次邻域构造后最优解s未被改进。

在LA算法方面，由于算法在迭代过程中接受的是非劣解，很有可能重复访问适应度值f(i)相同的局部最优解。故本发明在LA算法中引入禁忌策略，当每次访问逾期表后进行禁忌操作，若待接受的新解已被禁忌，则放弃接受，以避免重复的解空间搜索。算法流程如图9(b)所示。

本实施例中所使用的禁忌模拟退火算法的具体步骤为：

步骤4.1：初始化随机选择一个解i，计算收益值f(i)；设初始代数k＝0,初始温度t₀＝T,最优解s＝i；

步骤4.2：判断是否达到最大迭代次数。若达到最大迭代次数，则转步骤10，否则进入步骤4.3；

步骤4.3：判断当前模拟退火温度下是否完成30次内循环。若完成内循环，则进入步骤4.9，否则进入步骤4.4；

步骤4.4：从当前解i的邻域中随机选择一个解j，计算j的收益值f(j)；

步骤4.5：若f(j)>f(i)，则进入步骤4.7，否则进入步骤4.6；

步骤4.6：根据模拟退火算法Metropolis准则，判断解j是否被接受。若解j被接受，则进入步骤4.7，否则返回步骤4.2；

步骤4.7：判断新解j是否在禁忌表中。若新解j不在禁忌表中，则进入步骤8，否则返回步骤4.2；

步骤4.8：令i＝j，更新最优解s＝j；将解j放入禁忌表，并将禁忌表中最早的一个解删除；

步骤4.9：模拟冷却降温,令t_k＝t₀/(1+lg(1+k))，并令迭代次数k＝k+1；

步骤4.10：输出当前最优解s。

本实施例中所使用的禁忌逾期算法的具体步骤为：

步骤4.1’：初始化随机选择一个解i_k，计算收益f(i_k)；设逾期表长度为L，设初始代数k＝L,,最优解s＝i_k；

步骤4.2’：判断是否达到最大迭代次数。若达到最大迭代次数，则进入步骤9，否则进入步骤4.3’；

步骤4.3’：k＝k+1；更新逾期表，计算i_k-L的收益值f(i_k-L)；

步骤4.4’：从当前解i_k的邻域中随机选择一个解j，计算j的收益值f(j)；

步骤4.5’：若f(j)≥f(i_k)，则进入步骤4.7’，否则进入步骤4.6’；

步骤4.6’：若f(j)≥f(i_k-L)，则进入步骤4.3’，否则进入步骤4.7’；

步骤4.7’：判断新解j是否在禁忌表中。若新解j不在禁忌表中，则进入步骤8，否则返回步骤4.3’；

步骤4.8’：令i_k＝j，更新最优解s＝j；将解j放入禁忌表，并将禁忌表中最早的一个解删除；

步骤4.9’：输出当前最优解s。

下面通过实验与目前最先进的大规模敏捷成像卫星任务调度方法对比，来验证本方法的优越性。在效果验证中，本发明选择文献1“L.He,X.L.Liu,G.Laporte,Y.W.Chen andY.G.Chen,“An improved adaptive large neighborhood search algorithm formultiple agile satellites scheduling,”Comput.Operat.Res,vol.100,pp.12-25,2018”的成像目标场景和他提出的自适应大邻域搜索算法(Adaptive Task Assignmentbased Adaptive Large Neighborhood Search,A-ALNS)作为对比对象。该研究成果于2018年7月发表在运筹学领域顶级期刊《Computers and Operations Research》，是求解大规模敏捷成像卫星任务调度问题的最新解决方案。

在目标场景方面，实验效果验证中共采用目标数量分别为100，200，300，400，500，600，700，800，900和1000的9组场景，目标数量由100到1000反应了敏捷成像卫星任务调度规模由小到大的变化趋势。由于本发明主要针对我国卫星任务管控背景，故卫星成像目标主要分布于我国境内及周边国家(经度74°E～133°E，纬度3°N to 53°N)，如图10(a)所示。

在卫星环境方面，实验效果验证中供投入6颗敏捷成像卫星，其同一时刻的轨道面示意图如图10(b)所示，轨道参数如表3所示。每颗卫星的俯仰角、侧摆角和偏航角的最大值分别为45°,45°和90°。

表3:卫星轨道参数

参数卫星1卫星2卫星3卫星4卫星5卫星6轨道半长轴720000072000007200000720000072000007200000轨道偏心率0.0006270.0006270.0006270.0006270.0006270.000627轨道倾角96.576096.576096.576096.576096.576096.5760近地点角距000000升交点赤经175.72145.72115.7285.7255.7225.72平近点角0.075030.075060.075090.0750120.0750150.0750

在计算机仿真环境方面，协同进化神经网络及历史样本数据训练通过Python 3编写完成，任务分配及并行单星任务调度通过Java 1.8.0实现。实验计算机采用Intel(R)Core(TM)i7-7600U CPU 2.80GHz，系统环境为Windows10，内存为8GB RAM。实验验证的算法参数如表4所示。

表4实验效果验证的算法参数

参与对比验证的调度方法共有1)基于禁忌退火算法的数据驱动型并行调度方法；2)基于禁忌逾期算法的数据驱动型并行调度方法；3)无简化的一体化成像调度；4)文献1提出的A-ALNS方法；5)为每一个分配最早成像机会的启发式规则。不同方法的任务调度对比结果如表5和图11所示。

表5不同方法的任务调度对比结果

对比结果表明，基于禁忌退火算法(TSA)和基于禁忌逾期算法(TLA)的本方法在不同目标规模场景中均能取得显著优于多星一体化调度和启发式规则的结果。与最新研究成果A-ALNS方法相比，当目标规模超过400时，本发明的调度结果明显由于A-ALNS方法。而当目标规模小于400时，本发明的调度结果略小于A-ALNS方法。由此可见，本发明提出的数据驱动型并行调度方法能够具备有效求解大规模敏捷成像卫星任务调度问题的能力，在大规模任务调度结果方面均优于现有调度方法。

下面从调度效率来进一步验证本发明所提到的方法。

考虑到调度效率是一个很难定量的评估参数，故这里定义了两个具体参数来描述本方法任务调度的效率，如图12所示。其中，最大化计算时间为4h，当本发明提出的数据驱动型并行调度方法结果达到最终调度结果的99％，则定义该方法“收敛”，相应的计算时间为“收敛时间(T_c)”。而从图中也可见，本方法的收敛速度虽然由于多星一体化的调度方法，但受到任务分配的影响，最终调度结果并不能达到多星一体化调度的效果，那么，定义两种方法达到相同调度结果的时间为“相遇时间(T_m)”。当计算时间小于T_m时，本方法的调度效果更优；而当计算时间大于T_m时，则多星一体化的调度效果更佳。例如，在图12所示的1000目标场景下，本方法的收敛时间为1676s，收敛结果为4340，是多星一体化调度最终收益(4749)的91.3％。两种方法的相遇时间为5050s，是本方法收敛时间的3倍。由此可见，在达到相同调度结果时，本发明提出的数据驱动型并行调度方法将大规模敏捷成像卫星任务调度时间从1.5h缩短至0.5h，该调度时间是我国卫星管控部门的理想调度时间。

根据上述调度两种参数的定义，本方法在目标场景规模从100到1000的调度效率参数如图13所示。为了进一步量化本方法调度效率，引入式(12)来描述本方法对敏捷成像卫星任务调度效率的提升量。不同目标场景下本方法的调度效率提升如表6所示。

表6不同目标场景下本方法的调度效率提升值

目标规模效率提升目标规模效率提升10015.54％60061.72％20038.57％70066.00％30045.98％80070.23％40050.25％90070.33％50062.69％100066.55％

由上表可知，本发明提出的数据驱动型并行调度方法在不同目标规模下均能对敏捷成像卫星任务调度效率进行提升。同时，随着目标规模的增加，本方法的效率提升更加明显。当目标规模超过500时，本方法的效率提升量稳定于60％～70％。综上所述，本发明提出的数据驱动型并行调度方法能够显著提升敏捷成像卫星任务调度效率，对提升大规模敏捷成像卫星任务调度效率具有重大意义。

综上所述，敏捷成像卫星任务调度是一个具有大规模、长时耗和过度订阅特征的NP难问题，与传统成像卫星任务调度问题相比具有更高的求解难度。为了有效求解大规模敏捷成像卫星任务调度问题，本发明提出的基于数据驱动型敏捷卫星并行调度方法，将数据学习、任务分配和并行调度技术有机结合，充分利用了卫星历史任务调度数据，有效降低了问题求解规模。并且通过一系列实验对比实验，验证了本方法的能够在满足卫星管控部门时间需求的情况下取得高质量的任务调度结果，对合理调度充分发挥成像卫星观测能力、提升多星协同管控水平、最大化卫星资源使用效益均具有重大意义。