基于交叉的全局人工蜂群算法的研究

張平華，李敬明，胡賢德，胡 俊

(1.安徽新華學院 信息工程學院，安徽 合肥 230088；2.合肥工業大學 管理學院，安徽 合肥 230009)

基于交叉的全局人工蜂群算法的研究

張平華1，李敬明2，胡賢德1，胡 俊1

(1.安徽新華學院 信息工程學院，安徽 合肥 230088；2.合肥工業大學 管理學院，安徽 合肥 230009)

人工蜂群(Artificial Bee Colony，ABC )算法在求解函數最優值時，存在后期收斂速度慢、易于陷入局部最優、疏于開發等問題.為了解決這些問題，對算法進行了深入研究，結合其他仿生智能優化算法的機制，提出了一種能有效提高收斂速度，增強算法開發性和全局尋優能力，并能有效避免種群個體陷入局部最優的算法——基于交叉的全局人工蜂群算法.選取7個標準測試函數進行實驗仿真，結果表明，與ABC算法、全局最優人工蜂群算法(GABC)相比，基于交叉的全局人工蜂群算法(CGABC)的收斂速度及精度均有明顯提高.

智能算法；交叉；全局；人工蜂群算法

近年來，國內外學者對基于智能優化規則的啟發式算法做了大量的研究，各種先進的、智能的仿生群智能算法不斷出現(如魚群算法、蛙跳算法、禁忌搜索算法、遺傳算法、蟻群算法、粒子群算法等)，并被逐步應用到組合優化和資源調度等各方面的問題求解中.仿生群智能是指眾多簡單的個體通過相互協同方式，表現出復雜的智能行為的過程和特性.群體智能算法主要有模擬螞蟻覓食行為的蟻群算法[1](Ant Colony Optimization，ACO)、源于鳥群覓食行為的粒子群算法[2](Particle Swarm Optimization，PSO)、模擬真實魚類覓食行為的人工魚群算法[3](Artificial Fish Swarm Algorithm，AFSA)、模擬自然界中螢火蟲成蟲發光的生物學特性的螢火蟲算法[4](Glowworm Swarm Optimization，GSO)以及模擬蜜蜂群體尋找優良蜜源的人工蜂群算法[5](Artificial Bee Colony，ABC)等.

1 人工蜂群算法及計算框架

1.1 人工蜂群算法概述

在對蜜蜂群體采蜜行為進行深入觀察和研究后，受蜜蜂行為的啟發，土耳其Erciyes大學的KARABOGA教授在一種虛擬蜜蜂(Virtual Bee Algorithm，簡稱VBA)算法的基礎上，于2005年在文獻[6]中系統地提出了一種新型群智能優化算法——人工蜂群覓食優化算法.

人工蜂群(簡稱ABC)算法在組合優化方面已經被證實比上述的智能算法具有更優越的性能[7].但與其他群智能計算算法一樣，ABC算法也存在著缺乏全局最優值的記錄和算法參與過程、后期收斂速度慢、易于陷入局部最優、疏于開發等問題.ZHU等[8]優化了蜜源產生位置的規則，在ABC算法中引入全局最優，提高了算法的開發能力；王偉等[9]將遺傳算法的交叉算子引入了ABC算法中，提出了一種基于交叉算子的改進人工蜂群算法(MABC)，提高了算法的局部搜索能力，加快了收斂速度；在DE算法的變異策略啟發下，GAO[10]等通過產生候選蜜源位置，改進了蜂群對蜜源的搜索能力，提出了GABC算法；劉三陽[11]等引入局部搜索算子，利用隨機局部搜索算子對當前最優進行局部搜索，加快了算法的收斂速度；AKAY[12]等通過控制擾動頻率來加快算法的收斂速度.

本文針對以上不足，結合文獻[8]的優點，在全局最優的基礎上引入交叉系數，提高局部優化能力，提出一種基于交叉的全局人工蜂群算法.

依據文獻[6]中的描述及搖擺舞(如圖1所示)和采蜜過程(如圖2所示)可知，ABC算法主要由4個基本組成元素：蜜源(食物源，Food Sources)、引領蜂(又稱采蜜蜂或雇傭蜂，Employed Foragers，EF)、跟隨蜂(又稱觀察蜂Onlookers或非雇傭蜂，Unemployed Foragers，UF)、偵察蜂(Scouts).其中引領蜂和跟隨蜂用來開采蜜源, 即尋找最優解, 而偵查蜂用來觀察是否陷入局部最優[13]；兩種基本的智能行為模式為：(1)招募(Recruit)行為：采蜜蜂在蜂巢跳舞區傳遞蜜源信息，招募待工蜂(觀察蜂)；(2)放棄(Abandon)行為：某個食物源被持續開采極限(Limit)次后，采蜜蜂放棄該蜜源成為偵察蜂.

蜜源即待求解問題的可行解，在算法中用“適應度”又稱“適應值”來描述蜜源(可行解)質量的好壞.

引領蜂也稱作雇傭蜂或采蜜蜂，在算法中其數量與已知的蜜源數量一致，占整個蜂群規模的一半.它具有記憶功能，存儲著蜜源的相關信息，它會將蜜源的相關信息在舞蹈區分享給觀察蜂(待工蜂)，并依據蜜源情況不斷更新自身位置選取更好的蜜源，提高了解的質量.

圖1 搖擺舞

圖2 蜂群采蜜過程圖

偵察蜂主要在蜂巢周圍搜索潛在的食物源，一旦找到新的食物源，則變為雇傭蜂即采蜜蜂.參考實驗數據和文獻[6]，偵察蜂數量在算法中大約占蜂群數量的5%～20%；跟隨蜂占整個蜂群規模的一半，主要是在舞蹈區觀察引領蜂(雇傭蜂)的搖擺舞(如圖1所示)，按蜜源與適應度值比例的概率，選擇自己認為滿意的蜜蜂進行跟隨.

招募行為：引領蜂在指定的區域內隨機搜索新蜜源，并計算適應度值大小，以此來判斷是否更新當前的食物源，并存儲蜜源相關信息.引領蜂回到蜂巢跳舞區通過搖擺舞來傳遞蜜源信息給跟隨蜂，跟隨蜂采用貪婪算法并以一定的概率選擇一只引領蜂跟隨，成為引領蜂.

放棄(Abandon)行為：當某個蜜源經歷了Limit次迭代后仍沒有改進時，則被強制放棄，其對應的引領蜂轉變為偵查蜂，重新隨機搜尋一個新的蜜源.

1.2 人工蜂群算法框架描述

根據求解組全優化問題的分析，可以建立利用ABC算法求解智能優化問題的數學模型，即

(1)

式中：D為優化問題的維數；f(x)為優化的目標函數；G為可行解的解空間的(可以用上下界來表示，如[lb,ub]).

在ABC算法中，蜜源亦即優化問題的解，通常用一個N維向量來表示；蜜源的優劣用優化函數的適應度值來衡量.算法框架描述如下.

1.2.1 初始化階段

初始化人工蜂群的規模(SN)、最大迭代次數(maxCycle)、最大開采次數(limit)；初始化SN/2個D維的可行解xi(xi1,xi2,…,xiD)T(i=1,2,…，SN).

(2)

1.2.2 引領蜂階段

引領蜂依據(2)式進行鄰域搜索，并采用貪婪算法或輪盤賭算法依據(3)式計算初始適應度值(fitness(xi))，并按(4)式求出對蜜源選擇的概率.

(3)

式中：f(x)為待優化的函數；fitness(xi)為函數的適應度值.

f(x)通常是一個在實數域內連續的函數，其值也是對應于實數域中的適應度值fitness(xi).從式(2)可以明顯看出，適應度值fitness(xi)越大，對應的目標函數值就越小.因此，標準ABC算法中fitness(xi)的最大值，即對應為求解式(1)的最小化問題.反之如果要求解優化問題的最大值，只需求出適應度值fitness(xi)的最小值.以上分析可用圖3所示的二維曲線圖[7]來描述.

圖3 目標函數與適應度轉化曲線圖

1.2.3 跟隨蜂階段

跟隨蜂依據(3)式計算跟隨概率Pi，搜索蜜源，并計算適應度值，選擇相關蜜源.

(4)

1.2.4 偵察蜂階段

偵察蜂在其鄰域范圍內隨機地搜索新的蜜源.當蜜源經過限定的最大開采次數(limit)后，如果仍然沒有改進，則在此采蜜的引領蜂就放棄此蜜源，并變為偵查蜂，從而重新按(2)式隨機選取新的蜜源，產生新蜜源位置.

2 基于交叉的全局人工蜂群算法

2.1 交叉操作

在ABC算法中，算法的效率及收斂的關鍵是如何設計好適應度函數、種群的更新過程和如何避免陷入局部最優.在ABC算法中，引領蜂從其阾域中隨機選取一個食物源進行迭代更新，這種方式更新得到的新的食物源，在算法中不能保證它就是一個質量較好的解，可能導致算法局部搜索能力的下降.為了更好地提高算法的全局和局部搜索能力，本文將遺傳算法中種群的交叉算子引入到GABC(全局最優解引導的人工蜂群算法)算法中，提出一種基于交叉的全局人工蜂群算法(Crossover of the Global Artificial Bee Colony，CGABC).

交叉操作是將種群的父代個體基因中優秀的基因遺傳給子代，通過配對方式進行基因交換重組，重新結合成新個體，在一定程度上充分提高了蜂群的多樣性，提高了算法整體的優化能力.

交叉操作常見的方式有指數交叉和二項交叉兩種[14].交叉操作是將選擇出的兩個個體作為父個體，將二者的部分碼值按位進行交換.設有兩個8位個體P1和P2，如圖4所示.

圖4 P1，P2個體

現隨機產生一個在1到7之間的數c=3，則依據交叉原理可將P1和P2的低三位交換后，得到一個新的個體.其交換過程如圖5所示.

圖5 交叉操作示意圖

在交叉操作中，對于二項交叉，對每一個分量都隨機地產生一個0～l之間的隨機數rand，若rand

(5)

式中：交叉算子cr一般取值為0.3～0.6；β的取值在0～1.5.

為進一步提高算法的探索和開發能力，在文獻[8]CABC算法思想啟發下，通過全局引導來加快算法的收斂速度和算法搜索能力，具體鄰域搜索公式改變如下：

k≠i

(6)

式中：β的取值在0～1.5；α∈[-1,1]之間的隨機值.

2.2 CGABC算法框架

基于交叉的全局人工蜂群算法(CGABC)借鑒了DE算法的基本思想和CABC算法的思想，在CABC的基礎上引入交叉算子[15]，提高了算法種群的多樣性和變異更新能力，達到了提高算法的開發能力和整體尋優能力效果.算法流程圖如圖6所示.CGABC算法步驟如下：

S1:算法各種參數和種群的初始化；

S2: 引領蜂(采蜜蜂)依據(6)式進行鄰域搜索，依據(3)式計算初始適應度值(fitness(xi))并記錄全局最優值(GlobalValue)和全局最優解向量(GlobalMin)；

S3:進入采蜜階段，引領蜂根據蜜源情況，采蜜蜂進行鄰域搜索，依據(6)式更新食物源，產生新的候選位置，并進行交叉操作.具體過程如下：

While(iter

采蜜蜂將鄰域搜索后的解與迭代產生的最優解按(5)式進行交叉操作，計算新的適應度值，根據貪婪算法選擇更優的蜜源.

按(4)式計算觀察蜂跟隨概率，并轉為采蜜蜂進行鄰域搜索，然后按(5)式交叉操作，按照貪婪算法選擇新的蜜源，并保留全局最優值；

偵察蜂隨機尋找新蜜源替換超過鄰域搜索限制次數的蜜源；

記錄全局最優解；

End while

圖6 算法流程圖

3 數值實驗仿真與分析

為了充分測試提出的基于交叉的全局人工蜂群(CGABC)算法的優越性，在此選取了單模和多模函數共計7個(如表1所示)，分別進行實驗仿真，并與標準ABC算法和全局ABC算法的實驗結果進行比較.其中，只有Sphere 為單模態函數，其余都是多模態函數，它們的理論最優值(最小值)都是0，在實驗中，蜂群大小BN=50，采蜜蜂數量=觀察蜂的數量=BN/2=25，所有優化函數維度D=30，最大迭代次數maxCycle=3 000，最大開采次數limit=300，交叉系數cr=0.3；實驗針對每個測試函數在上述參數設置下獨立運行10次，記錄其最優值、平均值、最劣值和標準差.表2給出了CGABC算法、ABC算法和GABC算法對表1中的7個測試函數進行仿真尋優結果的比較.圖7～圖13為7個測試函數的優化收斂比較圖.

表1 測試函數

編號函數名模式函數表達式取值范圍全局極小值F1Sphere單模fx()=∑Di=1x2i[-100,100]f0→()=0F2Rosenbrock多模fx()=∑D-1i=1100[(xi+1-x2i)2+(xi-1)2][-2.048,2.048]f1→()=0F3Schaffer多模fx()=0.5+sin2 ∑Di=1x2i()-0.5(1+0.001(∑Di=1x2i))2[-100,100]f0→()=0F4Schwefel多模fx()=D*418.9829-∑Di=1x2isin( xi)[-500,500]f420.96→()=0F5Ackley多模 fx()=-20e-0.2 1D∑Di=1x2i()-e1D∑Di=1cos2πxi()+20+e[-32,32]f0→()=0F6Rastrigin多模fx()=∑D-1i=1x2i[-10cos2πxi()+10][-5.12,5.12]f0→()=0F7Griewank多模fx()=14000∑Di=1x2i-∏Di=1cosxi i()+1[-600,600]f0→()=0

表2 測試函數優化結果對比表

函數名算法全局極小值最劣值平均值標準差SphereABC4.55409×10-167.50686×10-165.72005×10-169.38136×10-17GABC2.63053×10-165.5108×10-165.0541×10-168.50722×10-17CGABC2.38339×10-163.28075×10-162.97085×10-162.65856×10-17RosenbrockABC0.1293804673.4995705431.2340769940.989323071GABC0.0029668641.7454077920.6157354010.613216816CGABC0.0585532680.4356478390.1964641660.109650872SchafferABC0.2276901410.3732906940.3404386050.045531083GABC0.1782223040.373290650.3036420660.051266344CGABC0.2727410960.3455094940.3097199320.032563777SchwefelABC0.0003818270.0003818270.0003818279.795557710-13GABC3.8182699×10-43.8182699×10-43.8182699×10-48.335656610-13CGABC3.8182699×10-43.8182699×10-43.8182699×10-40AckleyABC3.9968×10-144.35207×10-144.17444×10-141.77636×10-15GABC2.93099×10-144.35207×10-143.89022×10-144.21861×10-15CGABC2.930988×10-143.9968029×10-143.6415315×10-143.5527137×10-15RastriginABC05.68434×10-141.13687×10-142.27374×10-14GABC0000CGABC0000GriewankABC1.1102230×10-164.4408921×10-161.5543122×10-161.0175362×10-16GABC1.1102230×10-162.2204460×10-161.2212453×10-163.3306691×10-17CGABC1.1102230×10-161.1102230×10-161.1102230×10-160

圖7 Sphere函數收斂圖

圖 8 Rosenbrock函數收斂圖

圖9 Schaffer函數收斂圖

圖 10 Schwefel函數收斂圖

圖11 Ackley函數收斂圖

圖12 Rastrigin函數收斂圖

圖13 Griewank函數收斂圖

從表2和圖7～13的尋優收斂曲線圖可以看出，不管是單模態還是多模態的函數，CGABC算法性能優于標準ABC算法和GABC蜂群算法，它能更快速地收斂于最優值點，效果有了明顯的提升.

4 結束語

人工蜂群算法是一種新型的群體智能優化算法，因特有的勞動分工、自組織、貪婪選擇和協作機制，算法靈活，不依賴于問題的梯度而具有廣泛的適用性.本文利用交叉算子對全局優化算法進行改進，通過對函數的測試，表明該算法在求解多模態函數的全局優化問題時，在收斂速度、優化精度、收斂成功率和穩定性等方面的性能更優于標準人工蜂群算法.改進后的算法可在多目標優化問題及相關工程領域廣泛應用.

[1] COLORNI A, DORIGO M, MANIEZZO V. Distributed optimization by ant colonies[C]// Varela F J, Bourgine P. Proceedings of the First European Conference on Artificial Life. Second Printing Edition. Paris：Elsevier,1992:134-142.

[2] KENNEDY J. Particle Swarm Optimization[M]. New York: Spring US，2011:760-766.

[3] 李曉磊,邵之江,錢積新.一種基于動物自治體的尋優模式:魚群算法[J].系統工程理論與實踐，2002(11):32-38.

[4] KRISHNANAND K N, GHOSE D. Detection of multiple source locations using a glowworm metaphor with applications to collective robotics[C]// Symposium I S I .Proceedings 2005 IEEE Swarm Intelligence Symposium. Pasadena: IEEE,2005:84-91.

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

[6] KARABOGA D. An idea based on honey bee swarm for numerical optimization: Technical report-tr06[R].Kayseri: Erciyes University,2005.

[7]張偉. 人工蜂群混合優化算法及應用研究[D]. 杭州：浙江大學, 2014.

[8]ZHU G, KWONG S. Gbest-guided artificial bee colony algorithm for numerical function optimization[J]. Applied Mathematics and Computation, 2010, 217(7): 3 166-3 173.

[9]王偉,龍文.基于交叉算子的改進人工蜂群算法[J].蘭州理工大學學報，2015,41(1):101-106.

[10] GAO W, LIU S. A modified artificial bee colony algorithm[J]. Computers & Operations Research, 2012, 39(3): 687-697.

[11] 劉三陽,張平,朱明敏.基于局部搜索的人工蜂群算法[J].控制與決策，2014,(1):123-128.

[12] AKAY B, KARABOGA D. A modified artificial bee colony algorithm for real-parameter optimization[J]. Information Sciences, 2012, 192: 120-142.

[13]寧愛平,張雪英.人工蜂群算法的收斂性分析[J].控制與決策，2013(10):1 554-1 558.

[14]喬艷霞,鄒書蓉,張洪偉.基于K-means的改進差分進化聚類算法[J].四川理工學院學報( 自然科學版)，2014,27(5):64-67.

[15] 邱劍鋒,謝娟,汪繼文.基于交叉突變算子的人工蜂群算法及其應用[J].計算機應用研究，2014(5):1 336-1 341.

(編輯：郝秀清)

Research on global artificial bee colony algorithm based on crossover

ZHANG Ping-hua1，LI Jing-ming2，HU Xian-de1，HU Jun1

(1.School of Information Engineering, Anhui Xinhua University, Hefei 230088, China;2.School of Management, Hefei University of Technology, Hefei 230009, China;)

The shortcomings of artificial bee colony algorithm include slow convergence speed，easily falling into local optimum value，neglect of development and other issues. In order to overcome these problems,referencing the mechanism of other bionic intelligent optimization algorithms, a new algorithm of global artificial bee colony algorithm based on crossover is proposed, which can effectively improve the convergence rate, enhance the development of the algorithm and the global optimization ability, and the algorithm can effectively avoid the local optimum. Finally,seven standard test functions are selected to carry out the experiment and simulation. The results show that the convergence speed and accuracy of the proposed algorithm (CGABC) are significantly improved compared with other algorithms such as ABC algorithm, GABC algorithm and so on.

intelligent algorithm; cross; global; artificial bee colony algorithm

2016-09-07

國家自然科學基金項目(71271071);安徽省自然科學基金項目(KJ2016A304，KJ2016A308)

張平華，男，zphpinganye@qq.com

1672-6197(2017)05-0006-06

TP301.6； TP18

A