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

《基于cuda的图顶点着色问题的并行遗传算法研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于CUDA的图顶点着色问题的并行遗传算法研究第1章绪论1.1研究背景及意义图着色问题(GraphColoringProblem,GCP)是图论中的经典问题。图论(GraphTheory)在离散数学学科中处于核心地位[1]，其以图作为研究目标，许多实际问题都可通过图论抽象成图着色问题。图论中的图由若干个顶点及其连边构成，通常将物质生活中的诸多事物间的联系都能映射到图中：采用顶点表示事物，连边表示两个事物之间的联系，故而应用广泛。图的顶点着色问题同时也是一个重要的组合优化问题。组合优化问题广泛存在于运筹学[2]、数学[2]、生物学[4]、化学系统[5]、计算机系统[6]等等方面。因而，研

2、究图着色问题对解决组合优化问题关系重大。随着近两百来年的发展，图着色问题的研究与应用已经延伸到了许多交叉学科比如管理科学[7]、计算机科学[8]、分子物理学[9]、生物学[10]等等方面，图着色问题在理论和实践方面的应用兼并，在工程领域内，比如任务调度[11]、寄存器分配[12]、电子电路[13]等等方面应用广泛[14]。图着色问题是个典型的NP-完全问题[15]，在图论学科里中是重要基石。图着色问题它是给地图上任意两个相邻区域分配不同的颜色，该问题有两个条件需同时成立：(1)分配的颜色数为k;(2)相邻区域分配的颜色不同。若使用k种颜色对图G能够进行着色，则称图G是k-点可着色。若图

3、G是k-点可着色且(k-1)不可着色，则称图G是k-色图，k称为图G的着色数，简记为X(G)。..1.2研究现状图着色问题的常见求解方法有两类：一类是精确算法，他们在解空间较小的时候通过对解空间进行完整的搜索，可以找到最优解，另外一类就是近似算法，它们舍弃了搜索整个解空间的巨大代价，退而求其次，找到全局最优解，近似算法中比较典型的是超启发式算法，而如今为增强寻找最优解的能力，多种混合式启发算法也被提出。精确算法在求解最优解的过程中体现出了数学的严谨性。这类算法的优点是能够获得比其他算法更加优越的解。精确算法有在1979年DBrélaz等人提出的基于对比图的结构和顶点度的精

4、确算法[16]，在1985年M.Kubale等提出的隐式枚举算法[17]，在1991年SagerTJ,LinSJ提出的裁剪搜索树的算法[18]，在1995年AMehrotra,MATrick提出的基于列生成法的图着色算法[19]，在2008年Méndez-Díaz,P.Zabala提出的割平面算法[20]等。这类算法特点是只能在问题规模较小的时候效果较好，但是当问题的规模一旦变大，精确算法却无法避免指数爆炸问题除了精确算法外，对于NP完全问题，我们还有一类近似算法，它们一般都是先从一个粗略的解开始，通过在其领域范围内反复搜索对比替换，得到次优解，慢慢的向最优

5、解靠拢。早期的近似算法有模拟退火算法、蚁群算法、禁忌搜索算法、粒子群算法、人工神经网络算法等，这类算法被称作超启发式算法，这类超启发式算法能够有效解决NP完全问题求解规模大难以找到最优解的特点，如今为了增强超启发算法搜索能力而出现了许多混合式超启发式算法。就国内而言，在2010年，韩丽霞，王宇平等人提出了基于有序划分编码的图着色算法，其是对于整数编码带来的冗余性而提出的一种新型编码方式[21]。.第2章遗传算法和CUDA技术简介2.1遗传算法的介绍遗传算法（GeicAlgorithm）是根据达尔文的生物进化论而提出来的一种随机搜索算法，遗传算法区别于一般的随机算法，它本身具有动态适应的

6、特点，在一代代的进化中能够搜索到最优解。在1940年初，就有人探索借助计算机从生物学的角度模拟物种的进化过程，但是真正首次提出遗传算法这个概念的还是在1967年，当时执教于美国密执安大学的J.Holland教授所带的学生J.D.Bagley在其论文中第一次提及遗传算法这一概念，再此之后，Holland又指导过学生发表过多篇有关遗传算法的论文，而后的1975年，Holland出版了一本系统的介绍遗传算法的书籍《AdaptationinNaturalandArtificialSystems》[34],这本书的发表被世人当做是遗传算法的元年，进入八十年代以后，遗传算法的正是得到蓬勃发展，在K

7、.A.DeJong[35]戈尔德贝尔格[36]等人的不懈努力下，如今的遗传算法已经相当成熟。遗传算法是一类模仿自然选择的超启发式算法，它属于进化算法的一个分支，在系统发生学，工程，经济，化学，制造，数学，物理，生命科学等等方面应用广泛。在进入下一章节前，为了能更好理解遗传算法，首先会介绍些相关的基本概念。一长串的DNA分子信息序列，将表现型映射到遗传子型上。解码是其反向过程，从遗传分子序列中映射到表现型。编码是整个遗传算法的第一步，也是相当关键