一種鄰域搜索的人工蜂群算法

周新宇，吳志健，鄧長壽，彭虎

?

一種鄰域搜索的人工蜂群算法

周新宇1, 2，吳志健1，鄧長壽3，彭虎1

(1. 武漢大學 計算機學院，軟件工程國家重點實驗室，湖北 武漢，430072；2. 江西師范大學 計算機信息工程學院，江西 南昌，330022；3. 九江學院 信息科學與技術學院，江西 九江，332005)

提出采用鄰域搜索機制來改進人工蜂群算法的解搜索方程，從當前食物源的環形鄰域拓撲結構中選擇較優的鄰居食物源進行開采，平衡算法的勘探與開采能力。此外，為保存偵察蜂的搜索經驗，提出采用一般反向學習策略生成被放棄食物源的反向解，提高算法的搜索效率。在20個典型的benchmark函數上驗證算法的性能，并與6種知名的改進算法進行對比。實驗結果表明：本文算法在收斂速度和解的精度上均有較大優勢。

全局優化；人工蜂群；鄰域搜索；一般反向學習

人工蜂群(artificial bee colony, ABC)算法是近年來提出的一種較為新穎的全局優化算法[1?2]，具有結構簡單、控制參數少、易于實現等特點。該算法與粒子群優化(particle swarm optimization, PSO)算法[3]類似，都是通過模擬自然界生物的群體智能行為而設計的群智能優化算法。但與PSO算法不同的是，ABC模擬的是蜂群的智能采蜜行為，它根據不同種類蜜蜂的分工協作，實現整個蜂群采蜜量的最大化，即找到待優化問題的最優解[4]。Karaboga等[5]研究結果表明，ABC的性能要優于或者相當于差分演化(differential evolution，DE)算法、PSO算法和遺傳算法。目前，ABC算法已成功地用于解決多種不同類型的實際優化問題，如參數優化[6]、符號回歸[7]、神經網絡[8?9]以及車輛路徑問題[10]等。在標準ABC算法中，雇傭蜂(employed bee)和觀察蜂(onlooker bee)共用一種解搜索方程(solution search equation)生成新的候選食物源，因而算法的性能主要依賴于該方程。然而，最近的研究[11?13]指出，這種解搜索方程側重于算法的勘探(exploration)能力，而開采(exploitation)能力不足，易導致算法的收斂速度過慢和解的精度不高。針對此問題，受PSO算法的啟發，Zhu等[11]提出了一種引導的ABC算法，在解搜索方程中融入全局最優解的信息，用于提高算法的開采能力。類似地，Banharnsakun等[12]也在全局最優解的基礎上，提出了改進的解搜索方程。Gao等[13]受DE算法的“DE/best/1”變異策略的啟發，提出了一種“ABC/best/1”的改進解搜索方程，在該方法中同樣也利用了全局最優解。這幾種改進的ABC算法均利用了全局最優解信息來提高算法的開采能力。雖然使用全局最優解可增強開采能力，但在一定程度上也易導致算法陷入局部最優，特別是在優化多峰函數時。因此，為提高ABC算法的開采能力且不易于陷入局部最優，受局部版本的粒子群優化(local particle swarm optimization, LPSO)算法[14?15]的啟發，本文提出一種鄰域搜索的ABC(neighborhood search based artificial bee colony, NSABC)算法。LPSO是標準PSO算法[16]的一個改進版本，它采用粒子所在鄰域的最優粒子代替標準PSO的全局最優粒子來指導粒子的速度更新。受此啟發，在觀察蜂階段，采用鄰域搜索機制從當前食物源的環形鄰域拓撲結構中選擇1個最優的食物源，在該食物源的鄰域范圍內搜索新的候選食物源，有助于增強算法的開采能力且不易于陷入局部最優。此外，為幫助偵察蜂(scout bee)保存搜索經驗，提出采用一般反向學習策略來生成被放棄食物源的反向解，使得偵察蜂可以快速地找到新的優秀食物源。為驗證本文算法的性能，在20個典型的benchmark函數(包括單峰、多峰以及偏移加旋轉類型)上開展數值實驗，并與6種不同類型的改進算法進行對比。

1 人工蜂群算法

在ABC算法中，人工蜂群包含了3種不同類型的蜜蜂：雇傭蜂、觀察蜂和偵察蜂。雇傭蜂負責勘探食物源，并在蜂巢的舞蹈區通過搖擺舞的形式將食物源的相關信息分享給觀察蜂[17]，這些信息包括食物源的位置以及蜂蜜量。然后，觀察蜂根據收到的信息以一定概率選擇某一食物源繼續開采，該食物源的蜂蜜量越多，被選中的概率就越高。若一個食物源被開采完，則相對應的雇傭蜂就轉變為偵察蜂，再重新隨機搜索一個新的食物源。值得說明的是：1個食物源的位置對應于待優化問題的1個候選解，食物源的蜂蜜量即指適應值；而雇傭蜂與食物源是一一對應的，同時雇傭蜂的數量和觀察蜂相同。

類似于其他演化算法，ABC算法同樣采用1個隨機初始化的群體開始迭代搜索。設群體規模為，其中食物源X=(x,1, x,2, …, x,D)代表1個候選解，∈{1, 2, …,}，為待優化問題的維度。初始化之后，ABC算法根據蜜蜂的類型，將優化過程分為3個階段。

1) 雇傭蜂階段。在該階段，每一只雇傭蜂在對應的食物源X處，采用解搜索方程生成1個新的食物源V=(v,1，v,2，…，v,D)。若V的蜂蜜量更多即適應值更優，則就替換X。該方程如下：

2) 觀察蜂階段。在所有雇傭蜂完成了勘探后，觀察蜂根據接收到的信息隨機選擇一個食物源進一步開采。這種選擇方式通常采用基于適應值的方法，如：輪盤賭機制。若觀察蜂采用輪盤賭機制進行選擇，則食物源X被選中的概率p為

其中：f為食物源X的適應值。從式(2)可以看出，食物源的適應值越大，被觀察蜂選中的概率越高。

3) 偵察蜂階段。當雇傭蜂對應的食物源的適應值連續次未更新，說明該食物源已被開采耗盡。這種情況下，雇傭蜂轉變成偵察蜂，采用式(2)重新隨機搜索1個新的食物源。

其中：rand(0,1)為[0, 1]間的隨機數；[a,b]為第維變量的上下界。值得說明的是，除群體規模等公共參數外，是ABC算法中唯一的參數。

2 基于鄰域搜索的ABC算法

2.1 鄰域搜索機制

PSO算法模擬的是鳥群和魚群的覓食行為[16]。在標準PSO算法中，粒子的速度更新受自身歷史經驗和群體歷史經驗的共同影響，如式(4)所示：

但Kennedy等[14?15]指出：標準PSO算法中的在求解多峰函數時易出現早熟現象，為此提出了一種局部版本的PSO算法，即LPSO算法。在LPSO算法中，粒子的速度更新受自身歷史經驗和鄰域的最優粒子的共同影響，即

受LPSO算法的啟發，本文提出在觀察蜂階段采用鄰域搜索機制來選擇食物源進行開采，而不是直接利用全局最優解的信息。因而，在求解多峰函數時，能夠利用鄰域內較優的個體信息，而非全局最優解信息，有利于增加群體的多樣性，避免算法陷入局部最優。此外，雇傭蜂階段則保持原來的解搜索方程不變，這樣有助于結合雇傭蜂的勘探能力和觀察蜂的開采能力，充好利用和保持這兩種能力的平衡，提高ABC的搜索性能。因此，對觀察蜂而言，新食物源的搜索方式如下：

其中：()為當前食物源X所處鄰域的最優食物源，設鄰域半徑為，則()∈{?，…，?1，，1，…，}。1∈{1，2，…，}，2∈{?，…，?1，，1，…，}，且滿足1，2和互不相等.

值得說明的是，鄰域搜索的方式與群體的拓撲結構類型是相關的，依據Das等[18]的建議，本文采用效率較高的環形鄰域拓撲結構。這種結構的特點是群體中個體是否相鄰是由下標的關系確定，而不是搜索空間中的歐式距離。圖1給出了式(6)采用的環形鄰域拓撲結構示意圖，其中為鄰域半徑。

圖1 環形鄰域拓撲結構

為更加直觀地說明提出的鄰域搜索機制與原解搜索方程的區別，以2維Shekel’s Foxholes函數為例，采用標準ABC算法和結合了鄰域搜索機制的ABC(簡記為ABC-NS)分別優化該函數，給出2種算法在不同演化代數下的群體分布情況。2維的Shekel’s Foxholes函數是多峰函數，有24個局部極值和1個全局極值(?32,?32)=0.998 004，搜索空間的邊界是[65.536, 65.536]2。該函數的具體定義可參考文獻[19]，圖2所示為該函數的3-D圖。對標準ABC算法和ABC-NS算法，采用相同的參數設置，=30，=100。而在ABC-NS算法中，按文獻[18]的建議，取鄰域半徑為群體規模的10%。

圖2 2維Shekel’s Foxholes函數的3-D圖

圖3所示為標準ABC和ABC-NS算法在演化過程中的第1代、第15代和第30代的群體分布情況，實心圓點表示食物源，空心矩形是Shekel’s Foxholes函數在平面上的投影，即25個極值點。從圖3可以看出，在第1代中由于隨機初始化的作用，2種算法的群體分布無明顯區別，均隨機分散在搜索區域中。但隨著演化代數的增加，2種算法的有效搜索區域都不斷收縮，食物源也向各個極值點靠攏。但值得注意的是，ABC-NS算法的收縮速度要明顯比ABC算法的快。特別地，在第30代時，ABC-NS算法的所有食物源都已收斂到全局極值點處，而ABC算法只有部分食物源到了該點。結果表明：采用鄰域搜索機制可以有效地利用鄰域中優良個體的信息，增強算法的開采能力，且不易于陷入局部最優。

(a) ABC算法在第1代；(b) ABC算法在第15代；(c) ABC算法在第30代；(d) ABC-NS算法在第1代；(e) ABC-NS算法在第15代；(f) ABC-NS算法在第30代

2.2 一般反向學習策略

在標準ABC算法的偵察蜂階段，一個食物源若超過次未更新，則認為該食物源被開采耗盡，對應的雇傭蜂轉變為偵察蜂，并采用式(3)再重新隨機搜索一個新的食物源。這種機制存在不足，即被放棄的食物源可能包含了有益的搜索信息，直接采用隨機生成的新食物源來替換，則易導致這部分信息丟失。為此，本文提出采用一般反向學習策略生成被放棄食物源的反向解，充分利用這些食物源所含的有益信息，為偵察蜂提供更多的搜索經驗，有助于進一步提高算法的搜索效率。

一般反向學習(generalized opposition-based learning, GOBL)策略是反向學習[20?21]的改進版本。它的主要思想是：對當前待優化問題的1個可行解，同時計算并評估其反向解，從中選擇較優的作為候選解。該方法能提高找到全局最優解的概率，文獻[22]驗證了GOBL策略的有效性。

設X=(x,1，x,2，…，x,D)是當前待優化問題的一個可行解，其對應的反向解可定義為

其中：x,j∈[a,b]，∈(0,1)為一般化系數，[da, db]為第維搜索空間的動態邊界，可按如下公式計算得到：

若反向解跳出邊界[a,b]成為非可行解，對其采用隨機生成的方法來重置：

其中：rand(?)是區間[a,b]上的一個隨機數。

除了生成被放棄食物源的反向解，依舊使用原機制即式(3)生成1個隨機食物源，從反向解與隨機食物源中選擇較優的1個作為新的食物源。該過程可以表示為

2.3 NSABC的偽代碼描述

本文提出的NSABC算法在標準ABC的基礎上做了2處改進，1) 在觀察蜂階段，采用鄰域搜索機制來增強解搜索方程的開采能力；2) 在偵察蜂階段，采用一般反向學習策略來生成被放棄食物源的反向解用于保存搜索經驗。Algorithm 1中給出NSABC的偽代碼，其中表示適應度函數的評估次數，Max為適應度函數的最大評估次數，trial記錄了食物源X的適應值未更新的次數。

算法1 Pseudocode of NSABC

Randomly generatefood sources {X|=1，2，…，};

=;

while≤ Maxdo

/* Employed bee phase */

for1todo

Generate a new candidate solutionVaccording to Eq. (1);

if(V) <(X) then

ReplaceXwithV;

trial= 0;

else

trial=trial+1;

end

=+1;

end

/* Onlooker bee phase */

Calculate the probabilitypaccording to Eq. (2);

for1todo

Choose a food sourceXfrom the current populationby the roulette wheel selection mechanism;

Generate a new candidate solutionVaccording to Eq. (6);

if(V) <(X) then

ReplaceXwithV;

trial= 0;

else

trial=trial+1;

end

=+1;

end

/* Scout bee phase */

for1todo

iftrial>then

trial= 0;

Generate the opposite solution ofX,, by Eq. (7);

Generate a new random food sourceVaccording to Eq. (3);

Pick out the better one fromandVforXaccording to Eq. (10);

=+2;

end

end

end

3 數值實驗及分析

3.1 Benchmark函數

為驗證NSABC算法的性能，采用20個典型的benchmark函數進行實驗，如表1所示。F01-F04是單峰函數，F05在維度大于3時為多峰函數[23]。F06是非連續的函數，F07是帶噪聲的函數。F08-F13是多峰函數，而F14-F20是帶偏移和旋轉的復雜多峰函數。函數F01~F13的具體定義見參考文獻[18]，F14~F20的具體定義見參考文獻[24]。

表1 實驗中使用的benchmark函數

3.2 策略有效性分析

為驗證NSABC采用的2種策略的有效性，分別設計了2種算法ABC-NS和ABC-GOBL進行對比分析。ABC-NS算法是在標準ABC的基礎上，僅在觀察蜂階段采用鄰域搜索機制，其他部分保持不變；而ABC-GOBL算法是在標準ABC算法的基礎上，僅在偵察蜂階段采用一般反向學習策略，其他部分保持不變。因此，實驗中共包含(標準ABC，ABC-NS，ABC-GOBL和NSABC) 4種算法的比較，4種算法采用相同的參數設置，=30，=100。而對ABC-NS和NSABC算法，則按文獻[18]的建議，設置鄰域半徑=10%?。函數的維度為=30，適應度函數的最大評估次數Max按文獻[24]的建議設置為：對函數F01~F13，Max=5 000；對函數F14~F20，Max= 10 000。實驗中，每種算法在每個函數上獨立運行30次，記錄結果的均值與方差。表2給出了4種算法的結果，其中均值由()?(X)得到，*為全局極值點。

表2　D=30時標準ABC，ABC-NS，ABC-GOBL和NSABC算法的結果

從表2可以看出：與ABC算法相比，ABC-NS算法在大部分函數上的結果更好，僅在函數F03和F20上略差，這說明鄰域搜索機制有助于增強ABC算法的性能。ABC算法僅在函數F01和F03上比ABC-GOBL算法略優，而在其他函數上ABC-GOBL算法更好，這說明采用GOBL策略是有效的。結合2種策略，NSABC算法取得了4種算法中的最好結果，在所有測試函數上的性能均比ABC算法更優或者相當。值得說明的是，NSABC算法在函數F03，F04和F10上的性能比單獨使用1種策略更優，這說明2種策略的結合能夠取得更好的效果。

為了在統計意義上比較4種算法的性能，采用了非參數的Friedman檢驗[25?26]統計4種算法的平均排名情況。表3給出了4種算法的平均排名情況。從表3可看出：NSABC算法的性能最優，而其他3種算法性能從優到劣依次為：ABC-NS，ABC-GOBL和ABC算法。

表3 標準ABC，ABC-NS，ABC-GOBL和NSABC算法的平均排名

3.3 與其他改進ABC算法的比較

將NSABC算法與其他3種知名的改進ABC算法GABC[11]，MABC[13]和GOABC算法[27]進行對比研究。GABC算法是引導的ABC算法，它受PSO算法的啟發，將全局最優解的信息融入到解搜索方程中，用于提高ABC算法的開采能力。MABC算法提出了類似于DE算法中的“DE/best/1”變異策略的解搜索方程，在全局最優解的鄰域內搜索新的食物源，實驗結果表明：該算法能夠有效地增強ABC的搜索性能。GOABC算法是基于一般反向學習策略的ABC算法，它在算法的迭代過程中生成整個群體的反向解，從當前群體和反向群體中選擇較優的個體進入下一代，這種機制與其他基于反向學習策略的算法是相同的，如反向學習的DE算法(ODE)[21]。然而，不同于GOABC的是，本文提出的NSABC只是在偵察蜂階段對被放棄的食物源生成反向解。

4種算法的公共參數設置為=30，=100；對函數F01~F13，Max=5 000；而對函數F14~F20，Max=10 000。對每個算法的特殊參數按原文獻進行設置，對GABC算法，=1.5；對MABC算法，=0.7；對GOABC算法，=0.3。實驗中對所有函數進行2種維度的實驗，分別取=30和=50。此外，為了在統計意義上比較2個算法的性能是否存在顯著性差異，按文獻[25?26]采用非參數Wilcoxon假設檢驗進行統計，顯著性水平=0.05。表4和表5分別給出了=30和=50時4種算法的結果，其中，符號“+”、“?”和“≈”分別表示NSABC的性能要優于、劣于和相當于對比算法。

表4　D=30時 GABC,MABC,GOABC和NSABC算法的結果

表5　D=50時 GABC、MABC、GOABC和NSABC算法的結果

從表4可看出：NSABC在大部分函數上要優于其他3種對比算法。具體來說，NSABC算法在所有函數上要優于或者相當于GABC算法。與MABC算法相比，NSABC算法在4個函數上的性能不如MABC算法，例如在函數F01上。函數F01是簡單的球狀單峰函數，通常一個開采能力更強的算法會取得更優的結果。MABC算法是在全局最優解的鄰域內搜索新的食物源，因而其開采能力非常強，所以，在該函數上取得了不錯的效果。但在多峰函數上，NSABC算法的性能更好。值得注意的是：在函數F09上，雖然MABC算法的均值比NSABC算法要差得多，但Wilcoxon檢驗的結果卻是兩者無顯著性差異的。出現這種情況的可能原因是：MABC算法在F09上的30次運行結果并不是每次都能得到最優值0，而是產生了噪聲，即偶爾出現較差的結果，這也反映了NSABC算法的魯棒性更好。與GOABC算法相比，NSABC算法在15個函數上更優。

從表5可以看出：與=30時類似，NSABC算法依然在大部分函數上要優于其他3種算法。雖然隨著維度增加，求解的難度也相應增加，但NSABC算法的性能表現良好。表6給出了這4種算法在=30和=50時的平均排名。從表6可得：NSABC算法在2種測試維度下均取得了最好的排名。此外，圖4給出了=30時這4種算法在部分函數上的收斂曲線。從圖4可看出：NSABC算法的收斂速度較快。值得注意的是，MABC算法也具有較快的收斂速度。

(a) F01；(b) F04；(c) F08；(d) F12；(e) F15；(f) F17

表6 GABC，MABC，GOABC和NSABC算法的平均排名

3.4 與其他相關演化算法的比較

為進一步評估NSABC的性能，將其與另外3種知名的相關演化算法(LPSO[14]，GOPSO[22]和DEGL/SAW算法[18])進行對比。LPSO算法是局部版本的PSO算法，采用了鄰域搜索機制。GOPSO算法是采用一般反向學習策略的PSO算法，它以一定概率生成群體中所有粒子的反向解，從當前解和反向解中選擇較優的個體進入下一代。DEGL/SAW算法結合了鄰域搜索策略的DE算法，該算法同樣采用了環形鄰域拓撲結構。這3種算法的參數全部采用原文獻的推薦設置，如表7所示。

表7 LPSO, GOPSO和DEGL/SAW算法的參數設置

注：為群體規模；為慣性系數；1和2為學習因素；為反向學習概率；為縮放因子；為交叉概率。

所有函數的維度設為=30，適應度函數最大評估次數與3.3節中的相同。表8所示為這4種算法的最終結果。從表8可看出：NSABC算法的總體性能要顯著優于對比算法。具體地，與LPSO算法和GOPSO算法相比，NSABC算法在17個函數上取得了更好的結果。與DEGL/SAW算法相比，NSABC算法在12個函數上更優。值得注意的是，在函數F05上，DEGL/SAW算法的結果要明顯優于其他3種算法。文獻[23]指出F05在三維以上屬于多峰函數，其全局極值位于一個狹長的、拋物線狀的扁平山谷中，對大多算法而言很難進入到這個山谷中。但在函數F11上，NSABC算法的結果比其他3種算法明顯更優。表9所示為采用非參數Friedman檢驗得到的平均排名。從表9可以看出：NSABC算法的整體性能最好。圖5所示為這4種算法在部分函數上的收斂曲線。

表8 D=30時 LPSO，GOPSO，DEGL/SAW和NSABC算法的結果

(a) F01；(b) F02；(c) F07；(d) F10；(e) F13；(f) F15

表9 LPSO，GOPSO，DEGL/SAW和NSABC算法的平均排名

3.5 運行時間比較

通常，演化算法的運行時間包含算法的操作算子的運行時間和評估適應度函數的時間。將標準ABC和NSABC算法在本文采用的20個benchmark函數上分別獨立運行30次，記錄消耗的平均CPU時間。2種算法的公共參數采用相同的設置，=30，= 100。適應度函數的最大評估次數Max與前面相同，測試函數的維度設為30和50。算法的運行平臺如下：操作系統為Windows 7 (x64)，CPU為Intel Core 2 Quad CPU Q8200 (2.33 GHz)，內存為4G，編程語言及運行環境為Java和Eclipse SDK 4.2.0。標準ABC和NSABC算法的平均CPU時間如表10所示。從表10可以看出：在=30時，NSABC與標準ABC的CPU時間之比的范圍為[0.85, 1.24]，總的時間比是1.05。值得注意的是，在4個函數上的CPU時間之比要低于1，說明NSABC的運行時間比標準ABC算法的要低。出現這種現象的可能原因是在NSABC算法中，對所有連續次未更新的食物源均采用了一般反向學習機制來尋找新的替代食物源，使得偵察蜂階段消耗了更多的適應度函數評估次數，減少了雇傭蜂和跟隨蜂階段的執行次數，從而降低了整個算法的運行時間。當維度從30增至50時，函數的復雜度也隨之增加，從而導致算法的運行時間也相應增加。但對NSABC算法而言，其與標準ABC的CPU時間之比從30維時的1.05降至50維時的1.00，這正說明了適應度函數的復雜度越高，算法的操作算子占整個運行時間的比例越小。總之，與標準ABC算法相比，NSABC算法的運行時間未明顯地增加。

表10 標準ABC和NSABC算法的平均CPU時間

4 結論

1) 為提高ABC算法的開采能力，受局部版本的PSO算法的啟發，提出采用鄰域搜索機制來改進解搜索方程。此外，為保存搜索經驗，提出采用一般反向學習策略來生成被放棄食物源的反向解。

2) 在20個典型的benchmark函數上驗證提出算法的性能，并將實驗結果與6種知名的改進算法進行對比，結果表明這2種策略能夠有效地提高ABC算法的性能，在收斂速度和解的精度上均有較大的優勢。

3) 下一步研究工作的重點是將本文算法應用于求解實際優化問題，如分布式軟件系統的部件部署 問題。

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

[2] Karaboga D, Basturk B. A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm[J]. Journal of Global Optimization, 2007, 39(3): 459?471.

[3] 余伶俐, 蔡自興. 改進混合離散粒子群的多種優化策略算法[J]. 中南大學學報(自然科學版), 2009, 40(4): 1047?1053.
YU Lingli, CAI Zixing. Multiple optimization strategies for improving hybrid discrete particle swarm [J]. Journal of Central South University (Science and Technology), 2009, 40(4): 1047?1053.

[4] 高衛峰, 劉三陽, 黃玲玲. 受啟發的人工蜂群算法在全局優化問題中的應用[J]. 電子學報, 2012, 40(12): 2396?2403.
GAO Weifeng, LIU Sanyang, HUANG Lingling. Inspired artificial bee colony algorithm for global optimization problems[J]. Acta Electronic Sinica, 2012, 40(12): 2396?2403.

[5] Karaboga D, Akay B. A comparative study of artificial bee colony algorithm[J]. Applied Mathematics and Computation, 2009, 214(1): 108?132.

[6] 賈宗圣, 司錫才, 王桐. 基于人工蜂群技術的海雜波參數優化方法[J]. 中南大學學報(自然科學版), 2012, 43(9): 3485?3489.
JIA Zongsheng, SI Xicai, WANG Tong. Optimum method for sea clutter parameter based on artificial bee colony[J]. Journal of Central South University (Science and Technology), 2012, 43(9): 3485?3489.

[7] Karaboga D, Ozturk C, Karaboga N, et al. Artificial bee colony programming for symbolic regression[J]. Information Sciences, 2012, 209(11): 1?15.

[8] Yeh W C, Hsieh T J. Artificial bee colony algorithm-neural networks for s-system models of biochemical networks approximation[J]. Neural Computing and Applications, 2012, 21(2): 365?375.

[9] Garro B A, Sossa H, Vazquez A R. Artificial neural network synthesis by means of artificial bee colony (ABC) algorithm[C]//Proceedings of the IEEE Congress on Evolutionary Computation. New Orleans: IEEE, 2011: 331?338.

[10] Szeto W, Wu Y, Ho S C. An artificial bee colony algorithm for the capacitated vehicle routing problem[J]. European Journal of Operational Research, 2011, 215 (1): 126?135.

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

[12] Banharnsakun A, Achalakul T, Sirinaovakul B. The best-so-far selection in Artificial Bee Colony algorithm[J]. Applied Soft Computing, 2011, 11(2): 2888?2901.

[13] Gao W F, Liu S Y. A modified artificial bee colony algorithm[J]. Computers & Operations Research, 2012, 39(3): 687?697.

[14] Kennedy J, Mendes R. Population structure and particle swarm performance[C]//Proceedings of the IEEE Congress on Evolutionary Computation. Honolulu: IEEE, 2002: 1671?1676.

[15] Kennedy J, Mendes R. Neighborhood topologies in fully informed and best-of-neighborhood particle swarms[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 2006, 36(4): 515?519.

[16] Shi Y, Eberhart R. A modified particle swarm optimizer[C]//Proceedings of the IEEE Congress on Evolutionary Computation. Anchorage A.K.: IEEE, 1998: 69?73.

[17] Karaboga D, Gorkemli B, Ozturk C, et al. A comprehensive survey: artificial bee colony (ABC) algorithm and applications[J]. Artificial Intelligence Review, 2012, 39(3): 1?37.

[18] Das S, Abraham A, Chakraborty U K, et al. Differential evolution using a neighborhood-based mutation operator[J]. IEEE Transactions on Evolutionary Computation, 2009, 13(3): 526?553.

[19] Yao X, Liu Y, Lin G. Evolutionary programming made faster[J]. IEEE Transactions on Evolutionary Computation, 1999, 3(2): 82?102.

[20] Rahnamayan S, Tizhoosh H R, Salama M M A. Opposition-based differential evolution[J]. IEEE Transactions on Evolutionary Computation, 2008, 12(1): 64?79.

[21] 周新宇, 吳志健, 王暉, 等. 一種精英反向學習的粒子群優化算法[J]. 電子學報, 2013, 41(8): 1647?1652.
ZHOU Xinyu, WU Zhijian, WANG Hui, et al. Elite opposition-based particle swarm optimization[J]. Acta Electronic Sinica, 2013, 41(8): 1647?1652.

[22] Wang H, Wu Z J, Rahnamayan S, et al. Enhancing particle swarm optimization using generalized opposition-based learning[J]. Information Sciences, 2011, 181(20): 4699?4714.

[23] Shang Y W, Y. H. Qiu. A note on the extended Rosenbrock function[J]. Evolutionary Computation, 2006, 14(1): 119?126.

[24] Suganthan P N, Hansen N, Liang J J, et al. Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization[R]. Singapore: Nanyang Technological University, 2005.

[25] Garcia S, Molina D, Lozano M, et al. A study on the use of non-parametric tests for analyzing the evolutionary algorithms' behavior: a case study on the CEC'2005 Special Session on Real Parameter Optimization[J]. Journal of Heuristics, 2009, 15(6): 617?644.

[26] Garcia S, Molina D, Lozano M, et al. Advanced nonparametric tests for multiple comparisons in the design of experiments in computational intelligence and data mining: Experimental analysis of power[J]. Information Sciences, 2010, 180(10): 2044?2064.

[27] El-Abd M. Generalized opposition-based artificial bee colony algorithm[C]//Proceedings of the IEEE Congress on Evolutionary Computation. Brisbane: IEEE, 2012: 1?4.

Neighborhood search-based artificial bee colony algorithm

ZHOU Xinyu1, 2, WU Zhijian1, DENG Changshou3, PENG Hu1

(1. State Key Laboratory of Software Engineering, Computer School, Wuhan University, Wuhan 430072, China;2. College of Computer and Information Engineering, Jiangxi Normal University, Nanchang 330022, China;3. School of Information Science & Technology, Jiujiang University, Jiujiang 332005, China)

The neighborhood search mechanism was introduced to improve the solution search equation of artificial bee colony algorithm. In the ring neighborhood topology of current food source, the exploitation was focused on the best neighbor food source to balance the capabilities of exploration and exploitation. Moreover, in order to preserve search experience for scout bees, the generalized opposition-based learning strategy was utilized to generate opposite solutions of the discarded food sources, which helps enhance the search efficiency. Twenty classic benchmark functions were used to test the performance of our approach, and then the experimental results were compared with other six well-known algorithms. The results show that our approach has better convergence speed and solution accuracy.

global optimization; artificial bee colony; neighborhood search; generalized opposition-based learning

TP301.6

A

1672?7207(2015)02?0534?13

2014?03?25；

2014?06?26

國家自然科學基金資助項目(61364025, 61305150, 61462045)；中央高校基本科研業務費專項資金資助項目(2012211020205)；軟件工程國家重點實驗室開放基金資助項目(SKLSE2014-10-04)(Projects (61364025, 61305150, 61462045) supported by the National Natural Science Foundation of China; Project (2012211020205) supported by the Fundamental Research Funds for the Central Universities; Project (SKLSE2014-10-04) supported by the Foundation of State Key Laboratory of Software Engineering)

周新宇，博士，講師，從事智能計算、并行計算研究；E-mail：xyzhou@whu.edu.cn

10.11817/j.issn.1672-7207.2015.02.023

(編輯 趙俊)