基于細菌趨藥性和當前最優解策略的人工蜂群算法

周長喜　毛　力　吳　濱　楊　弘　肖　煒

1(江南大學物聯網工程學院　江蘇 無錫 214122)

2(輕工過程先進控制教育部重點實驗室　江蘇 無錫 214122)

3(中國水產科學研究院淡水漁業研究中心　江蘇 無錫 214081)

?

基于細菌趨藥性和當前最優解策略的人工蜂群算法

周長喜1,2毛力1,2吳濱1,2楊弘3肖煒3

1(江南大學物聯網工程學院江蘇 無錫 214122)

2(輕工過程先進控制教育部重點實驗室江蘇 無錫 214122)

3(中國水產科學研究院淡水漁業研究中心江蘇 無錫 214081)

摘要為了克服人工蜂群算法在求解函數優化問題中所存在的收斂精度低、收斂速度慢的缺點，提出一種基于細菌趨藥性和當前最優解策略的人工蜂群算法。該算法將細菌覓食優化算法中的趨向性操作引入到雇傭蜂的局部搜索策略中，然后跟隨蜂在當前最優解的基礎上繼續進行尋優，從而提高了人工蜂群算法的局部搜索能力。8個標準測試函數的仿真實驗結果表明，與基本人工蜂群算法相比，改進后的人工蜂群算法在尋優精度和收斂速度上均有明顯提高。

關鍵詞人工蜂群算法當前最優解細菌趨藥性局部搜索

0引言

人工蜂群ABC(Aartificial Bee Colony)算法[1]是Karaboga在2005年提出的一種模擬蜜蜂采蜜行為的仿生智能優化算法。ABC算法因其結構簡單、易于實現、控制參數較少、計算簡潔等優點歷來備受國內外學者的廣泛關注，成為群智能優化算法領域的研究熱點之一。但文獻[2-6]都已指出ABC算法和其他的群智能算法一樣，在求解函數優化問題中也存在收斂精度低、收斂速度慢的缺點。針對該問題，許多學者紛紛提出改進方案。如文獻[7]提出：利用當前全局最優解代替隨機選取的鄰域個體，并根據當前全局最優解的適應度調整鄰域搜索步長，提高收斂精度和收斂速度；文獻[8]提出：利用混沌序列的隨機性、遍歷性和規律性，設計一種混沌局部搜索算子，并將其嵌入蜂群算法框架中，以有效提高在當前最優解周圍進行局部搜索的能力；文獻[9]則提出了基于極值優化策略高效率的尋優機制重新設計ABC算法中跟隨蜂的局部搜索方案，從而提高算法的尋優精度和收斂速度。由此可見，改進ABC算法的局部搜索能力，對提高算法的性能和擴大其適用范圍具有重要的研究意義。

為了增強ABC算法的局部搜索能力，本文提出一種基于細菌趨藥性和當前最優解策略的人工蜂群算法(BCABC)。該算法把細菌覓食優化算法中的趨向性操作引入到雇傭蜂的局部搜索策略中，然后跟隨蜂在當前最優解的周圍進一步進行局部搜索，從而有效提高了人工蜂群算法的局部搜索能力，使算法的收斂精度和收斂速度得到明顯改善和提高。

1人工蜂群算法

人工蜂群算法在求解最小值優化問題Min(f(X))時，將優質蜜源的位置抽象成優化問題的可行解，人工蜂群尋找蜜源的過程就是算法搜尋最優解的過程。該算法把人工蜂群分為雇傭蜂、跟隨蜂和偵查蜂三種角色，并讓雇傭蜂、跟隨蜂和蜜源數目相等且一一對應。而偵查蜂由進化停滯的雇傭蜂轉化而來，蜜源的含蜜量則對應優化問題的適應度值。算法通過三種蜜蜂之間的相互協作來實現對最優蜜源的搜索過程。算法一次迭代過程的具體描述如下：

對于最小值優化問題Min(f(X))，其中f(X)為被優化的目標函數。假設初始種群含有SN個解(2SN個個體)，每個解Xi(i=1，2，…，SN)是一個D維向量，其中每個解與蜜源、雇傭蜂和跟隨蜂一一對應。

(1) 雇傭蜂負責全局搜索：依次對雇傭蜂中每個個體進行更新操作，即隨機選擇個體Xi中任意的一維分量按式(1)進行變異，產生新個體。

(1)

Xi=X'i f(X'i)

(2)

(3)

(2) 跟隨蜂在部分優質蜜源附近作局部搜索：跟隨蜂依據概率從種群中選擇部分適應度值較好的蜜源Xi，由式(4)和(5)可知，擁有較優適應度值的蜜源被選中的概率也較大。首先，根據式(4)計算Xi的適應度函數fiti；然后，根據適應度函數，利用式(5)計算Xi的選擇概率Pi；最后，針對選中的Xi執行與雇傭蜂相同的變異與選擇操作。

fiti=11+fi fi≥01+|fi| fi<0{

(4)

(5)

其中，fi是蜜源Xi對應的被優化的目標函數f(Xi)的適應度值，fiti是蜜源Xi對應的適應度值變換后的適應度函數值。

(3) 偵查蜂處理進化停滯的個體：如果某個解Xi經過指定的limit次循環沒有得到改善，則該解對應的雇傭蜂轉變為偵查蜂，通過式(6)產生一個新解來代替該解[10]。

Xi=Xmin+φ×(Xmax-Xmin)

(6)

式中，φ表示區間[0，1]內的隨機數，Xmax和Xmin是解空間的上、下邊界。

2改進人工蜂群算法

ABC算法每次迭代過程中都通過雇傭蜂和偵察蜂執行全局搜索，在式(1)和式(6)中：xkj是隨機選擇的任一個體的一維分量，R和φ也是隨機數，由此可知該算法的全局搜索能力很強。但該算法中，雇傭蜂和跟隨蜂都是隨機地選擇一維分量經過變異來執行局部搜索，而雇傭蜂變異后的新個體的適應度值是不確定的：可能比原來個體優秀，也可能比原來個體差。然后根據式(2)來更新個體，如果新個體比原來個體優秀則更新，否則不更新，所以式(1)所示的雇傭蜂在鄰域的局部搜索能力較差；同理，跟隨蜂也因為盲目地選擇一維變量進行變異，從而降低了產生更優秀個體的概率，使個體不被更新的可能性變大，增加了無效搜索次數，進而致使其局部搜索效率下降。綜上，這一系列問題導致該算法出現尋優精度不高、收斂緩慢的弊端。

2.1基于細菌覓食算法中的趨藥性的局部搜索策略

細菌覓食優化BFO(Bacteria Foraging Optimization)算法[11]是Passino在2002年根據人類大腸桿菌覓食行為提出的一種仿生學算法。該算法把細菌的覓食行為抽象為趨向性、復制和遷移三個操作。其中，趨向性操作包括翻轉和向前移動兩個過程，將細菌向任意方向移動單位步長定義為翻轉，而每當細菌完成一次翻轉后，就檢查其適應度值是否改善，若適應度值得到改善，細菌將沿同一方向繼續移動，如此循環直至適應度不再改善，或達到預定的移動步數Ns，此過程被定義為向前游動。BFO算法中的趨向性操作實質上是一種局部搜索策略，細菌按式(7)更新位置：

(7)

式中，θi(j,k,l)為第i個細菌在第j次趨向性操作、第k次復制操作、第l次遷移操作后的位置；C(i)表示細菌i向前翻轉的步長；Δ(i)表示隨機翻轉方向。

為了有效地提高雇傭蜂的局部搜索能力，把具有良好局部搜索性能的細菌趨向性操作引入到ABC算法中，使該算法具有較快的收斂速度和較高的尋優精度。其具體思路是：將式(1)中的個體變異部分R×(xij-xkj)視為細菌的翻轉，式(1)整體視為細菌向前游動，這樣ABC算法中的雇傭蜂就具有像細菌一樣的趨藥性行為。為了進一步提高雇傭蜂在鄰域的搜索效率，讓蜜蜂在D維空間中逐維嘗試翻轉和游動，在適應度值有所提高時，讓蜜蜂繼續在該有利的維度上向前移動。

2.2基于當前最優解的跟隨蜂局部搜索策略

當前最優蜜源的位置對改善ABC算法的收斂性能是一項極為有用的信息，跟隨蜂可以根據雇傭蜂所傳來的蜜源信息來比較蜜源的優劣，進而選擇當前的最優蜜源并在其周圍進行搜索。為了加快跟隨蜂的收斂速度，令其在雇傭蜂最優解[12]的基礎上進一步進行尋優，并且在每次迭代中逐維更新蜜源每一維度的值，以增加該可行解在搜索空間中的多樣性。因此本文提出了基于當前最優解引導的搜索策略公式：

(8)

與基本ABC算法中的搜索策略不同，本文所采用的是跟隨蜂在當前最優解的引導下在自身周圍進行局部搜索的策略。fb的值可以適時調節步長，有助于跟隨蜂尋找新位置，調高尋優性能。在迭代初期，由于fb的值較大，有效地擴大了領域的搜索范圍，提高了算法的局部搜索能力；而隨著迭代次數的增加，fb的值逐漸變小，有效的縮小領域的搜索范圍，將有助于算法進行深度尋優并能快速尋找到最優解。

2.3基于細菌趨藥性和當前最優解策略的ABC算法流程

對于最小值優化問題Min(f(X))，改進后的人工蜂群算法實現的具體步驟如下：

1) 初始化算法參數，隨機產生SN個解，每個解Xi=(xi1,xi2,…,xiD)是一個D維向量，最大迭代次數MCN、最大移動步數Ns、并指定偵察蜂用于判斷個體是否陷入停滯的控制參數limit的值。

2) 對種群中每個雇傭蜂Xi在D維度空間中利用式(1)逐維進行翻轉，并用式(2)對其更新。如果翻轉后適應度值得到改善，則繼續按照翻轉的方向向前移動，直至適應度值不再改善或達到設定的最大移動步數Ns為止。

3) 記錄此次迭代中雇傭蜂的最優解Xb，以供式(8)使用。

4) 根據式(4)計算Xi的適應度函數值fiti，再利用式(5)計算Xi的選擇概率Pi。

5) 跟隨蜂依據概率Pi選擇部分適應度較好的蜜源，然后每個跟隨蜂再根據式(8)在它的鄰域附近逐維進行局部搜索，并用式(3)記錄其未更新次數triali。

6) 偵查蜂檢查是否存在連續limit次迭代都沒有更新的個體，若存在則按式(6)產生一個新解代替原來的陷入局部最優的解。

7) 記錄到目前為止的最優解。

8) 判斷是否達到最大迭代次數MCN，若滿足，則輸出最優解，否則轉到步驟2。

3仿真實驗及分析

為了評估BCABC算法的性能，本文使用了8個典型的測函數[13]對BCABC算法與ABC算法[14]以及文獻[7]中提出的改進ABC(Best-so-far ABC)算法進行對比試驗，進而比較三種算法的穩定性、尋優精度和收斂速度。

3.1測試函數選擇

表1列出了8個測試函數的搜索范圍和理論最優值。其中：f1-f3是單模態函數，在定義域內只有一個極值點，主要用來測試算法的尋優精度和收斂速度；f4-f7是非線性多模態函數，存在多個局部極值點，用來測試算法的全局尋優性能和避免早熟的能力；f8被稱作變態函數，該函數的變量之間具有很強的關聯性，并且理論最優值位于一個彎曲的、平滑路徑上的谷底，由于該函數較特殊，通常用來評價優化算法的性能。

表1　測試函數的搜索范圍和理論最優值

續表1

Sphere函數：

Step函數：

Schwefel’s函數：

Rastrigin函數：

Ackley函數：

f5(x)= -20exp-0.21n∑ni=1x2i?è???÷-

Griewank函數：

Levy函數：

Rosenbrock函數：

3.2實驗結果與分析

在做BCABC、ABC和Best-so-far ABC三種算法求解函數最小值優化問題的對比實驗時，參數設置如下：種群規模SN=100，最大移動步數Ns=4，判斷是否陷入停滯的控制參數limit=300，維度D=30，最大循環次數MCN的值為1000。

為了測試算法的性能，分別使用以上三種算法對每個測試函數在30維的條件下進行30次獨立實驗。測試結果如表2所示，得出其所對應的最優值、最差值、平均值、標準差和平均時耗，其中，平均時耗指的是三種算法分別對8個測試函數在各自獨立運行30次達到收斂穩定精度所需要時間的平均值；同時，圖1—圖8還分別給出了三種算法對8個測試函數在各自獨立運行30次的平均適應值的進化曲線。

表2中的數據表明：基本ABC算法的穩定性較差、收斂速度慢而且收斂精度不高。Best-so-far ABC算法利用當前最優解及其對應的適應度值改進跟隨蜂的鄰域搜索方式，從而增強了該算法的局部搜索能力，也在一定程度上提高了算法的求解質量。BCABC算法則把細菌覓食優化算法里的趨向性操作加入到了雇傭蜂局部搜索策略中，然后跟隨蜂在當前最優解的周圍進一步進行局部搜索，顯著提高了該算法的局部搜索能力，并進而使算法的性能得到明顯提高。

表2　30維函數測試結果的比較

從表2中可以看出，BCABC算法的最優值和最差值的精度與基本ABC算法和Best-so-far ABC算法相比明顯得到提高，并且BCABC算法對各測試函數均具有較高的尋優精度。對除f2以外的所有測試函數，BCABC算法的均值和方差都優于另外兩種算法，而且存在數量級級別的提升，這說明BCABC算法穩定性較高，具有較好的魯棒性。

另外，從表2中可知，BCABC算法的平均時耗小于基本ABC算法和Best-so-far ABC算法，雖然BCABC算法在每次迭代過程中都在雇傭蜂搜索階段嘗試在各個方向上進行游動增加了計算量，從而增加了每次迭代的運行時間，但是從圖1—圖8可以看出，BCABC算法達到穩定收斂精度所需要的迭代次數遠小于基本ABC算法和Best-so-far ABC算法，特別是對函數f2、f4和f6在迭代幾十次就收斂到理論最優值。顯然，BCABC算法表現出比基本ABC算法和Best-so-far ABC算法更高的收斂精度和更快的收斂速度，并且在進化中BCABC算法始終保持向最優解進化的趨勢。這表明BFO算法中趨向性操作的局部搜索策略和基于當前最優解策略的跟隨蜂局部搜索策略明顯的改善了基本ABC算法中存在的一些不足之處，并能有效地提高算法的尋優精度和收斂速度，防止早熟收斂現象的出現。

圖1　Sphere函數的收斂曲線

圖2　Step函數的收斂曲線

圖3　Sehwefel’s函數的收斂曲線

圖4　Rastrigin函數的收斂曲線

圖5　Ackley函數的收斂曲線

圖6　Griewank函數的收斂曲線

圖7　Levy函數收斂曲線

圖8　Rosenbrock函數的收斂曲線

4結語

本文在對算法分析的基礎上，指出基本ABC算法中存在的雇傭蜂和跟隨蜂局部搜索能力較差的問題，并提出了具體的改進方案，即把BFO算法中的趨向性操作加入到基本ABC算法中雇傭蜂的局部搜索策略中，跟隨蜂再在當前最優解的引導下進一步進行局部搜索。而仿真實驗結果也表明，在求解函數最小值優化問題時，本文給出的改進基本ABC算法取得了較好的效果, 具有較強的魯棒性，并能有效避免算法陷入局部最優，使算法具有更高的尋優精度和更快的收斂速度。

參考文獻

[1] Karaboga D. An idea based on honey bee swarm for numerical optimiz- ation[R]. Technical Report-TR06.Kayseri: Erciyes Unversity, Engineer- ing Faculty, Computer Engineering Department, 2005.

[2] 楊建衛. 一種采用蜂群全局引導搜索策略的入侵雜草優化改進算法[J]. 計算機應用與軟件, 2014,31(4):161-164.

[3] Rajasekhar A, Abraham A, Pant M. Levy mutated artificial bee colony algorithm for global optimization[C]//IEEE International Conference on Systems, Man and Cybernetics, 2011: 655-662.

[4] Wu B, Fan S H. Improved artificial bee colony algorithm with chaos[M]//Computer Science For Environmental Engineering and Ecoinformatics, Berlin: Springer, 2011: 51-56.

[5] 張鵬, 劉弘, 王愛霖. 基于人工蜂群算法的疏散運動仿真[J]. 計算機工程, 2013, 39(7): 261-264.

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

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

[8] 王翔, 李志勇, 許國藝. 基于混沌局部搜索算子的人工蜂群算法[J]. 計算機應用, 2012,32(4):1033-1036, 1040.

[9] 葛宇, 梁靜, 王學平. 基于極值優化策略的改進的人工蜂群算法[J]. 計算機科學, 2013,40(6):247-251.

[10] Kang Fei, Li Junjie, Ma Zhenyue. Rosenbrock artificia1 bee colony algorithm for accurate global optimization of numerical functions[J]. Information Sciences, 2011,181(16):3508-353l.

[11] Passino K M.Biomimicry of bacterial foraging for distributed optimization and control[J]. IEEE Control Systems Magazine, 2002,22(3):52-67.

[12] Gao Weifeng, Liusanyang, Huang Ling-ling. A global best artificial bee colony algorithm for global optimization[J]. Journal of Comput-ational and Applied Mathematics, 2012, 236(11):2741-2753.

[13] 張銀雪, 田學民, 曹玉蘋. 改進搜索策略的人工蜂群算法[J]. 計算機應用, 2012, 32(12): 3326-3330.

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

ARTIFICIAL BEE COLONY ALGORITHM BASED ON STRATEGY OF BACTERIAL CHEMOTAXIS BEHAVIOUR AND CURRENT OPTIMAL SOLUTION

Zhou Changxi1,2Mao Li1,2Wu Bin1,2Yang Hong3Xiao Wei3

1(SchoolofInternetofThings,JiangnanUniversity,Wuxi214122,Jiangsu,China)2(KeyLaboratoryofAdvancedProcessControlforLightIndustry(MinistryofEducation),Wuxi214122,Jiangsu,China)3(FreshwaterFisheriesResearchCenterofChineseAcademyofFisherySciences,Wuxi214081,Jiangsu,China)

AbstractWe proposed an artificial bee colony (ABC) algorithm in this paper which is based on the strategy of bacterial chemotaxis behaviour and current optimal solution in order to overcome the drawbacks of low convergence accuracy and slow convergence rate the conventional ABC algorithm has in solving function optimisation problem. This algorithm introduces the chemotaxis operation in bacterial foraging optimisation algorithm into local search policy of employed bees, and then the onlooker bees continue to search for the optimal solution based upon the present optimal solution, therefore the local search capability of ABC algorithm is enhanced. It is indicted by the results of simulation experiments on eight standard test functions that the improved ABC algorithm gains significant improvement on optimisation accuracy and convergence rate compared with basic ABC algorithm.

KeywordsArtificial bee colony (ABC)Current optimal solutionBacterial chemotaxis behaviourLocal search

中圖分類號TP18

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.01.065

收稿日期：2014-06-26。國家青年科學基金項目(F030204)；輕工過程先進控制教育部重點實驗室開放課題資助(江南大學)項目(APCLI1004)；現代農業產業技術體系專項(CARS-49)。周長喜，碩士生，主研領域：智能算法。毛力，副教授。吳濱，講師。楊弘，研究員。肖煒，助理研究員。