基于岛的遗传算法在CUDA上的优化实现

论文摘要

随着图形处理器(Graphics Processing Unit, GPU)的迅猛发展,使得图像处理、计算机仿真等领域的发展得到了有力的推进。而随着GPU的发展,人们也开始利用GPU的强大的并行计算能力解决一些实际的问题,开始有越来越多的人参与到了基于GPU的以及GPU通用计算的课题的研究中来。这其中,并行算法方面的研究就是一个热点课题。本文以学习和研究基于CUDA大规模并行通用计算为目标,选择了基于岛的遗传算法进行了研究。遗传算法(Genetic Algorithm)是模仿生物界中适者生存、优胜劣汰这一规律,演化出的随机化的搜索方法。该算法的特点是：对结构对象进行操作,而受求导和函数连续性的限制；有很好的内在隐并行性和优秀的全局寻优能力；利用概率化巡游方法可以自动获得和指导优化的搜索空间,不用特意规定的去调整搜索方向,它已经被广泛用于组合优化、函数优化、遗传编码、机器学习和人工生命等领域,是当下有关智能计算中的关键性技术。虽然遗传算法可以有效的解决很多领域中的许多的实际问题,但是它的执行时间却成为了限制它使用的主要因素,尤其是在解决一些巨大任务量的问题时,遗传算法的运行时间会过长。不过,通过并行化适应度评估这个过程,算法运行时间过长的问题已经得到了解决,使得它可以在种群中的每个个体之间并行独立的执行,这样就可以大大降低算法的运行时间,提高遗传算法的效率本文对并行遗传算法——基于岛的遗传算法进行了研究和分析并在NVIDIA提出的CUDA架构建立模型实现了该算法：首先,整个种群被分成了若干个子种群,每个子种群被分离到GPU的各个处理器上；这些个分散的种群可以各自进化,从而达到各个子种群的最优状态；之后利用迁移算子再混合各个子种群呈现的优良特性。本文对算法在CPU和GPU上进行了测试,通过CUDA加速后的基于岛的遗传算法在运行速度方面和结果质量方面都得到了非常可观提升。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 遗传算法简述
• 1.2 基于图形处理器（GPU）的通用计算
• 1.3 研究GPU通用计算的意义
• 1.4 本文的主要工作和主要结构
• 第2章 GPU通用计算
• 2.1 GPU通用计算的发展
• 2.2 GPU通用计算的优势
• 2.3 GPU的体系架构
• 2.4 GPU进行大规模并行计算方面的优劣
• 第3章 CUDA编程介绍
• 3.1 CUDA编程模型
• 3.1.1 主机端与设备端
• 3.1.2 内核函数
• 3.1.3 线程层次
• 3.1.4 存储器层次
• 3.2 CUDA存储器模型
• 3.3 编程接口
• 3.3.1 CUDA的核心——CUDAC语言
• 3.3.2 编译流程
• 第4章 基于GPU并行计算的遗传算法设计
• 4.1 传统遗传算法
• 4.2 遗传算法中的基本算子
• 4.2.1 选择算子
• 4.2.2 交叉算子
• 4.2.3 变异算子
• 4.3 基于GPU并行计算的遗传算法设计
• 4.3.1 基于岛的遗传算法设计目的
• 4.3.2 基于岛的遗传算法的思路
• 4.4 岛与岛之间的种群迁移
• 4.5 算法的参数控制
• 第5章 基于岛的遗传算法在CUDA上的实现
• 5.1 算法的实现
• 5.2 实验结果
• 5.3 实验结果质量
• 第6章 总结与展望
• 6.1 工作总结
• 6.2 对未来工作的展望
• 参考文献
• 致谢