面向多星区域观测调度的改进型自适应遗传算法

樊育，刘莹莹，周军

西北工业大学 航天学院，西安 710072

地球观测卫星(Earth observation satellite, EOS)可以实现对指定点目标或区域目标的观测成像。但是，如果卫星不具有侧摆能力，那么卫星仅能对其星下点轨迹上视场角范围内的目标实现观测；而实际任务目标中的大部分区域都是没有在指定卫星星下点轨迹上及其视场角范围内的。因此在卫星不具有侧摆能力的情况下，对指定区域目标的覆盖效率是很低的。为了解决这个问题，可将星载相机在垂直于卫星星下点轨迹的方向上进行摆动，以此实现对未在星下点轨迹上及其视场角范围内的目标进行观测，大大提高卫星的对地覆盖效率。另外，随着微小卫星的发展，大大降低了卫星的制作成本，使得越来越多的卫星组成卫星星座[1-2]去完成对指定区域目标的观测成为各个国家和企业的研究重点。

当今资源充分利用的环境下，如何利用一定的卫星资源实现对目标区域最大程度的覆盖[3]，已经是研究对地观测卫星的热点问题，引起众多学者的关注。伍国华等[4-5]提出了动态聚类调度算法(dynamic clustering scheduling algorithm, DCSA)来解决多星多轨道圈次的观测调度问题，并使用模拟退火算法搜索全局最优解；李仕学等[6]面向月表大区域成像任务需求，提出了拼接成像侧摆角优化方法，并提出基于sigmoid函数的自适应遗传算法(sigmoid adaptive genetic algorithm, SAGA)对其进行求解；Wang等[7]为了提高计算效率，考虑了当前任务与历史任务的相似性，提出具有检索、匹配和修正的相似性学习法，并结合遗传算法对实际观测任务进行求解，大大加快了任务的求解速度； Fei等[8]考虑卫星传感器的实际侧摆能力，结合贪婪算法的思想提出一种动态划分目标区域的算法；Xu 等[9]针对多卫星区域调度问题，提出一种3阶段解决框架，即离散、分解和调度阶段，在最后一阶段利用遗传算法进行求解；Zhu等[10]综合考虑地球观测卫星调度中的成像与数据传输问题，提出了一种两阶段遗传模拟退火算法去解决调度问题；Wu等[11]针对调度任务中的重要紧急任务调度处理，提出一种结合局部搜索的混合蚁群算法对调度问题进行优化；刘华俊等[12]针对现有覆盖算法低效耗时的技术瓶颈，提出了一种针对成像卫星区域覆盖的自适应规划方法，包括自适应的网格划分、平衡成像精度和覆盖效率的最大可视覆盖计算以及窗口优化的卫星区域覆盖策略。

在以上研究中还存在以下不足：1)文献[4-5]只研究了点目标任务的聚类调度问题，针对区域目标的调度问题还未研究；2)文献[6]只研究了单星成像问题，并未对多星成像问题进行研究；3)文献[12]提出的优化方法只找到一个局部最优解，并不能保证其全局最优性；4)都是通过STK(Satellite tool kit)获得时间窗口，没有通过轨道六要素自主计算星下点轨迹，从而获得对目标观测的时间窗口，使得程序算法缺乏灵活性；5)都是仅仅以卫星对地观测的覆盖率作为唯一的收益指标，均未考虑对目标区域总覆盖时间这一指标；而这一指标直接反映了卫星在规定时间内对指定目标的观测时间长短，是一个重要的覆盖指标。

基于以上情况，本文根据卫星的轨道六要素计算出星下点轨迹，并采用网格点法自主划分区域目标，在指定的最大侧摆角范围内计算出每颗卫星每次过境的时间窗口，得出每颗卫星在每次过境时段内的侧摆角集合。最后将问题转化为多个时间窗口和多个侧摆角集合的动态组合调度优化问题，为了更高效地实现目标收益的最大化，提出了结合平均Hamming距离、神经元激活函数sigmoid和高斯函数的改进型自适应遗传算法(Hamming distance sigmoid Gauss function adaptive genetic algorithm, HSGAGA)对此动态组合调度优化问题进行求解，并通过算例与其他常用的优化算法,包括标准遗传算法(genetic algorithm，GA)、改进型遗传算法(improved genetic algorithm,IGA)、标准模拟退火算法(simulated annealing algorithm,SA)、改进型模拟退火算法(improved simulated annealing algorithm，ISA)进行对比，验证了本文所提出的HSGAGA算法的优良性能。

1 卫星对目标的侧摆角度计算

1.1 星载遥感器的覆盖能力

在卫星具有侧摆能力的情况下，卫星在轨道上对地的观测角指的是卫星在垂直于星下点轨迹的方向上，视场角与侧摆角的结合。如图1所示。

图1 卫星对地覆盖示意Fig.1 Illustration ofsatellite coverage

若卫星某时刻t的瞬时轨道高度为h，相应星下点为S′，星载遥感器的侧摆角度为β，视场角为FOV(field of view)，则卫星对地观测角为β+FOV/2。假设地球是一半径为Re的均匀圆球体，h为卫星轨道高度，卫星距地心距离SOe=h+Re，由几何关系，此时弧段AS′对应的地心覆盖角φ为：

(β+FOV/2)

同时，由地心覆盖角可得覆盖幅宽为：

AS′=φ·Re

当然，对于不同高度的轨道卫星，观测角β+FOV/2也有其相应的约束范围，如图2所示。

图2 卫星对地观测范围示意Fig.2 Illustration of satellite observation range

最大观测角即就是观测边界与地球相切，即θ=90°，根据几何关系，轨道高度为h的卫星对地最大观测角为：

即有观测角约束：

β+FOV/2≤φ

而且，对于不同高度、不同相机幅宽的轨道卫星，对地观测的视场角FOV也不同，如图3所示，其中l为相机半幅宽。

根据几何关系，轨道高度为h，相机幅宽为2l的卫星对地观测的视场角大小为：

图3 卫星相机半幅宽l与视场角FOVFig.3 Satellite camera width l and field of view FOV

1.2 侧摆角度的计算

对于卫星对区域目标的侧摆角度计算，可采用经典的网格点法将区域目标转化为点目标集合，进而将问题转化为卫星对区域点集合中各个点的侧摆角度计算。此时，采用点的包含性检验来判断是否可见，同时计算出侧摆角集合。

如图1所示，若目标点位于B(λ,φ)，则过B点作垂直于卫星星下点轨迹的垂线，并与其交与S′(λx,φx)。根据几何关系，采用基于球面三角学的大圆距离求解算法，得目标点B与卫星星下点S′的弧长BS′为：

BS′=arccos[sinλsinλx+

cosλcosλxcos(φx-φ)]·Re

则地心覆盖角∠BOeS为：

∠BOeS=BS′/Re

最后，在三角形BOeS中，根据几何关系，求得处于S处的卫星对目标点B的侧摆角度β为：

2 多星观测调度模型

2.1 问题特点及约束分析

对于本文所研究的多星观测调度问题，具有如下的特点及约束。

1)卫星调度方式：所有卫星仅在垂直于星下点轨迹的方向上具有侧摆能力。

2)卫星机动能力约束：限制卫星在同一过境时段内，只能以单一的侧摆角进行过境，在不同过境时段内，可以以不同的侧摆角进行过境。

3)光照条件约束：为了获得卫星对指定目标更好的的观测信息，必须要保证卫星对指定目标观测时的太阳高度角，即任一颗卫星对区域目标内的任意一个子目标进行观测时，太阳高度角[13]都必须大于所要求的保证良好光照条件的临界值。

2.2 调度模型中的参数含义及表示

1)Sat={S1,S2,…,SNS}表示卫星资源集合，即在调度任务中共有NS颗对地观测卫星资源可执行目标区域的观测任务。

2)O={oi|i=1,2,…,Ni}表示卫星对目标区域进行过境的轨道圈次资源，Ni表示多颗卫星的总的过境次数。

3)T={ti|i=1,2,…,N}是待观测的目标集合，N表示总任务数量。

4)Twrj={twrj1,twrj2,…,twrjNrj}表示在考虑天气条件的情况下，卫星r对目标j的Nrj个可见时间窗口，其可写为twrjm=[Strjm,Etrjm]。其中Strjm、Etrjm分别表示卫星r对候选任务j的第m个可见时间窗口的开始时间和结束时间。

(5)βr,i={βr,i,1,βr,i,2,…,βr,i,Ng}表示卫星r在第i次过境下可供选择的Ng个侧摆角集合。

(6)v={v1,v2,…,vi,…,vr}表示卫星r上的传感器要对准待观测目标时的侧摆速率。

(7)a={a1,a2,…,ai,…,ar}表示卫星r在对某个目标观测之前的传感器开机时间。

(8)wr={wr,1,wr,2,…,wr,oi,…,wr,N}表示卫星r在过境圈次oi上对地观测活动消耗星上存储资源的速率。

(9)Wr={Wr,1,Wr,2,…,Wr,oi,…,Wr,N}表示卫星r在过境圈次oi上允许消耗的最大存储资源。

(10)Xr,i,j={Xr,i,j,1,Xr,i,j,2,…,Xr,i,j,N}表示卫星r在第i次过境第j次侧摆情况下对各个目标点的可见性集合。若Xr,i,j,k=1，则表示卫星r在第i次过境第j次侧摆情况下对目标点k可见；反之，若Xr,i,j,k=0，则表示对目标点k不可见。

(11)tmr,i,j={tmr,i,j,1,tmr,i,j,2,…,tmr,i,j,N}表示卫星r在第i次过境第j次侧摆情况下对各个目标点的观测时刻集合。若tmr,i,j,k=t(t≠0)，则表示卫星r在第i次过境第j次侧摆情况下对目标点k的观测时刻为t；反之，若tmr,i,j,k=0则表示对目标点k不可见。

(12)tcr,i={tcr,i,1,tcr,i,2,…,tcr,i,Ng}表示卫星r在第i次过境且采用各个侧摆角的情况下对目标区域的覆盖持续时间。若tcr,i,j=t(t≠0)，则表示卫星r在第i次过境第j次侧摆情况下对目标区域的持续覆盖时间为t；反之，若tcr,i,j=0则表示对目标区域不可观测。

2.3 调度模型的建立

在指定时间段内，卫星对地观测的覆盖指标主要有两个：一是对目标区域的覆盖率；二是对目标区域总的覆盖时间。为了综合考虑这两种覆盖指标，此多星观测调度问题的目标收益取为：

式中：{x1,x2,…,xN}为决策向量集，xi表示多颗卫星第i次过境时选择第xi个侧摆角；wk为各覆盖指标的权值；fk{x1,x2,…,xN}为在决策向量集{x1,x2,…,xN}下的第k个覆盖指标的值，f1、f2分别表示覆盖率和总的覆盖时间。

调度过程中需要满足复杂的约束条件，如下所示。

1)侧摆角约束：考虑机动能力，任意侧摆角都必须不大于最大侧摆角，否则将不能侧摆成功。

2)侧摆时间约束：任意一颗卫星在对指定目标相邻两次过境观测过程中，所间隔的时间必须不小于卫星星载设备所需机动调整的时间，即：

3)存储容量约束：在第oi次过境观测中，卫星所获得的观测信息容量必须不大于卫星单轨运行所允许的最大存储容量，即：

3 改进型自适应遗传算法

3.1 算法实现流程

遗传算法(GA)是由Holland[14]于20世纪70年代提出的一种基于自然选择法则的搜索寻优算法。但标准遗传算法在交叉操作和变异操作中的交叉率和变异率为固定值，对于耦合性较高的复杂优化问题，不利于种群的进化而易于陷入局部最优。

为了改进这一缺陷，Srinivas、任子武等[15-16]提出了自适应遗传算法，但在进化初期或后期，都存在易陷入局部最优的问题。

为了更快更高效地搜索到全局最优解，实现目标收益的最大化，本文提出了结合平均Hamming距离、神经元激活函数sigmoid和高斯函数的改进型自适应遗传算HSGAGA对动态组合调度优化问题进行求解，其算法流程如图4所示，其中R表示染色体长度。

图4 改进型自适应遗传算法HSGAGA的流程Fig.4 Flowchart of improved adaptive genetic algorithm HSGAGA

3.2 算法典型步骤

(1)编码

采用k进制编码，直接将决策向量集x={x1,x2,…,xN}作为染色体，x中的元素xi作为基因。k编码类似于十进制编码，唯一不同的是十进制编码中基因的取值为0～9之间的整数，而k编码中基因的取值为1～k之间的整数。

(2)种群初始化

使用蒙特卡洛方法逐步生成初始种群中的个体，并且通过比较两个k进制编码的染色体对应基因不同的个数作为Hamming距离，以此来控制初始种群的个体差异，改善初始种群的活力，以扩大种群的多样性。具体方法如下：若新产生的个体与前面已产生的某一个体的Hamming距离小于染色体长度的三分之一，则摒弃此新个体，重新产生新的个体，直到种群初始化结束。

(3)交叉、变异操作的顺序确定

基本的遗传算法不论种群适应度如何变化，都是先进行交叉操作，后进行变异操作。这在种群的进化中，易于导致种群早熟而陷入局部最优解。如在种群进化后期，种群个体差异很小，此时倘若先进行交叉操作，则对优良个体的产生基本没有作用，缩小了搜索空间，使得种群陷入局部最优。

因此提出一种根据当代种群平均Hamming距离对交叉与变异操作的顺序进行确定的方法：

(1)

式中：Ha为当代种群的平均Hamming距离。若式(1)成立，说明此时种群多样性较小，应先进行变异操作，后进行交叉操作；反之，应先进行交叉操作，后进行变异操作。

(4)改进型的交叉操作、变异操作

本文中的交叉操作选择以“门当户对”原则且结合混沌序列[17]的多点交叉，利用混沌序列产生待交换位置串，进而实行多点交叉。变异操作选择结合混沌序列的多点变异。

交叉操作和变异操作中的交叉率和变异率是决定算法收敛速度、稳定程度的关键参数。交叉率是种群进化的基础，交叉率越大，种群越丰富，算法搜索空间越大，但优良个体被破坏的可能性也越大；交叉率过小，不易产生新个体，而最后陷于早熟现象。变异率则是产生全局最优解的关键一步，变异率过小，不易产生新个体，而最后陷于局部最优；变异率过大，又会使遗传算法趋近于随机搜索算法，大大增加了运算开销。

本文基于sigmoid函数[18]和高斯基函数[19]对交叉率和变异率进行改进，设计出一种自适应非线性调整交叉率和变异率的调节公式，如下所示：

(2)

(3)

根据式(2)和式(3)绘制本文HSGAGA算法中自适应交叉率和变异率的调整曲线，如图5和图6所示。

图5 自适应交叉率调整曲线Fig.5 Curve of adaptive crossover rate

图6 自适应变异率调整曲线Fig.6 Curve of adaptive mutation rate

由图5和图6可以看出：首先，在种群进化初期，由蒙特卡洛方法和Hamming距离生成的种群多样性可以在较大的交叉率下充分发挥作用，产生初始的优良个体；并且，较小的变异率可以阻止对初始优良个体的破坏，增加了算法的收敛速度。其次，在种群个体适应度与种群平均适应度favg相近时，为了防止种群产生“早熟”现象而陷入局部最优，给予了较大的交叉率Pc和变异率Pm，增加种群的多样性，避免了算法停滞不前。最后，当种群个体适应度接近种群最大适应度fmax时，说明种群的多样性很低，此时通过交叉操作已经不能产生更优的个体，应给予较小的交叉率Pc，而为了增加种群的多样性，防止种群“早熟”而陷入局部最优解，应适当地增加变异率Pm。

(5)选择操作

结合双精英保留策略和锦标赛选择策略[20]对经过交叉和变异之后的种群进行选择操作，构成新的种群。

双精英保留策略：为了防止遗传算法在运行过程中，由于交叉和变异等遗传操作破坏了当前种群中的最优个体，大大影响遗传算法的收敛速度，这里提出一种双精英保留策略，主要思想是，若下一代种群中的最优个体适应度小于当代种群中的最优个体适应度，则用当代种群中最优的两个个体替换掉下一代种群中最差的两个个体，以保证种群的收敛能力，增大种群的收敛速度。

锦标赛选择策略：模拟锦标赛竞争的方式，通过随机选择多个个体，并在多个个体中通过择优录取的方式实现选择操作。

(6)停机条件

采用双重停机条件。传统的遗传算法通常采用单一的g停机条件，即若进化代数达到预先给定的总的进化代数g，则结束算法运行。但若初始种群较优且参数选取非常理想，使得遗传算法很快能够搜索到最优解，倘若此时仍采取单一的g停机条件，便会额外增加算法的运行时间。

因此，本文算法在执行过程中，采用双重停机条件：进化代数达到总的进化代数g；连续N次进化的最优结果不变。在遗传进化过程中，满足上述两个条件中的任何一个，都结束算法的运行，大大提高了算法的收敛速度，减少了额外的计算时间。

4 仿真实验

4.1 卫星及目标区域参数设置

为了验证本文多星调度模型以及改进型自适应遗传算法HSGAGA的性能，进行仿真实验的卫星及目标区域参数设置如下。

(1)卫星轨道参数

由于对地观测卫星要求较好的光照条件以及一定的回归特性和稳定性[13]，因此本文使用的3颗卫星轨道均是作者设计的太阳同步回归冻结轨道，降交点地方时均为早上10:30:00，具体轨道参数如表1所示。

a,e,i,Ω,ω,f指轨道六要素，分别为轨道半长轴、偏心率、倾角、升交点赤经、近地点幅角、真近点角。卫星上传感器的相机幅宽均为2l=20 km；各卫星机动能力所限制的最大侧摆角为βmax=±30°；各卫星上传感器的侧摆速率为v=1(°)/min ；各卫星对地观测消耗星上存储资源的速率为w=1.5 Mbyte/s；各卫星单轨运行所允许的最大存储容量为W=90 Mbyte；能够清晰地观测到目标所要求的太阳高度角不小于10°；调度模型中目标收益的权值分别取为ω1=0.9，ω2=0.1。

表1 卫星参数

(2)目标区域参数

目标区域选择包括西安市在内的一个矩形区域，其4个顶点的经纬度坐标分别为(100°,30°)(110°,30°)(110°,40°)(100°,40°)。通过网格化方法，对此区域进行网格化，一共划分为13×13=169个网格点；且观测开始时间为2018-05-01 12:00:00，结束时间为2018-05-06 12:00:00。

4.2 算法参数设置及计算结果

为了验证本文改进型自适应遗传算法HSGAGA的性能，将其与标准遗传算法(GA)、结合改良圈、混沌序列的改进型遗传算法(IGA)、文献[6]中所提出的基于sigmoid激活函数的自适应遗传算法(SAGA)、模拟退火算法(SA)、结合蒙特卡洛方法的改进型模拟退火算法(ISA)进行对比，分别对此次调度问题进行求解。

算法采用Matlab r2012a实现，计算机的CPU为Pentium E5800，内存为3.00 Gbyte。其中各算法的参数设置如下：

SA算法：初始温度为T0=1，降温系数为α=0.999，终止温度为e=0.130，退火最大次数为T=40000。

ISA算法：初始温度为T0=1，降温系数为α=0.999，终止温度为e=0.130，退火最大次数为T=40 000。

GA算法：种群大小为w=30，最大进化代数为g=1 000，交叉率为Pc=0.7，变异率为Pm=0.1。

IGA算法：种群大小为w=30，最大进化代数为g=1 000，交叉率为Pc=0.7，变异率为Pm=0.1。

SAGA算法：种群大小为w=30，最大进化代数为g=1000，最大交叉率为Pcmax=0.8，最小交叉率为Pcmin=0.5，最大变异率为Pcmin=0.2，最小变异率为Pcmin=0.05。

HSGAGA算法：种群大小为w=30，最大进化代数为g=1 000，最大交叉率为Pcmax=0.8，最小交叉率为Pcmin=0.5，最大变异率为Pcmin=0.2，最小变异率为Pcmin=0.05，停机代数为150。

分别使用以上6种算法对本文的多星观测调度问题进行求解。其中，SA算法、ISA算法获得退火次数与每次退火后个体适应度值的关系如图7所示；HSGAGA算法、GA算法、IGA算法、SAGA算法获得进化代数与每代种群最大适应度值的关系如图8所示。

图7 SA、ISA算法的性能比较Fig.7 Performance of SA and ISA

图8 GA、IGA、HSGAGA算法的性能比较Fig.8 Performance of GA, IGA and HSGAGA

在HSGAGA算法下，这3颗卫星开始观测到区域目标的时间、侧摆角和覆盖持续时间如表2所示。

表2 HSGAGA算法下各卫星的观测结果

使用这6种方法对问题进行50次求解，所得到的对地观测卫星对目标区域进行观测的两个覆盖指标(覆盖率、总的覆盖时间)以及各个算法求解的执行时间，分别求其平均值，如表3所示。

表3 各算法求解所得覆盖性能及执行时间

由图7、图8和表3可以看出：

1)本文提出的HSGAGA算法执行了37.39 s，在287代时即达到全局最优解，而GA、IGA、SAGA算法分别执行了93.82 s、91.25 s、81.36 s，依然在1 000代仍进入了局部最优解，SA、ISA算法分别执行了121.97 s、123.11 s，依然在40 000次退火之后也仍进入了局部最优解。

2)应用HSGAGA算法对问题进行50次求解中，总共触发了39次双重停机条件，说明了在对问题进行优化求解中，使用双重停机条件的必要性；并且，其所求得的全局最优解使得卫星对地覆盖率达到了36.09%，比次好的SAGA算法高了2.95%；并且总的覆盖时间1 653 s也是最高的，比次好的SAGA算法高了18 s；而且算法的执行时间也最短，为37.39 s，仅是次好的SAGA算法执行时间的45.96%。

结合图8也可以看出，本文所设计的改进型自适应遗传算法HSGAGA可以在种群初期充分利用种群的多样性，通过交叉得到较好的个体，并且在种群中期，同时通过交叉和变异操作增加种群的多样性，避免种群“早熟”而陷入局部最优，最后在种群末期，能够以一定的变异率继续进行全局寻优，避免了种群停滞不前。这也充分说明了本文所提出的HSGAGA算法对于解决复杂动态组合优化问题的快速性与有效性。

5 结束语

本文提出了一种改进型自适应遗传算法(HSGAGA)，高效地解决了面向多星区域观测调度问题。具体的实验用例表明，相较于其他现代优化算法，HSGAGA算法所求得的侧摆调度方案不但大大提高了卫星对目标区域进行观测的覆盖率和总的覆盖持续时间，而且算法本身的执行时间很短，说明该算法既有效也高效。此外，该算法具有通用性，适用于其他动态组合调度优化问题的求解。

本文研究了只在垂直于星下点轨迹方向上侧摆的卫星调度问题，后续的工作是进一步研究敏捷卫星(agile earth observation satellite, AEOS)对地观测调度问题。