基于OpenMP的并行粒子群優化算法研究

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

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

基于OpenMP的并行粒子群優化算法研究

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

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

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

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

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

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

1 粒子群算法

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

1.1 算法原理

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

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

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

1.2 粒子群算法流程

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

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

2 粒子群算法并行化實現

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

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

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

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

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

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

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

3 實驗結果與分析

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

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

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

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

4 結論

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

[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]姜建國，田旻，王向前，等．采用擾動加速因子的自適應粒子群優化算法[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]王金敏，楊維嘉．動態吸引子在布局求解中的應用[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-），男（漢族），教授，博士生導師．

數字出版日期：2015-04-16數字出版網址：http://www.cnki.net/kcms/detail/13.1208.T.20150416.1046.006.html