应用改进多种群遗传算法的多星成像目标规划方法

张曼利 章文毅 马广彬 樊慧晶

(1 中国科学院空天信息创新研究院，北京 100094)(2 中国科学院大学，北京 100049)

随着近年来卫星遥感应用到各个领域[1-2]，人们对遥感影像数据的需求急剧增长。在卫星资源相对有限的条件下，研究如何充分利用现有卫星资源，给卫星合理安排成像目标序列，对多颗卫星协同规划，充分利用每颗卫星的观测能力，对遥感应用具有重要的作用。多星成像规划问题是研究对于点目标或者区域目标来说，在一定的成像时间周期内如何统筹多颗卫星对目标区域进行观测。对每颗卫星来说，如果在指定的时间周期内能飞过该目标区域，会对该目标区域产生一个或多个成像条带(卫星上带有多个遥感器)，对于多星观测区域会产生一个更大的条带集合，在多星观测的条带集合中如何规划出一个较优的组合方案，就是多星成像规划需要解决的问题。

目前，在卫星成像目标规划问题的模型和求解算法上已经取得一定成果。求解模型有背包模型[3]，以最大化时间覆盖率和最大化空间覆盖率建立时间分辨率优先、空间分辨率优先两种模型[4]，约束满足问题模型[5-6]，以及将最大化成像目标数量和目标优先级作为优化目标建立的任务组合优化模型[7]。求解算法有禁忌搜索算法[3,5，8]、贪婪算法[4]、遗传算法[4-5]、模拟退火算法[5]、基于基因表达式的改进遗传算法[6]和超启发式算法[7]。这些算法大都是智能优化算法[9]，容易陷入局部最优解，且对于大区域目标及时间周期较长的情况不能尽快规划出较优的成像方案。同时，对于文献[4-5]中使用的遗传算法，当成像目标区域较小时，解空间的规模较小，遗传算法比较适用；但是对大区域目标成像时，在解空间规模较大的情况下，遗传算法不能有效地规划出较优的成像方案。

为了有效解决上述问题，本文提出改进多种群遗传算法的多星成像目标规划方法。根据目标函数和约束规则建立模型，利用改进的多种群遗传算法对模型进行求解，采用移民算子种群在多种群之间关联及更新种群；移民算子种群保留每一次进化中所有种群中的部分最优成像方案，然后和每次进化中所有种群进行对比置换，保留每代进化中的最优成像方案，防止算法每次进化过程中最优成像方案丢失，从而针对多星区域目标能够有效地规划出目标函数较优的成像方案。

1 模型设计

对于多目标来说，考虑卫星的侧摆能力，卫星只有飞临目标上空时才有可能对目标进行成像。对于2个目标，如果成像时间窗口发生重叠，因为1个时间窗口只能观测1个目标，所以只能选择1个目标成像。如图1所示，对于观测目标1，2，3，4来说，因为目标1和目标2、目标3和目标4成像时间窗口重叠，所以只能选择其中的2个目标进行成像，例如目标1和目标3。

图1 目标成像时间窗口Fig.1 Target imaging time windows

对于点目标来说，卫星一次过境就可满足成像，但是对于区域目标来说，单星的幅宽和分辨率很难在短时间周期内完成对区域目标的成像覆盖，而采用多星联合对区域目标进行成像，则可以很好地满足短时间周期内对区域目标进行成像覆盖的要求。文献[4]模型约束条件中没有考虑成像目标重复观测的情况，文献[5-6]模型约束条件中没有考虑卫星遥感器最大开机时长和开机次数限制约束条件，文献[10]中对点目标进行研究，并没有对区域目标进行分析。对于单个区域目标来说，如果卫星的拍摄幅宽无法覆盖观测区域，就需要首先对区域进行划分，分解成多个成像条带，每个成像条带相当于点目标，相当于对多个点目标进行成像规划。对目标成像观测来说，如果使用不同的卫星，相同的分辨率，可能会出现对该目标中的条带重复观测，为了避免这种情况，设定每个条带至多被成像1次，且必须在某颗卫星的可见时间窗口内成像。考虑轨道覆盖会出现重复观测，为了尽可能地均分轨道，设定单个轨道只能开机1次，即对于成像目标划分的条带来说，不同的条带对应的成像卫星轨道不能相同。考虑卫星姿态转换需要时间，设定姿态转换时长限制。根据实际应用中的卫星测控规划需求，考虑到卫星能量和卫星存储容量的限制，采用卫星遥感器最大开机时长和开机次数约束设计规则，使模型更具有实际应用价值。本文针对单个区域目标的多星成像规划问题进行研究，对于单个目标区域来说，卫星遥感器开机时长比较短，开机次数也比较少，可以满足最大开机时长和开机次数约束。

为了便于模型的建立及求解[10]，本文将成像条带作为模型的数据输入。它包含卫星标志、轨道号、遥感器型号、成像范围、成像模式、成像时间和侧摆角等重要信息。在研究区域目标多星成像时，需要进行卫星轨道的计算。本文卫星星下点的位置和速度使用简化常规摄动(SGP4)模型和卫星的两行轨道根数(TLE)计算。根据目标区域，通过卫星轨道计算结合卫星侧摆角能力计算出所有可能的成像条带。成像方案由条带组成，在选取条带组成成像方案时，需要考虑一定的约束条件。

问题优化目标如式(1)～(3)所示。式(1)表示成像规划方案周期最短；式(2)表示成像规划方案覆盖率最大；式(3)表示把成像规划方案周期和覆盖率采用加权和计算成像规划方案综合收益。考虑到实际应用中的用户需求往往是近期尽快安排观测，目标区域要尽快地满足覆盖。考虑时间成本较低和任务完成率较高的情况，设置在时间周期较短、规划方案覆盖率较大情况下的合理规划方案，即成像规划方案中卫星拍摄的周期最短，对观测区域1次拍摄的覆盖最大，这样成像规划方案综合收益最佳。式(1)中成像规划方案周期最短目标函数要保证周期最短，同时要考虑该方案的覆盖率大小因素，如果只考虑周期最短为收益指标，可能会出现该成像规划方案的覆盖率非常低，因此采用方案覆盖率作为一个权值来平衡成像周期最短目标函数的收益函数。

问题约束规如式(4)～(9)所示。式(4)表示当卫星飞临目标的时间段内都可以对目标成像，为了避免不同的卫星对该条带重复观测，限定每个观测条带至多被成像1次，即条带i至多有1个成像时间窗口。式(5)表示观测条带如果被成像，任意条带的成像时间区间必须在某颗卫星的可见时间窗口内。式(6)表示不同的条带对应的成像卫星轨道不能相同。式(7)表示对于不同的观测条带来说，卫星遥感器成像需要转换姿态角，即2个相邻条带的成像时间间隔需要大于姿态转换时长,成像规划方案里所有条带按照成像时间窗口的开始时间排序，参考图1，对于相邻条带来说，成像时间窗口不能重叠，因此1个时间窗口只能观测1个条带。式(8)表示遥感器开机的持续总时间要小于最大开机时长。式(9)表示遥感器开机次数要小于最大开机次数。

(1)

(2)

(3)

yijr≤1

(4)

(5)

Oi≠Ok

(6)

fi+ti,i+1

(7)

(8)

npt

(9)

模型中式(1)～(9)的符号释义如下。条带序号i=1,2,3,…,nb，nb为条带总数；Ci为成像条带Bi的覆盖率，其中，Bi为成像规划方案里的所有条带集合B(所有条带按照成像时间窗口的开始时间排序)里面的任意条带；Tstart和Tend分别为成像规划输入的起始时间和结束时间，Ttstart和Ttend分别为成像规划方案的实际起始时间和实际结束时间；v1和v2分别为成像周期和成像区域覆盖率对应的权值；成像条带Bi在卫星Sj的第r个时间窗口成像时，yijr取值为1，否则为0，其中，Sj为卫星集合S里面的任意卫星，卫星序号j=1,2,3,…,ns，ns为卫星总数，成像窗口序号r=1,2,3,…,nij，nij为卫星Sj对成像条带Bi的可行成像时间窗口总数；bi和fi分别为条带Bi的实际成像开始时间和实际成像结束时间；wijr,s和wijr,e分别为条带Bi在卫星Sj的第r个时间窗口的开始时间和结束时间；Oi为条带Bi对应的轨道号，Ok为条带Bk对应的轨道号，其中，i≠k，k=1,2,3,…,nb；ti,i+1为条带Bi到后续条带Bi+1的姿态转换时长；bi+1为条带Bi+1的实际开始成像时间；tm,ps和tm,pe分别为遥感器第m次开机时间和关机时间，其中，m=1,2,3,…,npt，npt为遥感器开机总数；lpt为遥感器最大开机时间；NPT为遥感器最大开机次数。

2 改进的多种群遗传算法求解过程

2.1 算法框架

改进的多种群遗传算法源于遗传算法，设置生成多种群协同进化，每个种群随机生成不同的交叉概率和变异概率，提高对观测目标最优成像方案的搜索能力，避免算法的进化过程较早收敛。同时，加入移民算子种群在多种群之间进行关联及更新种群，移民算子种群保留每次进化中所有种群中的部分最优成像方案，然后和每次进化中所有种群进行对比置换，保留每代进化中的最优成像方案。利用精华种群中适应度最大的成像方案的最少保持代数作为终止判据，比遗传算法中设定1个最大进化代数作为终止判据更加有效，使收敛速度得到提高。

2.2 算法调度流程

改进的多种群遗传算法中种群的个体代表每个成像方案，个体的适应度函数代表模型中的目标函数，种群是由若干个个体组成，个体中的基因代表相对应的过境轨道产生的条带集中被选中的条带。每个过境轨道集包含多个过境轨道，且过境轨道相互冲突，所以选择其一参与成像。采用二进制编码方式，1位二进制编码代表1个成像条带，编码为0时表示该条带没有被选中，编码为1时表示选择该条带加入成像方案，成像方案由1个二进制串组成。算法详细设计求解流程见图2。

图2 算法流程Fig.2 Algorithm flow

(1)每次随机生成的成像方案需要判断方案中的所有条带是否满足约束规则式(4)～(9)，满足所有的约束规则后该方案才会被保留下来。

(2)初始化移民算子种群，即从n个种群中选择适应度最大的成像方案复制到初始移民算子种群中。

(3) 对n个种群随机产生交叉概率(Pc)和变异概率(Pm)。不同的Pc和Pm值对算法的搜索能力不同。

(4)采用轮盘赌选择个体。2个个体进行交叉时，被选中交换的二进制编码位代表1个条带，交换时不仅要把二进制编码段进行交换，还要把二进制码代表的条带信息进行交换。

(5)移民算子种群在多种群之间进行关联及更新种群，n个种群经过选择、交叉、变异后，把迭代过程中的每个种群Ax(x=1,2,3,…,n)和移民算子种群B比较成像方案的适应度值。若发现种群Ax中最优成像方案优于移民算子种群B中的最优成像方案，则把种群Ax中所有优于移民算子种群B中最优成像方案的成像方案加入到移民算子种群B中；否则，把移民算子种群B中所有优于种群Ax中的成像方案置换掉种群Ax中的最差成像方案。该过程可以保证每次产生的较优染色体被保留下来[6]，保证多种群共同进化。

(6)通过人工选择算子模块保存每个种群中适应度最大的成像方案及编码，放到精华种群中。

(7)最后判断精华种群中适应度最大成像方案的保持代数是否满足收敛条件，如果满足收敛条件，则输出精华种群中适应度最大的成像方案，否则，转到(4)。

3 试验验证与分析

本文使用NetBeans软件及Java语言编程实现卫星成像任务规划方法。改进的多种群遗传算法设置3个种群进行寻优求解，在[0.7,0.9]内随机产生Pc，在[0.001,0.300]内随机产生Pm。

为验证改进的多种群遗传算法进化过程的收敛效率，分别对遗传算法和改进的多种群遗传算法进行进化过程对比试验，对同一个目标区域分别进行5次试验，选择成像规划方案覆盖率最大目标函数收益值作为对比标准。目标函数收益值范围区间是[0,1]，最大收益值为1，试验设置GA进化500代，设置MPGA进化50代，试验对比结果如图3和图4所示。

由图3遗传算法的5次进化过程试验可以看出：5次试验的平均收益值都不相同，进化过程不稳定，且第1次试验和第5次试验进化500代后仍然没有稳定下来，收敛速度比较慢，第2～4次试验虽然在200代附近收敛，但是收敛值并不理想，导致过早的收敛。观察5次试验进化过程曲线可以看出：遗传算法得出的收益值并不是逐渐增长的曲线，这是因为遗传算法在进化过程中没有保留每代进化中的最优成像方案，容易丢失最优解。由图4改进的多种群遗传算法的5次试验结果可以看出：进化过程比较稳定，平均在20代以内收敛，并且5次收敛时的收益值都比较理想，5次试验曲线呈现稳定上升，这是因为移民算子种群模块保留了每代进化中的最优成像方案，子代种群进化是在父代种群的最优值基础上继续寻优，所以最终收敛值比较理想。可见，综合比较分析，改进的多种群遗传算法比遗传算法收敛进程快，且收敛值更优。

图3 遗传算法进化过程试验Fig.3 Genetic algorithm evolution process test

图4 改进的多种群遗传算法进化过程试验Fig.4 Improved multi-population genetic algorithm evolution process test

为验证改进的多种群遗传算法求解模型中成像规划方案周期最短、覆盖率最大目标函数的性能，与遗传算法[5]作对比分析。选取5个目标区域,成像卫星为昴宿星-1a，1b(Pleiades-1a,1b),成像时间在2020-04-01T00:00:00-2020-04-15T00:00:00。考虑到遗传算法的不稳定性，改进的多种群遗传算法和遗传算法均对每个区域做10次试验，最后取平均值作为收益结果进行对比。选择成像规划方案覆盖率最大和成像方案周期最短2个目标函数收益值作为对比标准，为了更直观地对比不同目标区域调用2种算法得出的成像方案的覆盖率和成像周期目标函数，分别将结果整理为图5和图6。

图5 成像方案覆盖率收益对比Fig.5 Benefit comparison of imaging scheme coverage

图6 成像方案周期收益对比Fig.6 Benefit comparison of imaging scheme time period

从图5和图6可以看出：改进的多种群遗传算法在成像规划方案覆盖率和成像周期目标函数上都优于遗传算法。在改进的多种群遗传算法的迭代计算过程中，因为设置生成多种群进行进化，每个种群随机生成不同的交叉概率和变异概率，每次进化过程中的所有种群和移民算子种群进行置换更新，在保留较优成像方案编码方案时，多个种群协同进化寻优；遗传算法则容易出现过早的收敛，收敛结果并不理想(参见图3和图4)，因此，改进的多种群遗传算法得出的规划方案结果优于遗传算法。本文多星成像目标规划方法能够较好地适应对模型的求解，在有效的成像时间内规划出比较理想的成像方案，适用于多星成像目标规划问题。

4 结束语

卫星成像规划问题的研究对于遥感应急应用等方面具有重要意义。本文面向区域目标进行求解，以目标成像时间周期最小和目标成像覆盖率最大为目标函数建立模型，加入移民算子种群，保证各个种群之间进行对比关联及协同寻优，以保留较优的成像方案。试验结果表明，改进的多种群遗传算法求解精度优于遗传算法，稳定性较佳，能较好地解决卫星成像任务规划问题。后续会进一步改进算法的性能，更加全面地考虑卫星实际约束情况，以及对于紧急任务的插入处理规则；同时，针对具备俯仰角姿态机动能力的卫星，研究在具有更加灵活的观测角情况下如何更好地协同多颗卫星进行规划成像。