基于数据驱动的多星协同卫星任务调度方法、系统及装置

1.本发明涉及卫星调度技术领域，尤其是涉及一种基于数据驱动的多星协同卫星任务调度方法、系统及装置。


背景技术：

2.卫星任务规划是指在不违反卫星使用约束的前提下，面向用户需求生成卫星可执行的任务序列，并确定任务的开始时间和结束时间以达到某些目标。类似于大区域目标覆盖、多频次密集点目标观测等复杂任务往往需要多颗卫星协同配合才能完成。多星协同调度的难点主要有：如图1所示，区别于传统非敏卫星只能在星下点观测目标，敏捷卫星由于具备滚动、俯仰、偏航三个方向的自由度，这使得敏捷卫星可以提前或延后对目标进行观测，可见时间窗口(vtw)将变长，甚至远大于任务的执行时长；相较于单星规划仅确定任务执行时刻，多星协同调度还需要考虑将任务分配给哪颗卫星去执行，决策空间随着卫星和任务数量的增加呈指数级增长。
3.求解多星协同调度问题的思路主要包括一体规划和分层规划。所述一体规划是指算法在搜索过程中同时决定任务由哪颗卫星去执行以及卫星执行该任务的时间。通常一体规划的调度对象是vtw，往往以0-1决策变量表示卫星执行任务所选的vtw，并求解了一些非敏卫星任务调度问题。对于敏捷卫星又有两种做法：一是在传统非敏卫星处理方法基础上，结合最早开始时间、最小姿态机动角、最高成像质量等选择任务在该vtw的开始时刻点；二是对vtw进行离散化处理。所述分层规划指的是将任务首先分配到单星上，再进行单星任务调度，从而实现了问题层面的分解。但相较于一体规划，分层规划由于无法搜索所有的分配方案，所以容易丢失优质解。
4.在方法层面，精确算法和元启发式算法是求解多星协同调度问题的常用方法。所述精确算法通常是简化卫星任务调度的约束条件，将问题建模成整数规划模型，再通过分支定界、列生成、割平面、动态规划等方法进行求解，其缺点是求解出来的任务规划方案无法满足实际工程需求，且仅适用于小规模的多星协同调度问题，在中大规模问题上不具备优势。所述元启发式算法是基于单个解或种群，不断通过邻域操作或种群进化产生新解或新种群，并有选择性地向优质解空间移动的算法，但其搜索随机性较大，容易出现过早或过晚收敛，同时没有利用问题的先验知识，算法求解效果难以保证。


技术实现要素：

5.本发明的目的在于提供基于数据驱动的多星协同卫星任务调度方法、系统及装置，以解决现有技术中存在的至少一种上述技术问题。
6.第一方面，为解决上述技术问题，本发明提供一种基于数据驱动的多星协同卫星任务调度方法，包括：
7.步骤1、构建卫星任务调度模型，该模型包括集合、决策变量、目标函数及约束；所述集合包括元任务集合、卫星集合、观测时间窗口集合等；所述决策变量包括二元变量；所
述目标函数是最大化任务调度的收益；
8.步骤2、调用卫星任务调度模型，输入元任务数据、卫星数据及观测时间窗口数据，以基于数据驱动的自适应并行搜索方法进行计算：通过分配算子、邻域搜索及频繁模式挖掘，将元任务分配至不同卫星；每个卫星基于所分配的元任务进行单星任务调度，通过破坏算子、排序算子以及快速插入的策略进行邻域搜索，根据禁忌和按照预设概率接受劣解的策略，寻优计算得到单星任务调度的最优解，作为卫星任务调度方案。
9.通过上述步骤，可以通过基于数据驱动的自适应并行搜索方法进行寻优计算，得到多星协同的卫星任务调度方案。
10.在一种可行的实施方式中，所述约束包括唯一性约束、有效性约束、转换时间约束、总存储约束及总电量约束等。
11.在一种可行的实施方式中，所述唯一性约束是指每个任务最多被执行一次。
12.在一种可行的实施方式中，所述有效性约束是指任务必须在可见时间窗口范围内执行，以便保证任务执行的有效性。
13.在一种可行的实施方式中，所述转换时间约束是指同一个卫星执行不同任务需要满足转换时间要求。
14.在一种可行的实施方式中，所述总存储约束是指任务占据的存储容量之和不能超过所在卫星的总存储容量。
15.在一种可行的实施方式中，所述总电量约束是指执行任务所消耗的电量之和不能超过所在卫星的总电量，所述电量包括卫星观测消耗的电量、姿态转换时卫星消耗的固定电量以及转换每一角度消耗的电量。
16.在一种可行的实施方式中，所述步骤2中将元任务分配至不同卫星的方法具体包括：
17.步骤201、根据元任务集合，初始化待分配任务集合；
18.步骤202、当某个卫星满足任务分配条件时，选择分配算子，生成任务分配方案，并记录分配算子，执行步骤203；
19.步骤203、初始化精英解集合及操作算子集合；
20.步骤204、根据概率选择邻域算子，进行邻域搜索，得到新解；
21.步骤205、当所述新解满足接收条件时，则将新解作为精英解，执行步骤206；
22.步骤206、根据先进先出原则，更新精英解集合，并记录邻域算子，更新操作算子集合；
23.步骤207、当满足数据挖掘开始条件时，将精英解集合中的精英解按照收益大小进行降序排列，取前若干个精英解存储至数据挖掘集合；定义卫星任务调度知识，根据该知识对数据挖掘集合中的精英解进行转换，并进行频繁模式挖掘，得到新精英解；
24.步骤208、更新邻域算子的概率；
25.步骤209、对其余卫星迭代执行步骤202，直至遍历所有卫星；
26.步骤210、合并各线程的新精英解得到总新解，更新未被调度的任务集合；
27.步骤211、依次将未被调度的任务集合中的任务插入至总新解中，得到最优解，并更新待分配任务集合；
28.步骤212、输出所述最优解。
29.通过上述步骤，便于将任务以最优的方式分配至各个卫星，以达到降低问题规模，缩减算法搜索空间的目的。
30.在一种可行的实施方式中，所述步骤202中的分配算子包括随机分配算子、卫星位置分配算子、时间窗口分配算子、数量均匀分配算子及历史方案分配算子等：
31.所述随机分配算子，用于将任务随机分配至有观测机会的卫星上；
32.所述卫星位置分配算子，用于将任务分配给具有最小姿态机动角的卫星上，目的是减少卫星的机动时间，从而预留更多的空间安排后续任务；
33.所述时间窗口分配算子，用于根据任务的可见时间窗口，优先将任务分配给可见时间窗口较多的卫星；
34.所述数量均匀分配算子，用于根据卫星已被安排的任务数量，优先将任务分配给任务安排较少的卫星，目的是减少任务的冲突度；
35.所述历史方案分配算子，用于根据所在算法中最近若干次迭代产生的中间解，优先将任务安排至最近若干次迭代未分配任务的卫星，目的是扩大该算法的搜索空间。
36.在一种可行的实施方式中，步骤202中的分配算子通过主线程进行概率更新。
37.在一种可行的实施方式中，所述步骤207中的卫星任务调度知识是指前一个任务与后一个任务的组合，这样可以体现前一个任务对后一个任务执行情况的影响，即二者之间的时间依赖特性，从而便于后序进行转换。
38.在一种可行的实施方式中，所述步骤207中的频繁模式挖掘，是指利用数据挖掘算法，例如fp-growth方法，发现频繁项集，具体包括：
39.步骤2071、将精英解按预设粒度切分成若干子序列，以便保证挖掘频繁项集的效率；
40.步骤2072、基于所述子序列，通过数据挖掘，得到若干个频繁模式；
41.步骤2073、在每个子序列中，对频繁模式按照收益大小进行排序；
42.步骤2074、将每个子序列中收益最大的频繁模式筛选出来，并进行约束检查，组合得到新精英解。
43.通过上述步骤，可以高效得到新精英解，便于后序处理。
44.在一种可行的实施方式中，所述步骤2中单星任务调度的具体方法包括：
45.步骤221、对初始解、目标函数、精英解集合长度、操作算子、精英解集合、操作算子集合、禁忌解集合、禁忌解集合长度、初始温度、降温系数及终止条件，进行初始化；
46.步骤222、当达到终止条件时，根据概率从算子池中选择破坏算子及排序算子，通过快速插入策略，构造邻域解；
47.步骤223、判断邻域解是否在精英解集合中：若是，则根据先进先出原则，更新精英解集合，将破坏算子及排序算子存入操作算子集合，执行步骤225；否则，执行步骤224；
48.步骤224、判断精英解集合的大小是否小于精英解集合长度：若是，则将邻域解存入精英解集合，并将破坏算子及排序算子存入操作算子集合，执行步骤225；否则，基于目标函数的值，找到最劣解，当邻域解对应的目标函数值大于等于最劣解对应的目标函数值时，用邻域解替换最劣解，并将破坏算子及排序算子存入操作算子集合，执行步骤225；
49.步骤225、判断邻域解对应的目标函数值是否大于等于当前解对应的目标函数值：若是，则用邻域解替换当前解，并用插入的任务更新禁忌解集合，执行步骤227；否则，执行
步骤226；
50.步骤226、按照预设概率判断是否接受该邻域解：若是，则用插入的任务更新禁忌解集合；若否，则用删除的任务更新禁忌解集合；
51.步骤227、基于降温系数更新温度；
52.步骤228、输出当前解、精英解集合及操作算子集合。
53.通过上述方法，实现了改进禁忌搜索与模拟退火混合的思路，具体采用“破坏+排序+快速插入”的策略产生邻域解，在整个求解过程中按照先进先出的原则动态更新精英解集合，并记录使用的操作算子作为更新算子使用概率。为防止算法陷入局部最优，还采取了禁忌和以一定概率接受劣解这两种策略。所述禁忌策略是指如果产生的新解被接受，那么本次插入的任务在未来若干代被禁止删除；反之，如果新解没有被接受，那么本次删除的任务在未来若干代被禁止删除。
54.在一种可行的实施方式中，所述步骤222中的破坏算子包括：随机删除、收益较低删除、单位收益删除、转换时间较大删除、时间窗口数量较多删除、冲突度较大删除及最差任务序列删除。
55.在一种可行的实施方式中，所述步骤222中的排序算子包括：随机排序、收益排序、单位收益排序、转换时间排序、时间窗口数量排序、冲突度排序及历史单位收益排序。
56.在一种可行的实施方式中，所述步骤222中破坏算子与排序算子通过主线程之外的其他线程进行概率更新。
57.在一种可行的实施方式中，所述步骤222中构造邻域解的方法具体包括：
58.步骤2221、选择某个破坏算子从当前解中删除若干个任务；
59.步骤2222、将删除的任务和剩余的任务按照某个排序算子进行排序；
60.步骤2223、将候选任务依次快速插入至当前解中，得到邻域解。
61.通过上述步骤，便于快速得到邻域解，从而有利于找到全局最优解。
62.在一种可行的实施方式中，所述步骤2223中快速插入的方法包括：
63.步骤22231、根据当前卫星时间窗口的最晚开始时间，即时间松弛，确定当前解中最后一个任务的最晚开始时间，并逐个倒推当前解中其余每个任务的最晚开始时间；
64.步骤22232、将第n个任务tn预插入至任务t
i-1
与任务ti之间的位置，并根据任务t
i-1
的结束时间紧前安排任务tn；基于任务tn的执行时长，计算任务ti的最早开始时间；判断该最早开始时间是否早于任务ti的最晚开始时间若是，则保留该位置：否则，舍弃该位置：
65.步骤22233、将任务tn预插入至下一个位置，迭代执行步骤22232，直至依次遍历所有剩余位置，得到保留位置集合；
66.步骤22234、计算每个保留位置导致的转换时间增量，选择转换时间增量最小的保留位置，作为最优插入位置。
67.通过上述步骤，便于确定快速插入的位置。
68.第二方面，基于相同的发明构思，本技术还提供了一种基于数据驱动的多星协同卫星任务调度系统，包括数据接收模块、数据处理模块及结果生成模块：
69.所述数据接收模块，用于接收元任务数据、卫星数据及观测时间窗口数据；
70.所述数据处理模块，包括模型单元、任务分配单元、单星任务调度单元：
71.所述模型单元，储存有卫星任务调度模型，包括集合、决策变量、目标函数及约束；所述集合包括元任务集合、卫星集合及观测时间窗口集合；所述决策变量包括二元变量；所述目标函数是最大化任务调度的收益；
72.所述任务分配单元，调用所述卫星任务调度模型，基于所述元任务数据、卫星数据及观测时间窗口数据；选择分配算子，通过邻域搜索及先进先出原则，得到精英解集合；根据卫星任务调度知识对精英解进行转换，并进行频繁模式挖掘，得到新精英解；合并各线程的新精英解得到任务分配的最优解，输出至单星任务调度单元；
73.所述单星任务调度单元，调用所述卫星任务调度模型，基于所述任务分配的最优解，根据概率选择破坏算子、排序算子及快速插入的策略构造邻域解；基于所述邻域解，按照先进先出的原则动态更新精英解集合；基于所述精英解集合，通过禁忌和按照预设概率接受劣解的策略，进行全局寻优，得到单星任务调度的最优解作为卫星任务调度方案；
74.所述结果生成模块，对外发布所述卫星任务调度方案。
75.第三方面，基于相同的发明构思，本技术还提供了一种基于数据驱动的多星协同卫星任务调度装置，包括处理器、存储器及总线，所述存储器存储可由处理器读取的指令及数据，所述处理器用于调用所述存储器中的指令及数据，以执行如上所述的任一一种基于数据驱动的多星协同卫星任务调度方法，所述总线连接各功能部件之间传送信息。
76.采用上述技术方案，本发明具有如下有益效果：
77.本发明提供的基于数据驱动的多星协同卫星任务调度方法、系统及装置，充分利用元启发式算法搜索产生的中间数据，利用人工智能方法挖掘与问题相关的知识，帮助算法优化结果和提升效率；采用双层规划求解思路，主要包括自适应任务分配、并行单星任务调度、数据挖掘、算子自适应更新等步骤，与传统规划方法相比，本方案利用数据挖掘提升单星任务调度的效率，在同等计算代价内显著提升任务分配的频率，从而提高了解的质量。本技术可应用于大规模多星协同卫星任务调度问题，求解质量好，效率高，避免了丢失优质解、过早及过晚收敛问题。
附图说明
78.为了更清楚地说明本发明具体实施方式或现有技术中的技术方案下面将对具体实施方式或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施方式，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
79.图1为背景技术中非敏卫星与敏捷卫星的观测模式对比图；
80.图2为本技术提供的基于数据驱动的自适应并行搜索方法(ddaps)的框架图；
81.图3为本发明实施例提供的基于数据驱动的多星协同卫星任务调度方法流程图；
82.图4为本发明实施例提供的卫星任务调度知识的示例图；
83.图5为本发明实施例提供的频繁模式挖掘的示例图；
84.图6为本发明实施例提供的快速插入策略的示意图；
85.图7为本发明实施例提供的基于数据驱动的多星协同卫星任务调度系统图；
86.图8为本发明实施例提供的卫星轨道示意图；
87.图9为本发明实施例提供的任务区域分布下算法运行时间对比图；
88.图10为本发明实施例提供的任务全球分布下算法运行时间对比图。
具体实施方式
89.下面将结合附图对本发明的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
90.在本发明的描述中，需要说明的是，术语“中心”、“上”、“下”、“左”、“右”、“竖直”、“水平”、“内”、“外”等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此不能理解为对本发明的限制。此外，术语“第一”、“第二”、“第三”仅用于描述目的，而不能理解为指示或暗示相对重要性。
91.为了便于介绍本发明实施例，先就本发明的设计构思进行说明如下：
92.针对背景技术中的技术问题，本技术提出了一种基于数据驱动的自适应并行搜索方法(ddaps)，其结构框架如图2所示，用于求解多星协同卫星任务调度问题。算法整体采用双层规划求解思路，主要包括自适应任务分配、并行单星任务调度、数据挖掘及算子自适应更新。多星协同调度是给定多颗卫星及多个观测任务，在不违反卫星使用、任务执行等约束的前提下，生成卫星执行的任务序列，同时确定任务执行的开始时间和结束时间。多星协同调度已经被证明是np-hard问题，因而不存在多项式时间内求解的精确算法。为了便于研究该问题，本技术基于两点假设：
93.假设1、本技术所指的任务均是指卫星可一次执行的元任务。需要多频次观测的目标、大区域目标、移动目标等复杂任务可通过任务分解、条带划分等方式处理成元任务；
94.假设2、任务在执行过程中不能被抢占。
95.下面结合具体的实施方式对本发明做进一步的解释说明。
96.还需要说明的是，下述具体实施例或具体实施方式，是本发明为进一步解释具体的发明内容而列举的一系列优化的设置方式，而该些设置方式之间均是可以相互结合或者相互关联使用的。
97.实施例一：
98.如图3所示，本实施例提供了一种基于数据驱动的多星协同卫星任务调度方法，包括：
99.步骤1、构建卫星任务调度模型，该模型包括集合、决策变量、目标函数及约束；
100.所述集合包括元任务集合、卫星集合、观测时间窗口集合；
101.所述元任务集合t＝{ti|1≤i≤n}其中，n表示任务数量；ti表示第i个任务；所述任务由四元组(pi，mi，ei，li)组成；其中，pi是任务ti的观测收益值，即优先级，用于评估任务的重要程度；mi是任务ti单位时间所占据的存储容量；ei是任务ti单位时间所消耗的电量；li是任务ti的执行时间；
102.所述卫星集合s＝{si|1≤j≤m}其中，m表示卫星数量；sj表示第j个卫星，所述sj由一个七元组成；其中，ej是第j个卫星的总电量；mj是第j个卫星的总存储容量；γ
jt
，π
jt
，分别表示第j个卫星处于时刻t的滚动、俯仰、偏航角；
p
js
，p
ja
分别表示每次姿态转换时第j个卫星消耗的固定电量及转换每一角度消耗的电量；
103.所述观测时间窗口集合w＝{w
ijk
|1≤i≤n，1≤j≤m，1≤k≤|w
ij
|}其中，w
ijk
表示任务ti在第j个卫星上的第k个可见时间窗口；|w
ij
|表示任务ti在第j个卫星上的可见时间窗口数量；所述w
ijk
由一个三元组(st
ijk
，et
ijk
，d
ijk
)勾成，其中，st
ijk
是时间窗口w
ijk
的开始时间；et
ijk
是时间窗口w
ijk
的结束时间；d
ijk
是时间窗口w
ijk
的时间长度；
104.所述决策变量可以为(x
ijk
，u
ijk
，z
ijk
)其中，所述x
ijk
表示一个二元变量：当任务ti在第j个卫星上的第k个可见时间窗口内执行时，令x
ijk
＝1；否则，令x
ijk
＝0；所述u
ijk
表示任务ti在时间窗口w
ijk
内的开始执行时间；所述z
ijk
表示任务ti在时间窗口w
ijk
内的结束时间，即z
ijk
＝u
ijk
+li；
105.所述目标函数是最大化任务调度的收益，其公式可以为：
[0106][0107]
步骤2、调用卫星任务调度模型，输入元任务数据、卫星数据及观测时间窗口数据，以基于数据驱动的自适应并行搜索方法进行计算：通过分配算子、邻域搜索及频繁模式挖掘，将元任务分配至不同卫星；每个卫星基于所分配的元任务进行单星任务调度，通过破坏算子、排序算子以及快速插入的策略进行邻域搜索，根据禁忌和按照预设概率接受劣解的策略，寻优计算得到单星任务调度的最优解，作为卫星任务调度方案。
[0108]
通过上述步骤，可以通过基于数据驱动的自适应并行搜索方法进行寻优计算，得到多星协同的卫星任务调度方案。
[0109]
进一步地，所述约束包括唯一性约束、有效性约束、转换时间约束、总存储约束及总电量约束。
[0110]
进一步地，所述唯一性约束是指每个任务最多被执行一次，其公式可以为：
[0111][0112]
进一步地，所述有效性约束是指任务必须在可见时间窗口范围内执行，以便保证任务执行的有效性，其公式可以为：
[0113][0114]
进一步地，所述转换时间约束是指同一个卫星执行不同任务需要满足转换时间要求，其公式可以为：
[0115][0116]
其中，表示任务在时间窗口内的开始执行时间；δ(ti，)表示姿态转换时间，其公式可以为：
[0117][0118]
其中，a1，a2，a3，a4表示四个不同姿态的转换速度；δg表示任务与任务之间的姿态角度的差值。
[0119]
进一步地，所述总存储约束是指任务占据的存储容量之和不能超过所在卫星的总存储容量，其公式可以为：
[0120][0121]
进一步地，所述总电量约束是指执行任务所消耗的电量之和不能超过所在卫星的总电量，所述电量包括卫星观测消耗的电量、姿态转换时卫星消耗的固定电量以及转换每一角度消耗的电量，其公式可以为：
[0122][0123]
进一步地，所述步骤2中将元任务分配至不同卫星的方法具体包括：
[0124]
步骤201、根据元任务集合t，初始化待分配任务集合tw；
[0125]
步骤202、当某个卫星满足任务分配条件时，选择分配算子，生成任务分配方案oa，并记录分配算子a，执行步骤203；
[0126]
步骤203、初始化精英解集合u
x
及操作算子集合uo；
[0127]
步骤204、根据概率选择邻域算子n，进行邻域搜索，得到新解n(s
x
)；
[0128]
步骤205、当所述新解n(s
x
)满足接收条件时，则将新解n(s
x
)作为精英解，执行步骤206；
[0129]
步骤206、根据先进先出原则，更新精英解集合u
x
，并记录邻域算子，更新操作算子集合uo；
[0130]
步骤207、当满足数据挖掘开始条件时，将精英解集合u
x
中的精英解按照收益大小进行降序排列，取前nm个精英解存储至数据挖掘集合um；定义卫星任务调度知识，根据该知识对um中的精英解进行转换，并进行频繁模式挖掘，得到新精英解x；
[0131]
步骤208、更新邻域算子的概率；
[0132]
步骤209、对其余卫星迭代执行步骤202，直至遍历所有卫星；
[0133]
步骤210、合并各线程的新精英解得到新解s
x
，更新未被调度的任务集合u
us
；
[0134]
步骤211、依次将u
us
中的任务插入至s
x
中，得到最优解sb，并更新待分配任务集合tw；
[0135]
步骤212、输出所述最优解sb。
[0136]
通过上述步骤，便于将任务以最优的方式分配至各个卫星，以达到降低问题规模，缩减算法搜索空间的目的，其伪代码可以如下：
[0137][0138]
进一步地，所述步骤202中的分配算子包括随机分配算子、卫星位置分配算子、时间窗口分配算子、数量均匀分配算子及历史方案分配算子等：
[0139]
所述随机分配算子，用于将任务随机分配至有观测机会的卫星上；
[0140]
所述卫星位置分配算子，用于将任务分配给具有最小姿态机动角的卫星上，目的是减少卫星的机动时间，从而预留更多的空间安排后续任务；
[0141]
所述时间窗口分配算子，用于根据任务的可见时间窗口，优先将任务分配给可见时间窗口较多的卫星；
[0142]
所述数量均匀分配算子，用于根据卫星已被安排的任务数量，优先将任务分配给任务安排较少的卫星，目的是减少任务的冲突度；
[0143]
所述历史方案分配算子，用于根据所在算法中最近若干次迭代产生的中间解，优先将任务安排至最近若干次迭代未分配任务的卫星，目的是扩大该算法的搜索空间。
[0144]
进一步地，步骤202中的分配算子通过主线程进行概率更新，本轮迭代中，第z个任务分配算子的概率其具体公式可以为：
[0145][0146]
其中，表示在上一轮迭代中第z个任务分配算子的概率；表示上一轮迭代中分配算子所占的比重；
[0147]
表示贡献度：
[0148]
其中，n表示对迭代过程的中间解，按照收益值由大至小进行排序后的前n个解；
表示第z个分配算子贡献的解的个数。
[0149]
通过上述公式，便于计算得到分配算子的概率。
[0150]
进一步地，所述步骤207中的卫星任务调度知识是指前一个任务与后一个任务的组合，这样可以体现前一个任务对后一个任务执行情况的影响，即二者之间的时间依赖特性，从而便于后序进行转换，如图4所示，将每个方案中单独的任务，依据顺序，两两一组进行组合，形成知识。
[0151]
进一步地，所述步骤207中的频繁模式挖掘，是指利用数据挖掘算法，例如fp-growth方法，发现频繁项集，如图5所示，具体包括：
[0152]
步骤2071、将精英解按预设粒度s切分成若干子序列，所述s可以为50，以便保证挖掘频繁项集的效率；
[0153]
步骤2072、基于所述子序列，通过数据挖掘，得到若干个频繁模式；
[0154]
步骤2073、在每个子序列中，对频繁模式按照收益大小进行排序；
[0155]
步骤2074、将每个子序列中收益最大的频繁模式筛选出来，并进行约束检查，组合得到新精英解。
[0156]
所述fp-growth方法属于现有技术，其可以通过建立fp-tree减少对数据库的扫描次数从而高效地发现频繁项集。
[0157]
通过上述步骤，可以高效得到新精英解，便于后序处理。
[0158]
进一步地，所述步骤2中单星任务调度的具体方法包括：
[0159]
步骤221、对初始解x、目标函数f(x)、精英解集合长度k、操作算子o、精英解集合u
x
、操作算子集合uo、禁忌解集合u
t
、禁忌解集合长度t、初始温度t
init
、降温系数c及终止条件，进行初始化；
[0160]
步骤222、当达到终止条件时，根据概率从算子池中选择破坏算子r及排序算子i，通过快速插入策略，构造邻域解x
′
；
[0161]
步骤223、判断邻域解x
′
是否在精英解集合u
x
中：若是，则根据先进先出原则，更新精英解集合u
x
，将破坏算子r及排序算子i存入操作算子集合uo，执行步骤225；否则，执行步骤224；
[0162]
步骤224、判断精英解集合u
x
的大小是否小于精英解集合长度k：若是，则将邻域解x
′
存入精英解集合u
x
，并将破坏算子r及排序算子i存入操作算子集合uo，执行步骤225；否则，基于目标函数f(x)的值，找到最劣解x
worst
当邻域解x
′
对应的目标函数值f(x
′
)大于等于最劣解对应的目标函数值f(x
worst
)时，用邻域解x
′
替换最劣解x
worst
并将破坏算子r及排序算子i存入操作算子集合uo，执行步骤225；
[0163]
步骤225、判断邻域解x
′
对应的目标函数值f(x
′
)是否大于等于当前解对应的目标函数值：若是，则用邻域解x
′
替换当前解，并用插入的任务更新禁忌解集合u
t
，执行步骤227；否则，执行步骤226；
[0164]
步骤226、按照预设概率判断是否接受该邻域解x
′
：若是，则用插入的任务更新禁忌解集合u
t
；若否，则用删除的任务更新禁忌解集合u
t
；
[0165]
步骤227、通过降温系数c及温度公式t＝t*c，更新温度；
[0166]
步骤228、输出当前解x、精英解集合u
x
及操作算子集合uo。
[0167]
通过上述方法，实现了改进禁忌搜索与模拟退火混合的思路，具体采用“破坏+排序+快速插入”的策略产生邻域解，在整个求解过程中按照先进先出的原则动态更新精英解集合，并记录使用的操作算子作为更新算子使用概率。为防止算法陷入局部最优，还采取了禁忌和以一定概率接受劣解这两种策略。所述禁忌策略是指如果产生的新解被接受，那么本次插入的任务在未来若干代被禁止删除；反之，如果新解没有被接受，那么本次删除的任务在未来若干代被禁止删除。其伪代码可以如下：
[0168][0169]
进一步地，所述步骤222中的破坏算子包括：随机删除、收益较低删除、单位收益删除、转换时间较大删除、时间窗口数量较多删除、冲突度较大删除及最差任务序列删除。不同破坏算子将影响算法的搜索性能，其时间复杂度如下表所示：
[0170]
破坏算子时间复杂度随机删除o(n)收益较低删除o(nlogn)单位收益删除o(nlogn)转换时间较大删除o(nlogn)时间窗口数量较多删除o(nlogn)
冲突度较大删除o(nlogn)最差任务序列删除o(nlogn)
[0171]
进一步地，所述步骤222中的排序算子包括：随机排序、收益排序、单位收益排序、转换时间排序、时间窗口数量排序、冲突度排序及历史单位收益排序。不同排序算子将影响算法的搜索性能，其时间复杂度如下表所示：
[0172]
排序算子时间复杂度随机排序o(n)收益排序o(nlogn)单位收益排序o(nlogn)转换时间排序o(nlogn)时间窗口数量排序o(nlogn)冲突度排序o(nlogn)历史单位收益排序o(nlogn)
[0173]
进一步地，所述步骤222中破坏算子与排序算子通过主线程之外的其他线程进行概率更新，本轮迭代中，第i个破坏算子的概率及第j个排序算子的概率具体公式分别可以为：
[0174][0175][0176]
其中，表示上一轮迭代中第i个破坏算子的概率；表示上一轮迭代中第j个排序算子的概率；表示上一轮迭代中破坏算子和排序算子所占的比重；表示本轮迭代中第i个破坏算子的贡献度；表示本轮迭代中j个排序算子的贡献度；
[0177]
所述的具体公式可以为：
[0178][0179]
其中，num
th
表示在线程th中，精英解集合u
th
中精英解的数量；表示第i个破坏算子贡献的精英解数量；
[0180]
所述的具体公式可以为：
[0181][0182]
其中，表示第j个排序算子贡献的精英解数量；
[0183]
通过上述公式，便于得到破坏算子和排序算子的概率。
[0184]
进一步地，所述步骤222中构造邻域解的方法包括：
[0185]
步骤2221、选择某个破坏算子从当前解中删除若干个任务；
[0186]
步骤2222、将删除的任务和剩余的任务按照某个排序算子进行排序；
[0187]
步骤2223、将候选任务依次快速插入至当前解中，得到邻域解。
[0188]
通过上述步骤，便于快速得到邻域解，从而有利于找到全局最优解。
[0189]
进一步地，如图6所示，所述步骤2223中快速插入的方法包括：
[0190]
步骤22231、根据当前卫星时间窗口的最晚开始时间，即时间松弛，确定当前解中最后一个任务的最晚开始时间，并逐个倒推当前解中其余每个任务的最晚开始时间，例如第i个任务的最晚开始时间的具体公式可以为：
[0191][0192]
其中，m表示当前解中任务的总数；ti表示第i个任务；eti表示任务ti的理论最晚开始时间，由时间窗口的最晚开始时间决定；li表示任务ti的执行时长；transitiontime(ti，t
i-1
)示任务ti与任务t
i-1
之间的转换时间；
[0193]
步骤22232、将第n个任务tn预插入至任务t
i-1
与任务ti之间的位置，并根据任务t
i-1
的结束时间紧前安排任务tn；基于任务tn的执行时长，计算任务ti的最早开始时间；判断该最早开始时间是否早于任务ti的最晚开始时间若是，则保留该位置；否则，舍弃该位置；
[0194]
步骤22233、将任务tn预插入至下一个位置，迭代执行步骤22232，直至依次遍历所有剩余位置，得到保留位置集合；
[0195]
步骤22234、计算每个保留位置导致的转换时间增量δt，具体公式可以为：
[0196]
δt＝transitiontime(tn，t
i-1
)+transitiontime(ti，tn)-transitiontime(ti，t
i-1
)
[0197]
选择转换时间增量δt最小的保留位置，作为最优插入位置。
[0198]
通过上述步骤，便于确定快速插入的位置。
[0199]
实施例二：
[0200]
如图7所示，本实施例提供了一种基于数据驱动的多星协同卫星任务调度系统，包括数据接收模块、数据处理模块及结果生成模块：
[0201]
所述数据接收模块，用于接收元任务数据、卫星数据及观测时间窗口数据；
[0202]
所述数据处理模块，包括模型单元、任务分配单元、单星任务调度单元：
[0203]
所述模型单元，储存有卫星任务调度模型，包括集合、决策变量、目标函数及约束；所述集合包括元任务集合、卫星集合及观测时间窗口集合；所述决策变量包括二元变量；所述目标函数是最大化任务调度的收益；所述约束包括唯一性约束、有效性约束、转换时间约束、总存储约束及总电量约束；
[0204]
所述任务分配单元，调用所述卫星任务调度模型，基于所述元任务数据、卫星数据及观测时间窗口数据；选择分配算子，通过邻域搜索及先进先出原则，得到精英解集合；根据卫星任务调度知识对精英解进行转换，并进行频繁模式挖掘，得到新精英解；合并各线程的新精英解得到任务分配的最优解，输出至单星任务调度单元；所述分配算子包括随机分
配算子、卫星位置分配算子、时间窗口分配算子、数量均匀分配算子及历史方案分配算子；
[0205]
所述单星任务调度单元，调用所述卫星任务调度模型，基于所述任务分配的最优解，根据概率选择破坏算子、排序算子及快速插入的策略构造邻域解；基于所述邻域解，按照先进先出的原则动态更新精英解集合；基于所述精英解集合，通过禁忌和按照预设概率接受劣解的策略，进行全局寻优，得到单星任务调度的最优解作为卫星任务调度方案；
[0206]
所述结果生成模块，对外发布所述卫星任务调度方案。
[0207]
实施例三：
[0208]
本实施例提供了一种基于数据驱动的多星协同卫星任务调度装置，包括处理器、存储器及总线，所述存储器存储可由处理器读取的指令及数据，所述处理器用于调用所述存储器中的指令及数据，以执行如上所述的任一一种基于数据驱动的多星协同卫星任务调度方法，所述总线连接各功能部件之间传送信息。
[0209]
本方案在又一种实施方式下，可以通过设备的方式来实现，该设备可以包括执行上述各个实施方式中各个或几个步骤的相应模块。模块可以是专门被配置为执行相应步骤的一个或多个硬件模块、或者由被配置为执行相应步骤的处理器来实现、或者存储在计算机可读介质内用于由处理器来实现、或者通过某种组合来实现。
[0210]
处理器执行上文所描述的各个方法和处理。例如，本方案中的方法实施方式可以被实现为软件程序，其被有形地包含于机器可读介质，例如存储器。在一些实施方式中，软件程序的部分或者全部可以经由存储器和/或通信接口而被载入和/或安装。当软件程序加载到存储器并由处理器执行时，可以执行上文描述的方法中的一个或多个步骤。备选地，在其它实施方式中，处理器可以通过其他任何适当的方式(例如，借助于固件)而被配置为执行上述方法之一。
[0211]
该设备可以利用总线架构来实现。总线架构可以包括任何数量的互连总线和桥接器，这取决于硬件的特定应用和总体设计约束。总线将包括一个或多个处理器、存储器和/或硬件模块的各种电路连接到一起。总线还可以将诸如外围设备、电压调节器、功率管理电路、外部天线等的各种其它电路连接。
[0212]
总线可以是工业标准体系结构(isa，i ndustry standard architecture)总线、外部设备互连(pci，peripheral component)总线或扩展工业标准体系结构(eisa，extended industry standard component)总线等，总线可以分为地址总线、数据总线、控制总线等。
[0213]
实施例四：
[0214]
通过设计多个多星调度场景实验，验证本发明基于数据驱动的自适应并行搜索方法(ddaps)的有效性，实验环境如下：
[0215]
编程语言：python 3.7.6；
[0216]
运行环境：intel(r)core(tm)i7-8700cpu 3.30ghz；
[0217]
操作系统：windows server 2010；
[0218]
内存容量：16gb。
[0219]
调度周期：2013/04/20/00：00：00到2013/04/20/23：59：59；
[0220]
轨道数量：15～16；
[0221]
卫星轨道六根数(半长轴a、偏心率e、倾角i、近地点角ω、升交点赤经raan和真近
点角m)，如下表所示：
[0222]
卫星编号aeiωraanm17200km0.00062796.5760175.720.07527200km0.00062796.5760145.7230.07537200km0.00062796.5760115.7230.07547200km0.00062796.576085.7290.07557200km0.00062796.576055.72120.075
[0223]
卫星仿真轨道图，如图8所示；
[0224]
卫星其余属性参数：
[0225]
m＝2400，e＝2400，a1＝1.5，a2＝2，a3＝2.5，a4＝3，
[0226]ei
＝1，p
js
＝2，p
ja
＝1
[0227]
任务分类：区域分布和全球分布；所述区域分布是指在中国境内随机生成任务，其中任务数量从100到1000，步长为100，卫星数量从2到5，共40个算例；所述全球分布是指在全球范围内随机生成任务，任务数量从400到2000，步长为400，卫星数量从2到5，共20个算例；
[0228]
ddaps算法最大迭代次数：1000；其中每运行100次调用一次任务分配，因此任务分配的次数为10；
[0229]
当启用单线程求解单星调度问题时，各线程算法的终止条件：运行次数达到100，但如果连续30次解都没有得到提升，那么算法也会终止。
[0230]
禁忌模拟退火混合算法的具体参数值设置如下：
[0231]
删除任务的百分比：10％；
[0232]
禁忌列表长度：10％*|t||t|表示分配给该卫星的任务数量；
[0233]
初始温度：初始方案的收益值；
[0234]
降温系数：1000^(-1/1000)；
[0235]
精英解集合的最大数量：30；
[0236]
数据挖掘开始条件：只有分配到单个卫星的任务数量大于等于100个时，算法才会进行数据挖掘；
[0237]
数据挖掘的参数设置：用于数据挖掘的精英个体数量：10；最小支持度：0.2。
[0238]
实验结果分析：
[0239]
对比算法：基于自适应任务分配的alns方法(a-alns)；基于随机分配的alns方法(r-alns)；基于随机分配的遗传算法(r-ga)；
[0240]
对比指标：收益率，表示为被调度任务的收益与全部任务收益的比值；算法的运行时间；所有实验指标数据均是算法独立运行10次后的平均值。
[0241]
任务区域分布的实验结果，如下表所示：
[0242][0243]
任务全球分布的实验结果，如下表所示：
[0244][0245]
实验结论：通过上述实验结果对比，ddaps在大部分算例上都能取得最优的收益率及最快的运行时间，故相较于其他三个对比算法，优化性能最优。
[0246]
结论分析：ddaps的主循环采用了局部搜索算法的架构，局部搜索算法能够有效地帮助算法寻找优质解；ddaps加入了数据驱动机制，数据驱动机制能够有效利用局部搜索算法产生的中间数据，挖掘任务与任务之间的关联关系，引导算法的搜索方向，提升优化效果及搜索效率；ddaps会定期更新分配算子的选择概率，满足算法对自适应的要求。
[0247]
需要说明的是，当任务规模和卫星数量较小时，ddaps并没有启动数据挖掘，因此不具备优势；当规模不断扩大，ddaps在运行时间上的优势便逐渐明显；
[0248]
例如：
[0249]
当卫星数量：2；任务数量：500、600、700、800、900、1000；共6个场景下时，四种算法的运行时间对比折线图，如图9所示；
[0250]
当卫星数量：2、3、4、5；任务数量：1600、2000；共8个场景下时，四种算法的运行时间对比折线图，如图10所示；
[0251]
综合上述两图，ddaps的运行时间最少，且随着规模的扩大，ddaps的优势更加明显。
[0252]
最后应说明的是：以上各实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述各实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的范围。

技术特征：
1.基于数据驱动的多星协同卫星任务调度方法，其特征在于，包括：步骤1、构建卫星任务调度模型，该模型包括集合、决策变量、目标函数及约束；所述集合包括元任务集合、卫星集合及观测时间窗口集合；所述决策变量包括二元变量；所述目标函数是最大化任务调度的收益；步骤2、调用卫星任务调度模型，输入元任务数据、卫星数据及观测时间窗口数据，以基于数据驱动的自适应并行搜索方法进行计算：通过分配算子、邻域搜索及频繁模式挖掘，将元任务分配至不同卫星；每个卫星基于所分配的元任务进行单星任务调度，通过破坏算子、排序算子以及快速插入的策略进行邻域搜索，根据禁忌和按照预设概率接受劣解的策略，寻优计算得到单星任务调度的最优解，作为卫星任务调度方案。2.根据权利要求1所述的方法，其特征在于，所述约束包括唯一性约束、有效性约束、转换时间约束、总存储约束及总电量约束。3.根据权利要求1所述的方法，其特征在于，所述步骤2中将元任务分配至不同卫星的方法，具体包括：步骤201、根据元任务集合，初始化待分配任务集合；步骤202、当某个卫星满足任务分配条件时，选择分配算子，生成任务分配方案，并记录分配算子，执行步骤203；步骤203、初始化精英解集合及操作算子集合；步骤204、根据概率选择邻域算子，进行邻域搜索，得到新解；步骤205、当所述新解满足接收条件时，则将新解作为精英解；步骤206、根据先进先出原则，更新精英解集合，并记录邻域算子，更新操作算子集合；步骤207、当满足数据挖掘开始条件时，将精英解集合中的精英解按照收益大小进行降序排列，取前若干个精英解存储至数据挖掘集合；定义卫星任务调度知识，根据该知识对数据挖掘集合中的精英解进行转换，并进行频繁模式挖掘，得到新精英解；步骤208、更新邻域算子的概率；步骤209、对其余卫星迭代执行步骤202，直至遍历所有卫星；步骤210、合并各线程的新精英解得到总新解，更新未被调度的任务集合；步骤211、依次将未被调度的任务集合中的任务插入至总新解中，得到最优解，并更新待分配任务集合；步骤212、输出所述最优解。4.根据权利要求3所述的方法，其特征在于，所述步骤202中的分配算子包括随机分配算子、卫星位置分配算子、时间窗口分配算子、数量均匀分配算子及历史方案分配算子。5.根据权利要求3所述的方法，其特征在于，所述步骤207中的卫星任务调度知识是指前一个任务与后一个任务的组合。6.根据权利要求3所述的方法，其特征在于，所述步骤207中的频繁模式挖掘，具体包括：步骤2071、将精英解按预设粒度切分成若干子序列；步骤2072、基于所述子序列，通过数据挖掘，得到若干个频繁模式；步骤2073、在每个子序列中，对频繁模式按照收益大小进行排序；步骤2074、将每个子序列中收益最大的频繁模式筛选出来，并进行约束检查，组合得到
新精英解。7.根据权利要求3所述的方法，其特征在于，所述步骤2中单星任务调度的具体方法包括：步骤221、对初始解、目标函数、精英解集合长度、操作算子、精英解集合、操作算子集合、禁忌解集合、禁忌解集合长度、初始温度、降温系数及终止条件，进行初始化；步骤222、当达到终止条件时，根据概率从算子池中选择破坏算子及排序算子，通过快速插入策略，构造邻域解；步骤223、判断邻域解是否在精英解集合中：若是，则根据先进先出原则，更新精英解集合，将破坏算子及排序算子存入操作算子集合，执行步骤225；否则，执行步骤224；步骤224、判断精英解集合的大小是否小于精英解集合长度：若是，则将邻域解存入精英解集合，并将破坏算子及排序算子存入操作算子集合，执行步骤225；否则，基于目标函数的值，找到最劣解，当邻域解对应的目标函数值大于等于最劣解对应的目标函数值时，用邻域解替换最劣解，并将破坏算子及排序算子存入操作算子集合，执行步骤225；步骤225、判断邻域解对应的目标函数值是否大于等于当前解对应的目标函数值：若是，则用邻域解替换当前解，并用插入的任务更新禁忌解集合，执行步骤227；否则，执行步骤226；步骤226、按照预设概率判断是否接受该邻域解：若是，则用插入的任务更新禁忌解集合；若否，则用删除的任务更新禁忌解集合；步骤227、基于降温系数更新温度；步骤228、输出当前解、精英解集合及操作算子集合。8.根据权利要求7所述的方法，其特征在于，所述步骤222中构造邻域解的方法具体包括：步骤2221、选择某个破坏算子从当前解中删除若干个任务；步骤2222、将删除的任务和剩余的任务按照某个排序算子进行排序；步骤2223、将候选任务依次快速插入至当前解中，得到邻域解。9.基于数据驱动的多星协同卫星任务调度系统，其特征在于，包括数据接收模块、数据处理模块及结果生成模块：所述数据接收模块，用于接收元任务数据、卫星数据及观测时间窗口数据；所述数据处理模块，包括模型单元、任务分配单元、单星任务调度单元：所述模型单元，储存有卫星任务调度模型，包括集合、决策变量、目标函数及约束；所述集合包括元任务集合、卫星集合及观测时间窗口集合；所述决策变量包括二元变量；所述目标函数是最大化任务调度的收益；所述任务分配单元，调用所述卫星任务调度模型，基于所述元任务数据、卫星数据及观测时间窗口数据；选择分配算子，通过邻域搜索及先进先出原则，得到精英解集合；根据卫星任务调度知识对精英解进行转换，并进行频繁模式挖掘，得到新精英解；合并各线程的新精英解得到任务分配的最优解，输出至单星任务调度单元；所述单星任务调度单元，调用所述卫星任务调度模型，基于所述任务分配的最优解，根据概率选择破坏算子、排序算子及快速插入的策略构造邻域解；基于所述邻域解，按照先进先出的原则动态更新精英解集合；基于所述精英解集合，通过禁忌和按照预设概率接受劣
解的策略，进行全局寻优，得到单星任务调度的最优解作为卫星任务调度方案；所述结果生成模块，对外发布所述卫星任务调度方案。10.基于数据驱动的多星协同卫星任务调度装置，其特征在于，包括处理器、存储器及总线，所述存储器存储可由处理器读取的指令及数据，所述处理器用于调用所述存储器中的指令及数据，以执行如权利要求1～8中任一所述的方法，所述总线连接各功能部件之间传送信息。

技术总结
本发明提供了一种基于数据驱动的多星协同卫星任务调度方法、系统及装置，涉及卫星调度技术领域，方法主要包括：构建卫星任务调度模型，该模型包括集合、决策变量、目标函数及约束；调用卫星任务调度模型，输入元任务数据、卫星数据及观测时间窗口数据，以基于数据驱动的自适应并行搜索方法进行寻优计算得到单星任务调度的最优解，作为卫星任务调度方案。本申请采用双层规划求解思路，通过自适应任务分配、并行单星任务调度、数据挖掘、算子自适应更新等手段，提升了多星协同卫星任务调度的效率及质量。及质量。及质量。


技术研发人员：陈宇宁 吴健 薛浚铧 吕济民 何磊 杜永浩 刘晓路 陈盈果 陈英武 闫俊刚 姚锋 张忠山 王涛 沈大勇
受保护的技术使用者：中国人民解放军国防科技大学
技术研发日：2023.06.02
技术公布日：2023/8/16