邓全才1  王利民1  郝桂珍2

（1 河北建筑工程学院数理系， 张家口075000； 2 河北建筑工程学院能源与环境工程学院， 张家口075000）

        摘要  针对单亲遗传算法中随机生成树的产生问题进行了研究。通过试验发现从L条边中随机取其中的n-1条边，然后判断这n-1条边是否能构成一棵树，但是当顶点数达到29的时候，在10 000次的循环中无法得到1颗随机生成树。以阳原县管网布置为例进行研究，在原有算法的基础上加入了分治式算法的思想，结合构建的适应度函数，将图形分为6个分区，且最大分区中的顶点数不超过20个。然后，在每个分区中单独形成随机树，在分区之间形成分区连接，将分区间的随机树和各个分区独立形成的随机树进行组合得到随机生成树。结果表明，该方法在不到1 min的时间内随机生成了60颗随机生成树。因此，分治式单亲遗传算法可以有效地解决产生随机生成树概率极低的问题。

        关键词   单亲遗传算法  适应度函数  管网  随机生成树   初始化  分治式