·656· 智能系统学报 第12卷 5)End 队，首先将最优团队teamy置为空，语句3)是以初 我们采用深度优先策略进行树搜索，以当前搜 始团队team。为根节点的迭代搜索。 索到的能够胜任任务集合中所有任务的最优团队 算法2从第m个任务开始搜索构建团队的迭 team的代价作为上界，根据分支限界法对树进行 代算法，语句2)~5)表示该分支的team构建完成， 剪枝，即对于当前正在构建的卫星任务团队 如果team的代价小于team的代价或者team为 Curteam,如果： 空，则更新team为最佳团队并结束该分支搜索。语 Curteam.Cost≥team·Cost 句7)~8)为基于分枝限界思想的剪枝过程，当team 则减去Curteam这个节点向下的所有分枝。 还不能胜任所有的任务，而其代价已经大于等于 基于这种搜索剪枝策略，提出了基于分枝限界 team的代价，则结束该分支搜索。语句9)表示在 思想的团队构建算法(team formation complete 当前team的情况下，完成task.产生的所有方案存 algorithm based-on a branch and bound techniques, 入teamSet。语句l0)~l2)对teamSet中的每个team TFCA),伪代码如算法1、2、3所示。 进入下一任务的搜索。 算法2 TFOfEachTask 算法3寻找在当前team下，能完成task.的所 功能从第m个任务开始搜索构建团队的迭 有团队的迭代算法。在当前team的情况，依次判断 代算法。 每颗卫星Sat,能否完成task,如果能完成，则生成 输入m,team,team; 新团队team1,并将该team,加入teamSet。 输出目标找到的最优团队team。 由算法的迭代过程可以看出，如果针对M个任 1)Begin 务，在N个卫星中构建团队，在最坏的情况下即每 2)if(m>M) 颗卫星都有能力执行所有的任务，而且没有任何剪 3)if(team.Cost<team .Costl I teamb= 枝操作发生，于是有TEAM:=N,那么迭代过程中 4)teamw team 5)Return 形成的方案总数为∑“TEA,=∑“N,该算 6)else if(team.Cost team.Cost&&team=) 法的时间复杂度为O(N+)。 7)Return 由上述分析可知，在最坏的情况下，算法时间 8)end if 复杂度将呈指数增长，该问题组合爆炸特征明显。 9)solve(1,team,teamSet,m) 为了降低基于分枝限界思想的团队构建算法的时 10)for each team in teamSet 间复杂度，提出了一种基于剪枝策略的启发式算法。 11)TFOfEachTask(m+1 team,team) 3 基于剪枝策略的启发式算法 12)end for 13)End 通过T℉CA算法进行树搜索，首先要找到一个 算法3 solve 胜任所有任务的团队，以这个团队的代价作为上界 功能寻找team向下能完成task的团队的迭 才可以进行剪枝操作，运行时间较长，剪掉的分支 代算法： 有限，效率较低，为了提高树搜索效率，需要寻找一 输入n,team,teamSet,m; 种新的剪枝策略。 输出当前team下能完成task的团队集合 我们将深度优先的搜索方式改成广度优先，对 teamSet 每一层的团队集合TEAM进行剪枝操作，从而达到 1)Begin 减少树分枝，降低时间复杂度的目的。 2)if(n>N) 首先，给出剪枝策略。设team1,team2∈ 3)Return TEAM,如果 4)else if(Satn能完成task) team1.Cost≥1+ teamz.Cost 5)teaml Update(team) 6)teamSet =teamSetU teaml 0<e<1记为team,<team2,则剪去team,这 7)solve(n+1,team,teamSet,m) 个团队所在的结点。其中，i是TEAM中的每个团 8)end if 队完成的任务个数，ε根据卫星初始状态调整，尽量 9)End 为团队挑选承担任务数少的卫星。 算法1是基于分枝限界思想的团队构建算法的 基于这种剪枝策略，提出了启发式团队构建算 主算法，采用深度优先的搜索方式遍历所有的团 heuristic team formation algorithm based-on a５） Ｅｎｄ 我们采用深度优先策略进行树搜索，以当前搜 索到的能够胜任任务集合中所有任务的最优团队 ｔｅａｍ ｂｅｓｔ Ｍ 的代价作为上界，根据分支限界法对树进行 剪枝， 即 对 于 当 前 正 在 构 建 的 卫 星 任 务 团 队 Ｃｕｒｔｅａｍ，如果： Ｃｕｒｔｅａｍ．Ｃｏｓｔ ≥ ｔｅａｍ ｂｅｓｔ Ｍ ·Ｃｏｓｔ 则减去 Ｃｕｒｔｅａｍ 这个节点向下的所有分枝。 基于这种搜索剪枝策略，提出了基于分枝限界 思想 的 团 队 构 建 算 法 （ ｔｅａｍ ｆｏｒｍａｔｉｏｎ ｃｏｍｐｌｅｔｅ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ⁃ｏｎ ａ ｂｒａｎｃｈ ａｎｄ ｂｏｕｎｄ ｔｅｃｈｎｉｑｕｅｓ， ＴＦＣＡ），伪代码如算法 １、２、３ 所示。 算法 ２ ＴＦＯｆＥａｃｈＴａｓｋ 功能 从第 ｍ 个任务开始搜索构建团队的迭 代算法。 输入 ｍ， ｔｅａｍ， ｔｅａｍ ｂｅｓｔ Ｍ ； 输出 目标找到的最优团队 ｔｅａｍ ｂｅｓｔ Ｍ 。 １）Ｂｅｇｉｎ ２）ｉｆ（ｍ＞Ｍ） ３） ｉｆ（ｔｅａｍ．Ｃｏｓｔ＜ ｔｅａｍ ｂｅｓｔ Ｍ ．Ｃｏｓｔ ｜ ｜ ｔｅａｍ ｂｅｓｔ Ｍ ＝ ∅ ４） ｔｅａｍ ｂｅｓｔ Ｍ ＝ ｔｅａｍ ５）Ｒｅｔｕｒｎ ６）ｅｌｓｅ ｉｆ（ ｔｅａｍ． Ｃｏｓｔ ＞ ｔｅａｍ ｂｅｓｔ Ｍ ．Ｃｏｓｔ＆＆ｔｅａｍ ｂｅｓｔ Ｍ ＝ ∅） ７）Ｒｅｔｕｒｎ ８）ｅｎｄ ｉｆ ９）ｓｏｌｖｅ（１，ｔｅａｍ，ｔｅａｍＳｅｔ，ｍ） １０）ｆｏｒ ｅａｃｈ ｔｅａｍ ｉｎ ｔｅａｍＳｅｔ １１）ＴＦＯｆＥａｃｈＴａｓｋ（ｍ＋１ ，ｔｅａｍ ， ｔｅａｍ ｂｅｓｔ Ｍ ） １２）ｅｎｄ ｆｏｒ １３）Ｅｎｄ 算法 ３ ｓｏｌｖｅ 功能 寻找 ｔｅａｍ 向下能完成 ｔａｓｋｍ的团队的迭 代算法； 输入 ｎ， ｔｅａｍ， ｔｅａｍＳｅｔ， ｍ； 输出 当前 ｔｅａｍ 下能完成 ｔａｓｋｍ 的团队集合 ｔｅａｍＳｅｔ。 １）Ｂｅｇｉｎ ２）ｉｆ（ｎ＞Ｎ） ３）Ｒｅｔｕｒｎ ４）ｅｌｓｅ ｉｆ（Ｓａｔ ｎ能完成 ｔａｓｋｍ ） ５）ｔｅａｍ１ ＝Ｕｐｄａｔｅ（ｔｅａｍ） ６）ｔｅａｍＳｅｔ ＝ ｔｅａｍＳｅｔ∪｛ｔｅａｍ１｝ ７）ｓｏｌｖｅ（ｎ＋１，ｔｅａｍ，ｔｅａｍＳｅｔ，ｍ） ８）ｅｎｄ ｉｆ ９）Ｅｎｄ 算法 １ 是基于分枝限界思想的团队构建算法的 主算法，采用深度优先的搜索方式遍历所有的团 队，首先将最优团队 ｔｅａｍ ｂｅｓｔ Ｍ 置为空，语句 ３）是以初 始团队 ｔｅａｍ０ 为根节点的迭代搜索。 算法 ２ 从第 ｍ 个任务开始搜索构建团队的迭 代算法，语句 ２） ～ ５）表示该分支的 ｔｅａｍ 构建完成， 如果 ｔｅａｍ 的代价小于 ｔｅａｍ ｂｅｓｔ Ｍ 的代价或者 ｔｅａｍ ｂｅｓｔ Ｍ 为 空，则更新 ｔｅａｍ 为最佳团队并结束该分支搜索。 语 句 ７） ～８）为基于分枝限界思想的剪枝过程，当 ｔｅａｍ 还不能胜任所有的任务，而其代价已经大于等于 ｔｅａｍ ｂｅｓｔ Ｍ 的代价，则结束该分支搜索。 语句 ９）表示在 当前 ｔｅａｍ 的情况下，完成 ｔａｓｋｍ产生的所有方案存 入 ｔｅａｍＳｅｔ。 语句 １０） ～１２）对 ｔｅａｍＳｅｔ 中的每个 ｔｅａｍ 进入下一任务的搜索。 算法 ３ 寻找在当前 ｔｅａｍ 下，能完成 ｔａｓｋｍ的所 有团队的迭代算法。 在当前 ｔｅａｍ 的情况，依次判断 每颗卫星 Ｓａｔ ｎ 能否完成 ｔａｓｋｍ ，如果能完成，则生成 新团队 ｔｅａｍ１ ，并将该 ｔｅａｍ１ 加入 ｔｅａｍＳｅｔ。 由算法的迭代过程可以看出，如果针对 Ｍ 个任 务，在 Ｎ 个卫星中构建团队，在最坏的情况下即每 颗卫星都有能力执行所有的任务，而且没有任何剪 枝操作发生，于是有 ＴＥＡＭｉ ＝ Ｎ ｉ ，那么迭代过程中 形成的方案总数为 ∑ Ｍ ｉ ＝ １ ＴＥＡＭｉ ＝ ∑ Ｍ ｉ ＝ １ Ｎ ｉ ，该算 法的时间复杂度为 Ｏ（Ｎ Ｍ＋１ ）。 由上述分析可知，在最坏的情况下，算法时间 复杂度将呈指数增长，该问题组合爆炸特征明显。 为了降低基于分枝限界思想的团队构建算法的时 间复杂度，提出了一种基于剪枝策略的启发式算法。 ３ 基于剪枝策略的启发式算法 通过 ＴＦＣＡ 算法进行树搜索，首先要找到一个 胜任所有任务的团队，以这个团队的代价作为上界 才可以进行剪枝操作，运行时间较长，剪掉的分支 有限，效率较低，为了提高树搜索效率，需要寻找一 种新的剪枝策略。 我们将深度优先的搜索方式改成广度优先，对 每一层的团队集合 ＴＥＡＭ 进行剪枝操作，从而达到 减少树分枝，降低时间复杂度的目的。 首 先， 给 出 剪 枝 策 略。 设 ｔｅａｍ１ ， ｔｅａｍ２ ∈ ＴＥＡＭｉ，如果 ｔｅａｍ１ ．Ｃｏｓｔ ≥ １ ＋ ε ｉ æ è ç ö ø ÷ ｔｅａｍ２ ．Ｃｏｓｔ ０ ＜ ε ＜ １ 记为 ｔｅａｍ１ ＜ ｔｅａｍ２ ，则剪去 ｔｅａｍ１ 这 个团队所在的结点。 其中，ｉ 是 ＴＥＡＭｉ 中的每个团 队完成的任务个数， ε 根据卫星初始状态调整，尽量 为团队挑选承担任务数少的卫星。 基于这种剪枝策略，提出了启发式团队构建算 法 （ ｈｅｕｒｉｓｔｉｃ ｔｅａｍ ｆｏｒｍａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ⁃ｏｎ ａ ·６５６· 智 能 系 统 学 报 第 １２ 卷