一種帶搜索因子的全局最優(yōu)人工蜂群算法

常扣扣,火久元,梅 凱

(蘭州交通大學 電子與信息工程學院， 蘭州 730070)

?

一種帶搜索因子的全局最優(yōu)人工蜂群算法

?？劭?火久元,梅 凱

(蘭州交通大學 電子與信息工程學院， 蘭州 730070)

針對全局最優(yōu)人工蜂群算法(GABC)搜索迭代過程中未充分考慮到全局優(yōu)化和局部優(yōu)化在優(yōu)化過程中的作用，在一定程度上降低了算法的全局搜索能力，容易陷入局部最優(yōu)解的問題，提出了一種帶搜索因子的全局最優(yōu)人工蜂群算法(HF-GABC)。在最優(yōu)人工蜂群(GABC)算法中引入了可以隨著優(yōu)化過程動態(tài)搜索的因子，在算法的全局搜索過程和局部搜索過程中進行動態(tài)搜索。應用改進的算法對4個標準測試集函數(shù)進行仿真試驗，并與ABC算法、GABC算法的結果進行比較。實驗結果表明：帶搜索因子的人工蜂群算法收斂性能優(yōu)于ABC和GABC算法，有效降低了局部收斂的可能性，并且提高了搜索精度。

全局最優(yōu)人工蜂群算法；全局優(yōu)化；局部優(yōu)化；動態(tài)調節(jié)；搜索因子

隨著科技的進步，人們在工程領域所遇到的問題越來越復雜。研究人員根據(jù)生物群體所表現(xiàn)的行為，對其群體活動比如尋找食物的過程進行模擬，建立了一系列的數(shù)學模型，用于解決工程實踐過程中的函數(shù)優(yōu)化問題，即群體智能優(yōu)化。群體智能是指復雜行為的特性由許多簡單的個體通過相互交互表現(xiàn)出來的智能[1]。比較常見的群體智能仿生算法有人工蜂群算法(ABC)[2]、人工魚群算法(AFSA)[3]、遺傳算法(GA)[4]、粒子群優(yōu)化算法(PSO)[5]等。

人工蜂群算法(artificial bee colony algorithm,ABC算法)是一種模擬蜜蜂群體合作覓食行為的群體智能優(yōu)化算法，由土耳其學者Karaboga于2005年首次系統(tǒng)地提出[2]。由于該算法具有操作簡單、控制參數(shù)較少、收斂速度較快、易于實現(xiàn)等特點，吸引了越來越多的學者研究，并廣泛應用于實際的優(yōu)化問題中。文獻[6]針對K-means聚類算法中對初始聚類中心敏感、易陷入局部最優(yōu)等缺點，提出一種基于K-means的人工蜂群聚類算法，提高了聚類算法的聚類效果，改善了K-means的穩(wěn)定性。文獻[7]利用人工蜂群算法解決了圖形染色問題。

基本人工蜂群算法的函數(shù)優(yōu)化過程中依靠貪婪性方法選擇最優(yōu)解，廣度與深度搜索不夠充分，搜索精度不高，容易陷入局部最優(yōu)解，影響算法的性能。因此，許多學者進行了對基本ABC算法的改進研究。文獻[8]引入混沌思想，降低了ABC算法陷入局部最優(yōu)解的可能性，提高了搜索速度和精度。文獻[9]提出一種基于細菌趨藥性和當前最優(yōu)解策略的人工蜂群算法，提高算法尋優(yōu)性能。文獻[10]提出了全局最優(yōu)人工蜂群算法(gbest-guided artificial bee colony algorithm,GABC算法)。GABC算法提高了深度搜索能力，收斂速度也有了較大提升。但GABC算法未充分考慮到全局優(yōu)化和局部最優(yōu)在優(yōu)化過程中的作用，導致算法的優(yōu)化精度和優(yōu)化效率提升不夠。因此，本文提出了一種帶搜索因子的GABC算法(HF-GABC)，通過增加可以根據(jù)進化過程動態(tài)變化的搜索因子來平衡人工蜂群算法的局部搜索和全局搜索能力，從而提升算法效率和提高算法精度。

1 基本人工蜂群算法(ABC算法)

人工蜂群算法模擬蜜蜂覓食機制進行函數(shù)優(yōu)化問題的處理，基本人工蜂群算法模擬蜜蜂采蜜的過程，分為初始化階段、雇傭蜂階段、觀察蜂階段和偵查蜂階段4部分[2]：① 初始化階段：參數(shù)初始化，包括蜂群總數(shù)、最大迭代次數(shù)和最大停止次數(shù)。② 雇傭蜂階段：根據(jù)其記憶在蜜源附近進行隨機鄰域搜索，并將蜜源信息傳遞給觀察蜂。當蜜源開采完之后，雇傭蜂的角色變成偵查蜂。③ 觀察蜂階段：根據(jù)雇傭蜂傳遞的蜜源適應度信息進行優(yōu)秀蜜源的選擇，然后在其附近進一步搜索優(yōu)秀蜜源。④ 偵查蜂階段：放棄適應度差的蜜源并尋找新的蜜源。3種蜜蜂相互合作，最終達到函數(shù)優(yōu)化的目的。算法流程如圖1所示。

基本人工蜂群算法詳細描述：

步驟1 初始化。算法隨機生成SN個蜜源，蜂群數(shù)目為NP,最大迭代次數(shù)為maxcycle，最大停滯次數(shù)為limit，在給定的取值范圍內按照式(1)隨機產生SN個花蜜源信息：X={Xij|i=1,2,3,…,SN;j=1,2,3,…,D}，并根據(jù)式(2)計算該蜜源的適應度值fitness。

Xij=bj+rand(0,1)(aj-bj)

(1)

(2)

式(1)中rand(0,1)表示(0,1)之間的分布均勻的隨機數(shù)，控制鄰域搜索范圍。D為優(yōu)化空間的維數(shù)，aj和bj分別表示第j維數(shù)據(jù)的上限和下限。確定算法的結束條件和花蜜源停滯最大次數(shù)limit。

圖1 ABC算法流程

步驟2 雇傭蜂階段。雇傭蜂根據(jù)式(3)在其當前位置附近進行鄰域搜索，產生1個新的候選蜜源并計算其適應度值fitness。

Vij=Xij+φij(Xij-Xkj)

(3)

式(3)中φij為[-1，1]之間的隨機數(shù)，k不等于j。如果新的蜜源Vij的適應度好于Xij，則用新花蜜源Vij的位置代替舊花蜜源Xij的位置；否則，仍然維持舊花蜜源位置不變，同時將花蜜源的停滯次數(shù)加1。

步驟3 觀察蜂階段。在此過程中，觀察蜂按照輪盤賭選擇雇傭蜂搜索到的花蜜源，根據(jù)雇傭蜂更新花蜜源位置的方法對當前花蜜源進行位置更新，其中較優(yōu)花蜜源有可能被多次更新，選擇概率為

(4)

步驟4 偵察蜂階段。統(tǒng)計每個花蜜源的停滯次數(shù)，當停滯次數(shù)達到limit仍沒有找到適應度值更高的花蜜源時，則需要放棄當前的花蜜源，并根據(jù)給定的取值范圍內隨機產生一個新的花蜜源位置。

步驟5 判斷解是否滿足要求。記錄當前的最優(yōu)蜜源是否為全局最優(yōu)位置，是則輸出全局最優(yōu)解，否則轉步驟2進行下一次迭代。

2 全局最優(yōu)人工蜂群算法(GABC算法)

在搜索過程中ABC算法的收斂性能受到蜜蜂深度搜索不夠充分、優(yōu)秀個體不能充分進化的影響。另外，人工蜂群算法缺乏對花蜜源最優(yōu)解的保護，可能會導致最優(yōu)花蜜源被拋棄，算法難以收斂于全局最優(yōu)解。朱國普等[10]提出一種名為gbest-guided ABC algorithm(GABC) 的算法。該算法用式(5)取代原始ABC算法中的式(2)。

Vij=Xij+φij(Xij-Xkj)+φij(Yj-Xij)

(5)

式中：φij是[-1,1]中的一個隨機數(shù)，是[0,C](C是一個正數(shù))中的一個隨機數(shù)；Yj是第j維空間的最優(yōu)解。如果新的蜜源Vij的適應度好于Xij，則用新花蜜源Vij的位置代替舊花蜜源Xij的位置，否則，仍然維持舊花蜜源位置不變，同時將花蜜源的停滯次數(shù)加1并判斷花蜜源的停滯次數(shù)是否達到limit。如果新的蜜源Vij的適應度好于Xij,則用新的花蜜源Vij代替舊的花蜜源Xij;否則仍然維持舊的花蜜源，并判斷花蜜源的停滯次數(shù)是否達到limit。依此規(guī)律，將所有的雇傭蜂所攜帶的花蜜源信息更新完畢。

3 GABC算法的改進及實驗

在GABC算法中，仍然保留著ABC算法的主要特性。GABC算法通過蜜蜂個體進行搜索并根據(jù)個體與鄰域之間的共享信息探索較高質量的花蜜源。在尋優(yōu)過程中，隨著搜索的進行，鄰域個體之間的共享信息會減少。由于蜜蜂的尋優(yōu)過程并沒有和鄰域個體位置之間的擾動系數(shù)φij相結合，因此GABC算法未充分考慮到全局優(yōu)化和局部最優(yōu)在優(yōu)化過程中的作用，通過φij(Yj-Xij)項來平衡算法的探索和開發(fā)能力在一定程度上降低了算法的全局尋優(yōu)能力，沒有更好地體現(xiàn)出對蜂群尋優(yōu)進程的控制，導致算法的優(yōu)化精度和優(yōu)化效率提升仍然不夠。因此，本文針對GABC算法中存在的缺陷，提出一種改進GABC算法，即帶搜索因子的GABC算法。

3.1 帶搜索因子的GABC算法

為了提高GABC算法的廣度搜索和深度搜索能力，本文結合文獻[11]和[12]引入了搜索因子，通過調整搜索因子，動態(tài)地控制算法的搜索能力，提出了一種帶搜索因子的GABC算法(HF-GABC)。在搜索過程中，為了進一步控制蜜蜂個體間的信息共享程度和算法的全局搜索精度，本文引入了2個搜索因子：局部搜索因子和全局搜索因子?；谒阉饕蜃拥腉ABC算法用式(6)代替式(5)進行搜索：

Vij=Xij+δφij(Xij-Xkj)+λφij(Yj-Xij)

(6)

圖2 全局搜索因子和局部搜索因子隨迭代次數(shù)的變化取值

3.2 HF-GABC算法的性能測試

為了驗證改進后算法HF-GABC的優(yōu)化性能，與ABC、GABC進行對比實驗。參數(shù)設置：最大迭代次數(shù)maxcycle=5 000,種群個數(shù)NP=20,蜜源個數(shù)SN=10，最大停滯次數(shù)limit=100。選取4個標準測試集函數(shù)進行性能測試，每個測試函數(shù)獨立運行30次，取平均值。測試集函數(shù)屬性如下所示：

Griewank函數(shù)：

[-600,600]D

Rastrigin函數(shù)：

[-5.12,5.12]D

Sphere函數(shù)：

Rosenbrock函數(shù)：

[-50,50]D

f1和f2函數(shù)為多峰值函數(shù)，理論最優(yōu)值為0；f3和f4函數(shù)為單峰值函數(shù)，理論最優(yōu)值也為0。

實驗在系統(tǒng)為32位win7系統(tǒng)、處理器為Intel(R) Core(TM)i3、內存為4G的計算機上實現(xiàn)。程序采用java語言實現(xiàn)。表1是ABC、GABC、HF-GABC三種算法對上述4種函數(shù)進行優(yōu)化的實驗結果比較。

由表1可見：對于多峰值函數(shù)Griewank(當D=30和D=60)和Rastrigin(當D=30和D=60)，HF-GABC的優(yōu)化效果更好，尤其是對Rastrigin，能達到理論上的最優(yōu)值；對于難以優(yōu)化的單峰值函數(shù)Sphere(當D=30和D=60)和Rosenbrock(當D=2和D=3)，HF-GABC的優(yōu)化效果比ABC和GABC更優(yōu)。改進之后的HF-GABC的均值與方差均優(yōu)于ABC算法和GABC算法，在收斂精度和算法穩(wěn)定性上更優(yōu)。

表1 3種算法對標準函數(shù)優(yōu)化結果比較

由圖3～10可知：由于在算法初始化時采用的隨機策略，故3種算法的初始最優(yōu)值并無明顯差別。隨著算法的不斷迭代，3種算法不斷改善當前最優(yōu)值。ABC算法出現(xiàn)了最優(yōu)解的丟失現(xiàn)象，由于對最優(yōu)解保護的缺乏，所以收斂精度也相對較差。GABC算法雖能在較少的迭代次數(shù)內找到較優(yōu)的解，但全局尋優(yōu)結果仍不理想。HF-GABC算法獲得了最優(yōu)的結果，且算法向好的方向收斂的性能可得到保證。

圖3 Griewank函數(shù)為30維時的優(yōu)化過程

圖4 Griewank函數(shù)為60維時的優(yōu)化過程

圖5 Rastrigin函數(shù)為30維時的優(yōu)化過程

圖6 Rastrigin函數(shù)為60維時的優(yōu)化過程

圖7 Sphere函數(shù)為30維時的優(yōu)化過程

圖8 Sphere函數(shù)為60維時的優(yōu)化過程

圖9 Rosenbrock函數(shù)為2維時的優(yōu)化過程

圖10 Rosenbrock函數(shù)為3維時的優(yōu)化過程

4 結束語

HF-GABC算法是在GABC算法基礎上，充分考慮到全局優(yōu)化和局部最優(yōu)在優(yōu)化過程中的作用，加入了搜索因子，可以更好地控制GABC算法的優(yōu)化過程，在保證算法開發(fā)能力的同時整體提高了算法的全局尋優(yōu)能力，降低了陷入局部最優(yōu)的可能性，使算法能在較短的時間內獲得收斂。與ABC、GABC算法的對比實驗結果表明： HF-GABC算法無論是在搜索精度還是算法穩(wěn)定性方面均具有更好的性能優(yōu)勢。

[1] BONABEAU E,DORIGO M,THERAULAZ G.Swarm Intelligence:From Natural to Artificial Systems[M].New York:Oxford University Press,1999.

[2] KARABOGA D,AKAY B.A Comparative Study of Artificial Bee Colony Algorithm[J].Applied Mathematics and Computation.2009,214(1):108-132.

[3] 李曉磊.一種新型的智能優(yōu)化方法-人工魚群算法[D].杭州：浙江大學,2003.

[4] HOLLAND J H.Adaptation in natural and artificial system:an introductory analysis with applications to biology,control,and artificial intelligence[M].2nd ed.Cambridge:MIT Press,1992.

[5] KENNEDY J,EBERHART R C.Partucle Swarm Optimization[C]//Proc.of IEEE International Conference on Neural Networks,IV.Piscataway,NJ,USA:IEEE Service Center,1995:1942-1948.

[6] KARABOGA D,AKAY B.A Comparative Study of Artificial Bee Colony Algorithm[J].Applied Mathematics and Computation.2009,214(1):108-132.

[7] 曹永春，蔡正琦，邵亞斌.基于K-means的改進人工蜂群聚類算法[J].計算機應用，2014，34(1)：204-207.

[8] MOHAMADI S A,DERAKHSHI M R F,AKBARI R.ANAdaptive Multi-Objective Artificial Bee Colony with Crowding Distance Mechanism[C]//Proceedings of 16thCSI International Symposium on Artificial Intelligence and Signal Processing.Shiraz:[s.n.],2012:68-73.

[9] 周長喜，毛利，吳濱，等.基于細菌趨藥性和當前最優(yōu)解策略的人工蜂群算法[J].計算機應用與軟件，2016，33(1)：268-272.

[10]王冰.基于局部最優(yōu)解的改進人工蜂群算法[J].計算機應用研究，2014，31(4)：1023-1026.

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

[12]王輝.一種帶共享因子的人工蜂群算法[J].計算機工程，2011,37(22)：140.

[13]劉立群.基于全局共享因子的混合蛙跳算法[J].計算機工程，2013,39(10)：163.

(責任編輯 楊黎麗)

A Gbest-Guided Aritificial Bee Colony Algorithm with Hunting Factor

CHANG Kou-kou, HUO Jiu-yuan, MEI Kai

(School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China)

Aiming at the problem that the Gbest-guided artificial bee colony (GABC) algorithm is not considered the role of global optimization and local optimization in the optimization process in the iterative process, and is easily to fall into the local optimal solution, a Gbest-guided ABC algorithm based on hunting factor (HF-GABC) is proposed in this paper. In the Gbest-guided artificial bee colony algorithm for numerical function optimization (GABC), the factors that can be dynamically hunted with the optimization process are introduced in the process of global optimization and local search. The simulation experiments were taken on four standard test functions and the improved algorithm were compared with the ABC algorithm and the GABC algorithm. The experimental results show that the convergence rate of HF-ABC algorithm performs better than the ABC and GABC algorithm, which effectively reduces the possibility of local convergence and improves the search precision.

Gbest-guided artificial bee colony algorithm; global optimization; local optimization; dynamic regulatory; hunting factor

2017-03-05

國家自然科學基金資助項目(61462058)；蘭州市科技計劃資助項目(2014-1-127)；蘭州市人才創(chuàng)新創(chuàng)業(yè)科技計劃資助項目(2014-RC-4)

?？劭?1991—),男,安徽宿州人,碩士研究生,主要從事智能計算、數(shù)據(jù)挖掘等研究，E-mail:929775937@qq.com； 火久元(1978—),男,甘肅蘭州人,博士研究生,副教授,主要從事智能計算、數(shù)據(jù)挖掘等研究，E-mail:huojy@lzb.ac.cn。

?？劭?火久元,梅凱.一種帶搜索因子的全局最優(yōu)人工蜂群算法[J].重慶理工大學學報(自然科學)，2017(6):160-165.

format：CHANG Kou-kou, HUO Jiu-yuan, MEI Kai.A Gbest-Guided Aritificial Bee Colony Algorithm with Hunting Factor[J].Journal of Chongqing University of Technology(Natural Science)，2017(6):160-165.

10.3969/j.issn.1674-8425(z).2017.06.024

TP301.6

A

1674-8425(2017)06-0160-06