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

摘要

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

目录

封面

声明

中文摘要

英文摘要

目录

第1章 绪论

1.1研究背景及意义

1.2研究现状

1.3 本文的主要工作及组织

第2章 遗传算法和CUDA技术简介

2.1遗传算法的介绍

2.2 CUDA并行编程介绍

2.3本章小结

第3章 基于遗传算法的图着色问题研究

3.1基于顶点序列的遗传算法

3.2 基于颜色序列的遗传算法

3.3实验对比与分析

3.4本章小结

第4章 基于CUDA的图着色并行遗传算法

4.1引言

4.2图的存储方式

4.3染色体的编码

4.4并行遗传算法描述

4.5染色体子空间的建立

4.6个体的优化

4.7 适应度函数的设计

4.8遗传算子的设计

4.9个体择优

4.10实验结果与分析

第5章 总结与展望

5.1总结

5.2展望

参考文献

致谢

附录1攻读硕士学位期间发表的论文

附录2攻读硕士学位期间参加的科研项目