基于混合變異的人工蜂群算法

張曉慶, 高 尚,范霽月

(江蘇科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院, 鎮(zhèn)江 212003)

人工蜂群算法(artificial bee colony algrithm,ABC)是文獻(xiàn)[1]中提出的一種群智能優(yōu)化算法,與其他智能優(yōu)化算法相比,該算法具有控制參數(shù)少、魯棒性強(qiáng)、易于實(shí)現(xiàn)等優(yōu)點(diǎn),已被成功應(yīng)用于組合優(yōu)化[2]、無(wú)線傳感網(wǎng)絡(luò)[3]、圖像處理[4]等領(lǐng)域．然而,原始的人工蜂群算法存在局部搜索能力較差、收斂速度較慢以及易于陷入局部最優(yōu)的缺點(diǎn),為此,眾多學(xué)者對(duì)其進(jìn)行了大量的研究．文獻(xiàn)[5-6]中利用混沌序列的隨機(jī)性、遍歷性和規(guī)律性,設(shè)計(jì)了一種混沌搜索算子,以提高算法的搜索精度和收斂速度;文獻(xiàn)[7]中提出了一種新的選擇策略和交叉策略以提高算法的收斂速度;文獻(xiàn)[8]中將信息熵引入跟隨蜂的選擇策略中,避免了算法陷入局部最優(yōu)值的問(wèn)題,增加了全局搜索能力;文獻(xiàn)[2]中利用全局最優(yōu)解和個(gè)體極值改進(jìn)了搜索模式,并引入異步變化學(xué)習(xí)因子以提高算法的局部搜索能力;文獻(xiàn)[9]中提出一種基于文化算法的人工蜂群算法,利用信度空間中的規(guī)范知識(shí)調(diào)整搜索范圍,提高了算法的收斂速度和勘探能力;文獻(xiàn)[10]中提出了在差分變異算子中引入混沌序列以增強(qiáng)算法的局部搜索能力,并提高了其收斂速度和解的精度．

為了進(jìn)一步提高人工蜂群算法的性能,文中利用差分進(jìn)化算法和高斯變異算法在維護(hù)種群多樣性以及搜索能力方面的較強(qiáng)優(yōu)勢(shì),將混合變異算子引入到人工蜂群算法,并從兩個(gè)方面對(duì)原始算法進(jìn)行了改進(jìn)．首先,跟隨蜂采用了基于當(dāng)前最優(yōu)解的差分變異搜索策略在食物源附近進(jìn)行搜索,利用差分變異的思想提高了算法的全局搜索能力,豐富了解的多樣性,并通過(guò)當(dāng)前最優(yōu)解的引導(dǎo),使算法的收斂速度加快;其次,當(dāng)某個(gè)食物源位置長(zhǎng)時(shí)間沒(méi)有更新時(shí),偵查蜂通過(guò)高斯變異局部最優(yōu)解來(lái)生成新的食物源位置,避免了解的隨機(jī)性,加快了算法的收斂速度．通過(guò)測(cè)試函數(shù)的仿真實(shí)驗(yàn)結(jié)果表明,文中提出的基于混合變異的人工蜂群算法有效提高了收斂速度和求解精度．

1 人工蜂群算法

人工蜂群算法的思想源于自然界中的蜜蜂采蜜行為,蜜蜂尋找優(yōu)質(zhì)食物源的過(guò)程可視為函數(shù)尋找最優(yōu)解的過(guò)程．蜂群產(chǎn)生的智能群體模型中主要包括食物源、引領(lǐng)蜂、偵查蜂和跟隨蜂4個(gè)部分,每個(gè)解代表一個(gè)食物源,解的個(gè)數(shù)等于引領(lǐng)蜂或跟隨蜂的個(gè)數(shù),引領(lǐng)蜂丟棄食物源之后轉(zhuǎn)變?yōu)閭刹榉?食物源的花蜜豐富程度由適應(yīng)度值來(lái)決定．

假設(shè)人工蜂群算法在D維搜索空間內(nèi)隨機(jī)產(chǎn)生SN個(gè)初始解(食物源),每個(gè)解可表示為xi=(xi1,xi2,…,xiD),i=1, 2,…,SN．首先,引領(lǐng)蜂在食物源附近(鄰域內(nèi))進(jìn)行循環(huán)搜索,以更新食物源的位置,其方式如下:

vij=xij+rij(xij-xkj)

(1)

式中：vij為候選食物源；xk為隨機(jī)選取的一個(gè)已知解,j為解對(duì)應(yīng)的維數(shù),且有k不等于i；rij為用來(lái)控制xij位置處的鄰域大小的隨機(jī)參數(shù),取值在[-1,1]內(nèi),隨著迭代次數(shù)的增加,鄰域的半徑會(huì)逐漸縮小,最終獲得最優(yōu)解．

引領(lǐng)蜂在食物源的位置更新后,比較候選食物源與原始食物源的花蜜豐富程度,如果候選食物源的適應(yīng)度值高于原始食物源,則用候選食物源代替原始食物源,否則保持原始食物源的位置不發(fā)生變化．然后,引領(lǐng)蜂返回到舞蹈區(qū)域,并通過(guò)搖擺舞方式將各個(gè)食物源的花蜜信息傳遞給跟隨蜂,跟隨蜂根據(jù)食物源的收益率來(lái)選擇到哪個(gè)食物源進(jìn)行采蜜行為．收益率與適應(yīng)度值密切相關(guān),食物源選擇的概率如下:

(2)

(3)

式中：Pi為第i個(gè)食物源的選擇概率；fiti為第i個(gè)食物源的適應(yīng)度值；SN為食物源的個(gè)數(shù)；fi為優(yōu)化問(wèn)題的目標(biāo)函數(shù)值．

由式(3)可知,當(dāng)目標(biāo)函數(shù)值fi≥0時(shí),適應(yīng)度值fiti隨著目標(biāo)函數(shù)值fi的減小而逐漸增大;當(dāng)目標(biāo)函數(shù)值fi<0時(shí),適應(yīng)度值fiti也隨著目標(biāo)函數(shù)值fi的減小而逐漸增大,又由式(2)可知,fiti越大,食物源的收益率越大,進(jìn)而食物源被選擇的概率越高．

跟隨蜂在選中食物源之后,也根據(jù)式(1)在其鄰域內(nèi)進(jìn)行搜索,并通過(guò)比較適應(yīng)度值,保留較好的食物源．如果引領(lǐng)蜂在經(jīng)過(guò)limit次循環(huán)后,食物源的位置仍未更新,則表明這個(gè)食物源位置已陷入局部最優(yōu),引領(lǐng)蜂應(yīng)放棄該食物源,轉(zhuǎn)變?yōu)閭刹榉?并隨機(jī)生成一個(gè)新的食物源位置來(lái)代替原始的食物源位置,其方式:

xij=xminj+δ(xmaxj-xminj)

(4)

式中：xij為新的食物源i在第j維的分量,j∈{1,2,…,D}；xmin j為第j維分量的最小值；xmax j為第j維分量的最大值；δ為(0,1)范圍內(nèi)的隨機(jī)數(shù)．

2 改進(jìn)的人工蜂群算法

2.1 差分進(jìn)化搜索策略

差分進(jìn)化算法是文獻(xiàn)[11]中提出的一種解決全局優(yōu)化問(wèn)題的方法．它是一種模擬生物進(jìn)化的隨機(jī)模型,通過(guò)不斷迭代,使適應(yīng)環(huán)境的個(gè)體被保留下來(lái),引導(dǎo)搜索過(guò)程向最優(yōu)解逼近．差分進(jìn)化算法具有較強(qiáng)的全局收斂能力和魯棒性,且進(jìn)化過(guò)程中最核心的步驟為差分變異,其方式:

U=Xr1+F(Xr2-Xr3)

(5)

式中：U為變異后的個(gè)體；Xr1,Xr2,Xr3為隨機(jī)選取的3個(gè)互不相同的個(gè)體；F為變異因子．

原始的人工蜂群算法中,跟隨蜂和引領(lǐng)蜂采用相同的搜索策略,由式(1)可知,該搜索策略具有較好的全局搜索能力,而忽略了算法的局部搜索性能．為此,文獻(xiàn)[12]中引入當(dāng)前最優(yōu)解,提出了一種新的搜索方式:

vij=xij+φij(xij-xkj)+φij(xbj-xij),

(6)

式中：vij為候選食物源；xk為隨機(jī)選取的已知解；φij為[-1,1]上均勻分布的隨機(jī)值；φij為[0,1.5]之間的隨機(jī)值；xbj為當(dāng)前最優(yōu)的食物源位置．由式(6)可以看出,引入當(dāng)前最優(yōu)解后,算法的局部搜索能力在一定程度上得到了提高,加快了收斂速度．

為了進(jìn)一步提高人工蜂群算法的全局搜索能力,增加種群的多樣性,將差分進(jìn)化算法中變異的思想引入到搜索策略中,即有:

vij=xij+η[(xpj-xqj)+(xbj-xij)]

(7)

且

(8)

式中：xpj,xqj為隨機(jī)選取的兩個(gè)已知解；xbj為當(dāng)前最優(yōu)的食物源位置；η為差分變異因子；itx為當(dāng)前迭代的次數(shù)；MCN為最大迭代次數(shù)．

由式(8)可知,差分變異因子η隨著迭代次數(shù)itx的增加而逐漸減小,又由式(7)可知,η越小,則蜂群搜查范圍越?。诘跗?η較大,有利于擴(kuò)大搜索空間,提高算法的全局搜索能力,增加解的多樣性;而在迭代后期,η逐漸變小,有利于收斂到局部最優(yōu)位置,從而提升收斂精度．

2.2 高斯變異偵查策略

高斯變異[12-13]是在原有個(gè)體的基礎(chǔ)上添加一個(gè)服從高斯分布的隨機(jī)擾動(dòng)項(xiàng),借助高斯隨機(jī)擾動(dòng)項(xiàng),可以增強(qiáng)個(gè)體跳出局部最優(yōu)解的能力,提高求解精度,其定義:

Xi=Xi+Xi·N(0,1)

(9)

式中：Xi為第i號(hào)個(gè)體；N(0, 1)為服從均值為0且方差為1的高斯分布．

原始的人工蜂群算法中,偵查蜂采用隨機(jī)偵查策略,通過(guò)式(4)隨機(jī)生成一個(gè)新的食物源來(lái)代替原始食物源,這樣生成的食物源位置的隨機(jī)性太強(qiáng),導(dǎo)致收斂速度減慢,且易在搜索過(guò)程中陷入局部最優(yōu)．因此,提出了一種更加有效的偵查策略,其方式:

(10)

與式(4)相比,式(10)利用高斯隨機(jī)干擾項(xiàng),讓算法跳出當(dāng)前最優(yōu)值,變異生成一個(gè)新的食物源位置,使得偵查蜂在當(dāng)前最優(yōu)解附近進(jìn)行局部搜索,基于當(dāng)前最優(yōu)解的高斯變異偵查策略可以有效避免解的隨機(jī)性,加快收斂速度,提高解的精度．

2.3 基于混合變異的人工蜂群算法

在差分進(jìn)化搜索策略和高斯變異偵察策略的基礎(chǔ)上,基于混合變異算子的人工蜂群算法(artificial bee colony algrithm based on hybrid mutation operator,HMABC)的具體步驟:

(1) 隨機(jī)生成SN個(gè)初始解,設(shè)置最大迭代次數(shù)MCN和limit值;

(2) 引領(lǐng)蜂根據(jù)式(1)在每個(gè)食物源的鄰域內(nèi)進(jìn)行搜索,并計(jì)算新的食物源的適應(yīng)度值,若新的食物源的適應(yīng)度較大,則更新食物源的位置,否則,食物源位置不變;

(3) 找出當(dāng)前的最優(yōu)食物源xbj;

(4) 根據(jù)式(2)計(jì)算每個(gè)食物源被選擇的概率,跟隨蜂根據(jù)貪心搜索策略選擇最優(yōu)食物源,并根據(jù)式(7)進(jìn)行局部搜索;

(5) 若食物源的位置在搜索次數(shù)達(dá)到limit次都沒(méi)有更新,則放棄該食物源,引領(lǐng)蜂變成偵查蜂并根據(jù)式(10)在當(dāng)前最優(yōu)食物源附近產(chǎn)生一個(gè)新的食物源位置;

(6) 判斷是否滿足最大迭代次數(shù),若不滿足,則轉(zhuǎn)入步驟(2),否則,輸出最優(yōu)位置．

3 實(shí)驗(yàn)分析

為了驗(yàn)證文中提出的HMABC算法的有效性,選擇6種典型的測(cè)試函數(shù)進(jìn)行仿真實(shí)驗(yàn)．將HMABC算法與原始的ABC算法、GABC算法[14]、ABCMSS算法[15]進(jìn)行對(duì)比分析．表1給出了6種測(cè)試函數(shù)的表達(dá)式、搜索空間和最優(yōu)值,其中f1(x)～f3(x)為單峰函數(shù),用來(lái)測(cè)試算法的收斂速度和尋優(yōu)精度;f4(x)～f6(x)為多峰函數(shù),具有多個(gè)極值點(diǎn),用來(lái)測(cè)試算法的全局尋優(yōu)能力．

4種算法均采用隨機(jī)生成初始解的方式,種群規(guī)模SN=100,搜索空間維數(shù)D=100,最大迭代次數(shù)MCN=1 000,limit=200．表2～7分別列出了4種算法對(duì)6種測(cè)試函數(shù)獨(dú)立運(yùn)行30次得到的實(shí)驗(yàn)結(jié)果．其中,均值反映了算法的平均精度,標(biāo)準(zhǔn)差反映了算法的穩(wěn)定性．圖1～6分別為測(cè)試函數(shù)的平均適應(yīng)值進(jìn)化曲線．

表1 測(cè)試函數(shù)

表2 Sphere函數(shù)上的實(shí)驗(yàn)對(duì)比

表3 Sum Squares函數(shù)上的實(shí)驗(yàn)對(duì)比

表4 Rosenbrock函數(shù)上的實(shí)驗(yàn)對(duì)比

表5 Rastrigin函數(shù)上的實(shí)驗(yàn)對(duì)比

表6 Ackley函數(shù)上的實(shí)驗(yàn)對(duì)比

表7 Griewank函數(shù)上的實(shí)驗(yàn)對(duì)比

圖1 Sphere函數(shù)進(jìn)化曲線

圖2 Sum Squares函數(shù)進(jìn)化曲線

圖3 Rosenbrock函數(shù)進(jìn)化曲線

圖4 Rastrigin函數(shù)進(jìn)化曲線

圖5 Ackley函數(shù)進(jìn)化曲線

圖6 Griewank函數(shù)進(jìn)化曲線

對(duì)于簡(jiǎn)單的單峰函數(shù)f1(x)～f2(x),從表2、3及圖1、2可以看出，HMABC算法比ABC算法、GABC算法和ABCMSS算法具有更快的收斂速度和更高的尋優(yōu)精度．對(duì)于比較復(fù)雜的單峰函數(shù)f3(x),在迭代初期,4種算法都具有較快的收斂速度,但由于其自身的特性,在迭代后期,算法的收斂速度減慢并容易陷入局部最優(yōu),而HMABC算法引入了混合變異的思想,能使其盡可能跳出局部最優(yōu)值,提高了算法的收斂速度,從表4和圖3也可以看出,HMABC算法的求解精度亦優(yōu)于另外3種算法．

對(duì)于復(fù)雜的非線性多峰函數(shù)f4(x)～f6(x),從表5～7和圖4～6可以看出,HMABC算法對(duì)于函數(shù)f5(x)的尋優(yōu)結(jié)果略差于ABCMSS算法,但相比ABC算法和GABC算法仍有較為明顯的優(yōu)勢(shì),對(duì)于另外兩種函數(shù),HMABC算法的收斂速度和尋優(yōu)精度都遠(yuǎn)優(yōu)于ABC算法、GABC算法和ABCMSS算法．由于這3個(gè)函數(shù)本身的特性,傳統(tǒng)的人工蜂群算法很容易陷入局部最優(yōu)值,而HMABC算法引入差分變異的思想,增加了種群的多樣性,平衡了算法的全局搜索能力和局部搜索能力,又引入高斯變異的思想,使其盡可能跳出局部最優(yōu)值,提高了算法的尋優(yōu)精度．由此可見(jiàn),HMABC具有較強(qiáng)的全局搜索能力和較快的收斂速度．

4 結(jié)論

(1) 在傳統(tǒng)的人工蜂群算法的基礎(chǔ)上,針對(duì)算法局部搜索能力弱、收斂速度慢和易于陷入局部最優(yōu)的缺陷,提出了一種基于當(dāng)前最優(yōu)解的差分進(jìn)化搜索策略和高斯變異偵查策略的混合變異人工蜂群算法．

(2) 先通過(guò)差分變異因子在迭代初期進(jìn)行全局搜索,增加解的多樣性,在迭代后期進(jìn)行局部搜索,提高了算法收斂速度,再通過(guò)高斯變異算子對(duì)偵查蜂的搜索模式進(jìn)行改進(jìn),增強(qiáng)了算法的局部搜索能力,避免算法陷入局部最優(yōu)．

(3) 6組基于典型的測(cè)試函數(shù)的實(shí)驗(yàn)結(jié)果表明,該算法的收斂速度和求解精度得到了顯著提高．

References)

[1] KARABOGA D. An idea based on honey bee swarm for numerical optimization[R].[s.l.]:Erciyes University,2005.

[2] 王慧穎, 劉建軍, 王全洲. 改進(jìn)的人工蜂群算法在函數(shù)優(yōu)化問(wèn)題中的應(yīng)用[J]. 計(jì)算機(jī)工程與應(yīng)用, 2012, 48(19): 36-39. DOI:10.3778/j.issn.1002-8331.012.19.010.

WANG Huiying, LIU Jianjun, WANG Quanzhou. Modified artificial bee colony algorithm for numerical function optimization[J]. Computer Engineering and Applications, 2012, 48(19): 36-39. DOI:10.3778/j.issn.1002-8331.012.19.010.(in Chinese)

[3] 文政穎, 翟紅生. 基于混沌人工蜂群算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化[J]. 計(jì)算機(jī)測(cè)量與控制, 2014, 22(5): 1609-1612. DOI:10.3969/j.issn.1671-4598.014.05.092.

WEN Zhengying, ZHAI Hongsheng. Coverage optimization of wireless sensor networks base on chaotic artificial bee colony algorithm[J]. Computer Measurement & Control, 2014, 22(5): 1609-1612. DOI:10.3969/j.issn.1671-4598.014.05.092.(in Chinese)

[4] 梁建慧, 馬苗. 人工蜂群算法在圖像分割中的應(yīng)用研究[J]. 計(jì)算機(jī)工程與應(yīng)用, 2012, 48(8): 194-196,229. DOI:10.3778/j.issn.1002-8331.012.08.055.

LIANG Jianhui, MA Miao. Artificial bee colony algorithm based research on image segmentation[J]. Computer Engineering and Applications, 2012, 48(8): 194-196,229. DOI:10.3778/j.issn.1002-8331.012.08.055.(in Chinese)

[5] 王翔, 李志勇, 許國(guó)藝, 等. 基于混沌局部搜索算子的人工蜂群算法[J]. 計(jì)算機(jī)應(yīng)用, 2012, 32(4): 1033-1036,1040. DOI:10.3724/SP.J.1087.012.01033.

WANG Xiang, LI Zhiyong, XU Guoyi, et al. Artificial bee colony algorithm based on chaos local search operator[J]. Journal of Computer Applications, 2012, 32(4): 1033-1036,1040. DOI:10.3724/SP.J.1087.012.01033.(in Chinese)

[6] 羅鈞, 李研. 具有混沌搜索策略的蜂群優(yōu)化算法[J]. 控制與決策, 2010, 25(12): 1913-1916.

LUO Jun, LI Yan. Artificial bee colony algorithm with chaotic-search strategy[J]. Control and Decision, 2010, 25(12): 1913-1916.(in Chinese)

[7] 畢曉君, 王艷嬌. 加速收斂的人工蜂群算法[J]. 系統(tǒng)工程與電子技術(shù), 2011, 33(12): 2755-2761. DOI:10.3969/j.issn.1001-506X.2011.12.34.

BI Xiaojun, WANG Yanjiao. Artificial bee colony algorithm with fast convergence[J]. Systems Engineering and Electronics, 2011, 33(12): 2755-2761. DOI:10.3969/j.issn.1001-506X.2011.12.34.(in Chinese)

[8] 李彥蒼, 彭?yè)P(yáng). 基于信息熵的改進(jìn)人工蜂群算法[J]. 控制與決策, 2015, 30(6): 1121-1125. DOI:10.13195/j.kzyjc.2014.0377.

LI Yancang, PENG Yang. Improved artificial bee colony algorithm based on information entropy[J]. Control and Decision, 2015, 30(6): 1121-1125. DOI:10.13195/j.kzyjc.2014.0377.(in Chinese)

[9] 林小軍, 葉東毅. 一種帶規(guī)范知識(shí)引導(dǎo)的改進(jìn)人工蜂群算法[J]. 模式識(shí)別與人工智能, 2013, 26(3): 307-314.

LIN Xiaojun, YE Dongyi. An improved artificial bee colony algorithm with guided normative knowledge[J]. Pattern Recognition and Artificial Intelligence, 2013, 26(3): 307-314.(in Chinese)

[10] 銀建霞, 孟紅云. 具有混沌差分進(jìn)化搜索的人工蜂群算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2011, 47(29): 27-30. DOI:10.3778/j.issn.1002-8331.011.9.008.

YIN Jianxia, MENG Hongyun. Artificial bee colony algorithm with chaotic differential evolution search[J]. Computer Engineering and Applications, 2011, 47(29): 27-30. DOI:10.3778/j.issn.1002-8331.011.9.008.(in Chinese)

[11] 楊啟文, 蔡亮, 薛云燦. 差分進(jìn)化算法綜述[J]. 模式識(shí)別與人工智能, 2008, 21(4): 506-513. DOI:10.3969/j.issn.1003-6059.008.04.013.

YANG Qiwen, CAI Liang, XUE Yuncan. A survey of differential evolution algorithms[J]. Pattern Recognition and Artificial Intelligence, 2008, 21(4): 506-513. DOI:10.3969/j.issn.1003-6059.008.04.013.(in Chinese)

[12] 莫愿斌, 劉付永, 張宇楠. 帶高斯變異的人工螢火蟲(chóng)優(yōu)化算法[J]. 計(jì)算機(jī)應(yīng)用研究, 2013, 30(1): 121-123. DOI:10.3969/j.issn.1001-3695.013.01.029.

MO Yuanbin, LIU Fuyong, ZHANG Yunan. Artificial glowworm swarm optimization algorithm with Gauss mutation[J]. Application Research of Computers, 2013, 30(1): 121-123. DOI:10.3969/j.issn.1001-3695.013.01.029.(in Chinese)

[13] 楊善友, 藍(lán)新波. 融入變異算子的螢火蟲(chóng)算法[J]. 火力與指揮控制, 2014, 39(8): 47-50. DOI:10.3969/j.issn.1002-0640.014.08.012.

YANG Shanyou, LAN Xinbo. Growworm swarm optimization algorithm based on mutation operator[J]. Fire Control & Command Control, 2014, 39(8): 47-50. DOI:10.3969/j.issn.1002-0640.014.08.012.(in Chinese)

[14] ZHU G, KWONG S. Gbest-guided artificial bee colony algorithm for numerical function optimization[J]. Applied Mathematics and Computation, 2010, 217(7): 3166-3173. DOI:10.1016/j.amc.2010.08.049.

[15] 王志剛. 一種改進(jìn)搜索策略的人工蜂群算法[J]. 計(jì)算機(jī)仿真, 2014, 31(10): 291-295. DOI:10.3969/j.issn.1006-9348.014.10.062.

WANG Zhigang. Artificial bee colony algorithm with modified search strategy[J]. Computer Simulation, 2014, 31(10): 291-295. DOI:10.3969/j.issn.1006-9348.014.10.062.(in Chinese)