程憲寶

(廣州工商學(xué)院 計算機(jī)科學(xué)與工程系， 廣東 廣州 510850)

基于二項式交叉改進(jìn)的人工蜂群算法

程憲寶

(廣州工商學(xué)院 計算機(jī)科學(xué)與工程系， 廣東 廣州 510850)

摘要：為了克服人工蜂群算法容易過早收斂和在接近全局最優(yōu)時搜索速度變慢、疏于開發(fā)的缺陷，提出一種基于二項式交叉改進(jìn)的人工蜂群算法.改進(jìn)算法引入全局最優(yōu)值，通過二項交叉將鄰域搜索的最優(yōu)值與全局最優(yōu)值進(jìn)行比較，以加快算法的收斂速度，提高算法在最優(yōu)解附近的開發(fā)能力.通過7個基準(zhǔn)函數(shù)進(jìn)行仿真測試發(fā)現(xiàn)：和標(biāo)準(zhǔn)的人工蜂群算法相比，改進(jìn)的人工蜂群算法有較好的收斂速度和收斂精度，有效提高了原算法的全局尋優(yōu)能力，且并未大量增加算法的復(fù)雜度，是一種有效的優(yōu)化算法.

關(guān)鍵詞：人工蜂群算法；優(yōu)化；二項式交叉；基準(zhǔn)函數(shù)

人工蜂群算法(artificial bee colony, ABC)是近年發(fā)展起來的人工智能算法之一，該算法思想簡單、參數(shù)少、易于實現(xiàn)，目前已在函數(shù)優(yōu)化、數(shù)據(jù)挖掘及生產(chǎn)調(diào)度等鄰域得到了廣泛應(yīng)用[1].人工蜂群算法在執(zhí)行全局探測時僅應(yīng)用隨機(jī)化個體一種策略，方法單一且效果不明顯，因此需要更加有效的全局搜索策略，以使算法能跳出局部極值避免早熟[2].

解決收斂到局部極值問題的關(guān)鍵就是增加進(jìn)化群體的物種多樣性和提高全局搜索能力，但增加多樣性的同時易導(dǎo)致進(jìn)化系統(tǒng)后期的振蕩，不能快速收斂于全局最優(yōu)點.人工蜂群算法在接近全局最優(yōu)時，存在搜索速度變慢、過早收斂、個體多樣性減少等問題，極易陷入局部最優(yōu).Zhu和Kwong[2]提出了一種全局最優(yōu)引導(dǎo)的人工蜂群算法(GABC)，參照粒子群算法將全局最優(yōu)項加入人工蜂群搜索公式，從而提高了人工蜂群算法的尋優(yōu)能力.Wang[3]采用類似的方法，在每次迭代中隨機(jī)取較優(yōu)值的一個值作為全局最優(yōu)值.Abdul[4]在迭代算法中，不僅引入全局最優(yōu)值，還引入全局次優(yōu)值.Zhang[5]在以上基礎(chǔ)上引入了線性權(quán)值，以提高蜂群算法的開發(fā)能力，Akbari[6]提出一種針對不同類型的蜂采用不同的搜索方法.Gao[7]針對人工蜂群算法求解時搜索公式的不足，提出通過產(chǎn)生一個候選解來提高算法的搜索能力的算法.尹雅麗等[8]提出一種基于轉(zhuǎn)軸法的導(dǎo)向人工蜂群算法，利用方向引導(dǎo)信息來指導(dǎo)個體朝更優(yōu)方向搜索，以加快收斂速度和算法的開采能力.Guo等[9]將粒子群算法公式中的全局社會項增加到人工蜂群算法中，構(gòu)建全局人工蜂群算法(GABCS)，以提高優(yōu)化算法的搜索能力，但和粒子群算法相似，算法復(fù)雜度更高.張?zhí)┑萚10]提出一種增強(qiáng)尋優(yōu)能力的自適應(yīng)人工蜂群算法，利用邏輯自映射函數(shù)產(chǎn)生混沌序列對雇傭蜂搜索行為進(jìn)行混沌優(yōu)化.本文根據(jù)人工蜂群算法缺陷，提出一種基于遺傳算法二項式交叉的改進(jìn)人工蜂群算法，有效增加個體向量的多樣性，避免群體陷入局部最優(yōu).改進(jìn)算法引入全局最優(yōu)值，將局部最優(yōu)和當(dāng)前全局最優(yōu)進(jìn)行比較，大大提高算法的開發(fā)能力.相對于結(jié)合粒子群算法的改進(jìn)，算法復(fù)雜度并未顯著增加.通過仿真實驗表明這種改進(jìn)人工蜂群算法大大提高了原ABC算法的性能.

1人工蜂群算法

蜜蜂尋找食物源的過程就是尋優(yōu)問題找最優(yōu)解的過程.首先要初始化種群，明確蜜蜂的總數(shù)、最大循環(huán)次數(shù)、最大限制搜索次數(shù)limit.初始種群中包含N個可行解，解的數(shù)量和引領(lǐng)蜂的數(shù)目相等.

初始化種群后，引領(lǐng)蜂會在每個食物源周圍進(jìn)行搜索，按照“貪婪算法”的思想進(jìn)行優(yōu)勝劣汰，在搜索次數(shù)未達(dá)到預(yù)定的次數(shù)之前，一直循環(huán)進(jìn)行.ABC算法對食物源xi的鄰域進(jìn)行搜索，依據(jù)式(1)產(chǎn)生新的食物源vi(vi1,vi2,…,viN).

(1)

式中，q為[1,N]間的隨機(jī)整數(shù)，且q≠i，即根據(jù)上式生成新的蜜源xq=(xq1,xq2,…，xqD)，且xq與xi不同，drand為[1,N]之間的隨機(jī)整數(shù)，rid∈[-1,1]是一個-1到1之間的隨機(jī)整數(shù)，用來控制引領(lǐng)蜂鄰域搜索范圍.

由式(1)可以看出，隨著xid和xqd的差值逐漸減小，新位置的產(chǎn)生的波動也越來越小.隨著循環(huán)的進(jìn)行，搜索會漸漸接近最優(yōu)解，xid-xqd會自適應(yīng)的減少，因此算法具有自適應(yīng)的收斂性.

當(dāng)引領(lǐng)蜂完成搜索后，會記下蜜源相關(guān)信息(質(zhì)量、方向、距離等)飛回蜂巢，在特定區(qū)域以“8”字舞或“搖擺”舞或其它方式向跟隨蜂傳遞蜜源信息.跟隨蜂以輪盤賭的方式選擇蜜源，質(zhì)量好且距離近的蜜源會招募到較多的跟隨蜂，跟隨蜂根據(jù)引領(lǐng)蜂所傳達(dá)的信息到達(dá)所選擇的蜜源位置后，在蜜源周圍進(jìn)行鄰域搜索，和引領(lǐng)蜂一樣利用“貪婪算法”優(yōu)勝劣汰進(jìn)行選擇.

引領(lǐng)蜂根據(jù)“貪婪算法”選擇后，如果經(jīng)過Limit次后都沒有更新蜜源，表明在當(dāng)前鄰域中所選擇的蜜源已經(jīng)是質(zhì)量最好的，即當(dāng)前解是局部最優(yōu)解，從算法的角度講，算法已陷入局部最優(yōu)，該蜜源應(yīng)該被放棄.此時，引領(lǐng)蜂轉(zhuǎn)換成偵查蜂，重新生成新的蜜源.找到蜜源后偵查蜂又變成引領(lǐng)蜂，重復(fù)算法搜索過程.

如果搜索達(dá)到預(yù)先設(shè)定好的循環(huán)最大次數(shù)，或是根據(jù)所求問題精度需要，達(dá)到程序結(jié)束條件，則算法結(jié)束，完成搜索.

2改進(jìn)的人工蜂群算法

2.1ABC算法的局限

ABC算法具有較強(qiáng)的鄰域搜索能力，但因算法未有全局最優(yōu)值記憶和參與算法過程，致使該算法很容易因全局探測能力不足而陷入局部最優(yōu)解.文獻(xiàn)[2]中提出了一種基于全局最優(yōu)解引導(dǎo)的人工蜂群算法(GABC)，較好的增強(qiáng)了算法的開發(fā)能力，在xid=xid.min+(xid.max-xid.min)rand之上增加了一個調(diào)配選項.通過大量仿真數(shù)據(jù)證明通過第3項來平衡算法的探索和開發(fā)能力會在一定程度上降低算法的全局尋優(yōu)能力[11].基于此，借鑒遺傳算法中交叉運算來加強(qiáng)蜂群算法的開發(fā)能力，引入全局最優(yōu)解，提出一種基于二項式交叉運算的全局人工蜂群算法.

2.2基于二項式交叉改進(jìn)的算法

將多種智能算法結(jié)合研究，已經(jīng)是對各算法研究的一個重要方向.遺傳算法早已被證明是具有良好收斂速度和搜索開發(fā)能力的智能算法，被廣泛應(yīng)用到各種復(fù)雜的求解和優(yōu)化問題，其操作包括選擇、開發(fā)和變異.遺傳算法的交叉運算有多種，常見的有二項式交叉和指數(shù)交叉.也有針對遺傳算法和人工蜂群算法相結(jié)合的研究，文獻(xiàn)[12]引入遺傳算法中的變異操作，提出一種人工蜂群算法及跟隨蜂選擇及搜索的混合遺傳算法.文獻(xiàn)[13]提出蜂群遺傳算法，在蜂群算法的局部搜索部分，引入混沌搜索算法進(jìn)行區(qū)域優(yōu)化.文獻(xiàn)[14]提出將遺傳算法中的交叉算子應(yīng)用到ABC算法中來提高算法的能力.這些算法的改進(jìn)已經(jīng)證明能夠有效提高人工蜂群算法的優(yōu)化能力.文獻(xiàn)[13-14]是將按一定概率隨機(jī)選擇的個體與當(dāng)前最優(yōu)個體進(jìn)行交叉操作.本文是將當(dāng)前局部最優(yōu)個體與全局最優(yōu)個體進(jìn)行交叉操作，算法收斂速度更快，開發(fā)能力更強(qiáng).算法采用最有效二項交叉模式與人工蜂群算法結(jié)合，并引入全局最優(yōu)解來提高人工蜂群算法的搜索和開發(fā)能力.

引入交叉操作的目的是增加個體向量的多樣性，避免群體陷入局部最優(yōu)，具體操作是這樣的，首先對每一個解分量都生成一個0到1之間均勻分布的隨機(jī)值rand，這個隨機(jī)值和二項式交叉系數(shù)cr進(jìn)行比較，如果rand

(2)

式中cr稱為交叉因子，是二項式交叉運算中的重要參數(shù).從理論上講，cr取較大的值時，進(jìn)化速度會加快，有利于算法的開發(fā)能力，但是會降低其探索能力，cr越小越有利于增強(qiáng)算法的探索能力，但是會降低算法的開發(fā)能力，經(jīng)過多次反復(fù)實驗，在cr=0.6時，無論極值點多少都能取得不錯優(yōu)化效果，本文采用的cr的值為0.6.

2.3改進(jìn)的人工蜂群算法流程

由文獻(xiàn)[15]可知，對于任意給定的兩個父代個體，在進(jìn)行算術(shù)交叉操作后所產(chǎn)生的新子代個體必定位于兩個父代個體之問的連線上.當(dāng)引領(lǐng)蜂進(jìn)行鄰域搜索后與全局最優(yōu)值進(jìn)行交叉操作，生成的新的個體比局部最優(yōu)值更接近當(dāng)前全局最優(yōu)值，算法的收斂速度會加快.從理論上來講，引領(lǐng)蜂進(jìn)鄰域搜索后與全局最優(yōu)值進(jìn)行交叉操作有助于提高人工蜂群算法的開發(fā)能力，但是單純與全局最優(yōu)進(jìn)行二項交叉會限制算法的探索能力，為了增加算法的搜索能力，新個體的產(chǎn)生按式(3)來產(chǎn)生

(3)

式中β為-1到1之間的隨機(jī)值，這樣可以避免過多的降低算法的探索能力，出現(xiàn)提前收斂的情況.

改進(jìn)算法運行的流程如圖1所示.

圖 1　改進(jìn)的算法流程

3仿真研究

3.1測試函數(shù)

為了檢驗人工蜂群法的效果，選取7個常用的測試函數(shù)進(jìn)行實驗(表1)，并將改進(jìn)算法(CABC，crossoverartificialbeecolonyalgorithm)與ABC算法進(jìn)行比較，主要測試算法的收斂速度和優(yōu)化精度.其中單峰函數(shù)極值數(shù)目較少，可以檢驗算法的收斂速度，多峰函數(shù)極值較多，對算法尋找極值會造成一定的干擾，可以用來檢驗算法的尋優(yōu)能力.仿真的數(shù)據(jù)以最優(yōu)值，最劣值，平均值和收斂性表示，收斂性=(最優(yōu)值-最劣值)/平均值，可以反應(yīng)算法的收斂速度.

表1測試函數(shù)

測試函數(shù)函數(shù)名稱類型函數(shù)表達(dá)式搜索范圍最優(yōu)值F1Sphere單峰f1(x)=∑Di=1x2i[-100,100]0F2Rastrigin多峰f2(x)=∑Di=1[x2i-10cos(2πxi)+10][-5.12,5.12]0F3Schaffer多峰f3(x)=0.5+sin2∑Dix2i()-0.51+0.001∑Dix2i()()2[-100,100]0F4Schwefel多峰f4(x)=D*418.9829-∑Di=1xisinxi()[-500,500]0F5Griewank多峰f5(x)=14000∑Di=1x2i-∏Di=1cosxii()+1[-600,600]0F6Rosenbrock單峰f6(x)=∑D-1i=1[100(xi+1-x2i)2+(xi-1)2][-2.048,2.048]0F7Ackley多峰f7(x)=-20exp-0.21D∑Di=1x2i?è???÷-exp1D∑Di=1cos(2πxi)()+20+e[-32,32]0

3.2仿真結(jié)果與分析

表2為仿真的結(jié)果.圖2為改進(jìn)算法和原算法對7個測試函數(shù)的求解變化趨勢，其中，函數(shù)F2、F7為迭代次數(shù)為5000，D=60時的仿真效果，F(xiàn)1、F3～F6設(shè)置迭代次數(shù)為1000，D=30，每個函數(shù)的效果圖都是10次優(yōu)化平均得到的結(jié)果.

表2兩種算法的性能比較

測試函數(shù)算法最優(yōu)值最劣值收斂性平均值F1ABC1.329752×10-171.435960×10-165.352417×10-172.434386CABC9.476235×10-189.695876×10-174.189673×10-172.088051F2ABC1.868805×10-173.914328×10-162.964618×10-171.257311×101CABC1.003313×10-184.254637×10-171.023359×10-174.059480F3ABC5.030180×10-48.337963×10-32.239765×10-33.498109CABC5.621974×10-171.234433×10-166.664257×10-171.008718F4ABC2.576932×10-72.965873×10-52.874321×10-61.022886×101CABC2.523370×10-172.958732×10-162.763155×10-169.794584×10-1F5ABC3.957433×10--51.499873×10-24.319765×10-33.462956CABC4.379825×10-171.120134×10-168.890142×10-177.673125×10-1F6ABC3.329785×10-51.632765×10-33.960258×10-44.038797CABC1.709347×10-189.728362×10-175.494431×10-171.739475F7ABC1.379256×10-171.943579×10-171.492536×10-173.780966×10-1CABC2.536924×10-181.025796×10-177.462514×10-171.034643×10-1

(a) F1函數(shù)　　　　　　　　　(b) F2函數(shù)

(c) F3函數(shù)　　　　　　　　　(d) F4函數(shù)

(e) F5函數(shù)　　　　　　　　　(f) F6函數(shù)

(g) F7函數(shù)圖2　兩種算法對7個測試函數(shù)的求解變化趨勢比較圖

仿真結(jié)果顯示，改進(jìn)算法與人工蜂群算法相比，在優(yōu)化精度和優(yōu)化速度上較原算法都有顯著提高.

4結(jié)束語

由于標(biāo)準(zhǔn)人工蜂群算法存在著容易過早收斂、陷入局部最優(yōu)值的缺陷，基于此本文提出一種基于二項式交叉的全局人工蜂群算法的改進(jìn)，在局部搜索的同時，引入全局最優(yōu)值，有效避免了算法陷入局部最優(yōu)，增強(qiáng)了算法的方向性和全局最優(yōu)值附近的開發(fā)能力.通過7個基準(zhǔn)函數(shù)的仿真實驗，證明本改進(jìn)算法在優(yōu)化精度和優(yōu)化速度上較原算法都有較大的提高.主要原因是通過引入交叉機(jī)制，將采蜜蜂領(lǐng)域搜索的解與全局最優(yōu)解進(jìn)行概率交叉，這種方式克服了人工蜂群算法疏于開發(fā)的缺陷，增強(qiáng)了算法方向性，大大提高了人工蜂群算法在最優(yōu)解附近的開發(fā)能力.與此同時，引入cr的值來取得滿意的解，增強(qiáng)了算法對各種優(yōu)化問題的適應(yīng)能力.本算法的改進(jìn)并未太多增加算法的復(fù)雜性，清晰明了，具有較強(qiáng)的實用性，可以方便的應(yīng)用于各種優(yōu)化問題.

參考文獻(xiàn)：

[1]TasgetirenMF,PanQK,SuganthanPN,AngelaH-Lchen.Adiscreteartificialbeecolonyalgorithmforthetotalflowtimeminimizationinpermutationflowshops[J].InformationSciences,2011,181(16):3459-3475.

[2]ZhuG,KwongS.Gbest-tuidedartificialbeecolonyalgorithmfornumericalfunctionoptimization[J].AppliedMathematicsandComputation, 2010, 217(7):3166-3173.

[3]WangB,WangL.Anovelartificialbeecolonyalgorithmfornumericalfunctionoptimization[C] //Proceedingsof2012 14thInternationalConferenceonComputationalandInformationSciences.Chongqing:ICCIS,2012:172-175.

[4]AbdulGA,JunitaMS.Enhancedglobal-bestartificalbeecolonyoptimizationalgorithm[C] //Proceedingsof2012UKSim-AMSS6thEuropeanModellingSymposium.Valetta:UKSim, 2012:95-100.

[5]ZhangY,ZengP,WangY,etal.Linearweightedgbest-guidedartificialbeecolonyalgorithm[C] //Proceedingsof2012 5thInternationalSymposiumonComputationalIntelligenceandDesign.Hangzhou:ISCID,2012:155-159.

[6]AkbariR,MohammadiA,ZiaratiK.ANovelbeeswarmoptimizationalgorithmfornumericalfunctionoptimization[M].//CommunNonlinearSciNumerSimulat. [s.l.]:2010,15:3142-3155.

[7]GaoWF,LiuSY,HuangLL.Anovelartificialbeecolonyalgorithmbasedonmodifiedsearchequationandorthogonallearning[J].IEEETransactiononSystems,ManandCybernetics, 2013,43(3):1011-1024

[8]尹雅麗，熊小峰，郭肇祿.基于轉(zhuǎn)軸法的導(dǎo)向人工蜂群算法[J] 江西理工大學(xué)學(xué)報,2015,26(5):45-48

[9]KarabogaD,BasturkB.Ontheperformanceofartificialbeecolony(ABC)algorithm[J].AppliedSoftComputing, 2008:8(1):687-697.

[10] 張?zhí)?，屠思遠(yuǎn)，吳濱，等 增強(qiáng)尋優(yōu)能力的自適應(yīng)人工蜂群算法[J] 計算機(jī)應(yīng)用研究 2015,33(11):25-26

[11] 侯麗萍，石磊. 一種新型混合遺傳算法及其應(yīng)用[J].科技通報,2012,28(5):159-162.

[12] 趙志,黃文杰. 改進(jìn)人工蜂群算法及在風(fēng)電場群調(diào)度中的應(yīng)用[J].中南大學(xué)學(xué)報,2011,42 (10):3012.

[13]YanXH,ZhuYL,ZouWP.Ahybridartificialbeecolonyalgorithmfornumercialfuncitonoptimization[C] //11thInternationalConferenceonHybridIntelligentSystems.Melacca:HIS,2011:127-132

[14] 宋佩莉，祁飛，張鵬. 混合蟻群算法在旅行Agent問題中的應(yīng)用[J].計算機(jī)工程與應(yīng)用,2012,48 (36):34-48.

[15]GenM,ChengRW.Geneticalgorithmandengineeringdesign[M].NewYork:JohyWiley&Sons,1997.

(編輯：姚佳良)

Improved artificial bee colony algorithm based on binomial crossover

CHENG Xian-bao

(Department of Computer Science and Engineering, Guangzhou College of Technology and Business， Guangzhou 510850， China)

Abstract:In order to overcome the artificial bee colony algorithm is easily premature convergence, search speed becomes slow near global optimal and bothers to develop,we proposed a kind of artificial bee colony algorithm based on improved binomial crossover.The improved algorithm introduced the global optimal value,and compared the optimal values of the neighborhood search with the global optimal values by binomial crossover, to speed up the convergence of the algorithm,and improve the development of the algorithm.The experimental results of 7 benchmark functions show that improved artificial colony algorithm has better convergence speed and convergence precision, improves the global optimization ability of the original algorithm effectively, compared with the original algorithm. It does not increase the complexity of the algorithm,and it is an effective optimization algorithm.

Key words:artificial bee colony algorithm(ABC); optimization; binomial crossover; bechmark function

收稿日期：2015-12-23

作者簡介：程憲寶，男，luyu1233@163.com

文章編號：1672-6197(2016)05-0074-05

中圖分類號：TP301.6

文獻(xiàn)標(biāo)志碼：A