信 息 技 术
DOI：10.16661/jki.1672-3791.2019.21.007
曹亚
(安徽水利水电职业技术学院 安徽合肥 231603)
摘 要：该文介绍了GPU概念及发展、并行计算的概念以及与串行计算相比而具有的优势，指出智能优化算法具有天然的并行性和分布性，在基础理论和工程应用中具有很高的研究价值，该文对智能优化算法中的模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法及蚁算法的原理和实际应用进行了深入研究，提出了基于GPU的并行优化算法。 关键词：GPU 并行计算 算法
中图分类号：TP301 文献标识码：A 文章编号：1672-3791(2019)07(c)-0007-02精神病学
Abstract:This paper introduces the concept and development of GPU, the concept of parallel computation and the advantage of the serial calculation, and points out that the intelligent optimization algorithm has the natural parallelism and the distribution, and has very high research value in the basic theory and engineering application. In this paper, the principle and practical application of the simulated annealing algorithm, the genetic algorithm, the tabu search algorithm, the artificial neural network algorithm and the ant colony algorithm in the intelligent optimization algorithm are deeply studied, and a parallel optimization algorithm based on the GPU is proposed.
Key Words: GPU; Parallel Computing; Algorithms
GPU并行计算是利用图形处理器，充分利用GPU内部结构，提高运算效率，目前，人们己经提出了很多GPU并行计算的模型，大家对GPU的并行计算都有非常大的兴趣，该文对GPU并行优化算法进行了研究。
1 CPU简介
GPU是Graphic Processing Unit的英文缩写，中文意思为图形处理器。GPU计算就是利用图形处理器进行科学和工程计算，最早GPU出现是为了提高3D图形处理速度，之后，GPU引入了编程和通用计算，目的是求解数学扩散方程和矩阵乘法。GPU在并行计算上的优势非常明显，矩阵运算、生命科学
等方面的应用，有大量重复的数据运算，所以都需要GPU强大的计算功能。但是GPU并行运算的条件是它要解决的问题能够分解并行执行。所以，GPU要发展得更好必须有两个方面能力：（1）分支能力。GPU只有具有更强的分支能力，复杂的计算程序才能进行。（2）更大的共用存储器和缓存空间。共享存储器是共享数据、挂起线程，缓存空间越大，线程跳转就越快，分支能力就越大。
GPU发展到如今，已经突破了很多技术壁垒，由当初图形处理而诞生的硬件发展成大规模并行计算。智能终端对图像显示的要求逐渐提高，GPU的性能也会随之更加优化。
2 并行计算
所谓并行计算[1]是指在单位时间内，充分利用多个处理器单元，同时执行多条数据及指令的计算，用传统的串行计算处理大规模数据需要很长时间，于是，人们研究是否有途径能同时处理不同的数据，并行计算就随之出现了，在时间上，并行是指流水线技术，在空间上，并行是指多个处理器同时进行计算。因为并行计算是用多个处理器共同完成一个计算任务，能最大程度地缩短完成任务的时间，所以与串行算法相比较，并行算法能有效解决大规模运算问题。如图1所示，所谓并行计算就是把要解决的问题划分成一系列子任务，然后由多个不同功能的处理核完成各自的计算任务，这些处理核在计算数据时应彼此配合，以求达到获得最大计算性能[2]。
3 智能优化算法
智能优化算法[3]是仿照自然界智能优化原理而设计产生的算法，智能优化算法具有天然的并行性和分布性，此特性十分适合在并行计算设备上实现并行算法。智能优化算法在理论研究上和工程应用上都具有很高的价值，在图像处理、信号处理、任务分配、生产调度、模式识别、机械设计和自动控制等众多领域得到了成功应用。其主要包括模拟退火算法、遗传算法、禁忌搜索算法和人工神经网络等。
白嘉轩
(1)模拟退火算法。
模拟退火算法是依照固态物质的退火原理而产生的，主要应用于解决组合优化问题。当被加热的固态物质的
①基金项目：本文系2017安徽省高校自然科学研究项目课题“基于GPU并行计算的线性规划算法研究”研究成果（项目 编号：KJ2017A600）。
北京语言大学bbs作者简介：曹亚（1978—），女，汉族，安徽宿州人，硕士，讲师，主要从事高等数学教学与研究。
7
科技资讯 SCIENCE & TECHNOLOGY INFORMATION
信 息 技 术
温度到某定值时，其里面微粒的布朗运动逐渐加剧，直至到达一定的运动强度时，固态就变成了液态，此时再退火，固态物质内的朗运动会慢慢变弱，最终稳定下来。
用模拟退火算法不会出现局部最优解，在模拟退火算法中设定某个理想概率P，若新解的目标函数的数值更优，就取P=1，也就是选择更加优化的解。否则，让理想概率P取当下解的目标函数、新解的目标函数及参数T的函数。可以看出，在求解最优解时该算法既考虑最优的解，同时还考虑目标函数不理想的解。算法中的参数T在运行该算法时会逐渐减小，直到小于某个数值时该算法结束。
(2)遗传算法。
遗传算法是来自于大自然中适者生存、优胜劣汰的遗传变异的生物进化而设计产生一种算法。该算法是开始于一个种，该种代表要优化问题的可能解集，包含标有基因编码的一定数目的个体，把基因编码为染体，所有个体都具有染体的特点，算法过程中引入一些随机参数高效搜索解空间。遗传算法首先编码生成初代种，然后检查否满足收敛准则，若不满足，则继续，若满足，则结束算法，接着评价检测适应性及选出最优个体，最后交叉配种和基因突变产生新的种。遗传算法过程类似于自然进化过程，产生的后代种比前代种有更好的适应性，算法结束后，把末代种内最优个体解码，就是问题的最优解[4]。
遗传算法是把要解决问题的所有潜在解看成个体即染体，且把每个染体编码，然后对照目标函数逐个评价染体，遗传算法依据给定的适应值借助选择、杂交及变异3个算子寻最优解。选择好变异算子是遗传算法关键一步，能够避免陷入局部最优解。
(3)禁忌搜索算法。
禁忌搜索算法TS（Tabu Search）是美国的Glover早在1986年提出的，是一种全局最优搜索算法，该算法是仿照人类的智力活动，引入一个数据储存结构，根据一些禁忌准则避免重复的搜索，从而确保搜索结果的全局最优化，提高搜索的有效性及准确性。禁忌搜索算法广泛应用于组合优化、机器学习、神经网络及电路设计等领域[5]。
(4)人工神经网络算法。
樊字疗法人工神经网络算法(Artificial Neural Network)最早是由Warren McCulloch和Walter Pitts于1943年根据生物学中神经网络的基本原理而建立的模拟人脑智能过程的计算模型。在该算法中，轴突、树突等神经元结构都是模仿人类处理问题的思考过程。人工神经网络算法有很好的并行性，在算法过程中有自主反馈能力。生命科学中的神经细胞称作神经元，是神经结构的基本单元，神经细胞类似于胳膊，长的像手掌的称作细胞体，其中含有细胞核。长的像手指的称为树突，像手臂的称作轴突，它们分别是信息的输入和输出通路，各神经元之间复杂地连接着，彼此传递信息。 ⑸蚁算法。
蚂蚁是自然界中常见的昆虫，单个蚂蚁看不出有什么特殊的，可是数以百计的蚂蚁共同完成一个任务时展现出的集体智慧值得人类研究。在觅食过程中它们表现出的集智能搜索启发着人们对最短路径的搜索，于是产生了蚁算法。生物学研究表明，一只蚂蚁不能但是一蚂蚁却能到蚁巢与食物两者间的最短路径，是因为蚁具有信息正反馈能力，即蚂蚁走过越多的路径，则此条路径被后面蚂蚁选择的可能性就越大，借助这种间接的互通信息寻出食物与蚁穴间最短路径。蚂蚁合作觅食本质如下：
七十七国集团(1)协同工作机制，即蚂蚁之间借助信息素进行联系通信。
(2)信息素强化机制，即短路径上的信息素踪迹浓度增加得快。(3)路径概率选择机制，即含有信息素踪迹的路径越浓，被选择的概率就越大。
蚁优化算法中人工蚁的程序如下：众多人工蚁彼此合作在解空间中寻好的解，它们根据人工信息素踪迹及问题的相关信息的提示下构造问题的解。此处的信息素好像一种长期记忆，该记忆是整个分布在问题空间。当众多人工蚁在要解决的问题空间中行走时，在它们走过的路径上有信息素踪迹，留下的踪迹展现了人工蚁“觅食”，即构造问题好的解的过程，在蚁的合作中信息素担当媒介的作用，蚂蚁们喜欢行走在信息素浓的路径上，也会在走过的路径上留下新的信息素，这种正反馈引导着蚁
到最优解。
上面讲到的模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法具有各自不同的特点，但是它们都没有天然的并行性，都不太适合在并行计算平台上进行仿真实现。而具有并行优化特征的蚁优化算法适合在并行计算机上运行、解决问题。
4 结语
该文对GPU、并行计算进行了简单的介绍，对基于GPU的并行优化算法进行了研究，通过对模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法及蚁算法的研究，说明了GPU并行优化计算在一些算法上是可行、高效的。
参考文献
[1] 周江，庄越.基于GPU的高性能并行算法研究[J].电子技
术与软件工程,2008,20(2):187-188．
[2] 杨柳，刘铁英.GPU架构下的并行计算[J].吉林大学学报:
信息科学版,2012,30(6):630-631．
[3] 李繁.基于GPU的高性能并行优化算法研究[D].大连理
工大学,2014．
[4] 海丽切木·阿布来提.浅谈几种智能优化算法[J].电脑知
识与技术,2011,7(19):4628-4629．
[5] 张庆科，杨波，王琳，等.基于GPU的现代并行优化算法[J].
计算机科学,2012,4(39):304-305.
8科技资讯 SCIENCE & TECHNOLOGY INFORMATION
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议