用单亲遗传算法求解度约束最小生成树问题

作     者：秦轶 

作者单位：内蒙古大学 

学位级别：硕士

导师姓名：行飞

授予年度：2013年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：度约束最小生成树 单亲遗传算法 Prufer编码 局部寻优 

摘      要：最小生成树问题是一类非常重要的组合优化问题,在现实中被广泛应用于各个领域,如通信网设计、道路系统设计、管道铺设等。如果在最小生成树问题中对每个顶点加以度约束即限制连接到顶点的边的数量,这时问题就成为度约束最小生成树问题。度约束最小生成树问题有很重要的现实意义,比如设计通信网时,如果不考虑度约束,某些重要节点一旦出现故障可能会导致整个网络瘫痪,因此限定连接到节点的边的数量是很有必要的。度约束最小生成树问题的求解方法有启发式算法、遗传算法等。 本文讨论完全图下的度约束最小生成树问题,使用单亲遗传算法求解。该算法首先利用Prufer数对生成树进行编码,保证产生的初始种群不含有任何不可行解;设计了三种变异操作,并分析三种变异操作对图的影响而采用按比例执行变异操作,保证产生优秀的可行的子代染色体,拓展搜索空间;构造了两种局部寻优算子,增强了算法在较小区域内搜寻更加适应环境的个体的能力,使得最终能够输出更优秀的个体。