采用混合遗传算法的敏捷卫星自主观测任务规划

高新洲，郭延宁，马广富，张海博，李文博

(1.哈尔滨工业大学 航天学院，哈尔滨 150001; 2.北京控制工程研究所，北京 100190)

敏捷对地观测卫星(agile earth observation satellite, AEOS)拥有良好的姿态机动能力，在民用和军用领域都有着广阔的应用前景，比如环境保护、国土普查、抗震减灾以及制空权、制天权、制海权等。在AEOS的运行过程中，对AEOS提前根据目标点特性进行任务规划至关重要，可有效发挥AEOS性能，获取更多的观测收益[1]。而在任务规划过程中，AEOS需要对多个目标点进行规划，同时也要考虑到卫星在观测过程中所面临的多种状态、控制等复杂约束条件，因此，国内外越来越多的学者开始进行卫星任务规划方面的研究。

Michel等[2]提出了对点目标以及区域目标的分割和观测方法，综合分析了时间约束、姿态机动约束、存储容量和能量的约束，同时考虑到了天气的不确定性，并提出了相应的优化目标函数。他们分别对比了贪婪算法、动态规划算法、局部搜索算法这几种算法的求解效率。赵琳等[3]对敏捷卫星的单星单轨任务规划问题进行了研究，引入了任务—姿态协同规划思想，并根据任务—姿态协同规划数学模型设计了自适应伪谱遗传算法(APGA)，用以求解满足调整时间最优的任务规划问题。耿远卓等[4]利用团划分算法对多个点目标进行了聚类，考虑了卫星的时间窗口约束以及最大加速度约束，在传统的蚁群算法的基础上引入了启发式寻优策略和新的信息素更新策略，加快了算法的收敛性。丁祎男等[5]面向单星的任务规划问题，在综合分析遗传算法与禁忌搜索算法优缺点的基础上，提出了遗传禁忌混合算法，该算法能够解决算法的早熟问题，同时能够加快算法收敛速度。王海蛟等[6]针对敏捷卫星的调度问题，采用了二进制与实数杂合的编码方式，将量子优化机制引入了遗传算法中，提出了改进的量子遗传算法，提高了搜索效率。Tangpattanakul等[7]针对单星的任务规划问题，提出了一种基于知识的多目标局部搜索方法(IBMOLS)，该方法实质上是局部搜索算法与遗传算法的综合方法，能够比遗传算法更快地收敛。Chu等[8]研究了由低分辨率和高分辨率的卫星组成的双星任务规划问题，对双星协同任务规划问题进行建模，提出了分支限定的求解方法。Lee等[9]面向多星任务规划问题，主要考虑了卫星能源以及存储容量的约束，利用遗传算法进行求解，就不同的应用场景进行了仿真。Zheng等[10]将多星的星上任务规划问题建模为约束优化问题，同时在现有的用于卫星任务规划的遗传算法的基础上，提出了求解速度更快的混合动态变异遗传算法(HDMGA)。黄生俊等[11]对知识定义、知识更新规则和任务冲突处理策略做了详细描述，并综合蚁群算法的反馈特性和模拟退火算法的局部搜索特性,设计了一种基于知识的改进模拟退火算法。何磊等[12]考虑了光学成像敏捷卫星中的云层遮挡问题，采用了预判和二分法进行云层遮挡时间窗口的计算，并针对这一问题提出了相应的蚁群算法进行求解，提高了光学成像卫星的成像效率。Tipaldi等[13]结合了规划系统和动态重规划的能力深入分析了马尔科夫决策过程(MDP)模型的自主规划方法，验证了该方法在实际应用中的性能。郝会成等[14]将免疫遗传算法与蚁群算法等相结合，提出了基于混合遗传求解算法，同样提高了算法的求解速度。Xu等[15]考虑了卫星的资源约束条件，在此基础上提出了基于优先权的结构算法，用于最大化观测收益。董轩鸿[16]研究了对观测目标的条带划分策略，设计了改进的遗传算法。

综合来看，目前已有很多文献应用遗传算法等智能优化算法来解决卫星的任务规划问题[3,5,7,10]。虽然应用遗传算法可以求解出卫星的最优观测序列，但是传统的遗传算法在交叉、变异等寻优过程仍有许多值得改进的地方，因此有必要对遗传算法的变异过程做出改进，进而提升算法的求解效率。同时，如果规划问题的适应度函数过于简单[17]，往往不能真实地反映卫星的实际观测情况，因此有必要对适应度函数做出改进。

基于上述考虑，本文提出了禁忌退火遗传混合算法，并将其应用于求解AEOS的任务规划问题。首先提出了本文的适应度函数.此函数综合考虑了卫星在观测过程中的多种约束条件，能够较为真实地反映卫星的实际观测情况。其次介绍了禁忌退火遗传混合算法。此算法对遗传算法的变异过程做出了改进，将禁忌搜索算法与模拟退火算法的寻优过程的优势引入到了遗传算法的变异过程，提升了遗传算法的邻域搜索能力，节省了算法的运行时间，适用于AEOS的任务规划问题。

1 任务规划问题建模

1.1 任务规划问题描述

AEOS在运行过程中，主要通过横滚轴和俯仰轴进行姿态机动。星上携带有摄像头，可以对地面实施观测任务。如图1所示，卫星沿滚动轴的最大姿态机动角度为θmax/2，沿俯仰轴的最大姿态机动角度为ξmax/2。当卫星经过目标点上空时，需要提前对目标点的观测序列做出规划，得到满足观测约束下的最优/次优观测序列。

图1 AEOS观测示意

卫星观测目标点时，会获得相应的收益，在对单目标的持续观测和目标间的姿态机动过程中，卫星需要消耗一定能量。因此，构建的目标优化函数必须综合考虑观测收益及观测代价(即能量消耗)，在满足各种约束条件情况下，通过优化算法获得卫星对目标点的观测序列。

1.2 适应度函数的建立

定义如下变量：M为目标点集合，M={m1,m2,…,mn}，其中mi为第i个目标点，n为目标点总数；ttwsi为卫星对mi可见的时间窗口的开始时间；ttwei为卫星对mi可见的时间窗口的结束时间；tsi为卫星对mi的实际开始观测时间；tei为卫星对mi的实际结束观测时间；di为卫星对mi的实际观测的持续时间，即di=tei-tsi；trij为卫星从观测mi到观测mj转过的姿态机动角度；pi为mi的任务优先级，pi取值越大，意味着mi的优先级越高；wi为卫星观测mi获得的收益，即wi=di·pi；posi=(lgti,lati)为mi的经、纬度坐标，其中lgti为mi的经度；lati为mi的纬度，决策变量si和Fij的定义如下：

(1)

(2)

基于上述定义的变量，考虑如下适应度函数:

(3)

上式表示的函数由观测收益与卫星姿态机动的能量消耗两部分组成. 式中：si·wi为卫星观测某一目标点所带来的收益，收益与目标点优先级成正比；f1+si·di为卫星观测过程中消耗的能量，其中si·di为持续观测某一目标点的能耗，f1为卫星姿态机动的能耗，与卫星姿态机动过程中匀加速与匀减速的时间Δt有关；η为卫星的能耗系数，是一个常数。Δt的计算方法如下。

本文假设卫星在目标点之间姿态机动时，每个轴均以最大力矩Tmax进行机动，根据卫星需要转过的角度大小分为两种情况考虑，如图2的两种情况所示。图2(a)对应大角度机动情况，图2(b)对应小角度的情况。

综上所述，考虑f1为

(4)

式中，Δt为卫星进行匀加速与匀减速过程的总时间。综合式(3)、(4)可得

(5)

图2 求解卫星姿态机动角度示意

从式(5)可以看出，f取得最大值是本文的优化目标，即在考虑到卫星的能量消耗的情况下尽可能多地获得观测收益。

1.3 AEOS任务规划的约束条件

下面给出AEOS任务规划的约束条件。

如果目标点mi被观测，那么观测的持续时间区间必须被包含在卫星对mi可见的时间窗口内，即

ttwsi≤tsi，ttwei≥tei,若si=1

(6)

卫星结束观测mi以后，必须在mj的时间窗口结束之前完成姿态机动才可以观测mj，即

tsi+trij+di≤ttwej,若Fij=1

(7)

考虑如下卫星轨道动力学约束：

(8)

以及如下卫星姿态角约束、姿态角速度约束、姿态角加速度约束:

|θ|≤θmax，|ξ|≤ξmax

(9)

ωθ≤ωθmax，ωξ≤ωξmax

(10)

αθ≤αθmax，αξ≤αξmax

(11)

此外，还需要考虑如下卫星姿态转移时间约束:

trij=f(rs,posi,posj,Tmax)

(12)

式中，时间trij与两个目标点的经纬度以及AEOS的最大机动力矩Tmax相关，计算方法如图2所示。其中AEOS需要机动的角度θ的求解采用了文献[17]的方法，如图3所示。

图3 AEOS姿态机动角度的求解

在图3中，Rei和Rej分别为mi和mj在地心惯性坐标系(ECI)中的坐标，具体公式为

(13)

式中:ω为地球自转角速度，Re为地球半径。

图3中Res为卫星在ECI中的坐标，可通过下式求得：

(14)

式中:Rs为卫星的轨道半径，Ω为升交点赤经，ψ为近地点幅角，α为卫星转过的角度，可由下式确定：

α=E+ωst

(15)

式中:E为卫星开始观测时刻的真近点角，ωs为卫星的角速度，t为当前的时刻。

由图3中可得下式

(16)

因此，卫星从观测mi姿态机动到mj所需转动的角度θ可通过下式求得：

θ=arccos

(17)

综合式(17)与图2，即可最终求得卫星的姿态机动时间trij。

2 禁忌退火遗传混合算法

对于大规模的卫星任务规划问题，传统的遗传算法很难在较短的运算时间内给出最优的观测序列。因此，有必要对遗传算法的寻优过程做出改进。相对于传统的遗传算法变异方法，本文提出的禁忌退火变异方法能够有效提高算法的求解搜索效率，节省算法的运行时间。

2.1 初始种群生成

本文采用整数编码来解决卫星的任务规划问题。整数编码与二进制编码等其他编码方式相比，能够更直观地表示卫星的观测序列，也便于算法搜寻邻域解。

采用整数编码方式的每个染色体(也称作解、个体)分别代表一种可行的观测序列。染色体上的每个基因所对应的数字即为目标点，如图4所示。

图4 整数编码的染色体

图4代表一条长度为6的染色体，表示卫星需要观测6个目标点，且最先5号目标点，最后观测6号目标点。

设地面上目标点总数为n，AEOS需要从n个目标点中选取N个目标点进行观测，种群规模为M。种群初始化的方法为，随机生成M个观测序列，其中每个观测序列都是N个不大于n且互不重复的正整数，即同一个目标点不会重复被观测。在此后算法的每一次迭代过程中，都会首先计算种群中每一条染色体所对应的适应度函数值。

2.2 适应度函数计算

适应度函数值的大小是衡量种群中每个个体优劣程度的重要指标。对于每一个给定的观测序列，为了计算此序列所对应的适应值，需要首先确定卫星能否依次观测此序列所有的目标点。过程如下：

Step1比较当前的时间t与mi的时间窗口结束时间ttwei。如果t>ttwei，则mi无法被观测，令si=0，i=i+1，继续执行step1。如果t

Step2比较t与ttwsi。如果t>ttwsi，则执行step3。如果t

Step3计算trij。如果t+trij>ttwei，则mi无法被观测，令si=0，i=i+1，执行step1。如果t+trij

Step4计算trij。如果t+trijttwei，则mi无法被观测，令si=0，i=i+1，执行step1。

Step5如果t+trijttwsi，令t=t+trij+di，i=i+1，执行step1。

从i=1起，重复执行上述过程，直至i=N，即可得到每个观测序列所对应的si以及Fij。将si、Fij以及关于每个目标点的wi等变量带入式(5)即可求得每个观测序列所对应的适应值的大小，每个个体的优劣程度也就可以依次确定。

2.3 选择、交叉操作

本文采用精英保留策略以及轮盘赌法对种群进行选择、交叉操作。精英保留策略将第g代种群中的若干优秀个体当做父本直接传递到第g+1代种群。随后根据轮盘赌法从父本中选择父本进行交叉运算，生成若干子代，使得第g+1代的种群规模为M。

轮盘赌法的计算过程如下所示：

(18)

(19)

式中:Fi为第i个父本对应的适应值，Qi为第i个父本被选择的概率，Pi为从第1个父本直至第i父本的累加概率。其中，各父本按照适应度从大到小的顺序排列。

第i个父本被选中参与交叉过程的方法如下：产生一个介于0和1之间的随机数r，如果该随机数满足Pi-1

图5 交叉操作

经过交叉操作得到的子代往往都含有相同的基因。比如图5中，子代1的6和3都是重复出现的元素。因此，需要进行去重复操作，使每个子代的各个基因之间都两两互不重复。去重复操作是将每个子代中重复的基因随机用没有出现在该子代染色体中的基因替代，如图6所示。

图6 去重复操作

2.4 禁忌退火变异

本文给出了禁忌退火变异(tabu search-simulated annealing mutation，TSSAM)。首先给出了禁忌搜索算法和模拟退火算法的相关定义；其次介绍了TSSAM的具体过程；最后分析了TSSAM对于传统的变异方法的改进之处。

2.4.1 禁忌搜索算法

禁忌搜索算法(tabu search algorithm,TS)寻优策略为，从初始解的邻域解集中选取最优解或者是未被禁忌的最优解作为新的初始搜索解，直至算法收敛。禁忌搜索算法通过不断更新禁忌表来避免在一个邻域内重复搜索，进而提高算法的全局搜索能力，加快算法收敛速度。禁忌搜索算法的一些定义如下。

1)初始解。参与禁忌搜索的最开始的解，在本文中即为参与变异的个体x0。

2)邻域解集。初始解x0的邻域解构成的集合。对于采用整数编码方式的染色体来讲，邻域解采用2-opt形式，即通过互换两个基因位上的元素来产生邻域解，如图7所示。邻域解集的规模与染色体的长度有关。

图7 产生邻域解

3)候选解。x0产生的邻域解集中的最优解或者是未被禁忌的最优解，用于同x0比较，决定是否要用候选解替换x0。

4)禁忌表。用于记录被禁忌的前若干次的操作。对于采用整数编码的染色体来讲，禁忌表是一个N×N的矩阵。其中N为染色体长度。禁忌表中第i行第j列的数字ai,j表示交换i,j两个位置上元素的操作当前被禁忌的次数。如果禁忌表中该位置上元素为0，则表示此操作当前未被禁忌。在算法最开始的时候，禁忌表初始化为零矩阵。

5)禁忌长度。被禁忌的操作不允许被选取的最大次数。禁忌长度与染色体长度有关。禁忌长度记为Ltabu。

2.4.2 模拟退火算法

模拟退火算法(simulated annealing algorithm,SA)的寻优过程为，假定一个着火物体，其温度随迭代过程指数下降。每次迭代时，在当前解的邻域内随机搜寻可行解，利用Metropolis法则判断是否接受邻域内可行解，循环此过程直至算法收敛。

1)退火温度。SA中物体的温度，记为T。物体的退火温度T从初始温度T0开始，随迭代过程指数下降。

2)退温率。物体的退火温度的衰减速度K。物体温度的退温策略为T(n+1)=K·T(n)，其中n为迭代次数。K满足0

3)Metropolis法则。如果在当前解s0的邻域内搜寻到的可行解s1优于当前解，则以概率1接受s1作为新的当前解。如果s1劣于s0，则以一定概率p接受s1作为新的当前解。此概率p与当前的温度T以及s1，s0适应值的差有关，计算公式如下：

p=exp(ΔE/T)

(20)

式中:ΔE为s1与s0适应度函数的差值，且ΔE<0；T为当前系统的温度。

2.4.3 禁忌退火变异算法(TSSAM)

决定种群中某一个体是否参与变异的方法如下：生成随机数r，如果变异率大于r，那么对当前个体执行TSSAM操作。TSSAM步骤如下：

Step1对于每一个参与变异的个体x0，首先产生此个体的邻域解集。x0也称作禁忌搜索的初始解。随后将x0产生的邻域解按照从优到劣的顺序进行排列，记最优邻域解为x1。先将x1作为候选解。

Step2将候选解x1与初始解x0进行比较。如果x1的适应度函数值大于x0，执行step3。如果x1的适应值小于x0，执行step4。

Step3将x1作为x0变异后的个体传回到种群中，同时更新禁忌表。记由x0得到x1的方法为互换第i1,j1个基因位上的元素。更新禁忌表的方法为：对禁忌表中所有非零元素执行如下操作：

(21)

随后考虑下一个参加变异的个体，执行Step1。

Step4搜索x0的邻域解集中未被禁忌的最优解，将此最优解记为新的候选解x2。将x0与x2的目标优化函数值的差记为ΔE，ΔE<0。产生一个随机数r，如果满足exp(ΔE/T)>r，则接受x2作为变异后的个体传回到种群中，同时更新禁忌表，随后考虑下一个参加变异的个体，执行step1。记由x0得到x2的方法为互换i2,j2基因位上的元素。更新禁忌表的方法为对禁忌表中所有非零元素执行如下操作：

(22)

生成随机数r，如果满足exp(ΔE/T)

重复执行上述过程，直至种群完成变异。

当种群中的所有参与变异的个体变异完成以后，更新退火温度，即令T(n+1)=K·T(n)，开始种群下一代的迭代进化过程。

传统遗传算法的变异过程本质是从参与变异的个体的邻域解集内随机选择一个解作为变异后的个体，而这一变异过程往往具有随机性。与传统的变异过程相比，TSSAM引入禁忌搜索算法中的邻域解集，在邻域解集中寻找可行解。如果变异个体的邻域解集中的最优解优于此个体，那么接受最优解为变异后的个体；反之，则通过Metropolis法则以一定概率接受未被禁忌的最优解作为变异后的个体。

综上分析，TSSAM兼具禁忌搜索算法与模拟退火算法的优点，既能够扩大解的搜索范围，又能够利用Metropolis法则提升算法的寻优能力，极大改善了遗传算法的变异过程，加快了算法的收敛过程。

本文设计的TSSAM算法的流程图如图8所示。

图8 TSSAGA流程图

3 典型AEOS任务规划问题验证

本文通过仿真验证了禁忌退火遗传混合算法提出的禁忌退火遗传混合算法在AEOS任务规划问题中的有效性。

3.1 仿真参数设置

考虑AEOS如下参数,见表1。

表1 卫星参数

通过STK建立上述卫星的场景，在场景中随机生成若干个卫星可见的目标点，并为这些目标点随机指定1～10的任务优先级。这些目标点的范围为20°N～50°N，110°E～130°E。仿真时间从2020年3月24日04∶00∶00开始，到2020年3月25日04∶00∶00结束。通过STK可以解算出卫星对目标点可见的时间窗口。

为了充分验证算法的有效性，将禁忌退火遗传混合算法(TSSAGA)分别与禁忌遗传算法(TSGA)、退火遗传算法(SAGA)以及普通的遗传算法(GA)进行对比仿真实验。

综上所述，目前可确定的各算法参数见表2。

表2 确定的参数

3.2 仿真结果分析

本文设置了2组不同规模的对比仿真实验来验证TSSAGA在AEOS任务规划中的性能。第1组实验为从50个目标点中选20个目标点进行观测，即染色体长度N=20。上文中未给出的各个算法其他参数见表3。

表3 未确定的参数(目标点个数∶50)

第2组实验为从100个目标点中选50个进行观测，染色体长度N=50。各算法其他参数见表4。

表4 未确定的参数(目标点个数∶100)

为了尽可能详尽全面地比较算法的求解能力，每组对比实验中，每种算法进行50次蒙特卡洛仿真实验，随后比较算法的平均适应度函数值以及算法达到收敛的总耗时。算法收敛的判断标准为，连续15次迭代的最优解相同。对50个目标点进行规划的对比试验结果见表5。

表5 任务规划结果对比(目标点个数∶50)

为了进一步验证算法的有效性，将每种算法分别运算10组，每组进行50次蒙特卡洛仿真实验并取平均值，对比试验结果如图9所示。最优的观测序列见表6。对100个点进行规划的对比实验结果见表7。同样地，将每种算法分别运算10组，每组进行50次蒙特卡洛仿真实验并取平均值，对比试验结果如图10所示。最优的观测序列见表8。

图9 算法对比结果(目标点个数∶50)

表6 任务规划结果(目标点个数∶50)

表7 任务规划结果对比(目标点个数∶100)

图10 算法对比结果(目标点个数∶100)

表8 任务规划结果(目标点个数∶100)

综合表5与表7可知，求解相同规模的任务规划问题，TSSAGA收敛最快，且收益高于其他算法。相比于GA，TSAG和SAGA节省了20%～30%的运算时间，TSSAGA节省了约40%的运算时间。相比于传统遗传算法的变异过程，TSSAGA在变异过程中引入了禁忌搜索的方法以及Metropolis法则，极大地提升了算法的搜索效率以及寻优能力，节省了算法的收敛时间，有较高的工程应用价值。

4 结 论

1)面向敏捷对地观测卫星观测大规模地面点目标这一实际工程问题，考虑了卫星面临的多种约束条件，建立了对应的适应度函数。

2)改进了传统遗传算法的变异过程，提出了禁忌退火变异方法，此方法兼具了禁忌搜索算法与模拟退火算法的有点，提高了整个算法的寻优能力，加快了算法的收敛速度。

3)仿真结果表明，禁忌退火遗传混合算法与传统的遗传算法相比，节省了约40%的算法优化时间，大幅提高了智能优化算法求解敏捷对地观测卫星任务规划问题的求解效率。