不同拓?fù)浣Y(jié)構(gòu)的并行粒子群優(yōu)化算法如何去實(shí)現(xiàn)？

摘 要： 針對(duì)粒子群優(yōu)化算法的鄰域拓?fù)浣Y(jié)構(gòu)對(duì)算法性能有重要影響、PSO算法在CPU上求解最優(yōu)化問(wèn)題時(shí)計(jì)算效率低下這兩點(diǎn)，分析了鄰域拓?fù)浣Y(jié)構(gòu)改變時(shí)PSO算法的并行特征，實(shí)現(xiàn)了環(huán)形和星形拓?fù)浣Y(jié)構(gòu)的PSO算法在統(tǒng)一計(jì)算設(shè)備架構(gòu)上的尋優(yōu)過(guò)程。分別在CPU和GPU上用兩種PSO算法對(duì)7個(gè)benchmark測(cè)試函數(shù)進(jìn)行求解。程序仿真結(jié)果顯示，基于CUDA的PSO算法計(jì)算效率均大大高于CPU；同時(shí)發(fā)現(xiàn)，GPU顯著地加快了星形結(jié)構(gòu)PSO算法的收斂速度，而對(duì)環(huán)形結(jié)構(gòu)PSO算法影響不大。

料子群優(yōu)化PSO（Particle Swarm Optimization）算法最早于1995年由EBERHART博士和KENNEDY博士提出[1]，由于實(shí)現(xiàn)容易、精度高和收斂快等優(yōu)點(diǎn)，引起了學(xué)術(shù)界的重視，并且在實(shí)際問(wèn)題的解決中展示了其優(yōu)越性。

近年來(lái)，針對(duì)基本PSO算法易陷入局部極值，求解某些問(wèn)題時(shí)精度不足的缺點(diǎn)[1]，研究人員們提出了各種改進(jìn)算法，包括參數(shù)調(diào)整[2]，改變搜索網(wǎng)絡(luò)空間[3-4]，混合其他算法[5-6]等。目前，PSO算法作為優(yōu)化工具成功應(yīng)用于多個(gè)領(lǐng)域，如無(wú)線傳感器網(wǎng)絡(luò)（WSN）覆蓋問(wèn)題的研究[7]。PSO算法性能對(duì)社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)具有強(qiáng)烈的依賴性[1，3-4]，鄰域拓?fù)浣Y(jié)構(gòu)的改變對(duì)PSO算法的收斂性有重要作用。

求解高維復(fù)雜函數(shù)時(shí)，傳統(tǒng)PSO算法因需處理大量數(shù)據(jù)，致計(jì)算效率過(guò)低，研究人員基于算法本身特性提出了各種并行PSO算法[8-10]，均取得了至少10倍以上的加速比。GPU起初只是負(fù)責(zé)圖形渲染，直到2006年公布了GeForce系列GPU，GPU才開(kāi)始應(yīng)用于通用計(jì)算[11]。GPU和CPU的協(xié)同工作，現(xiàn)已被廣泛應(yīng)用于石油勘探[12]、生物計(jì)算[13]等領(lǐng)域。本文借助于CUDA平臺(tái)，對(duì)鄰域拓?fù)浣Y(jié)構(gòu)發(fā)生變化時(shí)的PSO算法進(jìn)行了探究，驗(yàn)證了并行計(jì)算平臺(tái)的高效性，同時(shí)探索了并行計(jì)算平臺(tái)對(duì)星形和環(huán)形PSO算法收斂性的影響。

1 標(biāo)準(zhǔn)PSO算法

PSO算法[1]源于對(duì)鳥(niǎo)類覓食過(guò)程的模擬：將每只鳥(niǎo)看成D維空間中沒(méi)有質(zhì)量和體積的微粒，這些微粒以一定速度飛行，速度由個(gè)體的飛行經(jīng)驗(yàn)和群體的飛行經(jīng)驗(yàn)進(jìn)行動(dòng)態(tài)調(diào)整。

標(biāo)準(zhǔn)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）為當(dāng)前微粒在第t代的速度；為慣性權(quán)重，文中取?棕=0.5；c1為認(rèn)知系數(shù)；c2為社會(huì)系數(shù)，通常取c1=c2=2；r1，r2為服從均勻分布的0~1之間的隨機(jī)數(shù)；p（t）=（p1，p2，…，pd）為當(dāng)前微粒的歷史最優(yōu)位置；x（t）=（x1，x2，…，xd）為當(dāng)前微粒在第t代的位置；p（t）=（pg1，pg2，…，pgd）為群體歷史最優(yōu)位置。典型的標(biāo)準(zhǔn)PSO算法的尋優(yōu)流程如圖所示。

2 PSO算法的拓?fù)浣Y(jié)構(gòu)

為提高PSO算法的性能，參考文獻(xiàn)[3-4]提出了不同類型的拓?fù)浣Y(jié)構(gòu)，包括動(dòng)態(tài)拓?fù)浜挽o態(tài)拓?fù)?。KENNEDY J對(duì)在各種靜態(tài)鄰域結(jié)構(gòu)中的PSO算法性能進(jìn)行了分析[1]，認(rèn)為星型、環(huán)型和Von Neumann拓?fù)溥m用性最好，并稱小鄰域的PSO算法在復(fù)雜問(wèn)題上性能較好，大鄰域的PSO算法在簡(jiǎn)單問(wèn)題上性能更好，在本實(shí)驗(yàn)中得到進(jìn)一步論證。

分別為星形和環(huán)形拓?fù)鋱D，星形PSO算法中所有粒子全部相聯(lián)，每個(gè)粒子都可以同除自己以外的其他粒子通信，以共享整個(gè)群體最佳解；環(huán)形網(wǎng)絡(luò)結(jié)構(gòu)中每個(gè)粒子跟它的n個(gè)鄰居通信，每個(gè)粒子向鄰域內(nèi)的最優(yōu)位置靠攏，來(lái)更新自己的位置，可見(jiàn)，每個(gè)粒子只是共享所在鄰域內(nèi)的最優(yōu)解，即局部最優(yōu)，而全局最優(yōu)流動(dòng)在整個(gè)環(huán)形網(wǎng)絡(luò)中。

除以上兩種基本拓?fù)浣Y(jié)構(gòu)外，還有馮諾依曼型、輪型、金字塔型、四聚類型結(jié)構(gòu)和一些基于這幾種結(jié)構(gòu)的改進(jìn)拓?fù)鋄1，3-4]，其中普遍認(rèn)為馮諾依曼結(jié)構(gòu)在解決大多數(shù)問(wèn)題時(shí)要優(yōu)于其他結(jié)構(gòu)[1]。當(dāng)然，并不存在對(duì)所有問(wèn)題都適用的最好拓?fù)洹?/p>

3 CUDA及CUDAC

3.1 CUDA編程模型

統(tǒng)一計(jì)算設(shè)備架構(gòu)CUDA（Compute Unified Device Arch-itecture），在CUDA編程模型中，CPU為主機(jī)（Host）端，GPU作為協(xié)處理器，兩者各自擁有獨(dú)立的存儲(chǔ)器和各自的編譯器[14-15]。一個(gè)完整的CUDA編程模型如圖4所示：程序執(zhí)行始于主機(jī)，止于主機(jī)。圖中Kernel并行處理部分為基于單指令多線程SIMD（Single Instruction Multiple Thread）計(jì)算模型，線程被CUDA組織成3個(gè)不同的層次：線程（Thread）、線程塊（Block）以及線程格（Grid）。

3.2 CUDA存儲(chǔ)器模型

線程在執(zhí)行指令時(shí)，需訪問(wèn)處于不同存儲(chǔ)器的數(shù)據(jù)，而對(duì)各類存儲(chǔ)器的訪問(wèn)速度差異很大[13]。CUDA存儲(chǔ)器分為3層：（1）私有本地存儲(chǔ)器（private local memory），容量小，訪問(wèn)速度快；（2）全局存儲(chǔ)器（global memory），所有線程都可訪問(wèn)，訪問(wèn)速度慢；（3）共享存儲(chǔ)器（shared memory），屬于片上存儲(chǔ)器，訪問(wèn)速度與寄存器相當(dāng)，定義共享類型變量時(shí)需使用限定符__shared__。

3.3 CUDA C

CUDA C是對(duì)C的擴(kuò)展，為程序員提供了一種用C語(yǔ)言在設(shè)備上編寫(xiě)代碼的編程方式。主要擴(kuò)展[14-15]：（1）引入__device__，__host__和__global__3個(gè)限定符，限定函數(shù)調(diào)用和執(zhí)行的位置；（2）引入4個(gè)內(nèi)置變量，blockIdx，threadIdx，gridDim和blockDim；（3）引入<<<>>>運(yùn)算符，內(nèi)含4個(gè)參數(shù)，主要用于設(shè)置線程格和線程塊的尺寸；（4）擴(kuò)展了一些數(shù)學(xué)函數(shù)庫(kù)，如CURAND[16]。

4 基于CUDA的PSO算法

4.1 PSO算法的并行編程

群體中各粒子只在更新全局最優(yōu)時(shí)互相交換信息，其他步驟均相互獨(dú)立。獲取歷史最優(yōu)時(shí)，一個(gè)線程對(duì)應(yīng)一個(gè)粒子，各線程同時(shí)調(diào)用適應(yīng)函數(shù)；更新位置和速度時(shí)，一個(gè)線程對(duì)應(yīng)粒子的每一維；均按線程索引來(lái)讀取數(shù)據(jù)并處理。

主機(jī)端初始化粒子的位置和速度，將數(shù)據(jù)從CPU復(fù)制到GPU上，在設(shè)備上迭代尋優(yōu)，最后將最優(yōu)解復(fù)制到CPU輸出。表1列出了實(shí)現(xiàn)各部分功能的函數(shù)，獲取全局最優(yōu)值時(shí)，星形結(jié)構(gòu)可以通過(guò)線程歸約比較獲取全局最優(yōu)，環(huán)形結(jié)構(gòu)由于多鄰域而相對(duì)復(fù)雜，在后續(xù)部分詳述。

4.2 環(huán)形PSO算法尋優(yōu)過(guò)程

星形PSO算法獲取全局最優(yōu)較為簡(jiǎn)單，不作分析，環(huán)形PSO算法在獲取局部最優(yōu)時(shí)，文中設(shè)定每個(gè)粒子只有左右兩個(gè)鄰居。在編寫(xiě)該部分程序時(shí)，設(shè)置讓相鄰線程訪問(wèn)索引間隔為3的共享內(nèi)存中的數(shù)據(jù)，這種方法避開(kāi)了bank沖突，但以時(shí)間消耗作為代價(jià)。各線程具體負(fù)責(zé)找出粒子的歷史最優(yōu)值.

找出歷史最優(yōu)值的方式有以下兩種情形（其中N為粒子規(guī)模）：

（1）N%3=0時(shí)，各線程按圖5所示處理相應(yīng)的數(shù)據(jù)，3次并行運(yùn)行即可得到每個(gè)粒子在其鄰域內(nèi)的局部最優(yōu)。

（2）N%3≠0時(shí)，將圖5中N令為N-N%3，按情形（1）可以得到0~N-N%3-1號(hào)粒子在其鄰域內(nèi)的局部最優(yōu)，再對(duì)余下的1或2個(gè)粒子依次找出其鄰域內(nèi)局部最優(yōu)。

由于環(huán)型PSO算法有N個(gè)局部最優(yōu)值，設(shè)備上尋優(yōu)結(jié)束后，需將N個(gè)局部最優(yōu)從GPU復(fù)制到CPU進(jìn)行比較，最后輸出全局最佳解。

4.3 CUDA程序性能優(yōu)化

GPU性能雖然出色，但很大程度上受限于算法本身[15]。在CUDA的使用中，數(shù)據(jù)結(jié)構(gòu)和對(duì)內(nèi)存的訪問(wèn)對(duì)GPU性能有極大地影響，有時(shí)甚至起決定性作用。文中實(shí)驗(yàn)程序?qū)UDA性能優(yōu)化，主要考慮了以下4個(gè)方面：（1）最大化并行性；（2）優(yōu)化內(nèi)存訪問(wèn)以獲得最大的帶寬；（3）優(yōu)化指令使用以獲得最大指令的吞吐量；（4）線程塊和線程數(shù)的設(shè)置，實(shí)驗(yàn)表明當(dāng)設(shè)置線程塊數(shù)為32，每個(gè)塊中線程數(shù)為256時(shí)獲得最高效率。

5 結(jié)論分析

5.1 計(jì)算時(shí)間對(duì)比

在獨(dú)立的CPU和CPU+GPU并行計(jì)算平臺(tái)上，分別對(duì)以下7個(gè)benchmark函數(shù)進(jìn)行了測(cè)試，其中D表示粒子的維數(shù)，xi的范圍表示搜索空間。

（1）Sphere函數(shù)

f1（x）=x，|xi|≤15（3）

（2）Ackley函數(shù)

f2（x）=20exp-0.2-

expcos（2πoi）+20+e），|xi|≤15（4）

（3）Schwefel函數(shù)

f3=418.928×D-xisin（），|xi|≤500（5）

（4）Levy函數(shù)

f4=sin2（πyl）+[（yi-1）2×（1+10sin2（πyi+1））]+（yD-1）2（1+sin2（2π2n）） yi=1+，|xi|≤10（6）

（5）Griewank函數(shù)

f5+1，|xi|≤600（7）

（6）Rastrigin函數(shù)

f6=10cos（2ππi）+10]，|xi|≤5.12（8）

（7）Rosenbrock函數(shù)

f7=xi+12+（xi-1）2，-5≤xi≤10（9）

星形結(jié)構(gòu)和環(huán)形結(jié)構(gòu)PSO算法在CPU和CUDA上的運(yùn)行時(shí)間如表2所示，測(cè)試時(shí)取粒子數(shù)為1 000，粒子維數(shù)為50，迭代次數(shù)為5 000。表中數(shù)據(jù)經(jīng)多次測(cè)試，取均值得到。表2顯示，相同條件下，GPU和CPU上的環(huán)型PSO算法均略慢于星型。還可以看到，函數(shù)越復(fù)雜，加速比越大。并經(jīng)多次測(cè)試比較發(fā)現(xiàn)，迭代次數(shù)增加，加速比增大。表3為迭代次數(shù)為10 000時(shí)的函數(shù)f1~f7求解時(shí)間。

表4列出了維數(shù)50，粒子數(shù)為500，迭代次數(shù)10 000時(shí)，星形和環(huán)形PSO算法求解函數(shù)f1~f7的時(shí)間。對(duì)比表3和表4，可知粒子數(shù)為500時(shí)的加速比明顯要低于粒子數(shù)為1 000時(shí)，對(duì)比表2和表4發(fā)現(xiàn)，盡管迭代變大，而粒子數(shù)較大時(shí)加速比越大，說(shuō)明種群規(guī)模對(duì)加速比的影響要大于迭代數(shù)。這正體現(xiàn)了PSO算法粒子的并行性，粒子規(guī)模越大，在GPU上的并行處理越具優(yōu)勢(shì)；反而當(dāng)粒子數(shù)較小時(shí)，由于并行前后CPU和GPU之間的通信所需時(shí)間隱藏被弱化，此時(shí)在GPU上運(yùn)行不占任何優(yōu)勢(shì)，有時(shí)甚至差于CPU。進(jìn)一步說(shuō)明了GPU適用于大規(guī)模數(shù)據(jù)并行運(yùn)算中。

5.2 收斂性對(duì)比

除計(jì)算效率極大提升外，GPU還加快了星型PSO算法的收斂速度。圖6描繪了兩種結(jié)構(gòu)PSO算法在CPU和GPU上求解函數(shù)f2的收斂曲線，實(shí)驗(yàn)取粒子數(shù)500，維數(shù)50，迭代次數(shù)從0逐漸增大，基于算法本身的隨機(jī)性，記錄最優(yōu)解數(shù)據(jù)時(shí)對(duì)指定的迭代數(shù)循環(huán)100次，取其平均值。

可見(jiàn)，迭代早期兩種結(jié)構(gòu)PSO算法的收斂速度相差不大，而隨著迭代增大，星形PSO算法的收斂速度明顯加快。實(shí)驗(yàn)結(jié)果還表明，對(duì)于環(huán)形PSO算法，GPU并未加快收斂，而對(duì)于星形結(jié)構(gòu)，GPU明顯加快了算法的收斂速度。其余6個(gè)benchmark函數(shù)的求解也表明，GPU確實(shí)加快了星形PSO算法的收斂速度。

本實(shí)驗(yàn)GPU顯卡型號(hào)為NVIDIA GeForce GT 630M，CUDA計(jì)算能力為2.1。圖表中僅列出了粒子數(shù)和迭代數(shù)改變時(shí)加速比的變化情況，維數(shù)的改變對(duì)加速比也有重要影響。PSO算法的這種并行策略，在遺傳算法、蟻群算法、文化算法及一些混合算法中具有較強(qiáng)的通用性，可以很大地提高搜索效率。PSO作為一種新興進(jìn)化算法，各種研究工作種類繁多，在函數(shù)優(yōu)化、多目標(biāo)優(yōu)化、約束優(yōu)化、算法結(jié)構(gòu)改進(jìn)、應(yīng)用工程領(lǐng)域等方面[17]均取得重大成果，而CUDA作為一種新興計(jì)算平臺(tái)，必將推動(dòng)PSO算法的發(fā)展。

參考文獻(xiàn)

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

[2] 延麗平，曾建潮.具有自適應(yīng)隨機(jī)慣性權(quán)重的PSO算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2006，27（24）：4677-4679，4706.

[3] 楊道平.粒子群算法鄰域拓?fù)浣Y(jié)構(gòu)研究[J].中國(guó)高新技術(shù)企業(yè)評(píng)價(jià)，2009，（16）：36-37.

[4] 姚燦中，楊建梅.基于網(wǎng)絡(luò)鄰域拓?fù)涞牧Ｗ尤簝?yōu)化算法[J].計(jì)算機(jī)工程，2010，36（19）：18-20.

[5] 王志，胡小兵，何雪海，等.一種新的差分與粒子群算法的混合算法[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（6）：46-48.

[6] 易文周，張超英，王強(qiáng)，等.基于改進(jìn)PSO和DE的混合算法[J].計(jì)算機(jī)工程，2010，36（10）：233-235.

[7] 史朝亞，樊春麗.基于PSO算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋的研究[D].南京：南京理工大學(xué)，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的并行粒子群優(yōu)化算法的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用研究，2013，30（8）：2415-2418.

[11] 劉金碩，劉天曉，吳慧，等.從圖形處理器到基于GPU的通用計(jì)算[J].武漢大學(xué)學(xué)報(bào)（理學(xué)版），2013，59（2）：198-199.

[12] 張兵，趙改善，黃俊，等.地震疊前深度偏移在CUDA上的實(shí)現(xiàn)[J].勘探地球物理進(jìn)展，2008，31（6）：427-430.

[13] 余林彬，徐云.基于CUDA的高性能計(jì)算研究及生物信息學(xué)應(yīng)用[D].合肥：中國(guó)科學(xué)技術(shù)大學(xué)，2009.

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

[15] 張舒，褚艷利，趙開(kāi)勇，等.GPU高性能運(yùn)算之CUDA[M].北京：中國(guó)水利水電出版社，2009.

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

[17] 倪慶劍，邢漢承，張志政，等.粒子群優(yōu)化算法研究進(jìn)展[J].模式識(shí)別與人工智能，2007，20（3）：350-357.

編輯：jq