计算机中遗传算法中树构造的分析

中国医科大学附属盛京医院医务部 高 兴

计算机中遗传算法中树构造的分析

中国医科大学附属盛京医院医务部 高 兴

提出了一种解决Steiner最小树问题的自适应遗传算法，将Steiner最小树问题转化成一个组合优化问题，并对部分初始种群的构造给出了一种试探选择方法。通过对通讯网络Steiner最小树问题的实例仿真分析，表明算法能有效地跳出局部极小值并快速地收敛于全局最优值。将其推广到考虑建站费用的极小树问题上，取得了很好的近似解。

通讯网络 Steiner最小树 最小生成树 遗传算法

一、网络有线通讯问题

两个通讯站间通讯线路的费用与线路的长度成正比，通过引入若干个“虚设站”并构造一个新的Steiner树就可以降低由一组原始站点生成的传统的极小生成树的线路长度。用这种方法可以降低线路长度多达13。4%。假定对一包含9个通讯站点的局部网络进行布线，目的是使其网络连通且总线路最短。这9个站点的直角坐标分别为：

a（0，15），b（5，20），c（16，24），d（20，20），e（33，25），f（23，11），g（35，7），h（25，0），i（10，3）。限定两通讯站间的线路长度必须为两点间的直角折线距离，即d=︱x2-x1︱+︱y2-y1︱，且一切新增虚设点必须位于格子节点上（即坐标为整数）。通过构造这个网络的Steiner最小树，使网络布线达到全局最优化。

二、问题的分析与解决步骤

上述问题允许通讯线在非站点处连接，因而不同于最小生成树问题。最小生成树不允许非站点处连接，而此处取消了限制，允许在站点以外的点（即“虚设站”或Steiner点）连接，可使线路变短，但却增加了问题的复杂度。

本文将这个问题分3步解决：①确定Steiner点的个数；②确定Steiner点的位置；③建立使线路最短的生成树。

三、模型建立与求解

1. 遗传算法求解

前文已将Steiner最小树问题转化为一个组合优化问题，即在已知所有可能的Steiner点中，确定出最优的组合，使其与原始站点构成Steiner最小树。因搜索空间的不规则性，无法确定Steiner点的数目和位置，我们将使用遗传算法来解决这个问题。详细步骤如下：

（1）编码

采用自然数编码。对一有n个通讯站的通讯网络，将所有可能的Steiner点进行编号。通过上述分析我们已经解出所有可能的Steiner点（共m个）的位置，让每一个Steiner点都唯一对应一个1～m之间的自然数；用矩阵pop来表示所有的染色体，popsize表示矩阵pop的行数，n表示矩阵pop的列数，矩阵的每一行代表一个染色体。而每一染色体所示信息如下：设p=[p（1），p（2），…，p（n）]为矩阵pop的任一行。p（i）（i=1，2，…，n-2）：x（i）为0～m之间的自然数，如果p（i）=0则表示不加Steiner点，如果p（i）≠0则表示加入Steiner点。p n-1：表示由[p（1），p（2），…，p（n-2）]所确定的一组Steiner点与原来的n个通讯站点所确定的最小生成树线路长度。p n：表示适应度函数值。

（2）初始种群的选取

本文采用一种简单有效的快速算法来产生部分的初始解，这些值能够很好的逼近最优解。算法的中心思想是：每次迭代都随机加入一个点，并使得到的最小生成树费用有所减少，直到已加入n-2个点或加入任何一个剩余的可能的点都不可能有所减少为止，谓之试探选择方法。其步骤描述如下：

①求给定的n个通讯站点的最小生成树T，记录其线路长度为C；

②对可能的Steiner点集V p，分别计算每个候选点作为Steiner点加入之后所减少的费用，记为vf；

③随机取一个vf>0的候选点，把它加入到树T中，更新此树及线路长度；同时从点集V p中去掉该点；

④重复（ii）和（iii）直到已有n-2个点或所有的vf都小于等于零（即任何剩余的候选点加入都不能减少线路长度）。

将所得解作为部分初始种群，同时随机产生另外一部分初始种群，这样既保证了初始种群的质量，又保证了其多样性。

（3）选择操作

本文结合轮盘选赌和保留最优种群的方法，采用赌轮法进行选择，将最优保存策略嵌入其中，以加强对下一代中最好个体的保护并克服样本的随机误差。同时结合最优保存策略选择，取选择率pr，将种群中的比较好的一些个体加入到下一代。

（4）变异操作

本文采用单点变异操作。定义参数pm作为遗传系统中的变异概率，这个概率表明，总体中有期望值为（pm×popsize）个染色体用来进行变异操作。因此，如果pm过小，就不易产生新的个体结构；如果pm取值过大，那么遗传算法就变成了纯粹的随机搜索算法。

2. 结果

对于原始给定的9个通讯站，经过多次试验，遗传算法迭代不到第10次就可以收敛到最优解，并且有良好的稳定性，当然不同的运算，就有不同的随机数字产生，这里给出5种不同的总长都为94的最优解，这5组解分别为：（16，20）、（23，3）、（33，11）；（16，20）、（23，3）、（23，7）、（23，20）；（16，20）、（23，20）、（25，3）、（25，7）；（5，15）、（10，15）、（20，15）、（20，24）、（25，7）；（16，20）、（25，3）、（25，7）、（25，11）、（25，20）。所要添加的虚拟点为4个，分别为（16，20）、（23，3）、（23，7）及（23，20）。

算法评价遗传算法从多点开始并行操作，在解空间进行高效启发式搜索，克服了从单点出发的弊端及搜索的盲目性，从而使寻优速度更快，避免了过早陷入局部最优解。而同类方法中，单纯形法受初值和计算步长的影响较大，易收敛于局部最优解；传统的随机寻优技术效率较低。

应用模拟退火法得到的最优解一样，将遗传算法应用于本文所述的通讯网络优化布线问题可以较快的求得最优解，迭代不到10次就达到最优解，计算机运算时间仅需几秒；而且算法稳定性高，连续运行此程序50次，皆收敛到相同的最优解，收敛率达到100%。

本文采用的是自适应遗传算法，在数据规模较小的情况下，尚体现不出其优越性。现随机产生20个初始站点=[96 6；24 36；61 82；49 1；90 14；77 21；46 20；2 61；83 28；45 20；62 2；80 75；93 45；74 94；18 47；4142；94 85；92 53；42 21；90 68]，运行遗传算法主程序，适应函数值上升得较快，这说明遗传算法收敛得较快；当平均适应度函数值接近最大适应度函数值时，适应函数值也呈上升趋势，说明当种群单一，遗传算法陷入局部最优解时，遗传算法就会加快新个体的产生，避免算法的早熟收敛。

[1] 蒲俊，吉家锋，伊良忠.MA TL AB[6]0数学手册[M].上海：浦东电子出版社，2002. 6

[2] 许桂水，曾山.基于非线性规划问题GA的Matlab程序[J].武汉工业学院学报，2002，2(3)：35-37

book=92,ebook=215