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

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

?

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

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

(1. 武漢大學(xué) 計(jì)算機(jī)學(xué)院，軟件工程國家重點(diǎn)實(shí)驗(yàn)室，湖北 武漢，430072；2. 江西師范大學(xué) 計(jì)算機(jī)信息工程學(xué)院，江西 南昌，330022；3. 九江學(xué)院 信息科學(xué)與技術(shù)學(xué)院，江西 九江，332005)

提出采用鄰域搜索機(jī)制來改進(jìn)人工蜂群算法的解搜索方程，從當(dāng)前食物源的環(huán)形鄰域拓?fù)浣Y(jié)構(gòu)中選擇較優(yōu)的鄰居食物源進(jìn)行開采，平衡算法的勘探與開采能力。此外，為保存?zhèn)刹旆涞乃阉鹘?jīng)驗(yàn)，提出采用一般反向?qū)W習(xí)策略生成被放棄食物源的反向解，提高算法的搜索效率。在20個(gè)典型的benchmark函數(shù)上驗(yàn)證算法的性能，并與6種知名的改進(jìn)算法進(jìn)行對比。實(shí)驗(yàn)結(jié)果表明：本文算法在收斂速度和解的精度上均有較大優(yōu)勢。

全局優(yōu)化；人工蜂群；鄰域搜索；一般反向?qū)W習(xí)

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

1 人工蜂群算法

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

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

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

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

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

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

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

2 基于鄰域搜索的ABC算法

2.1 鄰域搜索機(jī)制

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

但Kennedy等[14?15]指出：標(biāo)準(zhǔn)PSO算法中的在求解多峰函數(shù)時(shí)易出現(xiàn)早熟現(xiàn)象，為此提出了一種局部版本的PSO算法，即LPSO算法。在LPSO算法中，粒子的速度更新受自身歷史經(jīng)驗(yàn)和鄰域的最優(yōu)粒子的共同影響，即

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

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

值得說明的是，鄰域搜索的方式與群體的拓?fù)浣Y(jié)構(gòu)類型是相關(guān)的，依據(jù)Das等[18]的建議，本文采用效率較高的環(huán)形鄰域拓?fù)浣Y(jié)構(gòu)。這種結(jié)構(gòu)的特點(diǎn)是群體中個(gè)體是否相鄰是由下標(biāo)的關(guān)系確定，而不是搜索空間中的歐式距離。圖1給出了式(6)采用的環(huán)形鄰域拓?fù)浣Y(jié)構(gòu)示意圖，其中為鄰域半徑。

圖1 環(huán)形鄰域拓?fù)浣Y(jié)構(gòu)

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

圖2 2維Shekel’s Foxholes函數(shù)的3-D圖

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

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

2.2 一般反向?qū)W習(xí)策略

在標(biāo)準(zhǔn)ABC算法的偵察蜂階段，一個(gè)食物源若超過次未更新，則認(rèn)為該食物源被開采耗盡，對應(yīng)的雇傭蜂轉(zhuǎn)變?yōu)閭刹旆?，并采用?3)再重新隨機(jī)搜索一個(gè)新的食物源。這種機(jī)制存在不足，即被放棄的食物源可能包含了有益的搜索信息，直接采用隨機(jī)生成的新食物源來替換，則易導(dǎo)致這部分信息丟失。為此，本文提出采用一般反向?qū)W習(xí)策略生成被放棄食物源的反向解，充分利用這些食物源所含的有益信息，為偵察蜂提供更多的搜索經(jīng)驗(yàn)，有助于進(jìn)一步提高算法的搜索效率。

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

設(shè)X=(x,1，x,2，…，x,D)是當(dāng)前待優(yōu)化問題的一個(gè)可行解，其對應(yīng)的反向解可定義為

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

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

其中：rand(?)是區(qū)間[a,b]上的一個(gè)隨機(jī)數(shù)。

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

2.3 NSABC的偽代碼描述

本文提出的NSABC算法在標(biāo)準(zhǔn)ABC的基礎(chǔ)上做了2處改進(jìn)，1) 在觀察蜂階段，采用鄰域搜索機(jī)制來增強(qiáng)解搜索方程的開采能力；2) 在偵察蜂階段，采用一般反向?qū)W習(xí)策略來生成被放棄食物源的反向解用于保存搜索經(jīng)驗(yàn)。Algorithm 1中給出NSABC的偽代碼，其中表示適應(yīng)度函數(shù)的評估次數(shù)，Max為適應(yīng)度函數(shù)的最大評估次數(shù)，trial記錄了食物源X的適應(yīng)值未更新的次數(shù)。

算法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 數(shù)值實(shí)驗(yàn)及分析

3.1 Benchmark函數(shù)

為驗(yàn)證NSABC算法的性能，采用20個(gè)典型的benchmark函數(shù)進(jìn)行實(shí)驗(yàn)，如表1所示。F01-F04是單峰函數(shù)，F(xiàn)05在維度大于3時(shí)為多峰函數(shù)[23]。F06是非連續(xù)的函數(shù)，F(xiàn)07是帶噪聲的函數(shù)。F08-F13是多峰函數(shù)，而F14-F20是帶偏移和旋轉(zhuǎn)的復(fù)雜多峰函數(shù)。函數(shù)F01~F13的具體定義見參考文獻(xiàn)[18]，F(xiàn)14~F20的具體定義見參考文獻(xiàn)[24]。

表1 實(shí)驗(yàn)中使用的benchmark函數(shù)

3.2 策略有效性分析

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

表2　D=30時(shí)標(biāo)準(zhǔn)ABC，ABC-NS，ABC-GOBL和NSABC算法的結(jié)果

從表2可以看出：與ABC算法相比，ABC-NS算法在大部分函數(shù)上的結(jié)果更好，僅在函數(shù)F03和F20上略差，這說明鄰域搜索機(jī)制有助于增強(qiáng)ABC算法的性能。ABC算法僅在函數(shù)F01和F03上比ABC-GOBL算法略優(yōu)，而在其他函數(shù)上ABC-GOBL算法更好，這說明采用GOBL策略是有效的。結(jié)合2種策略，NSABC算法取得了4種算法中的最好結(jié)果，在所有測試函數(shù)上的性能均比ABC算法更優(yōu)或者相當(dāng)。值得說明的是，NSABC算法在函數(shù)F03，F(xiàn)04和F10上的性能比單獨(dú)使用1種策略更優(yōu)，這說明2種策略的結(jié)合能夠取得更好的效果。

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

表3 標(biāo)準(zhǔn)ABC，ABC-NS，ABC-GOBL和NSABC算法的平均排名

3.3 與其他改進(jìn)ABC算法的比較

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

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

表4　D=30時(shí) GABC,MABC,GOABC和NSABC算法的結(jié)果

表5　D=50時(shí) GABC、MABC、GOABC和NSABC算法的結(jié)果

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

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

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

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

3.4 與其他相關(guān)演化算法的比較

為進(jìn)一步評估NSABC的性能，將其與另外3種知名的相關(guān)演化算法(LPSO[14]，GOPSO[22]和DEGL/SAW算法[18])進(jìn)行對比。LPSO算法是局部版本的PSO算法，采用了鄰域搜索機(jī)制。GOPSO算法是采用一般反向?qū)W習(xí)策略的PSO算法，它以一定概率生成群體中所有粒子的反向解，從當(dāng)前解和反向解中選擇較優(yōu)的個(gè)體進(jìn)入下一代。DEGL/SAW算法結(jié)合了鄰域搜索策略的DE算法，該算法同樣采用了環(huán)形鄰域拓?fù)浣Y(jié)構(gòu)。這3種算法的參數(shù)全部采用原文獻(xiàn)的推薦設(shè)置，如表7所示。

表7 LPSO, GOPSO和DEGL/SAW算法的參數(shù)設(shè)置

注：為群體規(guī)模；為慣性系數(shù)；1和2為學(xué)習(xí)因素；為反向?qū)W習(xí)概率；為縮放因子；為交叉概率。

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

表8 D=30時(shí) LPSO，GOPSO，DEGL/SAW和NSABC算法的結(jié)果

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

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

3.5 運(yùn)行時(shí)間比較

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

表10 標(biāo)準(zhǔn)ABC和NSABC算法的平均CPU時(shí)間

4 結(jié)論

1) 為提高ABC算法的開采能力，受局部版本的PSO算法的啟發(fā)，提出采用鄰域搜索機(jī)制來改進(jìn)解搜索方程。此外，為保存搜索經(jīng)驗(yàn)，提出采用一般反向?qū)W習(xí)策略來生成被放棄食物源的反向解。

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

3) 下一步研究工作的重點(diǎn)是將本文算法應(yīng)用于求解實(shí)際優(yōu)化問題，如分布式軟件系統(tǒng)的部件部署 問題。

[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ìn)混合離散粒子群的多種優(yōu)化策略算法[J]. 中南大學(xué)學(xué)報(bào)(自然科學(xué)版), 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] 高衛(wèi)峰, 劉三陽, 黃玲玲. 受啟發(fā)的人工蜂群算法在全局優(yōu)化問題中的應(yīng)用[J]. 電子學(xué)報(bào), 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] 賈宗圣, 司錫才, 王桐. 基于人工蜂群技術(shù)的海雜波參數(shù)優(yōu)化方法[J]. 中南大學(xué)學(xué)報(bào)(自然科學(xué)版), 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] 周新宇, 吳志健, 王暉, 等. 一種精英反向?qū)W習(xí)的粒子群優(yōu)化算法[J]. 電子學(xué)報(bào), 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

國家自然科學(xué)基金資助項(xiàng)目(61364025, 61305150, 61462045)；中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(2012211020205)；軟件工程國家重點(diǎn)實(shí)驗(yàn)室開放基金資助項(xiàng)目(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)

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

10.11817/j.issn.1672-7207.2015.02.023

(編輯 趙俊)