本书创造性地提出一种面向多敏捷卫星任务调度的数据驱动双层优化算法。本书从卫星任务管控实际业务需求出发，分析卫星任务调度问题的特点，针对其中的多星任务分配问题和单星任务调度问题展开讨论，构建卫星任务调度问题的双层优化模型。面向单星任务调度、多星常规任务调度、多星应急任务调度等问题，设计一种融合机器学习与传统优化方法的数据驱动优化算法，并通过大量实验证明所设计算法的有效性。本书的研究成果可以拓展大规模卫星任务调度、卫星应急任务调度等问题的研究思路，也可进一步改造应用于北斗导航、深空探测以及超低轨通遥一体卫星星座等重大专项工程，具有一定的实际意义。

目录
第1章绪论1
1.1研究背景与意义1
1.1.1研究背景1
1.1.2研究意义3
1.2卫星任务调度模型研究现状4
1.2.1整数规划模型4
1.2.2约束满足问题模型5
1.2.3经典运筹学模型5
1.3卫星任务调度算法研究现状6
1.3.1启发式规则算法7
1.3.2精确求解算法7
1.3.3元启发式算法8
1.3.4机器学习算法12
1.4数据驱动优化算法研究现状13
1.5主要工作与创新点15
1.5.1研究内容与组织结构15
1.5.2主要创新点18
第2章卫星任务调度问题分析与数据驱动双层优化算法框架设计20
2.1卫星任务调度实际业务流程20
2.2卫星任务调度问题分析与数学模型23
2.2.1敏捷卫星时间依赖特点分析23
2.2.2卫星任务调度问题分解26
2.2.3一体优化框架与双层优化框架26
2.2.4卫星任务调度数学模型30
2.3面向卫星任务调度问题的数据驱动双层优化算法框架设计34
2.3.1元启发式算法特点分析35
2.3.2面向卫星任务调度问题的数据驱动双层优化算法框架37
2.4本章小结42
第3章面向单颗敏捷卫星任务调度问题的数据驱动优化算法44
3.1单星调度问题建模44
3.1.1问题假设44
3.1.2数学模型45
3.2数据挖掘与元启发式结合的算法设计思路47
3.3基于频繁模式的自适应并行搜索算法48
3.3.1算法框架48
3.3.2初始解构造策略50
3.3.3并行搜索策略50
3.3.4算法算子自适应选择策略57
3.3.5基于频繁模式的新解构造策略59
3.4基于频繁模式的自适应模因算法61
3.4.1算法框架61
3.4.2子代群体产生策略63
3.4.3基于频繁模式的新解构造与提升策略64
3.4.4基于种群相似度的个体调整与种群更新策略64
3.5实验分析66
3.5.1实验场景设计66
3.5.2FPAPSA实验分析68
3.5.3FPAMA实验分析78
3.6本章小结85
第4章面向多星常规任务调度问题的数据驱动双层优化算法86
4.1多星常规任务调度问题建模86
4.1.1参数定义86
4.1.2数学模型87
4.2求解算法88
4.2.1算法框架89
4.2.2基于DRL的任务分配策略自适应选择机制91
4.2.3基于频繁模式的自适应局部搜索算法98
4.3实验分析99
4.3.1实验场景设计99
4.3.2对比算法及参数设置100
4.3.3实验结果102
4.4本章小结107
第5章面向多星应急任务调度问题的数据驱动双层优化算法108
5.1问题描述与难点分析108
5.2多星应急任务调度问题建模110
5.2.1参数定义110
5.2.2数学模型110
5.3求解算法112
5.3.1基于预设窗口的RRSM113
5.3.2SASA115
5.3.3STFAM118
5.4实验分析120
5.4.1实验场景设计120
5.4.2对比算法及参数设置122
5.4.3实验结果123
5.5本章小结136
第6章结论与展望138
6.1结论138
6.2展望140
参考文献142
附录缩写词列表154

前言

随着卫星技术的不断变革，成像卫星在地形勘探、灾难预警以及军事情报获取等方面发挥着越来越重要的作用。近年来，星上硬件水平不断发展、大型星座不断建设以及应用需求不断提出，为当前的卫星任务调度算法提出了新的挑战。首先，新一代具有高姿态机动能力的敏捷卫星得到大范围应用。与非敏捷卫星相比，敏捷卫星具有时间依赖的特点，其任务调度问题决策维度进一步提升，单体复杂度提高。其次，任务数量与卫星规模不断增长，问题解空间规模进一步增大。加之应急需求频繁发生，对算法求解时效性要求变高。由于一体优化框架需要遍历问题全部解空间，一旦问题规模扩大，算法在求解质量与求解速度间的矛盾将更加突出。双层优化框架能够将复杂问题分解成具有层级关系的上下两层子问题，实现问题层面的“分治降维”。然而，该框架会限制算法探索全部解空间，从而无法保证解的优质性。为有效降低双层优化框架对算法的影响，并统筹好我国在轨卫星和管控资源，本书开展面向多敏捷卫星任务调度的数据驱动双层优化算法研究，旨在通过数据驱动的方式来提升算法的求解性能，具体内容和创新点如下。
（1） 设计了面向卫星任务调度问题的数据驱动双层优化算法框架。在对实际业务流程详细梳理的基础上，分析了卫星任务调度中核心问题，即“多星任务分配和单星任务调度”的特点、输入以及输出；重点介绍了两种常见求解框架，即“一体优化和双层优化”，分析了两种框架的优势和劣势。鉴于当前卫星任务调度问题呈现出的大规模和不确定性的特点，明确了双层优化的算法框架。其中，多星任务分配作为上层领导者，单星任务调度作为下层从属者，据此给出问题的双层优化模型、目标函数以及约束条件。针对双层优化框架下，元启发式算法求解性能受限的现实情况，利用元启发式算法优秀的扩展性和兼容性，创新性地提出了“机器学习+元启发式”的数据驱动优化算法思路，进一步设计了面向卫星任务调度问题的数据驱动双层优化算法框架，为后续问题求解指明具体方向。
（2） 面向单颗敏捷卫星任务调度问题，提出了一种数据挖掘与元启发式结合的算法设计思路。高效求解单星任务调度问题，是能够良好解决多星常规任务调度问题和多星应急任务调度问题的关键。考虑单星任务调度问题的NPhard特点和元启发式算法求解质量差、速度慢以及效果不稳定的缺点，提出了一种数据挖掘和元启发式结合的算法设计思路。该思路是结合敏捷卫星时间依赖的特点，利用数据挖掘从元启发式算法前期产生的高质量解中提取知识（即任务执行的次序关系），并利用其构造新解，进一步引导元启发式算法后续开展有针对性的搜索。为验证该思路，分别在局部搜索算法和进化算法框架中加入了频繁模式挖掘，提出了基于频繁模式的自适应并行搜索算法和基于频繁模式的自适应模因算法。前者依次设计了初始解构造策略、并行搜索策略、算法算子自适应选择策略以及基于频繁模式的新解构造策略。后者则设计了子代群体产生策略、基于频繁模式的新解构造与提升策略以及基于种群相似度的个体调整与种群更新策略。实验结果表明，上述两种算法均能够在求解质量、求解时间以及稳定性方面优于当前算法。
（3） 面向多星常规任务调度问题，设计了一种基于强化学习的自适应搜索算法。求解多星常规任务调度问题的主要难点之一是解空间随着任务数量和卫星规模增长出现组合爆炸。基于我国现行集中管控模式下，卫星管理部门长期面临大批量任务需求和数百颗卫星管控压力的现实情况，设计了一种基于强化学习的自适应搜索算法。首先，面向上层任务分配问题，根据问题领域知识，设计了多种任务分配策略，将选择任务分配策略处理成时序决策问题，提出了一种基于深度强化学习的分配策略自适应选择机制。该机制采用深度Q网络（deep Q network，DQN）模型决策下一轮交互所要选择的任务分配策略，既保证算法低复杂度，又提升了任务分配方案的质量。其次，下层继承了前述单星调度算法的研究，将“算法并行”改造为“问题并行”，提出了基于频繁模式的自适应局部搜索算法。最后，设计了多个实验场景，涵盖小规模、中等规模和大规模。值得注意的是，本书所设计的大规模场景是迄今为止在敏捷卫星任务调度领域公开资料中规模最大的实验算例。实验结果表明，算法在求解质量和求解速度方面具有显著的优势。
（4） 面向多星应急任务调度问题，设计了一种基于预设窗口的滚动重调度机制和基于可调度性预测的自适应搜索算法。针对应急任务偶发性和执行紧迫性的特点以及常规调度算法时效性较低的实际情况，首先，界定了多星应急任务调度问题的定义、输入以及输出，分析了各类突发事件对求解问题的影响，总结了应急任务调度算法设计应当围绕求解速度、求解质量以及与原调度方案的差异性这三方面展开。其次，设计了一种基于预设窗口的滚动重调度机制，从时间维度将长周期应急任务调度问题切分成短周期任务调度问题，缩减了问题规模，又最大限度维持了原方案。再次，设计了基于可调度性预测的自适应搜索算法。其中，考虑到应急任务执行紧迫性的特点，上层任务分配与下层单星调度被设计成一次交互，利用历史数据训练可调度性预测模型，实现任务与卫星的快速匹配。最后，围绕引发任务数量和卫星规模变化的两大类突发事件，设计了多种应急调度场景，大量实验结果表明，算法在多星应急任务调度问题上具有良好的适应性。
本书是作者在西安电子科技大学工作和在国防科技大学求学期间完成的。本书的完成离不开作者导师姚锋研究员、邢立宁研究员的悉心指导，以及陈英武、刘晓路、陈盈果、陈宇宁、吕济民、张忠山、王涛、沈大勇、何磊、杜永浩、闫俊刚、何永明老师的大力支持。同时，本书的完成也离不开运筹学领域学者们的帮助，正因为他们丰硕的成果，作者才得以站在巨人的肩膀上完成这本专著的撰写。在此，向所有给予作者指导、帮助和启发的各位老师与学者表示衷心的感谢。
由于水平有限，书中难免存在不妥之处，欢迎专家学者批评指正，并提出宝贵意见，作者将不胜感激。

吴健
2026年5月