具有學(xué)習(xí)及十字交叉搜索的人工蜂群算法*

黃 珊，高興寶

陜西師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，西安 710119

具有學(xué)習(xí)及十字交叉搜索的人工蜂群算法*

黃 珊+，高興寶

陜西師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，西安 710119

為克服人工蜂群算法搜索策略的局部搜索能力較弱且計算資源分布不均勻等缺點(diǎn)，提出了一種改進(jìn)人工蜂群算法。首先對雇傭蜂和瞭望蜂，分別設(shè)計了新搜索策略，提高了在精英解和全局最好解鄰域內(nèi)的搜索能力；其次對依概率選取的瞭望蜂，采用局部學(xué)習(xí)策略，加快了收斂速度并增強(qiáng)了全局尋優(yōu)能力；最后為平衡全局搜索和局部開發(fā)，利用十字交叉搜索增強(qiáng)瞭望蜂和全局最好解的局部搜索能力，維持了種群多樣性，從而避免了早熟收斂現(xiàn)象。對10個標(biāo)準(zhǔn)測試函數(shù)和30個CEC2014測試函數(shù)集進(jìn)行仿真實(shí)驗(yàn)，并與四種人工蜂群算法和兩種非人工蜂群算法進(jìn)行比較，結(jié)果表明改進(jìn)的人工蜂群算法全局尋優(yōu)能力強(qiáng)且提高了收斂速度和精度。

人工蜂群算法（ABC）；十字交叉搜索；局部學(xué)習(xí)；數(shù)值優(yōu)化；鄰域搜索

1 引言

優(yōu)化技術(shù)在工程設(shè)計、運(yùn)籌學(xué)、生產(chǎn)運(yùn)營、科學(xué)和信息等相關(guān)領(lǐng)域中[1]扮演著至關(guān)重要的角色，是解決復(fù)雜問題的有效方法。然而，現(xiàn)實(shí)世界中的許多問題不連續(xù)或存在許多局部極小，因此使用傳統(tǒng)方法難以求解。而作為重要的隨機(jī)搜索方法，進(jìn)化計算已成功運(yùn)用于解決許多非凸、不連續(xù)、多峰優(yōu)化問題[2]，并且受到了廣泛的關(guān)注。受蜜蜂覓食行為的啟發(fā)，Karaboga于2005年提出了人工蜂群算法（artificial bee colony，ABC）[3]。作為一類重要的群智能優(yōu)化算法，ABC具有控制參數(shù)少、易于實(shí)現(xiàn)、自組織等優(yōu)點(diǎn)。然而與其他群智能優(yōu)化算法類似，如粒子群優(yōu)化算法（particle swarm optimization，PSO）[4]、差分進(jìn)化（differential evolution，DE）[5]、蟻群算法（ant colony optimization，ACO）[6]和免疫算法（immune algorithm，IA）[7]，ABC仍存在收斂速度慢、易于陷入局部極優(yōu)、早熟收斂等問題。其主要原因在于ABC算法的搜索策略具有較強(qiáng)的全局搜索能力而局部開發(fā)能力較弱，且隨機(jī)性使它不能很好地利用最好解的信息，導(dǎo)致無法充分開發(fā)更好的搜索方向。但對優(yōu)化問題，算法性能的優(yōu)劣，主要體現(xiàn)在能否合理地維持全局搜索和局部開發(fā)的平衡。為克服上述缺點(diǎn)，進(jìn)一步提高算法性能，研究者提出了許多改進(jìn)的ABC算法，大致可分為以下兩類：

（1）改進(jìn)每種類型蜂的搜索策略。文獻(xiàn)[8]提出了一種全局指導(dǎo)的人工蜂群算法。該算法設(shè)計了一種新搜索策略，把全局最好解的信息融入到搜索策略中。由于搜索策略后兩部分的指導(dǎo)方向不同，可能會造成震蕩現(xiàn)象，從而導(dǎo)致搜索遠(yuǎn)離真實(shí)最優(yōu)解（式（5））。文獻(xiàn)[9]結(jié)合禁忌表的記憶能力和混沌局部搜索算子來改進(jìn)偵查蜂的搜索過程，然而僅利用混沌策略來改進(jìn)偵查蜂初始化過程并不能有效平衡搜索全局性和局部性。文獻(xiàn)[10]設(shè)計了一種鄰域半徑搜索策略，更準(zhǔn)確地模擬了瞭望蜂的行為，并且分析了閾值Limit和種群大小對優(yōu)化結(jié)果的影響。雖然該算法顯著地提高了解的精度，但對不同問題，設(shè)置恰當(dāng)?shù)泥徲虬霃奖容^困難。文獻(xiàn)[11]提出了一種動態(tài)改變種群規(guī)模的策略。在進(jìn)化過程中，該策略依賴產(chǎn)生的候選解的優(yōu)劣來刪除或增加食物源。然而種群規(guī)模對算法的全局搜索能力和計算成本有重要影響，種群規(guī)模太大，計算成本高，收斂速度慢，種群規(guī)模太小，不能合理地覆蓋搜索范圍，全局搜索能力較弱，因此該策略并不能有效地改善算法性能。為提高算法的局部開發(fā)能力，文獻(xiàn)[12]提出一種多維搜索策略，以指導(dǎo)當(dāng)前個體朝最優(yōu)解方向移動，但該策略注重前期搜索的局部開發(fā)，并不能有效平衡全局搜索和局部開發(fā)。

（2）混合ABC算法。該類算法采取優(yōu)勢互補(bǔ)的思想恰當(dāng)?shù)厝诤狭薃BC和一些其他智能優(yōu)化算法。文獻(xiàn)[13]分析了螢火蟲算法（firefly algorithm，F(xiàn)A）和人工蜂群算法的各自特點(diǎn)，提出了一種集二者優(yōu)勢的混合算法，以解決約束均值方差文件夾的選擇問題，實(shí)驗(yàn)結(jié)果表明混合算法具有較強(qiáng)的選擇能力。受DE啟發(fā)，文獻(xiàn)[14]提出一種改進(jìn)的搜索策略，引入選擇概率P來選擇搜索策略，同時采用混沌方法和對稱學(xué)習(xí)方法初始化種群，以加快全局收斂。但選擇概率P的設(shè)置，并不能充分發(fā)揮改進(jìn)策略的優(yōu)勢，不能有效地平衡算法的全局性和局部性。

上述改進(jìn)算法在一定程度上改善了ABC算法的性能，但仍存在收斂速度慢和早熟收斂等現(xiàn)象。因此本文提出具有學(xué)習(xí)及十字交叉搜索的人工蜂群算法（improved artificial bee colony algorithm with learning and crisscross search，LCSABC）。該算法首先對雇傭蜂和瞭望蜂，分別利用精英解和全局最好解的信息，設(shè)計新穎的搜索策略，加快收斂速度并且提高局部開發(fā)能力。其次，為保持種群多樣性，避免算法早熟收斂，對瞭望蜂采用局部學(xué)習(xí)策略[15]，改善全局搜索能力。最后，利用十字交叉搜索方法對瞭望蜂和全局最好解依次序進(jìn)行水平交叉搜索和垂直交叉搜索，既加快了收斂速度，同時又增加了種群多樣性。通過對10個標(biāo)準(zhǔn)測試函數(shù)[16]和30個CEC2014測試函數(shù)集[17]的仿真實(shí)驗(yàn)，并與基本的ABC算法以及三種ABC算法變體和兩種非ABC算法的比較，說明所提算法能顯著提高算法的收斂速度和全局尋優(yōu)能力。

2 人工蜂群算法

人工蜂群算法模仿蜜蜂覓食的智能行為，是一種基于群體智能方法。在ABC算法[3]中，食物源的位置代表最優(yōu)化問題的可能解，每個食物源的花粉數(shù)代表相應(yīng)解的質(zhì)量，即適應(yīng)度值。為了找到最好的食物源，蜂群被劃分成雇傭蜂、瞭望蜂和偵查蜂三種類型。為方便下文敘述，記I={1,2,…,SN}和J={1,2,…,D}，其中D為搜索空間的維數(shù)，SN表示食物源數(shù)量，雇傭蜂和瞭望蜂的數(shù)量均為SN。

初始化階段在可行解空間內(nèi)，根據(jù)下式隨機(jī)初始化產(chǎn)生食物源的位置并計算當(dāng)前適應(yīng)度值：

其中,fit(i)表示第i個食物源Xi的適應(yīng)度值；f(Xi)表示食物源Xi處優(yōu)化問題的目標(biāo)函數(shù)值。此外，用counter來記錄未成功更新的個體的數(shù)量，且對每個食物源初始counter設(shè)為0。

雇傭蜂階段雇傭蜂和食物源是一一對應(yīng)的關(guān)系，且不同的雇傭蜂將飛向不同的食物源。

首先，在父代食物源的鄰域內(nèi)，按下式搜索產(chǎn)生一個新的食物源：

其中，j∈J，G為迭代數(shù)；為在第G次迭代第i個食物源的第j維；表示第k個食物源的第j維，k∈I且k≠i；?j是[-1,1]上服從均勻分布的隨機(jī)數(shù)。

瞭望蜂階段所有雇傭蜂完成更新任務(wù)后，飛回蜂巢通過舞蹈形式向瞭望蜂傳遞食物源的信息。每個瞭望蜂以輪盤賭的方式按如下概率選擇一個食物源進(jìn)行再次搜索：

其中，fiti表示第i個食物源的適應(yīng)度值。顯然，食物源的適應(yīng)度值越大，則它被瞭望蜂選擇的概率越高。瞭望蜂將在每個食物源的鄰域內(nèi)，按照式（3）產(chǎn)生新食物源，并采用貪婪選擇方法判斷新的食物源是否能夠被保留，同時更新counter。

偵查蜂階段選擇具有較大counter數(shù)的食物源并與預(yù)先設(shè)定的閾值Limit進(jìn)行比較，決定是否拋棄該食物源。即若counter＞Limit，則被選擇的食物源將被其雇傭蜂拋棄，同時該雇傭蜂將轉(zhuǎn)變成偵查蜂，并按照式（1）隨機(jī)產(chǎn)生新食物源。

3 本文算法

以下將詳細(xì)介紹兩種新穎的搜索策略、瞭望蜂局部學(xué)習(xí)策略和十字交叉搜索。

3.1 兩種新穎的搜索策略

在ABC算法中，解的搜索策略起著至關(guān)重要的作用。雖然新食物源產(chǎn)生公式（3）有較強(qiáng)的搜索能力，但其局部開發(fā)能力較弱。為提高算法的局部開發(fā)能力及充分利用當(dāng)前最好解的信息，文獻(xiàn)[8]提出了如下搜索策略：

其中，i=1,2,…,SN，j∈J；?i,j是[-1,1]上的隨機(jī)數(shù)；φi,j是[0,1.5]上服從均勻分布的隨機(jī)數(shù)；k是從I中隨機(jī)選取的數(shù)且k≠i。盡管式（5）利用全局最好解信息來指導(dǎo)搜索方向，但由于搜索策略（5）后兩部分的指導(dǎo)方向不同，可能會造成震蕩現(xiàn)象。文獻(xiàn)[18]設(shè)計了如下搜索策略：

其中，j∈J；r1和r2是從I中隨機(jī)選取的數(shù)且i≠r1≠r2；?i,j與式（5）相同。該搜索策略只在最后一項(xiàng)的指導(dǎo)下搜索而不偏向任何方向，從而有效地避免了震蕩現(xiàn)象。然而該策略并沒有充分開發(fā)種群中較好解的信息。為克服這些缺點(diǎn)，對雇傭蜂和瞭望蜂，分別提出如下兩種搜索策略：

3.2 瞭望蜂局部學(xué)習(xí)策略

在雇傭蜂階段，每個雇傭蜂對應(yīng)一個食物源，幾乎一半的計算資源被平均分配到所有食物源上；而在瞭望蜂階段，根據(jù)與適應(yīng)度值成比例的概率來選擇被搜索的食物源。盡管從理論上講，更高質(zhì)量的食物源將被分配更多的計算資源，然而當(dāng)適應(yīng)度值之間沒有顯著差異時，所有食物源可能會獲得幾乎相同的概率，且被分配相同的計算資源。此外，在ABC算法中食物源按賭輪選擇耗時較大，且式（3）更注重全局搜索，而沒有利用當(dāng)前最好解的信息，收斂速度慢。另一方面，雖然在優(yōu)化單峰函數(shù)時，式（5）能利用當(dāng)前最好解的信息加快收斂速度，但對多峰函數(shù)，由于的引導(dǎo)，使搜索方向容易向局部極優(yōu)移動而導(dǎo)致優(yōu)化過程陷入局部極優(yōu)[16]。

基于以上分析，在瞭望蜂階段，本文首先依據(jù)雇傭蜂分享的信息，即利用式（4）產(chǎn)生的概率信息選擇一個優(yōu)質(zhì)蜜源，并利用式（8）對該食物源的某一維進(jìn)行更新；其次，選擇適應(yīng)度值大的食物源作為更新后的個體；最后，為保持種群多樣性，對更新后的個體利用如下策略進(jìn)行局部學(xué)習(xí)：

其中，i、p和q∈I且p≠q≠i，j∈J；Xi,j表示更新后第i個個體的第j維；Li,j表示Xi的第j維學(xué)習(xí)后產(chǎn)生的候選解；φi,j是[-1,1]上服從均勻分布的隨機(jī)數(shù)；fit(Xi)表示解Xi處的適應(yīng)度值。若學(xué)習(xí)產(chǎn)生的食物源Li的適應(yīng)度值好于對應(yīng)的食物源Xi，則用Li代替Xi進(jìn)入下一次搜索。因此策略（9）能有效地提高當(dāng)前解之間互相學(xué)習(xí)的能力，加快收斂。

3.3 十字交叉搜索

十字交叉搜索[19]（crisscross，CS）作為一種能有效搜索到高質(zhì)量食物源的催化劑，有助于改善算法的收斂速度。該方法分為水平交叉搜索和垂直交叉搜索。水平交叉搜索在獨(dú)立的超立方體中產(chǎn)生候選解的概率較大，而在它們周邊區(qū)域產(chǎn)生候選解的概率較小；垂直交叉搜索通過對個體的某些維實(shí)施算術(shù)重組，在保持種群多樣性的同時，能促使停滯維數(shù)跳出局部極優(yōu)。

（1）水平交叉。對食物源中的所有個體，隨機(jī)兩兩分為SN/2組，然后對每組個體隨機(jī)選擇某一維執(zhí)行一種特殊的算術(shù)交叉。具體過程如下：

設(shè)某組中個體為Xi和Xj，隨機(jī)選擇第d維實(shí)施如下水平交叉，產(chǎn)生候選解：

其中，a1和a2是[0,1]上服從均勻分布的隨機(jī)數(shù)；c1和c2是[-1,1]上服從均勻分布的隨機(jī)數(shù)；分別表示由Xi,d和Xj,d產(chǎn)生的候選解。從式（10）、式（11）可以看出，右端前兩項(xiàng)來自遺傳算法中被廣泛應(yīng)用的算術(shù)交叉，能使候選解隨機(jī)分布在兩個父代的范圍之內(nèi)；而右端最后一項(xiàng)分別引入擴(kuò)展系數(shù)c1和c2來提高全局搜索能力。

（2）垂直交叉。對全局最好解隨機(jī)選取不同兩維執(zhí)行算術(shù)交叉，且無重復(fù)執(zhí)行Lc×D次算術(shù)交叉，其中Lc控制實(shí)施垂直交叉搜索的維數(shù)數(shù)量，建議Lc∈[0.2,0.4]。算術(shù)交叉具體操作如下：

設(shè)d1和d2為在[1,D]中隨機(jī)選取的兩個整數(shù)，對Xbest實(shí)施垂直交叉操作產(chǎn)生候選解：

其中,r是[0,1]上服從均勻分布的隨機(jī)數(shù)；表示由產(chǎn)生的候選解。從式（12）中可以看出，垂直交叉對父代的某一維采用算術(shù)重組。

3.4 算法框架

由3.1～3.3節(jié)，具有學(xué)習(xí)及十字交叉搜索的人工蜂群（LCSABC）算法的具體步驟如下。

算法1 LCSABC算法

步驟1初始化。

設(shè)置種群規(guī)模SN，問題維數(shù)D，精英解數(shù)量m，參數(shù)Lc、counter，閾值Limit。用式（1）隨機(jī)產(chǎn)生SN個個體構(gòu)成初始種群POP，并用式（2）計算適應(yīng)度值。

步驟2雇傭蜂階段。

（2.1）依適應(yīng)度值選取Topm個精英解；

（2.2）利用式（7）搜索新食物源；

（2.3）比較新食物源與其對應(yīng)父代個體的適應(yīng)度值，較優(yōu)個體進(jìn)入下一次搜索；

（2.4）若新食物源被保留，則對應(yīng)的食物源的counter=0,否則counter=counter+1。

步驟3瞭望蜂階段。

（3.1）利用式（4）選取適應(yīng)度值較大的食物源；

（3.2）利用式（8）搜索新食物源；

（3.3）比較新食物源與其對應(yīng)父代個體的適應(yīng)度值，較優(yōu)個體進(jìn)入下一次搜索；

（3.4）若保留新食物源，則對應(yīng)食物源的counter=0，否則counter=counter+1；

（3.5）利用式（9）對食物源進(jìn)行學(xué)習(xí)；

（3.6）比較學(xué)習(xí)產(chǎn)生的新食物源與對應(yīng)父代個體的適應(yīng)度值，較優(yōu)個體進(jìn)入下一次搜索。

步驟4十字交叉搜索。

（4.1）利用式（10）、式（11）對瞭望蜂實(shí)施水平交叉搜索；

（4.2）比較水平交叉產(chǎn)生的新食物源與對應(yīng)父代個體的適應(yīng)度值，較優(yōu)個體進(jìn)入下一次搜索；

（4.3）利用式（12）對全局最好解的不同兩維無重復(fù)地實(shí)施垂直交叉Lc×D次；

（4.4）比較垂直交叉產(chǎn)生的新食物源與全局最好解的適應(yīng)度值，較優(yōu)個體進(jìn)入下一次搜索。

步驟5偵查蜂階段。

若counter＞Limit，則拋棄食物源，并利用式（1）隨機(jī)生成新個體。

步驟6停止準(zhǔn)則。

若FES＞FES_max，則停止計算并輸出結(jié)果；否則轉(zhuǎn)步驟1繼續(xù)搜索。

4 數(shù)值實(shí)驗(yàn)及分析

為評估LCSABC算法的性能，本文選取10個標(biāo)準(zhǔn)函數(shù)[16]f1～f10（見表1）和30個CEC2014測試函數(shù)[17]f11～f40進(jìn)行數(shù)值實(shí)驗(yàn)，并與基本ABC算法[3]、3種改進(jìn)ABC 算法（qABC[10]、dABC[20]、ABCVSS[21]）和兩種非ABC 算法（DE[5]、PSO[4]）進(jìn)行比較。其中f1～f5和f11～f13是連續(xù)單峰函數(shù)，f6～f10和f14～f26是多峰函數(shù)，f27～f32是混合函數(shù)，f33～f40是復(fù)合函數(shù)。所有實(shí)驗(yàn)均在PC機(jī)（i5，6200 u，2.30 GHz，8 GB）上采用Matlab R2015b進(jìn)行。

LCSABC算法的參數(shù)設(shè)置如下：種群規(guī)模SN=50，Limit=SN×D，m=SN×0.2，Lc=0.4，δ=0.05。表 2給出了比較算法的參數(shù)設(shè)置（見文獻(xiàn)[16]）。在實(shí)驗(yàn)中每個測試函數(shù)均獨(dú)立運(yùn)行25次，并用函數(shù)誤差f(Xbest)-f(X?)的平均值（Mean）和標(biāo)準(zhǔn)差（Std）作為評價算法性能的標(biāo)準(zhǔn)，其中Xbest為算法運(yùn)行中獲得的最優(yōu)解，X?為理論最優(yōu)解。為確保算法評價的公平客觀及具有統(tǒng)計意義，采用顯著性水平為0.05的Wilcoxon秩和檢驗(yàn)對算法性能進(jìn)行評價。

Table 1 Benchmark functions表1 標(biāo)準(zhǔn)測試函數(shù)

Table 2 Parameters setting of allABC algorithms表2 所有ABC算法的參數(shù)設(shè)置

首先，對30維標(biāo)準(zhǔn)測試函數(shù)f1～f10進(jìn)行數(shù)值實(shí)驗(yàn)，并與6種算法（ABC、qABC、dABC、ABCVSS、DE、PSO）進(jìn)行比較。在數(shù)值實(shí)驗(yàn)中，所有算法的最大函數(shù)評估次數(shù)FES_max=150 000。表3給出數(shù)值結(jié)果，其中“+”、“-”和“≈”分別表示對比算法優(yōu)于、劣于和相似于本文算法，且最佳數(shù)值結(jié)果用黑色加粗標(biāo)注。

由表3可以看出，LCSABC算法總體上比其他6種算法具有明顯的優(yōu)勢。對單峰函數(shù)f1～f5，LCSABC算法在f2～f5上均獲得最好結(jié)果，ABC算法在f1上獲得最好結(jié)果，而對f4，除PSO算法外，其余6種算法均能得到最優(yōu)值。特別地，對多峰函數(shù)f6～f9，LCSABC算法均取得最好平均值和標(biāo)準(zhǔn)差，尤其對函數(shù)f7，獲得了理論最優(yōu)值。由顯著性水平為0.05的Wilcoxon秩和檢驗(yàn)知，LCSABC算法所得結(jié)果顯著地優(yōu)于ABC、qABC、dABC、ABCVSS、DE和PSO算法的函數(shù)個數(shù)分別為7、9、9、9、9和10，劣于它們的個數(shù)分別為2、0、0、0、0和0，以及相當(dāng)于它們的個數(shù)分別為1、1、1、1、1和0。

此外，與ABC算法相比，盡管LCSABC算法對簡單的單峰函數(shù)f1沒有取得最好結(jié)果，但對其他9個函數(shù)均取得最好結(jié)果，且在多峰函數(shù)f7上獲得了理論最優(yōu)值。因此LCSABC算法能有效平衡全局搜索和局部開發(fā)。

為進(jìn)一步說明LCSABC算法的進(jìn)化性能，圖1給出了8個函數(shù)f2～f9的進(jìn)化曲線。由圖1可以看出，對單峰函數(shù)f2～f5，LCSABC算法在100次迭代后均取得明顯優(yōu)于其他3種算法的最優(yōu)值，其收斂速度明顯優(yōu)于DE、PSO和ABC，而對f4，LCSABC和ABC算法獲得理論最優(yōu)值的迭代次數(shù)幾乎相同；對多峰函數(shù)f6～f9，LCSABC算法在進(jìn)化過程中具有較快的收斂速度，能有效平衡全局搜索和局部開發(fā)。特別地，對函數(shù)f7，LCSABC算法取得了理論最優(yōu)值，且收斂速度優(yōu)于其他3種算法。因此LCSABC算法不僅在解的精度和穩(wěn)定性方面明顯優(yōu)于其他6種算法，而且有效平衡了算法的全局搜索和局部開發(fā)能力。

Table 3 Comparison of 7 algorithms with 30D standard test functions表3 7種算法在30維標(biāo)準(zhǔn)測試函數(shù)上尋優(yōu)性能比較

其次，對30個CEC2014測試函數(shù)f11～f40在10維上進(jìn)行數(shù)值實(shí)驗(yàn)，并與6種算法ABC、qABC、dABC、ABCVSS、DE和PSO進(jìn)行比較。在實(shí)驗(yàn)中，最大函數(shù)評估次數(shù)FES_max=100 000。表4給出數(shù)值結(jié)果，其中“+”、“-”和“≈”與表3相同，最佳的數(shù)值結(jié)果用黑色加粗標(biāo)注。

由表4可以看出，與其他6種算法相比，LCSABC總體上具有明顯的優(yōu)勢，表現(xiàn)出更好的性能。對單峰函數(shù)f11～f13，LCSABC算法在f11上獲得了最好結(jié)果，其尋優(yōu)能力明顯優(yōu)于其他6種算法，DE算法在函數(shù)f12～f13上取得最好結(jié)果；對簡單的多峰函數(shù)f14～f26，LCSABC算法在函數(shù)f16、f18、f20、f21和f24上均取得最優(yōu)的平均值和標(biāo)準(zhǔn)差。除DE和PSO算法外，LCSABC算法和其他4種算法在函數(shù)f18上都能獲得理論最優(yōu)值，qABC算法在函數(shù)f14和f15上獲得最優(yōu)值，ABCVSS算法在函數(shù)f17和f23上獲得最優(yōu)值，而ABC和dABC算法分別在函數(shù)f19和f22上獲得最優(yōu)值；對混合函數(shù)f27～f32，LCSABC算法對函數(shù)f32獲得了明顯優(yōu)于其他6種比較算法的平均值和標(biāo)準(zhǔn)差；對組合函數(shù)f33～f40，LCSABC算法在函數(shù)f36、f38～f40上均獲得到了較好的平均值且穩(wěn)定性好于其他6種算法。特別地，LCSABC算法在f36上和dABC算法獲得了相近的平均值且標(biāo)準(zhǔn)差好于dABC算法，ABC算法在f35上獲得最優(yōu)值，dABC算法在f37上獲得最優(yōu)值。由顯著性水平為0.05的Wilcoxon秩和檢驗(yàn)知，LCSABC算法所得結(jié)果顯著地優(yōu)于ABC、qABC、dABC、ABCVSS、DE和PSO算法的函數(shù)個數(shù)分別為20、18、19、19、22和29，劣于它們的個數(shù)分別為8、8、8、10、7和1，以及相當(dāng)于它們的個數(shù)分別為2、4、3、1、1和0。

Fig.1 Evolutionary curves of 4 algorithms onf2～f9圖1 函數(shù) f2～f9上4種算法的進(jìn)化曲線

此外，盡管標(biāo)準(zhǔn)ABC算法在簡單函數(shù)f19和4個復(fù)雜函數(shù)f30、f33～f35上獲得最優(yōu)值，3種改進(jìn)的ABC算法在8個簡單函數(shù)f13～f15、f17、f22、f23、f25、f26和3個復(fù)雜函數(shù)f28、f29、f37上獲得最優(yōu)值，然而LCSABC算法在7個簡單函數(shù)f11、f12、f16、f18、f20、f21、f24和7個復(fù)雜函數(shù)f27、f31、f32、f36、f38～f40上均能獲得最優(yōu)值。因此，LCSABC算法能有效地避免陷入局部最優(yōu)，有效地平衡了搜索的全局性和局部性。

進(jìn)一步，雖然DE算法在2個單峰函數(shù)f12和f13及4個復(fù)雜混合函數(shù)f27、f28、f30、f31上獲得最優(yōu)解，而PSO算法在混合函數(shù)f27上獲得最優(yōu)解，但LCSABC算法在22個多峰函數(shù)和復(fù)雜混合函數(shù)f14～f26、f29、f32～f39上均獲得最優(yōu)值。因此，在解復(fù)雜優(yōu)化問題時，LCSABC算法能有效地避免陷入局部最優(yōu)，減少早熟收斂現(xiàn)象。

Table 4 Comparison of 7 algorithms with 10D CEC2014 test functions表4 7種算法在10維CEC2014測試函數(shù)上尋優(yōu)性能比較

續(xù)表4

綜上所述，實(shí)驗(yàn)結(jié)果表明LCSABC算法能有效平衡全局搜索和局部開發(fā)能力，不僅在求解精度和穩(wěn)定性方面表現(xiàn)出較好的性能，而且能有效避免算法陷入局部極優(yōu)。

5 結(jié)論

為增強(qiáng)ABC算法的局部搜索能力，加快收斂速度和避免早熟收斂現(xiàn)象，提出了一種具有學(xué)習(xí)及十字交叉搜索的改進(jìn)人工蜂群算法（LCSABC）。首先，對雇傭蜂和瞭望蜂，分別設(shè)計了兩種新穎的搜索策略，通過精英解和全局最好解鄰域的信息來加強(qiáng)全局搜索能力；其次，對瞭望蜂采用局部學(xué)習(xí)策略來加快收斂速度；最后，對瞭望蜂和當(dāng)前最好解依次序采用十字交叉搜索方法來維持種群的多樣性，避免了早熟收斂現(xiàn)象。對10個標(biāo)準(zhǔn)測試函數(shù)和30個CEC2014測試函數(shù)進(jìn)行仿真實(shí)驗(yàn)，并與6種算法進(jìn)行比較，結(jié)果表明LCSABC算法在收斂速度和尋優(yōu)精度方面都有顯著的提高。

[1]Azamathulla H M,Wu Fuchun.Support vector machine approach for longitudinal dispersion coefficients in natural streams[J].Applied Soft Computing,2011,11(2):2902-2905.

[2]Azamathulla H M,Ghani A A,Fei S Y.ANFIS-based approach for predicting sediment transport in clean sewer[J].Applied Soft Computing,2012,12(3):1227-1230.

[3]Karaboga D.An idea based on honey bee swarm for numerical optimization[R].Kayseri:Erciyes University,2005.

[4]Kennedy J,Eberhart R C.Particle swarm optimization[C]//Proceedings of the 1995 International Conference on Neural Networks,Perth,Australia,Nov 27-Dec 1,1995.Piscataway,USA:IEEE,1995:1942-1948.

[5]Storn R,Price K.Differential evolution:a simple and efficient adaptive scheme for global optimization over continuous spaces,TR-95-012[R].Barkeley:Global International Computer Science Institute,1995.

[6]Dorigo M,Birattari M,Stutzle T.Ant colony optimization[J].IEEE Computational Intelligence Magazine,2006,1(4):28-39.

[7]Jiao Licheng,Wang Lei.A novel genetic algorithm based on immunity[J].IEEE Transactions on Systems,Man,and Cybernetics,2000,30(5):552-561.

[8]Zhu Guopu,Kwong S.Gbest-guided artificial bee colony algorithm for numerical function optimization[J].Applied Mathematics and Computation,2010,217(7):3166-3173.

[9]Luo Jun,Li Yan.Artificial bee colony algorithm with chaoticsearch strategy[J].Control and Decision,2010,25(12):1913-1916.

[10]Karaboga D,Gorkemli B.A quick artificial bee colony(qABC)algorithm and its performance on optimization problems[J].Applied Soft Computing,2014,23(5):227-238.

[11]Aydin D,?zy?n S,Ya?ar C,et al.Artificial bee colony algorithm with dynamic population size to combined economic and emission dispatch problem[J].International Journal of Electrical Power&Energy Systems,2014,54(1):144-153.

[12]Cao Chunhong,Xu Guangxing.Geometric constraints based on improved artificial bee colony algorithm[J].Journal of Frontiers of Computer Science and Technology,2015,9(9):1122-1131.

[13]Tuba M,Bacanin N.Artificial bee colony algorithm hybridized with firefly algorithm for cardinality constrained meanvariance portfolio selection problem[J].Applied Mathematics&Information Sciences,2014,8(6):2831-2844.

[14]Gao Weifeng,Liu Sanyang.A modified artificial bee colony algorithm[J].Computers and Operations Research,2012,39(3):687-697.

[15]Ouyang Haibin,Gao Liqun,Li S,et al.Improved global-bestguided particle swarm optimization with learning operation for global optimization problems[J].Applied Soft Computing,2017,52(3):987-1008.

[16]Cui Laizhong,Li Genghui,Lin Qiuzhen,et al.A novel artificial bee colony algorithm with depth-first search framework and elite-guided search equation[J].Information Sciences,2016,367/368:1012-1044.

[17]Liang J J,Qu B Y,Suganthan P N.Problem definitions and evaluation criteria for the CEC 2014 special session and competition on single objective real-parameter numerical optimization,Technical Report 201311[R].Nanyang Technological University and Zhenzhou University,2013.

[18]Gao Weifeng,Liu Sanyang,Huang Lingling.A novel artificial bee colony algorithm based on modified search equation and orthogonal learning[J].IEEE Transactions on Cybernetics,2013,43(3):1011-1024.

[19]Meng Anbo,Chen Yucheng,Yin Hao,et al.Crisscross optimization algorithm and its application[J].Knowledge Based Systems,2014,67(4):218-229.

[20]Kiran M S,Findik O.A directed artificial bee colony algorithm[J].Applied Soft Computing,2015,26(C):454-462.

[21]Kiran M S,Hakli H,Gündüz M.Artificial bee colony algorithm with variable search strategy for continuous optimization[J].Information Sciences,2015,300:140-157.

附中文參考文獻(xiàn)：

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

[12]曹春紅,許光星.基于改進(jìn)人工蜂群算法的幾何約束求解[J].計算機(jī)科學(xué)與探索,2015,9(9):1122-1131.

ImprovedArtificial Bee ColonyAlgorithm with Learning and Crisscross Search*

HUANG Shan+,GAO Xingbao

School of Mathematics and Information Science,Shaanxi Normal University,Xi'an 710119,China

2017-04,Accepted 2017-06.

This paper presents an improved artificial bee colony algorithm to overcome the weaker search ability and imbalance in computing resource allocation.To enhance the neighborhood search of the elites and global best solution,two new strategies are first designed for the employed bees and onlooker bees,respectively.Then a local learning strategy is used to the onlooker bees chosen probably to speed up the convergence speed and enhance the global optimization ability.Finally,to balance the exploration and exploitation effectively,the crisscross search method is employed to enhance the performance of the onlooker bees and global best solution such that the diversity of the population is preserved and the premature convergence phenomenon is reduced.The proposed algorithm is compared with six excellent meta-heuristic algorithms on 10 classical benchmark functions and 30 CEC2014 benchmark functions with different dimensions.The experimental results show that the proposed algorithm is very competitive.

artificial bee colony(ABC);crisscross search;local learning;numerical optimization;neighborhood search

+Corresponding author:E-mail:huangshan151567@snnu.edu.cn

10.3778/j.issn.1673-9418.1704059

*The National Natural Science Foundation of China under Grant No.61273311(國家自然科學(xué)基金);the Fundamental Research Funds for the Central Universities of China under Grant No.GK201603002(中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金).

CNKI網(wǎng)絡(luò)優(yōu)先出版:2017-06-08，http://kns.cnki.net/kcms/detail/11.5602.TP.20170608.1424.004.html

HUANG Shan，GAO Xingbao.Improved artificial bee colony algorithm with learning and crisscross search.Journal of Frontiers of Computer Science and Technology,2017,11(12)：2004-2014.

A

TP18

HUANG Shan was born in 1992.She is an M.S.candidate at Shaanxi Normal University.Her research interest is intelligent optimization methods.

黃珊（1992—），女，甘肅酒泉人，陜西師范大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)橹悄軆?yōu)化方法。

GAO Xingbao was born in 1966.He is a professor and Ph.D.supervisor at Shaanxi Normal University.His research interests include intelligent optimization methods,optimization theories and algorithms.

高興寶（1966—），陜西隴縣人，博士，陜西師范大學(xué)教授、博士生導(dǎo)師，主要研究領(lǐng)域?yàn)橹悄軆?yōu)化方法，最優(yōu)化理論與算法。