基于GPU和Python的粒子群优化算法研究.pdf
《基于GPU和Python的粒子群优化算法研究.pdf》由会员分享,可在线阅读,更多相关《基于GPU和Python的粒子群优化算法研究.pdf(5页珍藏版)》请在咨信网上搜索。
1、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库为工具,将算法中的粒子评价、个体
2、历史最优解更新、粒子升级三个部分进行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,CHE
3、N 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
4、 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 paralle
5、l 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 accele
6、rated 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 等.但是,由于群体中的个体间相互作用、包含多个随机操作符等原因,导致群
7、体智能算法具有复杂的随机性和动态性,计算时间较长.因为个体间存在内在并行性,故可采用图形处理器(Graphics ProcessingUnit,GPU)通过并行计算的方式4 加速群体智能算法.粒子群优化算法(ParticleSwarmOptimization,PSO)是群体智能算法中最具代表性的一种,目前主要应用于如下几个领域:神经网络训练,如文献5 利用PSO算法调整深度信念网络的内部参数,提出了一套输电线路电晕损耗预测方法,文献6 基于PSO算法提出优化BP神经网络的PID控制算法;函数优化,如文献7 提出多策略混合进化的PSO算法求解大收稿日期:2 0 2 2-0 9-0 1通信作者:胡
8、建(198 0-),男,四川人,教授,研究方向:文献信息化,群体智能.E-mail:基金项目:国家社会科学基金重大招标项目(19ZDA284);西南民族大学中央高校基本科研业务费专项基金项目(2023NYXXS044)425熊大卫,P和Python的粒子群优化算法研究第4期规模函数优化问题,文献8 提出一种利用种群进化的改进PSO算法求解多模态函数优化问题;路径规划,文献9 提出利用差分进化算法改进的PSO算法,求解动态窗口法的动态路径规划问题,文献10 基于一种改进的PSO算法,求解多目标点路径规划问题.与其他群体智能算法一样,可采用GPU的CUDA架构(Compute Unified De
9、vice Architecture,CU-DA),通过并行计算的方式加速PSO,例如文献12以PSO算法为例,研究如何利用CUDA平台进一步发挥群体智能算法的并行性优势;文献13 利用CUDA架构并行实现了柯西振荡粒子群优化算法(CO-PSO);文献14 应用PSO算法优化克里金算法中的克里金参数,并通过CUDA架构加速PSO算法以提高插值效率近年人工智能飞速发展,作为深度学习领域首选编程语言的Python语言使用率也随之激增.照此趋势,Python相较于其他程序语言的绝对主流地位与PSO在高维复杂优化问题领域的卓越性能都预示这两者的结合趋于必然.但据我们调研,未见PSO算法基于Python语
10、言实现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
11、: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(P
12、bestia-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表示上一代粒子的速度对当代粒子速
13、度的影响,使粒子保持运动的惯性和搜索扩展空间的趋势,较大的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算法Pyth
14、on作为一种解释性语言运行速度较慢,本文选择Numba库通过即时编译技术(JustInTime,JIT)19对程序进行加速.相较于标准PSO算法,PSO-CUDA算法中种群初始化方式不变,将粒子评价、更新个体历史最优解、粒子升级三个部分改用GPU并行计算分别完成.由于全局最优解的更新过程中涉及大量的逻辑判断,虽然426第49 卷西南民族大自然科学版GPU有逻辑运算能力,但GPU不具备CPU的分支预测能力,只能顺序执行逻辑分支,且过程中可能因为Warp Divergence20产生不必要的时间开销,故将更新全局最优解的步骤置于CPU中完成.PSO-CUDA算法流程可概括如下:1)于CPU中完成种
15、群及所需参数初始化;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 BP
16、G,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的逻辑运
17、算能力不及CPU,如何合理为GPU分配计算任务、避免复杂逻辑是算法设计的关键.按照标准PSO算法逻辑,种群中个体升级都需要当前Gbest,但PSO-CUDA中的Gbest更新于CPU中完成、个体升级于GPU中完成,这将导致个体升级过程中不可避免地存在一次数据拷贝.为解决这一问题,PSO-CUDA算法将 Kernel核函数中的粒子升级步骤前置,使当代粒子直接利用上代得到的Gbest进行升级(首次迭代除外),以此减少数据拷贝的时间开销.PSO-CUDA算法中Kernel的流程如下所示.Kernel(粒子升级、评价粒子、更新个体历史最优解)1:Launch threads as the number
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 GPU Python 粒子 优化 算法 研究
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。