基于遗传算法的直径限制最小生成树问题的研究

发布时间：2017-10-28 04:13

  本文关键词：基于遗传算法的直径限制最小生成树问题的研究

  更多相关文章： 直径限制 非完全图 最小生成树 BDMST 树图

【摘要】：最小生成树是经典的组合优化问题,在实际的应用中,由于人们对传输速度、信号质量以及维修的简易性等方面的要求,对最小生成树的直径需要加一定的限制,于是得到一类基于遗传算法的直径限制的最小生成树问题。即在给定赋权无向连通图以及一个正整数D的前提下,在图的所有的生成树中,寻找一个满足直径限制且权值最小的生成树,并且不能包括超过直径限制D的路径。一般来说,当直径限制在[4,n-1)时,直径限制最小生成树问题是一个NP-Hard问题。对于此类问题,当规模比较大时,大多是采用启发式算法或遗传算法等现代优化方法求解,且基本上是以完全连通图为前提。针对非完全连通图,本文提出求解直径限制最小生成树的新的遗传算法。数值试验验证了算法的有效性。
【关键词】：直径限制 非完全图 最小生成树 BDMST 树图
【学位授予单位】：内蒙古大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5;TP18
【目录】：

• 摘要4-5
• ABSTRACT5-9
• 第一章 绪论9-12
• 1.1 引言9
• 1.2 BDMST的研究意义9-10
• 1.3 BDMST问题的研究现状10-11
• 1.4 本文的主要工作11-12
• 1.4.1 本文的主要结构和内容11
• 1.4.2 本文的创新工作11-12
• 第二章 BDMST问题的概述12-27
• 2.1 图的相关概念12-16
• 2.2 基本符号说明16-17
• 2.3 MST问题简介17
• 2.4 MST的数学模型17-18
• 2.5 MST的算法介绍18-20
• 2.6 BDMST问题描述20
• 2.7 BDMST的数学模型20-21
• 2.8 求解BDMST问题已有算法的综述21-27
• 2.8.1 求解BDMST问题的启发式算法22-25
• 2.8.2 使用序列编码的遗传算法求解BDMST问题25-27
• 第三章 用遗传算法求解BDMST问题27-62
• 3.1 求解BDMST问题的递归算法27-30
• 3.1.1 给出连通图全部生成树的方法简介27-28
• 3.1.2 直径限制最小生成树的递归算法28-30
• 3.2 求解BDMST问题算法的讨论30-38
• 3.2.1 OTTC算法、RGH算法的进一步讨论31-34
• 3.2.2 采用序列编码方式遗传算法的进一步讨论34-35
• 3.2.3 构造新算法的基本思路35-38
• 3.3 编码、解码38-42
• 3.4 适应度函数42-45
• 3.4.1 权矩阵的适应度函数42-44
• 3.4.2 边权向量的适应度函数44-45
• 3.5 初始化种群45-49
• 3.5.1 从中心点出发的初始化方法45-48
• 3.5.2 从最小生成树出发的初始化方法48-49
• 3.6 选择算子49-50
• 3.7 遗传算子50-59
• 3.7.1 交叉算子50-57
• 3.7.2 变异算子57-58
• 3.7.3 遗传算子使用策略58-59
• 3.8 局部寻优算子59-60
• 3.8.1 寻优算子a59
• 3.8.2 寻优算子b59-60
• 3.9 算法终止条件60-61
• 3.10 算法流程图61-62
• 第四章 算法验证62-68
• 4.1 实验数据的选取62-63
• 4.2 实验结果63-68
• 第五章 结论68-69
• 参考文献69-71
• 致谢71

【参考文献】

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

1 王栋,张文彬;用遗传算法求解dc_MST问题[J];哈尔滨理工大学学报;2001年05期

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

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

4 赵青;杨倩;;遗传算法三种编码策略的比较研究[J];重庆文理学院学报(自然科学版);2008年02期

5 赵礼峰;王小龙;;图的Steiner最小树问题的混合遗传算法[J];计算机技术与发展;2014年10期

6 阿不力米提·伊明;;树图及其顶点数的计算[J];新疆师范大学学报(自然科学版);2007年02期

，

本文编号：1106599