基于图染色的频率分配问题的研究

发布时间：2017-10-30 01:32

  本文关键词：基于图染色的频率分配问题的研究

  更多相关文章： 频率分配 图染色算法 禁忌搜索算法 双领域交替搜索

【摘要】：频率分配问题是一种完全多项式非确定性问题,属于多目标组合最优化问题。通常,频率分配的算法包括确定性算法、启发式算法、计算智能方法等。确定性算法每步可以得到确定的结果,但运行时间不能确定;启发式算法通常可以在合理的时间内解出答案,但不能保证每次的效率;计算智能方法具有自学习、自组织、自适应的特征和简单、通用、鲁棒性强、适于并行化处理的优点。本文研究的图染色算法就是计算智能方法的一种。针对大多数频率分配算法在收敛性、均衡性等方面存在的不足,结合图论图染色的特性,本文主要研究了图顶点染色算法和广义图染色算法在频率分配问题上的应用。论文围绕频率分配的关键技术,从以下几个方面展开了研究:(1)针对传统频率分配算法收敛性差、时间复杂度高、局部搜索能力不强等缺点,提出了一种基于图顶点染色的混合优化算法。该算法首先通过遗传算法产生后代解对问题进行初始化,然后根据图节点度的大小,将图中顶点进行排序染色,在相同的空间复杂度的情况下降低了编码执行的随机性,提高了整个系统的公平性;同时,利用禁忌搜索算法对搜索空间进行双领域交替搜索,减少算法陷入局部最优而产生的迂回,大大提高了算法的收敛速度。(2)针对频率分配问题中产生的邻频干扰,提出了一种新的基于广义图染色(T-Colorings)的优化算法。该算法以图顶点染色的混合优化算法为基础,把网络中的每个节点视为是独立、同步运行的,通过分布式并行执行,有效地提高了算法运行速度。在网络拓扑发生变化时,广义图染色优化算法只需在对比原来信息和现在信息之后,对局部做出少量修改补偿来完成新的频谱分配,而不需要重新生成分配方案,显著降低了系统开销。(3)本文通过图染色基准问题在Microsoft Visual Studio.NET 2013平台上进行测试。实验结果表明基于图顶点染色的混合优化算法在考虑到对用户的公平性的基础上,有较好的寻优能力和更快的收敛速度,能准确地得出满足全局最优的目标解。通过费城实例进行仿真实验测试,实证了广义图染色优化算法在一定程度上提高了信号间的抗干扰能力,实现了频率资源的最大化。
【关键词】：频率分配 图染色算法 禁忌搜索算法 双领域交替搜索
【学位授予单位】：江西理工大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TN925
【目录】：

• 摘要4-5
• Abstract5-10
• 第一章 绪论10-15
• 1.1 研究背景和意义10
• 1.2 国内外研究10-12
• 1.2.1 国内外研究现状10-12
• 1.2.2 频率分配问题的发展方向12
• 1.3 频率分配与图染色的主要研究内容12-13
• 1.4 论文的主要内容及组织结构13-15
• 第二章 频率分配问题15-24
• 2.1 频率分配概述16-18
• 2.1.1 频率分配的概念与发展16-17
• 2.1.2 频率分配的作用17
• 2.1.3 频率分配的分类17-18
• 2.1.4 频率分配策略的比较18
• 2.2 频率分配方案18-21
• 2.2.1 频率分配中的约束条件19
• 2.2.2 频率分配模型19-20
• 2.2.3 频率分配的主要性能指标20-21
• 2.3 频率分配的特性21
• 2.4 频率分配方案的算法与分析21-23
• 2.4.1 频率分配的常用算法21
• 2.4.2 频率分配的常用算法分析21-23
• 2.5 本章小结23-24
• 第三章 图染色问题24-33
• 3.1 图染色问题的概述24-27
• 3.1.1 预备知识24
• 3.1.2 图染色问题的起源24-25
• 3.1.3 图染色的相关概念25-26
• 3.1.4 图染色问题的相互转化26-27
• 3.2 图染色问题的模型27-29
• 3.3 图染色问题的算法分析29
• 3.4 图染色问题与频率分配的关系29-32
• 3.4.1 图染色问题与频率分配问题的相互转化30
• 3.4.2 图染色问题与频率分配问题的异同30-32
• 3.5 本章小结32-33
• 第四章 基于图顶点染色的混合优化算法33-43
• 4.1 问题的提出33
• 4.2 基于图染色的混合优化算法相关概念33-36
• 4.3 图顶点染色的混合优化算法36-42
• 4.3.1 算法思想36
• 4.3.2 初始解的生成36-37
• 4.3.3 双领域交替搜索37-38
• 4.3.4 算法执行38-40
• 4.3.5 实验结果与分析40-41
• 4.3.6 算法复杂度分析41-42
• 4.4 本章小结42-43
• 第五章 广义图染色优化算法在频率分配中的应用43-52
• 5.1 问题的提出43
• 5.2 基于广义图染色的优化算法相关理论知识43-46
• 5.2.1 基于广义图染色优化算法的主要参数43-44
• 5.2.2 费城实例44-46
• 5.3 基于广义图染色优化算法46-50
• 5.3.1 广义图染色优化算法的主要思想46
• 5.3.2 初始解的生成46-48
• 5.3.3 广义图染色优化算法的执行48-50
• 5.4 基于广义图染色的优化算法的实验与结果分析50-51
• 5.4.1 费城实例的实验结果50
• 5.4.2 算法复杂度分析50-51
• 5.5 本章小结51-52
• 第六章 总结与展望52-54
• 6.1 工作总结52-53
• 6.2 研究展望53-54
• 参考文献54-57
• 致谢57-58
• 攻读学位期间的研究成果58-59

【参考文献】

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

1 张远平;张永生;;一种求解频率分配问题的分布式算法[J];科学技术与工程;2006年20期

2 秦岭松,乔秦宝,宋光爱,陈泽宗;图着色问题的细胞神经网络算法研究[J];武汉水利电力大学学报;1999年02期

，

本文编号：1115546