针对多星多任务仿真调度的关键路径遗传算法

doi:10.16182/j.issn1004731x.joss.19-0301

摘要/Abstract

摘要： 卫星任务规划问题的求解空间随卫星数量和目标数量的增多而快速增大,针对大规模多星多任务规划问题,提出一种基于关键路径-遗传算法的卫星任务规划分层优化方法。该方法将卫星任务规划问题分解成任务分配和单星任务处理2个子问题,其中,任务分配通过遗传算法实现,一个分配结果对应种群中的一个个体,在单星任务处理子问题中引入关键路径法,用于求解每个个体的适应度,在提高优化效率的同时,确保得到当前任务分配条件下的最大观测效益,提高算法的全局优化能力。仿真结果表明,对于给定的6组大规模卫星任务规划算例,平均任务完成率均超过了99.7%,证明了该方法具有良好的稳定性和全局搜索能力;同时,相比于已有方法,该方法在优化效率上也有大幅提高,且任务规模越大,优化效率提升越大。

关键词: 卫星调度, 任务规划, 分层优化, 关键路径法, 遗传算法

Abstract: With the increase of the number of satellites and targets, the space for solving satellite task planning increases rapidly. For large-scale multi-satellite and multi-task planning, a hierarchical optimization method, which consists of Critical Path Method (CPM) and Genetic Algorithm (GA) is proposed. The method decomposes the satellite task planning into two subproblems: task allocation and single-satellite task processing. Task allocation is realized by GA and a task allocation result corresponds to an individual of the population. The CPM is used in the single-satellite task processing to solve the fitness of each individual, which improves the optimization efficiency, ensures the maximum observation benefit under the current task assignment condition, and improves the global optimization ability of the algorithm. Simulation results show that for a given set of 6 examples, the mission completion rate is over 99.7%, which proves that the method has good stability and global searching ability. Compared with the existing methods, the method also enhances the optimization efficiency greatly, and the larger the mission scale is, the higher the optimization efficiency will be improved.

Key words: satellites scheduling, task planning, hierarchic optimization, critical path method, genetic algorithm

中图分类号:

TP391

毛李恒, 邓清, 刘柔妮, 孔祥龙. 针对多星多任务仿真调度的关键路径遗传算法[J]. 系统仿真学报, 2021, 33(1): 205-214.

Mao Liheng, Deng Qing, Liu Rouni, Kong Xianglong. CPM-GA for Multi-satellite and Multi-task Simulation Scheduling[J]. Journal of System Simulation, 2021, 33(1): 205-214.

参考文献

[1] Lemaitre M, Verfaillie G, Jouhaud F, et al.Selecting and Scheduling Observation of Agile Satellites[J]. Aerospace Science and Technology (S1270-9638), 2002, 6(5): 367-381.
[2] Tangpattanakul P, Jozefowiez N, Lopez P.A Multi-Objective Local Search Heuristic for Scheduling Earth Observations Taken by An Agile Satellite[J]. European Journal of Operational Research (S0377-2217), 2015, 245(2): 542-554.
[3] Bunkheila F, Ortore E, Circi C.A New Algorithm for Agile Satellite-based Acquisition Operations[J]. Acta Astronautica (S0094-5765), 2016, 123: 121-128.
[4] Hosseinabadi S, Ranjbar M, Ramyar S, et al.Scheduling a Constellation of Agile Earth Observation Satellites with Preemption[J]. Journal of Quality Engineering and Production Optimization (S2423-3781), 2017, 2(1): 47-64.
[5] 严珍珍, 陈英武, 邢立宁. 基于改进蚁群算法设计的敏捷卫星调度方法[J]. 系统工程理论与实践, 2014, 34(3): 793-801.
Yan Zhenzhen, Chen Yingwu, Xing Lining.Agile Satellite Scheduling Based on Improved Ant Colony Algrithm[J]. System Engineering Theory & Practice, 2014, 34(3): 793-801.
[6] 刘嵩, 陈英武, 邢立宁, 等. 敏捷成像卫星自主任务规划方法[J]. 计算机集成制造系统, 2016, 22(4): 928-934.
Liu Song, Chen Yingwu, Xing Lining, et al.Method of Agile Imaging Satellites Autonomous Task Planning[J]. Computer Integrated Manufacturing Systems, 2016, 22(4): 928-934.
[7] 王凌峰, 陈兆荣, 陈浩, 等. 一种基于多目标优化的卫星周期性持续观测任务规划方法[J]. 小型微型计算机系统, 2018, 39(6): 1366-1371.
Wang Lingfeng, Chen Zhaorong, Chen Hao, et al.Method of Satellite Periodic Continuous Observing Task Scheduling Based on Multi-objective Optimization[J]. Journal of Chinese Computer Systems, 2018, 39(6): 1366-1371.
[8] 王建江, 朱晓敏, 吴朝波, 等. 面向应急条件的多星动态调度方法[J]. 航空学报, 2013, 34(5): 1151-1164.
Wang Jianjiang, Zhu Xiaomin, Wu Chaobo.Multi-satellite Dynamic Scheduling Method for Emergencies[J]. Acta Aeronautica et Astronautica Sinica, 2013, 34(5): 1151-1164.
[9] 白保存. 考虑任务合成的成像卫星调度模型与优化算法研究[D]. 长沙: 国防科学技术大学, 2008.
Bai Baocun.Modeling and Optimization Algorithms for Imaging Satellites Scheduling Problem with Task Merging[D]. Changsha: National University of Defense Technology, 2008.
[10] 孙凯, 邢立宁, 陈英武. 基于分解优化策略的多敏捷卫星联合对地观测调度[J]. 计算机集成制造技术, 2013, 19(1): 127-136.
Sun Kai, Xin Lining, Chen Yingwu.Agile Earth Observing Satellites Mission Scheduling Based on Decomposition Optimization Algorithm[J]. Computer Integrated Manufacturing Systems, 2013, 19(1): 127-136.
[11] 陈成. 时间依赖调度方法及在敏捷卫星任务规划中的应用研究[D]. 长沙: 国防科学技术大学, 2014.
Chen Cheng.Research on Time-dependent Scheduling Methods and Application on Agile Satellites Mission Planning[D]. Changsha: National University of Defense Technology, 2014.
[12] 陈金勇, 张超, 李艳斌. 基于超启发式的多星协同任务规划算法研究[J]. 中国电子科学研究院学报, 2018, 13(3): 254-259.
Chen Jinyong, Zhang Chao, Li Yanbin.Multi-Star Cooperative Task Planning Based on Hyper-Heuristic Algorithm[J]. Journal of CAEIT, 2018, 13(3): 254-259.
[13] 张超, 李艳斌. 多敏捷卫星协同任务规划调度方法[J]. 科学技术与工程, 2017, 17(22): 271-277.
Zhang Chao, Li Yanbin.Planning and Scheduling Method for Multi Agile Satellite Coordinated Mission[J]. Science Technology and Engineering, 2017, 17(22): 271-277.
[14] 王海蛟, 贺欢, 杨震. 敏捷成像卫星调度的改进量子遗传算法[J]. 宇航学报, 2018, 39(11): 1266-1274.
Wang Haijiao, He Huan, Yang Zhen.Scheduling of Agile Satellites Based on an Improved Quantum Genetic Algorithm[J]. Journal of Astronautics, 2018, 39(11): 1266-1274.
[15] 苗悦, 王峰. 敏捷成像卫星“逐级择优”在轨任务实时规划[J]. 光学精密工程, 2018, 26(1): 150-160.
Miao Yue, Wang Feng.Optimize-by-priority On-orbit Task Real-time Planning for Agile Imaging Satellite[J]. Optics and Precision Engineering, 2018, 26(1): 150-160.
[16] Li Y Q, Wang R X, Liu Y, et al.Satellite Range Scheduling with the Priority Constrain: an Improved Genetic Algorithm Using a Station ID Encoding Method[J]. Chinese Journal of Aeronautics (S1000-9361), 2015, 28(3): 789-803.
[17] James K, Morgan W.Critical Path Planning and Scheduling[C]. Eastern Joint Computer Conference. New York: American Institute of Electrical Engineering (AIEE), 1959: 160-173.
[18] 龙运军, 陈宇宁, 陈英武, 等. 基于Petri网和混合蚁群算法的多星成像调度[J]. 计算机工程, 2013, 39(1): 35-40.
Long Yunjun, Chen Yuning, Chen Yingwu, et al.Multiple Satellites Imagine Scheduling Based on Petri Net and Hybrid Ant Colony Algorithm[J]. Computer Engineering, 2013, 39(1): 35-40.