·490· 智能系统学报 第16卷 试CSA算法在不同通信半径条件下的求解效率， 人机个体数量n”与“边数/总边数（即完全图中的 实验结果如图9所示。 边数n(n-1)/2)”间的关系。 实验结果如图11所示。从图11中可以看 1.0 0.9 出，随着边数占比趋于1，领航顶点占比趋于 0.8 (n-1)/;随着边数占比趋于0，领航顶点占比趋 能0.7 ￥0.6 8odes 于1；特别是，领航顶点占比达最小。从图11 0.5 50 nodes -。-70 nodes 中可以看出，当无人机个体数量为10时，领航顶 0.4 0.3 点占比达最小的情况出现在边数占比为 0 4 6 810 通信半径dm 0.6~0.7;当无人机个体的数量为30时，领航顶点 占比达最小的情况出现在边数占比为0.4~0.6： 图9CSA算法求解效率与通信半径的关系 当无人机个体的数量为50(70)时，领航顶点占比 Fig.9 Relationship between the efficiency of CSA and communication radius of UAV 达最小的情况出现在边数占比为01~0.3。也就 从图9中可以看出，尽管CSA算法在求解过 是说，从整体上看，所有“领航顶点占比与边数占 程有一定程度的抖动，但当顶点个数小于30时， 比”曲线都是下凸曲线，无人机个体数越多，曲线 求解效率在95%上。一个有趣的现象是，当顶点 越向下凸且极小值点越向“左”偏。这一现象说 个数大于30时，若其通信半径介于3~9，则 明，若用较少个数的无人机个体控制整个无人机 CSA算法几乎100%可以找到领航集；若通信半 集群，则通信网络拓扑结构图中的边数应取值于 径小于3或大于9，则CSA算法都出现了不同程 适当范围，实验3从统计意义上给出了这个范围。 度的抖动，特别是当通信半径介于0.5~3时，算法 1.04 求解效率较差。出现这一现象的原因在于，此时 0.8 50nodes 图中单重特征值减少而多重特征值增加，这使得 出 同一特征值对应的关键集增加，而基于本文给出 的定理2~5，CSA算法只求出2关键集、3关键集 0.4 和孤立关键集等一些特殊的关键集，从而使得算 0.2 法难以找到领航集。例如，见图10，该无向网络 的特征值中，除单重特征值外，还有1个3重特征 0.2 0.40.6 0.8 1.0 值、1个4重特征值和1个5重特征值，CSA算法 边占比 难以找到它的领航集。这说明，当顶点个数多且 图11领航顶点个数与边数的关系 通信半径较小时，图中的关键集情况较复杂，需 Fig.11 Relationship between the number of leaders and edges 要进一步从理论上研究k关键集的图特征。 10 4结束语 本文以几十架无人机构成的无人机集群为应 用背景，利用Laplace矩阵的特征向量提出关键集 概念，指出领航集所必须具备的图特征，即领航 集需覆盖所有关键集。给出了2关键集和3关键 集的图特征，从图论角度给出独立集成为关键集 的一个充分条件。数值实验表明，基于关键集， 4 CSA算法在大多数情况下能以90%以上的概率 x/m 搜索到领航集。 图10复杂特征值情况的网络结构 如何刻画k(k≥4)关键集的图特征是需进一 Fig.10 Description of networks with multiple eigenvalues 步研究的内容。这是十分难以解决的问题，比如 实验3领航顶点个数与边数关系。 由图2知4关键集与这4个顶点的相邻关系有 随着无人机个体和边数的变化，领航顶点的 关，全体4阶互不同构的简单图有11个，其中边 个数也会相应地变化，因此，本实验不考虑领航 数为0、1、2、3、4、5、6的图的个数分别为1、1、 顶点个数的绝对值，而是考虑“领航顶点个数/无 2、3、2、1、1。而全体5阶互不同构的简单图有试 CSA 算法在不同通信半径条件下的求解效率， 实验结果如图 9 所示。 0 2 4 6 8 10 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 概率 10 nodes 30 nodes 50 nodes 70 nodes 通信半径 d/m 图 9 CSA 算法求解效率与通信半径的关系 Fig. 9 Relationship between the efficiency of CSA and communication radius of UAV k 从图 9 中可以看出，尽管 CSA 算法在求解过 程有一定程度的抖动，但当顶点个数小于 30 时， 求解效率在 95% 上。一个有趣的现象是，当顶点 个数大 于 30 时，若其通信半径介 于 3～ 9， 则 CSA 算法几乎 100% 可以找到领航集；若通信半 径小于 3 或大于 9，则 CSA 算法都出现了不同程 度的抖动，特别是当通信半径介于 0.5~3 时，算法 求解效率较差。出现这一现象的原因在于，此时 图中单重特征值减少而多重特征值增加，这使得 同一特征值对应的关键集增加，而基于本文给出 的定理 2~5，CSA 算法只求出 2 关键集、3 关键集 和孤立关键集等一些特殊的关键集，从而使得算 法难以找到领航集。例如，见图 10，该无向网络 的特征值中，除单重特征值外，还有 1 个 3 重特征 值、1 个 4 重特征值和 1 个 5 重特征值，CSA 算法 难以找到它的领航集。这说明，当顶点个数多且 通信半径较小时，图中的关键集情况较复杂，需 要进一步从理论上研究 关键集的图特征。 0 2 4 6 8 10 1 2 3 4 5 6 7 8 9 10 x/m y/m 图 10 复杂特征值情况的网络结构 Fig. 10 Description of networks with multiple eigenvalues 实验 3 领航顶点个数与边数关系。 随着无人机个体和边数的变化，领航顶点的 个数也会相应地变化，因此，本实验不考虑领航 顶点个数的绝对值，而是考虑“领航顶点个数/无 n n(n−1)/2 人机个体数量 ”与“边数/总边数 (即完全图中的 边数 )”间的关系。 (n−1)/n 0.6 ∼ 0.7 0.4 ∼ 0.6 0.1 ∼ 0.3 实验结果如图 11 所示。从图 11 中可以看 出，随着边数占比趋于 1，领航顶点占比趋于 ；随着边数占比趋于 0，领航顶点占比趋 于 1；特别是，领航顶点占比达最小。从图 11 中可以看出，当无人机个体数量为 10 时，领航顶 点占比达最小的情况出现在边数占比为 ；当无人机个体的数量为 30 时，领航顶点 占比达最小的情况出现在边数占比为 ； 当无人机个体的数量为 50(70) 时，领航顶点占比 达最小的情况出现在边数占比为 。也就 是说，从整体上看，所有“领航顶点占比与边数占 比”曲线都是下凸曲线，无人机个体数越多，曲线 越向下凸且极小值点越向“左”偏。这一现象说 明，若用较少个数的无人机个体控制整个无人机 集群，则通信网络拓扑结构图中的边数应取值于 适当范围，实验 3 从统计意义上给出了这个范围。 0.2 0.4 0.6 0.8 1.0 边占比 0 0.2 0.4 0.6 0.8 1.0 领航顶点占比 10nodes 30nodes 50nodes 70nodes 图 11 领航顶点个数与边数的关系 Fig. 11 Relationship between the number of leaders and edges 4 结束语 本文以几十架无人机构成的无人机集群为应 用背景，利用 Laplace 矩阵的特征向量提出关键集 概念，指出领航集所必须具备的图特征，即领航 集需覆盖所有关键集。给出了 2 关键集和 3 关键 集的图特征，从图论角度给出独立集成为关键集 的一个充分条件。数值实验表明，基于关键集， CSA 算法在大多数情况下能以 90% 以上的概率 搜索到领航集。 如何刻画 k(k ⩾ 4) 关键集的图特征是需进一 步研究的内容。这是十分难以解决的问题，比如 由图 2 知 4 关键集与这 4 个顶点的相邻关系有 关，全体 4 阶互不同构的简单图有 11 个，其中边 数为 0、1、2、3、4、5、6 的图的个数分别为 1、1、 2、3、2、1、1。而全体 5 阶互不同构的简单图有 ·490· 智 能 系 统 学 报 第 16 卷