学位论文 > 优秀研究生学位论文题录展示
基于遗传算法的QoS组播路由算法优化研究
作 者: 王军
导 师: 马范
学 校: 上海交通大学
专 业: 计算机应用技术
关键词: 遗传算法 QoS 组播路由 适应度值 早熟收敛
分类号: TP393.02
类 型: 硕士论文
年 份: 2008年
下 载: 44次
引 用: 0次
阅 读: 论文下载
内容摘要
视频广播、IPTV等应用的出现,使得传统的Internet所提供的“尽力而为”的服务已经无法满足新应用在QoS方面的要求,因此,近年来业界广泛地将研究的关注点放在了组播应用环境下如何确保用户的服务质量(QoS)这个难题上。QoS组播路由算法已经被证明是一个NPC问题,从而使得其成为组播进一步应用的症结。基于启发式算法的路由方法随着网络节点以及链路数量的增加,计算时间代价会急剧增加而且在处理多约束的条件下显得无能为力。遗传算法的诸多特点为QoS组播路由计算带来了新的动力,然而由于“早熟收敛”现象以及适应度函数设定等方面的原因造成收敛到最优解概率较低以及速度较慢的问题。针对上述传统遗传算法的不足,本文的主要研究工作如下:1.预防“早熟收敛”现象改进算法,主要是针对造成“早熟收敛”现象的“超级个体”和固定交叉、变异概率两方面原因进行改进,选择机制优化在出现“超级个体”时通过对种群进行对数化处理来提高低适应度个体被选择的几率,从而预防“超级个体”对种群进化的消极影响。自适应交叉、变异操作改进则通过侦测种群进化的情况来动态调整交叉、变异概率,从而在机制上预防了种群过早收敛。此改进算法提高了整体进化收敛到最优组播路由的概率。2.适应度函数改进方面,原适应度函数公式f(P)=(Afb+Bfd+Cfdj+Dfpl)/Efc虽明确了适应度值与四大QoS约束参数以及网络代价之间的关系,但并不能保证满足QoS约束是搜索最优组播路由的前提。改进后的适应度函数表达式f(P)=(Afb*Bfd*Cfdj*Dfpl)-Efc,不但明确了满足QoS约束是前提的地位,避免了产生不合理解的情况,更是提高了选择压,从而加快了种群进化的速度。3.初始群体生成预处理方面,通过对传统遗传算法的分析,初始群体中是否包含有符合QoS约束的组播路径个体直接影响到最优路径算法的收敛性。预处理改进算法就能够通过对初始群体进行侦测,若包含有有效路径则进入选择、交叉和变异操作,反之,则需重新进行初始群体生成操作。此改进能够有效降低收敛到最优解所需的平均代数。4.在上述三方面改进的基础上,本文提出了一种新的基于优化遗传算法的QoS组播路由算法,并从遗传算法设计基本步骤、编码表示、适应度函数设定、初始群体生成、选择算子设计、交叉算子设计、变异算子设计、遗传参数自适应优化以及终止条件设计等九个环节详细阐述了算法的实现方法。本文提出的优化算法均经过仿真验证。本文通过在预防“早熟收敛”现象改进算法、适应度函数改进以及初始群体生成预处理三方面的改进切实地提高了进化过程的动态性,促使算法能够收敛到质量更高的解,提升了算法的性能。
|
全文目录
摘要 3-5 ABSTRACT 5-9 第一章 绪论 9-16 1.1 概述 9 1.2 组播的特点 9-10 1.3 组播技术的应用 10 1.4 组播路由算法研究现状 10-13 1.5 本文的主要研究内容 13-14 1.6 本章小结 14-16 第二章 QoS 组播路由技术原理 16-21 2.1 组播路由技术概述 16-17 2.1.1 IGMP 16 2.1.2 组播路由选择方式 16-17 2.1.3 组播路由算法协议 17 2.2 QOS 路由概述 17-19 2.2.1 QOS 的定义 18 2.2.2 QOS 路由的定义 18 2.2.3 IP QOS 的基本结构 18-19 2.3 QOS 组播路由的数学模型 19-20 2.4 本章小结 20-21 第三章 遗传算法原理 21-27 3.1 遗传算法概述 21-22 3.1.1 遗传算法的发展历史 21 3.1.2 遗传算法的基本思想 21-22 3.1.3 遗传算法的特点 22 3.2 遗传算法的基本流程 22-23 3.3 遗传算法基本操作 23-25 3.4 遗传算法的收敛性分析 25-26 3.4.1 收敛的定义 25 3.4.2 遗传算法的Markov 链分析 25-26 3.5 遗传算法的种类 26 3.6 本章小结 26-27 第四章 “早熟”现象的优化算法研究 27-39 4.1 传统遗传算法中的“早熟”现象的概念 27 4.2 传统遗传算法“早熟”现象的产生原因 27-28 4.3 “早熟”现象的数学分析 28-31 4.3.1 相关定义 28 4.3.2 选择算子分析 28-29 4.3.3 交叉算子分析 29-30 4.3.4 变异阶段 30-31 4.4 预防传统遗传算法早熟收敛的策略 31-32 4.5 预防早熟收敛策略的算法 32-36 4.5.1 交叉、变异概率动态选择 32-34 4.5.2 选择机制优化算法 34-36 4.6 预防早熟收敛的算法仿真验证 36-38 4.6.1 仿真试验环境简介 36-37 4.6.2 降低“早熟”现象对整个算法的影响试验 37-38 4.7 本章小结 38-39 第五章 提高收敛速度的关键环节优化研究 39-50 5.1 适应度函数的优化设定 39-46 5.1.1 QoS 组播路由适应度函数的一般定义 39-41 5.1.2 本文提出的适应度函数 41-42 5.1.3 改进后的适应度函数公式如何设定各加权系数 42 5.1.4 仿真试验 42-46 5.1.5 结论 46 5.2 初始群体生成预处理 46-49 5.2.1 预处理算法描述 46-47 5.2.2 初始群体生成预处理仿真验证 47-49 5.3 本章小结 49-50 第六章 基于优化遗传算法的QoS 组播路由算法 50-73 6.1 遗传算法设计的基本步骤 50 6.2 编码表示 50-54 6.2.1 组播树编码的特征要求 51 6.2.2 常用的组播树编码方式 51-54 6.2.3 各种组播树编码的特点 54 6.3 适应度函数 54-58 6.3.1 本文中适应度函数的数学表示 54-56 6.3.2 适应度函数计算算法 56-58 6.3.3 算法在种群计算中的关键点 58 6.4 初始群体生成 58-61 6.4.1 现有的组播数生成方法 58 6.4.2 构成初始群体的组播树生成算法 58-61 6.4.3 初始群体生成算法 61 6.5 选择算子的设计 61-63 6.5.1 标准轮盘赌选择策略算法 62 6.5.2 选择机制优化 62-63 6.5.3 最优个体保持策略 63 6.6 交叉算子的设计 63-65 6.7 变异算子的设计 65-68 6.8 算法中遗传参数的自适应选择 68-69 6.9 算法终止条件 69 6.10 算法的具体描述 69-72 6.11 本章小结 72-73 第七章 试验与仿真 73-76 7.1 随机网络产生模型简介 73 7.2 本文仿真试验简介 73-74 7.3 仿真试验研究与结果分析 74-75 7.3.1 仿真试验环境简介 74 7.3.2 仿真测试结果分析 74-75 7.4 本章小结 75-76 结束语 76-78 参考文献 78-81 致谢 81-82 攻读硕士学位期间录用的论文 82-84
|
相似论文
- 天然气脱酸性气体过程中物性研究及数据处理,TE644
- 压气机优化平台建立与跨音速压气机气动优化设计,TH45
- 基于遗传算法的模糊层次综合评判在高职教学评价中的应用,G712
- 部队人员网上训练与考核系统的开发,TP311.52
- 基于并行算法的模糊综合评价模型的设计与应用,TP18
- 基于神经网络的牡蛎呈味肽制备及呈味特性研究,TS254.4
- 基于遗传算法的中短波磁天线的设计及实现,TN820
- 基于遗传算法的柑橘图像分割,TP391.41
- 基于混合自适应遗传算法的动态网格调度问题研究,TP393.09
- 基于遗传—牛顿算法的公交优化调度,TP18
- 基于遗传算法优化的BP网络对生物柴油制备工艺的优化,TE667
- 基于云理论和蜜蜂进化型遗传算法的纹理合成研究,TP391.41
- 基于遗传算法和粗糙集的聚类算法研究,TP18
- 基于遗传算法的淠史杭灌区渠系配水优化编组模型的研究,S274
- 遗传算法在物流仓储优化中的应用研究,F259.2
- 基于遗传算法的矿山资源优化调度模型的研究,O224
- 磁流变阻尼器的力学特性及其在火炮反后坐中的应用研究,TB535.1
- 模糊预测函数控制改进算法的研究及应用,TP273
- 基于模拟的注塑模浇注系统及成型工艺参数优化研究,TQ320.662
- 基于重型机床大型零件铣削加工性能及参数优化的研究,TG54
- 基于Click的模块化软件路由器的包调度算法研究,TP393.05
中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机的应用 > 计算机网络 > 一般性问题 > 计算机网络结构与设计
© 2012 www.xueweilunwen.com
|