基于多維貪婪搜索的人工蜂群算法

張素琪,滕建輔,顧軍華

(1.天津大學(xué)電子信息工程學(xué)院,天津300072;2.河北工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院,天津300401)

基于多維貪婪搜索的人工蜂群算法

張素琪1,滕建輔1,顧軍華2

(1.天津大學(xué)電子信息工程學(xué)院,天津300072;2.河北工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院,天津300401)

人工蜂群算法在多峰高維函數(shù)優(yōu)化問(wèn)題的求解上取得了較好的結(jié)果,但隨著函數(shù)的復(fù)雜度及維數(shù)增高,仍存在收斂速度慢、易陷入局部最優(yōu)等問(wèn)題。為此,提出一種新的人工蜂群算法。將人工蜂群對(duì)食物源的單維貪婪搜索改進(jìn)為多維貪婪搜索以增強(qiáng)蜂群的搜索能力,避免在個(gè)別維度上出現(xiàn)較優(yōu)解的食物源由于達(dá)到更新閾值卻被廢棄而造成迂回搜索的現(xiàn)象,引入擾動(dòng)搜索機(jī)制避免迭代后期食物源位置在個(gè)別維度收斂導(dǎo)致算法陷入局部最優(yōu)。仿真實(shí)驗(yàn)結(jié)果表明,該算法能保持深度挖掘和廣度搜索上的平衡,在高維函數(shù)優(yōu)化問(wèn)題求解的收斂速度和計(jì)算精度方面表現(xiàn)出較好的性能。

人工蜂群算法;函數(shù)優(yōu)化;貪婪搜索;擾動(dòng)搜索;深度挖掘;廣度搜索

1 概述

文獻(xiàn)［1］提出了人工蜂群(Artificial Bee Colony, ABC)算法。該算法是一種模仿蜂群覓食行為的優(yōu)化方法,其控制參數(shù)少,簡(jiǎn)單易操作,在高維函數(shù)優(yōu)化問(wèn)題求解方面與遺傳算法、粒子群算法、和聲算法以及差分進(jìn)化算法相比表現(xiàn)出良好的特性［2-4］,已成為國(guó)內(nèi)外學(xué)者們關(guān)注的熱點(diǎn)。文獻(xiàn)［5］提出了CABC方法,通過(guò)構(gòu)造混沌序列實(shí)現(xiàn)食物源的初始化,以改善各個(gè)食物源分布的均勻性和搜索的廣泛性,在避免算法陷入局部最優(yōu)方面取得了一定效果。文獻(xiàn)［6-7］引入了混沌的概念,在算法迭代一定次數(shù)后,在縮小的新區(qū)域上通過(guò)混沌搜索初始化一部分新的食物源,以提高搜索的多樣性。文獻(xiàn)［8］應(yīng)用反向?qū)W習(xí)理論來(lái)初始化食物源,同樣使食物源的多樣性得到增強(qiáng)。一些學(xué)者通過(guò)將標(biāo)準(zhǔn)ABC中觀察蜂的輪盤(pán)賭選擇改為boltzmann選擇和輪盤(pán)賭反向選擇來(lái)保持食物源的多樣性,避免算法過(guò)早收斂［9-10］。文獻(xiàn)［11-13］將個(gè)體最優(yōu)和全局最優(yōu)加入工蜂和觀察蜂的搜索策略中以加快算法的收斂。文獻(xiàn)［14-15］借鑒差分進(jìn)化算法的變異策略來(lái)改進(jìn)蜂群的搜索策略。本文提出一種多維貪婪搜索,使工蜂和觀察蜂均具備多維搜索的能力,以提升算法的搜索能力和收斂速度。

2 函數(shù)優(yōu)化問(wèn)題的求解

在ABC算法中,蜂群以獲得更好的食物源為目的,不斷更新食物源的位置信息。人工蜂群包含3種蜜蜂:工蜂,觀察蜂和偵查蜂,3種蜜蜂互相配合,共同更新食物源的位置。ABC算法在解決函數(shù)優(yōu)化問(wèn)題時(shí),每個(gè)食物源的位置都代表優(yōu)化問(wèn)題的一個(gè)可行解,可行解在蜂群進(jìn)行一次工作后得到更新,不斷迭代后,可行解集中出現(xiàn)最優(yōu)解,問(wèn)題得以解決。下面說(shuō)明ABC算法解決函數(shù)優(yōu)化問(wèn)題的幾個(gè)重要步驟。

Step 1 初始化n個(gè)食物源的位置:

Step 2 每個(gè)工蜂在所屬食物源xi附近進(jìn)行搜索,選擇候選食物源x′i,如果f(x′i)＜f(xi),那么當(dāng)前的食物源由候選食物源x′i替換,即xi←x′i,同時(shí)limit(i)置為0,否則食物源保持不變且limit(i)增加1,稱(chēng)為貪婪搜索或貪婪修正,修正公式如下:

顯見(jiàn),候選食物源的每次選擇本質(zhì)上是在求解空間中隨機(jī)選擇一個(gè)維度進(jìn)行修正,稱(chēng)為單維貪婪搜索。

Step 3 每一個(gè)工蜂完成對(duì)應(yīng)食物源的修正后,觀察蜂根據(jù)所有工蜂所代表食物源的質(zhì)量,按照式(3)計(jì)算概率進(jìn)行輪盤(pán)賭選擇,確定觀察蜂要選擇的食物源,可表示為s=roulette(n)。

觀察蜂在選定食物源xs的附近按照式(2)進(jìn)行搜索并修正食物源位置,同時(shí)更新limit(s)。

Step 4 判斷每個(gè)食物源的更新記錄,如果limit(i)≥N_limit,該食物源廢棄,偵查蜂將按照式(1)隨機(jī)生成新的食物源。這樣,ABC算法的一次迭代完成。

容易發(fā)現(xiàn)ABC算法中工蜂和觀察蜂搜索新食物源的策略相同但是對(duì)食物源的選擇方式不同。每個(gè)工蜂在所屬食物源xi附近都會(huì)進(jìn)行新的食物源搜索,如果找到更優(yōu)的食物源,修正食物源的同時(shí)其對(duì)應(yīng)limit(i)將會(huì)置為0,若沒(méi)有得到更新,食物源limit(i)將會(huì)增加1。而觀察蜂則根據(jù)輪盤(pán)賭選擇食物源,并在該食物源附近進(jìn)行新的食物源搜索。這樣,質(zhì)量較差的食物源得到更新的機(jī)會(huì)較少,而質(zhì)量較優(yōu)的食物源可能會(huì)被多次選擇,有更多的更新機(jī)會(huì)。

通過(guò)觀察ABC算法對(duì)多維函數(shù)的求解,發(fā)現(xiàn)當(dāng)函數(shù)維度不斷增加時(shí),ABC的單維貪婪搜索顯得越發(fā)不夠,求解過(guò)程中在個(gè)別維度上出現(xiàn)較優(yōu)解而沒(méi)有得到繼續(xù)挖掘的解由于達(dá)到N_limit次的限制而被廢棄,之后由偵查蜂重新隨機(jī)搜索,導(dǎo)致ABC錯(cuò)過(guò)很多達(dá)到全局最優(yōu)的機(jī)會(huì)而需要在其他食物源上重新開(kāi)始,增加了收斂時(shí)間,同時(shí)也影響了最終求解的精度。鑒于此,本文提出了基于多維貪婪搜索的ABC算法。

3 多維貪婪搜索ABC算法

3.1 多維貪婪搜索

每一種群體智能優(yōu)化算法都必須具備廣度探索和深度挖掘的能力,廣度探索指在整個(gè)搜索空間中探索未知域以發(fā)現(xiàn)全局最優(yōu),而深度挖掘是在前一個(gè)較好解的基礎(chǔ)上繼續(xù)挖掘更優(yōu)解的過(guò)程。只有廣度探索和深度挖掘互相配合,達(dá)到平衡,才能使得優(yōu)化算法在不斷求解中得到全局最優(yōu)。文獻(xiàn)［10-15］在標(biāo)準(zhǔn)ABC算法的基礎(chǔ)上均對(duì)搜索策略做了一些改進(jìn),但這些改進(jìn)在增大搜索能力的同時(shí),也破壞了標(biāo)準(zhǔn)ABC算法在廣度探索和深度挖掘上的平衡,而需要改變種群初始化方法、觀察蜂的選擇方法或偵查蜂的搜索方法來(lái)增加種群的多樣化,使算法重新達(dá)到平衡,勢(shì)必增加時(shí)間消耗。本文提出的新算法在增大搜索力度的同時(shí),并沒(méi)有破壞廣度和深度上的平衡,稱(chēng)為基于多維貪婪搜索的人工蜂群算法(multidimensional ABC,mdABC)。mdABC針對(duì)工蜂和觀察蜂在搜索新食物源的過(guò)程中,進(jìn)行每一維度的修正嘗試后都進(jìn)行貪婪選擇,如果當(dāng)前維度的嘗試成功就保留該維度的修正,而在此基礎(chǔ)上進(jìn)行下一維度的嘗試,如果失敗就將該維度上的值退回原值后進(jìn)行下一維度的探索,因此稱(chēng)為多維貪婪搜索。設(shè)當(dāng)前工蜂或觀察蜂所在的食物源為xi=(xi1, xi2,…,xij,…,xim),在食物源 xi附近搜索新食物源x′i=(x′i1,x′i2,…,x′ij,…,x′im)的具體步驟如下:

首先初始化更新標(biāo)志位為sign=0,針對(duì)食物源的每一維xij(j=1,2,…,m)做如下操作:

(1)隨機(jī)選擇當(dāng)前食物源附近的第k個(gè)食物源來(lái)計(jì)算x′ij:

(2)如果x′ij超出該維度上的限定［aj,bj］,則進(jìn)行調(diào)整:

(3)判斷x′ij是否能使得相應(yīng)的f(x′)得到改善,如果得到改善則保留x′ij并更新標(biāo)志位,否則返回原值xij:

按照上述步驟,對(duì)每一維度操作結(jié)束后,進(jìn)行標(biāo)志位判斷,如果標(biāo)志位為1,說(shuō)明在m維的探索中,有至少一維探索成功并進(jìn)行了修正,如果標(biāo)志位為0,說(shuō)明探索失敗,未做修正。

3.2 擾動(dòng)搜索

通過(guò)實(shí)驗(yàn)分析,發(fā)現(xiàn)在食物源經(jīng)過(guò)工蜂、觀察蜂和偵查蜂的多次迭代修正后,最后食物源的位置在個(gè)別維度上逐漸趨于一致,設(shè)在維度 j上有 xijxkj=0,則按照式(2)將導(dǎo)致食物源在該維度上無(wú)法得到修正,因此,按照式(4)增加一個(gè)擾動(dòng)機(jī)制,以避免該維度上的搜索停滯,避免陷入局部最優(yōu)。

其中,w是一個(gè)擾動(dòng)參數(shù),通常取0.01,也可以根據(jù)不同的函數(shù)和臨域范圍進(jìn)行設(shè)置。

3.3 mdABC的基本流程

下面給出mdABC的偽代碼,其中3行～14行和15行～27行詳細(xì)描述了工蜂和觀察蜂的多維貪婪搜索過(guò)程。擾動(dòng)搜索機(jī)制應(yīng)用在第 8行和第21行。常量Max_iter為算法的迭代次數(shù);n為食物源的個(gè)數(shù),工蜂、觀察蜂和偵查蜂數(shù)量分別為n,n,1; m為目標(biāo)函數(shù)的維數(shù);N_limit為食物源更新閾值;變量sign為更新標(biāo)志位;limit記錄每個(gè)食物源未得到更新的次數(shù),max_limit為其中最大值。

4 數(shù)值仿真實(shí)驗(yàn)和結(jié)果分析

為了驗(yàn)證mdABC的有效性,在Matlab2010a平臺(tái)上進(jìn)行仿真,實(shí)驗(yàn)設(shè)備為內(nèi)存 8 GB、處理器3.4 GHz以及64位Win7系統(tǒng)。采用了常用的4個(gè)標(biāo)準(zhǔn)函數(shù)［1-4］:Sphere函數(shù),Rosenbrock函數(shù),Ratrigin函數(shù)和Griewank函數(shù),如表1所示。其中,Sphere和Rosenbrock為單峰函數(shù);Ratrigin和Griewank為多峰函數(shù);Rosenbrock是一個(gè)復(fù)雜的單峰函數(shù),其全局最小值位于一個(gè)平滑的、彎曲路徑上的谷底,一般情況下很難獲得最優(yōu)解;Griewank是一個(gè)復(fù)雜的多峰函數(shù),其局部極小值點(diǎn)會(huì)隨著維度的增大而增多,當(dāng)維度大于等于30之后,多極值點(diǎn)消失成為單峰函數(shù),相對(duì)于低維變得簡(jiǎn)單。測(cè)試主要針對(duì)mdABC、ABC算法進(jìn)行求解精度和收斂速度的比較。參數(shù)設(shè)置與文獻(xiàn)［4］相同:食物源個(gè)數(shù)為 20,迭代次數(shù)均為2 500,控制參數(shù)N_limit對(duì)所有函數(shù)均設(shè)置為100。

對(duì)每個(gè)測(cè)試函數(shù)分別取維度為5,10,30,50,100,算法獨(dú)立運(yùn)行10次,記錄10次的均值、平均差和求取到最優(yōu)值的平均迭代次數(shù),實(shí)驗(yàn)結(jié)果如表2所示,其中,M表示平均值;S表示平均差;I表示平均迭代次數(shù)。

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

表2 mdABC與ABC算法的性能比較

圖1中的曲線分別描述上述參數(shù)設(shè)置下函數(shù)1～4(維度為30)的迭代過(guò)程。

由圖1和表2可看出,對(duì)于單峰函數(shù)Sphere和多峰函數(shù)Ratrigin,Griewank,mdABC的收斂速度和求解精度較標(biāo)準(zhǔn)ABC算法有明顯的改善;特別是對(duì)于單峰Sphere和多峰Ratrigin函數(shù),在不同維度設(shè)置下,均分別在迭代到1 200次和80次時(shí)已求得最優(yōu)值0(Matlab2010a中將小于1e-324的數(shù)處理為0),而且多次運(yùn)行的均值和標(biāo)準(zhǔn)差均為0。對(duì)于復(fù)雜的 Rosenbrock函數(shù),在低維情況下mdABC的優(yōu)勢(shì)相對(duì)較弱,但隨著維數(shù)的升高,優(yōu)勢(shì)變得逐漸明顯。

對(duì)于Griewank函數(shù),在維度低于30時(shí)為復(fù)雜多峰函數(shù),mdABC在迭代到500次時(shí)已求得最優(yōu)值0,在維度等于和高于30變?yōu)閱畏搴瘮?shù)時(shí),在迭代到80次左右就已求得最優(yōu)值0。綜上,mdABC算法相對(duì)于標(biāo)準(zhǔn)ABC算法在收斂速度和求解精度上都得到了很大程度的改善。

圖1 函數(shù)迭代曲線

5 結(jié)束語(yǔ)

針對(duì)ABC算法在高維函數(shù)優(yōu)化問(wèn)題上收斂速度慢、易陷入局部最優(yōu)的問(wèn)題,本文提出了包含擾動(dòng)機(jī)制的多維貪婪搜索mdABC算法。實(shí)驗(yàn)結(jié)果表明,該算法在求解精度和收斂速度上都優(yōu)于標(biāo)準(zhǔn)ABC算法,在保持深度挖掘和廣度搜索上的平衡方面表現(xiàn)出良好的性能。本文僅針對(duì)ABC算法的搜索機(jī)制進(jìn)行了研究,在此基礎(chǔ)上對(duì)種群初始化方法、觀察蜂確定食物源方法的研究將是下一步工作的重點(diǎn)。

［1］ Karaboga D.An Idea Based on Honey Bee Swarm for Numerical Optimization［R］.Kayseri,Turkey:Erciyes University,Technical Report:TR06,2005.

［2］ Karaboga D,Basluzk B.A Powerfuland Efficient Algorithm for Numerical Function Optimization: Artificial Bee Colony(ABC)Algorithm［J］.Journal of Global Optimization,2007,39(3):459-471.

［3］ Karaboga D,Basluzk B.On the Performance of Artificial Bee Colony(ABC) Algorithm［J］.AppliedSoft Computing,2008,8(1):687-697.

［4］ Karaboga D,Akay B.Artificial Bee Colony(ABC), Harmony Search and Bees Algorithms on Numerical Optimization［C］//Proceedings of Innovative Production Machines and Systems Virtual Conference.Melikgazi, Turkey:［s.n.］,2009.

［5］ Alatas B.Chaotic Bee Colony Algorithms for Global Numerical Optimization［J］.ExpertSystemswith Applications,2010,37(8):5682-5687.

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

［7］ 暴 勵(lì),曾建潮.自適應(yīng)搜索空間的混沌蜂群算法［J］.計(jì)算機(jī)應(yīng)用研究,2010,27(4):1330-1334.

［8］ Gao Weifeng,Liu Sanyang.A Modified Artificial Bee Colony Algorithm ［J］.Computers & Operations Research,2012,39(3):687-697.

［9］ 丁海軍,馮慶嫻.基于Boltzmann選擇策略的人工蜂群算法［J］.計(jì)算機(jī)工程與應(yīng)用,2009,45(31):53-55.

［10］ 向萬(wàn)里,馬壽峰.基于輪盤(pán)賭反向選擇機(jī)制的蜂群優(yōu)化算法［J］.計(jì)算機(jī)應(yīng)用研究,2013,30(1):86-89.

［11］ Zhu Guopu,Kwong S.Gbest-guided ArtificialBee Colony Algorithm for Numerical Function Optimization［J］.Applied Mathematics and Computation,2010,217 (7):3166-3173.

［12］ Banhaznsakun A,AchalakulT,SizinaovakulB.The Best-so-Far Selection in Artificial Bee Colony Algorithm［J］.Applied Soft Computing,2011,11(2):2888-2901.

［13］ 王慧穎,劉建軍,王全洲.改進(jìn)的人工蜂群算法在函數(shù)優(yōu)化問(wèn)題中的應(yīng)用［J］.計(jì)算機(jī)工程與應(yīng)用,2011,47 (13):36-39.

［14］ Gao W F,Liu S Y.Improved Artificial Bee Colony Algorithm for Global Optimization［J］.Information Processing Letters,2011,111(17):871-882.

［15］ 向萬(wàn)里,馬壽峰.基于向量整體擾動(dòng)的快速收斂人工蜂群算法［J］.計(jì)算機(jī)應(yīng)用研究,2013,30(5): 1329-1333.

編輯 顧逸斐

Artificial Bee Colony Algorithm Based on Multi-dimensional Greedy Search

ZHANG Suqi1,TENG Jianfu1,GU Junhua2
(1.School of Electronic Information Engineering,Tianjin University,Tianjin 300072,China;
2.School of Computer Science and Software,Hebei University of Technology,Tianjin 300401,China)

Artificial Bee Colony(ABC)algorithm can be efficiently employed to solve the multimodal and high dimensional function optimization problem.However,low search speed and premature convergence frequently appear with more complex problem.In order to improve the algorithm performance,this paper proposes a new artifciall bee colony algorithm.It introduces a search equation based on multi-dimensional greedy search to enhance local search and avoid the solution to be abandoned which achieves optimum value in some dimensions but reach the maximum update limit.New algorithm also adds a disturbance mechanism to avoid obtaining partial optimal solutions when premature convergence in a few dimensions.Experimental results show the new algorithm can balance the exploitation and exploration,has more fast convergence speed and better computational precision in solving the multimodal and high dimensional function optimization problem.

Artificial Bee Colony(ABC)algorithm;function optimization;greedy search;disturbance search;depth excavation;scope search

1000-3428(2014)11-0189-05

A

TP301.6

10.3969/j.issn.1000-3428.2014.11.037

天津市應(yīng)用基礎(chǔ)與前沿技術(shù)研究計(jì)劃基金資助重點(diǎn)項(xiàng)目(13JCZDJC26300)。

張素琪(1980-),女,博士研究生,主研方向:信號(hào)處理,數(shù)據(jù)挖掘;滕建輔、顧軍華,教授、博士。

2013-12-02

2013-12-31E-mail:suqizhang80@163.com

中文引用格式:張素琪,滕建輔,顧軍華.基于多維貪婪搜索的人工蜂群算法［J］.計(jì)算機(jī)工程,2014,40(11):189-193.

英文引用格式:Zhang Suqi,Teng Jianfu,Gu Junhua.Artificial Bee Colony Algorithm Based on Multi-dimensional Greedy Search［J］.Computer Engineering,2014,40(11):189-193.