基于改进蚁群算法设计的敏捷卫星调度方法

严珍珍, 陈英武, 邢立宁

系统工程理论与实践 ›› 2014, Vol. 34 ›› Issue (3) : 793-801.

PDF(1163 KB)
PDF(1163 KB)
系统工程理论与实践 ›› 2014, Vol. 34 ›› Issue (3) : 793-801. DOI: 10.12011/1000-6788(2014)3-793
研究论文

基于改进蚁群算法设计的敏捷卫星调度方法

    严珍珍, 陈英武, 邢立宁
作者信息 +

Agile satellite scheduling based on improved ant colony algorithm

    YAN Zhen-zhen, CHEN Ying-wu, XING Li-ning
Author information +
文章历史 +

摘要

敏捷卫星与传统非敏捷卫星相比,增加了俯仰和偏航两个自由度,提升了卫星的成像能力,也加大了搜索空间,使敏捷卫星的调度问题变得更加复杂,组合优化难度加大. 蚁群算法是可有效求解敏捷卫星调度问题的方法之一. 针对蚁群算法优化性能严重依赖于算法参数以及各个组件的设计的问题,提出利用均匀设计的方法优化组合算法的各个组件,设计出能有效求解敏捷卫星调度问题的蚁群算法. 利用7 个不同规模的实例进行实验,实验结果表明了方法的有效性.

Abstract

Agile earth observing satellite has two more degrees of freedom combined with the general earth observing satellite. It gives opportunities for a more efficient use of the satellite imaging capabilities, and on the other hand, it greatly expands the search space, which makes the scheduling of agile satellite become significantly difficulty. Ant colony system (ACS) algorithm is one of the efficient method to solve the agile satellite scheduling problem. Considering that the performance of ACS is deeply depend on the design of parameter and the modules, uniform design has been proposed to combine the modules optimality. An ACS which can solve the agile satellite effectively is designed. 7 instances are tested to prove that the designed ACS can solve the problem effectively.

关键词

敏捷卫星调度 / 蚁群算法 / 均匀设计

Key words

scheduling of agile satellite / ant colony system algorithm / uniform design

引用本文

导出引用
严珍珍 , 陈英武 , 邢立宁. 基于改进蚁群算法设计的敏捷卫星调度方法. 系统工程理论与实践, 2014, 34(3): 793-801 https://doi.org/10.12011/1000-6788(2014)3-793
YAN Zhen-zhen , CHEN Ying-wu , XING Li-ning. Agile satellite scheduling based on improved ant colony algorithm. Systems Engineering - Theory & Practice, 2014, 34(3): 793-801 https://doi.org/10.12011/1000-6788(2014)3-793
中图分类号: TP181   

参考文献

[1] Lemaitre M, Verfaillie G. Selecting and scheduling observations for agile satellites: Some lessons from the constraint reasoning community point of view[J]. Principles and Practice of Constraint Programming, 2001: 670-684.
[2] Mancel C, Lopez P. Complex optimization problems in space systems[C]// 13th International Conference on Automated Planning and Scheduling, Trento, Italy: 2003.
[3] Vasquez M, Habet D. Saturated and consistent neighborhood for selecting and scheduling photographs of agile earth observing satellites[C]// 5th Metaheuristics International Conference, Kyoto, Japan, 2003.
[4] Habet D, Vasquez M, Vimont Y. Bounding the optimum for the problem of scheduling the photographs of an agile earth observing satellite[J]. Computational Optimization and Applications[J]. 2010, 47: 307-333.
[5] Xu M Q, Li Y Q, Wang R X. Scheduling observations of agile satellites with combined genetic algorithm[C]// Third International Conference on Natural Computation, Haikou, China: 2007.
[6] Anghinolfi D, Boccalatte A, Paolucci M, et al. Performance evaluation of an adaptive ant colony optimization applied to single machine scheduling[J]. Simulated Evolution and Learning, 2008: 411-420.
[7] Fialho A. Adaptive operator selection for optimization[D]. Orsay, France: Université Paris-Sud XI, 2010.
[8] Pellegrini P, Stützle T, Birattari M. A critical analysis of parameter adaptation in ant colony optimization[J]. Swarm Intelligence, 2012, 6(1): 23-48.
[9] Blum C. Ant colony optimization: Introduction and recent trends[J]. Physics of Life Reviews, 2005, 2: 353-373.
[10] Baioletti M, Milani A, Poggioni V, et al. Experimental evaluation of pheromone models in ACOPlan[J]. Annals of Mathematics and Artificial Intelligence, 2011, 62: 187-217.
[11] Fang K T, Lin D K J, Winker P, et al. Uniform design: Theory and application[J]. Technometrics, 2000, 42(3): 237-248.
[12] Lu C, Huang H Z, Zheng B. An ant colony optimization approach to disassembly planning[C]// International Conference on Apperceiving Computing and Intelligence Analysis, Chengdu, China, 2008.
[13] Lu C, Huang H Z, Fu J. A multi-objective disassembly planning approach with ant colony optimization algorithm[J]. Proceedings of the Institution of Mechanical Engineers Part B —Journal of Engineering Manufacture, 2008, 222(11): 1465-1474.
[14] 黄永青, 梁昌勇, 张祥德. 基于均匀设计的蚁群算法参数设定[J]. 控制与决策, 2006, 21(1): 93-96. Huang Yongqing, Liang Changyong, Zhang Xiangde. Parameter establishment of an ant system based on uniform design[J]. Control and Decision, 2006, 21(1): 93-96.
[15] Reinelt G, Wang P. A heuristic for an earth observing satellite constellation scheduling problem with download considerations[J]. Electronic Notes in Discrete Mathematics, 2010, 36: 711-718.
[16] Cheng C C, Smith S F. Slack-based heuristics for constraint satisfaction scheduling[C]// Proceedings of the National Conference on Artificial Intelligence, 1993: 139-144.
[17] 杨剑锋. 蚁群算法及应用研究[D]. 杭州: 浙江大学, 2007.Yang Jianfeng. Research on the ant colony algorithm and the application[D]. Hangzhou: University of Zhejiang, 2007.
[18] Demsar J. Statistical comparisons of classifiers over multiple data sets[J]. Journal of Machine Learning Research, 2006, 7: 1-30.
[19] 陈英武, 方炎申, 李菊芳, 等. 卫星任务调度问题的约束规划模型[J]. 国防科技大学学报, 2006, 28(5): 126-132. Chen Yingwu, Fang Yanshen, Li Jufang, et al. Constraint programming model of satellite mission scheduling[J]. Journal of National University of Defense Technology, 2006, 28(5): 126-132.
[20] 贺仁杰. 成像侦查卫星调度问题研究[D].长沙: 国防科技大学, 2004. He Renjie. Research on imaging reconnaissance satellite scheduling problem[D]. Changsha: National University of Defense Technology, 2004.

基金

国防科学技术大学优秀研究生创新资助项目(S120501);国家自然科学基金(70971131,71031007,71101150)
PDF(1163 KB)

457

Accesses

0

Citation

Detail

段落导航
相关文章

/