基于遗传算法的Tiling 覆盖策略天文卫星任务规划*

徐子羚 刘玉荣 冯准

1(中国科学院国家空间科学中心 北京 100190)

2(中国科学院大学 北京 100049)

0 引言

面向天文观测的空间科学卫星是对目标天体或天区进行天文观测的重要手段。空间的机遇目标（Target of Opportunity，ToO），例如引力波（Gravitational Wave，GW）、γ 射线暴（Gamma Ray Burst，GRB）等是天文观测的重要现象，包含着物理发展新规律。典型的ToO 是一个瞬态目标，发现后必须尽快对其进行观测，否则其亮度会降至可检测的极限以下。某些瞬态目标衰减相对较慢，在几天或几周内保持可观测状态，例如超新星和新星。某些目标必须在发现后的数小时内观测到，例如γ 射线暴会快速消失。当正在衰减的目标仍保持足够大的亮度时，可以从光谱数据变化中获得更高的信噪比，所以对这些机遇目标观测响应时间的小幅改进可能会获得极大的科学观测收益。

机遇目标观测是多信使天文学（Multi-messenger Astronomy）的重要手段。2017年10月16日（美国东部时间10月16日10:00 LT）美国国家科学基金会召开新闻发布会，美国引力波探测器LIGO 和意大利引力波探测器处女座Virgo 于2017年8月17日共同探测到引力波事件GW170817，在该事件发生的随后几秒内，NASA 的Fermi 卫星和ESA 的INTEGRAL 卫星均探测到一个极弱的短时γ 射线暴GRB170817 A。这是第一次使用引力波和电磁波同时观测到同一个天体物理事件，标志着多信使天文学时代的开始[1]。引力波事件发生时通常所在的天区有几十到几百平方度，对这样较大天区的机遇目标观测一般根据天文望远镜视场的大小划分为小的天区，Tiling 覆盖策略是对天区划分的常用方法。Tiling 覆盖策略是指针对空间天文卫星的任务目标，根据载荷视场大小、观测角和视场形状，设计单位网格Tile，对被观测天区的轮廓进行覆盖，并根据概率密度函数积分计算等方式对每个Tile 赋予优先级。划分结果产生Tile 编号、优先级和天球坐标等信息。

机遇目标观测相对于常规观测是无法预先安排的观测对象，这是因为观测目标未知且目标坐标未知，或者已知目标具有行为不可预测的可变行为，所以机遇目标观测是事先不知道确切目标、时间、坐标或仪器配置详细信息的观测。机遇目标观测的时效性要求高，当ToO 出现时观测系统要快速响应，制定有效的观测队列方案，因此空间天文卫星机遇目标任务规划是空间天文卫星运行控制系统的重要工作。Tiling 覆盖策略天文卫星机遇目标任务规划的目的是针对一个天区观测目标，快速安排观测任务，解决科学观测需求与卫星系统资源约束的矛盾，制定合理任务执行观测方案，更高效地利用资源，得到更大的科学观测收益。

目前，卫星任务规划研究中面向基于机遇目标天文观测任务规划的研究很少。机遇目标观测的规划可以借鉴常规天文观测规划方法。NASA 发射了多颗空间天文卫星：哈勃望远镜（Hubble Space Telescope，HST），雨燕卫星（Swift Gamma-Ray Burst Mission，Swift）等。开发使用了多个任务规划系统，例如SPIKE 调度规划系统和TAKO 规划系统，采用约束满足问题（Constraint Satisfaction Problem，CSP）、神经网络（Neural Network，NN）以及N体模拟（N-body）等方法求解规划问题[2-4]。ESA 同样发射了多颗空间天文卫星，如XMM-Newton 和Integral 等，ESA 在高级规划方案APSI（Advanced Planning and Schedule Initiative）框架上开发了规划系统MrSPOCK、AIMS、XMAS，采用遗传算法（Genetic Algorithms，GA）和局部搜索算法（Local Search Algorithm），用一个通用的方法说明任务、时间和资源的约束，并结合爬山、禁忌搜索、模拟退火等算法思想解决任务规划问题[5-8]。中国发射了硬X 射线调制望远镜卫星（HXMT），采用贪婪算法、遗传算法等方法求解规划问题。Liu等[9]提出了采用多目标遗传算法对卫星巡天扫描任务进行智能规划的模型。Wu等[10]在研究天文观测卫星的任务规划问题时，建立了多目标任务规划模型，并基于带精英策略的快速非支配排序遗传算法（NSGA-II）设计了并行的基因组编码方式，有效解决了天文观测类卫星不同规模的任务规划问题。Liu等[11]在原有多目标遗传算法的基础上，设计了基于观测窗口序列的多目标遗传算法，改进了遗传算法的编码能力，得到每个观测任务的观测窗口序列，提高规划结果的灵活性和适用性。Han等[12]针对小卫星星群任务运行特点，采用改进型遗传算法，引入资源随机分配的解码策略及精英保留策略，保证了算法的全局收敛性。Liu等[13]研究了基于规则的启发式算法和遗传算法求解任务规划问题，并设计一种动态插入机遇目标任务的重规划算法。Long等[14]将遗传算法与模拟退火算法相结合，应用于低轨观测卫星任务规划工具的开发。Mao等[15]针对多星多任务的规划问题，提出一种基于关键路径遗传算法，具有良好的全局搜索能力和稳定性。

以上研究表明，采用智能优化算法在求解卫星任务规划问题是可行的方案。现有的任务规划模型和方法不能直接用于Tiling 覆盖策略天文卫星目标观测规划问题。观测目标在被观测天区上分布不均匀或出现概率不均匀，望远镜或仪器的每次观测只能覆盖一块观测区域（Tile），因此在制定观测计划过程中，一个优化的Tiling 方案需要在保证完备性的同时缩短观测时间。由于机遇目标的可观测时间宝贵，并且每个Tile 的增加都会增加观测的时间成本，对于预定观测天区的覆盖率以及整体的观测效率要求更高。本文以基于Tiling 策略的天文卫星机遇目标观测规划问题为研究对象，建立任务规划数学模型，设计算法 求解该问题，并进行仿真实验和结果分析。

1 目标任务规划问题建模

1.1 问题描述

Tiling 覆盖策略的天文卫星机遇目标任务规划问题可以简要描述为，根据科学的观测需求，结合星地资源以及环境约束进行约束检验，根据时间窗口、卫星姿态、观测时长等约束，规划对Tile 的合理观测方案，生成高效可行的卫星工作计划。其中观测需求来源通常是由科学团队提出的机遇目标，包括引力波、γ 暴等。观测目标范围是一片天区，根据Tiling策略进行天区划分得到一组Tile，其中每一个Tile 通过概率密度函数求解出各自的优先级。本文重点在于规划算法的设计，因此Tile 及其时间窗口等均由预处 理求解得出，直接作为输入使用。

1.2 问题假设

天文观测是复杂的系统工程，实际天文卫星机遇目标任务规划涉及卫星平台、地面站、运行轨道、时间窗口、任务类型等一系列因素，是NP-hard 问题。本文研究Tiling 覆盖策略的天文卫星机遇目标任务规划问题的基本规划方法，对于复杂问题提出建模假设，这些假设不影响研究算法的效果。结合实际任务规划问题做出的具体假设如下。

（1）假设卫星上多个有效载荷等效为一个有效载荷。多个工作模式不同的有效载荷等效为一个有效载荷的多个工作模式。在卫星运行过程中，多个载荷配合工作，本假设符合天文卫星的一般运控模式。

（2）假设卫星资源和地面资源满足任务规划需求。包括电源电量、存储器容量以及卫星和地面站的硬件条件等满足规划的需要，不考虑资源或故障对算法的影响。常规情况下，卫星资源能够保障卫星在轨按照正常模式开展科学观测。

（3）假设卫星调姿需要的时间与调姿角度线性相关，调姿需要的能量与调姿角度线性相关。

（4）假设卫星观测的数据量与观测时长成正比。

（5）假设同一时间段内卫星只能执行一项观测任务，一项观测任务至多执行一次且在执行过程中不被其 他任务抢占或中断执行。

1.3 数学模型

1.3.1 数学变量

为了描述Tiling 覆盖策略天文卫星机遇目标任务 规划问题，定义相关变量及符号（见表1）。

表1 数学模型中的变量定义Table 1 Parameters definition

1.3.2 变量定义

定义1可视时间窗口W。Wt为Tilet的可视时间窗口集合，表示可以被观测的时间段。∀wt∈Wt，其中，为Tilet的可视时间窗口集合中第k个时间窗口，为第k个时间窗口的开始时间，为第k个时间窗口的结束时间。

定义2观测任务目标Tile 集合T。∀t∈T。其中，t≡〈Pt,Dt,St〉，Pt表示观测坐标，Dt表示观测时长，St表示优先级。

定义3规划方案R。∀r∈R。其中rt≡〈Et,Nt,Ot,Θt,Lt,ϕt,∆t〉。Et表示Tilet的规划判决结果，Et为1 表示可规划，0 表示未规划。Nt表示Tilet的执行顺序。Ot表示Tilet的观测时间窗口集合，其中，为Tilet观测时间窗口集合ot中第n个观测时间窗口，为第n个观测窗口的开始时间，为第n个观测窗口的结束时间。Lt为由前一目标到观测当前Tilet目标需要调姿的距离。Θt表示Tilet的调姿时间窗口集合，∀θt∈Θt，ϕt表示由前一目标到观测当前Tilet目标需要调姿的角度。∆t表示Tilet的等待时间窗 口集合，

1.3.3 约束分析

约束1每个Tile 的观测时长约束，即每个Tile的观测总时长必须满足该Tile 观测时长需求Dt，

约束2任务冲突约束，卫星在同一时刻只能执行一个观测任务，每两个Tile 之间的观测区间不能冲突，即

约束3规划时间约束，规划结果占有的时间必须 能容纳在规划起止时间段内，即

1.3.4 规划模型

基于以上定义和约束，模型描述如下：给定一颗卫星S，观测天区Z。天区Z的Tiling 结果为观测任务目标集合T。任务目标集合T的每个任务目标即每个Tile 都有各自的位置、观测需求时长和优先级，任务目标集合T每个任务目标的数据已经由预处理求解出。

给定可视时间窗口集合W，可视时间窗口集合W的每个可观测时间段都有各自的起始时间和结束时间。每个任务目标t必须在该目标对应可观测时间窗口集合Wt内执行。切换任务目标需要调姿，调姿需要的时间与调姿角度线性相关，调姿需要的能量与调姿角度线性相关。

机遇目标天文观测任务的基本需求包括：ToO观测需要快速响应，需要考虑目标Tile 的优先级；节约天文卫星的能源，需要考虑尽可能短的路径；为了延长天文卫星的寿命，需要考虑减少天文卫星姿态的频繁调整。据此，建立模型多目标优化问题的目标函数如下。

（1）优先级。优先级以Tile 本身的优先级以及其被安排顺序的乘积表示，该值越小表明优先级高的tile 越早被安排，即

（2）总距离。总距离由被规划的相邻两个tile 之间调姿的距离累加和表示，该值越小则表明总体规划距离越短，即

（3）调姿满足率。调姿满足率用来评价调姿角度约束的满足程度，该值越小表示总体调姿对于满足调姿角度约束的程度越高。

调姿角度约束判断函数为

基于上述考虑，TPA算法（ToO Planning Algorithm）的目标函数为

多目标优化在某方面实现最优，大概率会导致其他方面性能的下降。可以根据实际任务需求改变目标函数的加权参数λpri和λdis，从而改变优化方向的权重 以取得更好的平衡。

2 算法设计

由于该问题是一个NP-hard 问题，问题复杂度随规模呈指数增加，求解收敛难度增加。遗传算法作为一个全局搜索算法，能够在整个可行解域开展搜索，同时组合优化问题中，可行解通常是有限但是非常大的，因此遗传算法特别适于求解组合优化问题。本文基 于遗传算法设计多目标优化任务规划算法TPA。

2.1 算法描述

（1）染色体编码与解码。根据机遇目标任务规划特点采用整数编码方式，每条染色体由待规划的Task任务组成，Task任务下标数字表示任务编号，对应任务在序列中执行的顺序。每个Task由坐标参数赤经和赤纬（RA，DEC）、观测时长、优先级分数组成，如图1 所示。采用该编码方式得到的解能够直接映射到原问题上，直观方便。

图1 染色体编码Fig.1 Example of a chromosome coding

（2）适应度。每个染色体都对应一个目标函数值，称为染色体的适应度。为了描述方便，统一使用f表示目标函数和染色体适应度的计算结果，有f=λprifpri+λdisfdis+fslewfdis。

（3）选择算子。根据基因计算得到的适应度，选出最好的基因和中位数以上的基因。如果不符合条件，则让该基因进行交叉变异操作。

（4）交叉算子。随机选择两条基因交叉得到一条新基因，交叉方式随机产生两个结点，将父结点2 片段保留至新基因的相应位置，其余位置由父基因1填补。

（5）变异算子。一条基因变异得到一条新基因，变异方式随机产生两个结点，该基因相应结点位置进行 翻转。

2.2 算法流程

TPA 算法的输入参数包括种群大小Sp、交叉概率Pc、变异概率Pm以及最大迭代次数Ie。

步骤1根据Sp、Pc、Pm，令k=0，初始化染色体种群Pop(k)。染色体种群中每个染色体随机生成全排列组成。

步骤2评估种群Pop(k)，即计算Pop(k)中每一个体的目标函数值，即适应度。

步骤3应用精英主义策略，记录Pop(k)中的最优解。

步骤4从种群Pop(k)选择得到配对池M(k)。

步骤5对配对池M(k)执行交叉和变异操作，具体方法如2.1 节所述。

步骤6构造新种群Pop(k+1)。

步骤7判断终止条件为k是否大于等于Ie，如果满足则停止迭代，输出最优解，否则k=k+1跳转至步骤2。

算法流程如图2 所示。

图2 TPA 规划算法流程Fig.2 Flow chart of TPA algorithm

3 实验及结果分析

为了验证本文算法的有效性，选择GW170814 为观测目标，该事件在2017年8月14日10:30:43 UTC，发生于Eridanus 星座的方向，是一个黑洞合并事件，赤经范围34.41°－53.43°，赤纬范围–54.34°－–7.78°。

本文实验中观测目标共划分230 个Tile，输入数据包括每个Tile 相应的观测坐标、观测时长及优先级（见表2）。

表2 输入数据TileTable 2 Input data of Tile

仿真使用了2022年9月26日的时间窗口数据（见表3）。为避免太阳光照对载荷仪器视场的强光影响（在SVOM 卫星工程中，太阳避免角度设为91°），该时间窗口数据剔除了太阳光照矢量进入载荷视场的时间，同时剔除了卫星进出SAA 区域的时间。对多种组合参数进行了仿真实验，其中：种群大小为100～1000，步进100；交叉概率0.1～0.6，步进0.1；变异概率0.1～0.6，步进0.1；迭代次数范围为500～10000。根据多次实验得出的经验，如果种群数太大则迭代时间会变长，种群数太小则收敛速度慢。如果交叉变异率太高，则收敛过程中适应度波动太大导致收敛变慢，交叉变异率太低又很难跳出局部最优。因此算法的相关参数设置如下：种群大小为600，交叉概率为0.5，变异概率为0.2，既保证了收敛速度，也不会过于早熟，种群大小在兼顾迭代速度和收敛速度下进行了折中选择。适应度函数中λpri和λdis均取为1，最大迭代次数为5000。

表3 时间窗口的输入数据Table 3 Input data of time windows

图3 和图4 给出了GW170814 的TPA 规划结果。图3 为GW170814 的Tiling 规划轨迹，彩色点为被规划的Tile，优先级数值越大代表该Tile 优先级越高，灰色为未被规划的Tile。由图3 可见Tiling 规划轨迹具有规律性，优先级高的Tile 能够被优先规划且整个规划结果走了尽可能短的路径。从表4 中同样可以得出，优先级高的Tile 能够被优先规划。

图3 GW170814 的Tiling 规划轨迹Fig.3 Tiles track after scheduled of GW170814

该算法能够满足对于高优先级任务先执行的需求，以提出的任务目标优先级为主要因素，兼顾路径规划。图4 给出的是GW170814 的时间规划结果。图4 中每条蓝色横向线条表示该Tile 的时间窗口，其中蓝色细虚线表示可观测时间段，蓝色粗实线表示不可观测时间段。TPA 算法规划结果为：共230 个Tile 中有84 个可规划，其中绿色粗实线表示该Tile占用的观测时间段，总观测时间占比为57.87%；红色粗实线表示该Tile 由于地球遮挡所占用的等待时间段，总等待时间占比为40.48%；黄色粗实线表示该Tile 到下一个Tile 占用的调姿时间段；总调姿时间占比为1.65%。将被规划的所有Tile 的可观测时间段的总和除以被规划的所有Tile 的数量的值定义为平均可观测时间。实验结果表明，该算法得到的规划方案具有高时间利用率的优点，规划结果可观测时间是平均可观测时间的1.39 倍。

图4 GW170814 的时间规划结果Fig.4 Planning results of GW170814

输出结果为历史最优解，图5 为算法收敛图像，用于辅助观察算法迭代的整体收敛趋势，不作为结果的输出依据。可以看出随着迭代次数增加，种群中最好基因对应的适应度值呈下降趋势，从44176.74 降至19497.86。适应度数值由优化准则决定，越小表明规划结果越好。在1000 次迭代时适应度值基本达到最优。TPA 算法设计的交叉变异使迭代结果不陷入局部最优值。

图5 TPA 算法收敛图像Fig.5 TPA algorithm convergence image

4 结论

以上结果表明了本文提出TPA 算法的有效性。

通过对基于Tiling 覆盖策略的天文卫星机遇目标任务规划问题进行分析，建立了以距离、任务优先级、调姿角度限制满足率为评价准则的多目标优化数学模型，设计了基于遗传算法的多目标优化任务规划算法。将该算法应用于SVOM 前期工程仿真，采用GW170814 数据对算法进行了实验，结果表明所建立的模型和方法能够有效解决问题，达到合理优化观测收益的目的。在应用中，可以根据实际需求对目标函数参数进行优化，实现加速收敛。

表 4 规划结果中Tile 优先级Table 4 Tile’s priority in planning results

致谢仿真目标源为GW170814，仿真数据由中法天文卫星SVOM 团队的JAUBERT Jean 提供。