用遗传算法求最小生成树

朱彦廷

(广西现代职业技术学院计算机系，广西河池547000)

0 引言

生成树是图论的一个重要概念，许多工程问题，如通讯、交通、供电和给排水等网络设计，通常都可以转化为求最小生成树问题.不同的最小生成树代表不同的方案，因为权值有时与几个因素(如路途远近、路况好坏，拆迁难易等)都有关，很难定得十分合理，几棵最小生成树，往往有一棵是最好的方案，有时某棵次小生成树甚至是一个更好的方案.因此，最好能找出几棵最小或次小生成树，然后再加斟酌，决策将更为科学.

使用经典算法，如Kruskal、Prim、Sollin算法，一般只能找出一棵最小生成树.遗传算法是一种模拟生物进化过程的算法，对求解组合优化问题很是有效，寻找最小生成树其实也是组合优化问题，可以考虑使用.

设一无向图共有n个顶点，m条边.用遗传算法求最小树，编码方法几乎都是边编码，对边进行编号，一个个体是一个二进制代码，长为m，代表图的一个子图，若某位为1，表示它所对应的边是子图的边;若为0，表示它所对应的边不是子图的边，因为一棵过n个项点的树有n－1条边，且是连通的，因而应使个体只有n－1位为1(否则肯定不代表生成树)，然后对它代表的子图进行遍历，若能访问到n个顶点，则子图是连通的，是一棵生成树.交叉、变异算子极可能破坏个体的可行性，即产生的新个体不是只有n－1位为1，不能直接使用，要进行变通，如文献［4］改成换位算子、逆转算子，相当于舍弃了交叉算子，修改了变异算子.在此，采用节点编码，对节点进行编号.

1 基本原理

根据图论中的Cayley定理，一个有n个顶点的完全图有nn－2棵不同的生成树，而由乘法原理，n－2个1～n之间的数有nn－2个不同的排列，两者可以是一一对应关系.这个排列通常称为Prufer数.例如，图1(a)是一个完全图，(b)是该图的一棵生成树，对应的排列是22.

图1 无向图和生成树

一棵生成树对应的排列可以这样构造:规定编号为n的节点为根节点，找到树上标号最小的叶子节点i，则它的双亲节点j是排列的第一个数，删除节点i及边(i，j).重复上述过程，直到只剩下一条边，得到一个n－2个数字的排列.

反过来，一个排列对应的生成树可以这样构造:找到最小的不在排列中而且未使用的节点i，设排列的第一个数是j，则(i，j)是树的一条边，从排列中删去j，并把i标记为已使用.重复上述过程，直到排列为空，这时还未使用的2个节点一个是n，另一个设为k，再加上边(k，n)，得到生成树的n－1条边.

2 算法设计

2.1 编码采用十进制编码，一个个体有n－2位，每位取值范围是1～n，代表完全图的一棵生成树.

2.2 适应度函数生成树各边的权值的和越小，适应度应该越大.设图的各边的权值分别为W1，W2，…，Wm.由个体得到完全图的生成树，如果它的各边在图中都存在，是图的生成树，适应度为

其中，F0=(n－1)max(W1，W2，…，Wm)，是完全图的生成树的边的集合，x是大于0的常数;如果有一条边不存在，不是图的生成树，适应度最小，为x.

2.3 遗传算子

2.3.1 选择算子采用赌轮选择(依据如表1，注意个体适应度的最小值是100(不是生成树)，最大值是139(最小生成树)，范围很小)，用个体的适应度与群体中个体的适应度的总和之比作为其被选择的概率，个体的适应度越高，被选择的概率将越大.因为选择是基于概率做出的，适应度低的个体也可能被选择，这有助于维持群体多样性.如果适应度函数中x等于0，最初很可能各个个体的适应度都为0(对于本问题，找到一棵生成树很不容易)，从而适应度的总和为0，无法计算个体被选择的概率，因此x应大于0，还应使适应度最大值、最小值的比值不致太大，以免出现早熟现象(在算法运行的初期，如果产生个别适应度非常高的个体，它们将很快充斥群体，使进化难以继续，陷于局部最优).

表1 是否采用赌轮选择性能对比

2.3.2 交叉算子采用单点交叉，从群体中随机选择2个个体，随机产生交叉位，交换它们该位后面的串，得到2个新个体.例如对于个体111111和222222，设产生的交叉位为3，则交换后产生的新个体分别为111222、222111.

2.3.3 变异算子先采用基本位变异，对交叉后的个体，随机产生变异位，变换该位，得到新个体.例如对于个体111111，设产生的变异位为3，随机产生的变换位为5，则变异后产生的新个体为115111.然后进行比较(依据如表2)，如果新个体不如原个体，放弃变异，即保留好的变异，舍弃坏的变异，这样如果变异产生的新个体不如原个体，不会有什么不利影响.生物进化到现在这个程度，用了几十亿年，因而恐怕不能说是十分完美的，遗传算法不应单纯的模仿进化，也应有所选择.

表2 是否进行比较性能对比

2.3.4 整理算子这是本算法特有的算子.算法追求的是找出尽可能多的最小、次小生成树.本问题比较特殊，好的父代个体产生好的子代个体的可能性小些，如果没有本算子，最后得到的个体适应度几乎都很低，没有什么价值.为了保存较好的个体(如果是最小、次小生成树，非常珍贵)，将新群体、原群体混合，选出最好的且不重复(对于本问题，较好的个体较少，如果不加这个限制，个别较好的个体可能充斥群体)的个体(约占群体中个体数目的80%)，这将最大限度地保存较好的个体，再随机产生少量个体(约占群体中个体数目的20%，这将增大搜索空间.依据如表3)，合起来组成下代群体.

表3 是否随机产生少量个体性能对比

这样如果交叉产生的新个体不及原个体，也没有什么不利影响.因此使用本算法，可以放心交叉、变异，无须担心交叉、变异概率设置得是否合适(这2个参数设置得过大、过小都将影响算法的性能［4］，最好不固定，随着算法的运行而变化［5］(但实现将更复杂)).

2.4 算法流程

(1)设置群体大小M、最大进化代数T，适应度函数中的常数x;

(2)随机生成M个个体作初始群体，计算各个个体的适应度;

(3)如果进化代数t=T，转到(9);(4)选择;

(5)交叉; (6)变异;

(7)整理，得到下代群体; (8)t=t+1，转到(3); (9)输出最终群体.

3 实例

要建立一给水网络，有10个节点，23条可能的线路，如图1所示(括号中为线路长度)，求一组线路总长度最短或次短的方案.采用经典算法，一般只能得到一棵权为60的最小生成树.应用本算法，取M=10，T=1000，x=100，运行20次，最终群体中个体的平均适应度为136.6，最高为138.4，最低为133.3，可见算法虽然带有随机性，结果不确定，但还是很有效的，其中第19次结果如表1所示(用c语言实现时，为了方便，将节点编号1～10依次改为0～9)，获得8棵最小、次小生成树(最后2个个体是随机产生的，不代表生成树)，其中1 号个体对应的边是:(1，5)，(0，1)，(2，0)，(4，7)，(3，4)，(2，3)，(6，2)，(8，6) ，(9，8)，即第 5、1、2、15、11、7、10、19、23条边，可以结合其它因素确定具体选择哪种方案.

表4 最终群体

图2 建立给水网络资料

为了取得更好的效果，可以先用经典算法求出一棵最小生成树，从而得到个体适应度的最大值，如果群体中有一个个体的适应度达到(或接近)这个值，标志着进化已经达到较高的阶段，可以考虑停止进化.

4 结束语

和边编码比较起来，节点编码编码较短(如果边数很多，应采用这种方式，以免编码过长)，产生的个体代表完全图的生成树，只要各边在(实际的)图中都存在就肯定是生成树，无须另行检验(过程比较繁琐)，交叉、变异算子基本都可以直接使用，但把个体转换成完全图的生成树(实际是找出它的各条边)实现不太容易.

［1］孙小军，刘三阳，王志强.一种求解最小生成树问题的算法［J］.计算机工程，2011，37(23):241－243.

［2］朱晓虹.量子遗传算法求解度约束最小生成树［J］.巢湖学院学报，2010，42(6):38－42.

［3］何忠华，孟祥瑞.基于节点编码的最小生成树算法［J］.黑龙江科技信息，2008(34):90.

［4］刘志成，钱建刚.基于改进遗传算法的最小生成树算法［J］.计算机工程与设计，2004，25(9):1620－1622.

［5］陈曦，林涛，唐贤瑛.遗传算法的参数设计与性能研究［J］.计算机工程与设计，2004，25(8):1309－1310.