·658. 智能系统学报 第12卷 表24种算法在小规模卫星集群上的运行时间对比 图2展现了在大规模卫星集群上HTFA-S、 Table 2 Running time of four algorithms in SSC HTFA-RC、HTFA-C算法的性能差异。HTFA-RC HTFA-C算法构建团队的效果普遍优于HTFA-S算 任务数量 TFCA HTFA-S HTFA-RC HTFA-C 法。从图3中可以看出，随着任务增多，HTFA-S、 10 7.591 0.026 0.054 0.054 HTFA-RC、HTFA-C算法构建团队时间都在逐渐增 12 42.479 0.107 0.057 0.088 加，而HT℉A-C构建团队时间的增长速度明显高于 153.379 0.179 0.096 0.209 HTFA-S和HTFA-RC,这是因为HTFA-C任务的有 序性在相同的剪枝策略下相比于其他两种算法， 16 1086.749 0.179 0.158 0.158 HT℉A-C在每一层会更多地保留效果好的分枝，因 18 8019.749 0.258 0.399 1.339 此整个团队构建过程中，搜索的分枝更多。 20 90078.369 0.418 1.241 2.096 实验3随机生成一组由10个任务构成的任 从图1可以看出，在小规模卫星集群中，HT℉A- 务集合，在不同规模的卫星集群上构建团队，比较 S、HTFA-RC、HTFA-C算法构建的团队效果接近 TFCA、HTFA-S、HTFA-C、HTFA-RC算法性能，实验 TFCA算法。HTFA-S算法由于任务输入的无序性， 结果如表3、图4所示。 在大部分情况下构建团队的效果比HTFA-RC 表34种算法的运行时间对比 HTFA-C算法差。表2展示了4种算法的时间特 Table 3 Running time of four algorithms 性，T℉CA算法的运行时间随着任务的增多，呈现指 卫星数量/个 TFCA HTFA-S HTFA-RC HTFA-C 数增长趋势，HTFA-S、HTFA-RC、HTFA-C算法的运 行时间增长缓慢。 5 0.158 0.007 0.007 0.014 实验2为了进一步验证我们提出的算法在大 规模卫星集群上的性能，在50颗卫星组成的卫星集 > 1.356 0.029 0.010 0.018 群上重新测试实验1中的6组任务数据。但由于 3.925 0.032 0.025 0.071 T℉CA算法运行时间太长（在50颗卫星组成的集群 上，对12个任务构建团队时，运行超过12h仍然不 11 14.640 0.039 0.033 0.014 能给出有效结果)我们仅对比HTFA-S、HTFA-RC和 13 20.877 0.042 0.016 0.009 HTFA-C的实验结果，如图2、3所示。 0.014 200 41.286 0.045 0.007 HTFA-S 150 OHTFA-RC ■HTFA-C 250 225 OTFCA 图HITFA-S 100 2 138 ▣HTFA-RC ■HTFA-C 50 12 10 12 14 16 18 20 29 任务数量/个 N 图23种启发式算法在LSC上的性能对比 9 11 13 Fig.2 Performances of three algorithms in LSC 卫星数量/个 30 图44种算法在不同规模卫星集群上的性能对比 3 .HTFA-S Fig.4 Performances of four algorithms in different 20 -HTFA-RC scales of SC HTFA-C 图4是在中小规模的多个卫星集群上对同一组 任务数据构建团队对比4种算法的性能。随着卫星 5 规模的逐步增大，团队的代价越来越小。多数情况 下，HTFA-C、HTFA-RC算法的性能优于HTFA-S算 10 12 141618 20 任务数量/个 法。从表3中可以看出，T℉CA算法的运行时间随 图33种启发式算法在LSC上的运行时间对比 着集群规模增大爆发式增长。而HTFA-S、HTFA Fig.3 Time comparison of three algorithms in LSC RC、HTFA-C算法的运行时间增长不明显。表 ２ ４ 种算法在小规模卫星集群上的运行时间对比 Ｔａｂｌｅ ２ Ｒｕｎｎｉｎｇ ｔｉｍｅ ｏｆ ｆｏｕｒ ａｌｇｏｒｉｔｈｍｓ ｉｎ ＳＳＣ ｓ 任务数量 ＴＦＣＡ ＨＴＦＡ⁃Ｓ ＨＴＦＡ⁃ＲＣ ＨＴＦＡ⁃Ｃ １０ ７．５９１ ０．０２６ ０．０５４ ０．０５４ １２ ４２．４７９ ０．１０７ ０．０５７ ０．０８８ １４ １５３．３７９ ０．１７９ ０．０９６ ０．２０９ １６ １ ０８６．７４９ ０．１７９ ０．１５８ ０．１５８ １８ ８ ０１９．７４９ ０．２５８ ０．３９９ １．３３９ ２０ ９０ ０７８．３６９ ０．４１８ １．２４１ ２．０９６ 从图 １ 可以看出，在小规模卫星集群中，ＨＴＦＡ⁃ Ｓ、ＨＴＦＡ⁃ＲＣ、 ＨＴＦＡ⁃Ｃ 算法构建的团队效果接近 ＴＦＣＡ 算法。 ＨＴＦＡ⁃Ｓ 算法由于任务输入的无序性， 在大部 分 情 况 下 构 建 团 队 的 效 果 比 ＨＴＦＡ⁃ＲＣ、 ＨＴＦＡ⁃Ｃ 算法差。 表 ２ 展示了 ４ 种算法的时间特 性，ＴＦＣＡ 算法的运行时间随着任务的增多，呈现指 数增长趋势，ＨＴＦＡ⁃Ｓ、ＨＴＦＡ⁃ＲＣ、ＨＴＦＡ⁃Ｃ 算法的运 行时间增长缓慢。 实验 ２ 为了进一步验证我们提出的算法在大 规模卫星集群上的性能，在 ５０ 颗卫星组成的卫星集 群上重新测试实验 １ 中的 ６ 组任务数据。 但由于 ＴＦＣＡ 算法运行时间太长（在 ５０ 颗卫星组成的集群 上，对 １２ 个任务构建团队时，运行超过 １２ ｈ 仍然不 能给出有效结果）我们仅对比 ＨＴＦＡ⁃Ｓ、ＨＴＦＡ⁃ＲＣ 和 ＨＴＦＡ⁃Ｃ 的实验结果，如图 ２、３ 所示。 图 ２ ３ 种启发式算法在 ＬＳＣ 上的性能对比 Ｆｉｇ．２ Ｐｅｒｆｏｒｍａｎｃｅｓ ｏｆ ｔｈｒｅｅ ａｌｇｏｒｉｔｈｍｓ ｉｎ ＬＳＣ 图 ３ ３ 种启发式算法在 ＬＳＣ 上的运行时间对比 Ｆｉｇ．３ Ｔｉｍｅ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｔｈｒｅｅ ａｌｇｏｒｉｔｈｍｓ ｉｎ ＬＳＣ 图 ２ 展现了在大规模卫星集群上 ＨＴＦＡ⁃Ｓ、 ＨＴＦＡ⁃ＲＣ、ＨＴＦＡ⁃Ｃ 算法的性能 差 异。 ＨＴＦＡ⁃ＲＣ、 ＨＴＦＡ⁃Ｃ 算法构建团队的效果普遍优于 ＨＴＦＡ⁃Ｓ 算 法。 从图 ３ 中可以看出，随着任务增多，ＨＴＦＡ⁃Ｓ、 ＨＴＦＡ⁃ＲＣ、ＨＴＦＡ⁃Ｃ 算法构建团队时间都在逐渐增 加，而 ＨＴＦＡ⁃Ｃ 构建团队时间的增长速度明显高于 ＨＴＦＡ⁃Ｓ 和 ＨＴＦＡ⁃ＲＣ，这是因为 ＨＴＦＡ⁃Ｃ 任务的有 序性在相同的剪枝策略下相比于其他两种算法， ＨＴＦＡ⁃Ｃ 在每一层会更多地保留效果好的分枝，因 此整个团队构建过程中，搜索的分枝更多。 实验 ３ 随机生成一组由 １０ 个任务构成的任 务集合，在不同规模的卫星集群上构建团队，比较 ＴＦＣＡ、ＨＴＦＡ⁃Ｓ、ＨＴＦＡ⁃Ｃ、ＨＴＦＡ⁃ＲＣ 算法性能，实验 结果如表 ３、图 ４ 所示。 表 ３ ４ 种算法的运行时间对比 Ｔａｂｌｅ ３ Ｒｕｎｎｉｎｇ ｔｉｍｅ ｏｆ ｆｏｕｒ ａｌｇｏｒｉｔｈｍｓ ｓ 卫星数量／ 个 ＴＦＣＡ ＨＴＦＡ⁃Ｓ ＨＴＦＡ⁃ＲＣ ＨＴＦＡ⁃Ｃ ５ ０．１５８ ０．００７ ０．００７ ０．０１４ ７ １．３５６ ０．０２９ ０．０１０ ０．０１８ ９ ３．９２５ ０．０３２ ０．０２５ ０．０７１ １１ １４．６４０ ０．０３９ ０．０３３ ０．０１４ １３ ２０．８７７ ０．０４２ ０．０１６ ０．００９ １５ ４１．２８６ ０．０４５ ０．０１４ ０．００７ 图 ４ ４ 种算法在不同规模卫星集群上的性能对比 Ｆｉｇ． ４ Ｐｅｒｆｏｒｍａｎｃｅｓ ｏｆ ｆｏｕｒ ａｌｇｏｒｉｔｈｍｓ ｉｎ ｄｉｆｆｅｒｅｎｔ ｓｃａｌｅｓ ｏｆ ＳＣ 图 ４ 是在中小规模的多个卫星集群上对同一组 任务数据构建团队对比 ４ 种算法的性能。 随着卫星 规模的逐步增大，团队的代价越来越小。 多数情况 下，ＨＴＦＡ⁃Ｃ、ＨＴＦＡ⁃ＲＣ 算法的性能优于 ＨＴＦＡ⁃Ｓ 算 法。 从表 ３ 中可以看出，ＴＦＣＡ 算法的运行时间随 着集群规模增大爆发式增长。 而 ＨＴＦＡ⁃Ｓ、ＨＴＦＡ⁃ ＲＣ、ＨＴＦＡ⁃Ｃ 算法的运行时间增长不明显。 ·６５８· 智 能 系 统 学 报 第 １２ 卷