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

黃 珊，高興寶

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

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

黃 珊+，高興寶

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

為克服人工蜂群算法搜索策略的局部搜索能力較弱且計(jì)算資源分布不均勻等缺點(diǎn)，提出了一種改進(jìn)人工蜂群算法。首先對(duì)雇傭蜂和瞭望蜂，分別設(shè)計(jì)了新搜索策略，提高了在精英解和全局最好解鄰域內(nèi)的搜索能力；其次對(duì)依概率選取的瞭望蜂，采用局部學(xué)習(xí)策略，加快了收斂速度并增強(qiáng)了全局尋優(yōu)能力；最后為平衡全局搜索和局部開(kāi)發(fā)，利用十字交叉搜索增強(qiáng)瞭望蜂和全局最好解的局部搜索能力，維持了種群多樣性，從而避免了早熟收斂現(xiàn)象。對(duì)10個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)和30個(gè)CEC2014測(cè)試函數(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è)計(jì)、運(yùn)籌學(xué)、生產(chǎn)運(yùn)營(yíng)、科學(xué)和信息等相關(guān)領(lǐng)域中[1]扮演著至關(guān)重要的角色，是解決復(fù)雜問(wèn)題的有效方法。然而，現(xiàn)實(shí)世界中的許多問(wèn)題不連續(xù)或存在許多局部極小，因此使用傳統(tǒng)方法難以求解。而作為重要的隨機(jī)搜索方法，進(jìn)化計(jì)算已成功運(yùn)用于解決許多非凸、不連續(xù)、多峰優(yōu)化問(wèn)題[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)、早熟收斂等問(wèn)題。其主要原因在于ABC算法的搜索策略具有較強(qiáng)的全局搜索能力而局部開(kāi)發(fā)能力較弱，且隨機(jī)性使它不能很好地利用最好解的信息，導(dǎo)致無(wú)法充分開(kāi)發(fā)更好的搜索方向。但對(duì)優(yōu)化問(wèn)題，算法性能的優(yōu)劣，主要體現(xiàn)在能否合理地維持全局搜索和局部開(kāi)發(fā)的平衡。為克服上述缺點(diǎn)，進(jìn)一步提高算法性能，研究者提出了許多改進(jìn)的ABC算法，大致可分為以下兩類：

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

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

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

2 人工蜂群算法

人工蜂群算法模仿蜜蜂覓食的智能行為，是一種基于群體智能方法。在ABC算法[3]中，食物源的位置代表最優(yōu)化問(wèn)題的可能解，每個(gè)食物源的花粉數(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)生食物源的位置并計(jì)算當(dāng)前適應(yīng)度值：

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

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

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

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

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

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

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

3 本文算法

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

3.1 兩種新穎的搜索策略

在ABC算法中，解的搜索策略起著至關(guān)重要的作用。雖然新食物源產(chǎn)生公式（3）有較強(qiáng)的搜索能力，但其局部開(kāi)發(fā)能力較弱。為提高算法的局部開(kāi)發(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）利用全局最好解信息來(lái)指導(dǎo)搜索方向，但由于搜索策略（5）后兩部分的指導(dǎo)方向不同，可能會(huì)造成震蕩現(xiàn)象。文獻(xiàn)[18]設(shè)計(jì)了如下搜索策略：

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

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

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

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

其中，i、p和q∈I且p≠q≠i，j∈J；Xi,j表示更新后第i個(gè)個(gè)體的第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)度值好于對(duì)應(yīng)的食物源Xi，則用Li代替Xi進(jìn)入下一次搜索。因此策略（9）能有效地提高當(dāng)前解之間互相學(xué)習(xí)的能力，加快收斂。

3.3 十字交叉搜索

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

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

設(shè)某組中個(gè)體為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)來(lái)自遺傳算法中被廣泛應(yīng)用的算術(shù)交叉，能使候選解隨機(jī)分布在兩個(gè)父代的范圍之內(nèi)；而右端最后一項(xiàng)分別引入擴(kuò)展系數(shù)c1和c2來(lái)提高全局搜索能力。

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

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

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

3.4 算法框架

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

算法1 LCSABC算法

步驟1初始化。

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

步驟2雇傭蜂階段。

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

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

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

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

步驟3瞭望蜂階段。

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

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

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

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

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

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

步驟4十字交叉搜索。

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

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

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

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

步驟5偵查蜂階段。

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

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

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

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

為評(píng)估LCSABC算法的性能，本文選取10個(gè)標(biāo)準(zhǔn)函數(shù)[16]f1～f10（見(jiàn)表1）和30個(gè)CEC2014測(cè)試函數(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è)置（見(jiàn)文獻(xiàn)[16]）。在實(shí)驗(yàn)中每個(gè)測(cè)試函數(shù)均獨(dú)立運(yùn)行25次，并用函數(shù)誤差f(Xbest)-f(X?)的平均值（Mean）和標(biāo)準(zhǔn)差（Std）作為評(píng)價(jià)算法性能的標(biāo)準(zhǔn)，其中Xbest為算法運(yùn)行中獲得的最優(yōu)解，X?為理論最優(yōu)解。為確保算法評(píng)價(jià)的公平客觀及具有統(tǒng)計(jì)意義，采用顯著性水平為0.05的Wilcoxon秩和檢驗(yàn)對(duì)算法性能進(jìn)行評(píng)價(jià)。

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

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

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

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

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

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

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

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

由表4可以看出，與其他6種算法相比，LCSABC總體上具有明顯的優(yōu)勢(shì)，表現(xiàn)出更好的性能。對(duì)單峰函數(shù)f11～f13，LCSABC算法在f11上獲得了最好結(jié)果，其尋優(yōu)能力明顯優(yōu)于其他6種算法，DE算法在函數(shù)f12～f13上取得最好結(jié)果；對(duì)簡(jiǎn)單的多峰函數(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)值；對(duì)混合函數(shù)f27～f32，LCSABC算法對(duì)函數(shù)f32獲得了明顯優(yōu)于其他6種比較算法的平均值和標(biāo)準(zhǔn)差；對(duì)組合函數(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ù)個(gè)數(shù)分別為20、18、19、19、22和29，劣于它們的個(gè)數(shù)分別為8、8、8、10、7和1，以及相當(dāng)于它們的個(gè)數(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算法在簡(jiǎn)單函數(shù)f19和4個(gè)復(fù)雜函數(shù)f30、f33～f35上獲得最優(yōu)值，3種改進(jìn)的ABC算法在8個(gè)簡(jiǎn)單函數(shù)f13～f15、f17、f22、f23、f25、f26和3個(gè)復(fù)雜函數(shù)f28、f29、f37上獲得最優(yōu)值，然而LCSABC算法在7個(gè)簡(jiǎn)單函數(shù)f11、f12、f16、f18、f20、f21、f24和7個(gè)復(fù)雜函數(shù)f27、f31、f32、f36、f38～f40上均能獲得最優(yōu)值。因此，LCSABC算法能有效地避免陷入局部最優(yōu)，有效地平衡了搜索的全局性和局部性。

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

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

續(xù)表4

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

5 結(jié)論

為增強(qiáng)ABC算法的局部搜索能力，加快收斂速度和避免早熟收斂現(xiàn)象，提出了一種具有學(xué)習(xí)及十字交叉搜索的改進(jìn)人工蜂群算法（LCSABC）。首先，對(duì)雇傭蜂和瞭望蜂，分別設(shè)計(jì)了兩種新穎的搜索策略，通過(guò)精英解和全局最好解鄰域的信息來(lái)加強(qiáng)全局搜索能力；其次，對(duì)瞭望蜂采用局部學(xué)習(xí)策略來(lái)加快收斂速度；最后，對(duì)瞭望蜂和當(dāng)前最好解依次序采用十字交叉搜索方法來(lái)維持種群的多樣性，避免了早熟收斂現(xiàn)象。對(duì)10個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)和30個(gè)CEC2014測(cè)試函數(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ì)算機(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(國(guó)家自然科學(xué)基金);the Fundamental Research Funds for the Central Universities of China under Grant No.GK201603002(中央高?；究蒲袠I(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)化理論與算法。