img

官方微信

遥感技术与应用, 2023, 38(4): 783-793 doi: 10.11873/j.issn.1004-0323.2023.4.0783

宽波段多光谱数据立方专栏

多目标算法在卫星区域覆盖调度及数传规划上的应用综述

何奇恩,1, 李峰,1,2,3, 钟兴1

1.长光卫星技术股份有限公司,吉林 长春 130102

2.中国科学院长春光学精密机械与物理研究所,吉林 长春 130033

3.中国科学院大学,北京 100049

A Review of the Application of Multi-objective Algorithms in Satellite Regional Coverage Scheduling and Data Transmission Planning

HE Qi'en,1, LI Feng,1,2,3, ZHONG Xing1

1.Chang Guang Satellite Technology Company Limited,Changchun 130102,China

2.Changchun Institute of Optics,Fine Mechanics and Physics,Chinese Academy of Sciences,Changchun 130033,China

3.University of Chinese Academy of Sciences,Beijing 100049,China

通讯作者: 李峰(1988-),男,河北唐山人,博士研究生,主要从事多目标卫星调度与规划算法研究。E⁃mail: lifeng@jl1.cn

收稿日期: 2022-08-25   修回日期: 2023-06-25  

基金资助: 吉林省重点研发项目“多星联合大区域覆盖成像关键技术研究”.  20210201015GX
国家重点研发计划“国产中高分辨率宽波段多光谱卫星数据集构建和高效国际化服务”.  2019YFE0127000

Received: 2022-08-25   Revised: 2023-06-25  

作者简介 About authors

何奇恩(1996-),男,吉林吉林人,硕士,主要从事多目标卫星调度与规划算法研究E⁃mail:heqien777@126.com , E-mail:heqien777@126.com

摘要

随着全世界航天事业的不断壮大,卫星成像业务已经向多星协同覆盖大区域目标转型发展。在此过程中需要同时优化如最大覆盖面积、最小卫星资源利用等多个目标函数。围绕地球观测卫星区域覆盖调度及数传规划全流程,首先总结了典型区域分解技术,其作为卫星区域覆盖计划制定的前期准备步骤,在卫星调度中发挥着重要作用。随后分析评述了近年来多目标算法在卫星区域覆盖调度及数传规划领域的代表性工作。最后进行总结并对未来研究提出几点展望,以期为相关任务的多目标算法应用提供可靠参考。

关键词: 地球观测卫星 ; 区域分解 ; 卫星调度与规划 ; 地面站 ; 多目标进化算法 ; 多星协同

Abstract

With the continuous development of the aerospace industry around the world, the satellite imaging business has developed towards the goal of multi-satellite collaboration covering large areas. In this process, multiple objective functions such as maximum coverage area and minimum satellite resource utilization need to be optimized simultaneously. Focusing on the whole process of regional coverage scheduling and data transmission planning of Earth observation satellites, the typical regional decomposition technology is firstly summarized, which plays an important role in satellite scheduling as a preparatory step for satellite regional coverage and makes the solving of combinatorial optimization problems possible. Then, the representative studies of Multi-Objective Evolutionary Algorithm (MOEA) in the field of multi-satellite joint regional coverage scheduling and data transmission planning in recent years are analyzed and reviewed. Common optimization goals include maximizing coverage rate, minimizing overlap ratio, minimizing the number of strips and so on. Finally, we summarize and put forward some prospects for future research, to provide a reliable reference for the application of multi-objective algorithms in related tasks.

Keywords: Earth observation satellite ; Regional decomposition ; Satellite scheduling and planning ; Ground station ; Multi-objective evolutionary algorithm ; Multi-satellite coordination

PDF (1688KB) 元数据 多维度评价 相关文章 导出 EndNote| Ris| Bibtex  收藏本文

本文引用格式

何奇恩, 李峰, 钟兴. 多目标算法在卫星区域覆盖调度及数传规划上的应用综述. 遥感技术与应用[J], 2023, 38(4): 783-793 doi:10.11873/j.issn.1004-0323.2023.4.0783

HE Qi'en, LI Feng, ZHONG Xing. A Review of the Application of Multi-objective Algorithms in Satellite Regional Coverage Scheduling and Data Transmission Planning. Remote Sensing Technology and Application[J], 2023, 38(4): 783-793 doi:10.11873/j.issn.1004-0323.2023.4.0783

1 引 言

随着我国航空航天事业的不断发展,遥感卫星市场正处于高速增长期。2015年10月7日,由长光卫星技术股份有限公司自主研发的商业卫星星座“吉林一号”组星成功发射,开创了我国商业卫星应用的先河。截止到2023年6月,“吉林一号”星座共有108颗在轨运行卫星,建成了我国目前最大的商业遥感卫星星座,具备了较强的服务能力。UCS卫星数据库显示截止到2022年12月31日,我国已有590颗在轨运行卫星,且近年来每年发射数量成指数型增长,我国已经成为了名副其实的航天大国1

在这些卫星中,有很大比例的卫星属于地球观测卫星(Earth Observation Satellite, EOS),其主要任务是通过光学相机对地球各区域进行观测并获取成像数据(区域覆盖)。卫星数据获取流程如图1所示。首先由来自各领域的客户提出观测需求,卫星运管中心综合考虑所提需求以及在轨卫星资源,选择可用卫星并制定其区域覆盖计划,生成指令上注到卫星,卫星接到指令后便可在特定时间内对指定区域进行拍照成像。成像数据暂时储存在星载硬盘中,当卫星可与地面站通信时将数据下传至地面站。在此过程中涉及多颗卫星之间的调度安排以及卫星与地面站之间的通信规划,是整个卫星数据获取过程中的关键环节。

图1

图1   卫星数据获取流程图

Fig.1   Flow chart of satellite data acquisition


随着卫星数量的不断增加、卫星能力的不断提升、以及用户需求日渐复杂和多元,地球观测对象逐渐由点目标过渡到区域目标。由于卫星幅宽和侧摆能力有限,如果待覆盖区域面积较大,则单颗卫星一次过境难以完整观测整个区域。为了提高观测效率,常见做法是多颗卫星协同工作,组成分布式卫星系统,共同完成区域覆盖任务。多星背景下的区域覆盖问题更加复杂,经常要面临任务冲突以及约束耦合。如果不对这一过程进行运筹优化,则很可能产生大量的重复观测,甚至不能完全观测整个区域,从而导致大量的资源浪费。另外目前地面站数量远小于卫星数量,并且地面站每次只能接收一颗卫星的下传数据,如果不进行规划安排,则无法在有效时间内最大化数据接收量,从而影响整个任务的完成。由于任务的复杂性,无论是多星协同区域覆盖调度还是与地面站之间的数传规划均已被证明是一种多约束时间相关的NP-hard问题2

卫星应用越来越广泛,不同的用户需求以及不同的应用场景意味着我们在进行卫星调度和规划时需要同时考虑如最短完工时间、最少卫星资源利用、最大面积覆盖率、最大数传时长等多个目标,以满足相应任务需求3。此外,目标区域分解是卫星实现区域覆盖任务不可或缺的一部分,常常作为制定卫星调度计划的先前步骤出现。经前期文献调研发现,目前尚没有将区域分解技术和多目标算法在区域覆盖上的应用进行整合的综述性文章。因此本文首先介绍了常用的区域分解技术,随后分析总结了近年来多目标算法在卫星区域覆盖调度及数传规划领域的代表性研究工作,最后进行总结并提出几点展望。

2 目标区域分解技术

区域覆盖是最常见的卫星业务之一,往往需要多颗卫星协同配合,在规定时间内完成对目标区域的观测成像,在城市规划与建设4、农林变化与监测5、灾难响应和救援3中有着广泛的应用。如图2所示,待覆盖区域根据其大小可分为点目标和区域目标。由于成像卫星幅宽、视场角、侧摆角等因素的限制,难以实现单星一次过境对区域目标的全覆盖,因此需要利用区域分解技术对待观测区域进行分解,然后分配给多颗卫星进行协同覆盖。此外,由于卫星所携带的相机可以侧摆,不同侧摆角度下卫星覆盖的区域有所不同;而侧摆角为连续变量,理论上一颗卫星可以生成无数个覆盖条带。应用区域分解技术可以将组合优化问题的解空间从无穷个转化为有限个,使得问题求解变为可能,为后续制定卫星调度和规划方案奠定了基础。

图2

图2   点目标、区域目标及区域覆盖示意图

Fig.2   Schematic diagram of spot target, area target and regional coverage


2.1 网格分解法

网格法是经典的区域分解方法之一,按网格属性又可细分为等经纬度法和等面积法。

2.1.1 等经纬度法

等经纬度法将等经纬度划分的球面映射到二维平面上形成网格。图3显示了其中一种投影方式。当以实际距离为横纵坐标时,网格大小会有所不同,同纬度下的经度跨度固定,即网格长不变;不同纬度线上网格长由赤道到高纬越来越小。早在20年前,Rivett等6便通过对区域目标进行网格化,建立了以最大覆盖率为目标函数的整数规划模型,使用8颗卫星完成了之前16颗卫星的观测任务。此项研究假设参与观测的卫星侧摆能力相同,且侧摆角度固定。阮启明等7将目标区域经过高斯投影后形成二维矩形并划分网格,随后基于约束满足理论,建立了多星协同区域覆盖问题的约束优化模型,将禁忌算法与约束传播相结合以迭代方式获得最优解。Shao等8利用等经纬度的网格将区域目标分解成多个点目标,并在此基础上建立了两目标规划模型。刘华俊等9指出传统等经纬度法一般会有5%的边界区域无法覆盖,而边界网格细分方法又需要大量的人机交互。为此他们提出了一种自适应网格划分方法,将实际覆盖率和计算效率表示成网格经纬度的函数,通过最大化两个函数乘积的平方根来确定最佳网格大小的取值。

图3

图3   等经纬度分解法

Fig.3   Equal longitude and latitude decomposition method


2.1.2 等面积法

图4所示,等面积法顾名思义是将目标区域划分为若干个相同面积的网格。其中比较有名的是预定义的全球参考系统,比较有代表性的是美国Landsat卫星采用的全球参考系统(World Reference System, WRS)和法国SPOT卫星采用的网格参考系统(Grid Reference System, GRS)。在受理到区域覆盖任务后,调度系统根据参考系选择与区域相关的场景进行任务规划。WRS以“Path/Row”坐标系表示;GRS则以星下点轨迹为参考,采用“卫星飞行方向/飞行垂直方向”坐标系10。这种方法在处理单个卫星时是合适的,但没有充分考虑目标区域的特征以及所有可利用的卫星资源,对多卫星任务调度问题并不友好。Zhu等11对观测区域建立等面积网格,引入最长基本覆盖模式的概念,利用上、左、下3个网格的顶点确定一个条带位置,并证明了最长基本覆盖模式可以代替绝大部分非最长的覆盖模式。该方法有利于覆盖到最大的面积,同时将连续空间内的优化问题转变到了离散空间。杨纪伟等12针对多星协同覆盖问题提出了一种基于全球网格的区域目标规划算法。采用军用分幅标准对全球底图进行网格划分,在选用的1:50 000基准比例尺下,全球约分为112万个大小约为22 km×17.8 km的网格。随后按照覆盖面积最大、单次成像最优、加权最优等规则通过贪婪算法依时间顺序选定不同条带,生成对应的协同方案。

图4

图4   等面积分解法

Fig.4   Equal area decomposition method


与此同时不少学者将网格简化成了离散点集。Li等13在成像任务规划之前,将目标区域离散化,便于计算面积覆盖率和条带重叠率。离散化过程主要采用等距散点的方法,精度由离散点之间的距离控制。离散点越密集,精度越高,但计算复杂度也随之增加。类似地,Xu等14利用等距点将目标区域离散化,用点集代表整个区域。可视时间窗口由条带表示,从而便于建立评价系统,收益可以由覆盖的点数来衡量。此类方法在计算覆盖面积时将计算网格面积转换为了统计覆盖点数,在一定程度上可以降低计算过程中的时间和空间复杂度,但其本质与网格形式无异。

2.1.3 网格划分优化方法

网格法直观明了、易于实现,但其局限性在于计算结果的精度与网格尺寸严重耦合。为提高网格法的效率,不少学者在网格法基础上进行改进。沈夏炯等15认为传统网格法面向的目标对象为经纬度区域(矩形),无法对任意几何形状的区域进行覆盖统计。基于此他们在传统网格法基础上增加了筛选目标区域网格点算法,改进的网格法可用于任意几何区域进行覆盖特性的分析。彭攀等16根据卫星对地覆盖的几何特性,将同纬度网格点作为一个整体从而考察卫星对每个纬度带的覆盖情况,由此设计出一种改进的网格点法,可降低瞬时性覆盖时间复杂度。汪荣峰等17针对传统网格法在评估覆盖性能时运算量大且效率低的问题,提出了一种基于扫描线的区域覆盖分析算法。在卫星条带多边形生成和目标区域包围盒网格划分的基础上,基于经度方向的网格点构造扫描线,将扫描线与目标区域的相交部分作为初始计算对象,通过初始计算对象与条带求交实现扫描线的分段划分,统计扫描线分段数据得到覆盖率、覆盖重数等指标。算例分析结果表明,该算法具有较低的时空复杂度。

2.2 条带分解法

另一种经典的区域分解方法是条带法。条带法将目标区域分解成若干矩形框,称为条带,该矩形框所包含区域可以由单个卫星一次过境完全覆盖,如图5所示。Liu等18考虑了卫星的轨道特性以及遥感器的观测能力,根据卫星轨迹在一定侧摆角度下进行条带绘制,建立了目标区域的条带分解方法。He等19主要基于时间窗口和侧摆角度建立了一个五元子任务集,将目标区域分解为一系列属于不同卫星和侧摆角度的候选子任务。通过建立以覆盖率为目标函数的调度模型,解决了双星模式下目标区域的调度问题。Niu等3将卫星侧摆角的范围划分为一组固定步长的离散值,并将其定义为偏移参数。随后根据卫星的不同特性将目标区域划分为一组连续的条带。潘耀等20首先根据卫星的轨道位置,计算卫星与目标区域的可见时间窗口,随后计算卫星在目标区域内的最大、最小有效观测角度,再通过控制卫星的侧摆角度偏移量,同时考虑幅宽的动态变化,将目标区域分解成相互平行且幅宽不等的条带。

图5

图5   条带分解法

Fig.5   Strip decomposition method


条带法不考虑所生成条带的长度以及如何最优化所覆盖网格,只通过调整侧摆角步长来控制生成条带的数量。因此与网格法相比,该方法可以明显降低候选条带的数量,减少冗余条带对后续调度模型求解速度的影响。另一方面,在得到区域覆盖计划之后通常需要对条带长度进行剪裁,以避免不必要的资源浪费。

2.3 静态与动态分解

区域分解技术还可分为静态分解技术和动态分解技术。基于独立场景的点目标覆盖方法、预定义参考系分解法以及固定宽度的条带分解法便属于静态分解技术21。静态分解方法计算相对简单,在工程应用中易于实现。但难以适用于多星协同的场景,特别是在遥感卫星异构化条件下,区域目标的分割难度大,存在重复观测的问题。动态分解技术是指在对目标区域进行分解时综合考虑了卫星轨道位置、侧摆角变动以及不同侧摆角下成像幅宽变化等动态因素。该方法同样将目标区域分解成若干条带,因此往往与条带法联合使用。

白保存等22针对多星对目标区域的协同覆盖问题提出了基于卫星观测能力的动态划分方法。划分时考虑遥感卫星载荷的幅宽、侧摆能力以及轨道参数,并按照不同的偏移参数对目标区域进行灵活划分,充分体现了不同卫星遥感器的观测能力。He等23提出了一种针对多边形目标区域的动态分解方法,以卫星在不同滚角下的区域覆盖为分解基础,将点目标作为特殊区域目标,根据观测机会对其进行分解。目标分解后的元任务被视为调度的基本元素。对不同类型目标分别构建的收益函数反映了两类目标在计算上的差异,从而实现了对两类目标的统一表示和处理。余婧等24针对大区域成像观测问题,建立了敏捷卫星同轨多条带拼幅成像工作模式。采用基于相机视场角的动态划分方法将区域目标划分成多个可观测条带,使得划分的条带能够完全覆盖目标区域,并保证相邻条带之间足够的重叠宽度。最近的一项研究工作是姚靖宇等25对平行条带分割方法的改进,利用卫星的侧摆角枚举了卫星每个观测机会下所有可访问的观测模式,设计了一种基于单元格的动态条带分割方法。与静态方法相比,动态分解方法能够充分发挥各类卫星的整体观测效能,更加适用于多星协同的观测场景。

3 多目标算法在卫星区域覆盖调度及数传规划方面的应用

随着卫星数量的不断增加,亟需在合理的计算时间内解决大规模卫星调度和数传规划问题。常用算法主要包括数学规划算法和智能优化算法。数学规划算法主要利用运筹学相关知识来研究该问题,但是作为一个典型的NP-hard问题,这种方法难以在短时间内取得好的结果,在大规模任务中体现得尤为明显。在资源不断增加的情况下,目前对精确求解算法的研究越来越少26。因此大多数研究者都将重心转向了智能优化算法,主要包括启发式算法和进化优化算法。启发式的典型代表是贪心算法、禁忌搜索算法和模拟退火算法。这类算法具有较强的局部搜索能力,但缺少统一、完整的理论体系,而且容易陷入到局部最优27。进化算法是一种成熟的全局优化方法,具有较高的鲁棒性和广泛的适用性28。常见的进化算法有遗传算法、蚁群算法、粒子群算法等。

3.1 加权和方式处理多目标问题

Bianchessi等29通过多个归一化效用函数的加权和来衡量多个目标函数,随后使用禁忌搜索算法解决多卫星调度问题。Mansour等30提出了一种改进的遗传算法来解决SPOT5调度问题,以一种新的基因组表示形式来确定要拍摄哪些照片,同时计算基因组利润,以加权和的形式构建最大化每日利润和拍摄照片数量的目标函数。Globus等31将进化算法应用于卫星调度问题,他们使用多个目标函数的加权和来评估适应度函数,并表明真正更好的多目标方法可能会产生更好的解。Chen等32通过加权和的方式建立了以最大利润和最大任务完成率为目标的数学模型,提出了一种基于种群扰动和消除策略的遗传算法来解决多卫星跟踪遥测与指挥(TT&C)调度问题。

然而上述方法对多目标优化问题的处理与单目标优化没有任何不同。此类方法的局限性主要有以下3点:①所求解对用来构造目标函数的权重特别敏感,特别是当存在相互冲突的目标时,权重的变化将导致产生不同的解。②如果由于使用无效的权重而导致得到的解不被接受,优化器不得不从头开始再次运行33。③加权和方法在凸帕累托前沿中可能工作得很好,但是当帕累托前沿为凹时,可能存在此类方法无法找到的解33

3.2 多目标进化算法在卫星区域覆盖调度及数传方面的应用

解决多目标优化问题的理想情况是找到每个目标函数的最优解。但在现实世界中这一任务往往很难实现,因为要同时优化的目标函数通常都会存在冲突。对于一组解,如果没有一个目标值可以在不降低其他目标值的情况下得到改进,那么这组解被称为帕累托最优解,也称为非支配解34。如图6所示,与上述这些将目标函数整合成一个加权和的传统方法相比,多目标进化算法(Multi-objective Evolutionary Algorithm, MOEA)的目的就是设法在帕累托最优前沿找到一组非支配解。

图6

图6   多目标进化算法求解示意图

Fig.6   Solutions of multi-objective evolutionary algorithm


3.2.1 常见优化目标及约束

为便于读者理解,本节首先对卫星区域覆盖调度与数传规划问题中的常见共性目标函数及约束进行汇总。各变量及意义见表1

表1   变量及说明

Table 1  Variables and explanation

变量符号说明
siSi个卫星
oijOii个卫星的第j次过境
xijki个卫星在第j次过境时的第k个条带
areaijkxijk所覆盖的面积
Mii个卫星的最大数据存储能力
αmaxii个卫星的最大侧摆能力
tq观测区域q的任务
rrq任务tq的要求分辨率
[rstq, retq]任务tq的要求开始时间和结束时间
wijkWiji个卫星第j次过境时第k个条带的可视时间窗口
[wstq, wetq]wijk的开始和结束时间
mijkwijk成像所占用的内存
grijkwijk获取的图像分辨率
overlap计算条带重叠率的函数
glGl个地面站
dtpDp个数传任务
twilhHi个卫星和第l个地面站之间的第h个时间窗口
[cstil, cetil]i个卫星和第l个地面站的实际通信时间

新窗口打开| 下载CSV


决策变量:

(1)是否在观测任务中选择某条带:

xijk=1,  wijk被选0,  wijk不被选择

(2)是否在数传规划任务中选择某时间窗口:

twilh=1,  twilh被选0,  twilh不被选择

常见目标函数:

(1)最大化覆盖面积(收益):

max  i=1|S|j=1|Oi|k=1|Wij|xijkareaijk

(2)最小化所选条带个数:

min  i=1|S|j=1|Oi|k=1|Wij|xijk

(3)最小化条带重叠率:

min  i=1|S|j=1|Oi|k=1|Wij|overlap(xijk)

(4)最小化任务完成时间:

min  max  i=1|S|j=1|Oi|k=1|Wij|xijk(wetq-wstq)

(5)最大化数传时长:

max  i=1|S|l=1|G|(cetil-cstil)

(6)最大化数传任务完成率:

max  p=1Dh=1Htwilh/|D|

常见约束条件:

(1)每颗卫星每次过境只能选择一个条带用于观测:

k=1|Wij|xijk1, i1,S,j1,Oi

(2)每颗卫星的内存限制:

j=1|Oi|k=1|Wij|xijkmijk<Mi

(3)每颗卫星的可视时间窗口必须在任务规定时间内:

rstqwstq<wetqretq,
i1,S,j1,Oi,k[1,|Wij|]

(4)获得的图像分辨率满足所要求分辨率:

grijkrrq,
 i1,S,j1,Oi,k[1,|Wij|]

(5)侧摆角度在允许范围内:

αiαmaxi

(6)每个地面站每次只能与一颗卫星进行数传:

cetil<csti+1l

3.2.2 多星协同区域覆盖问题

解决多星协同覆盖区域目标的一般方法包括两个步骤。第一步是将目标区域按照一定的规则分解成一系列元任务(meta-tasks),即区域分解过程。第二步是设计各种模型和算法(多为多目标进化算法)选择这些元任务的一个子集,并将它们分配给特定的卫星。换言之,该方法将卫星区域覆盖问题分为两个子问题,即目标区域的分解和调度模型的优化。

Xu等14以同时最大化总利润、最小化条带数量和最小化特定目标区域的条带重叠为目标,将卫星调度问题转化为集合覆盖问题,并建立数学模型,提出了一个三阶段求解框架。以等距离散点的方式将待覆盖区域分解成条带集合,随后引入多目标遗传算法NSGA-II35以生成最佳调度方案。Niu等3针对灾难响应阶段的两种典型应用场景,提出了一种多目标优化方法来解决观测大面积区域目标的卫星调度问题。首先设计了一种分解方法,将区域任务划分为一系列观测条带。为了选择最佳条带组合以形成令人满意的区域成像任务计划,以最大覆盖率、最短成像完成时间、最大平均空间分辨率和最小平均回转角为目标函数,将多卫星协同覆盖问题表示为一个多目标整数规划模型。最后使用NSGA-II算法获得卫星调度的最优解。Chen等36认为多星观测任务涉及到的目标区域分解和调度模型优化这两个步骤应该是相互关联的,为此他们以是否选择成像条带及其侧摆角为两类决策变量,将区域分解和卫星资源分配同时整合到调度模型中,建立了具有最大目标区域覆盖和最小卫星资源利用两个目标函数的优化模型,随后使用NSGA-II算法进行模型求解。实验结果表明,所提出的多目标建模方法能够以较少的卫星资源完成对目标区域的覆盖,显著提高卫星利用效率。

在其他算法应用方面,Li13认为目前多目标进化算法只能在收敛性、多样性、复杂性之一上表现良好,其目标是在所有3个方面找到一个更加平衡的MOEA。他们首先采用轨迹法将待观测多边形区域分解成大量元任务(条带),随后以最小条带数、最小条带重叠率、最大区域覆盖率和最小任务完成时间为目标函数建立数学模型,选用了Two-Archive2算法37来分配条带,制定区域覆盖调度方案。Wei等38以调度失败率和工作负载均衡度为双目标函数,提出了一种考虑卫星过渡时间的多目标Memetic算法39来处理敏捷卫星区域覆盖调度问题。计算实验表明所提方法可以得到具有更好质量和整体性能的非支配解。Wang等40针对SPEA241算法提出了一个新的编码方式,将地面站作为特殊成像要求考虑进去,来解决以最小资源消耗和最小成像要求为双目标的卫星成像调度问题。

大多数多目标进化算法都尝试逼近整个帕累托前沿。然而,当目标函数过多时(如超过3个),基于帕累托优势的算法会遇到很大困难,通常很难获取到整个帕累托解集。同时,决策者可能只关注较小区域的一组帕累托最优解,而不是整个帕累托前沿。多目标优化的最终目标是帮助决策者找到最符合其偏好的解。这种情况下逼近整个帕累托前沿既不高效也无必要。因此不少学者考虑在优化过程之前、之后以及优化过程期间(交互地)将决策者的偏好信息整合到多目标进化算法中以解决多目标优化问题42-45。如图7所示,通过偏好信息来引导搜索方向,多目标算法只关注决策者感兴趣的区域,从而大大减少不必要的计算工作。

图7

图7   加入目标区域偏好信息的多目标进化算法求解示意图

Fig.7   Solutions of multi-objective evolutionary algorithm with target region preference information


近年来,Li及其同事在这一方面做了大量的研究工作。在其2017年的研究论文中,首次将目标区域(target region)偏好信息与3个多目标算法SMS-EMOA46、R2-EMOA47和NSGA-II结合起来(分别命名为T-SMS-EMOA、T-R2-EMOA和T-NSGA-II),提出了一种基于目标区域的多目标进化算法框架(TMOEAs)。应用三级排序准则(按顺序分别为非支配排序、超容量/R2/拥挤距离以及解到目标区域的切比雪夫距离)以在目标区域获得一组拥有良好收敛和良好分布的帕累托最优解48。2018年,他们将该方法应用到了敏捷卫星对地观测任务调度领域,以收益、图像质量以及时效性为目标函数,同时加入决策者的偏好信息(如要求收益必须在0.95以上)。仿真结果表明所提算法可以很好地找到目标区域与帕累托前沿的交集,验证了TMOEAs在实际问题中的能力49。同年,他们又将该思想与MOEA/D和NSGA-III算法相结合,应用在了五目标敏捷卫星观测调度问题中;还提出了一个交互式框架,允许决策者在算法搜索过程中调整偏好信息50。Xiong等51在上述研究基础上,将目标区域和参考点两种偏好信息相结合来构建偏好模型,同样引入三级排序准则以同时保持解在目标区域内良好的收敛性和多样性。随后他们将所提方法应用在了五目标卫星调度问题上,仿真结果表明与经典NSGA-III算法相比,所提方法成功地获得了满足任务规划偏好的解,并在收敛性和多样性方面取得了更好的性能52

3.2.3 卫星与地面站数传规划问题

数传是指当卫星在与地面站可通信时将数据下传至地面站的过程。随着客户需求和卫星成像任务的不断增加,卫星数据传输流量也随之大幅度增长。如何在有效时间内解决大规模多目标数传问题引起了学者们的高度关注。卫星数传及地面站调度是卫星调度优化问题的变体,同样是一个涉及多个目标的复杂调度问题,并且被证明是NP-hard问题。Xhafa等53-55曾在多项研究中定义了4个主要目标函数,在此基础上,提出了4种不同的适应度函数。但Xhafa并没有从多目标优化的角度进行考虑,而是将4个目标整合成了一个,随后使用单目标优化算法进行求解。Zhang等56提出了一种基于分解-整合(DI)的方法来处理星地时间同步(Satellite-Ground Time Synchronization, SGTSTP)数传规划问题。在DI方法中,规划时间跨度被等长地划分为许多不相交的规划周期,并且为每个周期都分配一些时间窗口,在此基础上数传规划问题变成了一个多周期的0~1规划问题。随后将DI方法嵌入到进化算法框架中,提出了基于DI的多目标进化算法(DI-MOEA)来解决四目标组合优化问题。Song等57针对大规模TT&C调度问题,在NSGA-II算法中引入学习机制,试图最大化收益的同时减小任务失败率。

在交叉和突变操作之前,学习机制与选择操作一起应用于每个个体以获取任务序列的冲突率。学习机制可以使优化过程有一个明确的目的,使任务序列朝着减少任务冲突的方向前进。同时提出任务-时间窗口选择算法,可以为任务选择地面站时间窗口用于数传工作。实验结果显示所提方法在大规模任务数下表现出色。Zhang等58在其研究中将数传资源冲突的周期性、数传规划问题的大规模和多维度等特点考虑进去,借鉴机器学习领域的分类思想,提出了一种新的SVM+NSGA-II算法。首先构建了一个多分类SVM模型,通过训练历史规划数据形成分类器,对新任务进行预测从而生成初始规划方案。接下来将NSGA-II算法应用于初始规划方案中未成功规划的任务以生成最终规划方案。仿真结果表明该方法可以在保证良好优化目标的同时,在很短的时间内有效地解决大规模多目标数传规划问题。Petelin等59使用NSGA-II、NSGA-III60、SPEA2、GDE361、IBEA62和MOEA/D636种不同的多目标进化算法尝试解决地面站调度问题,目的是测试这些算法对地面站调度问题的一些基准静态实例的功效和性能。优化目标包括最大化卫星和可见地面站之间的通信持续时间、多个卫星与1个地面站的通信冲突、总数传时长大于需求时长以及最大化地面站利用率。此外作者又将4个目标函数通过加权和的形式整合成单一目标,并与多目标结果进行比对。仿真结果显示基于分解的MOEA/D方法在几乎所有方面都优于针对特定问题的其他算法。

4 总结与展望

随着卫星数量的不断增加以及各领域需求的不断增长,卫星观测成像已经向多星多任务多目标方向发展。多目标进化算法是一种成熟的具有高鲁棒性和广泛适用性的全局优化方法,具有自组织、自适应、自学习的特性,能够不受问题性质的限制,有效地处理传统优化算法难以解决的复杂优化问题,近年来广泛应用于多星调度及规划领域,并取得了不错的成果。本文针对整个卫星数据获取与生产流程,首先对常见的区域分解技术进行分类汇总,随后分析评述了近年来有代表性的多目标卫星区域覆盖调度及数传规划研究工作。从中可以看出基于遗传机制的NSGA-II、NSGA-III算法以及基于分解机制的MOEA/D算法是目前研究最多、应用最广的多目标算法,在各分支领域都取得不了错的效果6465。最后,针对目前研究现状以及实际应用问题,提出以下3点展望:

(1)点目标和多边形区域目标的联合观测任务规划。实际的用户观测需求往往是点目标和区域目标的结合。现有的区域分解和调度、规划方法不能很好地解决两者同时观测的问题。今后应重点研究融合点目标和区域目标的多星多目标协同观测问题。

(2)改进现有多目标算法以提升所求解的收敛性和多样性。收敛性(不断逼近最优解)和多样性(产生新的可行解)一直是多目标进化算法重点关注的两个基本问题。随着目标函数和约束的不断增加,传统多目标算法往往会出现求解效果衰退的现象。因此何如平衡收敛性与多样性之间的关系、提升算法求解效率值得进一步深入研究。

(3)将多目标算法与其他方法相融合。多目标算法种类繁多,特点各异。针对其自身局限性,可将其与局部搜索、机器学习等算法整合使用,使得多目标算法能够在更广泛的实际问题中得以应用。

参考文献

Union of Concerned Scientists (UCS) Satellite Database

[DB/OL]. https:∥www.ucsusa.org/resources/satellite-database, 2022-12-31. 2023-07-18.

URL     [本文引用: 1]

VAZQUEZ A JERWIN R S.

On the tractability of satellite range scheduling

[J]. Optimization Letters, 201592): 311-327. DOI: 10.1007/s11590-014-0744-8

[本文引用: 1]

NIU XTANG HWU L.

Satellite scheduling of large areal tasks for rapid response to natural disaster using a multi-objective genetic algorithm

[J]. International Journal of Disaster Risk Reduction,201828813-825. DOI:10.1016/j.ijdrr. 2018.02.013

[本文引用: 4]

GAROUANI A ELMULLA D JGAROUANI S ELet al.

Analysis of urban growth and sprawl from remote sensing data: Case of Fez, Morocco

[J]. International Journal of Sustainable Built Environment, 201761): 160-169. DOI: 10.1016/j.ijsbe.2017.02.003

[本文引用: 1]

KHALID NULLAH SAHMAD S Set al.

A remotely sensed tracking of forest cover and associated temperature change in Margalla hills

[J]. International Journal of Digital Earth,20191210):1133-1150. DOI:10.1080/17538947. 2018.1448008

[本文引用: 1]

RIVETT CPONTECORVO C.

Improving satellite surveillance through optimal assignment of assets

[R]. Defence Science and Technology Organisation Edinburgh (Australia) Intelligence Surveillance Reconn Div2003.

[本文引用: 1]

RUAN QimingTAN YuejinLI Yongtaiet al.

Using constraint satisfaction to cooperate satellites' activities for the mission of area target observation

[J]. Journal of Astronautics, 2007281): 5.阮启明, 谭跃进, 李永太, 等. 基于约束满足的多星对区域目标观测活动协同[J]. 宇航学报, 2007, 281): 5.

[本文引用: 1]

SHAO XZHANG ZWANG Jet al.

NSGA-II-based multi-objective mission planning method for satellite formation system

[J]. Journal of Aerospace Technology and Management, 20168451-458. DOI: 10.5028/jatm.v8i4.700

[本文引用: 1]

LIU HuajunCAI BoZHU Qing.

Self-adaptive planning method of imaging reconnaissance satellites area coverage

[J]. Geomatics and Information Science of Wuhan University, 20174212): 1719-1725.

[本文引用: 1]

刘华俊蔡波朱庆.

一种成像卫星区域覆盖的自适应规划方法

[J]. 武汉大学学报·信息科学版, 20174212): 1719-1725.

[本文引用: 1]

XU YudongZHOU JingboYIN Jiazhaoet al.

Review of mission planning strategies and applications of earth observation satellites

[J]. Radio Engineering, 2021518): 681-690.

[本文引用: 1]

许宇栋周敬博尹嘉昭.

对地观测卫星任务规划策略及应用研究综述

[J]. 无线电工程, 2021518): 681-690.

[本文引用: 1]

ZHU WHU XXIA Wet al.

A three-phase solution method for the scheduling problem of using earth observation satellites to observe polygon requests

[J]. Computers & Industrial Engineering, 20191302019): 97-107. DOI: 10.1016/j.cie.2019.02.014

[本文引用: 1]

YANG JiweiFU WeiHAN Liet al.

Regional target planning algorithm of satellite imaging based on global grid

[J]. Spacecraft Engineering, 2021301): 31-38.

[本文引用: 1]

杨纪伟付伟韩丽.

基于全球网格的卫星成像区域目标规划算法

[J]. 航天器工程, 2021301): 31-38.

[本文引用: 1]

LI X.

Two-archive2 algorithm for large-scale polygon targets observation scheduling problem

[C]∥Proceedings of the 2nd International Conference on Information Technology and Management EngineeringShanghai201723-24.

[本文引用: 2]

XU YLIU XHE Ret al.

Multi-objective satellite scheduling approach for very large areal observation

[C]∥IOP Conference Series: Materials Science and Engineering. IOP Publishing20184351): 012037.

[本文引用: 2]

SHEN XiajiongWU XiaoyangWANG Gengkeet al.

Remote sensing satellite covering method over ground facing to any geometric area

[J]. Application Research of Computers, 2016337): 1999-2013.

[本文引用: 1]

沈夏炯吴晓洋王更科.

面向任意几何区域的遥感卫星对地覆盖法

[J]. 计算机应用研究, 2016337): 1999-2013.

[本文引用: 1]

PENG PanSONG ZhimingNI Tao.

Application of improved net-point method to solving area coverage problem

[J].Chinese Journal of Engineering Geophysics, 2019163): 395-402.

[本文引用: 1]

彭攀宋志明倪涛.

改进的网格点法在区域覆盖问题中的应用

[J]. 工程地球物理学报, 2019163): 395-402.

[本文引用: 1]

WANG RongfengHU Min.

Algorithm for satellite regional coverage analysis based on scanline

[J]. Computer Engineering, 2020461): 243-246.

[本文引用: 1]

汪荣峰胡敏.

基于扫描线的卫星区域覆盖分析算法

[J]. 计算机工程, 2020461): 243-246.

[本文引用: 1]

LIU X DCHEN Y WLONG Y J.

A MapX-based preprocessing approach for multi-satellite cooperative observation towards area target

[J]. Systems Engineering-Theory & Practice, 2010302269-2275.

[本文引用: 1]

HE YXU MYANG Zet al.

Scheduling imaging mission for area target based on satellite constellation

[C]∥The 27th Chinese Control and Decision ConferenceQingdao20153225-3230.

[本文引用: 1]

PAN YaoCHI ZhongmingRAO Qilonget al.

Dynamic segmenting method of polygon target based on FOV for remote sensing satellite imaging

[J]. Spacecraft Engineering, 2017263):38-42.

[本文引用: 1]

潘耀池忠明饶启龙.

基于视场角的遥感卫星成像多边形区域目标动态分解方法

[J]. 航天器工程, 2017263): 38-42.

[本文引用: 1]

ZHANG GLI XHU Get al.

Mission planning issues of imaging satellites: Summary, discussion, and prospects

[J]. International Journal of Aerospace Engineering, 202120211-20.

[本文引用: 1]

BAI BaocunRUAN QimingCHEN Yingwu.

Dynamic segmenting method of polygon for remote sensing saltellites observing

[J]. Operations Research and Management Science, 2008172): 43-48.

[本文引用: 1]

白保存阮启明陈英武.

多星协同观测条件下区域目标的动态划分方法

[J]. 运筹与管理, 2008172): 43-48.

[本文引用: 1]

HE RBAI BCHEN Yet al.

Multi-satellite mission planning for environmental and disaster monitoring satellite system

[C]∥SpaceOps 2008 ConferenceHeidelberg20083488.

[本文引用: 1]

YU JingXI JinjunYU Longjianget al.

Study of one-orbit multi-strips splicing imaging for agile satellite

[J]. Spacecraft Engineering, 2015242): 27-34.

[本文引用: 1]

余婧喜进军于龙江.

敏捷卫星同轨多条带拼幅成像模式研究

[J]. 航天器工程, 2015242): 27-34.

[本文引用: 1]

YAO Jingyu.

Research on multiple satellite scheduling method oriented to regional target observation

[D]. HefeiHefei University of Technology2020.

[本文引用: 1]

姚靖宇.

面向区域目标观测的多星调度方法研究

[D]. 合肥合肥工业大学2020.

[本文引用: 1]

BRANDIMARTE P.

Scheduling satellite launch missions: an MILP approach

[J]. Journal of Scheduling, 2013161): 29-45. DOI: 10.1007/s10951-012-0304-y

[本文引用: 1]

RAMAN VGILL N S.

Review of different heuristic algorithms for solving travelling salesman problem

[J]. International Journal of Advanced Research in Computer Science, 201785): 423-425.

[本文引用: 1]

BEHESHTI ZSHAMSUDDIN S M H.

A review of population-based meta-heuristic algorithms

[J]. International Journal of Advances in Soft Computing and its Applications, 201351): 1-35.

[本文引用: 1]

BIANCHESSI NCORDEAU J FDESROSIERS Jet al.

A heuristic for the multi-satellite, multi-orbit and multi-user management of earth observation satellites

[J]. European Journal of Operational Research, 20071772): 750-762. DOI: 10.1016/j.ejor.2005.12.026

[本文引用: 1]

MANSOUR M ADESSOUKY M M.

A genetic algorithm approach for solving the daily photograph selection problem of the SPOT5 satellite

[J]. Computers Industrial Engineering, 2010583): 509-520. DOI: 10.1016/j.cie.2009.11.012

[本文引用: 1]

GLOBUS ACRAWFORD JLOHN Jet al.

Scheduling earth observing satellites with evolutionary algorithms

[C]∥International Conference on Space Mission Challenges for Information TechnologyCalifornia2003.

[本文引用: 1]

CHEN MWEN JSONG Y Jet al.

A population perturbation and elimination strategy based genetic algorithm for multi-satellite TT&C scheduling problem

[J]. Swarm Evolutionary Computation,202165100912. DOI:10.1016/j.swevo.2021. 100912

[本文引用: 1]

FONSECA C MFLEMING P J.

An overview of evolutionary algorithms in multiobjective optimization

[J]. Evolutionary Computation, 199531): 1-16.

[本文引用: 2]

DENG WZHANG XZHOU Yet al.

An enhanced fast non-dominated solution sorting genetic algorithm for multi-objective problems

[J]. Information Sciences, 2022585441-453. DOI: 10.1016/j.ins.2021.11.052

[本文引用: 1]

DEB KPRATAP AAGARWAL Set al.

A fast and elitist multiobjective genetic algorithm: NSGA-II

[J]. IEEE Transactions on Evolutionary Computation,200262): 182-197.

[本文引用: 1]

CHEN YXU MSHEN Xet al.

A multi-objective modeling method of multi-satellite imaging task planning for large regional mapping

[J]. Remote Sensing, 2020123): 344. DOI: 10.3390/rs12030344

[本文引用: 1]

WANG HJIAO LYAO X.

Two_Arch2: An improved two-archive algorithm for many-objective optimization

[J]. IEEE Transactions on Evolutionary Computation, 2014194): 524-541.

[本文引用: 1]

WEI LXING LWAN Qet al.

A multi-objective memetic approach for time-dependent agile earth observation satellite scheduling problem

[J]. Computers Industrial Engineering, 2021159107530. DOI: 10.1016/j.cie.2021.107530

[本文引用: 1]

MOSCATO P.

On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms

[J]. Caltech Concurrent Computation Program, C3P Report, 19898261989.

[本文引用: 1]

WANG JJING NLI Jet al.

A multi-objective imaging scheduling approach for earth observing satellites

[C]∥Proceedings of the 9th Annual Conference on Genetic and Evolutionary ComputationLondon20072211-2218.

[本文引用: 1]

ZITZLER ELAUMANNS MTHIELE L.

SPEA2: Improving the strength pareto evolutionary algorithm

[R]. TIK-report2001, 103.

[本文引用: 1]

DEB KSUNDAR J.

Reference point based multi-objective optimization using evolutionary algorithms

[J] International Journal of Computational Intelligence Research, 200623): 273-286.

[本文引用: 1]

SAID L BBECHIKH SGHÉDIRA K.

The R-dominance: A new dominance relation for interactive evolutionary multicriteria decision making

[J]. IEEE transactions on Evolutionary Computation,2010145):801-818. DOI: 10.1109/TEVC. 2010.2041060

MOLINA JSANTANA L VHERNÁNDEZ-DÍAZ A Get al.

G-dominance: Reference point based dominance for Mmultiobjective metaheuristics

[J]. European Journal of Operational Research, 20091972): 685-692. DOI: 10.1016/j.ejor.2008.07.015

THIELE LMIETTINEN KKORHONEN P Jet al.

A preference-based evolutionary algorithm for multi-objective optimization

[J].Evolutionary Computation,2009173):411-436.

[本文引用: 1]

BEUME NNAUJOKS BEMMERICH M.

SMS-EMOA: Multiobjective selection based on dominated hypervolume

[J]. European Journal of Operational Research, 20071813): 1653-1669.

[本文引用: 1]

TRAUTMANN HWAGNER TBROCKHOFF D.

R2-EMOA: focused multiobjective search using R2-indicator-based selection

[C]∥International Conference on Learning and Intelligent OptimizationBerlin201370-74.

[本文引用: 1]

WANG YLI LYANG Ket al.

A new approach to target region based multiobjective evolutionary algorithms

[C]∥2017 IEEE Congress on Evolutionary Computation (CEC)San Sebastián20171757-1764.

[本文引用: 1]

LI LWANG YTRAUTMANN Het al.

Multiobjective evolutionary algorithms based on target region preferences

[J]. Swarm Evolutionary Computation, 201840196-215. DOI: 10.1016/j.swevo.2018.02.006

[本文引用: 1]

LI LCHEN HLI Jet al.

Preference-based evolutionary many-objective optimization for agile satellite mission planning

[J]. IEEE Access, 2018640963-40978. DOI: 10.1109/ACCESS.2018.2859028

[本文引用: 1]

XIONG MXIONG WLIU C.

A hybrid many-objective evolutionary algorithm with region preference for decision makers

[J]. IEEE Access, 20197117699-117715. DOI: 10.1109/ACCESS.2019.2931742

[本文引用: 1]

XIONG MXIONG W.

A region preference-based optimization algorithm for satellite mission planning problem

[C]∥Journal of Physics:Conference SeriesShenzhen2022012035.

[本文引用: 1]

XHAFA FHERRERO XBAROLLI Aet al.

A tabu search algorithm for ground station scheduling problem

[C]∥2014 IEEE 28th International Conference on Advanced Information Networking and ApplicationsVictoria20141033-1040.

[本文引用: 1]

XHAFA FHERRERO XBAROLLI Aet al.

Evaluation of struggle strategy in genetic algorithms for ground stations scheduling problem

[J]. Journal of Computer System Sciences,2013797):1086-1100. DOI:10.1016/j.jcss.2013.01.023

LALA AKOLICI VXHAFA Fet al.

On local vs. population-based heuristics for ground station scheduling

[C]∥2015 Ninth International Conference on Complex, Intelligent, and Software Intensive SystemsSanta Catarina2015267-275.

[本文引用: 1]

ZHANG ZXING LCHEN Yet al.

Evolutionary algorithms for many-objective ground station scheduling problem

[C]∥International Conference on Bio-inspired Computing: Theories and ApplicationsSingapore2016265-270.

[本文引用: 1]

SONG Y JMA XLI X Jet al.

Learning-guided nondominated sorting genetic algorithm II for multi-objective satellite range scheduling problem

[J]. Swarm Evolutionary Computation,201949194-205. DOI:10.1016/j.swevo.2019.06.008

[本文引用: 1]

ZHANG JXING LPENG Get al.

A large-scale multiobjective satellite data transmission scheduling algorithm based on SVM+ NSGA-II

[J]. Swarm Evolutionary Computation, 201950100560. DOI: 10.1016/j.swevo.2019.100560

[本文引用: 1]

PETELIN GANTONIOU MPAPA G.

Multi-objective approaches to ground station scheduling for optimization of communication with satellits

[J]. Optimization and Engineering, 20211-38. DOI: 10.1007/s11081-021-09617-z

[本文引用: 1]

DEB KJAIN H.

An evolutionary many-objective optimization algorithm using reference-point-based nondominated sortinga approach, part I: Solving problems with box constraints

[J]. IEEE Transactions on Evolutionary Computation, 2013184): 577-601.

[本文引用: 1]

KUKKONEN SLAMPINEN J.

GDE3: The third evolution step of generalized differential evolution

[C]∥2005 IEEE Congress on Evolutionary ComputationEdinburgh2005443-450.

[本文引用: 1]

ZITZLER EKÜNZLI S.

Indicator-based selection in multiobjective search

[C]∥International Conference on Parallel Problem Solving from NatureBerlin2004832-842.

[本文引用: 1]

ZHANG QLI H.

MOEA/D: A multiobjective evolutionary algorithm based on decomposition

[J]. IEEE Transactions on Evolutionary Computation, 2007116): 712-731. DOI: 10.1109/TEVC.2007.892759

[本文引用: 1]

LIAO ZGONG WYAN Xet al.

Solving nonlinear equations system with dynamic repulsion-based evolutionary algorithms

[J]. IEEE Transactions on Systems, Man, Cybernetics: Systems, 2018504): 1590-1601. DOI: 10.1109/TSMC.2018.2852798

[本文引用: 1]

GONG WWANG YCAI Zet al.

Finding multiple roots of nonlinear equation systems via a repulsion-based adaptive differential evolution

[J]. IEEE Transactions on Systems, Man, Cybernetics: Systems, 2018504): 1499-1513. DOI: 10.1109/TSMC.2018.2828018

[本文引用: 1]

/