基于GPU和Python的粒子群优化算法研究.pdf

Vol.49 No.4Journal of Southwest MinzuUniversity(Natural Science Edition)第49 卷第4期Jul.20232023年7 月西南民族大自然科学版）doi:10.11920/xnmdzk.2023.04.010基于GPU和Python的粒子群优化算法研究熊大卫，胡建，陈园（西南民族大学计算机科学与工程学院，四川成都610041)摘要：针对基于Python语言的粒子群优化算法利用CPU实现加速的空缺问题，提出一种基于GPU和Python的改进粒子群优化算法：以CUDA架构和Python的Numba库为工具，将算法中的粒子评价、个体历史最优解更新、粒子升级三个部分进行CUDA编程，CUDA核函数中每个线程按单个粒子并行调用，在默认流中完成计算.经4种测试函数实验验证，所提出的改进算法在维数和粒子数较小时运行速度不及粒子群优化算法，在维数和粒子数较大时加速效果明显，最优速度达到粒子群优化算法的3倍以上。关键词：粒子群优化算法;Python;GPU;CUDA中图分类号：TP301.6文献标志码：A文章编号：2 0 95-42 7 1(2 0 2 3)0 4-0 42 4-0 5Particle swarm optimization based on GPU and PythonXIONG Da-wei,HU Jian,CHEN Yuan(School of Computer Science and Engineering,Southwest Minzu University,Chengdu 610041,China)Abstract:To address the vacancy problem of the Python-based particle swarm optimization algorithm using GPU to achieve ac-celeration,this paper proposed an improved particle swarm optimization algorithm based on GPU and Python:using CUDA archi-tecture and Python s Numba library as tools,and the three parts of the algorithm,particle evaluation,updating individual histori-cal optimal solutions,and particle upgrading,were programmed in CUDA.Each thread in the CUDA kernel function was calledin parallel by a single particle,and the computation was completed in the default stream.After experimental verification by fourcommonly used test functions,the proposed improved algorithm ran slower than the particle swarm optimization algorithm whenthe number of dimensions and particles was small,and accelerated significantly when the number of dimensions and particleswas large,and the optimal speed reached more than three times of the particle swarm optimization algorithm.Keywords:particle swarm optimization;Python;GPU;CUDA群体智能算法已被应用于众多领域，例如数据分析1、半结构化数据查询优化2 、图像分割3 等.但是，由于群体中的个体间相互作用、包含多个随机操作符等原因，导致群体智能算法具有复杂的随机性和动态性，计算时间较长.因为个体间存在内在并行性，故可采用图形处理器（Graphics ProcessingUnit,GPU)通过并行计算的方式4 加速群体智能算法.粒子群优化算法（ParticleSwarmOptimization，PSO)是群体智能算法中最具代表性的一种，目前主要应用于如下几个领域：神经网络训练，如文献5 利用PSO算法调整深度信念网络的内部参数，提出了一套输电线路电晕损耗预测方法,文献6 基于PSO算法提出优化BP神经网络的PID控制算法；函数优化，如文献7 提出多策略混合进化的PSO算法求解大收稿日期：2 0 2 2-0 9-0 1通信作者：胡建（198 0-），男，四川人，教授，研究方向：文献信息化，群体智能.E-mail:基金项目：国家社会科学基金重大招标项目（19ZDA284）；西南民族大学中央高校基本科研业务费专项基金项目(2023NYXXS044)425熊大卫，P和Python的粒子群优化算法研究第4期规模函数优化问题，文献8 提出一种利用种群进化的改进PSO算法求解多模态函数优化问题；路径规划,文献9 提出利用差分进化算法改进的PSO算法,求解动态窗口法的动态路径规划问题,文献10 基于一种改进的PSO算法,求解多目标点路径规划问题.与其他群体智能算法一样，可采用GPU的CUDA架构（Compute Unified Device Architecture，CU-DA),通过并行计算的方式加速PSO,例如文献12以PSO算法为例,研究如何利用CUDA平台进一步发挥群体智能算法的并行性优势；文献13 利用CUDA架构并行实现了柯西振荡粒子群优化算法（CO-PSO）;文献14 应用PSO算法优化克里金算法中的克里金参数,并通过CUDA架构加速PSO算法以提高插值效率近年人工智能飞速发展，作为深度学习领域首选编程语言的Python语言使用率也随之激增.照此趋势,Python相较于其他程序语言的绝对主流地位与PSO在高维复杂优化问题领域的卓越性能都预示这两者的结合趋于必然.但据我们调研，未见PSO算法基于Python语言实现GPU加速的报道.对此，本文基于Python语言，以CUDA架构、Numba库15 为工具提出了利用GPU加速的改进PSO算法，并经实验证明能达到有效的加速效率.这将为基于GPU和Python的PSO并行加速提供有价值的参考.1PSO算法简介PSO算法称解空间中的点为粒子,所有粒子构成种群.各粒子具有初始速度和位置，并根据种群的经验来调整自己的运动，最终找到全局最优位置16 ，其伪代码如下所示，Algorithm PSo1：Initial SwarminCPU/初始化种群2：Fori+-1tolterations:3：Forj1 to P:4：EvaluateParticle/粒子评价5：Check and Update Pbest/更新个体历史最优解6：Check and Update Gbest/更新全局最优解7：Forj-1 to P:8：UpdateVelocityand Position/粒子升级9：Return the bestPosition and Fitness其中，Swarm表示种群，Iterations为迭代代数，P为种群大小，Particle表示粒子，Pbest和Gbest分别表示个体历史最优解和全局最优解，Velocity和Position分别表示速度和位置，按照公式（1）与公式(2）进行更新，Fitness为适应度值.V+1d=wVia+CiT(Pbestia-Xia)+C2T2(Gbestia-Xia).(1)Xitl=Xia+Vul.(2)上述公式中，当前维数d=1,2.D，D 表示最大维数；t为当前代数；第i个粒子的速度向量记为V,=（Va,Va.Va），位置向量记为X=（Xi a，XXa）,其中i=1,.P;待优化问题边界根据测试函数设定记为Xmin，Xma x”，速度和位置更新后,若XiaXmax,则Xia=Xmax;若XiaXmin,则Xid=Xmin:在不同版本PSO算法中参数取值各有不同，但参数值的选取并不会在很大程度上影响本文所关注的算法运行时间.本文为简便起见，参数设置如下：惯性因子w表示上一代粒子的速度对当代粒子速度的影响，使粒子保持运动的惯性和搜索扩展空间的趋势，较大的w有利于全局搜索、跳出局部最优解，而较小的w有利于局部搜索、让算法快速收敛到最优解，w的典型取值范围是0,1.5，本文按照基本粒子群算法将w设置为0.517 ;认知因子c,表示粒子下一步动作来源于自身经验部分所占的权重，社会因子c表示粒子下一步动作来源于其它粒子经验部分所占的权重，当c,和c,都不为0 时算法更容易保持收敛速度和搜索效果的均衡,本文将c和c分别设置为1和218;随机数r,与r,为服从0,1 上的均匀分布随机数,加入此项以提升算法搜索的随机性.2基于GPU和Python的改进粒子群优化算法2.1PSO-CUDA算法Python作为一种解释性语言运行速度较慢，本文选择Numba库通过即时编译技术（JustInTime，JIT)19对程序进行加速.相较于标准PSO算法,PSO-CUDA算法中种群初始化方式不变，将粒子评价、更新个体历史最优解、粒子升级三个部分改用GPU并行计算分别完成.由于全局最优解的更新过程中涉及大量的逻辑判断，虽然426第49 卷西南民族大自然科学版GPU有逻辑运算能力，但GPU不具备CPU的分支预测能力，只能顺序执行逻辑分支，且过程中可能因为Warp Divergence20产生不必要的时间开销,故将更新全局最优解的步骤置于CPU中完成.PSO-CUDA算法流程可概括如下：1）于CPU中完成种群及所需参数初始化;2)拷贝种群至CPU;3)于CPU中调用核函数完成粒子评价、更新个体历史最优解、粒子升级；4)拷贝种群至CPU;5）更新全局最优解.基于Python语言实现的CUDA版本改进PSO算法（简称PSO-CUDA）的伪代码如下所示.Algorithm PSO-CUDA1:Initial Swarm inCPU2：Set TPB as threads per block,BPG as blocks per grid3：Fori-1 to lterations:4:cuda.to_device(Swarm)/拷贝种群至CPU5：cuda.jit/添加JIT修饰符6：Kernel BPG,TPB/调用核函数完成粒子评价、更新个体历史最优解、粒子升级7:cuda.copy_to_host(Swarm)/拷贝种群回CPU8：Check and Update Gbest/更新全局最优解9:Returmn the bestPosition and Fitness其中：Kernel为GPU核函数,TPB为线程块大小，值为10 2 4,BPG为网格大小,其值由种群粒子数除以TPB向上取整得到.调用Kernel的执行配置为BPG,TPB,表示GPU并行启动TPB*BPG个线程.2.2Kernel核函数PSO-CUDA算法分配至GPU中的计算任务主要由Kernel控制，考虑到GPU的逻辑运算能力不及CPU,如何合理为GPU分配计算任务、避免复杂逻辑是算法设计的关键.按照标准PSO算法逻辑，种群中个体升级都需要当前Gbest，但PSO-CUDA中的Gbest更新于CPU中完成、个体升级于GPU中完成，这将导致个体升级过程中不可避免地存在一次数据拷贝.为解决这一问题,PSO-CUDA算法将 Kernel核函数中的粒子升级步骤前置，使当代粒子直接利用上代得到的Gbest进行升级（首次迭代除外），以此减少数据拷贝的时间开销.PSO-CUDA算法中Kernel的流程如下所示.Kernel（粒子升级、评价粒子、更新个体历史最优解）1：Launch threads as the number of BPG*TPB2：AssignSwarmto threads3：For eachParticle in thread(Parallelly)do:4：Whilet!=O:/避免首次送代中的粒子升级5：UpdateVelocity and Position/粒子升级7：EvaluateParticle/粒子评价8：Check and UpdatePbest/更新个体历史最优解种群拷贝至GPU后被分配至不同线程，每个线程将独立地调用Kernel核函数进行并行计算.Kernel流程可概括如下：1）粒子升级；2）粒子评价；3）更新个体历史最优解.Kernel完成上述处理后，将种群拷贝至CPU完成后续步骤.3实验3.1实验环境及参数设置实验旨在通过对比PSO算法与PSO-CUDA算法在同条件下的耗时，验证后者加速效率.实验环境：CPU为Intel（R）Xe o n（R）G o ld-6130H 2.10 GHz,GPU 为 Tesla P100 16 GB,CUDA 版本为11.4,操作系统为Ubuntu18.04.为进行充分验证，实验在不同粒子数、维数、测试函数下进行：粒子数P取值为10、10 0、10 0 0、40 0 0 维数D取值为10、10 0、10 0 0、50 0 0，测试函数边界为-10,10 ”，送代次数Iterations为10 0.实验独立运行10 次，实验结果取10 次结果的均值.为体现公平性与普适性，本实验选取群体智能算法性能测试常用的四个基准测试函数,其中,Sphere函数是常用的新算法的标准测试函数,其特点是全局最优解唯一，由D个定义域相同的自变量求平方和得427熊大卫，的粒子群优化算法研究和Pvthon第4期到2 1;Rosenbrock函数也称山谷函数或香蕉函数,是基于梯度的优化算法的一个流行测试函数，其函数图像呈现为单峰，全局最小值位于图像中最低点，但即使这个最低点很容易找到，其收敛到最低限度也比较困难2 2 ;Rastrigin函数基于De Jong 函数,存在多个局部最优解，增加了一个余弦调制传递函数来产生频繁的局部最小值，其特点是函数极小值出现的位置是有规律的，常用于解决一些规律性问题2 3;Schwefel函数同样存在多个局部最优解，很容易引导算法陷人局部最优2 4 测试函数表达式如表1所示.表1测试函数及表达式Table 1 Test functions and formulas测试函数表达式Dfi(Sphere)fi（x)=i+1D-1f2(Rosenbrock)f2（x)=100(xi+1 2+(x;-1)i=1fs(Rastrigin)fs(x)=10D+i1fa(Schwefel)4(x)=418.9829D-x;sin(/xT13.2实验结果与分析表2算法耗时表Table 2Algorithm time tableD=10D=100D=1000D=5000PSO1.14E-021.01E-011.03E+005.19E+00P=10PSO-CUDA2.14E-011.75E-015.71E-012.24E+00PSO1.12E-011.01E+001.03E+015.34E+01P=100PSO-CUDA1.77E-014.42E-013.23E+001.65E+01PSO1.13E+001.02E+011.06E+025.26E+02P=1000PSO-CUDA5.75E-013.22E+003.28E+011.72E+02PSO4.58E+004.37E+014.26E+022.10E+03P=4000PSO-CUDA1.88E+001.27E+011.33E+026.60E+02运行耗时（秒）D-10SD=100=D=1000D-50001.00E+041.00E+031.00E+021.00E+011.00E+001.00E-011.00E-02PSOPSO_CUDAPSOPSO_CUDAPSOPSO_CUDAPSOPSO_CUDA!P=10-P=100P=1000P=4000-图1算法耗时图Fig.1Algorithm time graph实验结果如表2 和图1所示，其表明：1)当D和P较小时,如D,P=10,10 、10,100、10 0,10,PSO 算法的计算速度快于PSO-CU-DA算法.这种现象主要是因为CPU主频高、Cache大，当计算规模较小时，CPU的浮点运算比GPU表现更好2 5.此外CUDAcore的启动和终止、数据拷贝等也会造成时间开销，故在计算规模较小时，出现CU-DA程序计算速度慢于CPU程序的情况.2)随着D和P的增大：D=10时,PSO-CUDA算法的速度从P=1000开始快于PSO算法；D=100时,PSO-CUDA算法的速度从P=100开始快于PSO算法；D1000时的所有配置组,PSO-CUDA算法都体现出较好的速度优势.D,P】=10 0,40 0 0 】时PSO-CUDA算法的速度优势最大，达到PSO算法的（责任编辑：张阳，付：周序林，郑玉才）第49 卷428西南民族大自然科学版）3.44倍.4总结在PSO算法并行计算提速需求下,本文提出了基于GPU和Python的PSO算法，将计算量较大的粒子升级、粒子评价、更新个体历史最优解进行GPU加速，经实验验证，PSO-CUDA算法在维数和粒子数较小时速度表现差于PSO算法,PSO-CUDA算法的速度优势随着维数、粒子数的增加而逐渐体现，并在维数为10 0、粒子数为40 0 0 时达到了PS0算法3.44倍的加速效果.本文虽然研究了基于GPU的PSO加速问题,但由于群体智能算法的复杂性，该问题仍然是开放性的，仍有一些可研究的问题，例如：改变PSO算法的并行层面,从维度、核函数等方面并行；在其他版本的PSO算法中验证GPU并行的有效性；把本文的并行方法扩展应用于其他群体智能算法中参考文献1张欣，庄园，宁学玲，等基于群体智能算法的电力台区数据分析技术J.计算技术与自动化,2 0 2 2,41（0 2）：8 7-91.2高俊杰，杨帆。基于群体智能的半结构化数据查询优化算法J计算机仿真，2 0 2 1,38(0 8)：38 1-38 5.3史春天，曾艳阳,侯守明.群体智能算法在图像分割中的应用综述J.计算机工程与应用，2 0 2 1,57（0 8）：36 47.4韩俊刚,刘有耀,张晓图形处理器的历史现状和发展趋势J.西安邮电学院学报,2 0 11,16(0 3）：6 1-6 4.5黄书民,蒋林高，李志川,等.基于PSO寻优与DBN神经网络的电晕损耗预测J.中国电力，2 0 2 2,55（0 6）：95-10 2+2 14.6曾雄飞.基于粒子群算法优化BP神经网络的PID控制算法J.电子设计工程，2 0 2 2,30（11）：6 9-7 3+7 8.7肖天宇，张著洪求解大规模函数优化的粒子群优化算法J.计算机工程与设计,2 0 2 1,42（0 6）：16 14-16 2 2.【8 王栋浩，靳其兵，牛亚旭，采用种群进化的粒子群多模态函数优化J.现代电子技术，2 0 2 0,43（13）：10 6-10 9.9孙睿彤，袁庆霓，衣君辉，等改进粒子群算法和动态窗口法的动态路径规划J/0L.小型微型计算机系统：1-10.2 0 2 2-0 7-12 .ht-tp:/ 0 2 2,34（0 3）：2 2 5-2 32+2 8 4.11 NVIDIA.CUDA Toolkit Documentation vl1.4.0EB/OL.(2021-06-29】2 0 2 2-0 7-19 J.h t t p s:/d o c s.n v i d i a.c o m/c u d a/a r c h i v e/11.4.0/.12韩文成基于CPU的群智能算法研究与实现D.陕西西安：西安理工大学，2 0 19.13DONG L,LI D Q,JIANG F B.A two-stage CO-PSO minimum struc-ture inversion using CUDA for extracting IP information from MT dataJ.Journal of Central South University,2018,25(5):1195-1212.14J WANG Z,WAN B,HAN M.A Three-Dimensional visualization frame-work for underground geohazard recognition on urban road-facing GPRdata J.International Journal of Geo-Information,2020,9(11):668.15 ANACONDA,INC.Numba documentation EB/OL.(2022-05-25)2022-07-19.https:/numba.readthedocs.io.16 KENNEDY J,EBERHART R.Particle swarm optimization(PSO)C/Proc.IEEE International Conference on Neural Networks.Perth,Australia.1995:1942-1948.17SHI Y,EBERHART R.A modified particle swarm optimizerJ.IEEEWorld Congress on Computational Intelligence(Cat.No.98TH8360),1998:69-73.18JTRELEA I C.The particle swarm optimization algorithm:convergenceanalysis and parameter selection J.Information Processing Letters,2003,85(6):317-325.19 ANACONDA,INC.Compiling Python code with jit EB/OL.(2022-05-25)2022-07-19.https:/numba.readthedocs.io/en/sta-ble/user/jit.html.2O ROB FARBER.CUDA application design and development EB/OL.(2011-01-03)2023-06-28.https:/ J,DIXON LCW,et al.Toward global optimization J.Pro-ceedings of a Workshop at the University of Cagliari,1974,59(2):137-138.22 MOLGA M,SMUTNICKI C.Test functions for optimization needs EB/OL.（2 0 0 5-0 4-0 3)2 0 2 3-0 6-2 9 .h t t p s :/w w w.r e s e a r c h g a t e.n e t/file.PostFileLoader.html?id=58b2a0f65b495225de610cfO&assetKey=AS%3A465946130292736%401488101622191.23 POHLHEIM H.CEATbx examples:examples of objective functionsEB/OL.（2 0 0 5-11）2 0 2 3-0 6-2 9.h t t p:/w w w.g e a t b x.c o m/download/GEATbx_ObjFunExpl_v37.pdf.24J LAGUNA M,MARTI R.Experimental testing of advanced scattersearch designs for global optimization of multimodal functions J.Journal of Global Optimization,2005,33(2):235-255.25 LEE V W,KIM C,CHHUGANI J,et al.Debunking the 100X GPU vs.CPU myth:an evaluation of throughput computing on CPU and GPUC/International Symposium on Computer Architecture.ACM,2010.