三维欧氏Steiner最小树的Delaunay四面体网格混合智能算法

1、三维欧氏 Steiner 最小树的 Delaunay 四面体网格混合智能算法文章标识码： A引言Steiner 树问题是指连接给定点的最小树长问题，其最优解称为 Steiner 最小树（Steiner Minimum Tree , SMT。根据点 和连线的空间属性， Steiner 树问题可进一步细分为欧氏Steiner 树（Eucliclean Steiner Tree , EST）问题和绝对值距 离 Steiner 树（Rectilinear Steiner Tree , RST）问题（连线 只有水平和垂直两种形式）。三维欧氏 Steiner 树问题是对二维欧氏 Steiner 树问题的推

2、广， 其计算的复杂性和求解的难度超过了二维欧氏 Steiner 树问题。 国内外对此问题的相关研究成果也较少， 以致对该问题的求 解方法极为欠缺。本文基于计算几何中 Delaunay 四面体网格的相关理论，利用智能算法， 没计了一种混合型智能求解方法， 其特点在于从几何的角度人手， 同时结合了智能算法的特点， 为该问题的实际求 解提供了有效方法。l 欧氏 Steiner 最小树问题定义给定原点集X （也称正则点集），欧氏 Steiner树是指连接点集 X 中所有点的最短树。 由于允许增加辅助点集S（ s 一点集） ，因此，欧氏Steiner最小树问题的本质就是寻求点集 S,使得连 接 xus

3、的生成树最小性质对于欧氏 Steiner 最小树问题， 若能设法求出 s 一点的数目与位置，就可用最小生成树算法对其进行求解，因此，问题的关键在于 s- 点的选取。下面，先列出几条关于二维欧氏 Steiner 最小树的基本性质：性质1 SMT上任何两条邻接边的夹角不小于120度。性质2 SMT 上任何一个顶点的关联边不多于三条。性质3 SMr 上与s 一点相关联的边必定为三条，且这三条边中任意两边夹角为 120 度。性质4设SMT勺原点为n个，则s-点的数目Wn -2。性质 5 假设由 n 个原点所围成的区域为凸壳，则所有s- 点都必定包含在凸壳内。性质 6 SMT 中每个叶子都是原点。在文献

4、和中已说明，上述6 条性质可推广到三维欧氏Steiner 最小树。拓扑结构 X=A1,，An为n个原点所成之集。令 G为一将此n个点连接起来的最小网络，若过G 的每个 s- 点皆有三条边通过，它们两两交成120 度的角， 且任何两条边不相交， 又若过其中每个原点只有一条边通过，则称G具有满拓扑。下面的所有讨论都假定欧氏 Steiner 最小树是满拓扑的。（ 1）二维的情况当 n=3， 4， 5 时， 有关的 Steiner 树只出现一种满拓扑结构，如图 1 所示。当n6时，则不止一种。例如，对于n=6时，则有如图2所示的三种满拓扑结构。（ 2）三维的情况当 n=4， 5 时，有关的 Stein

5、er 树同二维的情况一样，只出现一种满拓扑结构。 值得注意的现象是， 三维的情况相对于二维的情况来说， 只是在空间上以一个s 一点和另一个s 一点的连线作为轴， 将两侧的分支进行了旋转。 如： 图 l （ b） 对应图 3（ a） ， 图 l （ c ）对应图3（ b）。当n=6时，三维的情况则有所不同。图4中的3张图看似是对图 2 中二维的 3 种拓扑结构的推广，但是实际上图 4 中（ b）和（c）这两张图是同一个三维图像的不同观察角度，因此三维拓扑结构的分类变成了一件棘手的事情。 本文中将用 s 一点之间的连接方式来对不同的三维满拓扑结构进行归类。 当 s 一点的个数为 2 和 3 时，

6、显然只有一种连接方式。 当 s 一点的个数为 4 时，有两种连接方式。图4 （a）对应图5 （b）,图4 （b） （c）都对应图 5（ a ）。同理，当 s 一点的个数为 5 时，有三种连接方式，如图 6 。当 s 一点的个数为 6 时，有五种连接方式，如图 7当 s 一点的个数为 7 时，有九种连接方式，如图8。显然， 按照如上的归类方法， 连接方式的种数随着s 一点的个数增加而增加。在文献中，讨论了关于 3-Sausage 结构（即图5 、 6、 7、 8中（a）的结构）的三维欧氏Steiner最小树的一些性质，该文献指出，即使已知是3 -Sausage 结构的 Steiner 最小树，也

7、只能求得正则点数在15 个点以内的精确解。而在文献中， 讨论了二维欧氏 Steiner 最小树的正则点个数n 和二维中相应归类方法得到的归类数目，当 n=6 时，其归类数为 5625， 当 n=8 时则为 2643795。 如此庞大的数目只能依靠高速计算机来处理。当 n 稍大，例如大于 10 时，问题已不可能用枚举法来求解。又文献中提到， 三维欧氏 Steiner 最小树问题显然比二维欧氏 Steiner 最小树问题来得更为复杂。因此， 综合以上几点， 对于空间任意点要想求解其三维欧氏Steiner 最小树，如果不知道其确切的拓扑结构，即使规模很小（在 10 以内），都几乎难以使用精确算法进行

8、求解，所以，本文将介绍一种新型的混合智能求解算法来求解较大规模的该问题。2 空间点集 Delaunay 四面体网格的基本概念1 ） Delaunay 规则：空间四面体外接球面的内部不包含空间点集中的点作为四面体生成的一个约束条件， 称之为 Delaunay规则。 在平面上， 相应的约束条件为三角形的外接圆的内部不包 含点集中的点。2 ） Delaunay 三角形：符合Delaunay 规则的三角形称为Delaunay 三角形。3）最大空圆凸多边形：以某个Delaunay 三角形的外接圆上的所有点集中的点为顶点构成的凸多边形称为最大空圆凸多边形。4 ） Delaunay 四面体：符合Delaun

9、ay 规则的四面体称为Delaunay 四面体。5）最大空球凸多面体：以某个Delaunay 四面体的外接球面上的所有点集中的点为顶点构成的凸多面体称为最大空球凸多面体。6）凸壳：包含平面上一个点集在其所围闭区域内的最小凸多边形称为这个平面点集的凸壳。 包含空间一个点集在其所围闭区域内的最小凸多面体称为这个空间点集的凸壳。算法描述及示例第一步对给定的正则点集构建Delaunay 四面体网格。具体算法此处不赘述，操作相对简单，只需在Matlab 中调用函数Delaunay3 即可。第二步对第一步中所形成的凸多面体进行剖分。 剖分遵循如下规则：1）剖分必须沿着Delaunay 四面体网格中四面体的

10、面；2）找出每个四面体面积最大的面，如果该最大面为两个四面体的公共面，则将两个四面体拼接在一起。第三步利用智能算法对剖分后每一块区域的正则点进行Steiner 点求解。本环节所用智能算法的核心为遗传算法， 其基本原理是借鉴自生物进化思想的随机优化算法，通过选择、交叉、变异等操作产生下一代的解， 并逐步淘汰掉适应度值较低的解， 获得适应度值较高的解，经过多次这样的操作得出适应度最高的解。1）染色体的产生。本文求解三维欧氏 Steiner 最小树的遗传算法中，染色体的产生尤为关键。在 1.2 节中对于欧氏 Steiner 最小树的性质有这样的描述：假设由 n 个原点所围成的区域为凸壳，则所有s-

11、点都必定包含在凸壳内。 对于三维欧氏 Steiner 最小树来说， 凸壳即为包含所有原点的最小凸多面体。要想在凸多面体中生成一个随机点，这是一个棘手的问题。本文利用了 Delaunay 四面体网格的剖分算法，对原点进行了四面体网格剖分，且剖分后的四面体的集合刚好是原点的凸多面体。经上述剖分处理后， 产生染色体的方法为设置染色体的长度为（n-2） X3,每3个数代表一个s-点的x、y、z坐标。随机选择一个四面体， 在该四面体中均匀分布的产生一个随机点， 如此循环生成n-2 个随机点，即生成一条染色体。（ 2）染色体的适应度。目标是生成树的长度最小化，因此适应度为该染色体中的 Steiner 点和

12、正则点求得的最小生成树 长度的倒数。3）染色体的选择。利用随机遍历抽样法（ StochasticUniversal Sampling ，简记 sus ），此方法与轮盘赌选择法基本相似， 是对轮盘赌选择法的一种改进， 特点是只要进行一次轮盘旋转。 其采用均匀分布且个数等于种群规模的旋转指针， 等距离选择个体， 其中第一个指针位置由 0 ， 1/M 区间的均匀随机数决定，提供了零偏差和最小个体扩展。4）染色体的交叉。采用 2-opt 法进行交叉。需要注意的是， 染色体断开的位置必须为 3 的倍数位置， 目的是不把一个点的 x 、 y 、 z 坐标割裂开来。5）染色体的变异。随机删除染色体中的一个点

13、的坐标，重新随机选择一个四面体，在其中生成一个随机点加入染色体中。最终经过若干次的进化迭代， 得到适应度最佳的染色体， 然后把染色体中度不为 3 的 Steiner 点去掉即可。第三步的结果如图 11 所示。第四步 选择适当的满拓扑结构，构成最终解。第三步中求得的所有满拓扑结构，有些结构共用相同的原点，如图12 （a）,所以并不能同时存在于最终解中，因此要选择适当的满拓扑结构来构成最终的解。在满拓扑结构数量较小的情况下（如 10 以内的规模），可使用经典算法， 诸如分支定界法或回溯法等， 精确地求得应选择哪些拓扑结构。 但是在满拓扑结构数量较大的情况下， 解空间的大小为2n,其时间复杂度为0

14、（2n）,用经典算法将在计算时间上达到难以容忍的程度， 因此， 这一步骤依然采用遗传算法进行求解。其中，染色体的长度为满拓扑结构的个数，变量均为布尔型变量， 0 代表不选择该满拓扑结构， 1 代表选择该满拓扑结构。实例测试L 述算法在问题规模较小的情况下，如正则点数在10 个以内，可省略第一、二、四步，即直接使用遗传算法进行求解，但在问题规模较大时， 直接使用遗传算法极易使拓扑结构陷入局部最优，因此，下述实例测试中，分别直接使用遗传算法和本文上述算法进行求解并比较相应结果。正则点的最小生成树长度=4.2240 ，直接使用遗传算法求得Steiner 树长 =4.1947 ，使用本文上述算法求得Steinei 树长=4.1363如图 l3 所示，（a ）为直接使用遗传算法，仅求得了2 个Steiner点，且均为正则点个数为3的满拓扑结构；（b）为使用本文上述算法， 求得了 5 个 Steiner 点， 分别形成了正则点个数为 4 和 5 的两个满拓扑结构。正则点的最小生成树长度=6.5175 ，直接使用遗传算法求得Steiner 树长 =6.4897 ，使用本文上述算法求得Steiner 树长=6.3498如图 14 所示，（ a ）为直接使用遗传算法，仅求得了 2 个Steiner