论文部分内容阅读
遗传算法(Genetic Algorithm)是模拟达尔文生物进化论的自然选择和遗传学的生物进化过程的计算机计算模型，是一种通过模拟自然进化过程搜索最优解的方法。在本质上，遗传算法是一种不依赖具体问题的直接搜索方法，其在模式识别、神经网络、机器学习、生物科学、社会科学、图像处理、工业优化控制、自适应控制等领域都有着广泛的应用。但是，在科学计算、物理模拟等涉及大规模复杂问题的领域中，往往需要处理大量的数据，应用遗传算法求解却需要大量的时间。因此，能减少求解时间的并行的遗传算法得到了研究者们的青睐。然而，细数当前流行的各大并行计算平台，使用消息传递接口的集群网络、采用多线程技术的多核CPU等计算平台却因网络带宽不够、硬件环境难以获得、多进程间通信复杂、CPU使用串行模拟并行等原因，导致算法的加速比往往都不是太高。
过去的二三十年，计算机的计算能力多是与CPU的时钟频率紧紧联系的，随着制作工艺的不断提高，CPU中包含的晶体管越来越多，CPU的时钟频率也达到了惊人的3GHz，但是，也因此达到了一个性能瓶颈，继而，研究者们采用多核处理器解决了这个瓶颈，也就使得采用并行计算解决传统单处理器计算机所不能解决的大规模问题变得越来越广泛，特别是图形处理器(GPU)的出现。GPU的高性能、高带宽、高并行性、可编程架构，以及在通用计算领域中已取得的应用成果正不断引起更多的研究者的兴趣，虽然GPU在某些方面仍然存在缺点，但这却掩盖不了它的巨大发展潜力，基于GPU的通用计算(GPGPU)正以前所未有速度发展开来。在GPU发展早期，只能通过3D图形APIs来迁移原有运行于CPU的代码，如：Direct3D或OpenGL，这种迁移在复杂应用中简直是灾难性的，同时开发者必须了解图形像素处理机制及图形硬件底层架构，还得采用图形编程的思维转化原有算法。近年来，随着各类GPU API平台的发布，开发GPU端的并行应用才真正变得触手可及。CUDA是NVIDIA公司于2006年末发布的一个GPU编程的统一计算设备架构，它的全称是Compute Unified Device Architecture，它是NVIDIA公司针对自家GPUs产品开发一款并行计算引擎，使得开发人员通过工业标准的编程语言(如：C、C++等)开发GPUs端应用变得更为容易。开发人员首先使用NVCC编译，将代码转化为GPU的内核函数(Kernel)，再在GPUs端运行转化好的代码程序，CUDA框架支持大量的计算接口，其中包括OpenCL和微软公司的DirectCompute，同时还支持多种第三方开发语言的封装，如：Python，JAVA，FORTRAN，Matlab等。在该架构下，GPU同时执行多个并发线程，为了提高并行速度，CUDA将多个线程组成一个线程块(Thread Block)，线程块中的线程可以读写同一线程块中的共享内存，线程之间的同步也因CUDA架构变得异常容易。
本文针对传统遗传算法早期收敛缓慢的不足，结合GPU的高性能、高并行性的优势，提出了一种基于对立学习的并行遗传算法(OPGA)，将遗传算法的自然选择、交叉变异、适应度计算等阶段都转化为GPU的内核函数，使用GPU的并行线程模拟个体，使得OPGA算法在GPU中得到有效的加速。算法在迭代早期采用对立学习机制，在算法迭代后期再恢复传统遗传算法，以求解对称旅行商问题为例，详细描述了算法设计思路和程序实现细节，提供了对不同规模的TSP问题的实验结果，并与相应的串行算法进行比较，分析了基于对立学习的并行遗传算法的优劣势，最后，还通过CUDA Visual Profiler分析各个内核函数的GPU计算时间和性能。实验结果表明算法早期引入的对立学习机制能快速靠近近似解，而在算法后期恢复常规遗传算法有效避免了对立学习的负作用，求得的最优解与传统遗传算法基本一致，同样的运算时间，基于对立学习的并行遗传算法能获得更好的解。