图的Steiner最小树问题的算法与应用研究

发布时间：2017-10-17 06:27

  本文关键词：图的Steiner最小树问题的算法与应用研究

  更多相关文章： Steiner树 遗传算法 启发式算法 随机网络 组播

【摘要】：图的Steiner最小树问题是经典的组合优化问题,在通信网络和电路设计等领域有广泛应用。该问题是一个NP难题,虽然有一些精确算法,但是随着网络规模的增大,这些算法的运行时间呈指数增长。为了能够在多项式时间内得到最优解或者近似最优解,寻找有效的启发式算法就显得尤为重要。本文对遗传算法和传统的启发式算法进行了改进,主要工作如下:1.针对基本遗传算法采用自适应规则,引入模拟退火思想,提出了一种解决Steiner最小树问题的混合遗传算法并进行仿真实验。实验结果表明:与基本遗传算法相比,改进的混合遗传算法能够加快收敛速度,减少迭代次数,使得到的解更稳定。2.分析已有典型启发式算法,提出了一种基于加权节点的Steiner树启发式算法。该算法根据正则点对间的最短路径、节点的度数、与正则点连接的次数等计算出节点的权值,然后根据权值对最短路径的费用进行修正,通过修正费用最短路径将正则点添加到多播树中,从而实现更多链路的共享,降低整棵树的费用。3.为了模拟真实的通信网络来测试算法的性能,本文对Waxman算法进行改进,设计了一种逼近现实网络特性的随机网络生成算法。用该算法生成不同规模的仿真网络,然后用启发式算法对仿真网络进行求解,结果表明基于加权节点的启发式算法是一个性能较好的算法。
【关键词】：Steiner树 遗传算法 启发式算法 随机网络 组播
【学位授予单位】：南京邮电大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要4-5
• Abstract5-8
• 第一章 绪论8-12
• 1.1 研究背景及意义8
• 1.2 课题研究现状综述8-9
• 1.3 本文主要内容及章节安排9-12
• 1.3.1 主要创新10
• 1.3.2 章节安排10-12
• 第二章 Steiner最小树问题及其相关算法12-20
• 2.1 Steiner最小树问题12-13
• 2.2 问题定义与分析13-15
• 2.2.1 图的Steiner树的定义13-14
• 2.2.2 数学性质分析14-15
• 2.2.3 多项式解法15
• 2.3 智能优化算法简介15-17
• 2.4 Steiner树启发式算法介绍17-19
• 2.5 本章小结19-20
• 第三章 Steiner最小树问题的混合遗传算法20-30
• 3.1 遗传算法原理20-24
• 3.1.1 遗传算法基本思想20
• 3.1.2 遗传算法基本操作20-22
• 3.1.3 遗传算法基本步骤22-23
• 3.1.4 遗传算法存在的问题23-24
• 3.2 模拟退火与Metropolis准则24
• 3.3 混合遗传算法描述24-27
• 3.3.1 编码方法和群体初始化24-25
• 3.3.2 适应度计算和选择种群25
• 3.3.3 交叉率和变异率的确定25-26
• 3.3.4 对最优个体进行模拟退火操作26-27
• 3.3.5 算法步骤27
• 3.4 实例测试27-29
• 3.5 本章小结29-30
• 第四章 基于加权节点的Steiner树启发式算法30-37
• 4.1 基于关键节点的启发式算法30-31
• 4.2 基于加权节点的启发式算法31-34
• 4.2.1 算法思想31
• 4.2.2 变量设置及公式31-32
• 4.2.3 算法步骤描述32-33
• 4.2.4 算法的正确性和复杂度33-34
• 4.3 实例分析34-36
• 4.4 本章小结36-37
• 第五章 网络仿真与实验数据37-46
• 5.1 随机网络仿真模型37-41
• 5.1.1 Waxman算法37-38
• 5.1.2 Doar算法38
• 5.1.3 随机网络的产生38-41
• 5.2 仿真结果41-43
• 5.2.1 参数设置41
• 5.2.2 仿真结果分析41-43
• 5.3 Steiner最小树问题的延伸43-45
• 5.3.1 静态QoS约束的组播路由问题44
• 5.3.2 动态无约束组播路由问题44-45
• 5.3.3 动态QoS约束的组播路由问题45
• 5.4 本章小结45-46
• 第六章 总结与展望46-48
• 参考文献48-51
• 附录1 程序清单51-52
• 附录2 攻读硕士学位期间撰写的论文52-53
• 致谢53

【参考文献】

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

1 贺素良,喻寿益;基于动态补偿参数和改进的自适应遗传算法的系统辨识方法[J];计算机工程与应用;2003年19期

，

本文编号：1047305