最小生成树问题是一个经典的网络优化问题，而实际应用中往往要对生成树加上某种限制，形成了一类有约束的最小生成树问题，如在有n个顶点的图G中求至少带有L片叶子的最小生成树，即叶约束最小生成树问题。解决该类问题一般采用启发式算法，如人工蚁群算法、遗传算法等。由于遗传算法是一种全局优化搜索算法，对所求问题相关领域知识没有直接的依赖性，表现出很强的鲁棒性，所以在网络优化界里日益受到重视，尤其在解决网络优化领域中的最小生成树问题时和问题相关知识及领域搜索方法相结合显示出了巨大的潜力。有效地解决网络优化领域中的最小生成树问题在现实生活中具有广泛的应用，如设施的选址、电路和网络的设计等方面。因此，对这类问题及其求解算法的研究具有很大的理论及现实意义。　　 通过对遗传算法存在的问题和叶约束最小生成树(Leaf-constrainedMinimumSpanningTreeProblem，LCMST)问题的分析，本文将遗传算法与领域搜索方法相结合，并将之用于对该问题的求解中。对算法方面的研究主要有：1)通过对生成树问题的不同编码方式测试对比分析发现，采用子集编码可以获得更好的性能；2)针对遗传算法本身存在局部搜索能力差，结合问题本身，对子集编码遗传算法采用了一种2-opt的算子进行领域局部搜索；3)从解的精度和收敛速度考虑，在变异操作之后设计了一种更快速的重新分配叶子归属的算法。　　 同时通过研究发现无约束p-中位问题(UncapacitatedP-medianProblem，UPMP)和叶约束最小生成树问题有很大的相似性，所以把求解叶约束最小生成树问题中的改进型子集编码遗传算法同样应用到求解无约束p-中位问题中。　　 理论分析和仿真实验结果表明，本文提出的改进型子集编码遗传算法对所选取的测试用例进行求解中，算法能得到问题的最优解或接近最优解，同时，收敛速度有了明显的提高。