朱彦廷

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

0 引言

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

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

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