第5期 杨舒，等：一种面向任务的对地观测卫星Aget团队构建方法 ·659· 实验4为了进一步比较3种启发式算法在大 星任务规划领域出现的新而亟待解决的问题。在 规模卫星集群上的性能，随机生成一组由20个任务 对问题进行分析的基础上，建立了数学模型，提出 组成的任务集合，在10、20、30、40、50颗卫星组成的 了基于分枝限界的卫星团队构建精确搜索算法 卫星集群上进行实验。由于TFCA算法运行时间太 (TFCA)。针对TFCA算法时间复杂度高的缺点，引 长（在20颗卫星组成的集群上，对20个任务构建团 入了启发式剪枝策略，并根据算法输入中任务集合 队时，运行超过12h仍然不能给出有效结果)，我们 的次序不同，提出了3种启发式卫星团队构建算法： 仅对比HTFA-S、HTFA-RC和HTFA-C的实验结果， HTFA-S、HTFA-RC和HTFA-C算法。实验结果表 如图5、6所示。 明：3种启发式算法HTFA-S、HTFA-RC和HTFA-C, 500 构建团队所需的时间成本远小于T℉CA算法，而其 SHTFA-S 400 性能与T℉CA算法相差不大，对任务集合根据任务 ▣HTFA-RC ■HTFA-C 代价排序的HTFA-C构建的团队的代价最接近 300 TFCA算法构建的团队的代价。 200 在下一步的工作中，我们将从理论上分析 HTFA-S、HTFA-RC和HTFA-C算法近似程度，并给 出算法性能上界。 o 20 30 40 0 卫星数量/个 参考文献： 图53种启发式算法在不同规模卫星集群上的性能对比 [1]LIN Zhenhai.Mission planning for electromagnetic Fig.5 Performances of three algorithms in different environment monitors satellite based on simulated scales of SC annealing algorithm C]//2015 IEEE 28th Canadian 25 Conference on Electrical and Computer Engineering 汤 …·HTFA-S CCECE).Halifax,Canada,2015:530-535 HTFA-RC [2]姜维，郝会成，李一军对地观测卫星任务规划问题研究 15 +一HTFA-C 述评[J].系统工程与电子技术，2013,35(9)： 10 1878-1885 JIANG Wei,HAO Huicheng,LI Yijun.Review of task scheduling research for the earth observing satellites[J]. 10 20 30 40 50 Systems engineering and electronics,2013,35 (9 ) 卫星数量/个 1878-1885. [3]WANG Jun,JING Ning,LI Jun,et al.A multi-objective 图63种启发式算法在不同规模的卫星集群上运行时间 imaging scheduling approach for earth observing satellites Fig.6 Time comparison of three algorithms in different [C]//Proceedings of the 9th annual conference on Genetic scales of SC and evolutionary computation.London,England,2007: 图6中随着卫星规模的增大，对同一组任务构 2211-2218. 建的团队代价逐渐减少，而构建团队的时间逐渐增 [4 CHEN Hao,LI Jun,JING Ning.User-oriented data 大。这是因为规模增大，可以挑选多个卫星承担任 acquisition chain task planning algorithm for operationally 务，无需一个卫星承担多个任务，团队代价随之 responsive space satellite[].Journal of systems engineering and electronics,2016,27(5):1028-1039. 降低。 [5]WANG P,REINELT G,GAO P,et al.A model,a 整体上来看，3种启发式算法HTFA-S、HTFA- heuristic and a decision support system to solve the RC和HTFA-C构建团队所需的时间成本远小于 scheduling problem of an earth observing satellite TFCA算法，而其性能与TFCA相差不大，对任务集 constellation [J].Computers industrial engineering, 合根据任务代价排序的HT℉A-C构建的团队的代价 2011.61(2):322-335. 最接近T℉CA算法构建的团队的代价，也就是最接 [6]郭玉华.多类型对地观测卫星联合任务规划关键技术研 究[D].长沙：国防科技大学，2009：19-57. 近全局最优解，HTFA-RC次之。 GUO Yuhua.The study on key technologies of multiple types of 5结束语 earth observing satellites united scheduling[D].Changsha: national university of defense technology,2009:19-57. 面向任务的对地观测卫星团队构建问题，是卫 [7]BIANCHESSI N,RIGHINI G.Planning and scheduling实验 ４ 为了进一步比较 ３ 种启发式算法在大 规模卫星集群上的性能，随机生成一组由 ２０ 个任务 组成的任务集合，在 １０、２０、３０、４０、５０ 颗卫星组成的 卫星集群上进行实验。 由于 ＴＦＣＡ 算法运行时间太 长（在 ２０ 颗卫星组成的集群上，对 ２０ 个任务构建团 队时，运行超过 １２ ｈ 仍然不能给出有效结果），我们 仅对比 ＨＴＦＡ⁃Ｓ、ＨＴＦＡ⁃ＲＣ 和 ＨＴＦＡ⁃Ｃ 的实验结果， 如图 ５、６ 所示。 图 ５ ３ 种启发式算法在不同规模卫星集群上的性能对比 Ｆｉｇ． ５ Ｐｅｒｆｏｒｍａｎｃｅｓ ｏｆ ｔｈｒｅｅ ａｌｇｏｒｉｔｈｍｓ ｉｎ ｄｉｆｆｅｒｅｎｔ ｓｃａｌｅｓ ｏｆ ＳＣ 图 ６ ３ 种启发式算法在不同规模的卫星集群上运行时间 Ｆｉｇ．６ Ｔｉｍｅ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｔｈｒｅｅ ａｌｇｏｒｉｔｈｍｓ ｉｎ ｄｉｆｆｅｒｅｎｔ ｓｃａｌｅｓ ｏｆ ＳＣ 图 ６ 中随着卫星规模的增大，对同一组任务构 建的团队代价逐渐减少，而构建团队的时间逐渐增 大。 这是因为规模增大，可以挑选多个卫星承担任 务，无需一个卫星承担多个任务， 团队代价随之 降低。 整体上来看，３ 种启发式算法 ＨＴＦＡ⁃Ｓ、ＨＴＦＡ⁃ ＲＣ 和 ＨＴＦＡ⁃Ｃ 构建团队所需的时间成本远小于 ＴＦＣＡ 算法，而其性能与 ＴＦＣＡ 相差不大，对任务集 合根据任务代价排序的 ＨＴＦＡ⁃Ｃ 构建的团队的代价 最接近 ＴＦＣＡ 算法构建的团队的代价，也就是最接 近全局最优解，ＨＴＦＡ⁃ＲＣ 次之。 ５ 结束语 面向任务的对地观测卫星团队构建问题，是卫 星任务规划领域出现的新而亟待解决的问题。 在 对问题进行分析的基础上，建立了数学模型，提出 了基于分枝限界的卫星团队构建精确搜索算法 （ＴＦＣＡ）。 针对 ＴＦＣＡ 算法时间复杂度高的缺点，引 入了启发式剪枝策略，并根据算法输入中任务集合 的次序不同，提出了 ３ 种启发式卫星团队构建算法： ＨＴＦＡ⁃Ｓ、ＨＴＦＡ⁃ＲＣ 和 ＨＴＦＡ－Ｃ 算法。 实验结果表 明：３ 种启发式算法 ＨＴＦＡ⁃Ｓ、ＨＴＦＡ⁃ＲＣ 和 ＨＴＦＡ⁃Ｃ， 构建团队所需的时间成本远小于 ＴＦＣＡ 算法，而其 性能与 ＴＦＣＡ 算法相差不大，对任务集合根据任务 代价排序的 ＨＴＦＡ⁃Ｃ 构建的团队的代价最接近 ＴＦＣＡ 算法构建的团队的代价。 在下一 步 的 工 作 中， 我 们 将 从 理 论 上 分 析 ＨＴＦＡ⁃Ｓ、ＨＴＦＡ⁃ＲＣ 和 ＨＴＦＡ⁃Ｃ 算法近似程度，并给 出算法性能上界。 参考文献： ［ １ ］ ＬＩＮ Ｚｈｅｎｈａｉ． Ｍｉｓｓｉｏｎ ｐｌａｎｎｉｎｇ ｆｏｒ ｅｌｅｃｔｒｏｍａｇｎｅｔｉｃ ｅｎｖｉｒｏｎｍｅｎｔ ｍｏｎｉｔｏｒｓ ｓａｔｅｌｌｉｔｅ ｂａｓｅｄ ｏｎ ｓｉｍｕｌａｔｅｄ ａｎｎｅａｌｉｎｇ ａｌｇｏｒｉｔｈｍ ［ Ｃ ］ ／ ／ ２０１５ ＩＥＥＥ ２８ｔｈ Ｃａｎａｄｉａｎ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｅｌｅｃｔｒｉｃａｌ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ （ＣＣＥＣＥ）． Ｈａｌｉｆａｘ， Ｃａｎａｄａ， ２０１５： ５３０－５３５． ［２］姜维，郝会成，李一军．对地观测卫星任务规划问题研究 述 评 ［ Ｊ ］． 系 统 工 程 与 电 子 技 术， ２０１３， ３５ （ ９ ）： １８７８－１８８５． ＪＩＡＮＧ Ｗｅｉ， ＨＡＯ Ｈｕｉｃｈｅｎｇ， ＬＩ Ｙｉｊｕｎ． Ｒｅｖｉｅｗ ｏｆ ｔａｓｋ ｓｃｈｅｄｕｌｉｎｇ ｒｅｓｅａｒｃｈ ｆｏｒ ｔｈｅ ｅａｒｔｈ ｏｂｓｅｒｖｉｎｇ ｓａｔｅｌｌｉｔｅｓ ［ Ｊ］． Ｓｙｓｔｅｍｓ ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ ｅｌｅｃｔｒｏｎｉｃｓ， ２０１３， ３５ （ ９ ）： １８７８－１８８５． ［３］ＷＡＮＧ Ｊｕｎ， ＪＩＮＧ Ｎｉｎｇ， ＬＩ Ｊｕｎ， ｅｔ ａｌ． Ａ ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ ｉｍａｇｉｎｇ ｓｃｈｅｄｕｌｉｎｇ ａｐｐｒｏａｃｈ ｆｏｒ ｅａｒｔｈ ｏｂｓｅｒｖｉｎｇ ｓａｔｅｌｌｉｔｅｓ ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ９ｔｈ ａｎｎｕａｌ ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｇｅｎｅｔｉｃ ａｎｄ ｅｖｏｌｕｔｉｏｎａｒｙ ｃｏｍｐｕｔａｔｉｏｎ． Ｌｏｎｄｏｎ， Ｅｎｇｌａｎｄ， ２００７： ２２１１－２２１８． ［４ ］ ＣＨＥＮ Ｈａｏ， ＬＩ Ｊｕｎ， ＪＩＮＧ Ｎｉｎｇ． Ｕｓｅｒ⁃ｏｒｉｅｎｔｅｄ ｄａｔａ ａｃｑｕｉｓｉｔｉｏｎ ｃｈａｉｎ ｔａｓｋ ｐｌａｎｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｏｐｅｒａｔｉｏｎａｌｌｙ ｒｅｓｐｏｎｓｉｖｅ ｓｐａｃｅ ｓａｔｅｌｌｉｔｅ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｓｙｓｔｅｍｓ ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ ｅｌｅｃｔｒｏｎｉｃｓ， ２０１６， ２７（５）： １０２８－１０３９． ［５］ ＷＡＮＧ Ｐ， ＲＥＩＮＥＬＴ Ｇ， ＧＡＯ Ｐ， ｅｔ ａｌ． Ａ ｍｏｄｅｌ， ａ ｈｅｕｒｉｓｔｉｃ ａｎｄ ａ ｄｅｃｉｓｉｏｎ ｓｕｐｐｏｒｔ ｓｙｓｔｅｍ ｔｏ ｓｏｌｖｅ ｔｈｅ ｓｃｈｅｄｕｌｉｎｇ ｐｒｏｂｌｅｍ ｏｆ ａｎ ｅａｒｔｈ ｏｂｓｅｒｖｉｎｇ ｓａｔｅｌｌｉｔｅ ｃｏｎｓｔｅｌｌａｔｉｏｎ ［ Ｊ ］． Ｃｏｍｐｕｔｅｒｓ ＆ ｉｎｄｕｓｔｒｉａｌ ｅｎｇｉｎｅｅｒｉｎｇ， ２０１１， ６１（２）： ３２２－３３５． ［６］郭玉华． 多类型对地观测卫星联合任务规划关键技术研 究［Ｄ］． 长沙：国防科技大学， ２００９： １９－５７． ＧＵＯ Ｙｕｈｕａ． Ｔｈｅ ｓｔｕｄｙ ｏｎ ｋｅｙ ｔｅｃｈｎｏｌｏｇｉｅｓ ｏｆ ｍｕｌｔｉｐｌｅ ｔｙｐｅｓ ｏｆ ｅａｒｔｈ ｏｂｓｅｒｖｉｎｇ ｓａｔｅｌｌｉｔｅｓ ｕｎｉｔｅｄ ｓｃｈｅｄｕｌｉｎｇ ［Ｄ］． Ｃｈａｎｇｓｈａ： ｎａｔｉｏｎａｌ ｕｎｉｖｅｒｓｉｔｙ ｏｆ ｄｅｆｅｎｓｅ ｔｅｃｈｎｏｌｏｇｙ，２００９： １９－５７． ［７ ］ ＢＩＡＮＣＨＥＳＳＩ Ｎ， ＲＩＧＨＩＮＩ Ｇ． Ｐｌａｎｎｉｎｇ ａｎｄ ｓｃｈｅｄｕｌｉｎｇ 第 ５ 期 杨舒，等：一种面向任务的对地观测卫星 Ａｇｅｎｔ 团队构建方法 ·６５９·