基于行動(dòng)軌跡的人工蜂群算法

何 堯， 郭文忠， 劉耿耿， 張順淼

(1. 福建工程學(xué)院信息科學(xué)與工程學(xué)院， 福建 福州 350118； 2. 福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院， 福建 福州 350116)

0 引言

人工蜂群(artificial bee colony, ABC)算法由土耳其學(xué)者Karaboga[1]于2005年提出， 是受蜂群采蜜行為啟發(fā)而來的群智能算法， 用于解決單?；蚨嗄５膬?yōu)化問題. 由于它操作簡(jiǎn)單， 控制參數(shù)少， 魯棒性和探索能力強(qiáng)， 受到了很多學(xué)者的關(guān)注. ABC目前已成熟應(yīng)用到了數(shù)據(jù)挖掘[2-4]、 神經(jīng)網(wǎng)絡(luò)[5-6]、 圖像處理[7-9]等多個(gè)領(lǐng)域.

眾所周知， 一個(gè)好的優(yōu)化算法需要平衡全局探索能力和局部搜索能力， 而ABC有著較強(qiáng)的全局探索能力， 但局部搜索能力較弱， 收斂速度較慢. 因此， 有相當(dāng)一部分研究是用于改善ABC的局部搜索能力. 文獻(xiàn)[10]采用鄰域搜索機(jī)制， 從當(dāng)前蜜源的環(huán)形鄰域拓?fù)浣Y(jié)構(gòu)中選擇較優(yōu)的鄰居蜜源進(jìn)行開采， 以平衡算法的探索與開采能力. 文獻(xiàn)[11]在標(biāo)準(zhǔn)ABC的基礎(chǔ)上添加方向信息， 提出基于方向的人工蜂群算法(directed artificial bee colony, DABC). 它用一個(gè)二維數(shù)組來保存每個(gè)解的每個(gè)維度的方向信息， 用來指導(dǎo)該維度參與下次蜜源開采的方向. 文獻(xiàn)[12]結(jié)合ABC和粒子群優(yōu)化算法(particle swarm optimization, PSO)的特點(diǎn)， 提出了基于全局最優(yōu)的ABC算法(gbest-guided artificial bee colony, GABC)， 在方案更新時(shí)不僅參考鄰域蜜源， 還以全局最優(yōu)解做指導(dǎo). 以上研究大大推動(dòng)人工蜂群的發(fā)展， 但在標(biāo)準(zhǔn)ABC及大部分改進(jìn)算法中， 開采蜜源的策略具有較大的隨意性， 隨機(jī)選擇解維度、 方向和開采步伐， 完全忽略以往的搜索經(jīng)驗(yàn). 對(duì)此本研究提出的基于行動(dòng)軌跡的蜂群算法(enhanced directed artificial bee colony, EDABC)， 記錄下蜜蜂在找尋新蜜源時(shí)的行動(dòng)軌跡， 該信息不僅保存蜜蜂在每個(gè)蜜源的每個(gè)維度開采成功的方向， 還保留了在該維度開采的連續(xù)失敗次數(shù)， 并以此來確定下次蜜蜂在該維度開采時(shí)的方向、 頻率和步伐， 從而加快算法的收斂速度， 最后將EDABC在函數(shù)優(yōu)化問題上進(jìn)行了仿真實(shí)驗(yàn).

1 標(biāo)準(zhǔn)人工蜂群算法

在ABC算法里， 所有的蜜蜂劃分為三組： 雇傭蜂、 跟隨蜂、 探索蜂. 雇傭蜂和跟隨蜂各占蜂群總數(shù)的一半. 雇傭蜂負(fù)責(zé)勘探蜜源并分享信息， 跟隨蜂跟隨雇傭蜂去采蜜， 當(dāng)蜜源被開采殆盡后， 探索蜂出動(dòng)尋找新蜜源. 其中， 每個(gè)蜜源的位置代表優(yōu)化問題的一個(gè)可行解， 初始化時(shí)隨機(jī)產(chǎn)生SN個(gè)蜜源(均勻分布)， 每個(gè)蜜源用xi(i=1, 2, …,SN)表示， D代表優(yōu)化問題維數(shù). 在對(duì)蜂群和蜜源進(jìn)行初始化后， ABC算法反復(fù)執(zhí)行三個(gè)過程： 雇傭蜂階段、 跟隨蜂階段、 探索蜂階段來尋找問題的最優(yōu)解. 每個(gè)階段現(xiàn)描述如下：

1) 雇傭蜂階段. 在雇傭蜂階段， 基于以下公式對(duì)蜜源進(jìn)行開采， 尋找新蜜源， 并利用貪婪算法留下更優(yōu)解.

vij=xij+φij(xij-xkj)

(1)

其中:vij表示vi中第j個(gè)緯度(vi是在蜜源xi附近搜索出來的新蜜源);k∈{1, 2, …,SN},j∈{1, 2, …, D}隨機(jī)生成， 且k≠i;φij是一個(gè)取值在[-1, 1]之間的隨機(jī)值.

2)跟隨蜂階段. 雇傭蜂勘探蜜源后在舞蹈區(qū)分享蜜源信息. 跟隨蜂基于花蜜量(適應(yīng)值)以某種策略(標(biāo)準(zhǔn)ABC采用輪盤賭策略， 以實(shí)現(xiàn)蜜源的適應(yīng)值越高， 被觀察蜂選中的概率越高)選擇某個(gè)蜜源進(jìn)行跟蹤開采， 開采過程與雇傭蜂相同.

3)探索蜂階段(scout bee phase). 如果經(jīng)過多次迭代后， 某個(gè)蜜源不被更新次數(shù)超過了預(yù)定閾值limit， 那么需拋棄該蜜源， 啟動(dòng)探索蜂階段. 探索蜂利用公式(2)隨機(jī)尋找新的解決方案來代替被拋棄的舊方案.

xij=xmin j+rand[0, 1](xmax j-xmin j)

(2)

其中， minj和maxj分別代表第j個(gè)維度取值的最小值和最大值.

2 DABC和GABC

DABC[11]是在ABC的基礎(chǔ)上添加了方向信息， 讓蜜蜂有方向地開采新的蜜源從而加快ABC的收斂速度. 具體見公式(3)：

(3)

式(3)中： abs代表取絕對(duì)值函數(shù);dij代表第i解第j維的方向信息， 由它來指導(dǎo)開采新蜜源的方向， 它的取值是由上一次開采時(shí)第j維的變化而定;φij是一個(gè)取值在[-1, 1]之間的隨機(jī)值;rij是一個(gè)取值為[0, 1]之間的隨機(jī)值.

受PSO啟發(fā)， 文獻(xiàn)[12]提出了GABC算法， 修改了標(biāo)準(zhǔn)ABC的公式(2)， 加入最優(yōu)解去引領(lǐng)蜜源開采， 具體見公式(4):

vij=xij+φij(xij-xkj)+ψij(yj-xij)

(4)

其中:yj是最優(yōu)解的第j維度值；φij為[-1， 1]的隨機(jī)數(shù)；ψij為取值[0，C]的隨機(jī)數(shù)；C是個(gè)非負(fù)常量.

3 基于行動(dòng)軌跡的人工蜂群算法

標(biāo)準(zhǔn)ABC算法對(duì)蜜源的開采， 具有較大的隨意性， 沒有積累以往的開采經(jīng)驗(yàn). 改進(jìn)算法DABC只記錄了蜜源開采時(shí)的每個(gè)維度的部分信息——方向， 而對(duì)其它有益信息沒有記錄. 對(duì)此可以在不影響DABC算法空間復(fù)雜度的情況下， 讓DABC算法里的參數(shù)dij保存更多蜜蜂開采的軌跡信息，dij的取值由公式(5)所示：

(5)

(6)

在公式(6)中， 新蜜源的產(chǎn)生根據(jù)方向的不同采取不同的策略. 其中φij代表[-1， +1]的隨機(jī)數(shù)，rij和ψij都代表[0， 1]的隨機(jī)數(shù)，yj代表全局最優(yōu)解，dijmod 10用來求dij的個(gè)位， 即方向信息. 用dij中記錄的連續(xù)開采失敗次數(shù)來調(diào)整步長(zhǎng)因子s1和s2， 這兩個(gè)因子分別控制了局部尋優(yōu)和全局尋優(yōu)的能力. 設(shè)置較大的s1, 會(huì)使蜂群發(fā)生過多的局部搜索， 而設(shè)置較大的s2, 將增強(qiáng)蜂群的開采能力. 當(dāng)蜂群有明確的方向時(shí)(方向信息為1或2)， 較大的s1和較小的s2將使蜂群盡量發(fā)散搜索空間， 擴(kuò)大搜索范圍， 增加種群的多樣性. 而當(dāng)蜜蜂沒有明確的方向(方向信息為3)， 且連續(xù)多次開采失敗， 采用較小的s1和較大的s2， 有利于收斂到全局最優(yōu)解. 具體見公式(7)

(7)

式中:smax為一個(gè)常數(shù)， 負(fù)責(zé)平衡s1和s2的取值;cmax為一個(gè)固定常量， 當(dāng)該維度影響值超過cmax時(shí)， 則以一定概率用下一維度替換該維度， 以保證減少該維度參與更新的頻率. 具體算法描述如下：

1) 初始化階段.

隨機(jī)產(chǎn)生SN個(gè)蜜源xij,i=1, …,SN;j=1, …， D.

初始化軌跡信息d， 設(shè)置每個(gè)蜜源的每個(gè)維度的初始值為0.

2) 反復(fù)執(zhí)行以下三個(gè)階段， 直到達(dá)到最大循環(huán)次數(shù)(或者其他終止條件).

雇傭蜂階段：

利用公式(6)開采新蜜源， 并計(jì)算適應(yīng)值.

根據(jù)貪婪算法， 如果新蜜源的適應(yīng)值優(yōu)于原蜜源， 則保留新蜜源.

根據(jù)公式(5)設(shè)置新的軌跡信息.

跟隨蜂階段：

跟隨蜂根據(jù)每個(gè)蜜源的適應(yīng)值采用輪盤賭算法決定是否跟蹤開采xi， 開采過程與雇傭蜂開采過程相同.

當(dāng)發(fā)現(xiàn)有被拋棄蜜源時(shí)， 執(zhí)行探索蜂階段：

探索蜂拋棄該蜜源， 根據(jù)公式(2)隨機(jī)找出全新蜜源代替原來被拋棄的蜜源， 并計(jì)算新蜜源的適應(yīng)值.

重新設(shè)置該蜜源的所有維度的方向信息為0，dij=0,i∈[1, …,SN],j∈[1, …, D].

歷史最優(yōu)蜜源與當(dāng)前解空間里每個(gè)蜜源比較， 保留最優(yōu)蜜源.

3) 輸出最優(yōu)蜜源.

4 算法實(shí)例測(cè)試

4.1 測(cè)試函數(shù)及算法參數(shù)設(shè)置

為了檢驗(yàn)EDABC的性能， 本研究選用5個(gè)具有代表性的測(cè)試函數(shù)， 并與ABC、 DABC、 GABC進(jìn)行比較. 表1列出了5個(gè)測(cè)試函數(shù)的表達(dá)式， 最優(yōu)解和取值范圍.

表1 標(biāo)準(zhǔn)測(cè)試函數(shù)

其中, Sphere是比較簡(jiǎn)單的單峰可分函數(shù)， 容易找到最優(yōu)值. Rosebrock是單峰不可分的非凸函數(shù)， 它的極值點(diǎn)處在一個(gè)狹長(zhǎng)的拋物線形的山谷里， 且取值范圍內(nèi)走勢(shì)平坦， 難以通過梯度下降法來收斂到最優(yōu)點(diǎn). 其它的函數(shù)都是多峰函數(shù)， 可以用來測(cè)試算法的全局搜索能力， 其中Ackley是多峰不可分函數(shù)， 由于其指數(shù)項(xiàng)原因， 導(dǎo)致該函數(shù)有多個(gè)局部最優(yōu)點(diǎn). Griewank是多峰不可分函數(shù)， 它會(huì)隨著維數(shù)(D>30)的增加而失去多峰特性， 呈現(xiàn)出單峰特性. Rastrigin是多峰可分函數(shù)， 它在Sphere函數(shù)的基礎(chǔ)上添加了余弦調(diào)制， 導(dǎo)致其有多個(gè)局部最小值. 這五個(gè)函數(shù)分別代表了尋優(yōu)問題的不同形式和難度， 被廣泛地用來檢測(cè)算法的性能. 表2列出了算法參數(shù)設(shè)置.

表2 參數(shù)設(shè)置

其中GABC的C參照文獻(xiàn)[12]為1.5， EDABC 中smax=2.0,cmax=20為經(jīng)驗(yàn)值. limit的取值由公式(8)計(jì)算[13]而得：

limit=SN×D

(8)

4.2 結(jié)果與分析

圖1 F1函數(shù)動(dòng)態(tài)尋優(yōu)過程(30維)Fig.1 The convergence graph of the methods on the Sphere function(30-D)

依據(jù)前述的參數(shù)設(shè)置， 分別對(duì)EDABC與標(biāo)準(zhǔn)ABC、 DABC、 GABC各運(yùn)行了30遍， 見圖1～5所示， 各算法在各函數(shù)的迭代尋優(yōu)過程.實(shí)驗(yàn)結(jié)果如表3所示.

從圖1和表3可看出， 由于Sphere函數(shù)比較簡(jiǎn)單， 所有算法對(duì)其尋優(yōu)結(jié)果精度都比較高， 并能穩(wěn)步收斂. 三個(gè)改進(jìn)算法無論從精度和穩(wěn)定性來看， 都明顯優(yōu)于原ABC算法， 其中， EDABC精度最高， 并且收斂速度最快. 而對(duì)于更難的Rosebrock函數(shù)， 所有算法精度明顯沒有Sphere函數(shù)的高， 從圖2可發(fā)現(xiàn)， 以最優(yōu)解引領(lǐng)的GABC算法過早收斂. 雖然EDABC在該函數(shù)的上精度要比其他算法更高， 但同時(shí)它的標(biāo)準(zhǔn)偏差較大， 即穩(wěn)定性較差. 剩下三個(gè)用來測(cè)試全局搜索能力的多峰函數(shù)， EDABC無論從精度和穩(wěn)定性來說， 都表現(xiàn)出眾， 其中， 通過圖5 Rastrigin函數(shù)的尋優(yōu)過程可看出， EDABC表現(xiàn)尤為突出， 具有更強(qiáng)的全局搜索能力， 能快速地跳出局部最優(yōu)解.

圖2 F2函數(shù)動(dòng)態(tài)尋優(yōu)過程(30維)Fig.2 The convergence graph of the methods on the Rosenbrock function(30-D)

圖3 F3函數(shù)動(dòng)態(tài)尋優(yōu)過程(30維)Fig.3 The convergence graph of the methods on the Ackley function(30-D)

圖4 F4函數(shù)動(dòng)態(tài)尋優(yōu)過程(30維)Fig.4 The convergence graph of the methods on the Griewank function(30-D)

圖5 F5函數(shù)動(dòng)態(tài)尋優(yōu)過程(30維)Fig.5 The convergence graph of the methods on the Rastrigin function(30-D)

函數(shù)名稱評(píng)價(jià)指標(biāo)ABCDABCGABCEDABCF1-Sphere最優(yōu)值7．46×10-126．32×10-164．72×10-163．71×10-18最差值6．50×10-101．17×10-159．70×10-167．53×10-16平均值8．74×10-118．39×10-167．58×10-165．54×10-16標(biāo)準(zhǔn)偏差1．24×10-108．26×10-167．45×10-168．64×10-17F2-Rosenbrock最優(yōu)值10．04741．68537．79010．6945最差值27．623026．145727．546419．7531平均值20．153810．498221．52487．4061標(biāo)準(zhǔn)偏差4．284310．32364．38537．2902F3-Ackley最優(yōu)值5．54×10-61．37×10-86．81×10-91．93×10-10最差值6．35×10-53．45×10-74．36×10-88．69×10-10平均值2．47×10-59．55×10-82．40×10-84．61×10-10標(biāo)準(zhǔn)偏差1．23×10-59．45×10-82．36×10-81．66×10-10F4-Griewank最優(yōu)值2．50×10-145．55×10-164．85×10-162．34×10-17最差值2．168×10-129．99×10-169．99×10-168．88×10-16平均值6．67×10-137．55×10-167．179×10-165．77×10-16標(biāo)準(zhǔn)偏差5．76×10-137．430×10-167．077×10-161．01×10-16

續(xù)表3

注：各指標(biāo)最優(yōu)值用黑體表示

5 結(jié)語

在ABC算法中， 跟隨蜂在蜜源附近隨意開采， 沒有利用以往搜索經(jīng)驗(yàn)， 為此， 本研究結(jié)合DABC和GABC算法特征, 記錄蜜蜂開采行為的行動(dòng)軌跡， 并以此為經(jīng)驗(yàn)指引蜜蜂下一次開采， 以提高ABC搜索能力. 通過對(duì)5個(gè)標(biāo)準(zhǔn)函數(shù)的尋優(yōu)測(cè)試并與ABC、 DABC、 GABC比較， 實(shí)驗(yàn)結(jié)果表明， 該算法能有效提高ABC的性能， 并具有良好的穩(wěn)定性和魯棒性.

EDABC算法能記錄不同維度對(duì)尋優(yōu)的貢獻(xiàn)度并采取不同的更新頻率和幅度的特性， 更適合解決不確定模型的尋優(yōu)問題， 下一步工作將考慮把EDABC應(yīng)用到復(fù)雜的組合優(yōu)化問題和具體應(yīng)用中， 提出性能更好的全局優(yōu)化算法.

參考文獻(xiàn)：

[1] KARABOGA D. An idea based on honey bee swarm for numerical optimization[R]. Kayser： Erciyes University, Engineering Faculty, Computer Engineering Department, 2005.

[2] OZTURK C, HANCER E, KARABOGA D. Dynamic clustering with improved binary artificial bee colony algorithm[J]. Applied Soft Computing, 2015, 28: 69-80.

[3] CELIK M, KOYLU F, KARABOGA D. CoABCMiner: an algorithm for cooperative rule classification system based on artificial bee colony[J]. International Journal on Artificial Intelligence Tools, 2016, 25(1): 1550028(1-50).

[4] 朱冰蓮, 朱方方, 段青言, 等. 采用多策略離散人工蜂群的改進(jìn)頻譜分配算法[J]. 西安交通大學(xué)學(xué)報(bào), 2016, 50(2): 20-25.

[5] KARABOGA D, KAYA E. An adaptive and hybrid artificial bee colony algorithm (aABC) for ANFIS training[J]. Applied Soft Computing, 2016, 49: 423-436.

[6] MENON N, RAMAKRISHNAN R. Brain tumor segmentation in MRI images using unsupervised artificial bee colony algorithm and FCM clustering[C]// IEEE International Conference on Communications and Signal Processing. [S.l.]: IEEE, 2015: 6-9.

[7] BHANDARI A K, KUMAR A, SINGH G K. Modified artificial bee colony based computationally efficient multilevel thresholding for satellite image segmentation using Kapur’s, Otsu and Tsallis functions[J]. Expert Systems with Applications, 2015, 42(3): 1573-1601.

[8] ALI M, AHN C W, PANT M,etal. An image watermarking scheme in wavelet domain with optimized compensation of singular value decomposition via artificial bee colony[J]. Information Sciences, 2015, 301: 44-60.

[9] DERICHE R, FIZAZI H. The artificial bee colony algorithm for unsupervised classification of meteorological satellite images[J]. International Journal of Computer Applications, 2015, 112(12): 44-60.

[10] 周新宇, 吳志健, 鄧長(zhǎng)壽, 等. 一種鄰域搜索的人工蜂群算法[J]. 中南大學(xué)學(xué)報(bào)(自然科學(xué)版)， 2015, 46(2): 534-546.

[11] KIRAN M S, FINDIK O. A directed artificial bee colony algorithm[J]. Applied Soft Computing, 2015, 26(C): 454-462.

[12] ZHU G P. Gbest- guided artificial bee colony algorithm for numerical function optimization[J] . Applied mathematics and Computation, 2010, 217(7): 3166 -3173.

[13] KARABOGA D, AKAY B. A comparative study of artificial bee colony algorithm[J]. Applied mathematics and Computation, 2009, 214(1): 108-132.