王劍，王冰，葛孟珂

摘要：提出基于反向學習的人工蜂群算法（簡稱OABC算法）.在人工蜂群算法的跟隨蜂階段，種群依概率進行反向學習代替跟隨蜂搜索方案.保留標準人工蜂群算法中雇傭蜂和偵察蜂階段以保證種群的探索能力以及種群的多樣性，增設參數(shù)控制一般的反向學習過程中對位搜索范圍，充分利用種群信息和個體信息優(yōu)化種群，提高對位點的有效性，從而提高反向學習的成功率.仿真實驗結果表明，OABC算法有效提升了算法尋優(yōu)速度和收斂精度.

關鍵詞：人工蜂群算法;反向學習;對位鄰域;函數(shù)優(yōu)化

[中圖分類號]TP301.6[文獻標志碼]A

An Improved Artificial Bee Colony Algorithm with

Opposition-based Learning

WANG Jian，WANG Bing*，GE Mengke

（College of Mathematical Sciences;Mudanjiang Normal University，Mudanjiang 157011，China）

Abstract：An improved artificial bee colony algorithm with opposition-based learning（OABC algorithm for short） is proposed.In the following bee phase of the artificial bee colony algorithm，the population implement opposition-based learning according to probability instead of following bee search，retains the employed bee phase and scout bee phase in the standard artificial bee colony algorithm to ensure the exploration ability and diversity of the population，and adds parameters to control the contraposition search range in the general opposition-based learning process，It makes full use of population information and individual information to optimize the population，improves the effectiveness of counterpoint，and improves the success rate of opposition-based learning.Simulation results show that the OABC algorithm effectively improves the optimization speed and convergence accuracy of the algorithm.

Key words：artificial bee colony algorithm;opposition-based learning;counterpoint neighborhood;function optimization

人工蜂群算法（artificial bee colony，ABC）是由土耳其學者 Karaboga[1]于2005年提出的.ABC算法因其過程簡單、計算容易、需要調整的參數(shù)較少以及收斂速度具有競爭力等優(yōu)點而被廣泛關注和研究.[2-7]學者們對其所做的改進方式各不相同，其中設計多階段算法是一種有效的方式.反向學習（opposition based learning，OBL）算法是多階段算法的代表之一，其關鍵思想在于充分利用適應度信息，選擇較好的個體組成種群.為使初始解具有多樣性，較均勻地分布在搜索空間，Rahnamayan[8]等人首先將反向學習應用在差分進化算法中，并得到不錯的效果.在改進人工蜂群算法方面，反向學習多應用于種群初始化.暴勵[9]等采用反向學習方法產(chǎn)生初始解.Gao[10]等人在種群初始化階段采用基于混沌序列的反向學習方法，研究參數(shù)的細微變化對初始種群分散程度的影響;分析搜索維數(shù)對算法性能的影響，在搜索方程中加入了優(yōu)秀個體信息，增強算法的開發(fā)能力;利用隨機個體信息來保證種群的多樣性.這些改進方式使得ABC算法的性能有所提升，但在處理具體優(yōu)化問題時，反向學習策略對人工蜂群算法的收斂速度和收斂精度的平衡作用還有很大的提升空間.

本文基于反向學習的人工蜂群算法（簡稱OABC算法），對一般的反向學習策略做了調整，并將此策略應用在跟隨蜂階段，使得跟隨蜂全體或是執(zhí)行反向學習策略或是執(zhí)行標準ABC算法中跟隨蜂策略.通過反向學習策略，群體能夠充分利用種群信息來尋找最優(yōu)值的潛在區(qū)域，在一定程度上提高算法的搜索精度.基于反向學習的人工蜂群算法仍然保留標準ABC算法跟隨蜂和偵察蜂搜索機制，保證種群的探索能力和種群的多樣性，以此種方式來平衡算法的探索和開發(fā)能力.測試結果表明，基于反向學習的人工蜂群算法在精度和速度方面均優(yōu)于ABC算法.

1標準人工蜂群算法

人工蜂群算法區(qū)別于其他群智能算法最顯著的特點在于蜂群角色的轉換，在ABC算法中，蜜源的位置代表空間中的解，花粉量代表解的適應度.蜜蜂分為三類，分別是雇傭蜂、跟隨蜂、偵察蜂，其中雇傭蜂和跟隨蜂各占蜂群數(shù)量的近一半，雇傭蜂記錄當前最優(yōu)解，跟隨蜂負責在蜜源附近搜索新的解，偵察蜂負責當前蜜源枯竭時隨機選取新的蜜源，進而避免陷入局部最優(yōu).

1.1蜂群初始化

對算法的基本參數(shù)進行設定.主要有蜜源i

（i=1，2，…，SN，SN為雇傭蜂或跟隨蜂的數(shù)量），蜜源迭代閾值limit，種群最大進化次數(shù)MAXFE.設目標函數(shù)維度為D，即每個蜜源是一個D維向量，在某個蜜源i附近進行第t次采蜜的位置表示為Xti=xti1，xti2，…，xtiD，xtid∈（mind，maxd）.其中，mind，maxd分別表示第d維搜索空間的下限和上限，d=1，2，…，D.蜜源i的初始位置由（1）式生成：

x0id=mind+rand（0，1）（maxd-mind）.（1）

初始化蜜源位置由（1）式對每個維度d隨機生成.

1.2雇傭蜂階段

在搜索開始階段，雇傭蜂在蜜源i的附近根據(jù)式（2）產(chǎn)生一個新蜜源：

xtid=xtid+φ（xtid-xtjd）.（2）

其中，d為[1，2，…，d的隨機數(shù)，代表著隨機對某一維度進行搜索.j=1，2，…，SN，且j≠i，即j為不同于i的蜜源，φ為[-1，1]的均勻分布隨機數(shù)，決定個體信息受其他個體影響的程度.通過（2）式得到新的蜜源后，計算其適應度fit，利用貪婪選擇策略對新舊蜜源擇優(yōu)選取.為不失一般性，以最小化優(yōu)化問題為例，適應度函數(shù)為：

fiti=1/（1+fi），fi≥0，

1+abs（fi），fi<0..（3）

其中，fi為目標函數(shù)值.

1.3跟隨蜂階段

所有雇傭蜂獲得各自優(yōu)質蜜源位置信息后，回到蜂巢，分享蜜源信息，跟隨蜂依據(jù)（4）式計算概率，進行跟隨.

Pi=fiti∑SNi=1fiti.（4）

跟隨蜂采用輪盤賭的方式?jīng)Q定其所跟隨的雇傭蜂，即首先按照均勻分布在[0，1]生成一個隨機數(shù)r，然后選擇首個滿足r

1.4偵察蜂階段

當某個蜜源經(jīng)過多次開采卻沒有得到更新時，即沒有得到更好的解，而迭代次數(shù)達到蜜源開采閾值limit時，需放棄當前蜜源，雇傭蜂轉變?yōu)閭刹旆?，按照?）式隨機生成一個新的蜜源，同時對應的traili置零.

當達到指定進化次數(shù)后，整個蜂群采蜜工作結束，輸出最終數(shù)據(jù).

2基于反向學習的人工蜂群算法

2.1一般的反向學習機制

Rahnamayan[3]等人提出基于反向學習的差分進化算法，首次給出了反向學習的概念，其中對位數(shù)及對位點的定義如下：

定義1（對位數(shù)）對于給定的一個實數(shù)x∈[a，b]，其對位數(shù)xop定義為

xop=a+b-x.（5）

同樣地，在多維空間中對其進行推廣.

定義2（對位點）設X=（x1，x2，…，xD）為D維空間中的一個點，其中xi∈[ai，bi]，則其對位點Xop=（xop1，xop2，xop1…，xopD），各分量為

xopi=ai+bi-xi.（6）

根據(jù)對位點的定義，對更一般的反向優(yōu)化過程可簡述為：對于解空間中的所有解（即當前種所有個體群），進行對位操作產(chǎn)生同等數(shù)目的對位解（即生成對位種群），在兩組解中選擇出前SN（種群規(guī)模的一半）個優(yōu)秀解組成新的一組候選解（即新的種群），進而提高了下一次尋優(yōu)的初始解質量.一般的反向學習操作為：

xopj=rand（0，1）（minj+maxj）-xj.（7）

其中minj和maxj分別表示第j維搜索空間的下限和上限.

2.2依概率集體反向學習

蜜蜂是一種群居性動物，單個的蜜蜂具有較為簡單的覓食行為，但在整個蜂群中，每個蜜蜂個體都會有社會性學習行為，從而能夠采到更好的蜜源.然而蜜蜂在學習時，并沒有充分利用蜂群整體的信息，僅利用個別個體信息指導蜜源的搜索.針對這個問題，本文提出了OABC算法，全體跟隨蜂以一定的概率進行反向學習;加設動態(tài)擾動參數(shù)控制對位點鄰域的范圍，在保證一般的OBL擴大搜索區(qū)域優(yōu)勢的前提下，利用個體與群體信息，提高對位點的有效性，進而提高算法性能.

跟隨蜂階段反向學習過程對位搜索策略為：

Xopij=rand（0，R）（minj+maxj）-Xij.（8）

R=R1，it≤MaxIt/3

R2，MaxIt/3

R3，it≥2MaxIt/3.（9）

其中，Xij為第i個個體的第j維分量，Xopij為Xij關于種群幾何中心的對位點，minj，maxj為當前種群第j維的下限和上限，rand（0，R）表示[0，R]間的均勻分布隨機數(shù)，it為當前迭代次數(shù)，Max It為最大迭代次數(shù).二維空間中操作過程見圖1.陰影區(qū)域Xop*i即為對位點所處范圍.圖1跟隨蜂階段對位搜索示意圖

OABC算法基本思想在于某一代跟隨蜂階段并未選擇蜜源進行發(fā)掘，而是進行對位鄰域反向學習，在新的反向學習過程中，充分利用蜂群信息（maxj以及minj）和個體信息（Xij）來確定對位點鄰域的范圍，并設置隨機范圍參數(shù)R，使得隨著進化的進程，對位搜索的范圍逐漸縮小，提高了對位點仍處于種群內(nèi)的概率，從而提高收斂速度.在算法初期，R取值較大，對位鄰域的搜索范圍相應較大，盡管對位點優(yōu)于當前點的概率可能沒有得到提高，但增加了找到更具潛力區(qū)域的可能性.隨著迭代的進行，R逐漸變小，這樣就保證算法在對位點附近搜索，使得新的種群在潛力區(qū)產(chǎn)生.當R足夠小后，個體僅向當前個體關于種群幾何中心的對位點學習，并且不斷的優(yōu)化使得對位點在當前個體足夠小的鄰域內(nèi)，亦即可看作是一次蜜源的開發(fā)，從而提高算法的開發(fā)能力.標準ABC在探索方面有著出色的表現(xiàn)，因此OABC算法仍然保留標準ABC算法的引領蜂和偵察蜂階段來保證算法的探索能力.

2.3算法流程

OABC算法沿用標準的ABC算法框架，主要不同點在于跟隨蜂階段以一定的概率執(zhí)行反向學習，本文僅給出跟隨蜂階段偽代碼，標準ABC算法參閱文獻[14].

3仿真實驗結果與分析

3.1測試函數(shù)與參數(shù)設置

驗證OABC算法的性能，比較OABC算法和ABC算法的性能.表1給出了本文所用測試函數(shù)的編號、名稱、搜索空間范圍和最優(yōu)值.U表示單峰函數(shù)，M表示多峰函數(shù)，S表示可分函數(shù)，N表示不可分函數(shù).

確定算法發(fā)揮最佳性能時Jr的選取，首先研究進行反向學習的控制參數(shù)Jr對OABC算法性能的影響.分別用Jr=0.1，0.2，0.3，0.4，0.5，0.6，0.7，0.8，0.9，1.0對前6個基準函數(shù)進行測試.ABC算法可以看作是OABC算法的一種特殊情況，即當Jr=0時，算法的跟隨蜂階段進行反向學習的概率為0，也就是說在所有代搜索中，跟隨蜂完全執(zhí)行標準ABC跟隨蜂的操作，此時整個算法即為標準ABC算法.

所有的測試均進行FES=105次函數(shù)評價，種群規(guī)模為100（SN=50），最大循環(huán)代數(shù)設置為Max It=1 000，蜜源迭代閾值limit=0.6*ndim*SN，其中ndim為維度，鄰域擾動參數(shù)R1=1，R2=10-2，R3=10-7.每個算法獨立運行30次，通過實驗獲取每個測試函數(shù)的平均值（Mean）和標準差（SD）.平均值反映在一定的評價次數(shù)下算法所能到達的平均精度，體現(xiàn)算法的收斂性能;標準差反映算法的穩(wěn)定性.

3.2實驗結果及分析

OABC算法的參數(shù)Jr對新的候選解搜索是否充分利用種群整體信息起著重要的控制作用.當參數(shù)Jr從零增加到一定值時，OABC算法提高了利用種群整體信息的能力，使得開發(fā)能力增強，探索能力相對降低.表2和表3給出了前6個函數(shù)在不同Jr值下的優(yōu)化結果.

將6個函數(shù)的測試結果根據(jù)Jr的變化繪制成圖，通過圖2-圖7可以觀察到：

（1）對于六種函數(shù)優(yōu)化，隨著參數(shù)Jr值的增加，優(yōu)化函數(shù)的最優(yōu)均值首先減小，表示解變好，然后在某一點開始增大，表示解變差.

（2）Sphere函數(shù)、Schwefel2.22函數(shù)、Rosenbrock函數(shù)以及Ackley函數(shù)均在Jr=0.2時取得最小值，Quartic函數(shù)雖然不在0.2處取得最小值，但其優(yōu)化幅度已經(jīng)大幅降低，表明額外的反向學習不再對提升算法的收斂性能有明顯作用.Rastrigin函數(shù)在Jr=0.1時取得最優(yōu)值，在Jr=0.2時的最優(yōu)值也優(yōu)于標準ABC最優(yōu)值.

（3）當Jr=1.0時大部分最優(yōu)值都要高于標準ABC最優(yōu)值，這是因為種群信息利用過度，算法的探索能力下降，整體易陷入初期種群的幾何中心，致使收斂精度下降.因此，此算法進行反向學習的參數(shù)取Jr=0.2.對其余四種函數(shù)進行優(yōu)化，并將十組數(shù)據(jù)整合，見表4.

實驗數(shù)據(jù)表明，在測試得到的十組數(shù)據(jù)中，OABC算法的結果均要優(yōu)于標準ABC算法，表明增設鄰域控制參數(shù)的反向學習方法能夠提升標準ABC算法的性能;種群整體信息對算法的提升起著重要的作用，甚至是對Griewank函數(shù)的優(yōu)化已經(jīng)取得了最優(yōu)值.OABC算法具有尋優(yōu)能力，對單峰函數(shù)Sphere，Schwefel2.22，Quartic，Rosenbrock以及多峰函數(shù)Rastrigin，Ackley，Weierstrass，Michalewicz，Himmelblau均有不同程度的提升，驗證了OABC算法在搜索精度方面的有效性.

進一步研究改進方案對算法收斂速度的影響，將幾種函數(shù)優(yōu)化過程繪制成圖，見圖8-圖13.從圖中能觀察到：

（1）算法在初期的收斂趨勢與標準ABC算法趨勢非常相似，這是因為在算法初期，完全采用一般的反向學習，并沒有提高對位個體更優(yōu)的幾率，主要保證了能夠探索到解的潛在區(qū)域，因此收斂的趨勢是基本相同的.

（2）Sphere函數(shù)、Rastrigin函數(shù)、Griewank函數(shù)以及Ackley函數(shù)在進化到350代左右時，收斂速度迅速提升，這與設定的擾動控制參數(shù)R相關.R的下降使得搜索在潛在區(qū)域更小的范圍內(nèi)進行，從而有效地提高了收斂速度.Quartic函數(shù)和Rosenbrock函數(shù)并沒有出現(xiàn)類似的情況，這可能與函數(shù)的性質有關，但仍可以看到其最優(yōu)值仍在變化，故所提出的改進方式仍具有尋優(yōu)潛力.

4總結

本文提出基于反向學習的人工蜂群算法（簡稱OABC算法）.OABC算法在一般的反向學習基礎上，設置對位鄰域擾動控制參數(shù)，調整反向學習的范圍，并在標準ABC算法跟隨蜂階段依概率執(zhí)行，強化個體對種群信息的利用，從而提高算法的開發(fā)能力，且沒有增加額外的評價次數(shù).OABC算法為保證算法的探索能力，仍然采用標準ABC算法的雇傭蜂和偵察蜂策略.幾種基準函數(shù)的仿真實驗表明，OABC算法能夠平衡算法的開發(fā)和探索能力，更容易找到最優(yōu)解，收斂精度更高，收斂速度更快.

參考文獻

[1]Karaboga D.An idea based on honey bee swarm for numerical optimization，Technical Report-TR06 [R].Kayseri：Erciyes University，2005.

[2]Guopu Zhu，Sam Kwong.Gbest-guided artificial bee colony algorithm for numerical function optimization[J].Applied Mathematics and Computation.2010，217（7）：3166-3173.

[3]羅鈞，李研.具有混沌搜索策略的蜂群優(yōu)化算法[J].控制與決策.2010，25（12）：1913-1916.

[4]畢曉君，王艷嬌.加速收斂的人工蜂群算法[J].系統(tǒng)工程與電子技術，2011，33（12）：2755-2761.

[5]Li Z，Wang W，Yan Y，et al.PS-ABC：A hybrid algorithm based on particle swarm and artificial bee colony for high-dimensional optimization problems[J].Expert Systems with Applications，2015，42（22）：8881-8895.

[6]王志剛，尚旭東，夏慧明，等.多搜索策略協(xié)同進化的人工蜂群算法[J].控制與決策，2018，33（2）：235-241.

[7]Cui L，Zhang K，Li G，et al.Modified Gbest-guided artificial bee colony algorithm with new probability model[J].Soft Computing，2018，22（7）：2217-2243.

[8]S.Rahnamayan，H.R.Tizhoosh，MA.Salama，Opposition-based differential evolution[J].IEEE Transactions on Evolutionary Computation，2008，12（1）： 64-79.

[9]暴勵，曾建潮.一種雙種群差分蜂群算法[J].控制理論與應用，2011，28（2）：266-272.

[10]Weifeng Gao，Sanyang Liu.Improved artificial bee colony algorithm for global optimization[J].Information Processing Letters.2011，111（17）：871-882.

[11]Weifeng Gao，Sanyang Liu.A modified artificial bee colony algorithm[J].Computers & Operations Research，2012，39（3）：687-697.

[12]Weifeng Gao，Sanyang Liu，Lingling Huang.A global best artificial bee colony algorithm for global optimization[J].Journal of Computational and Applied Mathematics，2012，236（11）：2741-2753.

[13]Wei-feng Gao，San-yang Liu，Ling-ling Huang.A novel artificial bee colony algorithm based on modified search equation and orthogonal learning[J].IEEE transactions on cybernetics.2013，43（3）：1011-1024.

[14]Karaboga D，Akay B.A comparative study of artificial bee colony algorithm[J].Applied Mathematics and Computation，2009，2（14）：108-132.

編輯：琳莉