基于OpenMP的并行粒子群優(yōu)化算法研究

康軍廣，段國林，王金敏，田永軍

（1.河北工業(yè)大學機械工程學院，天津 300130；2.天津職業(yè)技術(shù)師范大學機械工程學院，天津 300222）

基于OpenMP的并行粒子群優(yōu)化算法研究

康軍廣1，段國林1，王金敏2，田永軍1

（1.河北工業(yè)大學機械工程學院，天津 300130；2.天津職業(yè)技術(shù)師范大學機械工程學院，天津 300222）

針對現(xiàn)有粒子群優(yōu)化算法多采用串行方式執(zhí)行且運行效率較低的問題，提出一種基于OpenMP技術(shù)的并行粒子群優(yōu)化算法．該算法以多核硬件平臺為基礎，利用粒子群算法搜索速度快，易于并行等特點，引入OpenMP技術(shù)，通過將該并行算法應用于布局問題求解并與串行算法相比較，測試結(jié)果表明，該并行算法與串行算法結(jié)果一致，能夠充分利用多核CPU的計算資源，運行效率得到明顯提高．

OpenMP；并行；粒子群；多核CPU

粒子群優(yōu)化算法（Particle Swarm Optim ization，PSO）是一種基于群體智能的啟發(fā)式全局優(yōu)化方法，具有結(jié)構(gòu)簡單、參數(shù)少、收斂速度快、易于實現(xiàn)并行等優(yōu)點，近年來受到學術(shù)界的廣泛關注，目前已應用于函數(shù)優(yōu)化、TSP問題、布局問題、神經(jīng)網(wǎng)絡訓練、工業(yè)系統(tǒng)優(yōu)化與控制、系統(tǒng)辨識等諸多領域[1]．然而粒子群優(yōu)化算法多是基于串行方式執(zhí)行的，不能充分利用現(xiàn)有的多核CPU硬件平臺，造成過多的程序運行等待時間．

隨著多核CPU的普及，目前主流計算機均配置為多核CPU，并配有大容量內(nèi)存．如何讓原有串行執(zhí)行的程序在多核CPU下高效并行執(zhí)行，是目前急需解決的問題．有效解決這個問題的方法之一就是利用多核并行計算技術(shù)，在算法的執(zhí)行過程中，將程序任務下發(fā)給多個處理器核心，讓多個核心同時去處理，并返回最終結(jié)果，有效提高每個處理器核心的利用率．OpenMP是共享內(nèi)存并行程序設計的工業(yè)標準，支持C、C++以及Fortran等編程語言，具有良好的可移植性，適合于共享內(nèi)存的多核計算機，可以方便的通過編譯指導語句將串行程序改造成并行執(zhí)行[2]．本文在分析粒子群算法和OpenMP并行技術(shù)實現(xiàn)細節(jié)的基礎上，實現(xiàn)了基于OpenMP技術(shù)的并行粒子群算法，并將并行粒子群算法應用于矩形布局問題求解，驗證了該并行粒子群算法的可行性和高效性．

1 粒子群算法

粒子群優(yōu)化算法是由美國社會心理學家Kennedy和電氣工程師Eberhart于1995年提出的一種基于群智能的演化計算技術(shù)[3-4]，粒子群優(yōu)化算法通過群體中粒子間的合作與競爭產(chǎn)生的群體智能來指導優(yōu)化搜索．與演化計算相比，PSO算法保留了基于種群的全局搜索策略，它采用的速度—位移模型操作簡單，避免了復雜的遺傳操作．粒子群算法特有的記憶功能，使其可以動態(tài)跟蹤當前的搜索情況，調(diào)整其搜索策略，是一種高效的并行搜索算法．

1.1 算法原理

粒子群優(yōu)化算法采用“群體”與“進化”的概念，依據(jù)個體（微粒）的適應值大小進行操作，粒子群優(yōu)化算法不像其它進化算法那樣對于個體使用進化算子，而是將每個個體看做是在D維搜索空間的一個沒有重量和體積的微粒，并在搜索空間中以一定的速度飛行，該飛行速度隨個體的飛行經(jīng)驗和群體的飛行經(jīng)驗進行動態(tài)調(diào)整[5]．

設Xi=χi1,χi2,,χiDT為微粒i的當前位置；Vi=vi1,vi2,,viDT為微粒i的當前飛行速度；Pi=pi1, pi2,,piDT為微粒i所經(jīng)歷的最好位置，也就是微粒i所經(jīng)歷過的具有最好適應值的位置，稱為個體最好位置．粒子通過跟蹤2個“極值”來更新，第1個“極值”為粒子本身所找到的最好解，稱為個體最優(yōu)，其位置用pbest表示．第2個“極值”為整個粒子群中所找到的最好解，稱為全局最優(yōu)，其位置用gbest表示．粒子群算法的進化方程可描述為：

其中：χkid是粒子i在第k次迭代中第D維的位置，W為慣性權(quán)重，用來控制算法的開發(fā)和探索能力；c1、c2為加速系數(shù)，通常在0～2之間取值，分別調(diào)節(jié)個體向自身最好位置和全局最好位置方向飛行的最大步長；r1、r2為0,1之間的隨機數(shù)，為了減少在進化過程中，微粒離開搜索空間的可能性，vijvmax,vmax．如果問題的搜索空間限定在χmax,χmax內(nèi)，則可設定vmax=kχmax，0.1k1.0．

1.2 粒子群算法流程

本文將粒子群算法用于對矩形布局問題求解過程中定位函數(shù)的優(yōu)化[6]，其中，定位函數(shù)包含多個參數(shù)，每個參數(shù)的取值范圍均為[0,1]，每個粒子位置對應定位函數(shù)中某個參數(shù)的一組取值，通過粒子位置的更新找到種群中粒子的最優(yōu)位置gbest，gbest為滿足定位函數(shù)值最小的粒子位置，即滿足定位函數(shù)要求的參數(shù)最優(yōu)值，具體算法流程如下：

1）初始化粒子群，隨機產(chǎn)生滿足條件的粒子的位置和速度，并確定粒子的pbest和gbest；2）對每個粒子，將它的當前位置與它的pbest進行比較，如果是當前位置更好，則將其作為當前最好位置pbest，否則，pbest保持不變；3）對每個粒子，將它的當前位置和群體中的gbest比較，如果這個粒子的位置更好，則將其設置為當前的gbest，否則，gbest保持不變；4）更新粒子的速度和位置；5）如未達到終止條件，則轉(zhuǎn)步驟2）；6）開始下一輪迭代計算，否則取當前gbest為最優(yōu)解；7）將gbest的值賦值給定位函數(shù)中的各個參數(shù)，確定待布矩形的布入位置．

2 粒子群算法并行化實現(xiàn)

OpenMP的執(zhí)行模型采用fork-join的形式[7]，其中fork創(chuàng)建新線程或者喚醒已有線程，join即多線程的會合．Fork-join執(zhí)行模型在剛開始執(zhí)行的時候，只有一個稱為“主線程”的運行線程存在．主線程在運行過程中，當遇到需要進行并行計算的時候，派生出線程來執(zhí)行并行任務．在并行執(zhí)行的時候，主線程和派生線程共同工作，在并行代碼執(zhí)行結(jié)束后，派生線程退出或者阻塞，不再工作，控制流程回到單獨的主線程中．

粒子群優(yōu)化算法主要包括對種群中所有個體的位置和速度的初始化，選出局部最優(yōu)解和全局最優(yōu)解，通過速度、位置更新公式對所有個體進行更新迭代得到新的位置和速度．無論是個體的初始化，還是個體的位置和速度的更新，都是通過大量循環(huán)迭代實現(xiàn)的，是整個算法運行過程中最耗費時間的部分．循環(huán)并行化是使用OpenMP并行化程序的最重要部分，在OpenMP編程模式下，使用編譯指導語句能將循環(huán)中工作分配到一個線程組中，線程組中的每一個線程分擔循環(huán)中的一部分內(nèi)容，實現(xiàn)整個程序的并行化，種群中粒子位置、速度初始化并行實現(xiàn)如圖1所示．

OpenMP對循環(huán)并行化語句有嚴格的格式限制，循環(huán)變量必須是整數(shù)，而且在循環(huán)開始必須明確循環(huán)變量的初始值，結(jié)束條件和遞增值．而且循環(huán)語句應該是單入口單出口的，在循環(huán)過程中不能出現(xiàn)break、goto語句．由于OpenMP只支持for循環(huán)的任務分擔，需要將原有算法中的do-while循環(huán)改造成for循環(huán)格式，當循環(huán)次數(shù)比較小時，由于創(chuàng)建線程會占用一部分開銷，并行效率并不高，有時可能會因為線程的創(chuàng)建開銷增加程序運行時間，不適合改造成并行執(zhí)行．

圖1 粒子位置、速度初始化Fig.1 Initializationof the individuals'positionsand speeds

由于多線程同時執(zhí)行循環(huán)語句中的代碼，這就會出現(xiàn)數(shù)據(jù)的作用域問題，作用域用來控制某一個變量是否是在各個線程之間共享或者是某一個線程是私有的數(shù)據(jù)的作用域子句用shared來表示一個變量是各個線程之間共享的，用private來表示一個變量是每一個線程私有的，默認的變量作用域是共享的，在粒子群算法循環(huán)并行化之前要明確并行語句塊中哪些變量應該設置為private，哪些設置為shared．

并行粒子群優(yōu)化算法中每代粒子更新操作分散到多個線程同時執(zhí)行，每次循環(huán)需要調(diào)用適應值函數(shù)，計算當前粒子的適應值，然后更新當前粒子的最優(yōu)位置和整個種群的最優(yōu)位置，整個種群的最優(yōu)位置為全局變量，如果多個線程同時更新全局最優(yōu)位置，這將會出現(xiàn)變量的讀寫沖突，通過#pragma omp critical編譯制導語句可以解決該問題，當程序中的某一線程執(zhí)行到#pragma omp critical里面時，要查看有沒有其它線程正在里面執(zhí)行，如果有的話，要等其它線程執(zhí)行完再進去執(zhí)行．這樣就避免了數(shù)據(jù)讀寫沖突問題，但顯而易見，它的執(zhí)行速度會變低，因為可能存在線程等待的情況．粒子位置、速度更新并行程序如下：

圖2 不同迭代次數(shù)下串行和并行運行時間Fig.2 Running time of sequentialand parallelized way

3 實驗結(jié)果與分析

為了驗證算法的有效性，本文將并行粒子群算法用于矩形布局問題求解，并行算法和串行算法進行比較．為了使所得結(jié)果具有可比性，2種算法均運行在同一臺計算機上，計算機配置為Intel Core i7-2600，4G內(nèi)存，操作系統(tǒng)為32位w indows7，軟件為VSStudio 2008．選取同一個矩形布局問題進行測試，通過OpenMP的庫函數(shù)omp-setthreads()動態(tài)設置程序在并行運行過程中創(chuàng)建線程的數(shù)量．在改變種群的迭代次數(shù)和創(chuàng)建的線程數(shù)以后，并行程序運行時間比串行程序明顯降低，如圖2所示，當程序迭代次數(shù)在60次以內(nèi)時，并行運行時間大約在1 s左右，而串行執(zhí)行時間隨著循環(huán)迭代次數(shù)的增加呈直線增長，并行效率非常明顯，但當?shù)螖?shù)大于60次以上并小于500次時，串行運行時間和并行運行時間基本保持相等的間距，隨著迭代次數(shù)增加和線程數(shù)的不斷增加，并行程序運行時間和串行程序運行時間的差距逐漸變小，如圖3所示，當?shù)螖?shù)在1400次時，并行運行時間和串行運行時間基本相等，此時并行效果很差．

圖4為當循環(huán)迭代次數(shù)固定，隨著創(chuàng)建的線程數(shù)的增加，并行程序執(zhí)行時間變化圖．從圖中可以看出，創(chuàng)建的線程數(shù)增多會降低程序運行時間，因為循環(huán)塊中的代碼由更多的線程去同時處理，但創(chuàng)建的線程數(shù)達到循環(huán)規(guī)模一般以后，程序運行時間不再改善，維持在一個值附近波動，出現(xiàn)這種結(jié)果的原因是過多的創(chuàng)建線程會導致大量系統(tǒng)時間開銷，線程之間數(shù)據(jù)的訪問也會占用額外開銷，從而會抵消程序的并行效率，在將串行程序改造成并行方式時要仔細分析程序中每次循環(huán)的計算規(guī)模和PC機的性能，靈活的設置創(chuàng)建的線程數(shù)，充分利用多核CPU的計算能力．

圖3 迭代次數(shù)為500次以上串行并行運行時間Fig.3 Running tim eofabove500 iterations

圖4 不同迭代次數(shù)和不同線程數(shù)下程序運行時間Fig.4 Running time ofdifferent iterationsand threads

4 結(jié)論

本文針對現(xiàn)有粒子群優(yōu)化算法多采用串行方式執(zhí)行且運行效率較低的問題，對串行粒子群算法進行分析，提出了一種基于OpenMP的并行粒子群優(yōu)化算法．通過將該并行算法應用于矩形布局問題求解，并與串行算法相比較．實驗結(jié)果表明，本文提出的并行粒子群算法合理可行，并行算法充分利用現(xiàn)有計算機多核處理器的資源，提高了求解矩形布局問題的速度，為求解大規(guī)模布局問題提供了參考．

[1]Bratton D，Kennedy J．Definingastandard forparticlesw arm optim ization[C]//Proceedingsof the IEEESwarm IntelligenceSymposium．Honolulu，HI，2007：120-127．

[2]Barbara C，Gabriele J．UsingOpenMP[M]．London：TheM IT Press，2007．

[3]Kennedy J，EberhartR．Particleswarm optimization[C]//IEEE InternationalConferenceon NeuralNetwork-s，Perth，Australia，1995：1942-1948．

[4]姜建國，田旻，王向前，等．采用擾動加速因子的自適應粒子群優(yōu)化算法[J]．西安電子科技大學學報，2012，39（4）：74-80．

[5]Qi Yang，Wang Jinmin．The particle swarm optimization algorithm for solving rectangular packing probl em[J]．Advanced materials research，2011，186：479-483．

[6]王金敏，楊維嘉．動態(tài)吸引子在布局求解中的應用[J]．計算機輔助設計與圖形學學報，2005，17（8）：1725-1730．

[7]盛楠，廖成，張青洪，等．基于OpenMP的多輻射源二維電波傳播預測方法[J]．電波科學學報，2013，28（4）：611-615．

[責任編輯 楊屹]

Research on parallelparticle swarm optimization algorithm based on OpenMP

KANG Junguan1，DUANGuolin1，WANG Jinmin2，TIAN Yongjun1

(1.SchoolofMechanical Engineering,HebeiUniversity of Technology,Tianjin 300130,China;2.SchoolofM echanicalEngineering, Tianjin University of Technology and Education,Tianjin 300222,China)

Concerning the low performanceand executing in sequentialway ofmostparticle swarm optim ization algorithms,a parallelalgorithm based on OpenMPwasproposed.By introducingOpenMPtechnology,thealgorithm w ith the advantages of searching fastand easy to be parallelized of PSO isbased onmulti-core hardware platform.The parallel particleswarm algorithm is tested by solving the rectangular layoutinstance and iscomparedw ith thesequentialway.The experimental resultsw egotare the same asby choosing the sequentialway,also the results show that the proposed algorithm hasim proved the efficiency insolving the rectangular layoutproblem bymaking fulluse of themulticore com puting resources.

OpenMP;parallel;PSO;multi-coreCPU

TP301.6

A

1007-2373(2015)02-0034-04

10.14081/j.cnki.hgdxb.2015.02.008

2014-07-11

國家自然科學基金（60975046）

康軍廣（1981-），男（漢族），博士生．通訊作者：段國林（1963-），男（漢族），教授，博士生導師．

數(shù)字出版日期：2015-04-16數(shù)字出版網(wǎng)址：http://www.cnki.net/kcms/detail/13.1208.T.20150416.1046.006.html