基于遗传禁忌算法的多星协同任务规划方法

张泽华，张加友，张嘉凯，马松靖，李宇哲

(哈尔滨工程大学 航天与建筑工程学院，黑龙江 哈尔滨 150001)

0 引言

对地观测卫星利用星载传感器观测地面目标以获取关键信息，在大地测绘和自然灾害检测等多种应用场景中具有关键作用。随着对地观测应用的不断深入，任务需求量急剧攀升，同时多频次、多模式、多传感器等复杂观测需求也逐渐增多，很多情况下单一卫星无法完成这些复杂的观测需求。在此背景下，多星协同对地观测成为当前对地观测的主要方式[1-2]。

多星协同任务规划问题是一个多维多选的组合优化问题，目前主要采用智能优化算法解决此类问题。文献[3-5]基于蚁群算法对多星成像调度问题开展了研究，提出了一系列改进蚁群算法。文献[6]基于遗传算法引入向量编码，研究了新的交叉和变异算子、新的计算适应度方法以及保持最优个体的新方法。文献[7]设计了一种基于圈次进行交叉和变异的遗传算法，并与蚁群算法进行仿真比对，验证了其有效性。文献[8]利用蒙特卡洛法和双重停机条件对遗传算法进行了改进，提出了一种改进型自适应遗传算法，并通过实验表明了该算法在全局搜索能力和算法收敛速度方面的提高。文献[9]研究了双遗传算法与模拟退火算法、双蚁群算法与禁忌搜索算法2类求解方法，并通过实验数据证明了算法的有效性和适用性。文献[10]基于遗传算法设计了新的编码方式，开发了一种新型遗传算法进行求解对地观测卫星的调度问题。文献[11-12]提出了一种将高斯伪谱法与遗传算法相结合的混合方法，通过遗传算法生成规划调度的可行解，再用高斯伪谱法优化能量和时间。该混合方法在能量效率、计算效率和姿轨平滑方面具有优越性。

本文在上述研究基础上,提出了一种基于遗传禁忌算法的多星协同任务规划方法，该方法分为2个阶段：第1阶段为遗传搜索阶段，第2阶段为禁忌搜索阶段，兼具了遗传算法较强的全局寻优能力和禁忌搜索算法较强的局部寻优能力。同时，通过仿真验证了算法的稳定性和有效性。

1 多星协同任务规划问题模型

多星协同任务规划问题可概述为在指定场景时间内，根据用户提出的需求任务集合和卫星资源信息，通过规划调度给每个任务匹配满足约束的卫星观测时段，并保证卫星成像窗口不冲突。

由于一个任务可以被多颗卫星可见，且一颗卫星对一个任务的可见窗可能存在多个，即存在可见窗集合。假设卫星有n颗，任务有m个，那么可见窗个数为m×n，多星多任务可见窗集合如表1所示，卫星n对任务m的可见窗集合为Wmn。

多星协同任务规划问题就是基于表1中的多星多任务可见窗集合，通过任务规划得到合理的卫星观测方案。

表1 多星多任务可见窗集合Tab.1 Visible window collection for multiple multi-satellite missions

1.1 基本假设

多星协同任务规划问题涉及到的对象之间的关系复杂，并不能顾及到所有的具体细节和实际约束问题。在充分考虑到现实应用情况的基础上，本文对实际问题做出了如下的基本假设和简化：

① 假设观测目标都是预处理后的固定点目标；

② 假设卫星存储器的容量无限制；

③ 一般情况下，卫星能量约束用侧摆次数和总开机时间等标准来描述，本文采用最大观测任务数来描述；

④ 卫星姿态调整及稳定时间按照常数处理；

⑤ 假设每个任务只被观测一次，且每个任务的观测时长相同。

1.2 数学模型

多星协同任务规划问题的数学模型如下：

f=α×maxf1+β×maxf2+γ×maxf3，

(1)

(2)

(3)

(4)

(5)

SEj≤SMaxEj，∀j∈S，

(6)

STij,ETij∈Wij,∀i∈T,∀j∈S，

(7)

(8)

|CBij|≤SMaxCBj,∀i∈T,∀j∈S，

(9)

(10)

式(1)为优化目标函数，是由3个子目标加权建立。其中，α,β,γ分别为3个子目标的权重，且满足0<α<1,0<β<1,0<γ<1,0<α+β+γ<1。3个权重值可以根据具体任务需求自定义，在本文中，取α=0.7，β=0.2，γ=0.1。式(2)为子目标1，表示观测任务集合的总收益值最大；式(3)为子目标2，表示观测任务集合的总完成度最大；式(4)为子目标3，表示卫星集合的侧摆角之和最小，其中g(CBij)为侧摆角归一化函数，假设每颗卫星的最大成像侧摆角均为60°，则可设g(CBij)=2cos(CBij)-1。

式(5)表示每个任务最多被观测一次；式(6)表示卫星观测任务数应小于最大观测任务数，即本文中描述的能量约束；式(7)表示卫星观测任务的观测时段应在可见窗内；式(8)表示卫星观测任务集合中相邻观测任务之间应满足过渡时间约束；式(9)表示卫星进行任务观测时应满足卫星最大成像侧摆角约束；式(10)主要针对光学卫星，光学卫星观测任务时应满足太阳高度角约束。

2 遗传禁忌算法

2.1 基本思想

遗传算法[13-14]是于1975年基于进化生物学提出的，主要由初始化种群、遗传算子和适应度函数组成，遗传算子中包括交叉、变异和选择等。遗传算法具备较强的全局择优能力，但容易过早收敛。禁忌搜索算法[15-16]于1986年基于局部邻域搜索提出，主要由邻域结构、禁忌表和藐视准则等组成。禁忌搜索算法具有较好的局部搜索能力，但初始解的质量对其影响较大。

多星协同任务规划问题中任务成像观测时间解集搜索空间很大，本文综合遗传算法和禁忌搜索算法的优势，分2个阶段进行问题求解。第1阶段，利用遗传算法搜索效率较高的特点，采用遗传算法进行问题的初步求解；第2阶段，发挥禁忌搜索算法较强的局部搜索能力，并考虑初始解对禁忌搜索的影响，以遗传算法的优化结果为初始解，利用禁忌搜索算法对规划问题进行再次求解，从而得到更优的结果。

2.2 编码与个体可行性处理

2.2.1 编码

依据表1，将可见窗集合用一个矩阵M来表示，即：

(11)

基于式(11)中的矩阵，创建每个任务目标所对应的可见窗有序集合：M1,M2,…,MN,其中Mi=W1i∪W2i∪…∪Wni。给每颗卫星进行编号排序，每颗卫星的可见窗按照可见开始时间排序，在整个计算过程中顺序固定不变。由此，可以令个体染色体的维度为二维，第一维表示观测任务的卫星，第二维表示该卫星观测任务的观测开始时间，并且分别用卫星序号和观测开始时间位置序号进行表示。由于卫星观测任务的可见窗可能由多个不连续的可见弧段组成，所以需要将可见窗连续化进而得到卫星观测任务的观测开始时间位置序号，如图1所示。

图1 可见窗连续化示意Fig.1 Visible window continuity

假设卫星对目标的可见窗有3个，第1个开始时间为0，结束时间为2，可见时长为2；第2个开始时间为5，结束时间为10，可见时长为5；第3个开始时间为15，结束时间为18，可见时长为3。根据可见时长的比例进行连续化，若观测开始时间位置为4，则对应第2个窗口的时间位置为7。

根据上面的描述，通过编码产生的染色体可以表示为：

D={(x1,y1),(x2,y2),…,(xm,ym)}，

(12)

式中，xi= 0,1,2,…,n表示对任务Ti进行观测的卫星序号；yi=0,1,2,…,l表示该卫星观测任务Ti的观测开始时间位置序号。根据前述假设可知，每个任务最多被观测一次，所以若xi取值为0，就表示该任务不被观测。

2.2.2 个体可行性处理

为保证个体满足约束条件，需要对其进行可行性处理，该处理是针对个体中的每一个任务进行如下操作：

① 卫星能量约束判断。判断该任务所选观测卫星是否满足式(6)，若不满足，则进行卫星序号突变，再重新判断，直至挑选出满足该约束的卫星。若所有可见卫星都不满足该约束，则将该任务的观测卫星序号置为0。

② 卫星相邻任务时间窗口冲突判断。判断该任务的观测时段是否满足式(8)，若不满足，则进行观测开始时间位置序号突变，再重新判断。可见窗长度远大于成像时长，因此存在大量观测开始时间位置序号突变结果，本文设定观测开始时间位置序号突变次数上限，若其突变次数达到该上限仍未找到满足约束的观测时段，则进行卫星序号突变。若所有可见卫星的可见窗突变在达到突变次数上限时都未找到满足约束的观测时段，则将该任务的观测卫星序号置为0。

③ 卫星侧摆角约束判断。判断该任务所选观测卫星是否满足式(9)，若不满足，则依照第②步中的先突变观测开始时间位置序号后突变卫星序号的方法进行处理。

2.3 遗传搜索阶段

基于式(6)染色体结构，随机初始化种群，并对种群中个体进行可行性处理。设定迭代次数，对种群进行遗传迭代，每代种群的个体都需进行可行性处理，直至达到迭代次数，输出最优个体，即为遗传搜索阶段优化结果。遗传搜索阶段流程如图2所示，图中符号Pm表示变异概率。

图2 遗传搜索阶段流程Fig.2 Genetic search phases

2.3.1 交叉算子

将种群中的个体进行两两随机配对形成父代和母代染色体，父代和母代染色体通过部分基因片段的交叉产生子代个体。染色体交叉示意图如图3所示，随机选取2个整数index1和index2，并满足0

图3 染色体交叉示意Fig.3 Chromosomal crossover

2.3.2 变异算子

根据本文的编码方式，变异算子包括卫星序号突变和观测开始时间位置序号突变2种。

观测开始时间位置序号突变示意图如图4所示，若个体染色体在index1和index2处发生观测开始时间位置序号突变，则从连续化可见窗结果中随机突变新的观测开始时间位置序号。

图4 观测开始时间位置序号突变示意Fig.4 Observation start time position sequence number mutation

卫星序号突变示意图如图5所示，若个体染色体在index1和index2处发生卫星序号突变，首先判断突变处基因是否还存在其他可见卫星，若存在，选择新的可见卫星，同时选择新的观测开始时间位置序号，若不存在，将卫星序号置为0，即该任务不被观测。

图5 卫星序号突变示意Fig.5 Satellite number mutation

2.3.3 选择算子

本文采用锦标赛方法与双败淘汰制的结合进行选择。假设子代与父代个体形成的混合种群个体总数为N0，选择后新一代种群个体数为N。将所有个体随机分成10组，每组采用锦标赛方法将前N/10名判定获胜进入胜者组，其余个体进入败者组。败者组中采用锦标赛方法将前N/2名判定复活进入复活组，其余个体判定最终失败进行淘汰。胜者组中同样采用锦标赛方法将前N/2名判定最终胜利进入胜利组，后N/2名进入复活组。最后，复活组的所有个体争抢最后的N/2个名额，争夺方式依旧是锦标赛方法，将前N/2名判定最终胜利进入胜利组。至此，选择算子操作结束，胜利组即为新一代种群，具体操作流程如图6所示。

图6 选择算子操作流程Fig.6 Selection operator workflow

2.4 禁忌搜索阶段

禁忌搜索算法的初始解可以随机产生，但其初始解的优劣对搜索的性能影响较大。因此，本文将遗传搜索阶段的优化结果作为初始解进行禁忌搜索。禁忌搜索阶段流程如图7所示。

图7 禁忌搜索阶段流程Fig.7 Tabu search phases

2.4.1 邻域结构

邻域结构是指由当前解通过邻域函数产生另一个解的方式，通过邻域函数产生的解会有多个，这些解构成当前解的邻域解集。邻域结构的设计方法有很多，并且针对不同的问题会有不同的邻域结构设计方法。在本文中以遗传算法中的染色体为初始解的结构，由此设计出一种类似于遗传算法中变异算子的邻域结构，如图8所示。

图8 邻域结构示意Fig.8 Neighborhood structure

首先随机选择变异任务编号，其次选择变异该任务的可见卫星编号，最后选择变异该可见卫星的观测开始时间位置序号。

试验地设在建三江胜利农场科技园区；土壤情况为草甸白浆土；土壤养分含量：速氮：182m/kg，速磷：32.2mg/kg，速钾：67mg/kg，有机质 35.5mg/kg，PH 值 5.4.

2.4.2 禁忌表

本文中邻域结构设计时考虑了变异任务编号、变异任务的可见卫星编号、变异可见卫星的观测开始时间位置序号，因此本文基于禁忌长度和上述3个变异序号进行设计禁忌表，禁忌表结构如下：

TabuL={(a1,b1,c1,d1),(a2,b2,c2,d2),…,(aL,bL,cL,dL)}，

(13)

式中，L表示禁忌表中存储的禁忌解的个数；ai=1,2,3，…，T表示当前禁忌解的禁忌长度，T为初始禁忌长度；bi=1,2,…,m表示染色体上选择变异的任务位置编号，m为任务个数，即染色体上的基因个数；ci=1,2,…,nvs表示所选定任务选择变异后的卫星编号，nvs为任务的可见卫星个数；di=1,2,…,l表示所选定卫星选择变异后的观测开始时间位置编号。

2.4.3 藐视准则

当通过邻域结构生成的候选解属于禁忌表中的禁忌解时，需要进行藐视准则判断。判断准则如下：若该禁忌解优于当前最佳解则视为该禁忌解藐视禁忌准则，可以将其解禁，并将其更新为当前解和当前最佳解；否则该禁忌解无法藐视禁忌准则，无法解禁。

3 仿真验证

3.1 仿真场景设置

本文仿真场景中仿真时长为1 d。设置了4颗卫星，4颗卫星除了轨道倾角不同外，其他参数一致，具体参数值如表2所示。设置了7种观测任务群规模，任务群规模分别为100，150，200，250，300，350，400，不同规模任务群均为在全球范围内随机生成。

表2 卫星参数Tab.2 Satellite parameters

3.2 算法稳定性测试

针对规模为300的任务群，本文通过种群数分别为150，200，250的3种情况进行算法求解来对算法的稳定性进行测试，得到3种情况下种群最优个体适应度曲线，测试结果如图9所示。

由图9可以看出，种群数分别为150，200，300三种情况下，最优个体适应度收敛的迭代次数不同，随着种群数增加，收敛的迭代次数增加，但均在50次迭代之内收敛。同时，在迭代过程中每次迭代的适应度值不同，但3种情况下最终收敛的适应度值相近。由此可以说明,不同种群数下，算法求解的种群最优个体适应度相近，验证了算法的稳定性。

图9 不同种群数适应度曲线Fig.9 The fitness curve of different population numbers

3.3 不同任务群规模仿真比对

本文对7种不同规模的任务群进行仿真测试，测试中种群数量为200，迭代次数为400，得到每一种规模下种群最优个体适应度曲线、最优个体总收益值曲线、最优个体总完成度曲线以及最优个体总侧摆角曲线，仿真结果如图10～图13所示。

图10 不同任务群规模适应度曲线Fig.10 The fitness curve of different task group scales

图11 不同任务群规模总收益值曲线Fig.11 The total revenue value curve of different task group scales

图12 不同任务群规模总完成度曲线Fig.12 The total completion degree curve of different task group scales

图13 不同任务群规模总侧摆角曲线Fig.13 The total roll angle curve of different task group scales

本文中数学模型的优化目标函数由总收益值、总完成度以及总侧摆角值3个子目标组成，为了对上述适应度曲线的分析结果进行进一步验证，对不同任务群规模的总收益值、总完成度以及总侧摆角值进行分析。该仿真场景中卫星最大侧摆角为60°，因此式(4)中侧摆角归一化函数设为g(CBij)=2cos(CBij)-1。

图11、图12和图13分别为不同任务群规模总收益值曲线、总完成度曲线和总侧摆角曲线。

由图11和图12可以看出，前3种任务群规模的总收益值和总完成度相近，且大于后4种任务群规模。因此，图10中前3种任务群规模的最终收敛适应度值相近，且大于后4种任务群规模，与前面采用场景可完成任务数阈值分析的结果一致。由这3幅图可以看出其曲线变化趋势与图10一致，7种任务群规模均在迭代150次后达到最优，且随着任务群规模增大，总收益值、总完成度和总侧摆角递减。

由此，将规模为300的任务群的优化目标函数值及其3个子目标函数值进行分析，如图14所示。由图14可以看出,3个子目标函数值变化趋势及适应度值的变化趋势一致，同时适应度曲线较靠近总收益值曲线，该结果主要由于本文中子目标总收益值的权重占比较大。

图14 任务群规模300的优化目标值曲线Fig.14 The optimization objective function value curve of the task group size of 300

4 结束语

任务规划是多星协同对地观测研究中的关键点，规划结果的优劣直接关系着卫星资源的利用效率和观测任务的执行质量。针对多星协同对地观测中的任务规划问题，提出了一种基于遗传算法和禁忌搜索算法的多星协同任务规划算法。该方法利用遗传算法实现优化问题的初步求解，完成全局解空间的搜索；将遗传算法求得的初步解作为输入，利用禁忌搜索算法实现优化问题的进一步求解，完成局部解空间的细致搜索。所提出的方法综合了遗传算法全局寻优和禁忌搜索算法局部寻优的优势，解决了多星协同对地观测的任务规划问题。通过不同种群数下的仿真测试验证了算法的稳定性，通过不同任务群规模的仿真验证了算法的有效性。