第5期 杨舒，等：一种面向任务的对地观测卫星Aget团队构建方法 ·657. pruning strategy,HTFA),算法伪码如算法4所示。 团队的代价偏大。为此，对输人任务集合TaskSet 算法4是基于剪枝策略的启发式算法，以teamo 进行排序： 作为根节点，从第1个任务开始搜索，TEAM是所 1)记无序的任务集合为TaskSet-S,以TaskSet-S 有完成task,的team集合，对TEAM1中每个team, 作为输入的HTFA算法为HTFA-S; 搜索ask,以此类推直到搜索到TEAM。语句8)~ 2)根据任务代价由高到低排序的任务集合为 22)是根据剪枝策略对TEAMy进行的剪枝操作。 TaskSet-.C,以TaskSet-C作为输入的HTFA算法为 算法4HTFA HTFA-C: 功能基于剪枝策略的启发式算法； 3)根据任务性价比由高到低排序的任务集合 输入TaskSet,SatSet,teamo; 为TaskSet-RC,以TaskSet--RC作为输入的HTFA算 输出team。 法为HTFA-RC。 1)Begin 4实验与分析 2)set TEAM:=☑，i∈(0，M) 3)TEAM。=TEAM。U{team,} 为了验证TFCA算法、HTFA-S算法、HTFA-C 算法、HTFA-RC算法的性能，设计了4组实验。 4)for(i=1:i≤M:i++) 计算平台：ntel(R)Core(TM)i5-6400CPU@ 5)for each teamin TEAM- 2.70GHz(4CPUs),内存8192 MB RAM,操作系统 6)set TEAM,=☑ Win7,采用Microsoft Visual Studio2010C#编码。 7)solve(1,team,teamSet,i) 实验数据在STK卫星数据库中选取50颗低 8)for each team,in teamSet 轨卫星数据模拟卫星集群的运行，以全球100个重 9)if(TEAM:= 要城市作为观测目标，从中随机挑选。设定每颗卫 10)TEAM,=TEAM,U{team, 星上携带可见光、红外、电磁探测、多光谱、超光谱5 11)else 种载荷。根据卫星硬件情况，设置卫星使用代价 12)for each team,in TEAM SC:=a(|Btasks:,|+|TW_used:)中的参数a,随机 l3)if(team1>team,） 挑选1~5个时间窗作为卫星上已经被占用的时间 14)TEAM,TEAM /(team2} 窗集合TW_used。采用随机生成一组任务的方式， 15)TEAM,TEAM,U (team 模拟真实环境下一段时间内卫星系统接收到的待 16)else 规划任务集合。 17)if(team2 team) 卫星集群按照卫星成员的数量可以分为小规 18)break 模卫星集群(small--scale satellite cluster,SSC)和大 19)else 规模卫星集群(large-scale satellite cluster,LSC)。 20)TEAM,TEAM,U {team,) 小规模卫星集群中成员数量在10颗以下，大规模卫 21)end for 星集群的成员数量大于10颗。 22)end for 实验1随机生成6组任务，在10颗卫星构成 23)end for 的小规模集群上采用TFCA、HTFA-S、HTFA-C、 24)end for HTFA-RC构建团队，比较4种算法的性能。实验结 25)for each team in TEAM 果如图1和表2。 26)if(team.Cost teamu".Cost 450r 400 OTFCA 27)teamur"=team 350 HTFA-S 28)end for 300 题HTFA-RC 250 ■HTFA-C 29)return team 200 30)End 150 100 由于HTFA算法的这种剪枝策略，TaskSet的输 50 入顺序可能会影响算法最终输出结果。如果在随 0 10 12 141618 20 机的任务集合中，代价小的任务排在前面，HT℉A将 任务数量/个 会优先挑选代价小的卫星执行该任务，代价大的任 图14种算法在小规模卫星集群上的性能对比 务只能选择代价大的卫星，会使最终构建出的卫星 Fig.1 Performances of four algorithms in SSCｐｒｕｎｉｎｇ ｓｔｒａｔｅｇｙ， ＨＴＦＡ），算法伪码如算法 ４ 所示。 算法 ４ 是基于剪枝策略的启发式算法，以 ｔｅａｍ０ 作为根节点，从第 １ 个任务开始搜索，ＴＥＡＭ１ 是所 有完成 ｔａｓｋ１ 的 ｔｅａｍ 集合，对 ＴＥＡＭ１ 中每个 ｔｅａｍ， 搜索 ｔａｓｋ２ ，以此类推直到搜索到 ＴＥＡＭＭ 。 语句８） ～ ２２）是根据剪枝策略对 ＴＥＡＭＭ 进行的剪枝操作。 算法 ４ ＨＴＦＡ 功能 基于剪枝策略的启发式算法； 输入 ＴａｓｋＳｅｔ， ＳａｔＳｅｔ，ｔｅａｍ０ ； 输出 ｔｅａｍ ｂｅｓｔ Ｍ 。 １） Ｂｅｇｉｎ ２） ｓｅｔ ＴＥＡＭｉ ＝ ∅，ｉ ∈ （０，Ｍ） ３） ＴＥＡＭ０ ＝ ＴＥＡＭ０ ∪ ｔｅａｍ０ { } ４）ｆｏｒ（ｉ ＝ １； ｉ ≤ Ｍ ；ｉ＋＋） ５）ｆｏｒ ｅａｃｈ ｔｅａｍｉｎ ＴＥＡＭｉ－１ ６）ｓｅｔ ＴＥＡＭｉ ＝ ∅ ７）ｓｏｌｖｅ（１，ｔｅａｍ，ｔｅａｍＳｅｔ，ｉ） ８）ｆｏｒ ｅａｃｈ ｔｅａｍ１ ｉｎ ｔｅａｍＳｅｔ ９）ｉｆ（ ＴＥＡＭｉ ＝ ∅ ） １０） ＴＥＡＭｉ ＝ ＴＥＡＭｉ ∪ ｔｅａｍ１ { } １１）ｅｌｓｅ １２）ｆｏｒ ｅａｃｈ ｔｅａｍ２ ｉｎ ＴＥＡＭｉ １３）ｉｆ（ ｔｅａｍ１ ＞ ｔｅａｍ２ ） １４） ＴＥＡＭｉ ＝ ＴＥＡＭｉ ／ ｔｅａｍ２ { } １５） ＴＥＡＭｉ ＝ ＴＥＡＭｉ ∪ ｔｅａｍ１ { } １６）ｅｌｓｅ １７）ｉｆ（ ｔｅａｍ２ ＞ ｔｅａｍ１ ） １８）ｂｒｅａｋ １９）ｅｌｓｅ ２０） ＴＥＡＭｉ ＝ ＴＥＡＭｉ ∪ ｔｅａｍ１ { } ２１）ｅｎｄ ｆｏｒ ２２）ｅｎｄ ｆｏｒ ２３）ｅｎｄ ｆｏｒ ２４）ｅｎｄ ｆｏｒ ２５）ｆｏｒ ｅａｃｈ ｔｅａｍ ｉｎ ＴＥＡＭＭ ２６） ｉｆ（ ｔｅａｍ．Ｃｏｓｔ ＜ ｔｅａｍ ｂｅｓｔ Ｍ ．Ｃｏｓｔ ） ２７） ｔｅａｍ ｂｅｓｔ Ｍ ＝ ｔｅａｍ ２８）ｅｎｄ ｆｏｒ ２９）ｒｅｔｕｒｎ ｔｅａｍ ｂｅｓｔ Ｍ ３０） Ｅｎｄ 由于 ＨＴＦＡ 算法的这种剪枝策略，ＴａｓｋＳｅｔ 的输 入顺序可能会影响算法最终输出结果。 如果在随 机的任务集合中，代价小的任务排在前面，ＨＴＦＡ 将 会优先挑选代价小的卫星执行该任务，代价大的任 务只能选择代价大的卫星，会使最终构建出的卫星 团队的代价偏大。 为此，对输入任务集合 ＴａｓｋＳｅｔ 进行排序： １）记无序的任务集合为 ＴａｓｋＳｅｔ⁃Ｓ，以 ＴａｓｋＳｅｔ⁃Ｓ 作为输入的 ＨＴＦＡ 算法为 ＨＴＦＡ⁃Ｓ； ２）根据任务代价由高到低排序的任务集合为 ＴａｓｋＳｅｔ⁃Ｃ，以 ＴａｓｋＳｅｔ⁃Ｃ 作为输入的 ＨＴＦＡ 算法为 ＨＴＦＡ⁃Ｃ； ３）根据任务性价比由高到低排序的任务集合 为 ＴａｓｋＳｅｔ⁃ＲＣ，以 ＴａｓｋＳｅｔ⁃ＲＣ 作为输入的 ＨＴＦＡ 算 法为 ＨＴＦＡ⁃ＲＣ。 ４ 实验与分析 为了验证 ＴＦＣＡ 算法、ＨＴＦＡ－Ｓ 算法、ＨＴＦＡ－Ｃ 算法、ＨＴＦＡ－ＲＣ 算法的性能，设计了 ４ 组实验。 计算平台：Ｉｎｔｅｌ（Ｒ） Ｃｏｒｅ（ＴＭ） ｉ５⁃６４００ ＣＰＵ ＠ ２．７０ ＧＨｚ （４ ＣＰＵｓ），内存 ８１９２ ＭＢ ＲＡＭ，操作系统 Ｗｉｎ７，采用 Ｍｉｃｒｏｓｏｆｔ Ｖｉｓｕａｌ Ｓｔｕｄｉｏ ２０１０ Ｃ＃编码。 实验数据 在 ＳＴＫ 卫星数据库中选取 ５０ 颗低 轨卫星数据模拟卫星集群的运行，以全球 １００ 个重 要城市作为观测目标，从中随机挑选。 设定每颗卫 星上携带可见光、红外、电磁探测、多光谱、超光谱 ５ 种载荷。 根据卫星硬件情况，设置卫星使用代价 ＳＣｉ ＝ α Ｂｔａｓｋｓｉ ＋ ＴＷ＿ｕｓｅｄｉ ( ) 中的参数 α，随机 挑选 １～５ 个时间窗作为卫星上已经被占用的时间 窗集合 ＴＷ＿ｕｓｅｄ。 采用随机生成一组任务的方式， 模拟真实环境下一段时间内卫星系统接收到的待 规划任务集合。 卫星集群按照卫星成员的数量可以分为小规 模卫星集群（ ｓｍａｌｌ⁃ｓｃａｌｅ ｓａｔｅｌｌｉｔｅ ｃｌｕｓｔｅｒ， ＳＳＣ） 和大 规模卫星集群 （ ｌａｒｇｅ⁃ｓｃａｌｅ ｓａｔｅｌｌｉｔｅ ｃｌｕｓｔｅｒ， ＬＳＣ）。 小规模卫星集群中成员数量在 １０ 颗以下，大规模卫 星集群的成员数量大于 １０ 颗。 实验 １ 随机生成 ６ 组任务，在 １０ 颗卫星构成 的小 规 模 集 群 上 采 用 ＴＦＣＡ、 ＨＴＦＡ⁃Ｓ、 ＨＴＦＡ⁃Ｃ、 ＨＴＦＡ⁃ＲＣ 构建团队，比较 ４ 种算法的性能。 实验结 果如图 １ 和表 ２。 图 １ ４ 种算法在小规模卫星集群上的性能对比 Ｆｉｇ．１ Ｐｅｒｆｏｒｍａｎｃｅｓ ｏｆ ｆｏｕｒ ａｌｇｏｒｉｔｈｍｓ ｉｎ ＳＳＣ 第 ５ 期 杨舒，等：一种面向任务的对地观测卫星 Ａｇｅｎｔ 团队构建方法 ·６５７·