【深度】基于并行架构的敏捷卫星任务调度优化算法（下）算法研究与结论

查看原文

其他

【深度】基于并行架构的敏捷卫星任务调度优化算法（下）算法研究与结论

From 学术plus 学术plus 2019-03-28

【学术plus】新添加号内搜索功能！

进入公众号→点击菜单【智库扫描】→【搜搜文章】

→输入关键词→一键检索您需要的文章。快来试试！

【兼职】神秘岗位正在向你招手，敢来么？

【厚度】学术plus年终巨献：2017年你不可以错过的重磅报告们！（全文阅读链接）

今日荐文

今日荐文的作者为中国电子科技集团公司第五十四研究所专家张超，李艳斌，陈金勇。本篇节选自论文《基于并行架构的敏捷卫星任务调度优化算法》，发表于《中国电子科学研究院学报》第12卷第5期。本文为论文下半部分。

摘要：针对敏捷卫星任务规划调度问题，首先分析了敏捷卫星成像时间影响成像质量、调度和选择相结合等调度特点，构建了基于成像质量惩罚系数的敏捷卫星任务规划组合优化模型；分别采用差分演化、粒子群和模拟退火三种算法进行求解和分析评价；并且采用全局-主从式模型和独立-孤岛模型分别实现了三种算法的并行计算技术。

关键词：敏捷卫星；任务调度；并行算法

3 敏捷卫星任务调度优化算法

① 敏捷卫星任务编码设计

染色体结构由观测目标的编码和接收元任务的编码拼接得到，根据任务规划需求采用整数编码的方式。传统卫星一个观测目标的基因位取值只能是0到1两种，0代表对应的该点目标没有被选中，1代表该点目标会被安排进行观测成像，所有观测目标和接收元任务的数量之和即为染色体的长度。然而，敏捷卫星根据不同任务观测模式基因位取值范围不同，对于观测元任务数量不同。对于多点目标连续成像模式，每个点目标可以被观测N次；对于立体成像模式，每个目标至少被观测2次；对于宽幅目标，根据区域条带分解得到多个观测条带，即一个观测目标对应多个观测元任务，相关元任务必须一起安排；因此，敏捷卫星观测元任务对应的基因位取值范围为0到N；敏捷卫星接收元任务基因位的取值范围为0、1或2，0代表对应的接收元任务没有被选中，1代表对应的接收元任务被选中并且做回放模式，2代表对应的接收元任务被选中且做实传模式。

② 基于排序变异的差分演化算法

DE算法的核心算子是差分变异算子。一般情况下，变异算子是从当前种群中随机选择。在自然界中，优良物种总是包含好的基因信息，因此，它们有更多的机会被用来指导其他物种进化。受这种现象启发，双亲个体被选中为变异算子的概率是根据它们在当前种群中的评价值排名来决定的，评价值较高的个体将获得更大的差分变异概率，其中个体权重的设置使用二次方模型（quadratic model）。采用这种基于排序的变异方式，将种群个体进行适应度排序后，进行迭代更新，能够维持局部搜索和全局搜索的平衡。

（12）

③ 遗传模拟退火混合算法

本文针对模拟退火算法解的质量与求解时间长之间的矛盾，将遗传算法与模拟退火算法结合起来，提出了一种改进的遗传模拟退火算法。改进遗传模拟退火算法的基本思想是：与传统的模拟退火算法总体运行过程相类似，从一组随机产生的初始解（初始种群）开始全局最优解的搜索过程，通过选择、交叉、变异等遗传操作来产生候选解，然后对候选解采用Metropolis准则判断是否接受其作为下一代种群中的个体，执行退温操作。这个运行过程反复迭代进行，直到满足终止条件。

④ 基于相似度和聚集度的粒子群算法

根据标准PSO算法的性能分析，随着算法迭代运行，粒子变得越来越相似，算法缺少多样性，从而影响算法的全局搜索能力。改进的粒子群算法的基本思想是：根据每条染色体的基因位与最优染色体进行比较，计算出每条染色体与最优染色体的相似度，然后根据相似度计算出每一代种群的聚集度。随着迭代运行，标准PSO算法会越来越聚集在一起，因为粒子最终都向最优点粒子靠近。改进的粒子群通过相似度和聚集度，在染色体变异过程中，当种群聚集度大的时候，增加染色体的变异概率，从而使种群的多样性增加，有利于寻找到更优的结果。

⑤ 约束处理

敏捷卫星任务调度优化是一个带约束的优化问题，需要考虑诸多约束。算法运行过程中产生的逻辑规划对象很有可能是不合法的，必须要对这样的逻辑规划对象进行处理。算法在产生逻辑规划对象经约束处理模块，对组合元任务集进行处理，得到新的满足约束的组合元任务集。然后通过编码，生成对应的修正的逻辑规划对象，即规划结果。约束处理模块依次按照以下顺序进行约束处理：观测时间冲突约束、数传模式约束、指令模板约束、工作时间约束、文件下传约束、能源约束。

图 3 约束处理流程

⑥ 仿真测试结果

针对差分演化算法、模拟退火算法以及粒子群算法三种算法分别提出了改进算法。为了测试改进算法的效果，选取了5批工程数据，每批数据包含300个观测元任务，分别从综合评价值（完成任务数、优先级之和、俯仰角之和）以及耗时比较改进前后的算法效果。改进后的差分演化算法是使用了rankDE策略的算法，改进后的模拟退火算法是遗传模拟退火算法，改进后的粒子群算法是通过引入相似度和聚集度的概念来增大变异概率的算法。

图 4 改进前后算法的综合评价值

图 5 改进前后算法的耗时

通过以上图表数据的展示，可以看出：使用rankDE策略的差分演化算法，其规划结果及耗时与改进前的算法规划结果及耗时比较接近，改进效果并不明显；遗传模拟退火算法的改进效果比较明显，改进后的规划结果明显较优，虽然耗时相对较多，但算法改进后的耗时与差分演化算法接近，属于可接受范围；引入相似度和聚集度使变异概率增大之后的粒子群算法，其规划结果比未改进的粒子群算法的规划结果较优，虽然其耗时也相应的增加了，但综合其他算法来看，其耗时仍少于差分演化算法和模拟退火算法，说明粒子群算法的改进效果较明显。

4 并行算法研究

① 并行算法模型

由于智能优化算法的内在并行性，其并行处理方式是很自然的解决途径。本文中，卫星任务规划算法在并行模式上采用全局型和独立型。为了应用并行计算，必须把算法分解成相互独立的若干问题^[14]。

全局型—主从式模型（mast-slave model）首先统一三种智能优化算法的编码格式，然后在主线程中进行搜索，然后将算法的每一次迭代中得到的解分配到对应的处理器独立进行的编码解析、约束检查、评价和计算解的适应值等操作，然后将其返回给调用线程。主从式模型示意图如图6。

图6主从式模型的并行演化计算架构图

独立型—孤岛模型（island model）进行并行处理，多个解用“种群”表示，将“种群”分为若干个“子种群”分配给对应的处理器，每个处理器不仅独立计算适应度，而且独立进行选择、重组交叉和变异操作。每次迭代完成以后，选择“种群”中所有解的评价值中最高的解作为当前最优解。判断这个解是否满足终止条件的要求，满足则退出，不满足则继续迭代，如图7所示。

图7孤岛模型的并行演化计算架构图

② 并行算法测试

并行测试结果很大程度取决于并行环境，三种运行模式硬件采用四核Core（TM） i3-4150 3.5Ghz、内存4G。针对同一批测试数据，对主从式并行和孤岛式并行进行测试，分别采用三种算法运行10次求平均值，利用平均耗时与未加速的算法耗时进行对比，具体的算法耗时见表3，成像任务规划性能加速比如图8。

表 2 三种算法并行模型运行时间表

图8智能优化算法并行加速比图

在没有并行运算的情况下，三种算法运行耗时均较多；在采用并行框架后，三种算法运行时间均有明显下降；在主从式并行模型下，加速比分别为模拟退火算法1.614、差分演化算法1.911、粒子群算法1.990；在孤岛式并行模型下加速比分别为差分演化算法1.960、模拟退火算法2.254、粒子群算法2.478。综合比较两种模型，加速效果都很明显，但就两种模型来看，孤岛式并行模型加速效果更明显，三种算法的加速效果都高于主从式并行模型的加速比。

结语

本文针对敏捷卫星任务规划调度问题的特点，构建了基于成像质量惩罚系数的敏捷卫星任务规划组合优化模型；并对常见智能优化算法（差分演化、粒子群和模拟退火三种算法）进行改进实现和测试评价；在此基础上采用全局-主从式模型和独立-孤岛模型分别实现了三种算法单机多核并行计算技术。实验结果验证了提出的算法是可行的和有效的。

【参考文献】

[1] 徐雪仁, 宫鹏, 黄学智,等. 资源卫星(可见光)遥感数据获取任务调度优化算法研究[J]. 遥感学报, 2007, 11(1):109-114..

[2] Bonissone P P, Subbu R, Eklund N, et al. Evolutionary algorithms + domain knowledge = real-world evolutionary computation[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(3):256-280.

[3] 韩伟,张学庆. 一种基于离散粒子群的多星任务规划算法[J].无线电工程,2015,45(1):1-4.

[4] Lemaı̂tre M, Verfaillie G, Jouhaud F, et al. Selecting and scheduling observations of agile satellites[J]. Aerospace Science and Technology, 2002, 6(5): 367-381.

[5] Mancel C, Lopez P. Complex optimization problems in space systems[C].13Th International Conference on Automated Planning & Scheduling (ICAPS'03). 2003.

[6] 李玉庆, 徐敏强, 王日新. 三轴稳定卫星点目标观测任务优化调度技术[J].吉林大学学报:工学版, 2008, 38(6):1447-1451.

[7] 余婧, 喜进军, 于龙江,等. 敏捷卫星同轨多条带拼幅成像模式研究[J]. 航天器工程, 2015, 24(2):27-34.

[8] 张新伟, 戴君, 刘付强. 敏捷遥感卫星工作模式研究[J]. 航天器工程, 2011, 20(4):32-38.

[9] 王任享．三线阵CCD影像卫星摄影测量原理[M].北京：测绘出版社，2006:1-23

[10] 孙　凯，邢立宁，陈英武等.基于分解优化策略的多敏捷卫星联合对地观测调度[J].计算机集成制造系统, 2013, 19(1):127-136

[11] 郝会成，姜维，李一军.基于混合遗传算法的敏捷卫星任务规划求解 [J].科学技术与工程. 2013, 13(17) :4972-4978

[12] 何磊, 刘晓路, 陈英武, 邢立宁. 面向敏捷卫星任务规划的云层建模及处理方法[J]. 系统工程与电子技术, 2016, 38(4): 852-858.

[13] 陈成. 时间依赖调度方法及在敏捷卫星任务规划中的应用研究[D]. 国防科学技术大学. 2014

[14] 付鑫, 张峰, 冯占林,等. 基于并行计算的混沌遗传算法对反导预警雷达部署优化研究[J]. 中国电子科学研究院学报, 2016(3):276-282.

【厚度】学术plus年终巨献：

2017年你不可以错过的重磅报告们！（全文阅读链接）

【兼职】神秘岗位正在向你招手，敢来么？