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

張素琪,滕建輔,顧軍華

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

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

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

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

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

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

1 概述

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

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

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

Step 1 初始化n個食物源的位置:

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

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

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

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

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

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

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

3 多維貪婪搜索ABC算法

3.1 多維貪婪搜索

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

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

(1)隨機選擇當前食物源附近的第k個食物源來計算x′ij:

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

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

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

3.2 擾動搜索

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

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

3.3 mdABC的基本流程

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

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

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

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

表1 標準測試函數(shù)

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

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

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

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

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

5 結(jié)束語

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

［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］ 暴 勵,曾建潮.自適應(yīng)搜索空間的混沌蜂群算法［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］.計算機工程與應(yīng)用,2009,45(31):53-55.

［10］ 向萬里,馬壽峰.基于輪盤賭反向選擇機制的蜂群優(yōu)化算法［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］ 王慧穎,劉建軍,王全洲.改進的人工蜂群算法在函數(shù)優(yōu)化問題中的應(yīng)用［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］ 向萬里,馬壽峰.基于向量整體擾動的快速收斂人工蜂群算法［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ù)研究計劃基金資助重點項目(13JCZDJC26300)。

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

2013-12-02

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

中文引用格式:張素琪,滕建輔,顧軍華.基于多維貪婪搜索的人工蜂群算法［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.