梅 凱，火久元，常扣扣

(蘭州交通大學 電子與信息工程學院，甘肅 蘭州 730070)

并行人工蜂群算法研究

梅 凱，火久元，?？劭?/p>

(蘭州交通大學 電子與信息工程學院，甘肅 蘭州 730070)

針對人工蜂群算法在處理高維度問題時收斂速度慢的問題，利用OpenMP多線程技術(shù)和規(guī)約機制，并根據(jù)已改進的觀察蜂來選擇雇傭蜂的方式，提出了基于OpenMP的并行人工蜂群算法(PCABC)。仿真實驗分別在問題維度為100和200下進行來評估算法性能，在4個邏輯處理器環(huán)境下，基于靜態(tài)調(diào)度的并行人工蜂群算法的加速比最高可以達到3.95，效率可達98.65%。實驗結(jié)果表明，PCABC并行人工蜂群算法在處理高維度復(fù)雜函數(shù)時，收斂速度和算法運行時間都有較大的提升。

人工蜂群算法；人工蜂群算法改進；群體智能；并行化；OpenMP并行處理

人工蜂群算法[1]是一種新興的群智能優(yōu)化算法，由土耳其學者Karaboga在2005年提出，它具有設(shè)置參數(shù)少、易于實現(xiàn)、計算簡單等優(yōu)點，特別適合工程應(yīng)用[2]。文獻[3]將人工蜂群算法與其他其它群智能算法(遺傳算法[4]、粒子群算法[5]等)進行了比較，證明人工蜂群算法的性能要接近甚至優(yōu)于其他算法。文獻[6]將人工蜂群算法進行了改進并應(yīng)用到語音識別模型中，識別結(jié)果顯示了人工蜂群算法及其改進的人工蜂群算法具有良好的性能。文獻[7]通過引入基于引導(dǎo)素的化學通信方式，提出了一種基于引導(dǎo)素更新和擴散機制的人工蜂群算法，并將改進后的算法應(yīng)用在0-1多維背包問題上。文獻[8]將人工蜂群算法做了改進并應(yīng)用到人工神經(jīng)網(wǎng)絡(luò)中，優(yōu)化了網(wǎng)絡(luò)的均方誤差函數(shù)。但是標準的人工蜂群算法在解決高維函數(shù)優(yōu)化時，收斂速度較慢，算法運行時間較長。為此，本文經(jīng)過深入研究，并結(jié)合文獻[9]中已改進的觀察蜂來選擇雇傭蜂的方式，提出了并行人工蜂群算法(PCABC)算法，很好地解決了這一問題。

1 人工蜂群算法原理

在人工蜂群算法中，蜜源被抽象成待優(yōu)化問題的解，蜜源的收益率(蜜源濃度、離蜂巢的距離等)越好，表示解的質(zhì)量越好。蜜蜂被分為3種類型：雇傭蜂、觀察蜂和偵查蜂。進化迭代主要由這3種蜜蜂完成：(1)雇傭蜂在其記憶的花蜜源附近進行局部隨機搜索，同時將蜜源信息傳遞給觀察蜂；(2)觀察蜂從中選擇較優(yōu)的蜜源，然后在這些蜜源周圍做進一步的搜索；(3)偵察蜂對長期得不到更新的蜜源進行更新。

ABC算法的具體步驟如下：

(1)算法初始化：算法在給定的取值范圍內(nèi)按照式(1)隨機產(chǎn)生n個食物源信息

xij=r·(maxj-minj)+minj

(1)

式中，r為(0,1)之間的隨機數(shù)，maxj和minj為第j維取值的上限和下限；

(2)計算每個食物源的適應(yīng)度值；

(3)雇傭蜂更新食物源：雇傭蜂在食物源附近按照式(2)搜索新蜜源，比較新舊食物源的優(yōu)劣，若新食物源優(yōu)于舊食物源，則用新的食物源信息覆蓋舊食物源信息，否則保留舊的食物源，局部尋優(yōu)次數(shù)加1

(2)

其中i≠j，r為[-1,1]之間的隨機數(shù)；

(4)觀察蜂更新食物源：觀察蜂根據(jù)雇傭蜂的舞蹈信息，按照輪盤賭方式選擇食物源，并在其附近按式(2)搜索新蜜源。并根據(jù)貪婪選擇的方式確定保留的蜜源。若蜜源沒有被更新，則局部尋優(yōu)次數(shù)加1。觀察蜂選擇蜜源的概率按照式(3)進行計算

(3)

(5)偵察蜂更新食物源：拋棄停滯次數(shù)達到 的食物源，并按照式(1)在給定的取值范圍內(nèi)隨機生成新的食物源；參數(shù) 的作用是使長期得不到更新的引領(lǐng)蜂獲取重生[10]；

(6)達到最大循環(huán)次數(shù)：判斷算法是否達到算法預(yù)定的最大循環(huán)次數(shù)MaxCycle，是則算法結(jié)束，否則轉(zhuǎn)步驟(3)進行下一次迭代。

2 并行人工蜂群算法

2.1 人工蜂群算法并行性分析

群體智能算法是基于種群行為對給定的目標進行尋優(yōu)的啟發(fā)式搜索方法，其尋優(yōu)過程體現(xiàn)了隨機、并行和分布式等特點[11]，所以群體智能算法適合做并行化計算。人工蜂群算法作為一種群體智能算法，具有天然的并行性?？梢栽O(shè)想，在真正的大自然中，所有的蜜蜂進行花蜜源搜索的時候，都是各自完成各自范圍的搜索任務(wù)，獨立地把花蜜源的信息帶到蜂巢，這是明顯的并行性特征。同樣，當蜜蜂將自己的信息帶回蜂巢進行信息共享的時候，其他的蜜蜂也沒有因此而停止對各自蜜源的搜索，這也是天然并行性的體現(xiàn)[12]?？梢哉J為根據(jù)蜂群采蜜行為設(shè)計的人工蜂群算法也有并行性。圖1所示為蜜蜂采蜜過程的示意圖。

圖1 蜜蜂采蜜過程

2.2 OpenMP

按存儲方式對并行計算機進行分類[13]，并行計算機可以簡單分為共享式內(nèi)存和分布式內(nèi)存。共享內(nèi)存就是多個核心共享一個內(nèi)存，一般的大型計算機結(jié)合分布式內(nèi)存和共享內(nèi)存結(jié)構(gòu)，在每個計算節(jié)點內(nèi)是共享內(nèi)存，節(jié)點間是分布式內(nèi)存，如圖2所示。

圖2 按存儲方式對并行計算機進行分類

OpenMP(Open Multi-Processing)是一種基于共享內(nèi)存編程模型的并行化技術(shù)，它基于編譯制導(dǎo)，具有簡單、移植性好、可擴展性高以及支持增量并行化開發(fā)等優(yōu)點，已經(jīng)成為共享存儲系統(tǒng)中的并行編程標準。

1.2.6 疼痛護理：對于患者術(shù)后出現(xiàn)疼痛的情況，若患者屬于輕度疼痛，囑患者使用呼吸方法進行肢體放松的訓練：呼吸時深而慢，呼吸頻次控制在10次/min，每次進行15 min左右的鍛煉。或應(yīng)用音樂療法，囑患者聽輕快舒緩的音樂，以患者術(shù)后疼痛。若患者疼痛劇烈，根據(jù)實際情況，遵醫(yī)囑按時使用鎮(zhèn)痛藥物。

OpenMP有3大組成要素：環(huán)境變量、編譯制導(dǎo)指令、API函數(shù)。實驗中，主要設(shè)置兩個環(huán)境變量的值：OMP_NUM_THREADS和OMP_SCHEDULE。OMP_NUM_THREADS環(huán)境變量用于設(shè)置并行域中的線程個數(shù)，本文將其設(shè)為omp_get_num_procs()函數(shù)的返回值。omp_get_num_procs()函數(shù)的作用是返回系統(tǒng)中處理器的個數(shù)。本文所做實驗中，omp_get_num_procs()函數(shù)的返回值為4。在OpenMP中，OMP_SCHEDULE環(huán)境變量對應(yīng)3種循環(huán)并行化調(diào)度類型：靜態(tài)調(diào)度、動態(tài)調(diào)度和指導(dǎo)調(diào)度[14]，size參數(shù)為3種調(diào)度類型的可選參數(shù)。

2.3 并行人工蜂群算法具體實現(xiàn)

實驗考慮到OpenMP特性和實驗環(huán)境，采用不改變蜂群算法基本結(jié)構(gòu)，保持只有一個種群的主從式并行模型，耗時多的計算適應(yīng)度函數(shù)部分[15-16]采用多線程并行執(zhí)行。

本文設(shè)計的并行人工蜂群算法(PCABC)的流程圖如圖4所示，主要包括以下步驟：

圖3 并行人工蜂群算法示意圖

(1)算法初始化：主線程完成算法的初始化，初始化食物源個數(shù)FN，最大迭代次數(shù)MaxCycle，最大局部探優(yōu)次數(shù)Limit，優(yōu)化空間維度D，在給定的取值范圍內(nèi)按照式(1)隨機產(chǎn)生FN個食物源信息；

(2)計算每個食物源的適應(yīng)度值：算法進入并行區(qū)，并行計算每個食物源的適應(yīng)度值，本文采用4個線程并行計算，并使用OpenMP規(guī)約機制[14]對并行結(jié)果進行匯總，計算完成后，算法退出并行，回到主線程繼續(xù)執(zhí)行步驟(3)；

(4)觀察蜂更新食物源[9]：觀察蜂根據(jù)雇傭蜂跳的“搖擺舞”信息，按照輪盤賭方式選擇食物源，并在其附近按式(4)搜索新蜜源。算法進入并行區(qū)，并行計算新蜜源的適應(yīng)度值，并使用OpenMP規(guī)約機制對并行結(jié)果進行匯總，計算完成后，算法退出并行，回到主線程中，根據(jù)貪婪選擇方法確定保留的食物源

(4)

(5)偵查蜂更新食物源：主線程拋棄停滯次數(shù)達到Limit的食物源信息，并按照式(1)在給定的取值范圍內(nèi)隨機生成新的食物源；

(6)達到最大循環(huán)次數(shù)：主線程判斷算法是否達到預(yù)定的最大循環(huán)次數(shù)MaxCycle，是則算法結(jié)束，否則轉(zhuǎn)步驟(3)進行下一次迭代。

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

3.1 實驗平臺及參數(shù)

實驗在Inter(R) Core(TM) i3CPU M 370、主頻2.4 GHz，內(nèi)存4 GB，4個邏輯處理器的個人電腦上進行，操作系統(tǒng)是Windows 10，基于Visual Studio 2010編程工具，C++語言實現(xiàn)，采用OpenMP多線程并行編程技術(shù)。本文將已改進的觀察蜂來選擇雇傭蜂的人工蜂群算法記為CABC，標準人工蜂群算法的并行化算法記為PABC，將并行的CABC算法記為PCABC。

仿真實驗中，蜜蜂種群大小SN=80，食物源個數(shù)FN=SN/2，問題維數(shù)分別取D=100和D=200，最大循環(huán)次數(shù)MaxCycle=10 000，最大局部尋優(yōu)次數(shù)Limit取值按公式0.25×NP×D[17]計算，算法獨立運行30次，選取OpenMP靜態(tài)調(diào)度進行實驗。本文的所有實驗均在沒有設(shè)置size參數(shù)的條件下進行。實驗選取4個基準函數(shù)進行對比測試。

(1)f1：Sphere函數(shù)

Sphere函數(shù)是連續(xù)的單峰函數(shù)，各分量在xi=0(i=1,2,…，n)時達到最小值0[12]；

(2)f2：Rosenbrock函數(shù)

Rosenbrock屬于一種單峰函數(shù)里比較復(fù)雜的病態(tài)函數(shù)，其全局最優(yōu)點位于一個平滑、狹長的拋物線型山谷內(nèi)，搜索的過程中比較難辨別方向，也極難找到全局最小點，通常用來評價算法的執(zhí)行效率[9]。Rosenbrock函數(shù)在xi=1(i=1,2,…，n)時達到最小值0。

(3)f3：Rastrigin函數(shù)

Rastrigin函數(shù)為多峰函數(shù)，在定義域范圍內(nèi)大約存在10n(n為問題的維數(shù))個局部極小點，是典型的非線性多模態(tài)函數(shù)，峰形呈高低起伏不定跳躍性的出現(xiàn)，所以一般的優(yōu)化算法很難搜索到全局最優(yōu)值[9]。Rastrigin函數(shù)在xi=0(i=1,2,…，n)時達到最小值0。

(4)f4：Griewank函數(shù)

Griewank函數(shù)也為典型的非線性多模態(tài)函數(shù)，含有大量的局部極值點，數(shù)目與問題的維度有關(guān)，隨著函數(shù)維度的增加，極值點的個數(shù)會成指數(shù)倍數(shù)增長，整個

函數(shù)具有廣闊的搜索空間。所以Griewank函數(shù)通常被認為是一般的優(yōu)化算法比較難處理的復(fù)雜多模態(tài)優(yōu)化問題[9]。Griewank函數(shù)在xi=0(i=1,2,…，n)時達到最小值0。

在處理Griewank函數(shù)時，考慮到Griewank是在Sphere函數(shù)的基礎(chǔ)之上增加了cos函數(shù)，之后的實驗結(jié)果證明了在D=100維和D=200維時，Sphere函數(shù)的并行效果并不好,所以在這里本文只對Griewank函數(shù)的后半部分做了并行的規(guī)約操作。

3.2 實驗結(jié)果及分析

D=100維下的并行化實驗結(jié)果如表1所示，實驗設(shè)置的參數(shù)為：蜜蜂種群數(shù)量SN=80，食物源數(shù)量FN=SN/2=40，問題維度D=100，最大循環(huán)次數(shù)MaxCycle=10 000，最大局部尋優(yōu)次數(shù)Limit=0.25×NP×D[17]=2 000，算法獨立運行30次。

表1 D=100維下的并行化實驗結(jié)果

D=200維下的并行化實驗結(jié)果如表2所示，實驗設(shè)置的參數(shù)為：蜜蜂種群數(shù)量SN=80，食物源數(shù)量FN=SN/2=40，問題維度D=200，最大循環(huán)次數(shù)MaxCycle=10 000，最大局部尋優(yōu)次數(shù)Limit=0.25×NP×D[17]=4 000，算法獨立運行30次。

表2 D=200維下的并行化實驗結(jié)果

3.3 結(jié)果分析

分析1通過表1和表2的實驗數(shù)據(jù)，不難發(fā)現(xiàn)，除了相對簡單的Sphere函數(shù)，在D=100維和D=200維時，PABC算法和PCABC算法均比ABC算法和CABC算法的運行時間少，對于簡單的Sphere函數(shù)，并行時間反而比串行時間長，這是因為并行運算有創(chuàng)建線程、同步線程和銷毀線程的時間，當計算量比較少時，這部分的時間就變?yōu)橹饕南臅r間。

分析2通過對比表1和表2的數(shù)據(jù)，可以發(fā)現(xiàn)，隨著維度的增加，算法的運行時間越長，加速比和效率越大，且加速比向4靠近(在本文所做實驗中，邏輯處理個的個數(shù)是4)，但是都小于4。PCABC算法對Sphere函數(shù)的優(yōu)化精度略有提高，但是收斂時間較標準人工蜂群算法長，PCABC算法對Rosenbrock函數(shù)和Rastrign函數(shù)的優(yōu)化精度略低于標準人工蜂群算法，但是算法運行時間遠遠少于標準人工蜂群算法，這說明PCABC算法對Rosenbrock函數(shù)和Rastrign函數(shù)在優(yōu)化精度和優(yōu)化時間上達到了權(quán)衡，PCABC算法對Griewank函數(shù)的優(yōu)化精度和優(yōu)化時間均優(yōu)于標準人工蜂群算法。

分析3對比表1和表2可以發(fā)現(xiàn)，問題的維度越大，算法收斂的時間越長。并行PABC算法和PCABC算法總體收斂速度要優(yōu)于串行ABC算法和CABC算法，這是因為，PABC算法和PCABC算法采用了OpenMP并行機制，在相同的時間內(nèi)，可以做更多的運算工作。PCABC算法的收斂速度要稍優(yōu)于PABC算法，CABC算法的收斂速度要稍優(yōu)于ABC算法，這是因為CABC算法和PCABC算法能夠保證當前獲得的最優(yōu)解引導(dǎo)種群進化，使算法逐漸收斂到全局最優(yōu)解。

4 結(jié)束語

針對人工蜂群算法在處理高維復(fù)雜問題時收斂速度慢的問題，本文提出的基于OpenMP的采用主從并行模型的并行人工蜂群算法PCABC能夠以較快的速度收斂。實驗結(jié)果證明，在高維度復(fù)雜函數(shù)的情況下，PCABC算法相對于標準人工蜂群算法在運行時間和收斂速度上都有較大的提升，這是因為PCABC算法對耗時多的計算適應(yīng)度函數(shù)的部分做了并行處理，大幅提升了算法的運行時間和收斂速度，同時PCABC算法利用式(4)，保證算法當前獲得的最優(yōu)解引導(dǎo)種群進化，進一步加速了算法的運行時間和收斂速度。本文對人工蜂群算法的研究方法同樣適用于研究其他群智能算法。下一步工作將是分析并行人工蜂群算法size參數(shù)和其他并行化調(diào)度類型對并行人工蜂群算法收斂的影響。

[1] Karaboga D.An idea based on honey bee swarm for numerical optimization[M]. Erciyes:Erciyes University,2005.

[2] 畢曉君,王艷嬌.加速收斂的人工蜂群算法[J].系統(tǒng)工程與電子技術(shù),2011(12):2755-2761.

[3] Karaboga D,Akay B.A comparative study of artificial bee colony algorithm[J].Applied Mathematics and Computation,2009,214(1):108-132.

[4] Holland J H.Adaptation in natural and artificial systems[M].Ann Arbor, MI:University of Michigan Press,1975.

[5] Kennedy J, Eberhart R.C.Particle swarm optimization[C].MI,USA:1995 IEEE International Conference on Neural Networks,1995.

[6] 寧愛平.人工蜂群算法及其在語音識別中的應(yīng)用研究[D].太原:太原理工大學,2013.

[7] 魏紅凱.人工蜂群算法及其應(yīng)用研究[D].北京:北京工業(yè)大學,2012.

[8] 王允霞.蜂群算法的研究及其在人工神經(jīng)網(wǎng)絡(luò)中的應(yīng)用[D].廣州:華南理工大學,2013.

[9] 何鵬.人工蜂群算法研究[D].上海:華東理工大學,2014.

[10] 袁亞杰.一種改進的人工蜂群算法[J].中國科技信息,2011(24):102-103.

[11] 劉麗麗.基于智能算法的網(wǎng)絡(luò)入侵檢測技術(shù)研究[D].南京:江南大學,2009.

[12] 江銘炎,袁東風.人工蜂群算法及其應(yīng)用[M].北京:科學出版社,2014.

[13] 都志輝.高性能計算并行編程技術(shù)[M].北京:清華大學出版社,2001.

[14] 羅秋明,明仲.OpenMP編譯原理及實現(xiàn)技術(shù)[M].北京:清華大學出版社,2012.

[15] Parpinelli R S,Beritez C M V,Lopes H S.Parallel approaches for the artificial bee colony algorithm[M].UK:Swarm Intelligence,2011.

[16] 徐昆.群智能算法及其并行計算技術(shù)的研究與應(yīng)用[D].濟南:山東大學,2014.

[17] M Subotic,M Tuba,N Stanarevic.Parallelization of the Artificial Bee Colony (ABC) algorithm[C].Weston DC:Wseas International Conference on Nural Networks &Wseas International Conference on Evolutionary Computing &Wseas International Conference on Fuzzy Systems,2010.

A Parallel Approach for Artificial Bee Colony Algorithm

MEI Kai,HUO Jiuyuan,CHANG Koukou

(School of Electronic and Information Engineering,Lanzhou Jiaotong University,Lanzhou 730070,China)

Aiming at the slow convergence speed of artificial bee colony algorithm in dealing with high dimensional problems, this paper uses OpenMP multi-threading technology and regulation mechanism, and according to the improved way onlooker bees choose employed bees, a parallel artificial bee colony algorithm(PCABC) based on OpenMP is proposed. Simulation experiments are performed to evaluate the performance of the algorithm under three different types of cyclic parallel scheduling types of OpenMP. In the 4 core processor environment, the speedup of parallel artificial bee colony algorithm based on static scheduling can reach to 3.95, the efficiency can reach to 98.65%.The experimental results show that the PCABC parallel artificial bee colony algorithm has higher lifting speed and running time when dealing with high dimensional complex functions.

artificial bee colony algorithm;improved artificial bee colony algorithm;swarm intelligence;parallelism; OpenMP parallel processing

2017- 03- 14

國家自然科學基金(61462058)；甘肅省自然科學研究基金計劃(1606RJZA004)；2016年賽爾網(wǎng)絡(luò)下一代互聯(lián)網(wǎng)技術(shù)創(chuàng)新項目(NGII20160111)

梅凱(1989-)，男，碩士研究生。研究方向：智能計算、并行計算等。火久元(1978-)，男，博士，副教授。研究方向：智能計算、并行計算、數(shù)據(jù)挖掘等。

TP31

A

1007-7820(2018)01-020-06