基于CUDA的图顶点着色问题的并行遗传算法研究

发布时间：2017-10-18 00:36

  本文关键词：基于CUDA的图顶点着色问题的并行遗传算法研究

  更多相关文章： 图着色 并行遗传算法 CUDA NP完全问题

【摘要】：图着色问题是一个经典的组合优化问题，许多来源于生活的实际问题都可以转化为求解图着色问题。因此，图着色问题的求解，，对科学技术和工程设计等领域都具有重要作用。然而，没有任何算法可以在多项式时间内求解出该问题的最优解，所以，图着色问题是一个典型的NP完全问题。 近年来，国内外的许多学者提出各种求解图着色问题的算法，如隐式枚举算法、割平面算法等，这类精确算法当问题规模较小的时候效果较好，但是一旦问题规模变大，无法避免指数爆炸问题。除了精确算法，遗传算法、蚁群算法等也被用于求解图着色问题。然而，由于图着色问题具有指数级的解空间规模，无论是精确算法还是近似算法，都需要花费大量的时间进行计算，无法在让人满意的时间内求解出问题的解。 如今基于CUDA的高性能并行计算技术成为研究热点。本文将CUDA和遗传算法相结合，提出一种基于CUDA求解图着色问题的并行遗传算法，算法采用颜色序列对问题进行编码，设计出并行的种群初始化、选择算子、交叉算子和变异算子，极大地提高了算法的效率。 实验结果表明，和传统基于CPU的各类算法相比，本文提出的算法可以较大地减少计算时间，找到已知图例的最小着色数，可以有效求解更大规模的实例。
【关键词】：图着色 并行遗传算法 CUDA NP完全问题
【学位授予单位】：武汉科技大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要4-5
• Abstract5-8
• 第1章 绪论8-13
• 1.1 研究背景及意义8
• 1.2 研究现状8-11
• 1.2.1 图着色问题的研究现状8-9
• 1.2.2 遗传算法的研究现状9-10
• 1.2.3 CUDA 的发展现状10-11
• 1.3 本文的主要工作及组织11-13
• 第2章 遗传算法和 CUDA 技术简介13-24
• 2.1 遗传算法的介绍13-17
• 2.1.1 遗传算法的相关基本概念13-15
• 2.1.2 遗传算法的基本流程15-16
• 2.1.3 遗传算法的特点与应用16-17
• 2.2 CUDA 并行编程介绍17-23
• 2.2.1 GPU 及 CUDA 的发展与现状17-18
• 2.2.2 CUDA 的存储器层次结构18-19
• 2.2.3 CUDA 编程模型19-20
• 2.2.4 CUDA 中的通信20-21
• 2.2.5 CUDA 编程相关问题21
• 2.2.6 CUDA 软件开发方法及流程21-23
• 2.3 本章小结23-24
• 第3章 基于遗传算法的图着色问题研究24-36
• 3.1 基于顶点序列的遗传算法24-30
• 3.1.1 图的存储方式24-25
• 3.1.2 染色体的编码25
• 3.1.3 适应度函数的设计25-28
• 3.1.4 个体选择的设计28
• 3.1.5 个体的交叉设计28-29
• 3.1.6 个体的变异设计29
• 3.1.7 基于顶点序列的遗传算法29-30
• 3.2 基于颜色序列的遗传算法30-33
• 3.2.1 图的存储方式30-31
• 3.2.2 染色体的编码方式31
• 3.2.3 适应度函数的设计31-33
• 3.2.4 基于颜色序列的遗传算法33
• 3.3 实验对比与分析33-35
• 3.4 本章小结35-36
• 第4章 基于 CUDA 的图着色并行遗传算法36-53
• 4.1 引言36
• 4.2 图的存储方式36
• 4.3 染色体的编码36-37
• 4.4 并行遗传算法描述37-38
• 4.5 染色体子空间的建立38
• 4.6 个体的优化38-42
• 4.7 适应度函数的设计42
• 4.8 遗传算子的设计42-45
• 4.8.1 选择算子43
• 4.8.2 交叉算子43-44
• 4.8.3 变异算子44-45
• 4.9 个体择优45-46
• 4.10 实验结果与分析46-53
• 第5章 总结与展望53-54
• 5.1 总结53
• 5.2 展望53-54
• 参考文献54-58
• 致谢58-59
• 附录 1 攻读硕士学位期间发表的论文59-60
• 附录 2 攻读硕士学位期间参加的科研项目60-61
• 大摘要61-65

【参考文献】

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

1 韩丽霞;王宇平;兰绍江;;基于有序划分编码的图着色算法[J];电子学报;2010年01期

2 何利娟;;利用遗传算法实现病毒生命化[J];福建电脑;2011年02期

3 张楠;蒋海凤;;图的染色问题及其应用[J];计算机光盘软件与应用;2014年17期

4 吴恩华,柳有权;基于图形处理器(GPU)的通用计算[J];计算机辅助设计与图形学学报;2004年05期

5 周勇;王皓;程春田;;使用GPU技术的数据流分位数并行计算方法[J];计算机应用;2010年02期

6 杜文丽;原亮;;遗传算法的特点及应用领域研究[J];科技信息(科学教研);2008年10期

7 许进;强小利;方刚;周康;;一种图顶点着色DNA计算机模型[J];科学通报;2006年04期

8 赵兴娜;李文振;;遗传算法在自动控制领域的应用分析[J];科技致富向导;2013年08期

9 田朝薇;宋海洲;杨金勇;;一个组合优化问题的求解[J];黑龙江大学自然科学学报;2013年05期

10 张丽;丁晓东;;图着色问题的逆序蚁群算法研究[J];上海理工大学学报;2014年05期

本文编号：1051951