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

馬航航，沈慧娟

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

一、引言

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

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

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

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

（1）依據(jù)實(shí)際問(wèn)題對(duì)蜂群的尋優(yōu)空間以及對(duì)食物源的最大停滯次數(shù)limit進(jìn)行確定，按式（1）對(duì)食物源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）的方式對(duì)食物源迭代更新：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

同時(shí)，為了驗(yàn)證INABC算法的性能優(yōu)勢(shì)，選擇NABC算法進(jìn)行性能對(duì)比，關(guān)于INABC算法和NABC算法的參數(shù)設(shè)置保持一致，食物源個(gè)數(shù)SN=100，limit=0.6×SN×D，D為具體問(wèn)題的搜索維度，鄰域半徑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é)果更具客觀性，使算法對(duì)每一個(gè)函數(shù)的尋優(yōu)求解獨(dú)立運(yùn)行30次，以30次實(shí)驗(yàn)結(jié)果的平均值和方差作為標(biāo)準(zhǔn)進(jìn)行對(duì)比，對(duì)比結(jié)果如表2所示。

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

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

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

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

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

五、結(jié)論

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