不同拓扑结构的并行粒子群优化算法如何去实现?

电子说

1.3w人已加入

描述

摘  要: 针对粒子群优化算法的邻域拓扑结构对算法性能有重要影响、PSO算法在CPU上求解最优化问题时计算效率低下这两点,分析了邻域拓扑结构改变时PSO算法的并行特征,实现了环形和星形拓扑结构的PSO算法在统一计算设备架构上的寻优过程。分别在CPU和GPU上用两种PSO算法对7个benchmark测试函数进行求解。程序仿真结果显示,基于CUDA的PSO算法计算效率均大大高于CPU;同时发现,GPU显着地加快了星形结构PSO算法的收敛速度,而对环形结构PSO算法影响不大。

料子群优化PSO(Particle Swarm Optimization)算法最早于1995年由EBERHART博士和KENNEDY博士提出[1],由于实现容易、精度高和收敛快等优点,引起了学术界的重视,并且在实际问题的解决中展示了其优越性。

近年来,针对基本PSO算法易陷入局部极值,求解某些问题时精度不足的缺点[1],研究人员们提出了各种改进算法,包括参数调整[2],改变搜索网络空间[3-4],混合其他算法[5-6]等。目前,PSO算法作为优化工具成功应用于多个领域,如无线传感器网络(WSN)覆盖问题的研究[7]。PSO算法性能对社会网络结构具有强烈的依赖性[1,3-4],邻域拓扑结构的改变对PSO算法的收敛性有重要作用。

求解高维复杂函数时,传统PSO算法因需处理大量数据,致计算效率过低,研究人员基于算法本身特性提出了各种并行PSO算法[8-10],均取得了至少10倍以上的加速比。GPU起初只是负责图形渲染,直到2006年公布了GeForce系列GPU,GPU才开始应用于通用计算[11]。GPU和CPU的协同工作,现已被广泛应用于石油勘探[12]、生物计算[13]等领域。本文借助于CUDA平台,对邻域拓扑结构发生变化时的PSO算法进行了探究,验证了并行计算平台的高效性,同时探索了并行计算平台对星形和环形PSO算法收敛性的影响。

1 标准PSO算法

PSO算法[1]源于对鸟类觅食过程的模拟:将每只鸟看成D维空间中没有质量和体积的微粒,这些微粒以一定速度飞行,速度由个体的飞行经验和群体的飞行经验进行动态调整。

标准PSO算法的速度和位置更新方程如下:

v(t+1)=?棕v(t)+c1×r1×(p(t)-x(t))+c2×r2×(pg(t)-x(t))(1)

x(t+1)=x(t)+v(t+1)(2)

其中,v(t)=(v1,v2,…,vd)为当前微粒在第t代的速度;为惯性权重,文中取?棕=0.5;c1为认知系数;c2为社会系数,通常取c1=c2=2;r1,r2为服从均匀分布的0~1之间的随机数;p(t)=(p1,p2,…,pd)为当前微粒的历史最优位置;x(t)=(x1,x2,…,xd)为当前微粒在第t代的位置;p(t)=(pg1,pg2,…,pgd)为群体历史最优位置。典型的标准PSO算法的寻优流程如图所示。

PSO

2 PSO算法的拓扑结构

为提高PSO算法的性能,参考文献[3-4]提出了不同类型的拓扑结构,包括动态拓扑和静态拓扑。KENNEDY J对在各种静态邻域结构中的PSO算法性能进行了分析[1],认为星型、环型和Von Neumann拓扑适用性最好,并称小邻域的PSO算法在复杂问题上性能较好,大邻域的PSO算法在简单问题上性能更好,在本实验中得到进一步论证。

分别为星形和环形拓扑图,星形PSO算法中所有粒子全部相联,每个粒子都可以同除自己以外的其他粒子通信,以共享整个群体最佳解;环形网络结构中每个粒子跟它的n个邻居通信,每个粒子向邻域内的最优位置靠拢,来更新自己的位置,可见,每个粒子只是共享所在邻域内的最优解,即局部最优,而全局最优流动在整个环形网络中。

除以上两种基本拓扑结构外,还有冯诺依曼型、轮型、金字塔型、四聚类型结构和一些基于这几种结构的改进拓扑[1,3-4],其中普遍认为冯诺依曼结构在解决大多数问题时要优于其他结构[1]。当然,并不存在对所有问题都适用的最好拓扑。

3 CUDA及CUDAC

3.1 CUDA编程模型

统一计算设备架构CUDA(Compute Unified Device Arch-itecture),在CUDA编程模型中,CPU为主机(Host)端,GPU作为协处理器,两者各自拥有独立的存储器和各自的编译器[14-15]。一个完整的CUDA编程模型如图4所示:程序执行始于主机,止于主机。图中Kernel并行处理部分为基于单指令多线程SIMD(Single Instruction Multiple Thread)计算模型,线程被CUDA组织成3个不同的层次:线程(Thread)、线程块(Block)以及线程格(Grid)。

PSO

3.2 CUDA存储器模型

线程在执行指令时,需访问处于不同存储器的数据,而对各类存储器的访问速度差异很大[13]。CUDA存储器分为3层:(1)私有本地存储器(private local memory),容量小,访问速度快;(2)全局存储器(global memory),所有线程都可访问,访问速度慢;(3)共享存储器(shared memory),属于片上存储器,访问速度与寄存器相当,定义共享类型变量时需使用限定符__shared__。

3.3 CUDA C

CUDA C是对C的扩展,为程序员提供了一种用C语言在设备上编写代码的编程方式。主要扩展[14-15]:(1)引入__device__,__host__和__global__3个限定符,限定函数调用和执行的位置;(2)引入4个内置变量,blockIdx,threadIdx,gridDim和blockDim;(3)引入<<<>>>运算符,内含4个参数,主要用于设置线程格和线程块的尺寸;(4)扩展了一些数学函数库,如CURAND[16]。

4 基于CUDA的PSO算法

4.1 PSO算法的并行编程

群体中各粒子只在更新全局最优时互相交换信息,其他步骤均相互独立。获取历史最优时,一个线程对应一个粒子,各线程同时调用适应函数;更新位置和速度时,一个线程对应粒子的每一维;均按线程索引来读取数据并处理。

主机端初始化粒子的位置和速度,将数据从CPU复制到GPU上,在设备上迭代寻优,最后将最优解复制到CPU输出。表1列出了实现各部分功能的函数,获取全局最优值时,星形结构可以通过线程归约比较获取全局最优,环形结构由于多邻域而相对复杂,在后续部分详述。

4.2 环形PSO算法寻优过程

星形PSO算法获取全局最优较为简单,不作分析,环形PSO算法在获取局部最优时,文中设定每个粒子只有左右两个邻居。在编写该部分程序时,设置让相邻线程访问索引间隔为3的共享内存中的数据,这种方法避开了bank冲突,但以时间消耗作为代价。各线程具体负责找出粒子的历史最优值.

找出历史最优值的方式有以下两种情形(其中N为粒子规模):

(1)N%3=0时,各线程按图5所示处理相应的数据,3次并行运行即可得到每个粒子在其邻域内的局部最优。

(2)N%3≠0时,将图5中N令为N-N%3,按情形(1)可以得到0~N-N%3-1号粒子在其邻域内的局部最优,再对余下的1或2个粒子依次找出其邻域内局部最优。

由于环型PSO算法有N个局部最优值,设备上寻优结束后,需将N个局部最优从GPU复制到CPU进行比较,最后输出全局最佳解。

4.3 CUDA程序性能优化

GPU性能虽然出色,但很大程度上受限于算法本身[15]。在CUDA的使用中,数据结构和对内存的访问对GPU性能有极大地影响,有时甚至起决定性作用。文中实验程序对CUDA性能优化,主要考虑了以下4个方面:(1)最大化并行性;(2)优化内存访问以获得最大的带宽;(3)优化指令使用以获得最大指令的吞吐量;(4)线程块和线程数的设置,实验表明当设置线程块数为32,每个块中线程数为256时获得最高效率。

5 结论分析

5.1 计算时间对比

在独立的CPU和CPU+GPU并行计算平台上,分别对以下7个benchmark函数进行了测试,其中D表示粒子的维数,xi的范围表示搜索空间。

(1)Sphere函数

f1(x)=x,|xi|≤15(3)

(2)Ackley函数

f2(x)=20exp-0.2-

expcos(2πoi)+20+e),|xi|≤15(4)

(3)Schwefel函数

f3=418.928×D-xisin(),|xi|≤500(5)

(4)Levy函数

f4=sin2(πyl)+[(yi-1)2×(1+10sin2(πyi+1))]+(yD-1)2(1+sin2(2π2n))   yi=1+,|xi|≤10(6)

(5)Griewank函数

f5+1,|xi|≤600(7)

(6)Rastrigin函数

f6=10cos(2ππi)+10],|xi|≤5.12(8)

(7)Rosenbrock函数

f7=xi+12+(xi-1)2,-5≤xi≤10(9)

星形结构和环形结构PSO算法在CPU和CUDA上的运行时间如表2所示,测试时取粒子数为1 000,粒子维数为50,迭代次数为5 000。表中数据经多次测试,取均值得到。表2显示,相同条件下,GPU和CPU上的环型PSO算法均略慢于星型。还可以看到,函数越复杂,加速比越大。并经多次测试比较发现,迭代次数增加,加速比增大。表3为迭代次数为10 000时的函数f1~f7求解时间。

表4列出了维数50,粒子数为500,迭代次数10 000时,星形和环形PSO算法求解函数f1~f7的时间。对比表3和表4,可知粒子数为500时的加速比明显要低于粒子数为1 000时,对比表2和表4发现,尽管迭代变大,而粒子数较大时加速比越大,说明种群规模对加速比的影响要大于迭代数。这正体现了PSO算法粒子的并行性,粒子规模越大,在GPU上的并行处理越具优势;反而当粒子数较小时,由于并行前后CPU和GPU之间的通信所需时间隐藏被弱化,此时在GPU上运行不占任何优势,有时甚至差于CPU。进一步说明了GPU适用于大规模数据并行运算中。

5.2 收敛性对比

除计算效率极大提升外,GPU还加快了星型PSO算法的收敛速度。图6描绘了两种结构PSO算法在CPU和GPU上求解函数f2的收敛曲线,实验取粒子数500,维数50,迭代次数从0逐渐增大,基于算法本身的随机性,记录最优解数据时对指定的迭代数循环100次,取其平均值。

可见,迭代早期两种结构PSO算法的收敛速度相差不大,而随着迭代增大,星形PSO算法的收敛速度明显加快。实验结果还表明,对于环形PSO算法,GPU并未加快收敛,而对于星形结构,GPU明显加快了算法的收敛速度。其余6个benchmark函数的求解也表明,GPU确实加快了星形PSO算法的收敛速度。

本实验GPU显卡型号为NVIDIA GeForce GT 630M,CUDA计算能力为2.1。图表中仅列出了粒子数和迭代数改变时加速比的变化情况,维数的改变对加速比也有重要影响。PSO算法的这种并行策略,在遗传算法、蚁群算法、文化算法及一些混合算法中具有较强的通用性,可以很大地提高搜索效率。PSO作为一种新兴进化算法,各种研究工作种类繁多,在函数优化、多目标优化、约束优化、算法结构改进、应用工程领域等方面[17]均取得重大成果,而CUDA作为一种新兴计算平台,必将推动PSO算法的发展。

参考文献

[1] KENNEDY J, EBERHART R C. Particle swarm optimiza-tion[C]. Proceedings of IEEE International Conference on Neural Networks, Piscataway, 1995:1942-1948.

[2] 延丽平,曾建潮.具有自适应随机惯性权重的PSO算法[J].计算机工程与设计,2006,27(24):4677-4679,4706.

[3] 杨道平.粒子群算法邻域拓扑结构研究[J].中国高新技术企业评价,2009,(16):36-37.

[4] 姚灿中,杨建梅.基于网络邻域拓扑的粒子群优化算法[J].计算机工程,2010,36(19):18-20.

[5] 王志,胡小兵,何雪海,等.一种新的差分与粒子群算法的混合算法[J].计算机工程与应用,2012,48(6):46-48.

[6] 易文周,张超英,王强,等.基于改进PSO和DE的混合算法[J].计算机工程,2010,36(10):233-235.

[7] 史朝亚,樊春丽.基于PSO算法的无线传感器网络覆盖的研究[D].南京:南京理工大学,2013.

[8] You Zhou, Ying Tan. GPU-based parallel part- icle swarm optimization[J]. Proceedings of IEEE International Conference on Evolutionary Computation, 2009:1493-1500.

[9] LUCAS DE P VERONESE, RENATO A K-ROHLING. Swarm′s flight: accelerating the particles using C-CUDA[C]. Proceedings of IEEE International Conference on Evolutionary Computation,2009:3264-3270.

[10] 蔡勇,李光耀,王琥.基于CUDA的并行粒子群优化算法的设计与实现[J].计算机应用研究,2013,30(8):2415-2418.

[11] 刘金硕,刘天晓,吴慧,等.从图形处理器到基于GPU的通用计算[J].武汉大学学报(理学版),2013,59(2):198-199.

[12] 张兵,赵改善,黄俊,等.地震叠前深度偏移在CUDA上的实现[J].勘探地球物理进展,2008,31(6):427-430.

[13] 余林彬,徐云.基于CUDA的高性能计算研究及生物信息学应用[D].合肥:中国科学技术大学,2009.

[14] NVIDIA. NVIDIA CUDA Programming Guide Version 2.3.1[EB/OL].https://developer.nvidia.com/category/zone/cuda-zone[2007].

[15] 张舒,褚艳利,赵开勇,等.GPU高性能运算之CUDA[M].北京:中国水利水电出版社,2009.

[16] NVIDIA. NVIDIA CUDA CURAND Library[EB/OL]. http://docs.nvidia.com/cuda/curand/index.html[2010].

[17] 倪庆剑,邢汉承,张志政,等.粒子群优化算法研究进展[J].模式识别与人工智能,2007,20(3):350-357.

编辑:jq

打开APP阅读更多精彩内容
声明:本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人,不代表电子发烧友网立场。文章及其配图仅供工程师学习之用,如有内容侵权或者其他违规问题,请联系本站处理。 举报投诉

全部0条评论

快来发表一下你的评论吧 !

×
20
完善资料,
赚取积分