基于遗传算法的度约束最小生成树问题的研究

发布时间：2017-06-28 21:05

  本文关键词：基于遗传算法的度约束最小生成树问题的研究，由笔耕文化传播整理发布。

【摘要】：度约束最小生成树(Degree Constrained Minimum Spanning Tree, DCMST)问题是网络优化中一个常见的问题。近年来,度约束最小生成树在计算机网络、通信网络和运输网络设计等领域得到了广泛的应用,许多网络设计问题都和度约束最小生成树问题有关。比如,在构建通讯网络时,网络布局就是寻找连通图的生成树,建网费用最少就是寻找最小生成树,每个结点负载不能太多就是对结点的度约束。然而,度约束的最小生成树的求解被证明是一个NP难问题,因此对大规模DCMST问题,目前还没有有效的算法。本文介绍了求解DCMST问题的古典算法、启发式算法以及现代优化算法。设计了一种在非完全图下求解度约束最小生成树问题的遗传算法,为此构造了新的编码方法、适应度函数、初始化方法、遗传算子。为了加快优化进度,设计了寻优算子,取得了较好的效果。
【关键词】：度约束 最小生成树 DCMST 非完全图 遗传算法
【学位授予单位】：内蒙古大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5;TP18
【目录】：

• 摘要4-5
• Abstract5-9
• 第一章 绪论9-12
• 1.1 度约束最小生成树问题简介9-10
• 1.1.1 度约束最小生成树的提出背景及研究意义9-10
• 1.1.2 度约束最小生成树的研究现状10
• 1.2 本文的主要内容及结构10-11
• 1.3 本文创新工作11-12
• 第二章 DCMST问题综述12-20
• 2.1 基本概念及有关结论12-14
• 2.2 基本符号说明14-15
• 2.3 DCMST问题的数学模型15
• 2.4 求解DCMST算法综述15-20
• 2.4.1 求解DCMST问题的精确算法16
• 2.4.2 求解DCMST问题的启发式算法16-18
• 2.4.3 求解DCMST问题的现代优化算法18-20
• 第三章 求解度约束最小生成树的遗传算法20-49
• 3.1 求解DCMST问题的递归算法20-23
• 3.1.1 给出连通图全部生成树的方法简介20
• 3.1.2 度约束最小生成树的递归算法20-23
• 3.2 求解DCMST问题的新快速算法QDC23-27
• 3.2.1 定义边的可用度值23-24
• 3.2.2 修改边的可用度值的DET算法24
• 3.2.3 求解度约束生成树的快速算法QDC24-25
• 3.2.4 快速算法QDC有时会找不到生成树25-27
• 3.3 求解DCMST问题算法的讨论27-32
• 3.3.1 d-prim算法和d-kruska算法的进一步讨论27-29
• 3.3.2 采用Prufer编码方式遗传算法的进一步讨论29-30
• 3.3.3 构造新算法的基本思路30-32
• 3.4 求解DCMST问题的遗传算法流程32-33
• 3.5 编码和解码33-36
• 3.6 适应度函数36-37
• 3.7 初始化种群37-38
• 3.8 选择算子38-39
• 3.9 遗传算子39-46
• 3.9.1 交叉算子39-44
• 3.9.2 变异算子44-46
• 3.10 寻优算子46-48
• 3.11 算法终止条件48-49
• 第四章 结论49-50
• 参考文献50-52
• 致谢52

【参考文献】

中国期刊全文数据库 前10条

1 朱晓虹;;量子遗传算法求解度约束最小生成树[J];巢湖学院学报;2010年06期

2 董军,关凤岩,吕宗宝;基于遗传算法度约束的最小生成树问题的研究[J];淮北煤炭师范学院学报(自然科学版);2005年01期

3 赵玲;刘三阳;;基于蚂蚁搜索度约束最小生成树的改进算法[J];计算机仿真;2006年10期

4 熊小华;宁爱兵;马良;;基于降阶的最小生成树快速算法[J];计算机应用研究;2010年06期

5 胡茂林,蔺勇;全部生成树的组合生成法[J];陕西科技大学学报;2004年01期

6 马良,蒋馥;度限制最小树的蚂蚁算法[J];系统工程学报;1999年03期

7 宋海洲;;求解度约束最小生成树的快速近似算法[J];系统工程学报;2006年03期

8 王励成,孙麟平;求解度限制最小生成树问题的启发式遗传搜索算法[J];系统工程理论与实践;2003年05期

9 宋海洲;求解度约束最小生成树的单亲遗传算法[J];系统工程理论与实践;2005年04期

10 唐立军;罗日成;肖红光;邓敏;粟娟;;基于改进Wang-代数生成连通图全部树的方法研究[J];湘潭大学自然科学学报;2005年04期

中国硕士学位论文全文数据库 前4条

1 韩丽霞;解两类组合优化问题的遗传算法[D];西安电子科技大学;2005年

2 焦森林;度约束最小生成树算法[D];西安电子科技大学;2008年

3 尉春杰;度约束最小生成树WCJ遗传算法[D];东北大学;2008年

4 郭仁杰;基于单亲遗传算法的度约束最小生成树问题研究[D];内蒙古大学;2014年

  本文关键词：基于遗传算法的度约束最小生成树问题的研究，由笔耕文化传播整理发布。

，

本文编号：495250