梅 凱,火久元,??劭?/p>
(蘭州交通大學(xué) 電子與信息工程學(xué)院,甘肅 蘭州 730070)
并行人工蜂群算法研究
梅 凱,火久元,??劭?/p>
(蘭州交通大學(xué) 電子與信息工程學(xué)院,甘肅 蘭州 730070)
針對(duì)人工蜂群算法在處理高維度問題時(shí)收斂速度慢的問題,利用OpenMP多線程技術(shù)和規(guī)約機(jī)制,并根據(jù)已改進(jìn)的觀察蜂來選擇雇傭蜂的方式,提出了基于OpenMP的并行人工蜂群算法(PCABC)。仿真實(shí)驗(yàn)分別在問題維度為100和200下進(jìn)行來評(píng)估算法性能,在4個(gè)邏輯處理器環(huán)境下,基于靜態(tài)調(diào)度的并行人工蜂群算法的加速比最高可以達(dá)到3.95,效率可達(dá)98.65%。實(shí)驗(yàn)結(jié)果表明,PCABC并行人工蜂群算法在處理高維度復(fù)雜函數(shù)時(shí),收斂速度和算法運(yùn)行時(shí)間都有較大的提升。
人工蜂群算法;人工蜂群算法改進(jìn);群體智能;并行化;OpenMP并行處理
人工蜂群算法[1]是一種新興的群智能優(yōu)化算法,由土耳其學(xué)者Karaboga在2005年提出,它具有設(shè)置參數(shù)少、易于實(shí)現(xiàn)、計(jì)算簡(jiǎn)單等優(yōu)點(diǎn),特別適合工程應(yīng)用[2]。文獻(xiàn)[3]將人工蜂群算法與其他其它群智能算法(遺傳算法[4]、粒子群算法[5]等)進(jìn)行了比較,證明人工蜂群算法的性能要接近甚至優(yōu)于其他算法。文獻(xiàn)[6]將人工蜂群算法進(jìn)行了改進(jìn)并應(yīng)用到語音識(shí)別模型中,識(shí)別結(jié)果顯示了人工蜂群算法及其改進(jìn)的人工蜂群算法具有良好的性能。文獻(xiàn)[7]通過引入基于引導(dǎo)素的化學(xué)通信方式,提出了一種基于引導(dǎo)素更新和擴(kuò)散機(jī)制的人工蜂群算法,并將改進(jìn)后的算法應(yīng)用在0-1多維背包問題上。文獻(xiàn)[8]將人工蜂群算法做了改進(jìn)并應(yīng)用到人工神經(jīng)網(wǎng)絡(luò)中,優(yōu)化了網(wǎng)絡(luò)的均方誤差函數(shù)。但是標(biāo)準(zhǔn)的人工蜂群算法在解決高維函數(shù)優(yōu)化時(shí),收斂速度較慢,算法運(yùn)行時(shí)間較長。為此,本文經(jīng)過深入研究,并結(jié)合文獻(xiàn)[9]中已改進(jìn)的觀察蜂來選擇雇傭蜂的方式,提出了并行人工蜂群算法(PCABC)算法,很好地解決了這一問題。
在人工蜂群算法中,蜜源被抽象成待優(yōu)化問題的解,蜜源的收益率(蜜源濃度、離蜂巢的距離等)越好,表示解的質(zhì)量越好。蜜蜂被分為3種類型:雇傭蜂、觀察蜂和偵查蜂。進(jìn)化迭代主要由這3種蜜蜂完成:(1)雇傭蜂在其記憶的花蜜源附近進(jìn)行局部隨機(jī)搜索,同時(shí)將蜜源信息傳遞給觀察蜂;(2)觀察蜂從中選擇較優(yōu)的蜜源,然后在這些蜜源周圍做進(jìn)一步的搜索;(3)偵察蜂對(duì)長期得不到更新的蜜源進(jìn)行更新。
ABC算法的具體步驟如下:
(1)算法初始化:算法在給定的取值范圍內(nèi)按照式(1)隨機(jī)產(chǎn)生n個(gè)食物源信息
xij=r·(maxj-minj)+minj
(1)
式中,r為(0,1)之間的隨機(jī)數(shù),maxj和minj為第j維取值的上限和下限;
(2)計(jì)算每個(gè)食物源的適應(yīng)度值;
(3)雇傭蜂更新食物源:雇傭蜂在食物源附近按照式(2)搜索新蜜源,比較新舊食物源的優(yōu)劣,若新食物源優(yōu)于舊食物源,則用新的食物源信息覆蓋舊食物源信息,否則保留舊的食物源,局部尋優(yōu)次數(shù)加1
(2)
其中i≠j,r為[-1,1]之間的隨機(jī)數(shù);
(4)觀察蜂更新食物源:觀察蜂根據(jù)雇傭蜂的舞蹈信息,按照輪盤賭方式選擇食物源,并在其附近按式(2)搜索新蜜源。并根據(jù)貪婪選擇的方式確定保留的蜜源。若蜜源沒有被更新,則局部尋優(yōu)次數(shù)加1。觀察蜂選擇蜜源的概率按照式(3)進(jìn)行計(jì)算
(3)
(5)偵察蜂更新食物源:拋棄停滯次數(shù)達(dá)到 的食物源,并按照式(1)在給定的取值范圍內(nèi)隨機(jī)生成新的食物源;參數(shù) 的作用是使長期得不到更新的引領(lǐng)蜂獲取重生[10];
(6)達(dá)到最大循環(huán)次數(shù):判斷算法是否達(dá)到算法預(yù)定的最大循環(huán)次數(shù)MaxCycle,是則算法結(jié)束,否則轉(zhuǎn)步驟(3)進(jìn)行下一次迭代。
群體智能算法是基于種群行為對(duì)給定的目標(biāo)進(jìn)行尋優(yōu)的啟發(fā)式搜索方法,其尋優(yōu)過程體現(xiàn)了隨機(jī)、并行和分布式等特點(diǎn)[11],所以群體智能算法適合做并行化計(jì)算。人工蜂群算法作為一種群體智能算法,具有天然的并行性??梢栽O(shè)想,在真正的大自然中,所有的蜜蜂進(jìn)行花蜜源搜索的時(shí)候,都是各自完成各自范圍的搜索任務(wù),獨(dú)立地把花蜜源的信息帶到蜂巢,這是明顯的并行性特征。同樣,當(dāng)蜜蜂將自己的信息帶回蜂巢進(jìn)行信息共享的時(shí)候,其他的蜜蜂也沒有因此而停止對(duì)各自蜜源的搜索,這也是天然并行性的體現(xiàn)[12]??梢哉J(rèn)為根據(jù)蜂群采蜜行為設(shè)計(jì)的人工蜂群算法也有并行性。圖1所示為蜜蜂采蜜過程的示意圖。
圖1 蜜蜂采蜜過程
按存儲(chǔ)方式對(duì)并行計(jì)算機(jī)進(jìn)行分類[13],并行計(jì)算機(jī)可以簡(jiǎn)單分為共享式內(nèi)存和分布式內(nèi)存。共享內(nèi)存就是多個(gè)核心共享一個(gè)內(nèi)存,一般的大型計(jì)算機(jī)結(jié)合分布式內(nèi)存和共享內(nèi)存結(jié)構(gòu),在每個(gè)計(jì)算節(jié)點(diǎn)內(nèi)是共享內(nèi)存,節(jié)點(diǎn)間是分布式內(nèi)存,如圖2所示。
圖2 按存儲(chǔ)方式對(duì)并行計(jì)算機(jī)進(jìn)行分類
OpenMP(Open Multi-Processing)是一種基于共享內(nèi)存編程模型的并行化技術(shù),它基于編譯制導(dǎo),具有簡(jiǎn)單、移植性好、可擴(kuò)展性高以及支持增量并行化開發(fā)等優(yōu)點(diǎn),已經(jīng)成為共享存儲(chǔ)系統(tǒng)中的并行編程標(biāo)準(zhǔn)。
1.2.6 疼痛護(hù)理:對(duì)于患者術(shù)后出現(xiàn)疼痛的情況,若患者屬于輕度疼痛,囑患者使用呼吸方法進(jìn)行肢體放松的訓(xùn)練:呼吸時(shí)深而慢,呼吸頻次控制在10次/min,每次進(jìn)行15 min左右的鍛煉?;驊?yīng)用音樂療法,囑患者聽輕快舒緩的音樂,以患者術(shù)后疼痛。若患者疼痛劇烈,根據(jù)實(shí)際情況,遵醫(yī)囑按時(shí)使用鎮(zhèn)痛藥物。
OpenMP有3大組成要素:環(huán)境變量、編譯制導(dǎo)指令、API函數(shù)。實(shí)驗(yàn)中,主要設(shè)置兩個(gè)環(huán)境變量的值:OMP_NUM_THREADS和OMP_SCHEDULE。OMP_NUM_THREADS環(huán)境變量用于設(shè)置并行域中的線程個(gè)數(shù),本文將其設(shè)為omp_get_num_procs()函數(shù)的返回值。omp_get_num_procs()函數(shù)的作用是返回系統(tǒng)中處理器的個(gè)數(shù)。本文所做實(shí)驗(yàn)中,omp_get_num_procs()函數(shù)的返回值為4。在OpenMP中,OMP_SCHEDULE環(huán)境變量對(duì)應(yīng)3種循環(huán)并行化調(diào)度類型:靜態(tài)調(diào)度、動(dòng)態(tài)調(diào)度和指導(dǎo)調(diào)度[14],size參數(shù)為3種調(diào)度類型的可選參數(shù)。
實(shí)驗(yàn)考慮到OpenMP特性和實(shí)驗(yàn)環(huán)境,采用不改變蜂群算法基本結(jié)構(gòu),保持只有一個(gè)種群的主從式并行模型,耗時(shí)多的計(jì)算適應(yīng)度函數(shù)部分[15-16]采用多線程并行執(zhí)行。
本文設(shè)計(jì)的并行人工蜂群算法(PCABC)的流程圖如圖4所示,主要包括以下步驟:
圖3 并行人工蜂群算法示意圖
(1)算法初始化:主線程完成算法的初始化,初始化食物源個(gè)數(shù)FN,最大迭代次數(shù)MaxCycle,最大局部探優(yōu)次數(shù)Limit,優(yōu)化空間維度D,在給定的取值范圍內(nèi)按照式(1)隨機(jī)產(chǎn)生FN個(gè)食物源信息;
(2)計(jì)算每個(gè)食物源的適應(yīng)度值:算法進(jìn)入并行區(qū),并行計(jì)算每個(gè)食物源的適應(yīng)度值,本文采用4個(gè)線程并行計(jì)算,并使用OpenMP規(guī)約機(jī)制[14]對(duì)并行結(jié)果進(jìn)行匯總,計(jì)算完成后,算法退出并行,回到主線程繼續(xù)執(zhí)行步驟(3);
(4)觀察蜂更新食物源[9]:觀察蜂根據(jù)雇傭蜂跳的“搖擺舞”信息,按照輪盤賭方式選擇食物源,并在其附近按式(4)搜索新蜜源。算法進(jìn)入并行區(qū),并行計(jì)算新蜜源的適應(yīng)度值,并使用OpenMP規(guī)約機(jī)制對(duì)并行結(jié)果進(jìn)行匯總,計(jì)算完成后,算法退出并行,回到主線程中,根據(jù)貪婪選擇方法確定保留的食物源
(4)
(5)偵查蜂更新食物源:主線程拋棄停滯次數(shù)達(dá)到Limit的食物源信息,并按照式(1)在給定的取值范圍內(nèi)隨機(jī)生成新的食物源;
(6)達(dá)到最大循環(huán)次數(shù):主線程判斷算法是否達(dá)到預(yù)定的最大循環(huán)次數(shù)MaxCycle,是則算法結(jié)束,否則轉(zhuǎn)步驟(3)進(jìn)行下一次迭代。
實(shí)驗(yàn)在Inter(R) Core(TM) i3CPU M 370、主頻2.4 GHz,內(nèi)存4 GB,4個(gè)邏輯處理器的個(gè)人電腦上進(jìn)行,操作系統(tǒng)是Windows 10,基于Visual Studio 2010編程工具,C++語言實(shí)現(xiàn),采用OpenMP多線程并行編程技術(shù)。本文將已改進(jìn)的觀察蜂來選擇雇傭蜂的人工蜂群算法記為CABC,標(biāo)準(zhǔn)人工蜂群算法的并行化算法記為PABC,將并行的CABC算法記為PCABC。
仿真實(shí)驗(yàn)中,蜜蜂種群大小SN=80,食物源個(gè)數(shù)FN=SN/2,問題維數(shù)分別取D=100和D=200,最大循環(huán)次數(shù)MaxCycle=10 000,最大局部尋優(yōu)次數(shù)Limit取值按公式0.25×NP×D[17]計(jì)算,算法獨(dú)立運(yùn)行30次,選取OpenMP靜態(tài)調(diào)度進(jìn)行實(shí)驗(yàn)。本文的所有實(shí)驗(yàn)均在沒有設(shè)置size參數(shù)的條件下進(jìn)行。實(shí)驗(yàn)選取4個(gè)基準(zhǔn)函數(shù)進(jìn)行對(duì)比測(cè)試。
(1)f1:Sphere函數(shù)
Sphere函數(shù)是連續(xù)的單峰函數(shù),各分量在xi=0(i=1,2,…,n)時(shí)達(dá)到最小值0[12];
(2)f2:Rosenbrock函數(shù)
Rosenbrock屬于一種單峰函數(shù)里比較復(fù)雜的病態(tài)函數(shù),其全局最優(yōu)點(diǎn)位于一個(gè)平滑、狹長的拋物線型山谷內(nèi),搜索的過程中比較難辨別方向,也極難找到全局最小點(diǎn),通常用來評(píng)價(jià)算法的執(zhí)行效率[9]。Rosenbrock函數(shù)在xi=1(i=1,2,…,n)時(shí)達(dá)到最小值0。
(3)f3:Rastrigin函數(shù)
Rastrigin函數(shù)為多峰函數(shù),在定義域范圍內(nèi)大約存在10n(n為問題的維數(shù))個(gè)局部極小點(diǎn),是典型的非線性多模態(tài)函數(shù),峰形呈高低起伏不定跳躍性的出現(xiàn),所以一般的優(yōu)化算法很難搜索到全局最優(yōu)值[9]。Rastrigin函數(shù)在xi=0(i=1,2,…,n)時(shí)達(dá)到最小值0。
(4)f4:Griewank函數(shù)
Griewank函數(shù)也為典型的非線性多模態(tài)函數(shù),含有大量的局部極值點(diǎn),數(shù)目與問題的維度有關(guān),隨著函數(shù)維度的增加,極值點(diǎn)的個(gè)數(shù)會(huì)成指數(shù)倍數(shù)增長,整個(gè)
函數(shù)具有廣闊的搜索空間。所以Griewank函數(shù)通常被認(rèn)為是一般的優(yōu)化算法比較難處理的復(fù)雜多模態(tài)優(yōu)化問題[9]。Griewank函數(shù)在xi=0(i=1,2,…,n)時(shí)達(dá)到最小值0。
在處理Griewank函數(shù)時(shí),考慮到Griewank是在Sphere函數(shù)的基礎(chǔ)之上增加了cos函數(shù),之后的實(shí)驗(yàn)結(jié)果證明了在D=100維和D=200維時(shí),Sphere函數(shù)的并行效果并不好,所以在這里本文只對(duì)Griewank函數(shù)的后半部分做了并行的規(guī)約操作。
D=100維下的并行化實(shí)驗(yàn)結(jié)果如表1所示,實(shí)驗(yàn)設(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,算法獨(dú)立運(yùn)行30次。
表1 D=100維下的并行化實(shí)驗(yàn)結(jié)果
D=200維下的并行化實(shí)驗(yàn)結(jié)果如表2所示,實(shí)驗(yàn)設(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,算法獨(dú)立運(yùn)行30次。
表2 D=200維下的并行化實(shí)驗(yàn)結(jié)果
分析1通過表1和表2的實(shí)驗(yàn)數(shù)據(jù),不難發(fā)現(xiàn),除了相對(duì)簡(jiǎn)單的Sphere函數(shù),在D=100維和D=200維時(shí),PABC算法和PCABC算法均比ABC算法和CABC算法的運(yùn)行時(shí)間少,對(duì)于簡(jiǎn)單的Sphere函數(shù),并行時(shí)間反而比串行時(shí)間長,這是因?yàn)椴⑿羞\(yùn)算有創(chuàng)建線程、同步線程和銷毀線程的時(shí)間,當(dāng)計(jì)算量比較少時(shí),這部分的時(shí)間就變?yōu)橹饕南臅r(shí)間。
分析2通過對(duì)比表1和表2的數(shù)據(jù),可以發(fā)現(xiàn),隨著維度的增加,算法的運(yùn)行時(shí)間越長,加速比和效率越大,且加速比向4靠近(在本文所做實(shí)驗(yàn)中,邏輯處理個(gè)的個(gè)數(shù)是4),但是都小于4。PCABC算法對(duì)Sphere函數(shù)的優(yōu)化精度略有提高,但是收斂時(shí)間較標(biāo)準(zhǔn)人工蜂群算法長,PCABC算法對(duì)Rosenbrock函數(shù)和Rastrign函數(shù)的優(yōu)化精度略低于標(biāo)準(zhǔn)人工蜂群算法,但是算法運(yùn)行時(shí)間遠(yuǎn)遠(yuǎn)少于標(biāo)準(zhǔn)人工蜂群算法,這說明PCABC算法對(duì)Rosenbrock函數(shù)和Rastrign函數(shù)在優(yōu)化精度和優(yōu)化時(shí)間上達(dá)到了權(quán)衡,PCABC算法對(duì)Griewank函數(shù)的優(yōu)化精度和優(yōu)化時(shí)間均優(yōu)于標(biāo)準(zhǔn)人工蜂群算法。
分析3對(duì)比表1和表2可以發(fā)現(xiàn),問題的維度越大,算法收斂的時(shí)間越長。并行PABC算法和PCABC算法總體收斂速度要優(yōu)于串行ABC算法和CABC算法,這是因?yàn)?,PABC算法和PCABC算法采用了OpenMP并行機(jī)制,在相同的時(shí)間內(nèi),可以做更多的運(yùn)算工作。PCABC算法的收斂速度要稍優(yōu)于PABC算法,CABC算法的收斂速度要稍優(yōu)于ABC算法,這是因?yàn)镃ABC算法和PCABC算法能夠保證當(dāng)前獲得的最優(yōu)解引導(dǎo)種群進(jìn)化,使算法逐漸收斂到全局最優(yōu)解。
針對(duì)人工蜂群算法在處理高維復(fù)雜問題時(shí)收斂速度慢的問題,本文提出的基于OpenMP的采用主從并行模型的并行人工蜂群算法PCABC能夠以較快的速度收斂。實(shí)驗(yàn)結(jié)果證明,在高維度復(fù)雜函數(shù)的情況下,PCABC算法相對(duì)于標(biāo)準(zhǔn)人工蜂群算法在運(yùn)行時(shí)間和收斂速度上都有較大的提升,這是因?yàn)镻CABC算法對(duì)耗時(shí)多的計(jì)算適應(yīng)度函數(shù)的部分做了并行處理,大幅提升了算法的運(yùn)行時(shí)間和收斂速度,同時(shí)PCABC算法利用式(4),保證算法當(dāng)前獲得的最優(yōu)解引導(dǎo)種群進(jìn)化,進(jìn)一步加速了算法的運(yùn)行時(shí)間和收斂速度。本文對(duì)人工蜂群算法的研究方法同樣適用于研究其他群智能算法。下一步工作將是分析并行人工蜂群算法size參數(shù)和其他并行化調(diào)度類型對(duì)并行人工蜂群算法收斂的影響。
[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] 寧愛平.人工蜂群算法及其在語音識(shí)別中的應(yīng)用研究[D].太原:太原理工大學(xué),2013.
[7] 魏紅凱.人工蜂群算法及其應(yīng)用研究[D].北京:北京工業(yè)大學(xué),2012.
[8] 王允霞.蜂群算法的研究及其在人工神經(jīng)網(wǎng)絡(luò)中的應(yīng)用[D].廣州:華南理工大學(xué),2013.
[9] 何鵬.人工蜂群算法研究[D].上海:華東理工大學(xué),2014.
[10] 袁亞杰.一種改進(jìn)的人工蜂群算法[J].中國科技信息,2011(24):102-103.
[11] 劉麗麗.基于智能算法的網(wǎng)絡(luò)入侵檢測(cè)技術(shù)研究[D].南京:江南大學(xué),2009.
[12] 江銘炎,袁東風(fēng).人工蜂群算法及其應(yīng)用[M].北京:科學(xué)出版社,2014.
[13] 都志輝.高性能計(jì)算并行編程技術(shù)[M].北京:清華大學(xué)出版社,2001.
[14] 羅秋明,明仲.OpenMP編譯原理及實(shí)現(xiàn)技術(shù)[M].北京:清華大學(xué)出版社,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] 徐昆.群智能算法及其并行計(jì)算技術(shù)的研究與應(yīng)用[D].濟(jì)南:山東大學(xué),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
國家自然科學(xué)基金(61462058);甘肅省自然科學(xué)研究基金計(jì)劃(1606RJZA004);2016年賽爾網(wǎng)絡(luò)下一代互聯(lián)網(wǎng)技術(shù)創(chuàng)新項(xiàng)目(NGII20160111)
梅凱(1989-),男,碩士研究生。研究方向:智能計(jì)算、并行計(jì)算等?;鹁迷?1978-),男,博士,副教授。研究方向:智能計(jì)算、并行計(jì)算、數(shù)據(jù)挖掘等。
TP31
A
1007-7820(2018)01-020-06