最小生成树问题是组合优化中的经典问题,并在通信网络设计和最短路连接等方面有广泛的应用。在实际应用中,生成树顶点的度往往需要满足某些条件。比如通信网络设计中为了防止节点故障带来的脆弱性,对节点的度要有一定的限制。这种顶点带有度约束的最小生成树问题称为度约束最小生成树问题。遗传算法作为一种启发式搜索优化算法,它为求解度约束最小生成树问题提供了一个有效的途径。本文通过结合遗传算法的思想,针对度约束最小生成树问题的特点,提出了采用单亲遗传算法求解这一问题,并设计了新的编码方案和相应的遗传操作。本文首先对度约束最小生成树问题的研究背景作了介绍。其次,介绍了一些求解度约束最小生成树问题的常用算法。最后,提出了在完全图下求解度约束最小生成树问题的单亲遗传算法。本文通过对prufer编码的改进提出了新的编码方式和解码方式,这样的改进使得整个解码过程是静态的,提高了算法的运行效率,并且通过对新的编码的分析可直观得出树的结构。设计了新的变异算子,新算子保持了种群多样性的同时,又可使后代保留了父代的优良品质。设计了两种局部寻优算子,改善了优化质量,同时又提高了搜索效率。