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

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

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

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

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

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

PSO算法[1]源于對鳥類覓食過程的模擬：將每只鳥看成D維空間中沒有質(zhì)量和體積的微粒，這些微粒以一定速度飛行，速度由個體的飛行經(jīng)驗和群體的飛行經(jīng)驗進(jìn)行動態(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為社會系數(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)，包括動態(tài)拓?fù)浜挽o態(tài)拓?fù)?。KENNEDY J對在各種靜態(tài)鄰域結(jié)構(gòu)中的PSO算法性能進(jìn)行了分析[1]，認(rèn)為星型、環(huán)型和Von Neumann拓?fù)溥m用性最好，并稱小鄰域的PSO算法在復(fù)雜問題上性能較好，大鄰域的PSO算法在簡單問題上性能更好，在本實驗中得到進(jìn)一步論證。

分別為星形和環(huán)形拓?fù)鋱D，星形PSO算法中所有粒子全部相聯(lián)，每個粒子都可以同除自己以外的其他粒子通信，以共享整個群體最佳解；環(huán)形網(wǎng)絡(luò)結(jié)構(gòu)中每個粒子跟它的n個鄰居通信，每個粒子向鄰域內(nèi)的最優(yōu)位置靠攏，來更新自己的位置，可見，每個粒子只是共享所在鄰域內(nèi)的最優(yōu)解，即局部最優(yōu)，而全局最優(yōu)流動在整個環(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ù)問題時要優(yōu)于其他結(jié)構(gòu)[1]。當(dāng)然，并不存在對所有問題都適用的最好拓?fù)洹?/p>

3 CUDA及CUDAC

3.1 CUDA編程模型

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

3.2 CUDA存儲器模型

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

3.3 CUDA C

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

4 基于CUDA的PSO算法

4.1 PSO算法的并行編程

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

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

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

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

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

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

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

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

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

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

5 結(jié)論分析

5.1 計算時間對比

在獨立的CPU和CPU+GPU并行計算平臺上，分別對以下7個benchmark函數(shù)進(jìn)行了測試，其中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)行時間如表2所示，測試時取粒子數(shù)為1 000，粒子維數(shù)為50，迭代次數(shù)為5 000。表中數(shù)據(jù)經(jīng)多次測試，取均值得到。表2顯示，相同條件下，GPU和CPU上的環(huán)型PSO算法均略慢于星型。還可以看到，函數(shù)越復(fù)雜，加速比越大。并經(jīng)多次測試比較發(fā)現(xiàn)，迭代次數(shù)增加，加速比增大。表3為迭代次數(shù)為10 000時的函數(shù)f1~f7求解時間。

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

5.2 收斂性對比

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

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

本實驗GPU顯卡型號為NVIDIA GeForce GT 630M，CUDA計算能力為2.1。圖表中僅列出了粒子數(shù)和迭代數(shù)改變時加速比的變化情況，維數(shù)的改變對加速比也有重要影響。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作為一種新興計算平臺，必將推動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ī)工程與設(shè)計，2006，27（24）：4677-4679，4706.

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

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

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

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

[7] 史朝亞，樊春麗.基于PSO算法的無線傳感器網(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è)計與實現(xiàn)[J].計算機(jī)應(yīng)用研究，2013，30（8）：2415-2418.

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

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

[13] 余林彬，徐云.基于CUDA的高性能計算研究及生物信息學(xué)應(yīng)用[D].合肥：中國科學(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] 張舒，褚艷利，趙開勇，等.GPU高性能運(yùn)算之CUDA[M].北京：中國水利水電出版社，2009.

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

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

編輯：jq