火久元　張　政　孟凡明

1(蘭州交通大學電子與信息工程學院　甘肅 蘭州 730070)2(北京社會管理職業(yè)學院通識教育中心　北京 101601)

0　引　言

群智能研究是當下算法研究中的熱門，受到越來越多的學者的關注。群智能優(yōu)化算法是學習群體的進化或覓食，來模擬優(yōu)化搜索的過程，用自然界中的個體來模擬可行的解，學習個體對自然界的適應力來模擬問題的目標函數，模擬個體的覓食和優(yōu)勝劣汰，來演化函數優(yōu)化過程中較好的解替換劣解的迭代過程[1]。群智能算法也存在一定的問題，例如過早收斂，局部搜索能力差，收斂速度慢，精度低等問題，且算法的優(yōu)化效果對算法參數有一定的依賴性和理論分析深度不足等，有很大的改進空間。人工蜂群算法作為一種概率搜索算法，相對于梯度方法有著一定的優(yōu)勢，但也存在著群智能算法的通病。

人工蜂群算法ABC(Artificial Bee Colony Algorithm)[6]是一種群體智能優(yōu)化算法，是由土耳其學者Karaboga在2005年提出的一種較新的具有較好搜索能力的人工仿生算法。該算法的原理是模擬蜜蜂群體尋找優(yōu)良蜜源的過程。由于算法優(yōu)良的性能，隨著人們對它了解和研究不斷的深入，應用的范圍越來越廣闊。但是，文獻[3-5]發(fā)現，人工蜂群算法也存在著早熟、搜索領域不夠廣、收斂速度慢、解精度不高等問題。針對其存在的問題，大量的學者對其進行了改進。Banharnsakun等[7]將全局最優(yōu)解引入基本ABC算法中；為了增強人工蜂群算法的開發(fā)能力，Zhu等[8]參照粒子群算法提出了全局最優(yōu)解引導的全局人工蜂群算法(GABC)，增強了算法的開發(fā)能力。文獻[9]提出基于極值優(yōu)化的策略，優(yōu)化了ABC 算法中被雇傭蜂的局部搜索方案,從而提高算法的尋優(yōu)精度和收斂速度。文獻[10]提出在雇傭蜂和被雇傭蜂間引入萬有引力影響的搜索策略，從而提高算法的搜索能力。

為提高ABC算法在處理函數優(yōu)化問題中存在的效率和精度，本文提出了一種提高廣度和搜索深度的人工蜂群算法MHABC(Hybrid Artificial Bee Colony algorithm based on Mutation of inferior solutions)。該算法引入了劣解突變和二項交叉操作這兩種改進策略，劣解突變是對算法中被拋棄的劣解進行有方向的突變操作，進行擴大了局部搜索范圍。二項交叉操作是引入遺傳算法中的交叉操作，使領域搜索的結果與全局最優(yōu)值進行二項交叉操作，這樣顯著提高了算法的搜索精度，且提高了算法的效率。

1　標準人工蜂群算法

標準人工蜂群算法描述如下：蜜源,代表的是可行域內的各種可能解。其次是3種蜜蜂的角色，引領蜂也叫雇傭蜂，在可行解內搜索蜜源，一旦發(fā)現更好的蜜源就記住位置，并回蜂群招募跟隨蜂加入搜索。偵查蜂作為獨立的個體出現，隨機出現在可行域內，進行領域搜索，一旦發(fā)現更好的蜜源就更換當前結果。3種蜜蜂各自局部搜索，3個結果不斷比較，得到全局最優(yōu)值：

1) 引領蜂在蜜源附近進行領域搜索, 若發(fā)現比當前更好的蜜源,則更新蜜源的位置，否則不更新其位置[11]。

2) 跟隨蜂根據引領蜂所提供蜜源信息,按照某種特定的選擇策略，依附到特定的蜜源,轉化為雇傭蜂,一旦發(fā)現比當前好的蜜源,就更新蜜源的位置[11]。

3) 在多次迭代過程中，文中設置其次數為limit，如果在limit次迭代中未更新蜜源位置，則引領蜂轉化為偵查蜂，繼續(xù)隨機在整個解空問內進行隨機搜索，尋找一個新的可行解作為蜜源位置，并開始全局搜索[11]。

基本ABC算法流程見圖1。

圖1　基本ABC算法流程圖

人工蜂群算法實現的基本步驟如下[11]：

1) 初始化。蜜蜂總數SN，采蜜次數abs=0,記錄采蜜蜂在同一蜜源的停留次數，最大循環(huán)次數maxCycle,迭代次數iter，最大搜索次數limit，并按式(1)初始化解。隨機產生SN個初始解(X1，X2， …，Xsn) ，具體按式(1)隨機產生可行解Xi，其中i∈ {1，2，…，SN}，j∈{1，2，…，D}。

Xij=Xj,min+rand[0,1]×(Xj,max-Xj,min)

(1)

2) 引領蜂階段。對隨機產生的可行解進行局部搜索，將隨機的一維Xij按式(2)作步長搜索，更新為Vij，即對Vi和Xi的適應度值進行比較，若fit(Vi) >fit(Xi)，則替換Xi為Vi，否則保持Xi不變。

Vij=Xij+φij(Xij-Xkj)φij∈[-1,1]

(2)

3) 跟隨蜂階段。使用賭輪盤方法，即式(3)，計算跟隨蜂選擇的概率Pi。Xi的適應度值記為fiti，計算方法如式(4)所示，fun(Xi) 為目標函數值，為所有蜜源位置的適應度值總和。當Xi被選擇時，Xi按式(2)作步長搜索，更新為Vij，即對Vi和Xi的適應度值進行比較，若fit(Vi) >fit(Xi)，則替換Xi為Vi，否則保持位置不變。

(3)

(4)

4) 偵察蜂階段。某蜜源Xi的迭代次數記為abs，若abs>limit，則依附于該蜜源的引領蜂轉化為偵查蜂，調用式(1)，產生新的隨機的一個蜜源位置。

5) 記錄最優(yōu)解。比較當前SN個解的適應度值，記錄最優(yōu)解,若迭代次數iter>maxCycle,則結束。

2　基于劣值突變的改進混合人工蜂群算法

2.1　劣值突變方法

突變原指細胞內突然的違背基因鏈的變化。20世紀30年代，法國數學家勒內·托姆系統(tǒng)性提出了突變論，將系統(tǒng)內整體性的“突躍”稱為突變。Doush等[12]發(fā)表關于人工蜂群算法在不同突變策略下的比較研究。Sharma等[13]采用基于突變的人工蜂群算法，用于生成高質量關聯規(guī)則，用于從大數據集中查找頻繁項集。蔣成等[14]借鑒差分進化算法的突變算子，提出了一種新的錯位突變策略，增加了人工蜂群算法的種群多樣性。胡玉榮等[15]提出漸變與突變機制，并將其引入蜂群算法，增強了種群多樣性，避免陷入局部最優(yōu)。受生物進化過程中的突變操作啟發(fā)，將其突變操作引入到人工蜂群算法中的劣解中來，使其進行突變，擴展了可行解的范圍，提高了搜索的速度和精度。

本文利用這種機制有方向地引導人工蜂群算法中的劣解，在跟隨操作中被拋棄的引領蜂(雇傭蜂)，即可行解中的劣解(較壞的位置)進行突變操作，增加搜索的廣度，提高算法的搜索能力。具體實現如下：跟隨蜂階段，依據式(3)計算跟隨蜂的跟隨概率Pi，并生成隨機數rand與Pi比較，如rand

Vij=(rand[0.1]-0.5)×M×X

(5)

式中：M為突變系數，取值范圍為[-1,10]，Xglobal為全局最優(yōu)值(是目前為止的全局最優(yōu)值,還是第j次的最優(yōu)值)。

2.2　二項交叉操作

交叉操作由遺傳算法借鑒而來，常見的交叉操作包括指數交叉和二項交叉。由于人工蜂群算法全局探索能力不強，為增強人工蜂群算法的開發(fā)能力，Zhu等[8]參照粒子群算法提出的全局人工蜂群算法(GABC)。但平衡算法的探索和開發(fā)能力在一定程度上降低了算法的全局尋優(yōu)能力，所以引入二項交叉操作[1]，增強算法的全局尋優(yōu)能力。這里我們用到的是二項交叉，對每一個分量都生成一個0到1之間均勻分布的隨機值rand，與交叉系數cr對比，若rand

進行二項交叉操作，取范圍在[0，1]的交叉概率cr, 產生0到1隨機數rand，若rand≤cr, 則讓采蜜蜂進行領域搜索后與全局最優(yōu)值進行交叉操作，否則不進行交叉操作。如式(6)所示這樣的交叉操作提高了算法的開發(fā)能力，通過對cr的調節(jié)來提高算法的探索和開發(fā)能力。cr越大，算法的開發(fā)能力越強，反之則探索能力越強[1]。

Vij′=Xglobal+β(Xglobal-Vij)

(6)

2.3　基于劣解突變和二項交叉操作的混合人工蜂群算法

本文基于上述兩種改進策略提出了基于劣解突變的混合人工蜂群算法，既提高了領域搜索的廣度，又提高了領域搜索的深度，從而改進了算法的收斂速度和精度。其基本步驟如下：

1) 初始化。初始化種群，蜜蜂總數SN，采蜜次數abs=0,記錄采蜜蜂在同一蜜源的停留次數，最大循環(huán)次數maxCycle,迭代次iter，最大搜索次數limit，并按式(1)初始化解。隨機生成SN個初始解(X1，X2， …，XSN) ，具體按式(1)隨機產生可行解Xi，其中i∈ {1，2，…，SN} ，j∈{1，2，…，D}。

2) 引領蜂階段。對解Xi進行鄰域搜索和交叉操作。選取Xi的隨機一維Xij，按式(2)進行步長搜索，結果記為Vij，并產生鄰域解Vi，依據式(6)將領域搜索后的解與全局最優(yōu)解進行交叉操作，并在可行解允許的取值范圍之內，對Vi和Xi的適應度值進行對比，若fit(Vi) >fit(Xi)，則Vi替換Xi;否則保持Xi的位置不變。

4) 偵察蜂階段。某蜜源Xi的迭代次數記為abs，若abs>limit，則依附于該蜜源的引領蜂轉化為偵查蜂，調用式(1)，產生新的隨機的一個蜜源位置。

5) 最優(yōu)解記錄。比較當前SN個解的適應度值，記錄最優(yōu)解,若迭代次數iter>maxCycle,則結束。

具體算法流程見圖2。

圖2　MHABC算法流程圖

3　仿真實驗與分析

3.1　標準測試函數

選取了表1中的6個標準測試函數來檢驗改進算法的性能，表2為標準測試函數對應的表達式。其中Sphere、Schwefel為簡單的單模函數，僅有1個極值主要用了測驗算法的搜索精度和速度。Griewank、Rastrigin、Ackley為非線性多峰值測試函數，主要用來測試算法的全局尋優(yōu)能力。Rosenbrock為變態(tài)函數，其理論最優(yōu)值藏身于狹窄的谷地，該函數的搜索難度較大，一般用來測試算法的尋優(yōu)能力[16]。

表1　標準測試函數

表2　標準測試函數表達式

3.2　實驗數據與分析

3.2.1多次實驗綜合分析

選取表2的標準測試函數對ABC、GABC、MHABC算法進行了實驗，以比較3種算法的收斂精度。在相同條件下，每個算法對每個測試函數獨立重復30次，以統(tǒng)計分析實驗結果的平均值和標準偏差。實驗結果如表3所示，其中G表示算法的迭代次數，D表示對象函數的維數，Mean和SD是30次統(tǒng)計實驗數據的平均值和標準偏差的平均值獨立實驗。Mean表示算法在給定函數評估時間內可以實現的精度，反映了收斂精度。SD反映了算法的穩(wěn)定性和魯棒性[17]。為了清楚起見，最佳算法的結果分別標記為粗體。所有算法都在Java中編碼，實驗在具有4 GB內存容量的Intel i5 2.67 GHz雙核處理器上運行。算法的基本參數設定：蜂群數量為100，雇傭蜂(引領蜂)數量為50。拋棄食物源需要的最大迭代次數Limit=100。算法終止條件，即最大循環(huán)次數為2 500次。

表3　算法的參數設置和性能比較

續(xù)表3

從表3中的結果可以看出，對于30維的Schwefel，Sphere和Griewank函數，GABC算法的收斂精度比ABC算法略微差。但在60維的函數收斂和其他功能的比較中，它可以獲得比ABC算法更好的結果。不僅獲得了更好的精度，而且有著較快的收斂速度[18]。

在所有實驗中可以明顯的看出，MHABC算法可以實現比ABC和GABC算法更優(yōu)的結果。MHABC算法所得到的收斂結果要遠優(yōu)于ABC算法和GABC算法的結果， 而且MHABC算法只需要較少次的迭代，即可實現比ABC算法和GABC 算法更高的優(yōu)化精度，并且可以始終保持著向最優(yōu)解演化的趨勢。其優(yōu)點和算法性能是顯而易見的，說明該演化機制提高了算法搜索的深度和廣度，由此提高了算法的收斂性能。

3.2.2收斂性分析

為了更直觀地反映算法的優(yōu)化過程，采用了四個基準函數Sphere、Griewank、Rastrigin和Ackley，來比較ABC算法、GABC算法和MHABC算法的優(yōu)化過程。四個函數的維度都設置為30，迭代次數為1 000，見表3，其他參數與3.2.1節(jié)中的參數設置一致。圖3以圖形方式呈現了3個算法在進化過程中的收斂性特征。從圖中可以看出，全局最優(yōu)引導策略的GABC 算法總體優(yōu)于ABC算法，在這兩種算法進化的早期階段，沒有特別明顯的差別，但在后期進化中GABC 算法則表現出了更好的收斂性能。明顯地可以從圖3(b)中的演變曲線可以清楚的看出，MHABC算法所得到的收斂精度遠好于ABC算法和GABC算法。 MHABC算法只需較少次的迭代，即可實現比ABC算法和GABC 算法更高的優(yōu)化精度，并且可以始終保持朝著最優(yōu)解演化的趨勢。由收斂曲線可以看出MHABC算法，其收斂的速度和精度都要好于GABC算法和ABC算法。

圖3　基準函數Sphere，Griewank，Rastrigin和Ackley在30維下的收斂性分析

由實驗結果可以看出，在MHABC算法的處理階段，當前最優(yōu)個體總是具有更多的進化機會來加深優(yōu)化算法的深度，同時有更多更優(yōu)秀的個體有機會獲得進化，所以在處理Sphere這樣簡單的單模函數時具有很好的收斂性。對于復雜多峰值的Griewank，Ackley并沒有取得良好的收斂效果，說明算法在處理復雜函數時，在收斂性方面還存在缺陷。但對于解深藏在狹長谷地的變態(tài)函數，改進算法取得了更好的精度和收斂性，說明了算法具有很好的全局尋優(yōu)能力和良好的收斂性。

3.3　與遺傳算法(GA)、粒子群算法(PSO)的結果比較

為了驗證MHABC算法的有效性和全局尋優(yōu)能力，本文選取了文獻[20]中的30維的免疫遺傳算法(IIGA )運行數據和文獻[21]中的動態(tài)粒子群算法(PSO)在100維下的運行結果與改進的MHABC算法作了對比，其結果如表4-表5所示。

表4　30維下函數的運行結果

由表4可以看出GA算法在Sphere、Griewank、Rastrigin上的搜索結果要遠劣于MHABC算法的結果，但是在測試函數Rosenbrock上，GA算法的結果要較好于MHABC。

表5　100維下函數的運行結果

由表5可以看出PSO算法在測試函數Griewank，Rastrigin上的搜索結果要遠劣于MHABC算法的結果，但是在測試函數Rosenbrock上，PSO算法的結果要較好于MHABC。

4　結　語

為了提高算法的性能，并提高算法的收斂速度和收斂精度，本文對基本人工蜂群算法進行改進，引入劣解突變和二項交叉操作兩部分改進，在提高了領域搜索的廣度的同時，又提高了領域搜索的深度，取得了良好的算法性能。在多個測試函數上的實驗仿真結果表明，該算法具有更好的搜索能力，有效地提高了收斂速度和精度，并取得了更優(yōu)化的解，在解的穩(wěn)定性方面也有很好的效果。

[1] 江銘炎,袁東風.人工蜂群算法及其應用[M]. 北京：科學出版社,2014.

[2] 胡中功,李靜.群智能算法的研究進展[J].自動化技術與應用,2008,27(2):13-16.

[3] 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.

[4] Gao W, Liu S. Improved artificial bee colony algorithm for global optimization[J]. Information Processing Letters, 2011, 111(17):871-882.

[5] 王輝.一種帶共享因子的人工蜂群算法[J].計算機工程,2011,37(22):139-142.

[6] Karaboga D. An idea based on honey bee swarm for numerical optimization, TR06[R]. Kayseri: Erciyes University, Engineering Faculty, Computer Engineering Department, 2005.

[7] Banharnsakun A, Achalakul T, Sirinaovakul B. The best-sofar selection in artificial bee colony algorithm[J]. Applied Soft Computing, 2011,11(2): 2888-2901.

[8] Zhu G, Kwong S. Gbest-guided artificial bee colony algorithm for numerical function optimization[J].Applied Mathematics and Conference on Computation,2010,2(17):3166-3177.

[9] Karaboga D, Akay B. A comparative study of Artificial Bee Colony algorithm[J]. Applied Mathematics & Computation, 2009, 214(1):108-132.

[10] Tsai P W, Pan J S, Liao B Y, et al. Enhanced artificial bee colony optimization[J]. International Journal of Innovative Computing Information & Control Ijicic, 2009, 5(12):5081-5092.

[11] 倪志偉，李蓉蓉，方清華，等. 基于離散人工蜂群算法的云任務調度優(yōu)化[J].計算機應用,2016,36(1):107-112.

[12] Doush I A, Hasan B H F, Al-Betar M A, et al. Artificial bee colony with different mutation schemes: A comparative study[J]. Computer Science Journal of Moldova, 2014, 21(2).

[13] Sharma P, Tiwari S, Gupta M. Optimize Association Rules Using Artificial Bee Colony Algorithm with Mutation[C]// International Conference on Computing Communication Control and Automation. IEEE, 2015:370-373.

[14] 蔣成,汪繼文,邱劍鋒.基于錯位突變策略的改進人工蜂群算法[J]. 赤峰學院學報(自然科學版) ,2015,31(2):16-20.

[15] 胡玉榮,丁立新,謝大同,等.采用漸變與突變機制的反向人工蜂群算法[J]. 武漢大學學報(理學版),2013,59(2):123-128.

[16] 周長喜,毛力,吳濱,等.基于當前最優(yōu)解的人工蜂群算法[J].計算機工程,2015,41(6):147-151.

[17] 張新明,尹欣欣,馮夢清.動態(tài)高斯變異和隨機變異融合的自適應細菌覓食優(yōu)化算法[J].計算機科學,2015,42(6):101-106.

[18] 王冰.基于局部最優(yōu)解的改進人工蜂群算法[J].計算機應用研究, 2014, 31(4):1023-1026.

[19] 郁舒好, 蘇守寶. 混沌螢火蟲優(yōu)化算法的研究及應[J].計算機科學與探索, 2014, 8(3):352-358.

[20] 萬建臣, 靳宗信. 多峰值函數優(yōu)化問題的免疫遺傳算法求解[J]. 電子科技大學學報, 2013, 42(5):769-772.

[21] 孫蘭蘭，王曉超. 求解高維函數優(yōu)化的動態(tài)粒子群算法[J].計算機工程與應用,2011,47(27):36-37.