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

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

0 引言

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

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

1 標準人工蜂群算法

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

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

vij=xij+φij(xij-xkj)

(1)

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

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

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

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

(2)

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

2 DABC和GABC

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

(3)

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

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

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

(4)

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

3 基于行動軌跡的人工蜂群算法

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

(5)

(6)

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

(7)

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

1) 初始化階段.

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

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

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

雇傭蜂階段：

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

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

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

跟隨蜂階段：

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

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

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

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

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

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

4 算法實例測試

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

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

表1 標準測試函數(shù)

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

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

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

limit=SN×D

(8)

4.2 結(jié)果與分析

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

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

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

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

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

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

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

函數(shù)名稱評價指標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標準偏差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標準偏差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標準偏差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標準偏差5．76×10-137．430×10-167．077×10-161．01×10-16

續(xù)表3

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

5 結(jié)語

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

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

參考文獻：

[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]. 西安交通大學學報, 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] 周新宇, 吳志健, 鄧長壽, 等. 一種鄰域搜索的人工蜂群算法[J]. 中南大學學報(自然科學版)， 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.