基于二項式交叉改進的人工蜂群算法

程憲寶

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

基于二項式交叉改進的人工蜂群算法

程憲寶

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

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

關鍵詞：人工蜂群算法；優化；二項式交叉；基準函數

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

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

1人工蜂群算法

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

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

(1)

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

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

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

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

如果搜索達到預先設定好的循環最大次數，或是根據所求問題精度需要，達到程序結束條件，則算法結束，完成搜索.

2改進的人工蜂群算法

2.1ABC算法的局限

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

2.2基于二項式交叉改進的算法

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

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

(2)

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

2.3改進的人工蜂群算法流程

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

(3)

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

改進算法運行的流程如圖1所示.

圖 1　改進的算法流程

3仿真研究

3.1測試函數

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

表1測試函數

測試函數函數名稱類型函數表達式搜索范圍最優值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仿真結果與分析

表2為仿真的結果.圖2為改進算法和原算法對7個測試函數的求解變化趨勢，其中，函數F2、F7為迭代次數為5000，D=60時的仿真效果，F1、F3～F6設置迭代次數為1000，D=30，每個函數的效果圖都是10次優化平均得到的結果.

表2兩種算法的性能比較

測試函數算法最優值最劣值收斂性平均值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函數　　　　　　　　　(b) F2函數

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

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

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

仿真結果顯示，改進算法與人工蜂群算法相比，在優化精度和優化速度上較原算法都有顯著提高.

4結束語

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

參考文獻：

[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]尹雅麗，熊小峰，郭肇祿.基于轉軸法的導向人工蜂群算法[J] 江西理工大學學報,2015,26(5):45-48

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

[10] 張泰，屠思遠，吳濱，等 增強尋優能力的自適應人工蜂群算法[J] 計算機應用研究 2015,33(11):25-26

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

[12] 趙志,黃文杰. 改進人工蜂群算法及在風電場群調度中的應用[J].中南大學學報,2011,42 (10):3012.

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

[14] 宋佩莉，祁飛，張鵬. 混合蟻群算法在旅行Agent問題中的應用[J].計算機工程與應用,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

文獻標志碼：A