Progress in China’s aerospace technologies and applications makes the satellite ground station resource shortage problem increasingly prominent. It is necessary to optimize the usage of satellite ground station resources, also called satellite range scheduling problem, which has received extensive attention. Based on the analysis of the characteristics of the problem, the user's preference information on the scheduling results is modeled and formulated, a multi-objective mathematical scheduling model covering the user's preferences is established, and a satellite range scheduling algorithm based on preference-based multi-objective evolutionary algorithm is proposed. To further improve the performance of the proposed algorithm, heuristic strategies based on domain-knowledge including the tasks expansion strategy, conflicts resolution strategy and tasks reduction strategy are designed. Experimental results show that, with the help of user’s preference information, the proposed algorithm can effectively improve the capacity of exploring solutions in the preference region, outweighing the-state-of-art algorithm in the Inverted Generational Distance based on Composite Front(IGD-CP) indicator.
[1] CHEN H, YANG S, LI J, et al. Exact and heuristic methods for observing task-oriented satellite cluster agent team formation[J]. Mathematical Problems in Engineering, 2018(10):1-23.
[2] 彭双. 适应动态需求的卫星观测任务星上连续自主规划方法[D]. 长沙:国防科技大学, 2019:1-14. PENG S. An approach of autonomous satellite observation task onboard continuous planning for dynamic requests[D]. Changsha:National University of Defense Technology, 2019:1-14(in Chinese).
[3] VAZQUEZ A J, ERWIN R S. On the tractability of satellite range scheduling[J]. Optimization Letters, 2015, 9(2):311-327.
[4] VAZQUEZ R, PEREA F, VIOQUE J G. Resolution of an antenna-satellite assignment problem by means of integer linear programming[J]. Aerospace Science and Technology, 2014, 39:567-574.
[5] MARINELLI F, NOCELLA S, ROSSI F, et al. A Lagrangian heuristic for satellite range scheduling with resource constraints[J]. Computers & Operations Research, 2011, 38(11):1572-1583.
[6] XIAO Y, ZHANG S, YANG P, et al. A two-stage flow-shop scheme for the multi-satellite observation and data-down-link scheduling problem considering weather uncertainties[J]. Reliability Engineering & System Safety, 2019, 188:263-275.
[7] XHAFA F, HERRERO X, BAROLLI A, et al. A simulated annealing algorithm for ground station scheduling problem[C]//16th International Conference on Network-Based Information Systems. Piscataway:IEEE Press, 2013:24-30.
[8] LI Y, WANG R, LIU Y, et al. Satellite range scheduling with the priority constraint:An improved genetic algorithm using a station ID encoding method[J]. Chinese Journal of Aeronautics, 2015, 28(3):789-803.
[9] CHEN H, ZHONG Z, WU J, et al. Multi-satellite data downlink resource scheduling algorithm for incremental observation tasks based on evolutionary computation[C]//Proceedings of IEEE 7th International Conference on Advanced Computational Intelligence. Piscataway:IEEE Press, 2015.
[10] 赵琳, 王硕, 郝勇, 等. 基于地面任务-空间姿态映射的敏捷卫星任务规划[J]. 航空学报, 2018, 38(10):322066. ZHAO L, WANG S, HAO Y, et al. Mission planning for agile satellite based on mapping relationship between ground missions and spatial attitudes[J]. Acta Aeronautica et Astronautica Sinica, 2018, 38(10):322066(in Chinese).
[11] KARAPETYAN D, MINIC S M, MALLADI K T, et al. Satellite downlink scheduling problem:A case study[J]. Omega-International Journal of Management Science, 2015, 53:115-123.
[12] ZHANG Z, HU F, ZHANG N. Ant colony algorithm for satellite control resource scheduling problem[J]. Applied Intelligence, 2018, 48(10):3295-3305.
[13] ZHANG Z, ZHANG N, FENG Z. Multi-satellite control resource scheduling based on ant colony optimization[J]. Expert Systems with Applications, 2014, 41(6):2816-2823.
[14] IGLESIA B D L, REYNOLDS A, RAYWARDSMITH V J. Developments on a multi-objective metaheuristic (MOMH) algorithm for finding interesting sets of classification rules[C]//International Conference on Evolutionary Multi-criterion Optimization. Berlin:Springer, 2005:826-840.
[15] 李满林, 杜雷, 闻英友, 等. 多目标优化遗传算法在移动网络规划中的应用[J]. 控制与决策, 2003, 18(4):441-444. LI M L, DU L, WEN Y Y, et al. Applications of multiple objective genetic algorithms in mobile networks planning[J]. Control and Decision, 2003, 18(4):441-444(in Chinese).
[16] 张潜, 高立群, 胡祥培, 等. 物流配送路径多目标优化的聚类-改进遗传算法[J]. 控制与决策, 2003, 18(4):418-422. ZHANG Q, GAO L Q, HU X P, et al. Research on multi-objective vehicle routing problem of optimization based on clustering analysis and improved genetic algorithm[J]. Control and Decision, 2003, 18(4):418-422(in Chinese).
[17] MURUGESWARI R, RADHAKRISHNAN S, DEVARAJ D. A multi-objective evolutionary algorithm based QoS routing in wireless mesh networks[J]. Applied Soft Computing, 2016, 40:517-525.
[18] SONG Y J, MA X, LI X J, et al. Learning-guided nondominated sorting genetic algorithm Ⅱ for multi-objective satellite range scheduling problem[J]. Swarm and Evolutionary Computation, 2019, 49:194-205.
[19] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multi-objective genetic algorithm:NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197.
[20] DU Y H, XING L N, ZHANG J W, et al. MOEA based memetic algorithms for multi-objective satellite range scheduling problem[J]. Swarm and Evolutionary Computation, 2019, 49:194-205.
[21] JAIMES A L, MONTANO A A, COELLO C A C. Preference incorporation to solve many-objective airfoil design problems[C]//2011 IEEE Congress of Evolutionary Computation (CEC). Piscataway:IEEE Press, 2011:1605-1612.
[22] MAHBUB M S, WAGNER M, CREMA L. Multi-objective optimisation with multiple preferred regions[C]//Proceedings of the Australasian Conference on Artificial Life and Computational Intelligence. Berlin:Springer, 2017:241-253.
[23] OLIVEIRA E, ANTUNES C H, GOMES A. A comparative study of different approaches using an outranking relation in a multi-objective evolutionary algorithm[J]. Computers & Operations Research, 2013, 40(6):1602-1615.
[24] 李龙梅. 基于偏好的进化多目标优化及其在卫星任务规划中的应用[D]. 长沙:国防科技大学, 2018:43-107. LI L M. Preference-based evolutionary multi-objective optimization and its applications in satellite mission planning[D]. Changsha:National University of Defense Technology, 2018:43-107(in Chinese).
[25] BEUME N, NAUJOKS B, EMMERICH M. SMS-EMOA:Multiobjective selection based on dominated hypervolume[J]. European Journal of Operational Research, 2007, 181(3):1653-1669.
[26] TRAUTMANN H, WAGNER T, BROCKHOFF D. R2-EMOA:Focused multiobjective search using R2-indicator-based selection[M]. Berlin:Springer, 2013:70-74.
[27] PICEK S, GOLUB M. The new negative slope coefficient measure[C]//Proceedings of the 10th WSEAS International Conference on Evolutionary Computing. Prag, Czech Republic:World Scientific and Engineering Academy and Society, 2009:96-101.
[28] BÄCK T, FOGEL D B, MICHALEWICZ Z. Evolutionary computation 1:Basic algorithms and operators[C]//Institute of Physics Publishing, 2000.
[29] DAVID H. MOEA Framework[EB/OL].(2019-12-30)[2020-04-21]. http://moeaframework.org/.
[30] VAN VELDHUIZEN D A, LAMONT G. Evolutionary computation and convergence to a Pareto front[C]//Proceedings of the Late Breaking Papers at the Genetic Programming 1998 Conference, 1998:221-228.
[31] MOHAMMADI A, OMIDVAR M N, LI X. A new performance metric for user-preference based multi-objective evolutionary algorithms[C]//Proceedings of the 2013 IEEE Congress on Evolutionary Computation (CEC). Piscataway:IEEE Press, 2013:2825-2832.
[32] BOSMAN P, THIERENS D. The balance between proximity and diversity in multiobjective evolutionary algorithms[J]. IEEE Transactions on Evolutionary Computation, 2003, 7(2):174-188.
CJA