鄰域搜索策略人工蜂群算法的改進(jìn)

馬航航，沈慧娟

（甘肅廣播電視大學(xué) a.信息中心；b.理工農(nóng)醫(yī)學(xué)院，甘肅 蘭州 730030

一、引言

受生物信息啟發(fā)而發(fā)展起來的群智能算法[1]是一類重要的元啟發(fā)式算法，以其獨(dú)特的優(yōu)點(diǎn)和機(jī)制逐漸成為求解復(fù)雜非線性優(yōu)化問題的一個熱門和重要領(lǐng)域。受到蜜蜂群體覓食行為的啟發(fā)，2005年，Karaboga提出了一種新的群體智能算法——人工蜂群算法（Artificial Bee Colony，ABC）[2]，文獻(xiàn)[3-6]通過一系列的測試函數(shù)證明了ABC算法具有比遺傳算法（GA）[7]、混合蛙跳算法（SFLA）[8]、差分進(jìn)化（DE）算法[9]和粒子群（PSO）算法[10]更優(yōu)秀的收斂性能。然而，ABC算法雖然能夠保證一定的全局搜索能力，但是其在精細(xì)化搜索能力方面還有待改進(jìn)。針對此問題，文獻(xiàn)[11]基于群體最優(yōu)個體改變了ABC算法的進(jìn)化迭代公式，提高了算法的局部搜索能力；文獻(xiàn)[12]基于DE算法思想，通過蜜蜂群體對當(dāng)前最優(yōu)食物源的精細(xì)化搜索，提出了一種新的人工蜂群算法；文獻(xiàn)[13]提出一種帶共享因子改進(jìn)的人工蜂群算法，通過調(diào)節(jié)因子的動態(tài)調(diào)整使算法在全局搜索和局部搜索方面得到了均衡；文獻(xiàn)[14]受到PSO算法的思想啟發(fā)，使算法的進(jìn)化過程考慮了當(dāng)前最優(yōu)個體的啟發(fā)信息，增加了算法搜索的傾向性；文獻(xiàn)[15]根據(jù)自然界生物鄰域規(guī)則，提出了一種基于鄰域最優(yōu)食物源啟發(fā)信息的ABC算法（NABC），提高了人工蜂群算法的收斂速度和收斂精度。不同于文獻(xiàn)[11-14]只是對群體進(jìn)化公式的改進(jìn)，文獻(xiàn)[15]在環(huán)形結(jié)構(gòu)的基礎(chǔ)上，確定食物源鄰域半徑（算法進(jìn)化過程中，鄰域半徑保持不變），基于食物源鄰域內(nèi)最優(yōu)個體方向信息改進(jìn)了食物源的進(jìn)化方法，使算法能夠以更大的概率發(fā)現(xiàn)更為優(yōu)秀的食物源。相比文獻(xiàn)[11-14]的研究成果，文獻(xiàn)[15]提出的鄰域搜索策略人工蜂群算法在全局搜索能力和深度搜索能力方面同時得到了提高，算法性能相對更高，然而其迭代進(jìn)化公式只是利用了鄰域最優(yōu)個體的方向信息進(jìn)行啟發(fā)，并沒有對鄰域最優(yōu)食物源本身的周圍進(jìn)行搜索，使算法在收斂速度方面仍然具有提升的空間。文獻(xiàn)[12]研究表明，通過對蜂群最優(yōu)食物源的精細(xì)化搜索，可以有效提高算法的搜索效率，因此，本文將進(jìn)一步基于此進(jìn)化思想，對鄰域搜索策略人工蜂群算法的進(jìn)化公式進(jìn)行改進(jìn)（INABC），以期使算法的收斂性能得到進(jìn)一步改善。

二、領(lǐng)域搜索策略的人工蜂群算法（NABC）

在NABC算法中，蜂群由雇傭蜂、觀察蜂和偵察蜂三種蜜蜂構(gòu)成。雇傭蜂在發(fā)現(xiàn)新的食物源時，每一個雇傭蜂每次只能開采一個食物源，同樣每一個食物源每次也只能被一只雇傭蜂開采；進(jìn)一步，雇傭蜂通過與觀察蜂對食物源的共享，增加了算法的開采深度，觀察蜂則會以更大的概率對更加優(yōu)秀的食物源進(jìn)行搜索，在此過程中，蜜源更為豐富的食物源將會有可能吸引多只觀察蜂對其開采進(jìn)化，其也意味著較差的食物源將有可能不會被觀察蜂所開采；當(dāng)一個食物源在連續(xù)的limit次都沒有被蜂群所進(jìn)化時，偵察蜂負(fù)責(zé)丟棄多次沒有被進(jìn)化的食物源并隨機(jī)產(chǎn)生一個新的食物源，如此能夠避免算法陷入局部最優(yōu)。在算法尋優(yōu)求解過程中，食物源是對求解問題潛在解的一種描述，蜜源是對該食物源的適應(yīng)值大小的表示。如果優(yōu)化問題為一個D維空間求解問題，則食物源集合可表示為

x={xi=（xi1，xi2，…，xiD）｜i=1，2…，SN}，SN表示食物源個數(shù)，雇傭蜂、觀察蜂以及食物源的數(shù)量保持一致。當(dāng)雇傭蜂對食物源完成一次開采進(jìn)化后，觀察蜂將會對較為優(yōu)秀的食物源進(jìn)行再次開采，在此過程中，觀察蜂將會依據(jù)輪盤賭規(guī)則選擇所要依附的食物源，是算法的局部搜索能力的一種體現(xiàn)；如果停滯次數(shù)最大的食物源未在連續(xù)的limit次內(nèi)沒有被蜂群所進(jìn)化，偵察蜂將采用隨機(jī)搜索的方式在全局范圍內(nèi)產(chǎn)生一個新的食物源代替此食物源，從而增加了算法跳出局部最優(yōu)的能力。NABC算法的詳細(xì)流程可描述如下：

（1）依據(jù)實(shí)際問題對蜂群的尋優(yōu)空間以及對食物源的最大停滯次數(shù)limit進(jìn)行確定，按式（1）對食物源x={xi=（xi1，xi2，…，xiD）｜i=1，2…，SN}隨機(jī)初始化：

式（1）中，i=1，2…，SN，j=1，2…，D，maxj和minj為搜索空間第j維的上下限，rand（0，1）為（0，1）之間的隨機(jī)數(shù)，其服從均勻分布。

（2）雇傭蜂以式（2）的方式對食物源迭代更新：

圖1 xi的鄰域最優(yōu)食物源的選擇

在圖1中，r表示xi的鄰域半徑，NABC算法的思想主要體現(xiàn)在算法進(jìn)化開始時，將所有食物源按照隨機(jī)的次序排成一個環(huán)形結(jié)構(gòu)，并且在尋優(yōu)過程中此結(jié)構(gòu)始終保持不變。相較標(biāo)準(zhǔn)ABC算法，NABC算法的食物源進(jìn)化將會受到其自身鄰域內(nèi)最優(yōu)食物源的引導(dǎo)啟發(fā)，并且每一個食物源的鄰域構(gòu)成也是不同的，使算法的全局搜索能力能夠得以保證。同時，當(dāng)前最優(yōu)食物源將會引導(dǎo)其鄰域內(nèi)的非最優(yōu)食物源向其自身搜索，通過非最優(yōu)食物源的不斷改善，從而使其能夠引導(dǎo)其它食物源的進(jìn)化尋優(yōu)，為其它食物源提供了當(dāng)前最優(yōu)食物源的方向信息，使算法的深度搜索能力同時也能夠得到保證。

（3）按照式（3）計(jì)算所有食物源的選擇概率：

式（3）中，fiti和fitj分別表示第i和第j個食物源的適應(yīng)值；pi為第i個食物源的選擇概率。如果一個食物源的適應(yīng)值越大，則其被觀察蜂選擇依附的概率也就越大。

（4）觀察蜂采用輪盤賭規(guī)則選擇一個食物源按式（2）搜索新的食物源。同樣，對于觀察蜂發(fā)現(xiàn)的新食物源依據(jù)貪婪規(guī)則決定是否對其保留。

（5）判斷停滯次數(shù)最大的食物源的停滯次數(shù)是否大于最大停滯次數(shù)limit，如果大于limit，則由偵查蜂在全局空間內(nèi)隨機(jī)搜索一個新的食物源代替停滯次數(shù)最大的食物源，否則轉(zhuǎn)至步驟（6）。

（6）判斷結(jié)束條件是否滿足，不滿足則轉(zhuǎn)步驟（2）繼續(xù)迭代。

三、領(lǐng)域搜索策略人工蜂群算法的改進(jìn)（INABC）

在NABC算法中，蜂群在搜索新的食物源時，鄰域最優(yōu)食物源將會為其提供一定的方向信息，啟發(fā)雇傭蜂和觀察蜂朝著鄰域最優(yōu)食物源的方向搜索，如此機(jī)制即保證了食物源搜索具有一定的傾向性，同時也避免了蜂群陷入局部最優(yōu)。然而，NABC算法的鄰域機(jī)制保證了不同的食物源具有不同的鄰域構(gòu)成，說明通過算法本身的框架結(jié)構(gòu)就可以使其具有較為優(yōu)秀的全局搜索能力，雖然通過鄰域最優(yōu)食物源的啟發(fā)，使蜂群的迭代進(jìn)化在全局和局部搜索能力方面都有所兼顧，但是從算法的整體搜索能力方面分析可以看出，算法的全局搜索能力有較大幅度的提升，但是深度搜索能力方面仍然有所不足。文獻(xiàn)[12]研究表明，使蜜蜂群體通過對當(dāng)前最優(yōu)食物源的周圍進(jìn)行搜索，可以有效提高算法的尋優(yōu)深度和尋優(yōu)速度。受此思想啟發(fā)，本文結(jié)合NABC算法本身的結(jié)構(gòu)特點(diǎn)，特對蜂群的迭代進(jìn)化方式進(jìn)行改進(jìn)，改進(jìn)后的算法簡稱INABC。進(jìn)化方式改進(jìn)如式（4）所示：

式（4）中，所有參數(shù)代表的意義同式（2）。將式（4）與式（2）對比可以看出，INABC算法將使雇傭蜂和觀察蜂始終在鄰域最優(yōu)食物源周圍進(jìn)行搜索，有效提升了算法的精細(xì)化搜索能力和尋優(yōu)速度，而NABC算法只是通過鄰域最優(yōu)食物源提供了方向信息，兩者具有一定的區(qū)別，同時，不同食物源具有不同的鄰域構(gòu)成，如此將使INABC算法的全局和局部搜索能力方面同時得到提升。IN?ABC算法的詳細(xì)流程如下所述：

（1）采用式（1）所示方法對食物源初始化，并對最大停滯次數(shù)limit和算法的鄰域半徑r賦初值；

（2）將所有食物源按照隨機(jī)的次序排成一個環(huán)形結(jié)構(gòu)；

（3）雇傭蜂搜索的偽代碼：

（5）偵察蜂尋找停滯次數(shù)最大的食物源，如果其停滯次數(shù)大于limit，則通過隨機(jī)搜索的方法搜索一個新的食物源代替此食物源，否則轉(zhuǎn)至步驟（6）。

（6）判斷結(jié)束條件是否滿足，不滿足則轉(zhuǎn)步驟（3）繼續(xù)進(jìn)化迭代。

四、實(shí)驗(yàn)測試

為了分析INABC算法的收斂性能，本文采用文獻(xiàn)[11-15]中的8個60維的測試函數(shù)對INABC算法進(jìn)行實(shí)驗(yàn)分析，各函數(shù)的表達(dá)式、尋優(yōu)空間以及理論最優(yōu)值如表1所示。

同時，為了驗(yàn)證INABC算法的性能優(yōu)勢，選擇NABC算法進(jìn)行性能對比，關(guān)于INABC算法和NABC算法的參數(shù)設(shè)置保持一致，食物源個數(shù)SN=100，limit=0.6×SN×D，D為具體問題的搜索維度，鄰域半徑r=30。

設(shè)定全局迭代次數(shù)G=5000為兩種算法搜索的結(jié)束條件，所有實(shí)驗(yàn)均在內(nèi)存為4G，處理器In?tel（R）Core i5-3750 3.40GHz計(jì)算機(jī)上，采用VC++6.0實(shí)現(xiàn)。為了使實(shí)驗(yàn)結(jié)果更具客觀性，使算法對每一個函數(shù)的尋優(yōu)求解獨(dú)立運(yùn)行30次，以30次實(shí)驗(yàn)結(jié)果的平均值和方差作為標(biāo)準(zhǔn)進(jìn)行對比，對比結(jié)果如表2所示。

從以上結(jié)果可以看出，在優(yōu)化f4和f6時，IN?ABC算法和NABC算法同時獲得了理論最優(yōu)解，而對其它函數(shù)優(yōu)化時，INABC算法獲得了比NABC算法更優(yōu)秀的結(jié)果，而且在優(yōu)化f3時，IN?ABC算法獲得了理論最優(yōu)解，NABC算法卻沒有獲得最優(yōu)解，說明INABC算法優(yōu)勢較為明顯。這是因?yàn)镮NABC算法在進(jìn)化計(jì)算時，雇傭蜂和觀察蜂對食物源進(jìn)化時，總是能夠在其鄰域內(nèi)最優(yōu)食物源的周圍附近進(jìn)行搜索，迅速使食物源的質(zhì)量得到了提高，并且由于當(dāng)前最優(yōu)食物源對其鄰域內(nèi)非最優(yōu)食物源質(zhì)量的改善，這些被改善的食物源將會逐步引導(dǎo)其它食物源在其周圍附近進(jìn)行搜索尋優(yōu)，如此機(jī)制將使算法的尋優(yōu)速度和尋優(yōu)能力同時得到保證。同時由于各食物源的鄰域構(gòu)成是不同的，避免了群體全部收斂于某一局部最優(yōu)解，另外，結(jié)合偵查蜂的隨機(jī)搜索，使算法收斂效率得到提升的同時，算法的全局尋優(yōu)能力仍然能夠得到保證。為了比較兩種算法對各函數(shù)尋優(yōu)求解時的收斂速度，兩種算法對各函數(shù)30次的平均收斂過程如圖2所示。

表1 測試函數(shù)

表2 兩種算法的實(shí)驗(yàn)結(jié)果對比

圖2 兩種算法對各函數(shù)30次收斂的平均過程

從兩種算法對各函數(shù)的平均收斂過程可以看出，隨著算法迭代次數(shù)的變化，INABC算法總能夠以較快的速度發(fā)現(xiàn)比NABC算法更好的解，這是因?yàn)镮NABC算法在鄰域內(nèi)最優(yōu)食物源的周圍搜索，迅速使食物源的解的質(zhì)量得到了改善，并且算法的精細(xì)化搜索能力也得到了明顯的提升，從而使算法的尋優(yōu)效率更高，對比結(jié)果說明，本文提出的進(jìn)化策略相比NABC算法更加高效。

五、結(jié)論

針對NABC算法在深度搜索能力方面存在的不足，本文通過對該算法的迭代進(jìn)化公式進(jìn)行改進(jìn)，提出了INABC算法，使觀察蜂和雇傭蜂總是能夠在鄰域最優(yōu)食物源附近進(jìn)行搜索，使食物源的質(zhì)量迅速得到了提升，有效改善了算法的深度搜索能力和精細(xì)化搜索能力。為了對比說明IN?ABC算法的性能優(yōu)勢，采用常用的7個60維測試函數(shù)進(jìn)行實(shí)驗(yàn)分析，分析結(jié)果顯示本文對算法的改進(jìn)是有效的，INABC算法在函數(shù)優(yōu)化時具有比NABC算法更高的收斂效率。