基于超启发式的多星协同任务规划算法研究

陈金勇，张 超，李艳斌

(1. 中国电子科技集团公司航天信息应用技术重点实验室，石家庄 050081； 2. 中国电子科技集团公司第五十四研究所，石家庄 050081)

0 引 言

卫星对地观测任务是利用其携带的光电遥感器或无线设备等有效载荷，从太空轨道上捕获地面、海面和低空的重要目标信息并将信息传回地面接收站，如图1所示。卫星具有轨道高、探测范围大、周期性强等特点，是执行各类对地观测任务的主要平台。但卫星在执行任务的过程中，受到机动能力受限、时间窗口固定等约束，如何给卫星分配合理的任务列表，以充分利用星上载荷执行各类任务，是卫星任务规划研究中的主要问题之一。目前针对卫星任务规划问题的研究在系统建模技术和求解算法上取得了一定的成果。其中系统建模技术以混合整数规划[1]、约束满足模型[2]、多Agent技术[3-4]最为常见，前者主要运用数学规划方法对确定性、静态环境下的多任务规划问题进行建模，后者将多个卫星或卫星群刻画成多Agent系统，从而利用多Agent技术实现多星、动态环境下的任务规划系统建模；求解算法以遗传算法[5-6]、蚁群算法[7-8]、粒子群算法[9]等并行程度较高的亚启发式算法最为常见。

图1 卫星观测与下传示意图

经典优化算法和智能算法的搜索空间是问题解空间，而超启发式算法的搜索空间对象是各种经典的优化算法、启发式算法和智能算法。文献[10]指出超启发式算法是一种高层次启发式方法，能够对底层一系列算法进行管理和调度，并从中选择合适的算法求解问题，而且还可以生成新的启发式算法求解问题。经典优化算法和智能算法无法根据问题的规模确定算法的参数范围，以及选择其它算法协调求解优化问题。文献[11]认为超启发式算法的框架由两层组成，底层是求解实际优化问题的启发规则、各种经典算法以及智能算法；高层负责底层算法的管理与调度。根据计算结果反馈机制，高层算法管理与调度机制又可划分为在线学习、离线学习以及无监督学习[12]。文献[13]运用蒙特卡洛超启发式算法就考试日程安排问题进行了求解，通过线性和指数概率函数选择底层算法。实验结果表明，蒙特卡洛超启发式问题求解效果比现有的智能算法更好。

因此本文针对常规多星对地观测任务规划算法适应性弱、鲁棒性差,难以适应实际工程需要的问题，采用超启发式算法(Hyper-Heuristic Algorithm)的思路，研究一种新的算法应用框架对多种算法的管理和调度，研究超启发式多星对地观测任务规划模型和求解方法。

1 多星协同任务规划调度模型

采用多个不同类型的遥感卫星，实施分布式观测，能够以多尺度的时间、空间、谱段分辨率获得多时段、多重空间覆盖、多谱段、多极化的目标电磁特征信息。这些信息能够相互验证和互补，减少目标特征理解的不确定性，增加特征提取的全面性和精确性。通过适用的多源信息融合理论和技术，可达到对目标的综合感知，大幅度提高识别能力、定位精度能力。

1.1 参数定义及变量说明

1.2 多星协同任务规划组合优化模型

max:∑(TkPk+Tk)

s.t.

(1)

∀Sj∈S,v∈Ij

(2)

∀sj∈S,iu∈Ij,iv∈Ij

(3)

∀sj∈S,ik∈Ij,r=1…nkj

(4)

∀sj∈S,ik∈Ij,r=1…nkj

(5)

∀sj∈S,ik∈Ij,r=1…nkj

(6)

∀sj∈S,ik∈Ij,r=1…nkj

(7)

∀sj∈S,ik∈Ij,gl∈G

(8)

∀sj∈S,ik∈Ij,gl∈G

(9)

(10)

(11)

其中：目标函数表示问题求解应使得调度方案的收益最优，即安排观测的成像任务优先级和成像任务安排数量最大。式(1)说明成像任务如果被执行，只能在与某颗卫星的某个可行时间窗口内完成。式(2)说明为所有成像任务如果被执行必定有唯一的前驱任务和后继任务。式(3)说明了任一卫星执行的相邻成像任务之间的时间推进关系。式(4)和式(5)说明成像任务如果在与某颗卫星的某个可行时间窗口内执行，任务的起止时间不能超出时间窗口范围。式(6)和式(7)说明成像任务如果被执行，那么其起止时间必须在用户指定的有效期之内。式(8)说明任意任务的观测时间早于其数据传输时间；式(9)：说明卫星观测动作与数据传输动作之间不能在时间上冲突；式(10)说明了在指定时长时间段内，卫星累计开机时间不超过给定的最大值。式(11)说明了任意时刻星载存储器占用不能超过卫星的存储容量上限限制。

2 超启发式算法的实现

2.1 算法框架

超启发式算法底层包括求解问题描述和用于求解问题的各种算法集合H={H1,H2,…,Hn}两部分；高层由算法调度、算法选择以及可接受解等三个功能组件构成。超启发式算法框架如图2所示。

图2 超启发式算法的实现

算法调度组件，包括：(1)爬山算法，可以看作为局部邻域搜索算法，用于评价候选解的质量，目标是产生较好的候选解；(2)变异算法，用于产生新的解空间；(3)用于评价算法的执行效率的CPU运行时间；(4)算法选择与算法学习机制等。

2.2 算法调度流程

算法调度流程说明如下：

步骤1：进行初始化设置，设置超启发式算法运行时间T、精英算法best_heuristic、算法运行效力评价因子α=0.5、算法选择评价因子γ=0.5、当前解current_solution、优化目标适应度值fitness_change等；

步骤2：生成问题的初始解，并作为当前解current_solution；

步骤3：计算底层算法集中各个算法的评价值E(hi)，i=1,2,…,m，有m个底层算法；

该步骤主要从算法的求解效果和算法的运行效率两方面对算法进行评价，算法评价函数为：

E(hi)=e1(hi)+e2(hk,hi)+e3(hi)

(12)

(13)

(14)

(15)

步骤4：选择底层算法集中评价值最大的算法作为精英算法；

步骤5：运用精英算法对多星对地观测任务规划问题当前解进行优化，得到新解new_solution以及精英算法的运行时间t(hi)；

步骤6：用新解减去当前解得到优化目标适应度值fitness_change，并将新解作为当前解current_solution=new_solution；

步骤7：修改e1(hi)、e2(hk,hi)、e3(hi)函数；

步骤8：修改算法运行效力评价因子α和算法选择评价因子γ；

(16)

γ=1-α

(17)

步骤9：判断超启发式算法运行时间是否达到设置的最大运行时间，若没有达到，则跳到步骤3；否则，计算将当前解作为多星对地观测任务规划最优解。

上述步骤的基本流程如图3所示。

图3 算法调度流程

3 仿真实验结果及分析

考虑到目前底层算法有两类四种即双染色体遗传算法、双蚁群算法、模拟退火算法以及禁忌搜索算法。从算法的种群规模分类，双染色体遗传算法、双蚁群算法属于群类算法，而模拟退火算法以及禁忌搜索算法属于单解算法。因此，超启发式算法对底层算法的调度规则是宽度搜索算法优先，然后是运行深度搜索算法。针对本次仿真实验，首先是运行双染色体遗传算法或双蚁群算法，对问题解空间进行规模搜索，获得较好的解。然后运行模拟退火算法或禁忌搜索算法对当前解进行深度搜索，最终求出问题满意解。

(1)双染色体遗传算法与模拟退火算法

对遗传算法的参数设置如下：种群规模200、交叉概率0.9、变异概率0.1、迭代次数1000。模拟退火算法参数设置如下：初始温度200、内循环1000、外循环200、温度衰减率0.95。当双染色体遗传算法求解问题的迭代数到达设定的阈值或解的改善程度低于设定的阈值时，启用模拟退火算法对双染色体遗传算法当前解进行深度搜索。

通过对观测任务数分别为50、100、150以及200等4个不同规模算例，分别用超启发式算法和模拟退火算法各自运行10次。两种算法的而平均运行时间和目标函数平均值如表1所示。

表1 超启发式算法与模拟退火算法运行时间和目标函数值比较

表7显示超启发式算法和模拟退火算法对4种不同规模算例进行计算,比较两个算法的平均运行时间和目标函数平均值。超启发式算法运行时间较长，但是超启发式算法中的禁忌搜索算法平均运行时间低于单独运行禁忌搜索算法平均运行时间。

图4和图5表明超启发式算法求解问题效果优于模拟退火算法，但是超启发式算法运行时间较长。超启发式算法中的模拟退火算法求解问题目标函数平均值优于单独运行模拟退火算法求解问题目标函数平均值。这是因为独自运行模拟退火算法，初始解较差算法必须花费较长的时间对问题解空间进行搜索，而且容易陷入局部最优解。而超启发式算法先运行遗传算法，对问题解空间首先进行宽度搜索，获得较好的解作为下一个优化算法的初始解，而后继的模拟退火算法在当前解的基础上，对问题解空间进行深度搜索，容易获得问题满意结。

图4 超启发式算法与模拟退火算法目标函数平均值比较

图5 超启发式算法与模拟退火算法运行时间比较

(2)双蚁群算法与禁忌搜索算法

双蚁群算法和禁忌搜索算法的相关参数设置同第六章。当双蚁群算法求解问题的迭代数到达设定的阈值或解的改善程度低于设定的阈值时，启用禁忌搜索算法对双蚁群算法当前解进行深度搜索。两种算法的而平均运行时间和目标函数平均值如表2所示。

表2表明超启发式算法对4种不同规模算例进行计算,平均运行时间较长。但是超启发式算法中的禁忌搜索算法平均运行时间低于单独运行禁忌搜索算法平均运行时间。

表2 超启发式算法与禁忌搜索算法运行时间和目标函数值比较

图6和图7表明超启发式算法求解问题效果优于禁忌搜索算法，但是超启发式算法运行时间较长。超启发式算法中的禁忌搜索算法求解问题目标函数平均值优于单独运行禁忌搜索算法求解问题目标函数平均值。当初始解较差时，禁忌搜索算法对问题解空间搜索时间较长，且容易陷入局部最优解。而超启发式算法先运行双蚁群算法，对问题解空间首先进行宽度搜索，获得较好的解作为下一个优化算法的初始解，而后继的禁忌搜索算法在当前解的基础上，对问题解空间进行深度搜索，容易获得问题满意结，算法的运行时间较短。

图6 超启发式算法与禁忌搜索算法目标函数平均值比较

图7 超启发式算法与禁忌搜索算法运行时间比较

4 结 语

通过分析了成像卫星对地观测行为特征，给出了任务、卫星、地面站等元素的形式化表达，建立了多星协同任务规划组合优化模型。并且建立超启发式算法求解问题框架，在典型的智能算法(双染色体遗传算法、双蚁群算法、模拟退火算法以及禁忌搜索算法)的基础上，利用宽度搜索算法优先，然后是运行深度搜索算法的启发式规则，给出多星协同任务规划超启发式算法解的仿真结果和评价分析。