劉曉芳 柳培忠 黃德天 鄭 洋 黃煒欽

?

一種改進的人工蜂群算法*

劉曉芳 柳培忠 黃德天 鄭 洋 黃煒欽

華僑大學(xué)工學(xué)院

人工蜂群算法是一種模擬蜜蜂群智能搜索行為的隨機優(yōu)化算法，已被成功用于解決許多優(yōu)化問題。該文針對基本人工蜂群算法在收斂速度和局部尋優(yōu)方面存在的缺點，提出了一種具有平衡能力的改進算法。此算法在觀察蜂階段引入慣性權(quán)重，使用隨著迭代次數(shù)動態(tài)變化的慣性權(quán)重因子來平衡種群的局部搜索和全局探測能力，防止算法陷入局部最優(yōu)和加快尋優(yōu)速度；在偵察蜂階段（scout bees），則利用正弦函數(shù)搜索操作，正弦函數(shù)服從均勻分布，能很好地搜索全部范圍，以提高種群多樣性。通過對5個基準測試函數(shù)進行仿真實驗，并與原算法進行比較，結(jié)果表明，改進的算法在收斂速度和搜索精度上基本優(yōu)于人工蜂群算法。

人工蜂群算法 算法改進 慣性權(quán)重因子 正弦搜索 收斂性

1 概述

人工蜂群算法（Artificial Bee Colony，ABC）[1,2]是土耳其學(xué)者Karaboga等人在2005年提出的一種比較新的群智能算法，它是模擬蜜蜂群體尋找優(yōu)良食物源的方法，與遺傳算法、粒子群算法、蟻群算法等智能計算方法相比，該算法的突出優(yōu)點是在每次迭代中都進行全局和局部搜索、控制參數(shù)少、易于實現(xiàn)、計算方便等。目前，人工蜂群算法的應(yīng)用研究比較廣泛，已經(jīng)從最初的函數(shù)優(yōu)化領(lǐng)域發(fā)展到訓(xùn)練神經(jīng)網(wǎng)絡(luò)、圖像分割處理、路徑優(yōu)化、數(shù)據(jù)挖掘、組合優(yōu)化、語音識別等領(lǐng)域。

但是，人工蜂群算法仍存在與其它群智能算法相同的問題，比如在搜索后期會出現(xiàn)收斂速度減慢、種群種類減少和全局搜索能力差等問題。為改善ABC算法的這些缺陷，眾多研究人員進行了改進研究。Karaboga等[3]提出了改進的ABC算法（MABC），研究了控制參數(shù)變化頻率的攝動率、縮放因子（步長）以及“l(fā)imit ”對算法的影響，并用于解決實值參數(shù)優(yōu)化問題；P.Guo等[4]受粒子群算法的啟發(fā)，在搜索方程中引入全局最優(yōu)和個體最優(yōu)信息，使得算法在尋優(yōu)過程中可以兼顧全局和局部最優(yōu)解的引導(dǎo)，進而加快算法收斂速度和解的精確度；Banharnsakun等[5]提出利用當(dāng)前全局最優(yōu)解代替隨機選取的鄰域個體，根據(jù)當(dāng)前全局最優(yōu)解的適應(yīng)度調(diào)整鄰域搜索步長，從而改善算法解的精確度和收斂速度。除此之外，有的學(xué)者把混沌搜索引入到ABC算法中，比如：Alatas[6]提出了混沌人工蜂群算法，用于全局數(shù)值優(yōu)化問題，算法中采用多種可選的混沌映射來改進算法的性能；暴勵等[6]提出了自適應(yīng)搜索空間的混沌蜂群算法，動態(tài)調(diào)整搜索空間的范圍，達到加快解的收斂速度、避免最優(yōu)解被排除在搜索空間外的效果；Gao等[8]提出一種改進ABC算法并將其用于混沌系統(tǒng)的控制和同步中，算法采用反向?qū)W習(xí)和混沌映射方法初始化種群，采用全局最優(yōu)解引導(dǎo)進行鄰域搜索過程，并通過實驗證明了方法的可行性；羅鈞等[9]提出了基于Logistic混沌搜索的蜂群優(yōu)化算法，通過混沌映射進行初始化，以提高種群多樣性，使算法可以在全局內(nèi)進行搜索；張明等[10]提出基于適應(yīng)值歐氏距離比的均衡蜂群算法，在初始化時引入混沌策略提高種群多樣性；匡芳君等[11]提出了自適應(yīng)Tent混沌搜索的ABC算法，該算法應(yīng)用Tent映射得到算法的最初解，使得初始化個體盡可能均勻分布，再動態(tài)調(diào)整混沌搜索的空間大小，用目前的最優(yōu)食物源得到Tent混沌序列，從而得到最優(yōu)解等。有的學(xué)者利用熵來改進算法，熵是不確定性的一種度量，利用熵的值來度量算法中的不確定性，通過控制熵的值達到控制算法的目的。例如：李彥蒼等[12]提出了基于信息熵的改進算法；徐雙雙等[13]提出基于平均熵的自適應(yīng)ABC算法，利用平均熵機制初始化種群，增加種群的多樣性，避免算法陷入局部最優(yōu)等。

針對基本ABC算法收斂速度慢和搜索后期種群多樣性降低的缺點，本文提出了一種改進的ABC算法，即在觀察蜂階段（onlooker bees）引入慣性權(quán)重，使用隨著迭代次數(shù)動態(tài)變化的慣性權(quán)重因子來平衡種群的局部搜索和全局探測能力，防止算法陷入局部最優(yōu)和加快尋優(yōu)速度；在偵察蜂階段（scout bees），利用正弦函數(shù)搜索操作，正弦函數(shù)服從均勻分布，能很好地搜索全部范圍，以提高種群多樣性。

2 基本人工蜂群算法

在ABC算法中，將蜜蜂分為三種類型: 雇傭蜂、觀察蜂和偵察蜂。在搜索最優(yōu)解的過程中，一個蜜源對應(yīng)問題中的一個可行解，蜂群采蜜即搜索最優(yōu)解的過程?？尚薪獾馁|(zhì)量問題由優(yōu)化問題的適應(yīng)度值決定，適應(yīng)度值與可行解的質(zhì)量成正比。

ABC算法的尋優(yōu)過程主要由以下四部分組成:

2.1 雇傭蜂搜索

位置更新公式如下:

2.2 選擇操作

ABC算法中，觀察蜂通過“貪婪”選擇策略對食物源進行選擇，選擇概率為:

其中，考慮最小化問題：

（3）

2.3 觀察蜂搜索

位置更新公式同式(1)。

2.4 偵察蜂搜索

3 平衡蜂群算法

在基本ABC算法中，蜂群之間通過個體間進行共享信息來搜索新的食物源，具有很大的不確定性，可以基本搜索到所有解空間，所以，相對而言，基本人工蜂群算法具有較強的全局搜索能力，但其對當(dāng)前找到的最優(yōu)解并沒有較強的局部搜索機制，開采與開發(fā)能力出現(xiàn)不平衡的狀況，當(dāng)算法搜索進行到后期時，種群多樣性降低，搜索效率下降，從而使收斂速度減慢。本文采取兩種方法來提高算法性能：在觀察蜂階段引入慣性權(quán)重，在偵察蜂階段利用正弦函數(shù)搜索操作。

3.1 慣性權(quán)重因子

學(xué)者Shi等人在粒子群算法的速度公式中引入慣性權(quán)重，可達到提高收斂速度的效果[14]，慣性權(quán)重可達到保持粒子運動原狀態(tài)的效果，進而可使搜索空間擴大，不至于陷入局部最優(yōu)值。因為可達到平衡開采和開發(fā)能力的效果，所以通過的動態(tài)調(diào)整來改變開采和開發(fā)能力。在進行尋找最優(yōu)解的過程中，比較好的選擇是在搜索前期有較高的開發(fā)能力從而得到較好的解，而后要有較高的局部搜索能力以達到加快尋優(yōu)的效果，因此，可將設(shè)定為遞減變化。這樣，在初始時可以實現(xiàn)廣泛的搜索，而在算法后期將搜索空間的范圍縮小，對找到局部最優(yōu)有好處，可以使得算法性能更好。由此，本文設(shè)計了如公式( 5)所示的搜索方程，實現(xiàn)開發(fā)和開采的平衡。

（6）

3.2 正弦函數(shù)搜索

在算法搜索進行到后期，可能會引起種群的多樣性降低，從而導(dǎo)致算法陷入局部最優(yōu)，所以，需要采取一種提高全局搜索的方法，以提高種群多樣性。已有文獻指出sine（）服從均勻分布，可使解的分布盡可能均勻，全面覆蓋搜索范圍[15]，并已經(jīng)成功應(yīng)用到了DE算法中且取得了良好的結(jié)果。由此，本文設(shè)計了如公式 (7) 所示的正弦函數(shù)搜索公式，達到對解空間的全局搜索。

3.3 MABC算法流程

在改進的ABC算法（MABC）中，蜜蜂總數(shù)用NP表示，解的個數(shù)（SN）等于雇傭蜂的個數(shù)。一般,SN=NP/2。用表示第i個食物源（i=1,2,...,SN；D為搜索空間的維數(shù))。

MABC算法的具體實現(xiàn)步驟如下：

步驟1）：隨機產(chǎn)生NP個解，通過公式(4)隨機產(chǎn)生可行解,記作。

步驟2）：對各個解的每一維的適應(yīng)度函數(shù)值進行求解，按從大到小排序，取前SN個解作為最初的解，剩余的蜜蜂則為觀察蜂。

步驟3）：對于每只雇傭蜂，在當(dāng)前位置的鄰域進行搜索新的位置，然后求出其適應(yīng)度值，采用貪婪選擇算法選擇，取新位置和原位置中適應(yīng)度值大的保存下來，搜索公式為公式(1)。

步驟4）：對于每只觀察蜂，按照與食物源適應(yīng)度值成比例的概率，選擇一個食物源，并在其周圍繼續(xù)搜索，搜索其他蜜源，搜索公式采用經(jīng)過改進后的公式(5)，若新產(chǎn)生的食物源適應(yīng)度值比原食物源的大，那么觀察蜂變?yōu)楣蛡蚍?，并更新食物源位置，反之，則保持原來的解不變。觀察蜂通過概率選擇公式(3)來選擇。

步驟5）：當(dāng)雇傭蜂的搜索次數(shù)到達一定閾值，limit卻一直沒有變化時，則要重新隨機得到一個新的食物源位置，采用經(jīng)改進后的公式(7)替代它。

步驟7）：判斷是否滿足停止準則：達到最大迭代次數(shù)maxCycle，若達到該條件，則停止計算并得到最優(yōu)的食物源，若沒有達到該條件，則算法要轉(zhuǎn)向步驟 2）。

4 仿真實驗與結(jié)果分析

4.1 Benchmark函數(shù)

為了測試改進人工蜂群算法（MABC）的性能，本文采用了5種經(jīng)典的benchmark functions進行測試，如表1所示。其中，F(xiàn)01是單峰函數(shù)，主要用于測試算法是否具有尋優(yōu)能力。F02是著名的經(jīng)典優(yōu)化問題，該函數(shù)是一個單峰函數(shù)，但是全局最優(yōu)在一條長而窄的拋物線形的山谷中，難以收斂到全局最優(yōu)值，并且各變量間有很強的關(guān)聯(lián)性，梯度方向不指向最優(yōu)值，所以常用來測試優(yōu)化算法的性能。F03是球函數(shù)再加余弦模型，從而產(chǎn)生出許多局部極小，是多峰函數(shù)，找到全局最優(yōu)值有一定的難度。F04是復(fù)雜的多峰函數(shù)，局部最優(yōu)值的個數(shù)與維數(shù)成正比。F05 是多峰函數(shù)，用于測試算法的尋優(yōu)能力。

表1 實驗中使用的Benchmark函數(shù)

4.2 與基本ABC算法的對比

將改進算法與基本ABC算法進行比較，2種算法采用相同的參數(shù)設(shè)置，以消除參數(shù)不同對算法的影響。實驗中，食物源個數(shù)SN取30，最大搜索次數(shù)limit取100，最大迭代次數(shù)maxCycle取1000, 函數(shù)維度分別取D=30和D=50。算法執(zhí)行結(jié)束后，記錄結(jié)果的均值與標準差。測試結(jié)果如表2、表3所示，其中均值的作用是對算法尋優(yōu)精度的體現(xiàn)，標準差的作用是算法穩(wěn)定性的體現(xiàn)。

表2 D=30時基本ABC和MABC的實驗結(jié)果

表3 D=50時基本ABC和MABC的實驗結(jié)果

由表2可見，在單峰函數(shù)測試中，MABC算法在解的精度和穩(wěn)定性兩方面都優(yōu)于基本ABC算法。在多峰函數(shù)的測試中, 除F02之外，MABC算法可以得到較高精度的解，并且性能均優(yōu)于基本ABC算法。由表3可見，D=50時，MABC算法依然在大部分函數(shù)上要優(yōu)于基本ABC算法。顯而易見，尋優(yōu)問題的難易程度與解的維數(shù)成正比，但MABC算法與基本ABC算法相比，尋優(yōu)精度以及收斂速度都表現(xiàn)良好。為了更直觀地反映MABC算法的收斂性能，圖1～圖4為兩種算法對部分測試函數(shù)的收斂曲線，從總體來看，MABC算法的性能要優(yōu)于基本ABC算法。

圖1 Sphere函數(shù)進化曲線（D=30）

圖2 Rastrigin函數(shù)進化曲線（D=30）

圖3 Sphere函數(shù)進化曲線（D=50）

圖4 Rastrigin函數(shù)進化曲線（D=50）

5 結(jié)束語

為了加快基本ABC算法的收斂速度并避免算法陷入局部最優(yōu)，本文提出了改進的人工蜂群算法。算法在觀察蜂階段引入慣性權(quán)重，使用隨著迭代次數(shù)動態(tài)變化的慣性權(quán)重因子來平衡種群的開發(fā)和開采能力，防止算法陷入局部最優(yōu)和加快尋優(yōu)速度；在偵察蜂階段，利用正弦函數(shù)搜索操作，正弦函數(shù)服從均勻分布，能很好地搜索全部范圍，以提高種群多樣性。通過測試函數(shù)表明，該算法性能得到了改善。后續(xù)將把就該改進算法應(yīng)用于實際工程中，以解決實際問題。

參考文獻:

[1] Karaboga D, Basturk B. A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm[J]. Journal of Global Optimization, 2007, 39(3):459-471.

[2] Karaboga D, Basturk B. On the performance of artificial bee colony (ABC) algorithm[J]. Applied Soft Computing, 2008, 8(1):687-697.

[3] Akay B, Karaboga D. A modified Artificial Bee Colony algorithm for real-parameter optimization[J]. Information Sciences, 2012, 192(6):120-142.

[4] Zhu G, Kwong S. Gbest-guided artificial bee colony algorithm for numerical function optimization[J]. Applied Mathematics & Computation, 2010, 217(7):3166-3173.

[5] Banharnsakun A, Achalakul T, Sirinaovakul B. The best-so-far selection in Artificial Bee Colony algorithm[J]. Applied Soft Computing, 2011, 11(2):2888-2901.

[6] Alatas B. Chaotic bee colony algorithms for global numerical optimization[J]. Expert Systems with Applications, 2010, 37(8):5682-5687.

[7] 暴勵, 曾建潮. 自適應(yīng)搜索空間的混沌蜂群算法[J]. 計算機應(yīng)用研究, 2010, 27(4):1330-1334.

[8] Gao W F, Liu S Y. A modified artificial bee colony algorithm[J]. Computers & Operations Research, 2012, 39(3):687-697.

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

[10] 張明, 田娜, 紀志成. 基于適應(yīng)值歐式距離比的均衡蜂群算法[J]. 系統(tǒng)仿真學(xué)報, 2015, 27(5):980-989.

[11] 匡芳君, 徐蔚鴻, 金忠. 自適應(yīng)Tent混沌搜索的人工蜂群算法[J]. 控制理論與應(yīng)用, 2014, 31(11):1502-1509.

[12] 李彥蒼, 彭揚. 基于信息熵的改進人工蜂群算法[J]. 控制與決策, 2015(6):1121-1125.

[13] 徐雙雙, 黃文明, 雷茜茜. 基于平均熵的自適應(yīng)人工蜂群算法[J]. 計算機科學(xué), 2015, 42(8):253-258.

[14] Shi Y, Eberhart R. Modified particle swarm optimizer[C]// IEEE International Conference on Evolutionary Computation Proceedings. IEEE World Congress on Computational Intelligence, 1998:69-73.

[15] 程正東, 章毓晉, 樊祥. 2DPCA在圖像特征提取中優(yōu)于PCA的判定條件[J]. 工程數(shù)學(xué)學(xué)報, 2009, 26(6):951-961.

華僑大學(xué)研究生科研創(chuàng)新能力培育計劃資助項目。